Jawaharlal Nehru Technological University Hyderabad B.Tech III CONCURRENT PROGRAMMING Previous Question Paper (August - 2022 - R18)

Lamport’s Bakery Algorithm is a software-based solution for the mutual exclusion problem among n processes. It mimics the process of taking a ticket at a bakery, where each process is assigned a number, and the process with the lowest number enters the critical section first.

The algorithm uses two shared arrays: choosing (a boolean array) and number (an integer array). When a process i wants to enter the critical section, it performs the following steps:

1. It sets choosing[i] to true and finds the maximum value in the number array, then sets its own number[i] to max(number[0], ..., number[n-1]) + 1.
2. It sets choosing[i] to false.
3. For every other process j, it waits until choosing[j] is false and then checks if number[j] is zero or if the pair (number[j], j) is lexicographically greater than (number[i], i).

If two processes pick the same number, the process with the smaller PID (index) is given priority, ensuring no two processes enter the critical section simultaneously while preventing starvation.

Mutual Exclusion is a property of concurrency control that ensures that if one process is executing in its critical section, no other process is allowed to execute in its critical section. This prevents race conditions and data inconsistency.

Critical Section is the segment of code within a process where the process accesses shared resources, such as variables, files, or hardware devices, that must not be accessed by more than one process at a time.

For example, in a banking application, the code block that updates a shared account balance is a critical section. If two processes attempt to update the balance simultaneously without mutual exclusion, a 'lost update' problem occurs where one transaction overwrites the other. By enforcing mutual exclusion, the system ensures that the read-modify-write cycle for the balance is performed atomically by only one process at a time.