CPSC 351 Lecture 17 (D.H.)

Lecture 17

1. Interprocess Communication

Race condition, critical section, Peterson’s solution, TSL and Sleep and Wakeup -review.

2. Semaphores.

Description, DOWN and UP.

3. The producer-consumer problem using semaphores.

4. Event counters, monitors and message passing.

5. Equivalence of using synchronization and mutual exclusion primitives.

1. Interprocess Communication (see the previous two lecture notes (lecture 16 and 17)

Race condition, critical section, Peterson’s solution, TSL and Sleep and wakeup –review.

2. Semaphores.

Semaphores were introduced in 1965 by Dijkstra. He suggested that to avoid lost “Wakeups” an integer variable be kept which would count the number of wakeups saved for future use. This variable is called a semaphore.

If semaphore is equal to 0 than no wakeups are saved. If semaphore is greater than 0 than one or more wakeups are saved.

Only two operations are allowed for semaphores: DOWN and UP. DOWN and UP are indivisible, atomic operations; i.e. checking the value of s, changing its value or putting it to sleep is all done as a single operation.

DOWN(s):

if (s>0)

s=s-1;

else

put the calling process to sleep in Queue(s) /* until somebody else does “UP(s) */

UP(s):

if (s = = 0) and (Queue(s) is not empty)

wakeup a process and remove it from Queue(s);

else

s=s+1;

NOTE! It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed or blocked. This atomicity is absolutely essential to solving synchronization problems and avoiding race conditions.

3. The producer-consumer problem using semaphores. (See fig. 2-11 p.43 of text)

#define N 100/* number of slots in the buffer */

typedef int semaphore/* semaphores are special type of variables */

semaphore mutex =1;/* controls access to critical section*/

semaphore empty =N;/* initial number of empty slots is N */

semaphore full=0;/* initial number of full slots is 0 */

void producer(void)void consumer(void)

{{

int item;int item;

while (TRUE) { /* infinite loop */ while (TRUE) {/* infinite loop */

ProduceItem (); down(&full);/* decrement full count */

down(&empty) /* decrement empty count */down(&mutex);/* enter critical section */

down(&mutex) /* enter critical section */RemoveItem();/* critical sec. = take item */

EnterItem(); /* critical sec. = put item */ up(&mutex);/* leave critical section */

up(&mutex); /* leave critical section */up(&empty);/* increment empty count */

up(&full); /* increment full count*/ConsumeItem();

} }

}}

The above solution to the producer-consumer problem uses three semaphores: full, empty and mutex.

Variable mutex is used to assure mutually exclusive access to the buffer. It is initialized to 1. Semaphores that are initialized to 1 and are used by two or more processes to access to ensure that only one of them can enter its critical section at the same time are called binary semaphores.

Variable full is used for counting the number of buffer slots that are full. Variable empty is used for counting the number of buffer slots that are empty. These two semaphores are used to ensure that the producer stops running (goes to sleep) when the buffer is full, and the consumer stops running (goes to sleep) when the buffer is empty. This use is different from mutual exclusion, it assures that certain event sequences do or do not occur; it is called process synchronization.

4. Event counters, monitors and message passing.

Additional primitives used for process synchronization are: even counters, monitors and message passing.

Event counters which are special kind variables, were introduced in 1979 by Reed and Kanodia.

Three operations are defined on event counter E:

1. Read(E): Return current value of E.

2. Advance(E): Atomically increment E by 1.

3. Await (E,v) : Wait until E has a value v or more.

The producer-consumer problem can be easily solved using event counters (see fig.2-12 p. 44).

Monitors are higher level synchronization primitives, proposed by Hoare in 1974. They were introduced to make programming easier. A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package. Processes may call procedures in a monitor whenever they want to but they cannot directly access monitor’s internal data structures.

Monitors are programming language constructs that have the property of mutual exclusion: only one process can be active in the monitor at any time instant. It is up to the compiler to implement the mutual exclusion on monitor entries but a common way is to use a binary semaphore.

Message passing is a method of inteprocess communication that uses two operations SEND and RECEIVE, which like semaphores (and unlike monitors) are system calls.

1. send (destination, &MessageBuffer) sends a message (located in the MessageBuffer) to a given destination.

2. receive(source, &MessageBuffer) receives a message (in the MessageBuffer) from a given source.

5. Equivalence of using inter-process communication primitives.

The list of inter-process communication primitives is long. Each one has its supporters who maintain that their favorite way is the best way. However, all the methods are semantically equivalent. Using any of them, you can build the other ones. The textbook shows on pp. 52-55 how you can:

implement monitors and messages using semaphores

implement semaphores and messages using monitors

implement monitors and semaphores using messages