Presentation on Bakery Algorithm
Download as PPTX, PDF0 likes140 views
The document presents information about the Bakery algorithm, which is a mutual exclusion algorithm designed by Leslie Lamport to prevent concurrent threads from entering critical sections of code at the same time. It works by having each process receive a number before entering the critical section, and the process with the lowest number gains access first. If two processes have the same number, the process with the lower ID will enter first. Real-life examples are provided to illustrate how the algorithm handles processes with the same ticket number or different ticket numbers. The conclusion states that the Bakery algorithm assumes sequential consistency and requires special handling to work on modern hardware.
More Related Content
What's hot (20)
Similar to Presentation on Bakery Algorithm (20)
Recently uploaded (20)
Presentation on Bakery Algorithm
- 3. What is Bakery algorithm ? Bakery algorithm is an algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion. In computer science, it is common for multiple threads to simultaneously access the same resources. But data corruption can occur if two or more threads try to write into the same memory location. Lamport's bakery algorithm is one of many mutual exclusion algorithms designed to prevent concurrent threads entering critical sections of code concurrently to eliminate the risk of data corruption.
- 4. How it works ? Before entering its critical section, the process receives a number. The smallest number enters the critical section. If processes Pi and Pj receive the same number, if Pi < Pj Pi is served first; else Pj is served first.
- 5. Real life examples P1 P2 In the above diagram there are two processes p1 and p2. the process p2 will go to the critical section because it has lowest ticket number. Token 9 Token 8
- 6. Real life examples P1 P2 Here, we can see that there are two processes p1 and p2. The process p1 & p2 have same token number. Then process ID will be checked. P1 process has lowest ID and will go to critical section first. Token 9 Token 9
- 7. Conclusion This algorithm model can be used to implement mutual exclusion on memory that lacks synchronization primitives. It is remarkable that this algorithm is not built on top of some lower level "atomic" operation. Lamport's bakery algorithm assumes a sequential consistency memory model. Few, if any, languages or multi-core processors implement such a memory model. Therefore correct implementation of the algorithm typically requires inserting fences to inhibit reordering.
- 8. Thank You!
- 9. 3.CRITICAL SECTION : Critical section is a code segment that accesses shared variables and has to be executed an atomic action. Only one process can execute its critical section at a given time. A mutual exclusion is a program object that prevents simultaneous access to a shared resource. This concept is used in concurrent programming with a critical section, a piece of code in which processes or threads access a shared resource. 4. The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of N process. Bakery Algorithm is a critical section solution for N processes. The algorithm preserves the first come first serve property. 12. Bakery Algorithm (ID 9, p1) (ID 8, p2) in the above diagram we can see that there are two processes p1 and p2. the process p2 will go to the critical section because it has lowest ticket number. 13. Bakery Algorithm (ID 8, p1) (ID 8, p2) In the above diagram we can see that there are two processes p1 and p2.the 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