15- Bakery-Algorithm.pptx

Bakery-Algorithm operating system

1. CSC351- Operating System Week-8 Lecture-15 Semester 5 Lahore Garrison University

2. Preamble (Past lesson brief) Process Synchronization Peterson's Solution Algorithm 1 Algorithm 2 Algorithm 3 Lahore Garrison University

3. Agenda Critical Section (Review) Introduction to Bakery Algorithm Bakery Algorithm Notations Bakery Algorithm Data Structure

4. Critical Section (Review) Critical section is a code segment that accesses shared variables and has to be executed an atomic action. Only one process must be executing its critical section at a given time. Do { Entry section Critical section Exit section Remainder-section } While (true)

5. Critical Section Solution (Review) Mutual exclusion : Only one process should execute in its critical section. Progress : If no process is executing in its critical section and some process wish to enter the critical section. Then only those processes that are not executing in its remainder section can participate. Bounded waiting : There is a limit on the number of times that other process are allowed to enter their critical section.

6. Introduction to Bakery Algorithm What is Bakery algorithm? Devised by “Leslie Lamport ” Before entering its critical section, process receives a ticket number. Holder of the smallest ticket number enters the critical section. If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first .

7. Bakery Algorithm The ticket numbering scheme always generates numbers in the increasing order of enumeration; i.e., 1, 2, 3, 4, 5 .. P i P j

8. Bakery Algorithm (Cont.) In the above diagram we can see that there are two processes p1 and p2. T he process p1 & p2 have same ticket number .Then process ID will be checked. P1 process has lowest ID and will go to critical section first (Ticket # 24, p1) (Ticket # 24, p 2 )

9. Bakery Algorithm (Data Structure ) Data Structures boolean choosing[n]; int number[n]; These data structures are initialized to false and 0, respectively When pi is waiting to enter its critical section then number[ i ] will be nonzero.

10. Bakery Algorithm Notations (ticket #, process id #) ( a,b ) < ( c,d ) if a < c or if a == c and b < d max (a ,…, a n-1 ) is a number, k, such that k  a i for i = 0, …, n–1

11. Bakery Algorithm Structure of P i do { choosing[ i ] = true; number[ i ] = max(number[0],number[1],…,number [n – 1]) + 1; choosing[ i ] = false; for (j = 0; j < n; j++) { while (choosing[j]) ; while ( (number[ j ] != 0) && ((number[j], j) < (number[ i ], i )) ) ; } Critical Section number[ i ] = 0; Remainder section } while (1); This loop is going to compare the (no, id) pair of P i with (no, id) pair of all other processes and finally selects which process goes to the CS Before choosing a number, every process will first set its choosing to true and later will set it to false. After leaving the CS, P i set its number to 0, showing that it is now not interested to enter its CS If P j is interested to go to its CS, then check its ordered pair, with ordered pair of P i . If P j ’s (no, id) pair is less than P i ’s pair then P i wait in this loop, else move up to for loop, increment j and check next process. If P j is having a number equal to 0, i.e. P j is not interested to enter its CS. So break this while loop, go back to for loop, increment j and check next process

12. Bakery Algorithm (Example) Process Number P0 3 P1 P2 7 P3 4 P4 8

13. Bakery Algorithm (Example) P0 P1 P2 P3 P4 ( 3,0) < (3,0 ) (3,0) < (0,1) (3,0) < (7,2) (3,0) < (4,3) (3,0) < (8,4) (0,1) < (3,0) (0,1) < (0,1) (0,1) < (7,2) (0,1) < (4,3) (0,1) < (8,4) (7,2) < (3,0) (7,2) < (0,1) (7,2) < (7,2) (7,2) < (4,3) (7,2) < (8,4) (4,3) < (3,0) (4,3) < (0,1) (4,3) < (7,2) (4,3) < (4,3) (4,3) < (8,4) (8,4) < (3,0) (8,4) < (0,1) (8,4) < (7,2) (8,4) < (4,3) (8,4) < (8,4)

14. P0 P1 P2 P3 P4 P0 1 1 1 P1 1 1 1 1 P2 1 P3 1 1 P4 (a, b) < (c, d) If a < c OR If a == c AND b < d P0 P1 P2 P3 P4 ( 3,0) < (3,0 ) (3,0) < (0,1) (3,0) < (7,2) (3,0) < (4,3) (3,0) < (8,4) (0,1) < (3,0) (0,1) < (0,1) (0,1) < (7,2) (0,1) < (4,3) (0,1) < (8,4) (7,2) < (3,0) (7,2) < (0,1) (7,2) < (7,2) (7,2) < (4,3) (7,2) < (8,4) (4,3) < (3,0) (4,3) < (0,1) (4,3) < (7,2) (4,3) < (4,3) (4,3) < (8,4) (8,4) < (3,0) (8,4) < (0,1) (8,4) < (7,2) (8,4) < (4,3) (8,4) < (8,4) Condition True = 1 Condition False = 0

15. P0 P1 P2 P3 P4 P0 1 1 1 P1 1 1 1 1 P2 1 P3 1 1 P4 P0 P2 P3 P4 P0 1 1 1 P2 1 P3 1 1 P4 Check Column Wise, If all entries are zero; The process is complete, Remove this process from both Column and Row. Note: It does not matter If row has all zeros. Row is dependent on Column. P1 is complete ; After removing P1, see that P0 has all entries as zero. Hence, P0 is complete ; After removing P0, see that P3 has all entries as zero. Hence, P3 is complete ; After removing P3, see that P4 has all entries as zero. Hence, P2 is complete . After removing P2, see that P4 is the only process which has zero entry. Hence, P4 is complete . P2 P3 P4 P2 1 P3 1 1 P4 P2 P4 P2 1 P4 P4 P4 All processes have been completed in order.

16. Bakery Algorithm (Example)

17. Bakery Algorithm Process Number P0 3 P1 P2 7 P3 4 P4 8 P0 P2 P3 P4 (3,0) < (3,0) (3,0) < (7,2) (3,0) < (4,3) (3,0) < (8,4) Number[1] = 0 Number[1] = 0 Number[1] = 0 Number[1] = 0 (7,2) < (3,0) (7,2) < (7,2) (7,2) < (4,3) (7,2) < (8,4) (4,3) < (3,0) (4,3) < (7,2) (4,3) < (4,3) (4,3) < (8,4) (8,4) < (3,0) (8,4) < (7,2) (8,4) < (4,3) (8,4) < (8,4) 1 3 2 4

18. Bakery Algorithm P1 not interested to get into its critical section  number[1] is 0 P2, P3, and P4 wait for P0 P0 gets into its CS, get out, and sets its number to 0 P3 get into its CS and P2 and P4 wait for it to get out of its CS P2 gets into its CS and P4 waits for it to get out P4 gets into its CS Sequence of execution of processes: <P0, P3, P2, P4>

19. Bakery Algorithm Meets all three requirements: Mutual Exclusion : (number[j], j) < (number[ i ], i ) cannot be true for both P i and P j Progress : Decision takes complete execution of the ‘for loop’ by one process No process in its ‘Remainder Section’ (with its number set to 0) participates in the decision making Bounded-waiting: At most one entry by each process (n-1 processes) and then a requesting process enters its critical section (First-Come- First-Serve)

20. Synchronization Hardware Test and Set Lock A hardware solution to the synchronization problem There is a shared lock variable which can take either of the two values, 0 and 1 Before entering the critical section, a process inquires about the lock If it is locked, it keeps on waiting till it becomes free If it is not locked, it takes the lock and executes the critical section Lahore Garrison University

21. Summary Critical Section Problem Critical Section Solution Bakery Algorithm Data Structure Bakery Algorithm Example Bakery Algorithm Results

22. Reference To cover this topics , different reference material has been used for consultation. Operating systems concept by Abraham silberchatz edition 9 Tutorialspoint.com Google.com Lahore Garrison University