31.

Semaphores
Operating System: Three Easy Pieces

AOS@UC 1
Semaphore: A definition

p An object with an integer value

w We can manipulate with two routines; sem_wait() and sem_post().

w Initialization

1 #include <semaphore.h>
2 sem_t s;
3 sem_init(&s, 0, 1); // initialize s to the value 1
¢ Declare a semaphore s and initialize it to the value 1

¢ The second argument, 0, indicates that the semaphore is shared between

threads in the same process.

AOS@UC 2
Semaphore: Interact with semaphore

p sem_wait()
1 int sem_wait(sem_t *s) {
2 decrement the value of semaphore s by one
3 wait if value of semaphore s is negative
4 }

w If the value of the semaphore was one or higher when called

sem_wait(), return right away.

w It will cause the caller to suspend execution waiting for a subsequent post.

w When negative, the value of the semaphore is equal to the number of

waiting threads.

AOS@UC 3
Semaphore: Interact with semaphore (Cont.)

p sem_post()
1 int sem_post(sem_t *s) {
2 increment the value of semaphore s by one
3 if there are one or more threads waiting, wake one
4 }

w Simply increments the value of the semaphore.

w If there is a thread waiting to be woken, wakes one of them up.

AOS@UC 4
Binary Semaphores (Locks)

p What should X be?

w The initial value should be 1.
1 sem_t m;
2 sem_init(&m, 0, X); // initialize semaphore to X; what should X be?
3
4 sem_wait(&m);
5 //critical section here
6 sem_post(&m);

AOS@UC 5
Thread Trace: Single Thread Using A Semaphore

Value of Semaphore Thread 0 Thread 1

1
1 call sema_wait()
0 sem_wait() returns
0 (crit sect)
0 call sem_post()
1 sem_post() returns

AOS@UC 6
Thread Trace: Two Threads Using A Semaphore (1 CPU)
Value Thread 0 State Thread 1 State
1 Running Ready
1 call sem_wait() Running Ready
0 sem_wait() retruns Running Ready
0 (crit set: begin) Running Ready
0 Interrupt; Switch → T1 Ready Running
0 Ready call sem_wait() Running
-1 Ready decrement sem Running
-1 Ready (sem < 0)→sleep sleeping
-1 Running Switch → T0 sleeping
-1 (crit sect: end) Running sleeping
-1 call sem_post() Running sleeping
0 increment sem Running sleeping
0 wake(T1) Running Ready
0 sem_post() returns Running Ready
0 Interrupt; Switch → T1 Ready Running
0 Ready sem_wait() retruns Running
0 Ready (crit sect) Running
0 Ready call sem_post() Running
1 Ready sem_post() returns Running

AOS@UC 7
Semaphores As Condition Variables

1 sem_t s;
2
3 void *
4 child(void *arg) {
5 printf("child\n");
6 sem_post(&s); // signal here: child is done
7 return NULL;
8 }
9
10 int
11 main(int argc, char *argv[]) {
12 sem_init(&s, 0, X); // what should X be?
13 printf("parent: begin\n");
14 pthread_t c;
15 pthread_create(c, NULL, child, NULL);
16 sem_wait(&s); // wait here for child
17 printf("parent: end\n"); parent: begin
18 return 0; child
19 } parent: end
A Parent Waiting For Its Child The execution result
w What should X be?
¢ The value of semaphore should be set to is 0.

AOS@UC 8
Thread Trace: Parent Waiting For Child (Case 1)

p The parent call sem_wait() before the child has called sem_post().

Value Parent State Child State

0 Create(Child) Running (Child exists; is runnable) Ready
0 call sem_wait() Running Ready
-1 decrement sem Running Ready
-1 (sem < 0)→sleep sleeping Ready
-1 Switch→Child sleeping child runs Running
-1 sleeping call sem_post() Running
0 sleeping increment sem Running
0 Ready wake(Parent) Running
0 Ready sem_post() returns Running
0 Ready Interrupt; Switch→Parent Ready
0 sem_wait() retruns Running Ready

AOS@UC 9
Thread Trace: Parent Waiting For Child (Case 2)

p The child runs to completion before the parent call sem_wait().

Value Parent State Child State

0 Create(Child) Running (Child exists; is runnable) Ready
0 Interrupt; switch→Child Ready child runs Running
0 Ready call sem_post() Running
1 Ready increment sem Running
1 Ready wake(nobody) Running
1 Ready sem_post() returns Running
1 parent runs Running Interrupt; Switch→Parent Ready
1 call sem_wait() Running Ready
0 decrement sem Running Ready
0 (sem>=0)→awake Running Ready
0 sem_wait() returns Running Ready

AOS@UC 10
The Producer/Consumer (Bounded-Buffer) Problem

p Producer: put() interface

w Wait for a buffer to become empty in order to put data into it.

p Consumer: get() interface

w Wait for a buffer to become filled before using it.

1 int buffer[MAX];
2 int fill = 0;
3 int use = 0;
4
5 void put(int value) {
6 buffer[fill] = value; // line f1
7 fill = (fill + 1) % MAX; // line f2
8 }
9
10 int get() {
11 int tmp = buffer[use]; // line g1
12 use = (use + 1) % MAX; // line g2
13 return tmp;
14 }

AOS@UC 11
The Producer/Consumer (Bounded-Buffer) Problem

1 sem_t empty;
2 sem_t full;
3
4 void *producer(void *arg) {
5 int i;
6 for (i = 0; i < loops; i++) {
7 sem_wait(&empty); // line P1
8 put(i); // line P2
9 sem_post(&full); // line P3
10 }
11 }
12
13 void *consumer(void *arg) {
14 int i, tmp = 0;
15 while (tmp != -1) {
16 sem_wait(&full); // line C1
17 tmp = get(); // line C2
18 sem_post(&empty); // line C3
19 printf("%d\n", tmp);
20 }
21 }
22 …

First Attempt: Adding the Full and Empty Conditions

AOS@UC 12
The Producer/Consumer (Bounded-Buffer) Problem

21 int main(int argc, char *argv[]) {

22 // …
23 sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with…
24 sem_init(&full, 0, 0); // … and 0 are full
25 // …
26 }

First Attempt: Adding the Full and Empty Conditions (Cont.)

w Imagine that MAX is greater than 1 .

¢ If there are multiple producers, race condition can happen at line P1.

¢ It means that the old data there is overwritten.

w We’ve forgotten here is mutual exclusion.

¢ The filling of a buffer and incrementing of the index into the buffer is a critical
section.

AOS@UC 13
A Solution: Adding Mutual Exclusion

1 sem_t empty;
2 sem_t full;
3 sem_t mutex;
4
5 void *producer(void *arg) {
6 int i;
7 for (i = 0; i < loops; i++) {
8 sem_wait(&mutex); // line p0 (NEW LINE)
9 sem_wait(&empty); // line p1
10 put(i); // line p2
11 sem_post(&full); // line p3
12 sem_post(&mutex); // line p4 (NEW LINE)
13 }
14 }
15
(Cont.)

Adding Mutual Exclusion (Incorrectly)

AOS@UC 14
A Solution: Adding Mutual Exclusion

(Cont.)
16 void *consumer(void *arg) {
17 int i;
18 for (i = 0; i < loops; i++) {
19 sem_wait(&mutex); // line c0 (NEW LINE)
20 sem_wait(&full); // line c1
21 int tmp = get(); // line c2
22 sem_post(&empty); // line c3
23 sem_post(&mutex); // line c4 (NEW LINE)
24 printf("%d\n", tmp);
25 }
26 }

Adding Mutual Exclusion (Incorrectly)

AOS@UC 15
A Solution: Adding Mutual Exclusion (Cont.)

p Imagine two thread: one producer and one consumer.

w The consumer acquire the mutex (line c0).

w The consumer calls sem_wait() on the full semaphore (line c1).

w The consumer is blocked and yield the CPU.

¢ The consumer still holds the mutex!

w The producer calls sem_wait() on the binary mutex semaphore (line p0).

w The producer is now stuck waiting too. a classic deadlock.

AOS@UC 16
Finally, A Working Solution

1 sem_t empty;
2 sem_t full;
3 sem_t mutex;
4
5 void *producer(void *arg) {
6 int i;
7 for (i = 0; i < loops; i++) {
8 sem_wait(&empty); // line p1
9 sem_wait(&mutex); // line p1.5 (MOVED MUTEX HERE…)
10 put(i); // line p2
11 sem_post(&mutex); // line p2.5 (… AND HERE)
12 sem_post(&full); // line p3
13 }
14 }
15
(Cont.)

Adding Mutual Exclusion (Correctly)

AOS@UC 17
Finally, A Working Solution

(Cont.)
16 void *consumer(void *arg) {
17 int i;
18 for (i = 0; i < loops; i++) {
19 sem_wait(&full); // line c1
20 sem_wait(&mutex); // line c1.5 (MOVED MUTEX HERE…)
21 int tmp = get(); // line c2
22 sem_post(&mutex); // line c2.5 (… AND HERE)
23 sem_post(&empty); // line c3
24 printf(“%d\n”, tmp);
25 }
26 }
27
28 int main(int argc, char *argv[]) {
29 // …
30 sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with …
31 sem_init(&full, 0, 0); // ... and 0 are full
32 sem_init(&mutex, 0, 1); // mutex=1 because it is a lock
33 // …
34 }

Adding Mutual Exclusion (Correctly)

AOS@UC 18
Reader-Writer Locks

p Imagine a number of concurrent list operations, including inserts and

simple lookups.
w insert:
¢ Change the state of the list

¢ A traditional critical section makes sense.

w lookup:
¢ Simply read the data structure.

¢ As long as we can guarantee that no insert is on-going, we can allow many

lookups to proceed concurrently.

This special type of lock is known as a reader-write lock.

AOS@UC 19
A Reader-Writer Locks

p Only a single writer can acquire the lock.

p Once a reader has acquired a read lock,

w More readers will be allowed to acquire the read lock too.

w A writer will have to wait until all readers are finished.

1 typedef struct _rwlock_t {

2 sem_t lock; // binary semaphore (basic lock)
3 sem_t writelock; // used to allow ONE writer or MANY readers
4 int readers; // count of readers reading in critical section
5 } rwlock_t;
6
7 void rwlock_init(rwlock_t *rw) {
8 rw->readers = 0;
9 sem_init(&rw->lock, 0, 1);
10 sem_init(&rw->writelock, 0, 1);
11 }
12
13 void rwlock_acquire_readlock(rwlock_t *rw) {
14 sem_wait(&rw->lock);
15 …

AOS@UC 20
A Reader-Writer Locks (Cont.)

15 rw->readers++;
16 if (rw->readers == 1)
17 sem_wait(&rw->writelock); // first reader acquires writelock
18 sem_post(&rw->lock);
19 }
20
21 void rwlock_release_readlock(rwlock_t *rw) {
22 sem_wait(&rw->lock);
23 rw->readers--;
24 if (rw->readers == 0)
25 sem_post(&rw->writelock); // last reader releases writelock
26 sem_post(&rw->lock);
27 }
28
29 void rwlock_acquire_writelock(rwlock_t *rw) {
30 sem_wait(&rw->writelock);
31 }
32
33 void rwlock_release_writelock(rwlock_t *rw) {
34 sem_post(&rw->writelock);
35 }

AOS@UC 21
A Reader-Writer Locks (Cont.)

p The reader-writer locks have fairness problem.

w It would be relatively easy for the readers to starve writer.

w How to prevent more readers from entering the lock once a writer is
waiting?

AOS@UC 22
The Dining Philosophers

p Assume there are five “philosophers” sitting around a table.

w Between each pair of philosophers is a single fork (five total).

w The philosophers each have times where they think, and don’t need any forks, and
times where they eat.

w In order to eat, a philosopher needs two forks, both the one on their left and the
one on their right.

w The contention for these forks. P1

f2 f1

P2 P0

f3 f0

P3 P4
f4

AOS@UC 23
The Dining Philosophers (Cont.)

p Key challenge
w There is no deadlock.

w No philosopher starves and never gets to eat.

w Concurrency is high.

while (1) { // helper functions

think(); int left(int p) { return p; }
getforks();
eat(); int right(int p) {
putforks(); return (p + 1) % 5;
} }

Basic loop of each philosopher Helper functions (Downey’s solutions)

¢ Philosopher p wishes to refer to the for on their left à call left(p).

¢ Philosopher p wishes to refer to the for on their right à call right(p).

AOS@UC 24
The Dining Philosophers (Cont.)

p We need some semaphore, one for each fork: sem_t forks[5].

1 void getforks() {
2 sem_wait(forks[left(p)]);
3 sem_wait(forks[right(p)]);
4 }
5
6 void putforks() {
7 sem_post(forks[left(p)]);
8 sem_post(forks[right(p)]);
9 }
The getforks() and putforks() Routines (Broken Solution)

w Deadlock occur!
¢ If each philosopher happens to grab the fork on their left before any
philosopher can grab the fork on their right.

¢ Each will be stuck holding one fork and waiting for another, forever.

AOS@UC 25
A Solution: Breaking The Dependency

p Change how forks are acquired.

w Let’s assume that philosopher 4 acquire the forks in a different order.

1 void getforks() {
2 if (p == 4) {
3 sem_wait(forks[right(p)]);
4 sem_wait(forks[left(p)]);
5 } else {
6 sem_wait(forks[left(p)]);
7 sem_wait(forks[right(p)]);
8 }
9 }

¢ There is no situation where each philosopher grabs one fork and is stuck
waiting for another. The cycle of waiting is broken.

AOS@UC 26
How To Implement Semaphores

p Build our own version of semaphores called Zemaphores

1 typedef struct __Zem_t {
2 int value;
3 pthread_cond_t cond;
4 pthread_mutex_t lock;
5 } Zem_t;
6
7 // only one thread can call this
8 void Zem_init(Zem_t *s, int value) {
9 s->value = value;
10 Cond_init(&s->cond);
11 Mutex_init(&s->lock);
12 }
13
14 void Zem_wait(Zem_t *s) {
15 Mutex_lock(&s->lock);
16 while (s->value <= 0)
17 Cond_wait(&s->cond, &s->lock);
18 s->value--;
19 Mutex_unlock(&s->lock);
20 }
21 …

AOS@UC 27
How To Implement Semaphores (Cont.)

22 void Zem_post(Zem_t *s) {

23 Mutex_lock(&s->lock);
24 s->value++;
25 Cond_signal(&s->cond);
26 Mutex_unlock(&s->lock);
27 }

w Zemaphore don’t maintain the invariant that the value of the semaphore
means the number of threads waiting.
¢ The value never be lower than 0.

¢ This behavior is easier to implement and matches the current Linux

implementation.

AOS@UC 28
p Disclaimer: This lecture slide has been adapted to be used in AOS course at University of
Cantabria by [Link]. Was initially developed for Operating System course in Computer
Science Dept. at Hanyang University. This lecture slide set is for OSTEP book written by Remzi
and Andrea Arpaci-Dusseau (at University of Wisconsin)

AOS@UC 29