A precedence graph is a directed, acyclic graph. Nodes represent tasks and arcs specify the order in which tasks are to be accomplished: a task can execute as soon as all its predecessors have completed. Assume that the tasks are processes of following form:

process P wait for predecessors, if any body of P signal successors, if any 

Using semaphores synchronize five processes with the precedence graph to the right. Minimize the number of semaphores and do not impose constraints not specified in the graph. For example, P2 and P3 can execute concurrently after P1 completes.

Complete the Python implementation below. It contains testing code that starts the five processes in random order and then checks if the trace of the processes contains only allowed interleavings.

from threading import Thread, Semaphore from sys import stdout from random import sample

# YOUR CODE HERE raise NotImplementedError()

def doing(s): global tr; e.acquire(); tr = tr + s; e.release()

class P1(Thread): def run(self): # YOUR CODE HERE raise NotImplementedError() doing('P1') # YOUR CODE HERE raise NotImplementedError()

class P2(Thread): def run(self): # YOUR CODE HERE raise NotImplementedError() doing('P2') # YOUR CODE HERE raise NotImplementedError()

class P3(Thread): def run(self): # YOUR CODE HERE raise NotImplementedError() doing('P3') # YOUR CODE HERE raise NotImplementedError()

class P4(Thread): def run(self): # YOUR CODE HERE raise NotImplementedError() doing('P4') # YOUR CODE HERE raise NotImplementedError()

class P5(Thread): def run(self): # YOUR CODE HERE raise NotImplementedError() doing('P5') # YOUR CODE HERE raise NotImplementedError()

for _ in range(20): tr, e = '', Semaphore(1) # trace and lock for trace PS = [P1(), P2(), P3(), P4(), P5()] for p in sample(PS, k=5): p.start() for p in PS: p.join() assert tr in ('P1P2P3P4P5', 'P1P2P4P3P5', 'P1P3P2P4P5')