Module 3 : Process Synchronization

IPC: Shared memory, message passing - Race condition –

Critical section problem - Peterson's solution – Bakery
Algorithm - Hardware synchronization: Test-and-Set, Swap -
Mutex locks - Semaphores – Classical synchronization
problems: Bounded buffer, Readers-Writers, Dining
Philosophers – Monitors.

1
 Module 3: Process Synchronization
• Background
• The Critical-Section Problem
• Peterson’s Solution
• Synchronization Hardware
• Semaphores
• Classic Problems of Synchronization
• Monitors
• Synchronization Examples
• Atomic Transactions
 Objectives
• To introduce the critical-section problem, whose
solutions can be used to ensure the consistency of
shared data

• To present both software and hardware solutions

of the critical-section problem

• To introduce the concept of an atomic transaction

and describe mechanisms to ensure atomicity
 Interprocess Communication
• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes,
including sharing data
• Reasons for cooperating processes:
– Information sharing
– Computation speedup
– Modularity
– Convenience
• Cooperating processes need interprocess communication (IPC)
• Two models of IPC
– Shared memory
– Message passing
Communications Models
 Cooperating Processes
• Independent process cannot affect or be affected by the execution
of another process

• Cooperating process can affect or be affected by the execution of

another process

• Advantages of process cooperation

– Information sharing
– Computation speed-up
– Modularity
– Convenience
 Producer-Consumer Problem
• Paradigm for cooperating processes, producer process
produces information that is consumed by a consumer
process
– unbounded-buffer places no practical limit on the
size of the buffer
– bounded-buffer assumes that there is a fixed buffer
size
 Producer-Consumer Problem
Challenges:

The buffer has limited size.

• Multiple producers and consumers may run
concurrently.
• Access to the buffer must be synchronized to
avoid errors.
Bounded-Buffer – Shared-Memory Solution
Shared data
#define BUFFER_SIZE 10
typedef struct {
...
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

• Solution is correct, but can only use BUFFER_SIZE-10

elements
 Bounded-Buffer – Producer
while (true) {
/* Produce an item */
while (((in = (in + 1) % BUFFER SIZE) == out)
; /* do nothing -- no free buffers */
buffer[in] = item;
in = (in + 1) % BUFFER SIZE;
}
Bounded Buffer – Consumer

while (true) {
while (in == out)
; // do nothing -- nothing to
consume

// remove an item from the buffer

item = buffer[out];
out = (out + 1) % BUFFER SIZE;
return item;
}
 Interprocess Communication – Message Passing
• Mechanism for processes to communicate and to synchronize their
actions.
• Message system – processes communicate with each other
without resorting to shared variables
• IPC facility provides two operations:
– send(message) – message size fixed or variable
– receive(message)
• If P and Q wish to communicate, they need to:
– establish a communication link between them
– exchange messages via send/receive
• Implementation of communication link
– physical (e.g., shared memory, hardware bus)
– logical (e.g., logical properties)
 Synchronization
• Message passing may be either blocking or non-blocking

• Blocking is considered synchronous

– Blocking send has the sender block until the message is
received. In blocking send, the sender sends a message and
then waits until the receiver has actually received the
message before it continues.
– Blocking receive has the receiver block until a message is
available, In blocking receive, the receiver is blocked (i.e., it
cannot continue its execution) until a message is available to
be received.
 Synchronization

• Non-blocking is considered asynchronous

– Non-blocking send has the sender send the message and

continue. In non-blocking send, the sender sends the
message and immediately continues with its work, without
waiting for the receiver to confirm the receipt of the
message.
– Non-blocking receive has the receiver receive a valid message
or null. In non-blocking receive, the receiver tries to get the
message, but if there’s no message available, it doesn’t block;
instead, it simply gets a null or empty response and
continues executing.
 Synchronization

Blocking Non-Blocking
Feature
(Synchronous) (Asynchronous)
Waits? Yes No
Sender waits? Yes (until received) No
Receiver Yes (until message
No
waits? arrives)
Example Phone call Email
 Buffering
Queue of messages attached to the link; implemented in one of three
ways
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous). Sender must wait
until receiver is ready. Fully synchronous.

• 2. Bounded capacity – finite length of n messages Sender must

wait if link full. Fixed number of slots. Producer waits if full.
Consumer waits if empty. Most common in Producer–Consumer
problem.

• 3. Unbounded capacity – infinite length Sender never waits. No

waiting for producer. Theoretically unlimited storage.
 Concurrent Execution

• Concurrent execution has to give the same results as

serial execution.
• Concurrent execution with shared data leads us to
speak about synchronization.
• To get data consistency we should have mechanism
to avoid data inconsistency problem.
• Synchronization as embedded system topic we have
to speak about producer consumer problem
 Concurrent Execution

• Maintaining data consistency requires mechanisms to ensure the

orderly execution of cooperating processes

• Suppose that we wanted to provide a solution to the consumer-

producer problem that fills all the buffers. We can do so by having
an integer count that keeps track of the number of full buffers.
Initially, count is set to 0.

• It is incremented by the producer after it produces a new buffer

and is decremented by the consumer after it consumes a buffer.
 Producer Consumer Problem

• The producer-consumer problem illustrates the

need for synchronization in systems where many
processes share a resource.
• In the problem, two processes share a fixed-size
buffer. One process produces information and puts
it in the buffer, while the other process consumes
information from the buffer.
• These processes do not take turns accessing the
buffer, they both work concurrently.
• It is also called bounded buffer problem
 Producer Consumer Problem
Without proper control:
• Race conditions may occur
• Data may be corrupted
• System may crash

OS uses synchronization tools like:

• Semaphores
• Mutex locks
• Monitors
 Producer

while (true) {
/* produce an item and put in nextProduced */
while (counter == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
• shared variables are: counter, in, buffer[]. Both Producer
and Consumer will modify counter.
 Producer
is NOT atomic. It actually happens in three steps
internally:
• Read counter
• Add 1
• Store updated value back
 Consumer

while (true) {
while (counter == 0)
; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in nextConsumed */
}
• shared variables are: counter, in, buffer[]. Here Consumer
give counter --
 Race Condition

• counter++ could be implemented as

register1 = counter
register1 = register1 + 1
counter = register1

• counter-- could be implemented as

register2 = counter
register2 = register2 - 1
count = register2
 Race Condition

Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute counter = register1 {count = 6 }
S5: consumer execute counter = register2 {count = 4}
 Race Condition
• Now we have arrived at the incorrect state "counter == 4", indicating
that four buffers are full, If we reversed the order of the statements
at S4 and S5, we would arrive at the incorrect state "counter —— 6".

• We would arrive at this incorrect state because we allowed both

processes
to manipulate the variable counter concurrently.

• A situation like this, where several processes access and manipulate

the same data concurrently and the outcome of the execution
depends on the particular order in which the access takes place, is
called a race condition.

• To avoid the race condition, we need to ensure that only one process
at a time can be manipulating the variable counter. To make such a
guarantee, we require that the processes be synchronized in some
 Critical Section Problem

• Consider system of n processes {p0, p1, … pn-1}

• Each process has critical section segment of code
– Process may be changing common variables, updating
table, writing file, etc
– When one process in critical section, no other may be in its
critical section
• Critical section problem is to design protocol to solve this.
• Each process must ask permission to enter critical section in
entry section, may follow critical section with exit section,
then remainder section
• Especially challenging with preemptive kernels
 Critical Section

• General structure of process pi is

 Solution to Critical-Section Problem
1. Mutual Exclusion - If process Pi is executing in its critical section,
then no other processes can be executing in their critical sections.

2. Progress - If no process is executing in its critical section and there

exist some processes that wish to enter their critical section, then
the selection of the processes that will enter the critical section
next cannot be postponed indefinitely.

3. Bounded Waiting - After a process has made a request to enter it’s

CS, there is a bound on the number of times that the other processes
are allowed to enter their CS .
– otherwise the process will suffer from starvation
– Of course also no deadlock (no cycles)
 Peterson’s solutions: Algorithm 1
Process Pi:
repeat
while(turn!=i){};//turn 0–enter CS
CS
turn:=j;
RS
forever
An execution view of Algorithm 1

Process P0: Process P1:

repeat repeat
while(turn!=0); while(turn!=1);
CS CS
turn:=1; turn:=0;
RS RS
forever forever
Pj not able to enter into CS
 Algorithm 1 (cont.) – Progress cond is not
satisfied
Initial State: Assume turn = 0 (P0's turn).
Process P0:
– P0 checks while(turn != 0); → Since turn == 0, it proceeds.
– P0 enters the critical section (CS).
– After completing its CS, P0 sets turn := 1 (now it’s P1's turn).
– P0 then moves on to the remainder section (RS).
Process P1:
– Now turn = 1, so P1 enters the while(turn != 1); loop.
– Since turn == 1, P1 proceeds.
– P1 enters the critical section (CS).
– After completing its CS, P1 sets turn := 0 (now it’s P0's turn).
– P1 then moves on to its remainder section (RS).
Next Cycle:
– The process repeats, with P0 and P1 taking turns as determined by the
turn variable.
 Algorithm 1 (cont.) – Progress cond is not
satisfied
• The shared variable turn is initialized (to 0 or 1) before
executing any Pi
• Pi’s critical section is executed iff turn = i
• Pi is busy waiting if Pj is in CS: mutual exclusion is satisfied
• Progress requirement is not satisfied since it requires strict
alternation of CSs
• If a process requires its CS more often then the other, it
cannot get it.

Disadvantages: Progress condition is not satisfied.

 Algorithm 2

Flag[i]=flag[j]=false Flag[i]=flag[j]=false
Process Pi:
repeat Process Pj:
repeat
flag[i]:=true; flag[j]:=true;
while(flag[j]);//True while(flag[i]);
CS CS
flag[i]:=false; flag[j]:=false;
RS
RS forever
forever
Algorithm 2 - (Peterson’s algorithm) – Progress
cond not satisfied – Deadlock occurs
• Keep 1 Bool variable for each process: flag[0] and
flag[1]
• Pi signals that it is ready to enter it’s CS by:
flag[i]:=true
• Mutual Exclusion is satisfied but not the progress
requirement
• If we have the sequence:
T0: flag[0]:=true
T1: flag[1]:=true
Both process will wait forever to enter their CS: we
have a deadlock
 Algorithm 3 (Peterson’s algorithm)

Process Pi:
repeat
flag[i]:=true; // want in
turn:=j; // let the other in
while
(flag[j]&turn=j){};
CS
flag[i]:=false; // do not want in
RS
forever
 Algorithm 3 (Peterson’s algorithm)
• Initialization: flag[0]:=flag[1]:=false turn:= 0 or 1
• Willingness to enter CS specified by flag[i]:=true
• If both processes attempt to enter their CS simultaneously,
only one turn value will last
• Exit section: specifies that Pi is unwilling to enter CS

Execution view of Algorithm 3

Bakery Algorithm
 Bakery Algorithm

•Each process is assigned a unique number (ticket) that indicates the

order in which it will enter the critical section (CS).

•The process with the smallest number enters the critical section
first, and the others wait for their turn.

•After a process leaves the critical section, the ticketing system

ensures that the process with the next smallest number will get the
chance to enter.

Shared Variables:
•boolean choosing[n] = {false}; - unique number (ticket)
•int number[n] = {0}; - Process Id
 Bakery Algorithm

For each process, we need the following shared variables:

[Link][]: An array that holds the ticket number for each process.
Each process i gets a unique number (larger than all previous ones)
when it wants to enter the critical section.

[Link][]-True - CS: A boolean array indicating whether a process wants

to enter the critical section. If flag[i] is true, then process i wants to
enter the critical section.

•flag[i]: True if process i wants to enter CS; False otherwise.

•number[i]: The number or ticket assigned to process i.
 Bakery Algorithm
1. Choosing a Ticket Number:

The process Pi first sets flag[i] = true, signaling its intent

to enter the critical section.
Pi then chooses a ticket number larger than any other
process’s number. It does this by setting

number[i] = max(number[0], number[1], ..., number[n-

1]) + 1;
 Bakery Algorithm

4 processes: P0, P1, P2, P3.

•Initially: flag[0] = flag[1] = flag[2] = flag[3] = false (None of the
processes want to enter CS).
number[0] = number[1] = number[2] = number[3] = 0 (All processes
have no ticket yet)

Step 1: P0 wants to enter the CS

P0 sets flag[0] = true to signal it wants to enter CS.
P0 picks a ticket number:
number[0] = max(number[0], number[1], number[2], number[3])
+ 1 = max(0, 0, 0, 0) + 1 = 1;

P0’s ticket number - 1.

 Bakery Algorithm

Step 2: P1 wants to enter the CS

P1 sets flag[1] = true to signal it wants to enter CS. P1 picks a ticket
number:
number[1] = max(number[0], number[1], number[2], number[3]) + 1
= max(1, 0, 0, 0) + 1 = 2;
P1’s ticket number - 2. P1 sets flag[1] = false after picking its number.

Step 3: P2 wants to enter the CS

P2 sets flag[2] = true to signal it wants to enter CS. P2 picks a ticket
number:
number[2] = max(number[0], number[1], number[2], number[3]) + 1
= max(1, 2, 0, 0) + 1 = 3;
P2’s ticket number - 3. P2 sets flag[2] = false after picking its number.
 Bakery Algorithm

Step 4: P3 wants to enter the CS

P3 sets flag[3] = true to signal it wants to enter CS. P3 picks a ticket
number:
number[3] = max(number[0], number[1], number[2], number[3]) + 1
= max(1, 2, 3, 0) + 1 = 4;
P3’s ticket number - 4. P3 sets flag[3] = false after picking its number.
 Bakery Algorithm
P0 Checks:
P0 checks if there’s any process with a smaller or equal ticket number.
Since P0 has the smallest ticket number (1), it can enter the CS
immediately.
P1 Checks:
P1 checks if any process has a smaller ticket number. P0's ticket
number (1) is smaller than P1's (2), so P1 waits.
P2 Checks:
P2 checks if any process has a smaller ticket number. P0's ticket
number (1) is smaller than P2's (3), so P2 waits. P1's ticket number (2)
is also smaller, so P2 waits for both P0 and P1 to finish.
P3 Checks:
P3 checks if any process has a smaller ticket number. P0's ticket
number (1), P1's ticket number (2), and P2's ticket number (3) are all
smaller than P3's ticket number (4), so P3 waits until all the previous
processes finish.
 Bakery Algorithm
Entering the Critical Section

1.P0 enters CS: P0 enters the Critical Section because its ticket
number (1) is the smallest. After finishing, P0 sets flag[0] = false.
2.P1 enters CS: After P0 finishes, P1 checks the ticket numbers
again and enters because its ticket number (2) is now the smallest.
P1 enters the Critical Section and, once finished, sets flag[1] =
false.
3.P2 enters CS: After P1 finishes, P2 enters the Critical Section
because its ticket number (3) is now the smallest. P2 enters and
sets flag[2] = false after finishing.
4.P3 enters CS: Finally, after P2 finishes, P3 enters the Critical
Section because its ticket number (4) is now the smallest. P3
enters and sets flag[3] = false after finishing.
Bakery Algorithm : Case 1 – CS chosen based on Token Value
while (true) { CS
choosing[i] = true; number[i] = 0;
number[i] = 1 + max(number[0], RS
number[1], ..., number[n-1]); }
choosing[i] = false;

j = 0;
while (j < n) {
while (choosing[j]);
while (number[j] != 0 &&
(number[j] < number[i] ||
(number[j] == number[i] &&
j < i)));
j = j + 1;
}
Bakery Algorithm Case 2 – CS chosen based on Token Value
and Process ID
while (true) {
// Choosing the token
choosing[i] = true;
number[i] = 1 + max(number[0], number[1], ..., number[n-1]);
choosing[i] = false;
// Compare token values and process IDs
for (j = 0; j < n; j++) {
// If process j has a smaller token or the same token but
smaller ID, process i waits
while (number[j] != 0 && (number[j] < number[i] || // j has
smaller token value (number[j] == number[i] && j < i))); // j has
same token but smaller ID
}
CS
number[i] = 0;
RS }
Bakery Algorithm Case 3 – CS chosen based on Case 2, but
wait for generating a Token Value (two process not have
same token)
while (true) {
// Choosing the token
choosing[i] = true;
number[i] = 1 + max(number[0], number[1], ..., number[n-1]);
choosing[i] = false;
// Waiting for other processes to choose their tokens
j = 0;
while (j < n) {
while (choosing[j]); // Wait if process j is still choosing a token
// Wait if process j has a lower token number or if process j has the same token but
smaller ID
while (number[j] != 0 &&
(number[j] < number[i] ||
(number[j] == number[i] && j < i)));
j = j + 1;
}
CS
number[i] = 0;
RS }
 Bakery Algorithm – Case 3 Condition
while (true) {
// Choosing the token
choosing[i] = true;
number[i] = 1 + max(number[0], number[1], ..., number[n-1]);
choosing[i] = false;
// Waiting for other processes to choose their tokens
j = 0;
while (j < n) {
while (choosing[j]); // Wait if process j is still choosing a token
// Wait if process j has a lower token number or if process j has
the same token but smaller ID
while (number[j] != 0 &&
(number[j] < number[i] ||
(number[j] == number[i] && j < i)));
j = j + 1;
}
Bakery Algorithm
Bakery Algorithm
 Bakery Algorithm
Meets All Three Requirements:

1. Mutual Exclusion: (number[j], j) < (number[i], i) cannot be true

for both Pi and Pj.

2. Progress:
The decision takes complete execution of the for loop by one
process.
No process in its Remainder Section (with its number set to 0)
participates in the decision making.

3. Bounded Waiting:
•There is bounded waiting because each process can make at most
one entry into the critical section (out of the n-1 processes).
•After a process has had its turn, it will wait for the next requesting
process to enter the critical section in a First-Come-First-Serve (FCFS)
manner.
 Synchronization Hardware
• Many systems provide hardware support for critical section code

• Uniprocessors – could disable interrupts

– Currently running code would execute without preemption
– mutual exclusion is preserved but efficiency of execution is
degraded
– The reason is that while in CS, we cannot interleave execution
with other processes that are in RS
– Generally too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable

• Modern machines provide special atomic hardware instructions

• Atomic = non-interruptable
– mutual exclusion is not preserved
– Either test memory word and set value
– Or swap contents of two memory words
Hardware solutions: interrupt disabling/enabling
Process Pi:
repeat
disable interrupts
critical section
enable interrupts
remainder section
forever
Solution to Critical-section : Problem Using Locks

do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);
 Test And Set Instruction
Lock initially – False:
If one process want to enter in CS, then make lock as
1||[True]

• Definition:
boolean TestAndSet (boolean *target)
{
boolean rv = *target; //rv return value
*target = TRUE;
return rv:
}
If false - [*target] then return rv – [False]
If True – [*target] then return rv – [True]
But lock always be True
 Test And Set Instruction

• Definition:

boolean TestAndSet (boolean *target)

{
boolean rv = *target; //save old value
*target = TRUE; //set to TRUE .
return rv: //return old value
}
rv - return value

Working of Algorithm:

• Execute atomically
• Returns the original value of passed parameter
• Set the new value of passed parameter to “TRUE”
 Solution using Test And Set
• Shared boolean variable lock, initialized to FALSE
Solution:
do {
while ( TestAndSet (&lock )); // do nothing
CS
lock = FALSE;
RS
} while (TRUE);
• If TestAndSet returns TRUE → lock was already taken →
keep waiting.
• If it returns FALSE → lock was free → you acquired it →
enter critical section.
 Solution using Test And Set
Example: Returns True // Lock is
acquired by some other Process
do {
while ( TestAndSet (&lock )); // do nothing – not
able to get the lock
CS
lock = FALSE;
RS
} while (TRUE);
• If TestAndSet returns TRUE → lock was already taken →
keep waiting.
• If it returns FALSE → lock was free → you acquired it →
enter critical section.
 Solution using Test And Set

Returns False // Lock is released by another

Example: process, which is get by this process
do {
while ( TestAndSet (&lock )); // codn fails go to CS
CS
lock = FALSE;
RS
} while (TRUE);
• If TestAndSet returns TRUE → lock was already taken →
keep waiting.
• If it returns FALSE → lock was free → you acquired it →
enter critical section.
 Swap Instruction
Algorithm:
0 0 True:1
int compare_and_swap(int *value, int expected, int new_value)
always 0
{ Lock value
int temp = *value;
if (*value == expected) //Lock value = 0, then change to 1,
*value = new value; //Lock value = 1, then no-change
return temp;
}
 Swap Instruction
Algorithm:

int compare_and_swap(int *value, int expected, int new_value)

{
if (*value == expected)
*value = new value;
return temp;
}

Working steps:
• Executed atomically.
• Returns the original value of passed parameter “value”.
• Set the variable “value” the value of the passed
parameter “new_value” but only if
“value”==“expected”. That is, the swap takes place only
under this condition.
 Solution using Swap
• Shared Boolean variable lock initialized to FALSE;
Each process has a local Boolean variable key
Solution:
do {
while ( compare_and_swap (&lock, 0, 1) !=0);
/* i.e return_value!=0 (1), then another process is in
CS, then, do nothing */
CS
lock = 0;
RS
} while (TRUE);
 Mutex Locks
• Previous solutions are complicated and generally
inaccessible to application programmers.
• OS designers build software tools to solve CS problem.
• Simplest is mutex lock.
• Protect a critical section by first acquire() (function) a
lock then release() (function) the lock.
-> boolean variable indicating if lock is available or not.
• Calls to acquire() (check resource available=True, the
resource is available)and release (make the resource
available=True, so that another process acquire the
resource) must be atomic
-> usually implemented via hardware atomic
instructions. (at any time only one process execute acquire())
• But this solution requires busy waiting.
-> This lock therefore called a spinlock.
Mutex Locks

• a
 Mutex Locks – acquire() and release() lock
available == False
//no resource
Bounded-waiting Mutual Exclusion
with TestandSet()
 Semaphore
• A semaphore is hardware or a software variable whose value
indicates the status of a common resource. Its purpose is to lock the
resource being used.

• A process which needs the resource will check the semaphore for
determining the status of the resource followed by the decision for
proceeding.

• In multitasking operating systems, the activities are synchronized

by using the semaphore techniques.
 Semaphore
• Example, say we have four rooms with identical locks and keys. The
semaphore count - the count of keys - is set to 4 at beginning (all
four rooms are free), then the count value is decremented as people
are coming in. If all rooms are full, ie. there are no free keys left, the
semaphore count is 0. Now, when eq. one person leaves the rooms,
semaphore is increased to 1 (one free key), and given to the next
person in the queue.

• "A semaphore restricts the number of simultaneous users of a

shared resource up to a maximum number. Threads can request
access to the resource (decrementing the semaphore), and can
signal that they have finished using the resource (incrementing the
semaphore).“
 Semaphore
• Synchronization tool that does not require busy waiting
• Semaphore S – integer variable
• Two standard operations modify S: wait() and signal()
– Originally called P() and V()
• Less complicated

• Can only be accessed via two indivisible (atomic) operations

– wait (S) {
while S <= 0
; // no-op
S--;
}
– signal (S) {
S++;
}
 Semaphore
Initially S==1 :available
wait (S) { //decrement function
while S <= 0; // no-op
S--; //S=1, the decrement and enter into CS
/* CS if S=0*/
}
signal (S) { //increment function
S++; /* 0+1 = S=1 */ //:available for
Others
}
 Semaphore as General Synchronization Tool
1. Counting semaphore – integer value can range over an
unrestricted domain
2. Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
– Also known as mutex locks
• Can implement a counting semaphore S as a binary
semaphore
3. Provides mutual exclusion
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);
 Semaphore – Binary Example
Semaphore – Binary Example
• There is One printer
• There are 2 processes (P1, P2)
• Two process waiting for the same printer
• Use Binary Semaphore
• Initial value: s==1
 Semaphore – Binary Example
• Binary: Between two process
Semaphore
Step Process Action What Happens?
Value (S)
1 Initial State 1 Printer is free
P1 enters critical section
2 P1 executes wait(S) 0
(uses printer)
P2 must wait (printer
3 P2 executes wait(S) 0
busy)
P1 executes
4 1 Printer released
signal(S)
P2 enters critical
5 0 P2 now uses printer
section
P2 executes
6 1 Printer free again
signal(S)
 Semaphore – Counting Example
• Counting semaphore - unrestricted domain
• There is three printer – 3 instances (copies) of printer
• There are 4 processes (P1, P2, P3, P4)
• All are waiting for the same printer
• Use Counting Semaphore
• Initial value: s==3
 Semaphore - Counting
Semaphore Running
Step Process Action Explanation
Value (S) Processes
1 Initial State 3 None 3 printers free
2 P1 → wait(S) 2 P1 1 printer used
3 P2 → wait(S) 1 P1, P2 2 printers used

4 P3 → wait(S) 0 P1, P2, P3 All printers used

5 P4 → wait(S) 0 P4 Waiting No printer available

6 P1 → signal(S) 1 P2, P3 1 printer released

7 P4 enters 0 P2, P3, P4 P4 uses released printer

8 P2 → signal(S) 1 P3, P4 1 printer free

9 P3 → signal(S) 2 P4 2 printers free
10 P4 → signal(S) 3 None All printers free
 Semaphore Implementation
• Must guarantee that no two processes can execute wait ()
and signal () on the same semaphore at the same time
• Thus, implementation becomes the critical section
problem where the wait and signal code are placed in the
critical section
– Could now have busy waiting in critical section
implementation
• But implementation code is short
• Little busy waiting if critical section rarely occupied
• Note that applications may spend lots of time in critical
sections and therefore this is not a good solution
Semaphore Implementation with no Busy waiting (Cont.)
• Implementation of wait: S->value → integer (resource count)
CS wait(semaphore *S) { S->list → queue of waiting processes
S->value--;
if (S->value < 0) {
add this process to S->list;
block(); //waiting queue
} Reduce while loop cond
} checking at each time – call
• Implementation of signal: block method (queue)
Reduce while loop cond checking at
signal(semaphore *S) {
each time – call block method
S->value++;
(queue)
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
 Semaphore Implementation with no Busy waiting (Cont.)
Implementation of wait: Example S=1 : Waiting Queue
wait(semaphore *S) { P1-> S=S-1 =0 CS
S->value--; //CS// P2->S=S-1= -1<0 – Move to
if (S->value < 0) { waiting queue
add this process to S->list; P3->S=S-1= -2<0 – Move to
block(); //waiting queue waiting queue
} Example S=-2 : Ready Queue
} P1-> Complete execution
Implementation of signal: S=-2+1 =-1 - someone in waiting
queue
P2->using wakeup – comeout from
signal(semaphore *S) { waiting queue using wakeup signal.
S->value++; P3-> Complete execution
if (S->value <= 0) { S=-1+1 =0 - No one in waiting queue
remove a process P from S->list; P3->using wakeup – comeout from
wakeup(P); waiting queue using wakeup signal.
}
}
Semaphore Implementation with no Busy waiting (Cont.)
• Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
} }
•S > 0 → Free resources available
•S = 0 → No free resources
•S < 0 → Number of waiting processes
Example: If S = -3, processes are waiting in queue.

Initial S->value = 2 instance available

Processes: P1, P2, P3, P4
Semaphore Implementation with no Busy waiting
• With each semaphore there is an associated waiting
queue
• Each entry in a waiting queue has two data items:
– value (of type integer)
– pointer to next record in the list

• Two operations:
– block – place the process invoking the operation on
the appropriate waiting queue.
– wakeup – remove one of processes in the waiting
queue and place it in the ready queue.
Semaphore Implementation with no Busy waiting (Cont.)
• Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
} }
S->value After Conditio Waiting
Step Process Operation Action Taken
Decrement n (S<0?) List
1 P1 wait() 1 No P1 enters CS —
2 P2 wait() 0 No P2 enters CS —
3 P3 wait() -1 Yes P3 blocked P3
4 P4 wait() -2 Yes P4 blocked P3, P4
Semaphore Implementation with no Busy waiting (Cont.)
• Implementation of signal:
signal(semaphore *S) { •wait() → Try to enter critical section
S->value++; •signal() → Leave critical section
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}}
Process S->value After Condition Waiting
Step Operation Action Taken
Finishing Increment (S≤0?) List
5 P1 signal() -1 Yes Wake up P3 P4
6 P2 signal() 0 Yes Wake up P4 —
No wakeup
7 P3 signal() 1 No —
needed
No wakeup
8 P4 signal() 2 No —
needed
 Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for an
event that can be caused by only one of the waiting processes
• Let S and Q be two semaphores initialized to 1
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
. .. . .
signal (S); signal (Q);
signal (Q); signal (S);
• Starvation – indefinite blocking
– A process may never be removed from the semaphore queue in
which it is suspended
• Priority Inversion – Scheduling problem when lower-priority process
holds a lock needed by higher-priority process
– Solved via priority-inheritance protocol
 Classical Problems of Synchronization
• Classical problems used to test newly-proposed
synchronization schemes

– Bounded-Buffer Problem

– Readers and Writers Problem

– Dining-Philosophers Problem
 Bounded-Buffer Problem
• N buffers, each can hold one item

• Semaphore mutex initialized to the value 1

• Semaphore full initialized to the value 0

• Semaphore empty initialized to the value N

 Bounded Buffer Problem (Cont.)
• The structure of the producer process

do {

We must make sure

that the producer and
// produce an item in nextp
the consumer make The producer must wait
changes to the shared for an empty space in
buffer in a mutually wait (empty); the buffer (so that
exclusive manner
(Mutex lock – only one wait (mutex); producer can add its
process should use the data items)
buffer at one time- –
Now producer locked
the buffer)
// add the item to the buffer

signal (mutex);
signal (full);
} while (TRUE);
 Bounded Buffer Problem (Cont.)
• The structure of the consumer process

The consumer must wait for a

do { filled space in the buffer (so that
We must make sure wait (full); consumer consumes data items
that the producer and produced by producer using
the consumer make wait (mutex); mutex lock on buffer for that
changes to the shared
buffer in a mutually
particular consumer itself)
exclusive manner
(Mutex lock – only one // remove an item from buffer to nextc
process should use
the buffer at one time
– Now consumer signal (mutex);
locked the buffer)
signal (empty);

// consume the item in nextc

} while (TRUE);
 Readers/Writers Problem
W

R R
R

• Motivation: Consider a shared database

– Two classes of users:
• Readers – never modify database
• Writers – read and modify database
– Is using a single lock on the whole database sufficient?
• Like to have many readers at the same time
• Only one writer at a time
 Readers/Writers Problem
• A database is to be shared among several concurrent processes.
Some of these processes may want only to read the database,
whereas others may want to update the database
• We distinguish between these two types of processes by referring to
the former as readers and to the latter as writers.
• Obviously, if two readers access the shared data simultaneously,
nothing bad will happen
• However, if a writer and some other process (either a reader or a
writer) access the database simultaneously, chaos may ensue
 Readers/Writers Problem
• To ensure that these difficulties do not arise, we require that the
writers have exclusive access to the shared database
• There are several variations of this problem, all involving priorities
– The first and simplest one, referred to as the first readers/writers
problem, requires that no reader will be kept waiting unless a
writer has already obtained permission to use the shared object
(i.e., no reader should wait for other readers to finish simply
because a writer is waiting) NOTE: writers may starve
– The second readers/writers problem requires that, once a writer
is ready, that writer performs its write as soon as possible (i.e., if
a writer is waiting, no new readers may start reading) NOTE:
readers may starve
 Readers/Writers Problem
Shared Data
• Dataset
• Semaphore rw_mutex (read_write mutex) initialized to 1.
• Semaphore mutex initialized to 1.
• Integer read_count initialized to 0.
 Readers-Writers Problem (Cont.)
• The structure of a writer process
A writer will wait if either another
do { writer is currently writing or one or
more readers are currently reading
wait (wrt) ;

// writing is performed

signal (wrt) ;
} while (TRUE);
 Readers-Writers Problem (Cont.)
• The structure of a reader process
A reader will wait
only if a writer is
do { currently writing.
wait (mutex) ; Note that if
readcount == 1, no
readcount ++ ; reader is currently
We must make
sure that readers if (readcount == 1) //Perf by first reader reading and thus
that is the only time
update the shared wait (rw_mutex) ;//CS that a reader has to
variable
readcount in a signal (mutex) make sure that no
mutually writer is currently
exclusive manner writing (i.e., if
// reading is performed readcount > 1,
there is at least one
reader reading and
wait (mutex) ; thus the new reader
does not have to
readcount - - ; wait)
if (readcount == 0) //performed by last reader
signal (rw_mutex) ;
signal (mutex) ;
} while (TRUE);
Dining-Philosophers Problem
 Dining-Philosophers Problem

• Philosophers spend their lives thinking and eating

• Don’t interact with their neighbors, occasionally try to pick up 2
chopsticks (one at a time) to eat from bowl
– Need both to eat, then release both when done
• In the case of 5 philosophers
– Shared data
• Bowl of rice (data set)
• Semaphore chopstick [5] initialized to 1
 Dining-Philosophers Problem Algorithm
• The structure of Philosopher i: Only for 5 philosophers
do { i=0, then next chopstick i+1 =
0+1=1
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] ); A philosopher must wait for
his/her left and right chopsticks to
be available before he/she can
// eat start eating
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );

// think
} while (TRUE);
This solution guarantees that no two neighbors can be
eating simultaneously (i.e., mutual exclusion)
• What is the problem with this algorithm?
This solution could create a deadlock.
How?
 Problems with Semaphores
• Incorrect use of semaphore operations:

– signal (mutex) …. wait (mutex)

– wait (mutex) … wait (mutex)

– Omitting of wait (mutex) or signal

(mutex) (or both)

• Deadlock and starvation

 Monitors
• A high-level abstraction that provides a convenient and effective
mechanism for process synchronization
• Goal of OS is to share resources amongst many programs.
• Separate schedulers should be created for each class of resource.
• Each scheduler contains local data + procedures that programs may
use to acquire and release resources. Such a collection of data +
procedures is a monitor.

• Abstract data type, internal variables only accessible by code

within the procedure.
• Only one process may be active within the monitor at a time If
more than one program attempts to enter at the same time, only
one will succeed, and the remaining programs will remain on a
queue.
• But not powerful enough to model some synchronization schemes
 Monitors
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
procedure Pn (…) {……}
Initialization code (…) { … }
}
}
• Only one process should in CS.
• The methods only be access the shared procedures.
• Once the shared resources are predefined, then only it can be
accessed.
Schematic view of a Monitor
Process P1, or, P2, or P3

[Link] initialization component

contains the code that is used
exactly once when the monitor is
created
[Link] monitor procedures are
procedures that can be called
from outside of the monitor.
[Link] monitor entry
queue contains all threads that
called monitor procedures but
have not been granted
permissions.
[Link] Data
 Condition Variables
• Mutual exclusion → only one process/thread can execute inside
the monitor at a time.
• Condition variables → used to wait for certain conditions.
Inside a monitor you usually have:
• shared variables
• procedures
• condition variables (like x, y)

Example
monitor Example {
int data;
condition x, y;
}
 Condition Variables
Condition Variables
P1: [Link]()
Result P1: [Link]() → P1 goes to
P1 → moves to waiting queue of x waiting queue
P1 → blocked
P2: [Link]() → wakes P1

[Link]() P1 resumes execution

• When a process calls [Link]():
• It wakes up one process waiting on x
• That waiting process resumes execution

P2: [Link]() //[Link]() → does nothing

-> One process waiting on x (say P1) wakes up.
P1 continues execution.
 Condition Variables
condition x, y;
• Two operations on a condition variable:
– [Link] () – a process that invokes the operation is suspended
until [Link] ().
Example P1 calls [Link](). The P1 goes to suspend queue (goes to
waiting state), then P2 calls [Link](). The P1 resumes.
If a procedure calls wait, the calling program will block until some
other procedure calls signal.
– [Link] () – resumes one of processes (if any) that invoked
[Link] ().
When a procedure calls signal, then the lock on the monitor is also
released, and another program that previously called wait will run
immediately.
• If no [Link] () on the variable, then it has no effect on the
variable.
Monitor with Condition Variables
 Condition Variables Choices
• If process P invokes [Link] (), with Q in [Link] () state, what
should happen next?
– If Q is resumed, then P must wait

• Options include
– Signal and wait – P waits until Q leaves monitor or waits for
another condition
– Signal and continue – Q waits until P leaves the monitor or
waits for another condition
– Both have pros and cons – language implementer can decide
– Monitors implemented in Concurrent Pascal compromise
• P executing signal immediately leaves the monitor, Q is
resumed
– Implemented in other languages including Mesa, C#, Java
 Monitor Solution to Dining Philosophers
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
Philosophers number
void pickup (int i) { //fork pickup function
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;// another one is eating
}
void putdown (int i) { //put the fork
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
 Solution to Dining Philosophers (Cont.)

void test (int i) {//check if left and right philosophers are not eating
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ; //change state as eating
self[i].signal () ; //call signal function
}
}

initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
 Solution to Dining Philosophers (Cont.)

• Each philosopher i invokes the operations pickup() and

putdown() in the following sequence:

[Link] (i);

EAT

[Link] (i);

• No deadlock, but starvation is possible

 Monitor Implementation Using Semaphores
• Variables
semaphore mutex; // (initially = 1)-enter into monitor
semaphore next; // (initially = 0) – to suspend the
signalling process
int next_count = 0;// no of suspended processess

• Each procedure F will be replaced by

wait(mutex);
…
body of F;
…
if (next_count > 0) // check for suspended process
signal(next)
else
signal(mutex);

Mutual exclusion within a monitor is ensured

Monitor Implementation – Using Condition Variables
• For each condition variable x, we have:

semaphore x_sem; // (initially = 0)

int x_count = 0;

The operation [Link] The operation [Link] can

can be implemented as:
be implemented as:
x-count++;
if (x-count > 0) {
if (next_count > 0)
signal(next); next_count++;
else signal(x_sem);
signal(mutex); wait(next);
wait(x_sem); next_count--;
x-count--; }
Monitor Implementation – Using Condition Variables
• For each condition variable x, we have:

semaphore x_sem; // (initially = 0)

int x_count = 0;

The operation [Link]

can be implemented as:
x-count++;
if (next_count > 0) P1 calls [Link]()
signal(next);
else 1) x_count++ → register waiting
signal(mutex); 2) release monitor → allow others to enter
wait(x_sem); 3) wait(x_sem) → P1 sleeps
4) another process calls [Link]()
x-count--;
5) P1 wakes up
6) x_count--
Monitor Implementation – Using Condition Variables
• For each condition variable x, we have:

semaphore x_sem; // (initially = 0)

int x_count = 0;

The operation [Link] can

be implemented as:
P1: [Link]() → sleeps
if (x-count > 0) {
next_count++; P2: [Link]()
↓
signal(x_sem); wake P1
wait(next); P2 sleeps

next_count--; P1 runs
} P1 exits monitor

P2 resumes
Monitor Implementation – Using Condition Variables
• For each condition variable x, we have:

semaphore x_sem; // (initially = 0)

int x_count = 0;

The operation [Link]

can be implemented as:
x-count++; x_count → number of processes waiting on
if (next_count > 0) condition variable x
signal(next); x_sem → semaphore for condition variable x. used
to block processes waiting on condition x
else mutex → semaphore for mutual exclusion of the
signal(mutex); monitor
wait(x_sem); next → semaphore for processes that were
signaled
x-count--;
next_count → number of processes waiting on next
Monitor Implementation – Using Condition Variables
• For each condition variable x, we have:

semaphore x_sem; // (initially = 0)

int x_count = 0;

The operation [Link] can

be implemented as: x_count → number of processes
if (x-count > 0) { waiting on condition variable x
next_count++; x_sem → semaphore for condition
signal(x_sem); variable x
wait(next); next → semaphore for temporarily
suspending the signaling process
next_count--;
next_count → number of processes
} waiting on next
 Resuming Processes within a Monitor
• If several processes queued on condition x, and
[Link]() executed, which should be resumed?

• FCFS frequently not adequate

• conditional-wait construct of the form [Link](c)

– Where c is priority number
– Process with lowest number (highest priority) is
scheduled next
 A Monitor to Allocate Single Resource
monitor ResourceAllocator
{
boolean busy;
condition x;
void acquire(int time) {
if (busy)
[Link](time);
busy = TRUE;
}
void release() {
busy = FALSE;
[Link]();
}
initialization code() {
busy = FALSE;
}}
 Synchronization Examples
• Solaris

• Windows XP

• Linux

• Pthreads
 Solaris Synchronization
• Implements a variety of locks to support multitasking,
multithreading (including real-time threads), and multiprocessing
• Uses adaptive mutexes for efficiency when protecting data from
short code segments
– Starts as a standard semaphore spin-lock
– If lock held, and by a thread running on another CPU, spins
– If lock held by non-run-state thread, block and sleep waiting for
signal of lock being released
• Uses condition variables
• Uses readers-writers locks when longer sections of code need
access to data
• Uses turnstiles to order the list of threads waiting to acquire either
an adaptive mutex or reader-writer lock
– Turnstiles are per-lock-holding-thread, not per-object
• Priority-inheritance per-turnstile gives the running thread the
highest of the priorities of the threads in its turnstile
 Windows XP Synchronization
• Uses interrupt masks to protect access to global resources on
uniprocessor systems
• Uses spinlocks on multiprocessor systems
– Spinlocking-thread will never be preempted
• Also provides dispatcher objects user-land which may act mutexes,
semaphores, events, and timers
– Events
• An event acts much like a condition variable
– Timers notify one or more thread when time expired
– Dispatcher objects either signaled-state (object available) or
non-signaled state (thread will block)
 Linux Synchronization
• Linux:
– Prior to kernel Version 2.6, disables interrupts to implement
short critical sections
– Version 2.6 and later, fully preemptive

• Linux provides:
– semaphores
– spinlocks
– reader-writer versions of both

• On single-cpu system, spinlocks replaced by enabling and disabling

kernel preemption
 Pthreads Synchronization
• Pthreads API is OS-independent

• It provides:
– mutex locks
– condition variables

• Non-portable extensions include:

– read-write locks
– spinlocks