Amirkabir University of
Technology
(Tehran Polytechnic)
Department of Computer Engineering and Information
Technology
Process Synchronization
Hamid R. Zarandi
h_zarandi@aut.ac.ir
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28
Operating Systems
Motivation
Cooperating process/thread:
o the one that can affect or be affected by other processes executing in system.
o Processes, threads
Processes can execute concurrently
o May be interrupted at any time, partially completing execution
Problem: Data inconsistency
o It may occur in the case of concurrent access to shared data
How to solve?
o Orderly execution of cooperating processes that share a logical address space
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 2
Operating Systems
One example!
o A solution to consumer-producer problem that fills all the buffers.
We can have an integer counter that keeps track of the number of full buffers.
Initially, counter is set to 0.
It is incremented by the producer after it produces a new buffer
It is decremented by the consumer after it consumes a buffer.
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 3
Operating Systems
Circular buffer & producer-consumer problem
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Producer Consumer
item next_produced; item next_consumed;
while (true) { while (true) {
/* produce an item in next produced */ while (counter == 0)
while (counter == BUFFER_SIZE)) ;/* do nothing */
; /* do nothing */
next_consumed = buffer[out];
buffer[in] = next_produced; out = (out + 1) % BUFFER_SIZE;
counter --;
in = (in + 1) % BUFFER_SIZE;
/* consume the item in next consumed */
counter ++;
} }
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 4
Operating Systems
Race condition
counter++ could be implemented as
register1 = counter MOV AX, [100]
register1 = register1 + 1 ADD AX, 1
counter = register1 MOV [100], AX
counter-- could be implemented as
register2 = counter MOV BX, [100]
register2 = register2 – 1 ADD BX, 1
counter = register2 MOV [100], BX
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 5
Operating Systems
Another Race condition
Invoking echo() procedure:
Same problem exists on:
o Multiprogramming environment
o Multiprocessing environment
o Distributed processing environment
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 6
Operating Systems
Other examples?
Have you ever seen other examples?
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 7
Operating Systems
Definition
Race condition
o Several process access and manipulate the same data concurrently
o Outcomes of the execution depends on the order in which the access take
place
How to remove Race Condition?
o Serial execution
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 8
Operating Systems
Critical Section Problem
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2015/10/10 9
Operating Systems
Critical section problem
Consider system of n processes {p0, p1, … pn-1}
Each process has critical section segment of code
o Process may be changing common variables, updating table, writing file, etc
o When one process in critical section, no other may be in its critical section
Critical section problem is to design protocol to solve this
Each process must ask permission to enter critical section in entry section, may
follow critical section with exit section, then remainder section
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 10
Operating Systems
Critical section
General structure of process Pi
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 11
Operating Systems
Requirements to solutions
Mutual exclusion
o If process Pi is executing in its critical section, then no other processes can be executing in
their critical sections
Progress
o 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
Bounded waiting
o 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
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 12
Operating Systems
Preemption definition
Preemption
o The act of temporarily interrupting a task being carried out by a
computer system, without requiring its cooperation, and with the intention
of resuming the task at a later time [wiki]
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 13
Operating Systems
Handling critical-section by OS
Two approaches, depend on type of OS kernels
o Preemptive
Allows preemption of process when running in kernel mode
Difficult to design in SMP architectures (why?)
o Non-preemptive
Runs until exits kernel mode, blocks, or voluntarily yields CPU
Essentially free of race conditions in kernel mode (why?)
Which one
ois responsive?
ois suitable for real-time programming?
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 14
Operating Systems
1) Peterson’s solution
A classis SW solution
No guarantees in correct working of the method
o Correctness depends on computer architecture
o Atomic instructions are needed (which & where?)
Good algorithm!
Shared variables
o int turn; /* whose turn is */
o Boolean flag[2] /* who enters the critical-section */
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 15
Operating Systems
Peterson algorithm for Pi
(Pi, Pj)=(P0, P1)
do {
How requirements are satisfied?
flag[i] = true;
Mutual exclusion (?)
turn = j;
Progress (?)
while (flag[j] && turn = = j); Bounded waiting (?)
critical section
flag[i] = false;
remainder section
} while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 16
Operating Systems
2) Hardware solution
Some hardwares support implementing the critical section code!
All solutions are based on idea of locking
o Protecting critical regions via locks
Uniprocessors – could disable interrupts
o Currently running code would execute without preemption
o Generally too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
Multiprocessors – provide special atomic hardware instructions
Atomic = non-interruptible
o Either
test memory word and set value
swap contents of two memory words
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 17
Operating Systems
Hardware solution for critical section
do {
acquire lock How requirements are satisfied?
critical section Mutual exclusion (?)
release lock Progress (?)
remainder section Bounded waiting (?)
} while (TRUE);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 18
Operating Systems
test_and_set instruction
Definition:
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv; /* old value */
}
1. Executed atomically
2. Returns the original value of passed parameter
3. Set the new value of passed parameter to “TRUE”.
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 19
Operating Systems
Hardware solution using test_and_set()
Shared Boolean variable lock, initialized to FALSE
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 20
Operating Systems
compare_and_swap instruction
Definition:
int compare _and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp; /* old value */
}
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.
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 21
Operating Systems
Hardware solution using compare_and_swap()
Shared integer “lock” initialized to 0;
do {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
How requirements are satisfied?
lock = 0; Mutual exclusion (?)
Progress (?)
/* remainder section */ Bounded waiting (?)
} while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 22
Operating Systems
Bounded-waiting mutual exclusion with test_and_set
do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test_and_set(&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 */
} while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 23
Operating Systems
3) OS solution!: 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 (mutual exclusions)
Protect a critical section by first acquire() a lock then release() the lock
o Boolean variable indicating if lock is available or not
Calls to acquire() and release() must be atomic
o Usually implemented via hardware atomic instructions
But this solution requires busy waiting
o This lock therefore called a spinlock
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 24
Operating Systems
acquire() and release()
acquire() {
while (!available) do {
; /* busy wait */ acquire lock
critical section
available = false;; release lock
} remainder section
} while (true);
release() {
available = true;
} How requirements are satisfied?
Mutual exclusion (?)
Progress (?)
Bounded waiting (?)
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 25
Operating Systems
What is the main problem of all mentioned methods?
Busy waiting!
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2015/10/10 26
Operating Systems
4) Semaphore
Synchronization tool that provides more sophisticated ways (than Mutex locks)
for process to synchronize their activities
Semaphore S – integer variable
Can only be accessed via two indivisible (atomic) operations
wait()and signal()
wait(S) signal(S)
{ {
while (S <= 0) S++;
; // busy wait }
S--;
}
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 27
Operating Systems
No busy waiting in Semaphore
Have a FIFO queue for waiting process
typedef struct{
int value;
struct process *list;
} semaphore;
wait(semaphore *S) { signal(semaphore *S) {
S->value--; S->value++;
if (S->value < 0) { if (S->value <= 0) {
add this process to S->list; remove a process P from S->list;
block(); wakeup(P);
} }
} }
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 28
Operating Systems
Accessing shared data by Semaphore
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 29
Operating Systems
Types of semaphore
Types
o Binary semaphore (same as mutex lock)
o Counting semaphore (suitable for managing number of resources)
Can solve various synchronization problems
Example:
o Consider P1 and P2 that require S1 to happen before S2
Create a semaphore “synch” initialized to zero
P1: P2:
S1; wait(synch);
signal(synch); S2;
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 30
Operating Systems
Semaphore points
Must guarantee that no two processes can execute the wait()and signal()on the same
semaphore at the same time (why?)
o wait() and signal() must be atomic!
o wait() and signal() generate a Critical Section Problem!
o How to solve?
Uniprocessors
Disabling interrupts
SMP (Multiprocessors)
Disabling interrupts (bad performance effect)
Other methods: compare_and_swap() and spinlock (is it good to have busy waiting?)
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 31
Operating Systems
Two implementations of semaphores
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 32
Operating Systems
Problems with semaphores
Be careful in the usage
o Deadlock, Starvation, Priority inversion
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
Starvation signal(S);
signal(Q);
signal(Q);
signal(S);
o LIFO queue
Priority Inversion – Scheduling problem when lower-priority process holds
a lock needed by higher-priority process
o Example: L (R) < M < H (R)
Solved via priority-inheritance protocol
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 33
Operating Systems
Classic synchronization problems
The bounded-buffer problem
The readers-writers problem
The dining-philosophers problem
How can semaphore solve these problems?
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 34
Operating Systems
The bounded-buffer problem
int n;
semaphore mutext = 1;
semaphore empty = n;
Producer semaphore full = 0; Consumer
do { do {
... wait(full);
/* produce an item in next_produced */ wait(mutex);
... ...
wait(empty); /* remove an item from buffer to next_consumed */
wait(mutex); ...
...
signal(mutex);
/* add next produced to the buffer */ signal(empty);
... ...
signal(mutex); /* consume the item in next consumed */
signal(full); ...
} while (true); } while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 35
Operating Systems
The readers-writers problem
semaphore rw_mutex = 1;
semaphore mutex = n;
int read_count = 0;
Readers
Writers do {
wait(mutex);
do { read_count++;
wait(rw_mutex); if (read_count == 1)
wait(rw_mutex);
... signal(mutex);
...
/* writing is performed */
/* reading is performed */
...
...
signal(rw_mutex);
wait(mutex);
read count--;
if (read_count == 0)
} while (true); signal(rw_mutex);
signal(mutex);
} while (true);
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 36
Operating Systems
The dining-philosophers problem
Thinking and eating alternatively
semaphore chopstick[5];
do {
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );
// eat
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (TRUE);
Any problem?
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 37
Operating Systems
Other problems with semaphore
Problems with bad usage
Deadlock and starvation are possible.
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 38
Operating Systems
5) Monitor
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
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
procedure Pn (…) {……}
Initialization_Code (…) { … }
}
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 39
Operating Systems
Monitor (with condition variables)
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 40
Operating Systems
Structure of a Monitor
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 41
Operating Systems
The dining-philosophers problem
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) { void test (int i) {
state[i] = HUNGRY; if ((state[(i + 4) % 5] != EATING) &&
test(i); (state[i] == HUNGRY) &&
if (state[i] != EATING) (state[(i + 1) % 5] != EATING) ) {
self[i].wait(); state[i] = EATING;
} self[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;
} }
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 42
Operating Systems
The dining-philosophers problem
DiningPhilosophers.pickup(i);
EAT
DiningPhilosophers.putdown(i);
Any problem?
No deadlock
Starvation is possible
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 43
Operating Systems
Solving bounded-buffer using a Monitor
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 44
Operating Systems
Points to monitor
Monitors can be implemented by semaphores (See the textbook).
OSes support
o Monitor, semaphore, spinlock, mutex
o Examples
Solaris
Windows
Linux
Pthreads
void update(int value)
Alternative approaches {
o Transactional Memory #pragma omp critical
o OpenMP {
o Functional Programming Languages count += value
}
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) } 2018/10/28 45
Operating Systems
Questions?
Hamid R. Zarandi Amirkabir Univ. of Tech. (Tehran Polytechnic) 2018/10/28 46
