Mehwashma Amir
Lecturer
Process Synchronization
• In multiprogramming OS we can have more than one process
presenting in Main memory having some shared resource
• Shareable resource can be use in non-shareable mode like printer is
shareable but only one instance can use at a time
Concurrent access to shared data may result in data inconsistency.
Maintaining data consistency requires mechanisms to ensure that
cooperating processes access shared data sequentially.
Cont…Example
• a=10; Case 1: Case 2:
P() { P1 P1 --- > 10 read [Link]
R(a) P1 --- > 11 p2 --- > 11
a=a+1 P2 ---> 12 Control given to P1
w(a) P1 has 10 but P2 makes
} the value of a 11 P1 will
also increment a and
value will be 11 now
that is a problem
Bounded-Buffer Problem
If both the producer and consumer attempt to update the buffer
concurrently, the machine language statements may get interleaved.
Interleaving depends upon how the producer and consumer processes
are scheduled.
Bounded-Buffer Problem
Assume counter is initially 5. One interleaving of
statements is:
producer: MOV R1, counter (R1 = 5)
INC R1 (R1 = 6)
consumer: MOV R2, counter (R2 = 5)
DEC R2 (R2 = 4)
producer: MOV counter, R1 (counter = 6)
consumer: MOV counter, R2 (counter = 4)
The value of count may be either 4 or 6, where the
correct result should be 5.
Process Synchronization
More Examples
Bank transactions
Airline reservation
Bank Transactions
D Balance W
Deposit Withdrawal
MOV A, Balance MOV B, Balance
ADD A, Deposited SUB B, Withdrawn
MOV Balance, A MOV Balance, B
Bank Transactions
Bank Transactions
Current balance = Rs. 50,000
Check deposited = Rs. 10,000
ATM withdrawn = Rs. 5,000
Bank Transactions
Check Deposit:
MOV A, Balance // A = 50,000
ADD A, Deposit ed // A = 60,000
ATM Withdrawal:
MOV B, Balance // B = 50,000
SUB B, Withdrawn // B = 45,000
Check Deposit:
MOV Balance, A // Balance = 60,000
ATM Withdrawal:
MOV Balance, B // Balance = 45,000
Process Synchronization
Race Condition: The situation where several processes
access and manipulate shared data concurrently, the
final value of the data depends on which process
finishes last.
Critical Section: A piece of code in a cooperating
process in which the process may updates shared data
(variable, file, database, etc.).
That area where process access share resource is called
critical section
Solution of the Critical Problem
Software based solutions
Hardware based solutions
Operating system based solution
Structure of Solution
do {
entry section
critical section
exit section
reminder section
} while (1);
Solution to Critical-Section Problem
• 2-Process Critical Section Problem
• N-Process Critical Section Problem
• Conditions for a good solution:
1. Mutual Exclusion: If a process is executing in its critical section, then
no other processes can be executing in their critical sections.
Solution to Critical-Section Problem
2. Progress: If no process is executing in its critical section and
some processes wish to enter their critical sections, then only
those processes that are not executing in their remainder
sections can decide which process will enter its critical section
next, and this decision cannot be postponed indefinitely.
only those process should compete or should be in the race to
enter in the CS those who actually wants to
3. 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.
Case 1: M.E Meets .Progress Not
• P0 P1
While(1) While(1)
{ {
While(turn!=0); While(turn!=1) ;
C.S C.S
Turn=1; Turn=0;
R.S R.S
}
}
Case 2:
M.E Meets .Progress meets but issue
• P0 P1
While(1)
While(1)
{
{ Flag[1]=T
Flag[0]=T While(flag[0]);
While(flag[1]); C.S
C.S Flag[1]=F;
Flag[0]=F; R.S
R.S }
}
Petersen Solution:
M.E Meets .Progress meets Petersen
P0 P1
While(1) While(1)
{ {
Flag[0]=T Flag[1]=T
Turn=1 Turn=0
While(turn==1 && flag[1]); While(turn==0 && flag[0]);
C.S C.S
Flag[0]=F; Flag[1]=F;
R.S R.S
} }
Semaphores
Semaphores
• Synchronization tool
• Available in operating systems
• Semaphore S – integer variable that can only be
accessed via two indivisible (atomic) operations,
called wait and signal
• Semaphore can be used to solve
• Critical Section problem
• Resource management
• Deciding Order of execution
Semaphores
wait(S){
while S 0
; //no-op
S--;
}
signal(S){
S++;
}
n-Processes CS Problem
• Shared data:
semaphore mutex = 1;
• Structure of Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);
Is it a Good Solution?
•Mutual Exclusion: Yes
•Progress: Yes
•Bounded Waiting: No
Process Synchronization
Execute statement B in Pj only
after statement A has been
executed in Pi
Use semaphore S initialized to 0
Pi Pj
A wait(S)
signal(S) B
Process Synchronization
Give a semaphore based solution
for the following problem:
Statement S1 in P1 executes only
after statement S2 in P2 has
executed, and statement S2 in P2
should execute only after
statement S3 in P3 has executed.
Process Synchronization
P1 P2 P3
S1 S2 S3
Solution
Semaphore A=0, B=0;
P1 P2 P3
wait(A) wait(B) S3
S1 S2 signal(B)
signal(A)
Classical Problems of
Synchronization
Bounded-Buffer Problem
Readers and Writers Problem
Dining Philosophers Problem
Bounded Buffer Problem
Empty Pool
Producer Consumer
Full Pool
Bounded-Buffer Problem
Shared data
semaphore full, empty, mutex;
Initialization
full = 0, empty = n, mutex = 1;
Producer Process
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
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);
Readers and Writers Problem
Readers Writers
Readers and Writers Problem
Reader
Reader
Reader
Reader Writer
Reader Writer
Writer
Reader
Reader Writer
Reader Writer
Writer
Reader Writer
Writer
Shared Resource
Readers and Writers Problem
Writer
Writer
Writer
Writer
Writer
Writer
Writer
Writer
Reader
Reader
Reader
Reader
Reader
Reader
Reader
Reader
Reader
Shared Resource
Readers and Writers Problem
Reader
Reader
Reader
Reader Writer
Reader Writer
Writer
Reader
Reader Writer
Reader Writer
Writer
Reader Writer
Writer
Shared Resource
First Readers and Writers
Problem
No reader will be kept
waiting unless a writer
has already obtained
permission to use the
shared object.
Second Readers and Writers
Problem
If a writer is ready, it
waits for the minimum
amount of time.
First Readers and Writers Problem
Shared data
semaphore mutex, wrt;
Initialization
mutex = 1, wrt = 1;
readcount = 0;
Writer Process
wait(wrt);
…
writing is performed
…
signal(wrt);
Reader Process
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
Reader-Writer Problem
• For Reader
Wait(mutex)
Reader++
If(readcount==1)
Wait(wrt)
Signal(mutex)
Read operation
Wait(mutex)
Readcount—
If(readcount==0)
Signal(wrt)
Signal(mutex)