System Programming

(1)

Introduction to

System Programming

Department of Military Information Engineering Hanyang University

Haewoon Nam Lecture 8 (CSE2018)

* Some slides and/or pictures are regenerated from the slides made by Silberschatz, Galvin, and

(2)

CSE2018 System Programming

Semaphore

• Semaphore: Synchronization tool

– Generalized locks

– Semaphore S : integer variable – Counting semaphore

• integer value can range over an unrestricted domain

– Binary semaphore

• integer value can range only between 0 and 1

• Same as a mutex lock

• Can only be accessed via two (atomic) operations

– Wait() and signal(), which are commonly called P() and V() – Wait() or P()

• waits for semaphore to become positive, then decrements it by 1 – Signal() or V()

• increments the semaphore by 1, waking up a waiting P if any

2

(3)

Semaphore Implementation

• Semaphore implementation with busy waiting

– Wait() and signal()

• Example: Bank ATM machines

wait(S) {

while (S <= 0)

; // busy wait S--;

}

signal(S) ^{

S++;

}

S = 0

S = 2 wait(S)

S = 1 S = 0 signal(S)

S = 1

(4)

Two Uses of Semaphore

• Mutual exclusion

– Initial value = 1 – Binary semaphore

• Scheduling constraints

– Initial value = 0

– Two processes that C1 needs to happen before C2

4 Initial value of S=1;

Semaphore.P()

// Critical section Semaphore.V()

Codes to execute ...

signal(S);

wait(S);

...

Codes to execute

Process 1 Process 2

C1

C2

(5)

Semaphore Implementation

• Semaphore implementation with no busy waiting

– For each semaphore

• there is an waiting queue – Two operations

• Block() : put the process on the waiting queue

• Wakeup() : remove one of processes in the waiting queue and put it in the ready queue

wait(semaphore *S) { S->value--;

if (S->value < 0) {

add this process to S->list;

block();

} }

signal(semaphore *S) { S->value++;

if (S->value <= 0) {

remove a process P from S->list;

wakeup(P);

typedef struct{

int value;

struct process *list;

} semaphore;

(6)

Classical Problems of Synchronization

• Classical problems used to test synchronization schemes

– Bounded-Buffer Problem

– Readers and Writers Problem – Dining-Philosophers Problem

6

(7)

Producer-Consumer with Bounded Buffer

• Problem Definition

– Producer puts items into a shared buffer – Consumer takes them out

– n buffers, each can hold one item

• Need synchronization to access the buffer

– Only one thread can manipulate the buffer at a time

– Producer needs to wait if buffer is full (until consumer takes items from the buffer)

– Consumer needs to wait if buffer is empty (until producer put some items into the buffer)

Buffer (queue) Producer

(sender)

Consumer (Receiver)

(8)

Producer-Consumer with Bounded Buffer

• Producer-consumer problem

– Semaphore mutex initialized to the value 1 (for mutual exclusion) – Semaphore full initialized to the value 0 (consumer’s constraint) – Semaphore empty initialized to the value n (producer’s constraint)

8 do {

...

/* produce an item */

...

wait(empty);

wait(mutex);

...

/* add an item to the buffer */

...

signal(mutex);

signal(full);

} while (true);

do {

wait(full);

wait(mutex);

...

/* remove an item from buffer */

...

signal(mutex);

signal(empty);

...

/* consume the item */

...

} while (true);

Producer

Consumer Wait until

space Lock the

buffer Release the buffer

Tell consumer there is more item

Check if there is an item

Lock the buffer Release the buffer Tell producer

need more item

(9)

Readers and Writers Problem

• A data set is shared among a number of processes

– Readers : only read the data set; they do not update – Writers : can both read and write

• Problem

– Multiple readers to read at the same time

– Only one single writer can access the shared data at the same time (need mutual exclusion)

• Constraints

– Readers can access data set when there is no writers – A writer can access data set when no readers or writers – Only one thread manipulates state variables at a time

(10)

Readers and Writers Problem

• Basic structure

– Reader()

• Wait until no writers

• Read data set

• Check out – wake up a waiting writer

10

reader1

reader2

reader3 writer1 File

writer2

waiting reader1

reader2

reader3 writer1 File

writer2 waiting

– Writer()

• Wait until no active readers or writers

• Read or write data set

• Check out – wake up waiting readers or writer

(11)

Readers and Writers Problem

• Shared Data

– Data set

– Semaphore rw_mutex initialized to 1 (mutual exclusion for writer) – Semaphore mutex initialized to 1 (mutual exclusion)

– Integer read_count initialized to 0

do {

wait(rw_mutex);

...

/* writing is performed */

...

signal(rw_mutex);

} while (true);

do {

wait(mutex);

read_count++;

if (read_count == 1) { wait(rw_mutex); } signal(mutex);

...

/* reading is performed */

...

wait(mutex);

read count--;

if (read_count == 0) { signal(rw_mutex); } signal(mutex);

} while (true);

Writer

Reader

Lock for writing

Release the lock

Only one reader can execute the entry section

Entry section

The first reader use the lock

(no readers or writers)

The last reader

Release the entry section Only one reader can

execute the exit section _section^Exit

Release the

(12)

Dining Philosophers Problem

• Setting

– Five philosophers sitting around the table

– There is 1 chopstick (not 1 pair) between seats

• Problem

– Philosophers only alternately think and eat

– Philosophers do not interact with their neighbors

– A philosopher can eat when he has both left and right chopsticks – A philosopher can take a chopstick on his left or one on his right

as they become available

– Each chopstick can be held only by one philosopher

– After he finishes eating, he needs to put down both chopsticks

12

(13)

Dining Philosophers Problem

• Structure

– How to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve

– No philosopher can know when others may want to eat or think.

• Instruction for each philosopher

– Think until the left chopstick is available; when it is, pick it up – Think until the right chopstick is available; when it is, pick it up – When both chopsticks are held, eat for a fixed amount of time – Then, put the left chopstick down

– Then, put the right chopstick down – Repeat from the beginning

(14)

Dining Philosophers Problem

• Shared data

– Bowl of rice (data set)

– Semaphore array chopstick[5] initialized to 1

– Does this solution work?

14 do {

wait (chopstick[i] );

wait (chopstick[(i + 1) % 5]);

// eat

signal (chopstick[i] );

signal (chopstick[(i + 1) % 5]);

// think } while (TRUE);

Philosopher i

It fails since it reaches a deadlock.

Each philosopher has picked up the left

chopstick, and is waiting for the right chopstick to become available..

(15)

Dining Philosophers Problem

• Deadlock handling

– Allow at most 4 philosophers to be sitting simultaneously at the table.

– Allow a philosopher to pick up the forks only if both are available (picking must be done in a critical section).

– Use an asymmetric solution -- an odd-numbered philosopher

picks up first the left chopstick and then the right chopstick. Even- numbered philosopher picks up first the right chopstick and then the left chopstick.

(16)

Deadlock and Starvation

• Deadlock

– Two or more processes are waiting indefinitely for an event that can be triggered by only one of the waiting processes

• Starvation

– Two or more processes are waiting indefinitely for an event that can be triggered by only one of the waiting processes

16 wait(S);

wait(Q);

...

signal(S);

signal(Q);

wait(Q);

wait(S);

...

signal(Q);

signal(S);

Process 1 Process 2