CENG328- OPERATING

SYSTEMS
PROCESS SYNCHRONIZATION
Outline
● The Critical Section Problem
● Synchronization Hardware
● Semaphores
● Classical Problems of Synchronization
● Critical Regions
● Monitors
Producer-Consumer Problem

1.The Producer process must not produce an

item if the shared buffer is full.

2.The Consumer process must not consume an

item if the shared buffer is empty.

3.Access to the shared buffer must be mutually

exclusive; this means that at any given
instance, only one process should be able to
access the shared buffer and make changes to
it.
Producer-Consumer Problem
● Paradigm for cooperating processes;
● producer process produces information that is
consumed by a consumer process.
● We need buffer of items that can be filled by
producer and emptied by consumer.
• Unbounded-buffer places no practical limit on the size of the
buffer. Consumer may wait, producer never waits.
• Bounded-buffer assumes that there is a fixed buffer size.
Consumer waits for new item, producer waits if buffer is
full.
● Producer and Consumer must synchronize.
Producer-Consumer Problem
Bounded Buffer using IPC
(messaging)
● Producer
repeat
…
produce an item in nextp;
…
send(consumer, nextp);
until false;
● Consumer
repeat
receive(producer, nextc);
…
consume item from nextc;
…
until false;
Bounded-buffer - Shared
Memory Solution
● Shared data
var n;
type item = ….;
var buffer: array[0..n-1] of item;
in, out: 0..n-1;
in :=0; out:= 0; /* shared buffer = circular array */
/* Buffer empty if in == out */
/* Buffer full if (in+1) mod n == out */
/* noop means ‘do nothing’ */
Bounded Buffer - Shared
Memory Solution
● Producer process - creates filled buffers
repeat
…
produce an item in nextp
…
while in+1 mod n = out do noop;
buffer[in] := nextp;
in := in+1 mod n;
until false;
Bounded Buffer - Shared
Memory Solution
● Consumer process - Empties filled buffers
repeat
while in = out do noop;
nextc := buffer[out] ;
out:= out+1 mod n;
…
consume the next item in nextc
…
until false
Shared data
● 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 the bounded-
buffer problem allows at most (n-1) items in
the buffer at the same time.
Bounded Buffer
● A solution that uses all N buffers is not that
simple.
● Modify producer-consumer code by adding a variable
counter, initialized to 0, incremented each time a new
item is added to the buffer
● Shared data
type item = ….;
var buffer: array[0..n-1] of item;
in, out: 0..n-1;
counter: 0..n;
in, out, counter := 0;
Bounded Buffer
● Producer process - creates filled buffers
repeat
…
produce an item in nextp
…
while counter = n do noop;
buffer[in] := nextp;
in := in+1 mod n;
counter := counter+1;
until false;
 Bounded Buffer
● Consumer process - Empties filled buffers
repeat
while counter = 0 do noop;
nextc := buffer[out] ;
out:= out+1 mod n;
counter := counter - 1;
…
consume the next item in nextc
…
until false;
● The statements
counter := counter + 1;
counter := counter - 1;

must be executed atomically.

● Atomic Operations
● An operation that runs to completion or not at all.
 The Critical-Section Problem
● N processes all competing to use shared data.
• Structure of process Pi ---- Each process has a code segment, called the
critical section, in which the shared data is accessed.
repeat
entry section /* enter critical section */
critical section /* access shared variables */
exit section /* leave critical section */
remainder section /* do other work */
until false

● Problem
• Ensure that when one process is executing in its critical section, no
other process is allowed to execute in its critical section.

18
Solution: Critical Section
Problem - Requirements
● Assume that each process executes at a
nonzero speed in the critical section. That is,
assume that each process finishes executing
the critical section once entered
● No assumption concerning relative speed of
the n processes.
● Assume that a process can get stuck in its
remainder section indefinitely, e.g., in a non-
terminating while loop

20
 Supporting Synchronization

Programs Shared Programs

Higher-level
Locks Semaphores Monitors Send/Receive CCregions
API

Hardware Load/Store Disable Ints Test&Set Comp&Swap

● We are going to implement various synchronization primitives using

atomic operations
● Everything is pretty painful if only atomic primitives are load and store
● Need to provide inherent support for synchronization at the hardware level
● Need to provide primitives useful at software/user level
How to implement Locking?
Software Solutions
Hardware Solutions
 Hardware Support: Other
examples
● swap (&address, register) { /* x86 */
temp = M[address];
M[address] = register;
register = temp;
}
● compare&swap (&address, reg1, reg2) { /* 68000 */
if (reg1 == M[address]) {
M[address] = reg2;
return success;
} else {
return failure;
}
}
● load-linked&store conditional(&address) {
/* R4000, alpha */
loop:
ll r1, M[address];
movi r2, 1; /* Can do arbitrary comp */
sc r2, M[address];
beqz r2, loop;
}
Busy Waiting
 Mutex Locks
● 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 acquiring a lock and then releasing the lock
● Boolean variable indicating if lock is available or not
● Calls to acquire()/wait() and release() must be atomic
● Usually implemented via hardware atomic instructions
● But this solution requires busy waiting
● This lock therefore called a spinlock

57
 acquire() and release()

Semantics of acquire
● acquire(mutex_lock) {
while Test&Set(mutex_lock)) ; /* busy wait */
}
● Semantics of release
● release(mutex_lock) {
mutex_lock = 0;
}
● Critical section implementation
do {
acquire (lock)
critical section
release (lock)
remainder section
} while (true);

58
Spinlock vs Mutex
Mutex

• Advantages • Disadvantages
• Mutex is just simple locks • If a thread obtains a lock and goes
obtained before entering its to sleep or is preempted, then the
critical section and then releasing other thread may not move
it. forward. This may lead to
• Since only one thread is in its starvation.
critical section at any given time, • It can't be locked or unlocked
there are no race conditions, and from a different context than the
data always remain consistent. one that acquired it.
• Only one thread should be
allowed in the critical section at a
time.
• The normal implementation may
lead to a busy waiting state,
which wastes CPU time.
Change low priority task priority to higher value
SEMAPHORES
Is this solution correct? What is the problem then?
P() = down() = wait()
V () = up() = signal()
 Semaphores
Semaphore is distinguished by the operating system in two categories;
Counting semaphore and Binary semaphore.
Blocked here!
Mutual Exclusion Using Semaphores

semaphore s = 1;
Pi { P() = down() = wait()
while(1) { V () = up() = signal()
semWait(s);
/* Critical Section */
semSignal(s);
/* remainder */
}
}

79
 Process Process Critical Region
Value of
Queue A B
Semaphore Normal Execution

lock Blocked on
semaphore
1 semWait(lock) lock

0
semWait(lock)

B 0
semSignal(lock) semWait(lock)

01
semSignal(lock)

1
80
Semaphore Example 1

semaphore s = 2; • What happens?

Pi {
while(1) {
semWait(s); • When might this be
/* CS */ desirable?
semSignal(s);
/* remainder */
}
}

81
Semaphore Example 1

semaphore s = 2; • What happens?

Pi {
while(1) {
semWait(s); • When might this be
/* CS */ desirable?
semSignal(s);
/* remainder */
}
}

×× ×
s = 2 1 0 -1

82
Semaphore Example 1

semaphore s = 2; • What happens?

Pi { • Allows up to 2 processes to
while(1) { enter CS
semWait(s); • When might this be
/* CS */ desirable?
• Need up to 2 processes inside
semSignal(s);
CS
/* remainder */ • e.g., limit number of processes
reading a var
}
• Be careful not to violate
} mutual exclusion inside CS!

83
Semaphore Example 2

semaphore s = 0; • What happens?

Pi {
while(1) {
semWait(s); • When might this be
/* CS */ desirable?
semSignal(s);
/* remainder */
}
}

84
Semaphore Example 2

semaphore s = 0; • What happens?

Pi {
while(1) {
semWait(s); • When might this be
/* CS */ desirable?
semSignal(s);
/* remainder */
}
}

× × ×
s = 0 -1 -2 -3

85
Semaphore Example 2

semaphore s = 0; • What happens?

Pi { • No one can enter CS! Ever!
while(1) { • When might this be
semWait(s); desirable?
/* CS */ • Never!
semSignal(s);
/* remainder */
}
}

86
 Semaphore Example 3

semaphore s = 0; semaphore s; /* shared */

P1 { P2 {
/* do some stuff */ /* do some stuff */
semWait(s); semSignal(s);
/* do some more stuff */ /* do some more stuff */
} }
 What happens?

 When might this be desirable?

87
 Semaphore Example 3

semaphore s = 0; semaphore s; /* shared */

P1 { P2 {
/* do some stuff */ /* do some stuff */
semWait(s); semSignal(s);
/* do some more stuff */ /* do some more stuff */
} }
 What happens?

××
s = 1 0 1

 When might this be desirable?

88
 Semaphore Example 3

semaphore s = 0; semaphore s; /* shared */

P1 { P2 {
/* do some stuff */ /* do some stuff */
semWait(s); semSignal(s);
/* do some more stuff */ /* do some more stuff */
} }
 What happens?
 P1 waits until P2 signals
 if P2 signals first, P1 does not wait
 When might this be desirable?
 Having a process/thread wait for another process/thread
89
 Semaphore Example 4

Process 1 executes: Process 2 executes:

while(1) { while(1) {
semWait(S); semWait(Q);
a; b;
semSignal(Q); semSignal(S);
} }
 Two processes
 Two semaphores: S and Q

 Protect two critical variables ‘a’ and ‘b’.

 What happens in the pseudocode if Semaphores S and

Q are initialized to 1 (or 0)?
90
 Semaphore Example 4

Process 1 executes: Process 2 executes:

while(1) { while(1) {
semWait(S); semWait(Q);
a; b;
semSignal(Q); semSignal(S);
} }

×
S = 0 -1

×
Q = 0 -1

91
 Semaphore Example 4

Process 1 executes: Process 2 executes:

while(1) { while(1) {
semWait(S); semWait(Q);
a; b;
semSignal(Q); semSignal(S);
} }

×××
S = 1 0 1 0

×××
Q = 1 0 1 0

92
 Semaphore Example 4

Process 1 executes: Process 2 executes:

while(1) { while(1) {
semWait(S); semWait(Q);
a; b;
semSignal(Q); semSignal(S);
} }

×× ××
S = 1 0 -1 0 1

×××
Q = 1 0 1 0

93
 Be careful!

Deadlock or Violation of Mutual Exclusion?

semSignal(s); semWait(s);
1 critical_section(); 4 critical_section();
semWait(s); semWait(s);

semWait(s); semWait(s);
2 5
critical_section(); semWait(s);
critical_section();
semSignal(s);
critical_section(); semSignal(s);
3
semSignal(s);
94
 Be careful!

Mutual exclusion violation Certain deadlock!

semSignal(s); semWait(s);
1 critical_section(); 4 critical_section();
semWait(s); semWait(s);

Possible deadlock Deadlock again!

semWait(s); semWait(s);
2 5
critical_section(); semWait(s);
critical_section();
Mutual exclusion violation semSignal(s);
critical_section(); semSignal(s);
3
semSignal(s);
95
Block/Resume Semaphore
Implementation
● If process is blocked, enqueue PCB of process
and call scheduler to run a different process.
● Semaphores are executed atomically;
● no two processes execute wait and signal at the same
time.
● Mutex can be used to make sure that two processes do
not change count at the same time.
• If an interrupt occurs while mutex is held, it will result in a
long delay.
• Solution: Turn off interrupts during critical section.

96
Two Types of Semaphores
● Counting Semaphore - integer value can range
over an unrestricted domain.
● Binary Semaphore - integer value can range
only between 0 and 1; simpler to implement.
● Can implement a counting semaphore S as a
binary semaphore.

97
Difference between Mutex and Semaphore

• Mutex uses a locking mechanism

• if a process wants to use a resource then it locks the resource, uses it and then
release it.
• semaphore uses a signalling mechanism
• wait() and signal() methods are used to show if a process is releasing a resource
or taking a resource.
• A mutex is an object but semaphore is an integer variable.
• In semaphore, we have wait() and signal() functions. But in mutex, there is
no such function.
• A mutex object allows multiple process threads to access a single shared
resource but only one at a time.
• On the other hand, semaphore allows multiple process threads to access the
finite instance of the resource until available.
• In mutex, the lock can be acquired and released by the same process at a
time.
• The value of the semaphore variable can be modified by any process that
needs some resource but only one process can change the value at a time.
Classical Problems of
Synchronization
● Bounded Buffer Problem
● Readers and Writers Problem
● Dining-Philosophers Problem

Principles of Operating Systems -

Process Synchronization 99
Bounded Buffer Problem
● Shared data
type item = ….;
var buffer: array[0..n-1] of item;
full, empty, mutex : semaphore;
nextp, nextc :item;
full := 0; empty := n; mutex := 1;

Principles of Operating Systems -

Process Synchronization 100
The Producer Operation

Principles of Operating Systems -

Process Synchronization 102
The Consumer Operation

Principles of Operating Systems -

Process Synchronization 104
Discussion

● ASymmetry?
● Producer does: P(empty), V(full)
● Consumer does: P(full), V(empty)
● Is order of P’s important?
● Yes! Can cause deadlock
● Is order of V’s important?
● No, except that it might affect scheduling efficiency

Principles of Operating Systems -

Process Synchronization 105
 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
The Solution

• Readers have higher priority than writer.

• If a writer wants to write to the resource, it must wait until
there are no readers currently accessing that resource.
• Here, we use one mutex m and a semaphore w.
• An integer variable read_count is used to maintain the
number of readers currently accessing the resource.
• The variable read_count is initialized to 0. A value of 1 is
given initially to m and w.
• Instead of having the process to acquire lock on the shared
resource, we use the mutex m to make the process to
acquire and release lock whenever it is updating
the read_count variable.
The Solution

writer process

reader process
 Dining-Philosophers Problem

Shared Data
var chopstick: array [0..4] of semaphore (=1 initially);

111
The Solution
Higher Level Synchronization
● Timing errors are still possible with
semaphores
● Example 1
signal (mutex);
…
critical region
...
wait (mutex);
● Example 2
wait(mutex);
…
critical region
...
wait (mutex);
● Example 3
wait(mutex);
…
critical region
...
Forgot to signal
114
Monitors
High-level synchronization construct that allows the safe sharing of
an abstract data type among concurrent processes.

120
Characteristics of Monitors

• Inside the monitors, we can only execute one process at a time.

• Monitors are the group of procedures, and condition variables that
are merged together in a special type of module.
• If the process is running outside the monitor, then it cannot access
the monitor’s internal variable. But a process can call the procedures
of the monitor.
• Monitors offer high-level of synchronization
• Monitors were derived to simplify the complexity of synchronization
problems.
• There is only one process that can be active at a time inside the
monitor.
 Monitor with Condition
Variables

● Lock: the lock provides mutual exclusion to shared data

● Always acquire before accessing shared data structure
● Always release after finishing with shared data
● Lock initially free
● Condition Variable: a queue of threads waiting for something inside a
critical section
● Key idea: make it possible to go to sleep inside critical section by atomically
releasing lock at time we go to sleep
Monitors with condition
variables
● To allow a process to wait within the monitor,
a condition variable must be declared, as:
var x,y: condition
● Condition variable can only be used within the operations
wait and signal. Queue is associated with condition
variable.
• The operation
x.wait;
means that the process invoking this operation is suspended
until another process invokes
x.signal;
• The x.signal operation resumes exactly one suspended
process. If no process is suspended, then the signal
operation has no effect.
Principles of Operating Systems -
Process Synchronization 123
Characteristics of Monitors

Monitor monitorName{ •We can only run one program at a time inside the monitor.
variables_declaration; •Monitors in an operating system are defined as a group of
condition_variables;
methods and fields that are combined with a special type of
procedure p1{ ... }; package in the OS.
procedure p2{ ... }; •A program cannot access the monitor's internal variable if it
...
procedure pn{ ... };
is running outside the monitor. However, a program can call
the monitor's functions.
{ •Monitors were created to make synchronization problems
initializing_code; less complicated.
}
•Monitors provide a high level of synchronization between
} processes.
Monitors

• Advantages of Monitor in OS • Disadvantages of Monitor in OS

• Monitors offer the benefit of • Monitors must
making concurrent or parallel be implemented with the
programming easier and less error- programming language.
prone than semaphore-based • Monitor increases the compiler's
solutions. workload.
• It helps in process synchronization • The monitor requires to understand
in the operating system. what operating system features are
• Monitors have built-in mutual available for controlling
exclusion. crucial sections in the parallel
• Monitors are easier to set up than procedures.
semaphores.
• Monitors may be able to correct for
the timing faults that semaphores
cause.
Monitors vs Semaphores
Dining Philosophers
type dining-philosophers= monitor
var state: array[0..4] of (thinking, hungry, eating);
var self: array[0..4] of condition;
// condition where philosopher I can delay himself when hungry
but // is unable to obtain chopstick(s)
procedure entry pickup (i :0..4);
begin
state[i] := hungry;
test(i); //test that your left and right neighbors are not
eating
if state [i] <> eating then self [i].wait;
end;
procedure entry putdown (i:0..4);
begin
state[i] := thinking;
test (i + 4 mod 5 ); // signal one neighbor
test (i + 1 mod 5 ); // signal other neighbor
end;

Principles of Operating Systems -

Process Synchronization 128
Dining Philosophers (cont.)
procedure test (k :0..4);
begin
if state [k + 4 mod 5] <> eating
and state [k ] = hungry
and state [k + 1 mod 5] <> eating
then
begin
state[k] := eating;
self [k].signal;
end;
end;

begin
for i := 0 to 4
do state[i] := thinking;
end;

Principles of Operating Systems -

Process Synchronization 129