What is the Lamport’s bakery algorithm?

The Lamport’s bakery algorithm, devised by Leslie Lamport in 1974, provides a means to ensure that multiple threads or processes can access shared resources without conflicting with each other. It’s like when customers visit a bakery, receive a number, and are served based on that number.

The algorithm aims to solve the mutual exclusion problem, wherein several processes wish to access a shared resource. It ensures that they don’t do so simultaneously, which can lead to issues like data corruption.

Key concepts

Mutual exclusion: One process enters its critical section at a time.
Bounded waiting: A limit exists to how long a process will wait after requesting entry.
Freedom from deadlock: Processes won’t be left waiting endlessly.

The problem

When several processes run concurrently and want to use a shared resource (like a printer, CPU, or any other utility), they might conflict or interfere with each other. We need a way to ensure that only one process can use the resource at any given time, and others must wait for their turn.

Concepts used in the algorithm

1. Taking a number

Just like in a bakery, every process that wants to access the shared resource takes a number. The process with the smallest number gets to use the resource.

2. Number assignment

Processes decide their number based on the maximum number already chosen and add one to it. If a process sees that no other process has a number, it takes the number one.

3. Waiting

If a process sees that another process with a lower number (or an earlier position in the queue) is also interested in the shared resource, it waits.

How the algorithm works:

Entering the critical section:
1. When a process wants to enter its critical section, it first looks at all other processes to see what numbers they have.
2. It then chooses a number that is one more than the maximum number it has seen.
3. If two processes pick the same number at the same time, the process with the lower process ID gets priority.
Exiting the critical section:
1. After completing its task in the critical section, the process sets its number to zero, indicating that it no longer wishes to access the shared resource.
Dealing with starvationIt refers to a situation where a process or resource in the system is unable to make progress or obtain the necessary resources to complete its task, despite being eligible and waiting for a long time. This phenomenon occurs when certain processes or resources are consistently prioritized over others, leading to a lack of fairness in resource allocation.:
1. The bakery algorithm ensures that every process gets a fair chance (or turns) to access the resource. It guarantees that if a process wants to access the shared resource, it will eventually get its turn.

Example

Imagine three processes: A, B, and C.

A decides it wants to access the shared resource. It looks around and sees no other process has a number.
It takes the number one.
B also wants to access the resource. It sees A has number one, so it takes number two.
C comes in and takes number three after seeing A and B's numbers.
A has the smallest number, so it accesses the resource first. B and C wait.
A finishes and sets its number to zero. B, having the next smallest number, accesses the resource.
C goes next after B finishes and sets its number to zero.

import threading
import time
# Number of processes
N = 5
# Flag to indicate if a process is in the entry section
entering = [False] * N
# Number for each process
number = [0] * N
def max_number():
    return max(number)
def bakery_algorithm(process_id):
    global entering, number
    # Entry Section
    entering[process_id] = True
    number[process_id] = 1 + max_number()
    entering[process_id] = False
    for i in range(N):
        if i != process_id:
            # Wait until process 'i' receives its number
            while entering[i]:
                pass
            # Wait until all processes with smaller numbers or with the same
            # number, but with higher process IDs, finish their work
            while (number[i] != 0) and (number[process_id], process_id) > (number[i], i):
                pass
    # Critical Section
    print(f"Process {process_id} is in the critical section.")
    time.sleep(1)  # Simulating some work in the critical section
    # Exit Section
    number[process_id] = 0
# Creating and starting threads for each process
threads = []
for i in range(N):
    thread = threading.Thread(target=bakery_algorithm, args=(i,))
    threads.append(thread)
    thread.start()
# Waiting for all threads to complete
for thread in threads:
    thread.join()
print("All processes have completed their execution.")

Code explanation

Line 1: import threading: Imports the threading module, allowing the program to run multiple threads concurrently.
Line 2: import time: Imports the time module, which provides various time-related functions.
Line 4: N = 5: Defines a constant N representing the number of processes. In this case, there are five processes.
Line 6: entering = [False] * N: Initializes a list named entering with N elements, all set to False. This list is used to indicate if a process is in the entry section.
Line 8: number = [0] * N: Initializes another list named number with N elements, all set to 0. This list will store the ticket numbers for each process.
Line 12: def max_number():: Defines a function named max_number(), which returns the maximum ticket number currently in use.
Line 16: def bakery_algorithm(process_id):: Defines the main function, bakery_algorithm(), which will be executed by each process. It takes a parameter process_id to identify each process.
Line 18: global entering, number: Indicates that the function will use the global variables entering and number.
Lines 21–25: entering[process_id] = True: Marks the entry section for the current process by setting entering[process_id] to True.
Lines 26–27: number[process_id] = 1 + max_number(): Assigns a ticket number to the current process, which is one greater than the current maximum number.
Lines 28–29: entering[process_id] = False: Marks the end of the entry section for the current process by setting entering[process_id] back to False.
Lines 31–49: Loop iterates over all processes.
Lines 33–35: while entering[i]:: Waits until process "i" receives its number by checking if entering[i] is True.
Lines 38–41: while (number[i] != 0) and ...: Waits until all processes with smaller numbers or with the same number, but with higher process IDs, finish their work.
Lines 44–46: Critical section: Prints a message indicating that the current process is in the critical section and simulates some work by sleeping for one second.
Line 49: number[process_id] = 0: Marks the exit section for the current process by resetting its ticket number to 0.
Lines 52–57: Creates and starts threads for each process:
Line 54: thread = threading.Thread(target=bakery_algorithm, args=(i,)): Creates a new thread that will execute the bakery_algorithm function with the process ID i.
Line 55: threads.append(thread): Appends the thread to the threads list.
Line 56: thread.start(): Starts the thread.
Lines 60–64: Waits for all threads to complete their execution.
Line 62: thread.join(): Waits for the thread to complete its execution.
Line 66: print("All processes have completed their execution."): Prints a message indicating that all processes have finished executing.

Limitations

Performance: Processes keep checking others’ numbers, leading to potential inefficiencies.
Scalability issues: With many processes, checking can become burdensome.

Conclusion

Lamport’s bakery algorithm offers a straightforward and fair method to ensure mutual exclusion in systems. where multiple processes seek access to a shared resource. By mimicking the process of customers waiting their turn in a bakery, the algorithm provides an understandable mechanism to prevent simultaneous access and potential system conflicts.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments