Python Implementation of Bakery Algorithm
Python Implementation of Bakery Algorithm
Description:
This algorithm solves the critical section problem for n processes in software. The basic idea is that of a bakery; customers take numbers, and whoever has the lowest number gets service next. Here, of course, "service" means entry to the critical section.
All process threads must take a number and wait their turn to use a shared computing resource or to enter their critical section. The number can be any of the global variables, and processes with the lowest number will be processed first. If there is a tie or similar number shared by both processes, it is managed through their process ID. If a process terminates before its turn, it has to start over again in the process queue.
When a thread wants to enter critical section it has to make sure it has the smallest number, but
Program:1. with threads it may not be true thatonly one thread gets the same number2. if more that one thread has the smallest numberthen the thread with lowest id can enter
import threading
import random
import time
class BakeryAlgorithm():
# declaration and initial values of global variables
# ticket for threads in line, n - number of threads
tickets = [0,1,2,3,4]
# True when thread entering in line
entering = [False]*5
def lock(self,*args):
self.entering[args[0]] = True
maximum = 0
for ticket in self.tickets:
maximum = max(maximum, ticket)
self.tickets[args[0]] = maximum+1
self.entering[args[0]] = False
for i in range(len(self.tickets)):
if i != args[0]:
# Wait until thread j receives its number:
while self.entering[i]:
print("waiting")
# Wait until all threads with smaller numbers or with the samenumber, but with higher priority, finish their work:
while self.tickets[i] != 0 and (self.tickets[args[0]] > self.tickets[i] or (self.tickets[args[0]]==self.tickets[i] and args[0])>i):
print("waiting")
# The critical section goes here...
print(f"critical section used by process{args[0]}")
#exit section
self.tickets[args[0]] = 0
def main(self):
# Running all the 5 processes using thread module and passing process index as args since Thread supports args and kwargs argument only
t1 = threading.Thread(target = self.lock, args = (0,))
t2 = threading.Thread(target = self.lock, args = (1,))
t3 = threading.Thread(target = self.lock, args = (2,))
t4 = threading.Thread(target = self.lock, args = (3,))
t5 = threading.Thread(target = self.lock, args = (4,))
t1.start()
t2.start()
t3.start()
t4.start()
t5.start()
if __name__ == "__main__":
b = BakeryAlgorithm()
b.main()
import random
import time
class BakeryAlgorithm():
# declaration and initial values of global variables
# ticket for threads in line, n - number of threads
tickets = [0,1,2,3,4]
# True when thread entering in line
entering = [False]*5
def lock(self,*args):
self.entering[args[0]] = True
maximum = 0
for ticket in self.tickets:
maximum = max(maximum, ticket)
self.tickets[args[0]] = maximum+1
self.entering[args[0]] = False
for i in range(len(self.tickets)):
if i != args[0]:
# Wait until thread j receives its number:
while self.entering[i]:
print("waiting")
# Wait until all threads with smaller numbers or with the samenumber, but with higher priority, finish their work:
while self.tickets[i] != 0 and (self.tickets[args[0]] > self.tickets[i] or (self.tickets[args[0]]==self.tickets[i] and args[0])>i):
print("waiting")
# The critical section goes here...
print(f"critical section used by process{args[0]}")
#exit section
self.tickets[args[0]] = 0
def main(self):
# Running all the 5 processes using thread module and passing process index as args since Thread supports args and kwargs argument only
t1 = threading.Thread(target = self.lock, args = (0,))
t2 = threading.Thread(target = self.lock, args = (1,))
t3 = threading.Thread(target = self.lock, args = (2,))
t4 = threading.Thread(target = self.lock, args = (3,))
t5 = threading.Thread(target = self.lock, args = (4,))
t1.start()
t2.start()
t3.start()
t4.start()
t5.start()
if __name__ == "__main__":
b = BakeryAlgorithm()
b.main()
Output:
waiting
waiting
waiting
waiting
critical section used by process0
waiting
waiting
critical section used by process1
waiting
waiting
waiting
critical section used by process2
waiting
waiting
critical section used by process3
waiting
critical section used by process4
waiting
waiting
waiting
critical section used by process0
waiting
waiting
critical section used by process1
waiting
waiting
waiting
critical section used by process2
waiting
waiting
critical section used by process3
waiting
critical section used by process4
Comments