In this section some exercises about concurrent programming will be presented. The solutions of the exercises are provided using a pseudo-code similar to the C programming language. The functions P() and V() have the same behavior of the POSIX functions sem_wait() and sem_post(), respectivelly. Assume that it is possible to define and to initialize a semaphore with a pseudo-statement like: sem_t <initial_value>;. The variables with name m (m, m1, m2, …) are semaphore used as mutex.

It is assumed, for all the exercises, that the threads used for the implementation of the concurrent program have already been created. Indeed, the purpose of the exercises is to realize only the functions that allow the synchronization and the communication between these concurrent threads. For a complete running program, to the provided solution, the function pthread_create() should be added, in order to start the execution of the threads.

An undefined number of threads T_i can call the functions int p(int prio, int value_p) and int v(int value_v). These functions must simulate (by using classical semaphores and under the hypothesis that the threads are queued by these semaphores in a FIFO order), the behavior of semaphores that queue threads in an order depending on the value of the variable prio, that is an argument of the function p() (0 < = prio < = 9, prio=9 is the maximum priority).
The behavior of the two functions is:

• int p(int prio, int value_p): when the value of the semaphore is a number greater than 0, the function decreases of one the value and returns 0. In the case the value of the semaphore is 0, the function is blocking. When unblocked by the calling of the v() function, the function p() must return to the caller the value value_v, previously passed as argument to the function v().
• int v(int value_v): if executed when no thread is blocked on p(), it increments of one the value of the semaphore and returns 0. In the case at least a thread is blocked on p(), the function must unblock the blocked thread with higher priority and it must return the value value_p, passed as argument to the function p(). In the case of more than two threads with the same priority are blocked by the semaphore, the following v() will unblock one of the threads.

The semaphore is initialized to the value 2 (i.e., sem=2).

Realize the functions int p(int prio, int value_p) and int v(int value_v).

Example:

• T₁ calls p(3, 10) that sets the semaphore sem=1 and it returns 0
• T₁ calls p(4, 20) that sets the semaphore sem=0 and it returns 0
• T₁ calls p(4, 30) that blocks T₁
• T₂ calls p(7, 15) that blocks T₂
• T₃ calls v(14) that unblocks the thread T₂, because 7 > 4. The function p() returns to T₂ the value 14 and the function v() returns to T₃ the value 15
• T₃ calls v(35) that unblocks the thread T₁. The function p() returns to T₁ the value 35 and the function v() returns to T₃ the value 30
• P₃ calls v(16) that sets the semaphore sem=1 and it returns 0

solution_es1_semaphores.c

#define NPRIO 10
 
sem_t wait[NPRIO]={0,0....};
int nBlockedPrio[NPRIO]={0,0,...};
int nBlocked=0;
int pass = 0;
int sem=2;
sem_t sync=0;
 
 
int p(int prio, int value_p){
  int ret;
 
  P(m);
  if(sem==0){
    nBlocked++;
    nBlockedPrio[prio]++;
    V(m);
    P(wait[prio]);
    ret=pass;
    pass=value_p; 
    V(sync);
    return ret;
  }else{
    sem--;
    V(m);
    return 0;
  }
}
 
 
int v(int value_v){
  int ret;
 
  P(m);
  if(nBlocked){
    for(i=NPRIO-1; i>=0; i--){
      if (nBlockedPrio[i]){
        nBlockedPrio[i]--;
        nBlocked--;
        pass = value_v;
        V(wait[i]);
        P(sync);
        ret=pass;
        V(m);
        return ret;
      }
    }
  }else{
    sem++;
    V(m);
    return 0;
  }
}

An undefined number of threads C_i can call the function int bConsume() and only one thread P can call the function void bProduce(int value).

The behavior of the two functions is:

• int bConsume() is blocking while waiting that the thread P calls the function bProduce(int value). The function bProduce(int value), when called, will unblock all the thread blocked on int bConsume(). The function int bConsume() must return to any unblocked thread the value value passed as an argument to the function bProduce(int value).
• bProduce(int value), in the case some threads are blocked by int bConsume(), it must unblock such threads and it must pass to them the value value. In the case no thread is blocked by the function int bConsume(), it must block the process P waiting that a thread executes the function int bConsume(). After unblocking the thread P, the function bProduce(int value) must pass the value value to the function int bConsume() that, because in this case it does not block any thread, it will return immediately the value value to the calling thread.

Realize the functions int bConsume() and bProduce(int value).

Example:

• C₁ calls bConsume() and it blocks on it
• C₂ calls bConsume() and it blocks on it
• P calls bProduce(21) which unblocks the threads C₁ and C₂ that are blocked on bConsume(). The function bConsume() returns to both threads the value 21
• P calls bProduce(12) and it blocks on it
• C₂ calls bConsume() that unblocks the threads P and returns to the thread C₂ the value 12
• C₁ calls bConsume() and it blocks on it

solution_es2_semaphores.c

int pBlocked=0, cBlocked=0, pass;
sem_t pWait=0, cWait=0;
sem_t m=1, m2=1;
 
 
void bProduce(int value){
  int localCBlocked, c;
 
  P(m);
  if(cBlocked==0){
    pBlocked++;
    V(m);
    P(cWait);
  }
  localCBlocked = cBlocked;
  pass = value;
 
  for(c=0; c<localCBlocked; c++) V(pWait);
}
 
 
int bConsume() {
  int ret;
 
  P(m);
  cBlocked++;
  if(pBlocked){
    pBlocked--;
    V(cWait);
  }else{
    V(m);
  }
 P(pWait);
 
  P(m2);
  cBlocked--;
  ret = pass;
  if(cBlocked==0) V(m);
  V(m2);
}

An undefined number of threads T_i can call the function int val(int v) and only one thread M can call the function void mul(int m).

The behavior of the two functions is:

• int val(int v) blocks the calling thread waiting for the thread M calls the function void mul(int m). When the function void mul(int m) is called by the process M, it must unblock all the threads T blocked until that moment by int val(int v). To each unblocked thread T, the function int val(int v) must return the value v multiplied by the value m.
• void mul(int m), besides the behavior described in the preceding point, in the case no thread is blocked by int val(int v), it must block the calling process waiting for a thread of type T that calls the function int val(int v). When such an event happens, the thread M must be unblocked, and the function int val(int v), called by the thread T, must immediately return the value v*m.

Realize the functions int val(int v) and void mul(int m).

Example:

• T₁ calls val(3) and it blocks on it
• T₂ calls val(5) and it blocks on it
• M calls mul(2) which unblocks the threads T₁ and T₂ blocked on val(). The two functions val() will return to the calling threads, T₁ and T₂, the values 3*2=6 and 5*2=10, respectively
• M calls mul(3) and it blocks on it
• T₂ calls val(4) which unblocks the thread M and it will return immediately to the thread T₂ the value 4*3=12

solution_es3_semaphores.c

sem_t m1=1, m2=1, sync=0, syncMul=0;
int n=0, s=0, mean=0, meanBlock=0;
 
 
int sum(int x){
  int ret;  
 
  P(m1);
  if(meanBlock){
    s=x;
    V(syncMul);
    ret = mean;
    P(sync);
    V(m1);
    return ret;
  }else{
    s += x;
    n++;
    V(m1);
    P(sync);
    ret = mean;
    P(m2)
    n--;
    if(n==0) V(m1);
    V(m2);
    return ret;
  }
}
 
 
void mul(int m){
  int c;
 
  P(m1);
  if(n>0){
    mean = s*m;
    for (c=0; c<n;c++){
      V(sync);
    }
  }else{
    meanBlock+=1;
    V(m1);
    P(syncMul);
    mean = s*m;
    V(sync);
  }
}

An undefined number of threads T_i can call the functions int wait(int w_prio, int max_proc) and int unblock(int s_prio, int value). The parameters w_prio and s_prio can assume values between 0 and 9.

The behavior of the two functions is:

• int wait(int w_prio, int max_proc) is blocking if the total number of threads blocked until it calling is less than max_proc, alternatively the function wait returns the value -1. If the threads blocked by wait are unblocked by the function unblock, the function wait must return the value value (passed as an argument of the function unblock).
• int unblock(int s_prio, int value) unblocks all the threads blocked by the function wait that have the value w_prio equal to s_prio. The function wait must return to all the unblocked thread the value value. The function unblock returns the number of unblocked thread (or -1 in the case no thread is unblocked).

Pay particular attention to the fact that the value value is returned correctly to all the unblocked threads and that the threads T_i, that execute the function wait after the function unblock, are properly unblocked by the function wait.

Realize the functions int wait(int w_prio, int max_proc) and int unblock(int s_prio, int value).

Example:

• T₁ calls wait(3,2) and it blocks on it
• T₂ calls wait(3,4) and it blocks on it
• T₃ calls wait(5,2) that returns immediately -1, because the total number of threads blocked by the function wait is 2 that is not smaller than the value max_proc=2
• T₃ calls wait(5,3) and it blocks on it
• T₄ calls unblock(3,6) that unblocks the threads T₁ and T₂. The function wait returns to both threads the value 6. The function unblock returns to T₄ the value 2
• T₁ calls unblock(2,7) that return immediately the value -1, because it does not unblock any thread

soluzion_es4_semaphores.c

#define N_CLASSES 10
 
int value_pass;
int nwait = 0;
int nwait_prio[N_CLASSES] = {0,0,...};
sem_t sync[N_CLASSES] = {0,0,...};
sem_t mutex = 1, mutex2 = 1;
 
 
int wait(int w_prio, int max_proc){
  int res;
 
  P(mutex);
  if (nwait >= max_proc){
    V(mutex);
    return -1;
  }else{
    nwait_prio[w_prio]++;
    nwait++;
    V(mutex);
    P(sync[w_prio]);
 
    P(mutex2);
    res = value_pass;
    nwait--;
    nwait_prio[w_prio]--;
    if (nwait_prio[w_prio]==0) V(mutex);
    V(mutex2);
    return res;
  }
}
 
 
int unblock(int s_prio, int value){
  int c, res;
 
  P(mutex);
  if (nwait_prio[s_prio] > 0){
    res = nwait_prio[s_prio];
    value_pass = value;
    for(c=0; c<res; c++){
      V(sync[w_prio]);
    }
  }else{
    res = 0;
    V(mutex);
  }
  return res;
}