Hong Bang International University

Department of Information Technology

04793 Operating Systems

Synchronization

Adapted from the textbook

Operating System Concepts – 10th Edition

Instructor: Hoang Ngoc Long

 Objectives and Outline

Objectives Outline
• To introduce the critical-section problem • Classic Problems of Synchronization
• Monitors
• Critical section solutions can be used to • Synchronization Examples from operating
ensure the consistency of shared data systems

• To present both software and hardware

solutions of the critical-section problem

2
 Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

3
 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.

buffer
prod cons

full = 4
empty = 6

4
 Bounded Buffer Problem

The structure of the producer process The structure of the consumer process

do { do {
// produce an item in nextp wait (full);
wait (mutex);
wait (empty);
wait (mutex); // remove an item from
// buffer to nextc
// add the item to the buffer
signal (mutex);
signal (mutex); signal (empty);
signal (full);
// consume the item in nextc
} while (TRUE); } while (TRUE);

5
 Readers-Writers Problem

• A data set 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

reader
writer
reader

Data Set
reader
writer
writer reader

6
 Readers-Writers Problem

• Shared Data
– Data set
– Integer readcount initialized to 0
• Number of readers reading the data at the moment
– Semaphore mutex initialized to 1
• Protects the readcount variable
(multiple readers may try to modify it)
– Semaphore wrt initialized to 1
• Protects the data set
(either writer or reader(s) should access data at a time)

7
 Readers-Writers Problem

The structure of a reader process

do {
The structure of a writer process wait (mutex) ;
readcount ++ ;
if (readcount == 1)
do {
wait (wrt) ;
wait (wrt) ; signal (mutex);
// writing is performed
// reading is performed
signal (wrt) ;
} while (TRUE); wait (mutex) ;
readcount -- ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);

8
 Dining-Philosophers Problem

a resource

a process

Assume a philosopher needs two forks to eat. Forks are like resources.
While a philosopher is holding a fork, another one can not have it.
9
 Dining-Philosophers Problem

• Is not a real problem; but lots of real resource allocation problems look like this. If we can solve
this problem effectively and efficiently, we can also solve the real problems.

• From a satisfactory solution:

– We want to have concurrency: two philosophers that are not sitting next to each other on the
table should be able to eat concurrently.

– We don’t want deadlock: waiting for each other indefinitely.

– We don’t want starvation: no philosopher waits forever.

10
Dining-Philosophers Problem (Cont.)

Semaphore chopstick [5] initialized to 1

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

// eat

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

// think
} while (TRUE);

This solution provides concurrency but may result in deadlock.

11
 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)

12
 Monitors

• A high-level abstraction that provides a convenient and effective mechanism for process synchronization
• Only one process may be active within the monitor at a time
– Threads monitoring to enter or a condition to happen
• Shared data/object put and accessed in monitor. Monitor controls access. No race condition then.
• Other names: thread-safe class, thread-safe object, or thread-safe module

monitor monitor-name
{
// shared variable declarations

procedure P1 (…) { …. }
…
procedure Pn (…) {……}

Initialization code ( ….) { … }

…
13
}
Schematic view of a Monitor

14
 Condition Variables

• condition x, y;

• Two operations on a condition variable:

– x.wait () – a process that invokes the operation is suspended.
– x.signal () – resumes one of processes (if any) that
invoked x.wait ()

15
Monitor with Condition Variables

16
 Condition Variables

• Condition variables are not semaphores. They are different even though they look similar.

– A condition variable does not count: have no associated integer.

– A signal on a condition variable x is lost (not saved for future use) if there is no process waiting
(blocked) on the condition variable x.

– The wait() operation on a condition variable x will always cause the caller of wait to block.
– The signal() operation on a condition variable will wake up a sleeping process on the condition
variable, if any. It has no effect if there is nobody sleeping.

17
 What happens when a process signals?

• If a process P signals (a waiting process Q), there is danger of two processes to be in monitor:
– Signaling process (P).
– Waiting process (Q) P Q
procedure f1() procedure f2()
(waiting for that signal).
…
…
x.wait()
… x.signal()
…
• Two possibilities:
– Signal and wait: Q in monitor (Hoare semantics)
– Signal and continue: P in monitor (Mesa semantics);
• This (Mesa) is most commonly used now!
• To be safe, you can try to put signal() at the end of the procedure.

18
 Condition variables: example

• Let us do an example.

• Assume we have a resource to be accessed by many processes. Assume we have 5 instances

of the resource. 5 processes can use the resource simultaneously.

• We want to implement a monitor that will implement two functions: acquire() and release() that
can be called by a process before and after using a resource.

19
 Condition variables: example

monitor Allocate
{
int count = 5; // we initialize count to 5.
condition c;

void acquire () {
if (count == 0)
c.wait();
count--;
}

void release () {
count++;
c.signal();
}
}
20
 Condition variables: example

A process will be coded like the following:

Allocate MA; // resource allocation monitor

….
MA.acquire();

// ….use the resource …

MA.release();

….

21
 Monitor Solution to Dining Philosophers

monitor DP {
enum { THINKING, HUNGRY, EATING } state [5];
condition cond [5];

void pickup (int i) { void test (int i) {

state[i] = HUNGRY; if ( (state[(i + 4) % 5] != EATING) &&
test(i); (state[(i + 1) % 5] != EATING) &&
if (state[i] != EATING) (state[i] == HUNGRY)) {
cond[i].wait(); state[i] = EATING ;
} cond[i].signal();
}
void putdown (int i) { }
state[i] = THINKING;
// test left and right neighbors initialization_code() {
test((i + 4) % 5) for (int i = 0; i < 5; i++)
test((i + 1) % 5); state[i] = THINKING;
} }

} /* end of monitor */ 22
 Solution to Dining Philosophers (cont)

• Each philosopher invokes the operations pickup() and putdown() in the following sequence:

Philosopher i

…
DP DiningPhilosophers;
….
while (1)
THINK…

DiningPhilosophters.pickup (i);

EAT /* use resource(s) */

DiningPhilosophers.putdown (i);

THINK…
}
23
 Monitor Solution to Dining Philosophers

#define LEFT (i+4)%5 THINKING?

#define RIGHT (i+1)%5 HUNGRY?
EATING?

state[LEFT] = ? state[i] = ? state[RIGHT] = ?

Process Process Process

… …
(i+4) % 5 i (i+1) % 5

Test(i)
Test(i+4 %5) Test(i+1 %5)

24
 Broadcast operation may be useful as well

• Broadcast on a condition variable: wakes up all sleeping processes

• Consider an allocation problem where each thread can request and can be given (if available)
multiple instances of a resource.
• Consider 3 threads.
– Thread 1 wants 10 instances
– Thread 2 wants 5 instances.
– Thread 3 has 5 instances.
• When thread 3 releases these 5 instances and signals on a condition variable and wakeup
thread 1, it is not enough for thread 1 and thread 1 will wait again.

25
 Broadcast operation may be useful as well

• Instead thread 3 can use broadcast operation on the condition variable.

• Assuming MESA semantics, the usage pattern is as follows:
– Always wait in a while loop (not if statement)
– That means: check the condition again after returning from wait

26
Monitor functions using broadcast on a condition
variable

Request (k) // request k instances

{
while (k > avail-count)
cv.wait();
avail-count -= k;
Thread Code
return
.
}
..
..
M.Request(m);
Release (k) // release k instances
{ // do something
avail-count += k;
cv.broadcast() M.Release (m);
} ..
..

27
 Spin Locks

• Kernel uses to protect short critical regions (a few instructions) on multi-processor systems.

• Assume we have a process A running in CPU 1 and holding a spin lock and executing the
critical region touching to some shared data.
• Assume at the same, another process B running in CPU 2 would like run a critical region
touching to the same shared data.

• B can wait on a semaphore, but this will cause B to sleep (a context switch is needed; costly
operation). However, critical section of A is short; It would be better if B would busy wait for a
while; then the lock would be available.

• Spin Locks are doing this. B can use a Spin Lock to wait (busy wait) until A will leave the critical
region and releases the Spin Lock. Since critical region is short, B will not wait much.

28
 Spin Locks

Process A running in kernel mode Process B running in kernel mode

(i.e. executing kernel code shown) (i.e. executing kernel code shown)

f1() {… f2() {…
acquire_spin_lock_(X); acquire_spin_lock_(X);
…//critical region…. …//critical region….
…touch to SD (shared data); …touch to SD (shared data);
release_spin_lock(X); release_spin_lock(X); …
} }

CPU 1 CPU 2

Kernel X lock variable (accessed atomically)

Main f1() {…}
Memory f2() {…} SD shared data

29
 Spin Locks

• a spin lock can be acquired after busy waiting.

• Remember the TestAndSet or Swap hardware instructions that are atomic even on multi-processor
systems. They can be used to implement the busy-wait acquisition code of spin locks.

• While process A is in the critical region, executing on CPU 1 and having the lock (X set to 1), process A
may be spinning on a while loop on CPU 2, waiting for the lock to be become available (i.e. waiting X to
become 0). As soon as process A releases the lock (sets X to 0), process B can get the lock (test and set
X), and enter the critical region.

30
 Synchronization Examples

• Solaris
• Windows XP
• Linux
• Pthreads
• Java

31
 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
• Uses condition variables and 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

32
 Windows XP Synchronization

• Uses interrupt masks to protect access to global resources on uniprocessor systems

• Uses spinlocks on multiprocessor systems
• Also provides dispatcher objects which may act as either mutexes and semaphores
• Dispatcher objects may also provide events
– An event acts much like a condition variable

33
 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
– spin locks

34
 Pthreads Synchronization

• Pthreads API is OS-independent

• It provides:
– mutex locks
– condition variables
– Semaphores

• Mutex locks and conditions variables together can be used like monitors. But there is no monitor
construct in C and pthreads
• Non-portable extensions include:
– read-write locks
– spin locks

35
 Pthreads

• Use of mutex locks and condition variables are very common in multithreaded Pthread
programs in Linux
– Also they are recommended synchronization variables.
• Usage patterns exist for use of mutex and condition variables.
– Study and use them.
• Note that there is no monitor in C.
– Hence condition variables in a Pthread C program is not accessed inside a monitor.
– Therefore they are used in combination with mutex locks.
– We need explicit locking (with mutex locks) to be used in our Pthread programs (with
monitor this is not required, but no monitor in C).
• Get lock at function start and release lock at function end.

36
 Pthreads

#include <pthread.h>

pthread_mutex_t mutex;
pthread_mutex_init (&mutex, NULL);

pthread_mutex_lock (&mutex);

// CS

pthread_mutex_unlock (&mutex);

37
 Pthreads

• Pthreads also have broadcast call on a condition variable.

– Wakes up all sleeping / waiting processes.
• Mesa semantics is used.
• The wait should be done in a loop (while loop).
– check condition and wait Loop.
– Do not check condition with an “if” statement.
• Check with “while” statement

38
 Usage Pattern

• When there is shared state (data) to be accessed by multiple processes, encapsulate it into a
shared object:
– Define a class with public/private methods and shared data and some other variables.
Shared data (shared state)
– Have a lock variable associated with the object (defined in the class)
– Have one or more condition variables (defined in the class)
– When a public method will access shared state, make it first acquire the lock in the
beginning and release the lock at the end.
– Wait on a condition variable when needed
• Use a while loop for this (this is safer and more modular)
– Signal or Broadcast on a condition variable when needed
• Mesa semantics

39
 Example

cv: condition variable

lock: a lock variable

method1 body: method2 body:

acquire (lock) acquire (lock)

//access shared state //access shared state

while (! an_expected_condition) // change the state to make

wait (cv, &lock); // expected condition true
signal(cv)
release(lock) // or broadcast (cv);
return;
release(lock)
return;
40
 Java Synchronization

Java provides rich set of synchronization features:

• Java monitors
• Reentrant locks
• Semaphores
• Condition variables
 Java Monitors

• Every Java object has associated with it a single lock.

• If a method is declared as synchronized, a calling thread must own the lock for the object.
• If the lock is owned by another thread, the calling thread must wait for the lock until it is
released.
• Locks are released when the owning thread exits the synchronized method.
Bounded Buffer – Java Synchronization
 Java Synchronization

• A thread that tries to acquire an unavailable lock is placed in the object’s entry set:
 Java Synchronization

• Similarly, each object also has a wait set.

• When a thread calls wait():
1. It releases the lock for the object
2. The state of the thread is set to blocked
3. The thread is placed in the wait set for the object
 Java Synchronization

• A thread typically calls wait() when it is waiting for a condition to become true.
• How does a thread get notified?
• When a thread calls notify():
1. An arbitrary thread T is selected from the wait set
2. T is moved from the wait set to the entry set
3. Set the state of T from blocked to runnable.
• T can now compete for the lock to check if the condition it was waiting for is now true.
Bounded Buffer – Java Synchronization
 Java Reentrant Locks

• Similar to mutex locks

• The finally clause ensures the lock will be released in case an exception occurs in the
try block.
 Java Semaphores

• Constructor:

• Usage:
 Java Condition Variables

• Condition variables are associated with an ReentrantLock.

• Creating a condition variable using newCondition() method of ReentrantLock:

• A thread waits by calling the await() method, and signals by calling the signal() method.
 Java Condition Variables

• Example:
• Five threads numbered 0 .. 4
• Shared variable turn indicating which thread’s turn it is.
• Thread calls doWork() when it wishes to do some work.
– (But it may only do work if it is their turn).
• If not their turn, wait
• If their turn, do some work for awhile …...
• When completed, notify the thread whose turn is next.
• Necessary data structures:
Java Condition Variables
 References

• The slides here are adapted/modified from the textbook and its slides: Operating System
Concepts, Silberschatz et al., 7th & 8th editions, Wiley.
• Operating System Concepts, 7th and 8th editions, Silberschatz et al. Wiley.
• Modern Operating Systems, Andrew S. Tanenbaum, 3rd edition, 2009.

53
 End of Chapter

Adapted from the textbook

Operating System Concepts – 10th Edition

Instructor: Hoang Ngoc Long