Process syncronization with semaphore primitives

Question

How would you complete this scheme and how many semaphores would you use to obtain

a) ABCD ACBD sequence

b) ABCD ABDC sequence

using these two processes (consider using pseudocode es: wait(s1) signal(s1) etc...)

Process 1

P1:while(1){
        .
        printf("A");
        .
        .
        printf("C");
        .
   }       

Process 2

 P2:while(1){
        .
        printf("B");
        .
        .
        printf("D");
        .
   }

Consider the dots as places where the missing code(primitives) could be inserted

@Jerry

After some internet researching I think I've got my first point (a) solved,

the solution would be to build a precedence graph like this

      A<--(s0)--^
     / \        |
(s1)-- --(s2)   |
(me)-------     |
    /   \       |
   B     C      |
    \   /       |
   -------(s3)  |
     \ /        |
      D-------->|

with INIT(s0)=INIT(ME)=1 and INIT(s1)=INIT(s2)=INIT(s3)=0

therefore I'd have P1

P1:while(1){
       wait(s0);
       printf("A");
       signal(s2);
       signal(s1);

       wait(s1);
       wait(ME);
       printf("C");
       signal(ME);
       signal(s3)
   }

and P2

P2:while(1){
       wait(s2);
       wait(ME);
       printf("B");
       signal(s3);
       signal(ME);

       wait(s3);
       wait(s3);
       printf("D");
       signal(s0)
   }

Do you think my approach is right ?, could I reduce more the number of semaphores used ? (for now there are 5 (2 mutex and 3 normal))

Answer 1

I do think your approach with a precedence graph is correct, but the problem statement is a bit unclear, for example, from the graph is looks like B and C can occur in any order, but no indication of this in the original a) and b) sequences.

(EDIT: it become clear that B and C have to alternate)

So, for case a) the following (infinite) sequence is acceptable:

ABCD ACBD ABCD ACBD ABCD ACBD ...

  A<--+
 / \  |
B<->C |
 \ /  |
  D---+

A precedes B by program logic and they are in the same thread. Likewise C precedes D for the same reasons. Hence, semaphores are needed to enforce precedence only along the edges A->C, B->D and D->A. The edge between B and C changes direction each cycle, hence we need an additional bit of state, to determine the direction: B->C or B<-C It can be done with an extra variable, or we can maintain the state implicitly by duplicating the loop bodies, like below:

#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>

#define NLOOPS 100000

sem_t s0, s1, s2, s3;

void *
process_A (void *unused)
{
  int n = NLOOPS;

  while (n--)
    {
      sem_wait (&s0);
      putchar ('A');
      sem_post (&s1);
      putchar ('B');
      sem_post (&s3);
      sem_post (&s2);

      sem_wait (&s0);
      putchar ('A');
      sem_post (&s1);
      sem_wait (&s3);
      putchar ('B');
      sem_post (&s2);
    }

  return 0;
}

void *
process_B (void *unused)
{
  int n = NLOOPS;

  while (n--)
    {
      sem_wait (&s1);
      sem_wait (&s3);
      putchar ('C');
      sem_wait (&s2);
      putchar ('D');
      sem_post (&s0);

      sem_wait (&s1);
      putchar ('C');
      sem_post (&s3);
      sem_wait (&s2);
      putchar ('D');
      sem_post (&s0);
    }

  return 0;
}


int
main ()
{
  pthread_t a, b;

  sem_init (&s0, 0, 1);
  sem_init (&s1, 0, 0);
  sem_init (&s2, 0, 0);
  sem_init (&s3, 0, 0);

  pthread_create (&a, 0, process_A, 0);
  pthread_create (&b, 0, process_B, 0);

  pthread_join (a, 0);
  pthread_join (b, 0);

  putchar ('\n');
  return 0;
}

I will leave you to implement b) by yourself :)