OPERATING SYSTEMS

Chapter 5
Process Synchronization
Week 09+10, CS3104-Operating Systems
Syed Sherjeel Ahmad Gilani, Spring 2018
Process Synchronization
 Background
 The Critical-Section Problem
 Peterson’s Solution
 Synchronization Hardware
 Semaphores
 Synchronization Examples
 Atomic Transactions
 POSIX Synchronization

2 Operating Systems (Spring 2018)

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

 To explore classical problems in process

synchronization.
3 Operating Systems (Spring 2018)
Background
 Concurrent access to shared data may result
in data inconsistency.
 Maintaining data consistency requires
mechanisms to ensure the orderly execution
of cooperating processes.
 Shared-memory solution to bounded-buffer
problem (Chapter 4) allows at most n – 1
items in buffer at the same time. A solution,
where all N buffers are used is not simple.
 Suppose that we modify the producer-consumer
code by adding a variable counter, initialized to 0
and incremented each time a new item is added to
the buffer
4 Operating Systems (Spring 2018)
 Bounded-Buffer

 Shared data

#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

5 Operating Systems (Spring 2018)

Bounded-Buffer
 Producer process

item nextProduced;

while (1) {
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
6 Operating Systems (Spring 2018)
Bounded-Buffer
 Consumer process

item nextConsumed;

while (1) {
while (counter == 0)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}

7 Operating Systems (Spring 2018)

Bounded Buffer
 The statements

counter++;
counter--;

must be performed atomically.

 Atomic operation means an operation that

completes in its entirety without interruption.

8 Operating Systems (Spring 2018)

Bounded Buffer
 The statement “counter++” may be
implemented in machine language as:

register1 = counter
register1 = register1 + 1
counter = register1

 The statement “counter--” may be

implemented as:

register2 = counter
register2 = register2 – 1
9 counter = register2
Operating Systems (Spring 2018)
Bounded Buffer
 If both the producer and consumer attempt to
update the buffer concurrently, the assembly
language statements may get interleaved.

 Interleaving depends upon how the producer

and consumer processes are scheduled.

10 Operating Systems (Spring 2018)

Bounded Buffer
 Assume counter is initially 5. One
interleaving of statements is:

producer: register1 = counter (register1 =

5)
producer: register1 = register1 + 1
(register1 = 6)
consumer: register2 = counter (register2 =
5)
consumer: register2 = register2 – 1
(register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter =
11 Operating Systems (Spring 2018)
4)
Race Condition
 Race condition: The situation where several
processes access – and manipulate shared
data concurrently. The final value of the
shared data depends upon which process
finishes last.
 To guard against the race condition, we need
to ensure that only one process at a time can
access the data
 To prevent race conditions, concurrent
processes must be synchronized.

12 Operating Systems (Spring 2018)

Critical Section
 A piece of code in a cooperating process in
which the process may update shared data.
(variable, file, database etc.)

 Critical Section Problem: Serialize executions

of critical sections in cooperating processes.

13 Operating Systems (Spring 2018)

Critical Section
 Let a system consisting of n processes {P 0,
P1, ..., Pn}
 Each process has a segment of code, called a
critical section
 in which the process may be changing common
variables, updating a table, writing a file, and so on
 When one process is executing in its critical
section, no other process is to be allowed to
execute in its critical section
 No two processes are executing in their critical
sections at the same time

14 Operating Systems (Spring 2018)

Critical Section
 General structure of process pi is (Structure of
solution)

15 Operating Systems (Spring 2018)

Critical Section
 Each process must request permission to
enter its critical section
 The section of code implementing this request
is the entry section
 The critical section is followed by an exit
section
 The remaining code is the remainder
section

16 Operating Systems (Spring 2018)

Solution to Critical-Section Problem
 Requirements for a solution to the critical section problem
are:(following three properties of a good solution)
 Mutual Exclusion - If process Pi is executing in its critical
section, then no other processes can be executing in their
critical sections
 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, processes which are in remainder section will
not participate in this decision that which process will go
into critical section
 Bounded Waiting - A bound must exist on the number of
times that other processes are allowed to enter their critical
sections after a process has made a request to enter its
critical section and before that request is granted
17
Peterson’s Solution
 Two process solution
 The two processes share two variables:
 int turn;
 Boolean flag[2]
 The variable turn indicates whose turn it is to
enter the critical section
 The flag array is used to indicate if a process
is ready to enter the critical section
 flag[i] = true implies that process Pi is ready

18 Operating Systems (Spring 2018)

Algorithm for Process Pi
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);

 Provable that
1. Mutual exclusion is preserved
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met
19 Operating Systems (Spring 2018)
Synchronization Hardware
 Many systems provide hardware support for
critical section code
 Modern machines provide special atomic
hardware instructions
 Atomic instruction = non-interruptable
 Race conditions are prevented by requiring
that critical regions be protected by locks
 That is, a process must acquire a lock before
entering a critical section
 It releases the lock when it exits the critical
section

20 Operating Systems (Spring 2018)

Solution to Critical-section
Problem Using Locks
do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);

21 Operating Systems (Spring 2018)

 A Semaphore

Value: -6

Queue:

23 Operating Systems (Spring 2018)

Semaphores
 Synchronization tool that does not
require busy waiting
 Semaphore S – integer variable
 Queue is used to hold processes
waiting on the semaphore
 Can only be accessed via two
indivisible (atomic) operations
 Wait and signal operations cannot be interrupted
 The wait() operation was originally termed P (from
the Dutch proberen, “to test”)
 signal() was originally called V (from verhogen, “to
increment”).

24 Operating Systems (Spring 2018)

 Critical Section of n Processes
 Shared data:
semaphore mutex; //initially mutex =
1

 Process Pi:

do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);
25 Operating Systems (Spring 2018)
Semaphore Implementation
 Define a semaphore as a record
typedef struct {
int value;
struct process *list;
} semaphore;

 Assume two simple operations:

 block suspends the process that invokes it.
 wakeup(P) resumes the execution of a blocked
process P.

26 Operating Systems (Spring 2018)

Implementation
 Semaphore operations now defined as
wait(S):
S.value--;
if (S.value < 0) {
add this process to S.list;
block;
}

signal(S):
S.value++;
if (S.value <= 0) {
remove a process P from S.list;
wakeup(P);
}

27 Operating Systems (Spring 2018)

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
 
A wait(flag)
signal(flag) B

28 Operating Systems (Spring 2018)

Java Semaphore

 http://docs.oracle.com/javase/1.5.0/docs/api/ja
va/util/concurrent/Semaphore.html

29 Operating Systems (Spring 2018)

Assignment
 http://javarevisited.blogspot.com/2012/05/cou
nting-semaphore-example-in-java-5.html

 An example has been posted on the web page

(url above), your task is to implement that
example into java and excute it.
 What to submit – A rar/zip file with
 Complete code in .java file with
 One page (pdf) of description of different methods
and your understanding of the whole program.
 When to submit – 18May2018.

30 Operating Systems (Spring 2018)

Deadlock
 Deadlock – two or more processes are
waiting indefinitely for an event that can be
caused by only one of the waiting processes
 A set of blocked processes each holding a
resource and waiting to acquire a resource
held by another process in the set

 Example
 System has 2 disk drives
 P1 and P2 each hold one disk drive and each needs
another one

31 Operating Systems (Spring 2018)

Deadlock
 To illustrate this, consider a system consisting
of two processes, P0 and P1, each accessing
two semaphores, S and Q, set to the value 1:

32 Operating Systems (Spring 2018)

Starvation and Priority Inversion
 Starvation – indefinite blocking
 A process may never be removed from
the semaphore queue in which it is
suspended
 Indefinite blocking may occur if we
remove processes from the list
associated with a semaphore in LIFO
(last-in, first-out) order.
 Priority Inversion – Scheduling problem
when lower-priority process holds a lock
needed by higher-priority process
 Solution: implementing a priority-inheritance
33
protocol. Operating Systems (Spring 2018)
Classical Problems of Synchronization
 Bounded-Buffer Problem

 Readers and Writers Problem

 Dining-Philosophers Problem

34 Operating Systems (Spring 2018)

Producer/Consumer Problem
 One or more producers are generating data and
placing data in a buffer
 A single consumer is taking items out of the
buffer one at a time
 Only one producer or consumer may access the
buffer at any one time
 Two semaphores are used
 one to represent the amount of items in the buffer
 one to signal that it is all right to use the buffer

35 Operating Systems (Spring 2018)

Bounded-Buffer Problem
 Shared data

semaphore full, empty, mutex;

Initially:

full = 0, empty = n, mutex = 1

36 Operating Systems (Spring 2018)

Bounded-Buffer Problem Producer Process
 Shared data
semaphore full, empty, mutex;
Initially:
full = 0, empty = n, mutex = 1

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
37 Operating Systems (Spring 2018)
Bounded-Buffer Problem Consumer Process

do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);
38 Operating Systems (Spring 2018)
Bounded-Buffer Problem Producer Consumer
 Shared data
semaphore full, empty, mutex;
Initially:
full = 0, empty = n, mutex = 1
//Producer //Consumer
do { do {
… wait(full)
produce an item in nextp wait(mutex);
… …
wait(empty); remove an item from buffer to
nextc
wait(mutex);
…
…
signal(mutex);
add nextp to buffer
signal(empty);
…
…
signal(mutex);
consume the item in nextc
signal(full);
…
} while (1);
} while (1);
39 Operating Systems (Spring 2018)
Readers/Writers Problem
 Any number of readers may simultaneously
read the file
 Only one writer at a time may write to the file
 If a writer is writing to the file, no reader may
read it

40 Operating Systems (Spring 2018)

Readers-Writers Problem
Shared data
 semaphore mutex, rw_mutex,
readcount;
Writer Process
 Initially mutex = 1, rw_mutex = 1,
readcount = 0
wait(rw_mutex);
…
writing is performed
…
signal(rw_mutex);

41 Operating Systems (S2018)

Readers-Writers Problem Reader Process
wait(mutex);
readcount++;
if (readcount == 1)
wait(rw_mutex);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(rw_mutex);
signal(mutex):
42 Operating Systems (Spring 2018)
Dining Philosophers Problem

 Shared data
semaphore chopstick[5];
Initially all values are 1
43 Operating Systems (Spring 2018)
Dining-Philosophers Problem
 Philosopher i:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
44 Operating Systems (S2018)
Dining-Philosophers Problem - Deadlock
 Suppose that all five philosophers become hungry
at the same time and each grabs her left
chopstick
 Deadlock will occur
 Solutions could be;
 Allow at most four philosophers to be sitting
simultaneously at the table.
 Allow a philosopher to pick up her chopsticks only if
both chopsticks are available (to do this, she must
pick them up in a critical section).
 Use an asymmetric solution—that is, an odd-
numbered philosopher picks up first her left
chopstick and then her right chopstick, whereas an
even-numbered philosopher picks up her right
chopstick and then her left chopstick
45 Operating Systems (S2018)
 PROCESS SYNCHRONIZATION
High-level synchronization construct that allows the safe sharing
of an abstract data type among concurrent processes.

monitor monitor-name
{
shared variable declarations
procedure body P1 (…) {
...
}
procedure body P2 (…) {
...
}
procedure body Pn (…) {
...
}
{
initialization code
}
46 Operating Systems (S2018)
}
Modern OSs
 Windows, Linux, and Solaris provide
mechanisms such as semaphores, mutex
locks, spinlocks, and condition variables to
control access to shared data.

 Pthreads API provides support for mutex locks

and semaphores, as well as condition
variables.

47 Operating Systems (S2018)

 Windows XP Synchronization
 Uses interrupt masks to protect access to
global resources on uniprocessor systems.
 Uses spinlocks on multiprocessor systems.
 Also protects spinlocks, by not allowing a
process to be preempted when holding a
spinlock.
 Also provides dispatcher objects which may
act as mutexes and semaphores.
 Dispatcher objects may also provide events.
An event acts much like a condition variable.

48
Operating Systems (S2018)
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
POSIX Synchronization
 POSIX supports
 mutex locks for short-term locking
 condition variables for waiting on events of
unbounded duration
 Synchronization functions available in the
POSIX:THR Extension
 mutex locks
 conditions variables
 read-write locks

50 Operating Systems (S2018)

POSIX Synchronization
 Mutex locks are ideal for making changes to
data structures
 state of the data structure is temporarily
inconsistent
 E.g. updating pointers in a shared linked list
 These locks are designed to be held for a short
time
 Use condition variables to synchronize on
events of indefinite duration
 E.g. waiting for input

51 Operating Systems (S2018)

POSIX Synchronization
 Each synchronization mechanism provides an
initialization function and a function for
destroying the object
 The mutex locks and condition variables allow
static initialization
 All three types of synchronization have
associated attribute objects

52 Operating Systems (S2018)

mutex locks
 A mutex is a special variable that can be either in
the locked state or the unlocked state
 If the mutex is locked, it has a distinguished
thread that holds or owns the mutex
 If no thread holds the mutex, we say the mutex is
unlocked, free or available
 The mutex also has a queue for the threads that
are waiting to hold the mutex
 The order in which the threads in the mutex
queue obtain the mutex is determined by the
thread-scheduling policy

53 Operating Systems (S2018)

Acknowledgement & References
 Silberschatz et. al. , “Operating System Concepts”
 Kay A. Robbins and Steve Robbins, "UNIX
Systems Programming: Communication,
Concurrency and Threads", 2nd Edition, ISBN:
0130424110, Prentice Hall, June 27, 2003

54 Operating Systems (S2018)