Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Tutorial 5:  Semaphores

CSSE7610

The exercises below are from chapter 6 of M. Ben-Ari principles  of concurrent and Distributed programming  (second edition), 2OO6.

1.  consider the following algorithm:

(a) what are the possible outputs of this algorithm？

(b) what are the possible outputs if we remove the statement wait(s)？

(c) what are the possible outputs if we remove the statement wait(T)？

2. what are the possible outputs of the following algorithm？

3. what are the possible outputs of the following algorithm？

4. The following algorithm attempts to use binary semaphores to solve the critical section problem with at most k out of N processes in the critical section:

For N=4 and k=2, construct a scenario in which delay=2, contrary to the deinition of a binary semaphore.  Show this also for N=3 and k=2.  (Note that m is a local variable and count a global, shared, variable.)

5.  Here is a version of the implementation of the signal operation of a weak semaphore in Promela that does not use the variable choice.  Is the pro- gram correct？

inline   signal ( S )  {

atomic  {

S . i   =  O ;

do

: :   ( S . i  == NPROCS)  ->  break

: :   ( S . i  <  NPROCS)  &&  S . blocked [ S . i ]   ->  break     : :   ( S . i  < NPROCS)  &&  S . blocked [ S . i ]  ->  S . i++    : :   ( S . i  < NPROCS)  &&  !S . blocked [ S . i ]  ->  S . i++ od ;

if

: :   S . i  == NPROCS ->  S . count++

: :   else  ->  S . blocked [ S . i ]  =  false

fi

}

}