User Tools

Site Tools


cs:exercises_about_concurrent_programming_pseudo-code
Return to Home page

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cs:exercises_about_concurrent_programming_pseudo-code [2019/02/26 14:33] (current)
Line 1: Line 1:
 +====== 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 //​T<​sub>​i</​sub>//​ 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<​sub>​1</​sub>//​ calls ''​p(3,​ 10)''​ that sets the semaphore ''​sem=1''​ and it returns ''​0''​
 +  * //​T<​sub>​1</​sub>//​ calls ''​p(4,​ 20)''​ that sets the semaphore ''​sem=0''​ and it returns ''​0''​
 +  * //​T<​sub>​1</​sub>//​ calls ''​p(4,​ 30)''​ that blocks //​T<​sub>​1</​sub>//​
 +  * //​T<​sub>​2</​sub>//​ calls ''​p(7,​ 15)''​ that blocks //​T<​sub>​2</​sub>//​
 +  * //​T<​sub>​3</​sub>//​ calls ''​v(14)''​ that unblocks the thread //​T<​sub>​2</​sub>//,​ because ''​7 > 4''​. The function ''​p()''​ returns to //​T<​sub>​2</​sub>//​ the value ''​14''​ and the function ''​v()''​ returns to //​T<​sub>​3</​sub>//​ the value ''​15''​
 +  * //​T<​sub>​3</​sub>//​ calls ''​v(35)''​ that unblocks the thread //​T<​sub>​1</​sub>//​. The function ''​p()''​ returns to //​T<​sub>​1</​sub>//​ the value ''​35''​ and the function ''​v()''​ returns to //​T<​sub>​3</​sub>//​ the value ''​30''​
 +  * //​P<​sub>​3</​sub>//​ calls ''​v(16)''​ that sets the semaphore ''​sem=1''​ and it returns ''​0''​
 +
 +<code c 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;
 +  }
 +}
 +</​code>​
 +
 +===== Example 2 (Message broadcast) =====
 +An //​undefined//​ number of threads //​C<​sub>​i</​sub>//​ 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<​sub>​1</​sub>//​ calls ''​bConsume()''​ and it blocks on it
 +  * //​C<​sub>​2</​sub>//​ calls ''​bConsume()''​ and it blocks on it
 +  * //P// calls ''​bProduce(21)''​ which unblocks the threads //​C<​sub>​1</​sub>//​ and //​C<​sub>​2</​sub>//​ 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<​sub>​2</​sub>//​ calls ''​bConsume()''​ that unblocks the threads //P// and returns to the thread //​C<​sub>​2</​sub>//​ the value 12
 +  * //​C<​sub>​1</​sub>//​ calls ''​bConsume()''​ and it blocks on it
 +
 +
 +<code c 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);
 +}
 +</​code>​
 +
 +
 +
 +===== Example 3 (Multiplication between threads) =====
 +An //​undefined//​ number of threads //​T<​sub>​i</​sub>//​ 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<​sub>​1</​sub>//​ calls ''​val(3)''​ and it blocks on it
 +  * //​T<​sub>​2</​sub>//​ calls ''​val(5)''​ and it blocks on it
 +  * //M// calls ''​mul(2)''​ which unblocks the threads //​T<​sub>​1</​sub>//​ and //​T<​sub>​2</​sub>//​ blocked on ''​val()''​. The two functions ''​val()''​ will return to the calling threads, //​T<​sub>​1</​sub>//​ and //​T<​sub>​2</​sub>//,​ the values ''​3*2=6''​ and ''​5*2=10'',​ respectively
 +  * //M// calls ''​mul(3)''​ and it blocks on it
 +  * //​T<​sub>​2</​sub>//​ calls ''​val(4)''​ which unblocks the thread //M// and it will return immediately to the thread //​T<​sub>​2</​sub>//​ the value ''​4*3=12''​
 +
 +
 +<code c 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);
 +  }
 +}
 +</​code>​
 +
 +
 +
 +===== Example 4 =====
 +An //​undefined//​ number of threads //​T<​sub>​i</​sub>//​ 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<​sub>​i</​sub>//,​ 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<​sub>​1</​sub>//​ calls ''​wait(3,​2)''​ and it blocks on it
 +  * //​T<​sub>​2</​sub>//​ calls ''​wait(3,​4)''​ and it blocks on it
 +  * //​T<​sub>​3</​sub>//​ 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<​sub>​3</​sub>//​ calls ''​wait(5,​3)''​ and it blocks on it
 +  * //​T<​sub>​4</​sub>//​ calls ''​unblock(3,​6)''​ that unblocks the threads //​T<​sub>​1</​sub>//​ and //​T<​sub>​2</​sub>//​. The function ''​wait''​ returns to both threads the value 6. The function ''​unblock''​ returns to //​T<​sub>​4</​sub>//​ the value 2
 +  * //​T<​sub>​1</​sub>//​ calls ''​unblock(2,​7)''​ that return immediately the value -1, because it does not unblock any thread
 +
 +
 +<code c 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;
 +}
 +</​code>​

If you found any error, or if you want to partecipate to the editing of this wiki, please contact: admin [at] skenz.it

You can reuse, distribute or modify the content of this page, but you must cite in any document (or webpage) this url: https://www.skenz.it/cs/exercises_about_concurrent_programming_pseudo-code?rev=1551188037&do=diff
/web/htdocs/www.skenz.it/home/data/pages/cs/exercises_about_concurrent_programming_pseudo-code.txt ยท Last modified: 2019/02/26 14:33 (external edit)

Privacy Policy