Formula Sheets: Process Synchronization | Operating System - Computer Science Engineering (CSE) PDF Download

 Page 1


Pro cess Sync hronization F orm ula Sheet
Critical Section Problem
• Requiremen ts : Mutual Exclusion, Progress, Bounded W aiting.
• Bounded W aiting Time : T
w ait
= (N-1)·T
critical
, where N is n um b er of pro cesses, T
critical
is
critical section execution time.
Semaphores
• Binary Semaphore : S?{0,1} , for m utual exclusion.
• Coun ting Semaphore : S= 0 , for resource coun ting.
• Op erations :
– W ait(S ): S = S-1 , blo c k if S < 0 .
– Signal(S ): S = S +1 , un blo c k a w aiting pro cess.
• W aiting Time : T
w ait
= T
queue
+T
acquire
, where T
queue
is time in blo c k ed queue.
• Queue Length : L = ?·T
a vg-w ait
, where ? is pro cess arriv al rate (Little’s La w).
Mutex vs. Semaphore
• Mutex : Binary semaphore with o wnership, S?{0,1} , only o wner can signal.
• Semaphore : General sync hronization, coun ting or binary .
• Lo c k A cquire Time : T
m utex
˜ T
semaphore
, but m utex enforces o wnership.
Monitors
• Definition : Ensures m utual exclusion with a lo c k p er monitor.
• Condition V ariables :
– W ait(): Susp ends pro cess, releases monitor lo c k.
– Signal(): Resumes one w aiting pro cess.
– T
cond-w ait
˜ T
signal
+T
resc hedule
.
• Monitor Ov erhead : T
monitor
= T
lo c k-acquire
+T
critical
+T
lo c k-release
.
In ter-Pro cess Comm unication (IPC)
• Shared Memory : T
comm
˜ T
memory-access
, fast but requires sync hronization.
• Message P assing : T
IPC
= T
queue
+T
transfer
, where T
transfer
is message send/receiv e time.
• Message Queue Size : Q
size
= N
max-messages
, limited b y system buffer.
• Pip e Throughput : S =
L
data
T
transfer
+T sync
, where L
data
is data siz e.
Hardw are Sync hronization
• T est-and-Set (T AS) : A tomic, sets lo c k to 1, returns old v alue.
• Compare-and-Sw ap (CAS) : A tomic, up dates if v alue matc hes exp ected.
• Spinlo c k Ov erhead : T
spin
= N
con ten tion
·T
cycle
, where N
con ten tion
is n um b er of con tending pro-
cesses, T
cycle
is CPU cycle time.
• Sw ap : A tomic exc hange of t w o v ariables, T
sw ap
˜ T
T AS
.
1
Page 2


Pro cess Sync hronization F orm ula Sheet
Critical Section Problem
• Requiremen ts : Mutual Exclusion, Progress, Bounded W aiting.
• Bounded W aiting Time : T
w ait
= (N-1)·T
critical
, where N is n um b er of pro cesses, T
critical
is
critical section execution time.
Semaphores
• Binary Semaphore : S?{0,1} , for m utual exclusion.
• Coun ting Semaphore : S= 0 , for resource coun ting.
• Op erations :
– W ait(S ): S = S-1 , blo c k if S < 0 .
– Signal(S ): S = S +1 , un blo c k a w aiting pro cess.
• W aiting Time : T
w ait
= T
queue
+T
acquire
, where T
queue
is time in blo c k ed queue.
• Queue Length : L = ?·T
a vg-w ait
, where ? is pro cess arriv al rate (Little’s La w).
Mutex vs. Semaphore
• Mutex : Binary semaphore with o wnership, S?{0,1} , only o wner can signal.
• Semaphore : General sync hronization, coun ting or binary .
• Lo c k A cquire Time : T
m utex
˜ T
semaphore
, but m utex enforces o wnership.
Monitors
• Definition : Ensures m utual exclusion with a lo c k p er monitor.
• Condition V ariables :
– W ait(): Susp ends pro cess, releases monitor lo c k.
– Signal(): Resumes one w aiting pro cess.
– T
cond-w ait
˜ T
signal
+T
resc hedule
.
• Monitor Ov erhead : T
monitor
= T
lo c k-acquire
+T
critical
+T
lo c k-release
.
In ter-Pro cess Comm unication (IPC)
• Shared Memory : T
comm
˜ T
memory-access
, fast but requires sync hronization.
• Message P assing : T
IPC
= T
queue
+T
transfer
, where T
transfer
is message send/receiv e time.
• Message Queue Size : Q
size
= N
max-messages
, limited b y system buffer.
• Pip e Throughput : S =
L
data
T
transfer
+T sync
, where L
data
is data siz e.
Hardw are Sync hronization
• T est-and-Set (T AS) : A tomic, sets lo c k to 1, returns old v alue.
• Compare-and-Sw ap (CAS) : A tomic, up dates if v alue matc hes exp ected.
• Spinlo c k Ov erhead : T
spin
= N
con ten tion
·T
cycle
, where N
con ten tion
is n um b er of con tending pro-
cesses, T
cycle
is CPU cycle time.
• Sw ap : A tomic exc hange of t w o v ariables, T
sw ap
˜ T
T AS
.
1
Soft w are Sync hronization Algorithms
• P eterson’s Algorithm (T w o Pro cesses) :
– V ariables: turn?{0,1} , interested[0],interested[1]?{ true, false} .
– En try Condition: Pro cess i w aits if interested[j] = true and turn = j , where j?= i .
– Bounded W aiting: T
w ait
= T
criticalj
.
• Dekk er’s Algorithm : Extends P eterson’s for t w o pro cesses, ensures m utual exclusion.
• Lamp ort’s Bak ery Algorithm :
– Tic k et Num b er: ticket[i] = max(ticket[0..N-1])+1 .
– W aiting Time: T
w ait
= (N-1)·T
critical
, where N is n um b er of pro cesses.
Classic Sync hronization Problems
• Pro ducer-Consumer Problem :
– Buffer Size: N (items).
– Semaphores: mutex?{0,1} , full , empty , with full+empty = N .
• Readers-W riters Problem :
– Semaphores: mutex (for rc ), wrt (for writer exclusion).
– Reader Coun t: rc , up dated atomically .
– Starv ation A v oidance: P
writer
>P
reader
or use fairness queue.
• Dining Philosophers Problem :
– Semaphores: S
i
?{0,1} p er c hopstic k, N philosophers.
– Deadlo c k Prev en tion: Limit to N-1 eating philosophers or resource ordering.
• Sleeping Barb er Problem :
– Semaphores: customers , barber , mutex .
– W aiting Ro om Size: N
c hairs
, customers= N
c hairs
.
Deadlo c k, Starv ation, and Liv elo c k
• Deadlo c k Conditions : Mutual Exclusion, Hold-and-W ait, No Preemption, Circular W ait.
• Bank er’s Algorithm (Deadlo c k A v oidance) :
– Safe State: A v ailable= Need
i
for some pro cess i .
– Time Complexit y: O(m·n
2
) , where m is resource t yp es, n is pro cesses.
• Starv ation Probabilit y : P
starv ation
?
1
Pi
, where P
i
is pro cess priorit y .
• Liv elo c k : Pro cesses con tin uously c hange states without progress, T
liv elo c k
?8 .
P erformance Metrics
• Sync hronization Ov erhead : T
sync
= T
lo c k-acquire
+T
lo c k-release
+T
w ait
.
• Con ten tion Probabilit y : P
con ten t ion
?
N
R
, where N is n um b er of pro cesses, R is n um b er of
resources.
• Throughput : S =
N
tasks
T
total
+T sync
, where N
tasks
is completed tasks.
2