CENG328- OPERATING
SYSTEMS
PROCESS SYNCHRONIZATION
Outline
● The Critical Section Problem
● Synchronization Hardware
● Semaphores
● Classical Problems of Synchronization
● Critical Regions
● Monitors
Producer-Consumer Problem
[Link] Producer process must not produce an
item if the shared buffer is full.
[Link] Consumer process must not consume an
item if the shared buffer is empty.
[Link] 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
[Link];
means that the process invoking this operation is suspended
until another process invokes
[Link];
• The [Link] 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