| Lamport's Bakery Algorithm |
Website Links For Bakery |
Information AboutLamport's Bakery Algorithm |
|
Nature of the problem In Computer Science , it is common for multiple threads to simultaneously access the same resources. They either try to write into the same Memory location, or one thread reads a location before another has finished writing into it. This is undesirable as it can end in hazardous loss of data. ''Lamport's bakery algorithm'' is one of many Mutual Exclusion algorithms. ALGORITHM Analogy Lamport envisaged a Bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When done shopping, the customer loses their number and can then do whatever they want, except for shopping without getting a new number. In the computer world, the 'customers' will be threads, identified by the letter ''i'', obtained from a global variable. Due to the limitations of computer architecture, some parts of the Lamport's Analogy need slight modification. It is possible that more than one thread will get the same number when they request it; this cannot be avoided. Therefore, it is assumed that the thread identifier ''i'' is also a priority identifier. A lower value of ''i'' means a higher priority and threads with higher priority will enter the Critical Section first. Critical section The critical section is that part of code that requires exclusive access to resources and may only be executed by one thread at a time. In the bakery analogy, it is when the customer trades with the baker and others must wait. When a thread wants to enter the critical section, it has to check whether it is its turn to do so. It should check the numbers of every other thread to make sure that it has the smallest one. In case another thread has the same number, the thread with the smallest ''i'' will enter the critical section first. In Pseudocode this comparison will be written in the form: (a, b) < (c, d) which is equivalent to: (a < c) or ((a == c) and (b < d)) Once the thread ends its critical job, it gets rid of its number and enters the non-critical section. Non-critical section The non-critical section is the part of code that doesn't need exclusive access. It represents some thread-specific computation that doesn't interfere with other threads' resources and execution. This part is analogous to actions that occur after shopping, such as putting change back in the wallet. IMPLEMENTATION OF THE ALGORITHM Pseudocode // ''declaration and initial values of global variables'' Enter, Number: array {Link without Title} '''of''' '''integer''' = {0}; 1 Thread(i) { 2 while (true) { 3 Enter {Link without Title} = 1; 4 Number = 1 + max(Number[1 , ..., Number[N]); 5 Enter {Link without Title} = 0; 6 for (j = 1; j <= N; j++) { 7 while (Enter {Link without Title} != 0) { 8 // ''wait until thread j receives its number'' 9 } 10 while ((Number != 0) && ((Number[j , j) < (Number[i], i))) { 11 // ''wait until threads with smaller numbers or with the same'' 12 // ''number, but with higher priority, finish their work'' 13 } 14 } 15 // ''critical section...'' 16 Number {Link without Title} = 0; 17 // ''non-critical section...'' 18 } 19 } Note: The thread also checks itself before entering the critical section, but that doesn't cause any delays since every condition will be evaluated as ''false''. Discussion Each thread only writes its own storage, only reads are shared. Remarkable is that this algorithm is not built on top of some lower level 'atomic' operation, e.g. Compare-and-swap . The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. The read operation can return an arbitrary number. Therefore this algorithm can be used to implement mutual exclusion on 'memory' that lacks synchronisation primitives, e.g. a simple shared SCSI disk between two computers. The necessity of variable ''Enter'' might not be obvious as there is no 'lock' around lines 7 to 13. See UCDAVIS: Bakery Algorithm for an in depth discussion. SEE ALSO
REFERENCES
|
|
|