Table of Contents

Exercises about concurrent programming (Pseudo-code)

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.

Exercise 1 (Semaphore with priority)

An undefined number of threads Ti 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:

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:

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;
  }
}

Example 2 (Message broadcast)

An undefined number of threads Ci 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:

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

Example:

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);
}

Example 3 (Multiplication between threads)

An undefined number of threads Ti 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:

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

Example:

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);
  }
}

Example 4

An undefined number of threads Ti 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:

Pay particular attention to the fact that the value value is returned correctly to all the unblocked threads and that the threads Ti, 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:

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;
}