Operating Systems

Synchronization
Solutions
 Cooperating Processes

• Introduction to Cooperating Processes

• Producer/Consumer Problem
• The Critical-Section Problem
• Synchronization Hardware
• Semaphores

2
 Synchronization Hardware
• Many systems provide hardware support for
implementing the critical section code.
• All solutions below based on idea of locking:
– Protecting critical regions via locks.
• Uniprocessors – could disable interrupts:
– Currently running code would execute without preemption.
– Generally too inefficient on multiprocessor systems:
• Operating systems using this are not broadly scalable.
• Modern machines provide special atomic (non-
interruptible) hardware instructions:
– Either test memory word and set value at once.
– Or swap contents of two memory words.
3
 Interrupt Disabling
• On a Uniprocessor:
mutual exclusion is preserved
but efficiency of execution is
degraded: while in CS, we Process Pi:
cannot interleave execution repeat
with other processes that disable interrupts
are in RS. critical section
• On a Multiprocessor: enable interrupts
mutual exclusion is not remainder section
preserved: forever
– CS is now atomic but not
mutually exclusive
(interrupts are not disabled
on other processors).
4
 Special Machine Instructions
• Normally, access to a memory location
excludes other access to that same location.
• Extension: designers have proposed machines
instructions that perform 2 actions atomically
(indivisible) on the same memory location
(e.g., reading and writing).
• The execution of such an instruction is also
mutually exclusive (even on Multiprocessors).

5
 Solution to Critical Section Problem using Locks

• The general layout is of lock solution is:

do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);
6
 TestAndSet Synchronization Hardware
• Test and set (modify) the content of a word atomically (a
Boolean version):
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = TRUE;
return rv;
}
1. Executed atomically.
2. Returns the original value of passed parameter.
3. Set the new value of passed parameter to “TRUE”.
• The Boolean function represents the essence of the
corresponding machine instruction.
7
 Mutual Exclusion with TestAndSet
• Shared data:
boolean lock = FALSE;
Process Pi
do {
while (TestAndSet(&lock));
critical section
lock = FALSE;
remainder section
} while (TRUE);

8
 Another Test-and-Set Example
• An algorithm that uses testset for
• A C++ description Mutual Exclusion:
of machine instruction – Shared variable b is initialized to 0
of test-and-set:
– Only first Pi who sets b enters CS
bool testset(int& i) Process Pi:
{ repeat
if (i==0) { repeat{}
i=1; until testset(b);
return TRUE; CS
} else { b:=0;
return FALSE; RS
} forever
9 }
 Test-and-Set Instruction at Assembly Level

10 A. Frank - P. Weisberg
 Swap Synchronization Hardware
• Atomically swap (exchange) two variables:
void Swap(boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
}
• The procedure represents the essence of the
corresponding machine instruction.
11
 Mutual Exclusion with Swap
• Shared data:
boolean lock = FALSE;
• Process Pi
do {
/* Each process has a local Boolean variable key */
key = TRUE;
while (key == TRUE)
Swap(&lock, &key);
critical section
lock = FALSE;
remainder section
} while (TRUE);
12
 Swap instruction at Assembly Level

13 A. Frank - P. Weisberg
 Compare and Swap Synchronization Hardware
int compare_and_swap(int *value, int expected, int
new_value) {
int temp = *value;

if (*value == expected)
*value = new_value;
return temp;
}
1. Executed atomically.
2. Returns the original value of passed parameter “value”.
3. 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.
14
 Mutual Exclusion with Compare and Swap
• Shared integer “lock” initialized to 0;
• Solution:
do {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
} while (true);

15
 Disadvantages of Special Machine Instructions

• Busy-waiting is employed, thus while a process

is waiting for access to a critical section it continues
to consume processor time.
• No Progress (Starvation) is possible when a process
leaves CS and more than one process is waiting.
• They can be used to provide mutual exclusion but
need to be complemented by other mechanisms to
satisfy the bounded waiting requirement of the CS
problem.
• See next slide for an example.
16
 Critical Section Solution with TestAndSet()
• Process Pi
do {
waiting[i] = TRUE;
key = TRUE;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting[i] = FALSE;
critical section
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i) lock = FALSE;
else waiting[j] = FALSE;
remainder section
17 } while (TRUE);
 Mutex Locks (Spin Lock)
• Previous solutions are complicated and generally
inaccessible to application programmers.
• OS designers build software tools to solve critical
section problem.
• Simplest is mutex lock.
• Protect a critical section by first acquire() a lock then
release() the lock:
– Boolean variable indicating if lock is available or not.
• Calls to acquire() and release() must be atomic:
– Usually implemented via hardware atomic instructions.
• But this solution requires busy waiting:
18 – This lock therefore called a spinlock.
 acquire() and release()
• acquire() {
while (!available)
; /* busy wait */
available = false;;
}
• release() {
available = true;
}
• do {
acquire lock
critical section
release lock
remainder section
} while (true);
19
 Semaphores (1)
• Synchronization tool that provides more
sophisticated ways (than Mutex locks)
for process to synchronize their activities.
• Logically, a semaphore S is an integer
variable that, apart from initialization, can
only be changed through 2 atomic and
mutually exclusive operations:
– wait(S) (also down(S))
– signal(S) (also up(S))
• Less complicated.
20
 Critical Section of n Processes
• Shared data:
semaphore mutex; // initiallized to 1
• Process Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (TRUE);
21
 Semaphores (2)
• Access is via two atomic operations:

wait (S) :
while (S <= 0);
S--;

signal (S) :
S++;

22
 Semaphores (3)
• Must guarantee that no 2 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 CS 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.
23
 Semaphores (4)
• To avoid busy waiting, when a process has to wait, it will be
put in a blocked queue of processes waiting for the same event.
• Hence, in fact, a semaphore is a record (structure):
type semaphore = record
count: integer;
queue: list of process
end;
var S: semaphore;
• With each semaphore there is an associated waiting queue.
• Each entry in a waiting queue has 2 data items:
– value (of type integer)
– pointer to next record in the list
24
 Semaphore’s operations
• When a process must wait for a semaphore S, it is blocked and
put on the semaphore’s queue.
• Signal operation removes (assume a fair policy like FIFO) first
process from the queue and puts it on list of ready processes.
wait(S):
S.count--;
if (S.count<0) {
block this process
place this process in S.queue
}
signal(S):
S.count++;
if (S.count<=0) {
remove a process P from S.queue
place this process P on ready list
25 }
 Semaphore Implementation (1)
• Define semaphore as a C struct:
typedef struct {
int value;
struct process *list;
} semaphore;
• Assume 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.
26
 Semaphore Implementation (2)
• Semaphore operations now defined as
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);
}
27 }
 Two Types of Semaphores
1. Counting semaphore – integer value can range
over an unrestricted domain.
2. Binary semaphore – integer value can range
only between 0 and 1 (really a Boolean);
can be simpler to implement (use waitB and
signalB operations); same as Mutex lock.
• We can implement a counting semaphore S
using 2 binary semaphores (that protect its
counter).
28
 Binary semaphores
waitB(S):
if (S.count = 1) {
S.count := 0;
} else {
block this process
place this process in S.queue
}

signalB(S):
if (S.queue is empty) {
S.count := 1;
} else {
remove a process P from S.queue
place this process P on ready list
}
29
 Implementing S as a Binary Semaphore (1)
• Data structures:
binary-semaphore S1, S2;
int C;
• Initialization:
S1 = 1
S2 = 0
C = initial value of counting
semaphore S

30
 Implementing S as a Binary Semaphore (2)
• wait operation:
waitb(S1);
C--;
if (C < 0) {
signalb(S1);
waitb(S2); }
signalb(S1);
• signal operation:
waitb(S1);
C++;
if (C <= 0)
signalb(S2);
else signalb(S1);
31
 Semaphore as a General Synchronization Tool

• Execute B in Pj only after A executed in Pi

• Use semaphore flag initialized to 0.
• Code:
Pi Pj
M M
A wait(flag)
signal(flag) B
32
 Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for
an event that can be caused by only one of waiting processes.
• Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
M M
signal(S); signal(Q);
signal(Q) signal(S);
• Starvation – indefinite blocking. A process may never be
removed from the semaphore queue (say, if LIFO) in which
it is suspended.
• Priority Inversion – scheduling problem when lower-priority
process holds a lock needed by higher-priority process
33
 Problems with Semaphores
• Semaphores provide a powerful tool for enforcing
mutual exclusion and coordinate processes.
• But wait(S) and signal(S) are scattered among several
processes. Hence, difficult to understand their effects.
• Usage must be correct in all the processes (correct
order, correct variables, no omissions).
• Incorrect use of semaphore operations:
– signal (mutex) …. wait (mutex)
– wait (mutex) … wait (mutex)
– Omitting of wait (mutex) or signal (mutex) (or both)
• One bad (or malicious) process can fail the entire
collection of processes.
34
Operating Systems

Classical Problems
of Concurrency
 Introduction to Concurrency

• Classical Problems of Concurrency

• Monitors
• Inter-Process Communication (IPC)
• Synchronization Examples

36
 Classical Problems of Concurrency
• There are many of them –
let’s briefly see three
famous problems:
1. P/C Bounded-Buffer
2. Readers and Writers
3. Dining-Philosophers

37
 Reminder: P/C problem with race condition

38 A. Frank - P. Weisberg
 P/C Bounded-Buffer Problem
• We need 3 semaphores:
1. A semaphore mutex (initialized to 1) to
have mutual exclusion on buffer access.
2. A semaphore full (initialized to 0) to
synchronize producer and consumer on
the number of consumable items.
3. A semaphore empty (initialized to n) to
synchronize producer and consumer on
the number of empty spaces.
39
 Bounded-Buffer – Semaphores
• Shared data

semaphore full, empty, mutex;

Initially:

full = 0, empty = n, mutex = 1

40
 Bounded-Buffer – Producer Process
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (TRUE);
41
 Bounded-Buffer – Consumer Process
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (TRUE);
42
 Notes on P/C Bounded-Buffer Solution

• Remarks (from consumer point of view):

– Putting signal(empty) inside the CS of the
consumer (instead of outside) has no effect since
the producer must always wait for both semaphores
before proceeding.
– The consumer must perform wait(full) before
wait(mutex), otherwise deadlock occurs if
consumer enters CS while the buffer is empty.
• Conclusion: using semaphores is a
difficult art ... ☺
43
 Full P/C Bounded-Buffer Solution

44 A. Frank - P. Weisberg
 Readers-Writers Problem
• A data set/repository is shared among a number
of concurrent processes:
– Readers – only read the data set; they do not
perform any updates.
– Writers – can both read and write.
• Problem – allow multiple readers to read at the
same time. Only one single writer can access
the shared data at the same time.

45
 Readers-Writers Dynamics
• Any number of reader activities and writer
activities are running.
• At any time, a reader activity may wish to read
data.
• At any time, a writer activity may want to
modify the data.
• Any number of readers may access the data
simultaneously.
• During the time a writer is writing, no other
reader or writer may access the shared data.
46
 Readers-Writers with active readers

47 A. Frank - P. Weisberg
 Readers-Writers with an active writer

48 A. Frank - P. Weisberg
 Should readers wait for waiting writer?

49 A. Frank - P. Weisberg
 Readers-Writers problem
• There are various versions with different
readers and writers preferences:
1. The first readers-writers problem, requires that no
reader will be kept waiting unless a writer has
obtained access to the shared data.
2. The second readers-writers problem, requires that
once a writer is ready, no new readers may start
reading.
3. In a solution to the first case writers may starve;
In a solution to the second case readers may starve.

50
 First Readers-Writers Solution (1)
• readcount (initialized to 0) counter keeps
track of how many processes are currently
reading.
• mutex semaphore (initialized to 1) provides
mutual exclusion for updating readcount.
• wrt semaphore (initialized to 1) provides mutual
exclusion for the writers; it is also used by the
first or last reader that enters or exits the CS.

51
 First Readers-Writers Solution (2)

• Shared data
semaphore mutex, wrt;
int readcount;
Initially
mutex = 1, wrt = 1, readcount = 0

52
 First Readers-Writers – Writer Process

do {
wait(wrt);
…
writing is performed
…
signal(wrt);
} while(TRUE);
53
 First Readers-Writers – Reader Process
do {
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} while(TRUE);
54
 Dining Philosophers Problem (1)
• Philosophers spend their lives
alternating between thinking and
eating.
• Five philosophers can be seated
around a circular table.
• There is a shared bowl of rice.
• In front of each one is a plate.
• Between each pair of philosophers
there is a chopstick, so there are
five chopsticks.
• It takes two chopsticks to take/eat
rice, so while n is eating neither
n+1 nor n-1 can be eating.
55
 Dining Philosophers Problem (2)
• Each one thinks for a while, gets the
chopsticks/forks needed, eats, and puts the
chopsticks/forks down again, in an endless
cycle.
• Illustrates the difficulty of allocating resources
among process without deadlock and starvation.

56
 Dining Philosophers Problem (3)
• The challenge is to grant requests for chopsticks
while avoiding deadlock and starvation.
• Deadlock can occur if everyone tries to get their
chopsticks at once. Each gets a left chopstick,
and is stuck, because each right chopstick is
someone else’s left chopstick.

57
 Dining Philosophers Solution (1)
• Each philosopher
is a process. Process Pi:
repeat
• One semaphore think;
per fork: wait(fork[i]);
wait(fork[i+1 mod 5]);
– fork: array[0..4] eat;
of semaphores signal(fork[i+1 mod 5]);
– Initialization: signal(fork[i]);
fork[i].count := 1 forever
for i := 0..4
Note: deadlock if each philosopher starts by picking up
his left fork!
58
 Dining Philosophers Solution (2)
Possible solutions to avoid deadlock:
• Allow at most four 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.
59
 Dining Philosophers Solution (4)
• A solution: admit only 4
philosophers at a time Process Pi:
that try to eat. repeat
• Then 1 philosopher can think;
always eat when the other wait(T);
3 are holding 1 fork. wait(fork[i]);
wait(fork[i+1 mod 5]);
• Hence, we can use another eat;
semaphore T that would signal(fork[i+1 mod 5]);
limit at 4 the number of signal(fork[i]);
philosophers “sitting at signal(T);
the table”. forever
• Initialize: T.count := 4
60
 Dining Philosophers Solution (5)

...

61 A. Frank - P. Weisberg
 Dining Philosophers Problem (6)

62 A. Frank - P. Weisberg
 Monitors
• The monitor is a programming-language
construct that provides equivalent functionality
to that of semaphores and that is easier to
control.
• Implemented in a number of programming
languages, including
– Concurrent Pascal, Pascal-Plus,
– Modula-2, Modula-3, and Java.

63
 Monitors Characteristics
• Local data variables are accessible only by the
monitor
• Process enters monitor by invoking one of its
procedures
• Only one process may be executing in the
monitor at a time

64
 Synchronization
• Synchronisation achieved by condition
variables within a monitor
– only accessible by the monitor.
• Monitor Functions:
– Cwait(c): Suspend execution of the calling process
on condition c
– Csignal(c) Resume execution of some process
blocked after a cwait on the same condition

65
 Structure of a Monitor

66
 Monitor With Condition Variables

67 A. Frank - P. Weisberg
 Solution using Monitors

68
 Monitor solution cont.

69
 Inter-Process Communication (IPC)
• Mechanism for processes to communicate and
to synchronize their actions.
• Message system – processes communicate with
each other without resorting to shared variables.
• We have at least two primitives:
– send(destination, message) or send(message)
– receive(source, message) or receive(message)
• Message size is fixed or variable.

70
 Basic Message-passing Primitives

71 A. Frank - P. Weisberg
 Message format
• Consists of header and
body of message.
• In Unix: no ID, only
message type.
• Control info:
– what to do if run out of
buffer space.
– sequence numbers.
– priority.
• Queuing discipline: usually
FIFO but can also include
priorities.
72
 Mutual Exclusion – Message Passing
• create a mailbox mutex Process Pi:
shared by n processes. var msg: message;
• send() is non-blocking. repeat
receive(mutex,msg);
• receive() blocks when CS
mutex is empty. send(mutex,msg);
• Initialization: RS
send(mutex, “go”); forever
• The first Pi who executes
receive() will enter CS.
Others will be blocked
until Pi resends msg.
73
 Bounded-Buffer – Message Passing
• The producer place items (inside messages) in the
mailbox mayconsume.
• mayconsume acts as our buffer: consumer can
consume item when at least one message present.
• Mailbox mayproduce is filled initially with k null
messages (k= buffer size).
• The size of mayproduce shrinks with each
production and grows with each consumption.
• Solution can support multiple producers/consumers.
74
 Bounded-Buffer – Message Passing
Producer:
var pmsg: message;
repeat
receive(mayproduce, pmsg);
pmsg := produce();
send(mayconsume, pmsg);
forever

Consumer:
var cmsg: message;
repeat
receive(mayconsume, cmsg);
consume(cmsg);
send(mayproduce, null);
forever
75
 P/C Problem with Message Passing (1)

76
 P/C Problem with Message Passing (2)

77
 Resource starvation
• Starvation is similar to deadlock in that it causes a
process to freeze. Two or more processes become
deadlocked when each of them is doing nothing while
waiting for a resource occupied by another one.
• On the other hand, a process is in starvation when it is
waiting for a resource that simply keeps getting given
to other processes.
• A possible solution to starvation is to use a scheduling
algorithm with priority queue that increasing the
priority of processes that wait in the system for a long
time.
78
 Synchronization Examples

• Solaris
• Windows XP
• Linux
• Pthreads

79
 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.
80
 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).
81
 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
– Atomic integers
– spinlocks
– reader-writer versions of both.
• On single-CPU system, spinlocks replaced by enabling
and disabling kernel preemption.
82
 Pthreads Synchronization

• Pthreads API is OS-independent.

• It provides:
– mutex locks
– condition variables
• Non-portable extensions include:
– read-write locks
– spinlocks

83