Page 119 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
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. Assume that each process executes at a nonzero
speed. No assumption concerning relative speed of the n processes.
Initial Attempts to Solve Problem
Only 2 processes, P0 and P1

General structure of process Pi (other process Pj)
repeat
entry section
critical section
exit section
remainder section
until false;
Processes may share some common variables to synchronize their actions.

Algorithm 1
Shared variables:
– var turn: (0..1);
initially turn = 0
– turn = i) Pi can enter its critical section
Process Pi
repeat
while turn =6 i do no-op;
critical section
turn := j;
remainder section

until false;
Satises mutual exclusion, but not progress.
Algorithm 2
Shared variables

– var ag: array [0..1] of boolean;
initially ag[0] = ag[1] = false.
– ag[i] = true ) Pi ready to enter its critical section
Process Pi
repeat
ag[i] := true;
while ag[j] do no-op;
critical section

112 LOVELY PROFESSIONAL UNIVERSITY