Page 120 - DCAP103_Principle of operating system

Unit 4: Process Management-III

ag[i] := false; Notes
remainder section
until false;

Does not satisfy the mutual exclusion requirement.
Algorithm 3

Combined shared variables of algorithms 1 and 2.
Process Pi
repeat

ag[i] := true;
turn := j;

while (ag[j] and turn=j) do no-op;
critical section
ag[i] := false;
remainder section

until false;
Meets all three requirements; solves the critical-section
problem for two processes.

Bakery Algorithm
Critical section for n processes Before entering its critical section, process receives a number.
Holder of the smallest number enters the critical section.
If processes Pi and Pj receive the same number, if i < j, then

Pi is served rst; else Pj is served rst. The numbering scheme always generates numbers in
increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5...
Notation < lexicographical order (ticket #, process id #)
– (a,b) < (c,d) if a < c or if a = c and b < d
– max(a0, . . . , an1) is a number, k, such that k ai
for i = 0,

n 1 , . . .
Shared data
var choosing: array [0..n1] of boolean;
number: array [0..n1] of integer;
Data structures are initialized to false and 0, respectively
Bakery Algorithm (Cont.)

repeat
choosing[i] := true;

number[i] := max(number[0], number[1], ..., number[n 1])+1;

LOVELY PROFESSIONAL UNIVERSITY 113