Python Implementation of Eisenberg and McGuire Algorithm














































Python Implementation of Eisenberg and McGuire Algorithm



Python Implementation of Eisenberg and McGuire's Algorithm

Description: This algorithm is alternative to the Bakery Algorithm, which does not use unique id numbers (at least not in the same way as the Bakery Algorithm)
It solves the Critical Section Problem for N Processes.
The common data structures are:
var flag: array [0 .. n-1] of (idle, waiting, active) ;
turn: 0 .. n-1 ;

All the elements of the flag are initially idle, the initial value of "turn" is
immaterial (between 0 and n-1).

Let's understands the algorithm through the program, read comments carefully!

Program:

import threading

class Solution():
# turn is set arbitrarily to a number between 0 and n-1 .

# flags variable for each process is set to WAITING whenever it intends to enter the
critical section. flags take either IDLE or WAITING or ACTIVE. Initially, the flags variable for each process is initialized to IDLE.
flags = [0]
turn = 0
n = 8

def entryProtocol(self,*args):
index = self.turn

# if there were no other active processes, AND if we have the turn or else whoever
has it is idle, then proceed. Otherwise, repeat the whole sequence.
while (not((index >= self.n) and ((self.turn == args[0]) or (self.flags[self.turn] == "IDLE")))):
# announce that we need the resource
self.flags[args[0]] = "WAITING"

index = self.turn

# scan processes from the one with the turn up to ourselves. repeat if necessary
until the scan finds all processes idle
while (index != args[0]):
if (self.flags[index] != "IDLE"):
index = self.turn
else:
index = (index + 1) % self.n

# now tentatively claim the resource
self.flags[args[0]] = "ACTIVE"

# find the first active process besides ourselves, if any
index = 0
while ((index < self.n) and ((index == args[0]) or (self.flags[args[0]] != "ACTIVE"))):
index+=1

 # Start of CRITICAL SECTION HERE!

 # claim the turn and proceed
self.turn = args[0]
#End of critical section


def exitProtocol(self,*args):
index = (self.turn + 1) % self.n
#find a process which is not IDLE
while (self.flags[index] == "IDLE"):
index = (index + 1) % self.n
self.turn = index
# we're finished now
self.flags[args[0]] = "IDLE"


def main(self):
# starting the entry and exit protocol for all 8 processes
for i in range(8):
t1 = threading.Thread(target = self.entryProtocol, args = (i,))
t1.start()
t2 = threading.Thread(target = self.exitProtocol, args = (i,))
t2.start()


if __name__ == '__main__':
d = Solution()
d.main()





More Articles of yash boura:

Name Views Likes
Python Implementation of Mutual-Exclusion with TestAndSet 1593 1
Introduction to Deadlock 1335 2
Introduction To Monitors 1633 3
Python Implementation of Bakery Algorithm 2619 3
Introduction to Critical-Section Problem 1485 2
Python 998 9
Python Implementation of Mutual-Exclusion with semaphore 4529 2
Python Implementation of Reader-Writer Solution using Semaphore 6425 2
Python Implementation of Producer-Consumer Solution using Semaphore 5737 2
Different Method for Handeling Deadlock 1286 2
Python Implementation of Dining-Philosphers Solution using Semaphore 11079 2
Python Numpy polynomials operation and implementation in Matplotlib 1804 2
Python Implementation of Eisenberg and McGuire Algorithm 1584 2
Python Implementation of Petersons Solution 2719 2
Introduction to Process Synchronization 1747 2
Python Implementation of Bankers Algorithm 8108 2
Python Implementation of Deadlock-Detection Algorithm 5294 1
Python Implementation of Dekkers Algorithm 2464 1

Comments