Semaphores

q A semaphore is an object that consists of a counter, a waiting list of processes and two methods (e.g., functions): signal and wait.
method signal counter method wait waiting list

semaphore

Semaphore Method: wait

void wait(sem S) { S.count--; if (S.count < 0) { add the caller to the waiting list; block(); } }

q After decreasing the counter by 1, if the counter value becomes negative, then vadd the caller to the waiting list, and then vblock itself.

Semaphore Method: signal

void signal(sem S) { S.count++; if (S.count <= 0) { remove a process P from the waiting list; resume(P); } }

q After increasing the counter by 1, if the new counter value is not positive, then vremove a process P from the waiting list, vresume the execution of process P, and return
3

Important Note: 1/4

S.count--; if (S.count<0) { add to list; block(); } S.count++; if (S.count<=0) { remove P; resume(P); }

q If S.count < 0, abs(S.count) is the number of waiting processes. q This is because processes are added to (resp., removed from) the waiting list only if the counter value is < 0 (resp., <= 0).
4

Important Note: 2/4

S.count--; if (S.count<0) { add to list; block(); } S.count++; if (S.count<=0) { remove P; resume(P); }

q The waiting list can be implemented with a queue if FIFO order is desired. q However, the correctness of a program should not depend on a particular implementation of the waiting list. q Your program should not make any assumption 5 about the ordering of the waiting list.

Important Note: 3/4

S.count--; if (S.count<0) { add to list; block(); } S.count++; if (S.count<=0) { remove P; resume(P); }

q The caller may be blocked in the call to wait(). q The caller never blocks in the call to signal(). If S.count > 0, signal() returns and the caller continues. Otherwise, a waiting process is released and the caller continues. In this case, two processes continue.
6

The Most Important Note: 4/4

S.count--; if (S.count<0) { add to list; block(); } S.count++; if (S.count<=0) { remove P; resume(P); }

q wait() and signal() must be executed atomically (i.e., as one uninterruptible unit). q Otherwise, race conditions may occur. q Homework: use execution sequences to show race conditions if wait() and/or signal() is not executed atomically.
7

Three Typical Uses of Semaphores

q There are three typical uses of semaphores: vmutual exclusion: Mutex (i.e., Mutual Exclusion) locks vcount-down lock: Keep in mind that semaphores have a counter. vnotification: Indicate an event has occurred.
8

Use 1: Mutual Exclusion (Lock)

initialization is important semaphore S = 1; int count = 0; Process 1 Process 2 while (1) { while (1) { // do something entry // do something S.wait(); S.wait(); count++; critical sections count--; S.signal(); S.signal(); // do something exit // do something } }

qWhat if the initial value of S is zero? qS is a binary semaphore (similar to a lock).

Use 2: Count-Down Counter

semaphore S = 3; Process 1 Process 2 while (1) { while (1) { // do something // do something S.wait(); S.wait(); at most 3 processes can be here!!! S.signal(); S.signal(); // do something // do something } }

q After three processes pass through wait(), this section is locked until a process calls signal().

10

Use 3: Notification
semaphore S1 = 1, S2 = 0; process 1 process 2 while (1) { while (1) { // do something // do something notify S1.wait(); S2.wait(); cout << 1; cout << 2; S2.signal(); notify S1.signal(); // do something // do something } }

q Process 1 uses S2.signal() to notify process 2, indicating I am done. Please go ahead. q The output is 1 2 1 2 1 2 q What if both S1 and S2 are both 0s or both 1s? 11 q What if S1 = 0 and S2 = 1?

 Five philosophers are in a thinking - eating cycle. When a philosopher gets hungry, he sits down, picks up two nearest chopsticks, and eats. A philosopher can eat only if he has both chopsticks. After eating, he puts down both chopsticks and thinks. This cycle continues.

Lock Example: Dining Philosophers

12

Dining Philosopher: Ideas

q Chopsticks are shared items (by two philosophers) and must be protected. q Each chopstick has a semaphore with initial value 1. q A philosopher calls wait() before picks up a chopstick and calls signal() to release it.
outer critical section left chop locked Semaphore C[5] = 1; C[i].wait(); C[(i+1)%5].wait(); has 2 chops and eats C[(i+1)%5].signal(); C[i].signal();

inner critical section 13 right chop locked

Dining Philosophers: Code

semaphore C[5] = 1;

philosopher i wait for my left chop while (1) { // thinking wait for my right chop C[i].wait(); C[(i+1)%5].wait(); release my right chop // eating C[(i+1)%5].signal(); C[i].signal(); release my left chop // finishes eating }

Does this solution work? 14

Dining Philosophers: Deadlock!

If all five philosophers sit down and pick up their left chopsticks at the same time, this program has a circular waiting and deadlocks. An easy way to remove this deadlock is to introduce a weirdo who picks up his right chopstick first!
15

Dining Philosophers: A Better Idea

semaphore C[5] = 1; philosopher i (0, 1, 2, 3) Philosopher 4: the weirdo

while (1) { while (1) { // thinking // thinking C[i].wait(); C[(i+1)%5].wait(); C[(i+1)%5].wait(); C[i].wait(); // eating // eating C[(i+1)%5].signal(); C[i].signal(); C[i].signal(); C[(i+1)%5].signal(); // finishes eating; // finishes eating } } lock left chop lock right chop
16

Dining Philosophers: Questions

q The following are some important questions for you to work on. vWe choose philosopher 4 to be the weirdo. Does this choice matter? vShow that this solution does not cause circular waiting. vShow that this solution will not have circular waiting if we have more than 1 and less than 5 weirdoes. q These questions may appear as exam problems.
17

Count-Down Lock Example

q The nave solution to the dining philosophers causes circular waiting. q If only four philosophers are allowed to sit down, no deadlock can occur. q Why? If all four of them sit down at the same time, the right-most philosopher can have both chopsticks! q How about fewer than four? This is obvious. 18

Count-Down Lock Example

semaphore C[5]= 1; semaphore Chair = 4; get a chair this is a count-down lock while (1) { that only allows 4 to go! // thinking Chair.wait(); C[i].wait(); C[(i+1)%5].wait(); // eating this is our old friend C[(i+1)%5].signal(); C[i].signal(); Chair.signal(); } release my chair
19

The Producer/Consumer Problem

q Suppose we have a circular buffer of n slots. q Pointers in (resp., out) points to the first empty (resp., filled) slot. q Producer processes keep adding info into the buffer q Consumer processes keep retrieving info from the buffer. 20

bounded-buffer

Problem Analysis
q A producer deposits info into Buf[in] and a consumer retrieves info from Buf[out]. q in and out must be advanced. q in is shared among producers. q out is shared among consumers. q If Buf is full, producers should be blocked. buffer is implemented with an array Buf[ ] q If Buf is empty, consumers should be blocked.
21

q We need a sem. to protect the buffer. q A second sem. to block producers if the buffer is full. q A third sem. to block consumers if the buffer is empty.
22

Solution
no. of slots semaphore NotFull=n, NotEmpty=0, Mutex=1;

producer

consumer

while (1) { while (1) { NotFull.wait(); NotEmpty.wait(); Mutex.wait(); Mutex.wait(); Buf[in] = x; x = Buf[out]; in = (in+1)%n; out = (out+1)%n; Mutex.signal(); Mutex.signal(); NotEmpty.signal(); NotFull.signal(); } } notifications critical section
23

Question
q What if the producer code is modified as follows? q Answer: a deadlock may occur. Why?

while (1) { Mutex.wait(); NotFull.wait(); Buf[in] = x; order changed in = (in+1)%n; NotEmpty.signal(); Mutex.signal(); }
24

The Readers/Writers Problem

q Two groups of processes, readers and writers, are accessing a shared resource by the following rules: vReaders can read simultaneously. vOnly one writer can write at any time. vWhen a writer is writing, no reader can read. vIf there is any reader reading, all incoming writers must wait. Thus, readers have higher priority.
25

Problem Analysis
q We need a semaphore to block readers if a writer is writing. q When a writer arrives, it must be able to know if there are readers reading. So, a reader count is required which must be protected by a lock. q This reader-priority version has a problem: bounded waiting condition may be violated if readers keep coming, causing the waiting writers no chance to write.
26

q When a reader comes in, it increase the count. q If it is the 1st reader, waits until no writer is writing, q Reads data. q Decreases the counter. q Notifies the writer that no reader is reading if it is the last.
27

q When a writer comes in, it waits until no reader is reading and no writer is writing. q Then, it writes data. q Finally, notifies readers and writers that no writer is in.

28

Solution
semaphore Mutex = 1, WrtMutex = 1; int RdrCount;

reader

writer

while (1) { while (1) { Mutex.wait(); RdrCount++; if (RdrCount == 1) blocks both readers and writers WrtMutex.wait(); WrtMutex.wait(); Mutex.signal(); // read data // write data Mutex.wait(); RdrCount--; if (RdrCount == 0) WrtMutex.signal(); WrtMutex.signal(); Mutex.signal(); } } 29