Assignment #7 Solution

$30.00

Description

What to submit: One zip file named <studentID>-hw7.zip(replace <studentID> with your own student ID). It should contain four files:

  • one PDF file namedhw7.pdffor Section 1 and Section 2.Write your answers in

English. Check your spelling and grammar. Include your name and studentID!

  • Section 2: Python source files. Include your name and student ID in the program comments ontop.

    • Section 2.1:graph.py,typescript1

    • Section2.2,2.3,2.4:banker.py,typescript2(showingoutputof TestUtility(), TestConstructor(), TestSafety(), andTestRequest())

    • Section 2.5:detect.py,typescript5

  1. [40 points] ProblemSet

    1. [20 points] 7.4 In Section 7.4.4, we describe a situation in which we prevent deadlock by ensuring that all locks are acquired in a certain order. However, we also point out that deadlock is possible in this situation if two threads simultaneously invoke thetransaction()function. Fix thetransaction()function to prevent deadlocks.

voidtransaction(Account from, Accountto,doubleamount){mutex lock1, lock2;

lock1 = get_lock(from); lock2 = get_lock(to); acquire(lock1);

acquire(lock2); withdraw(from, amount); deposit(to, amount);

release(lock2); release(lock1);

}

    1. [20 points] 7.7 Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlockfree.

  1. [60 points] ProgrammingExercise

In this programming exercise, you are to implement a number of deadlock detection and avoidance algorithms.

    1. [10 points] Cycle Detection inGraphs

Cycle detection can be used to detect deadlocks. Cycles are found in graphs. A (system) resource-allocation graph (RAG) is a directed graph for capturing the dependencies of processes on resources. An example of a RAG is shown in the following figure (a):

For a special case of a RAG where there is exactly one instance of resource per type, it can be transformed into a wait-for graph (WFG), which can use a conventional directed graph to capture just the processes but not resources. It is shown in figure (b) above.

A conventional graphG(V,E) can be represented in adjacency-list format, which has space complexity closer toO(V+E) for sparse graphs. In Python, a (directed) graph can be represented more conveniently using a dictionary, where a dictionary keeps track of

key-value pairs often in the form of a hash table. For example, consider the graph from Fig.

(b) above. It can be represented in Python as

G ={‘P1’: [‘P2’], ‘P2’: [‘P4’, ‘P5’, ‘P3’], ‘P3’: [‘P4’], ‘P4’:[‘P1′],’P5’:[]}

To find the list of neighbors of a vertexv, simply doG[v].For example,G[‘P2’]gives the value[‘P4’, ‘P5’, ‘P3’].However, it is more convenient to wrap the adjacency list inside a class so that more attributes can be associated with the graph. One way to do this is

classGraph:

definit(self, G): self.G = G

self.vertices = list(G.keys())

defAdj(self, v):

# return the adjacency list

foriinself.G[v]:

yieldi

defV(self):

foriinself.vertices:

yieldi

Cycle detection can be done by depth-first search (DFS), among many other algorithms. A generic version of DFS based on the CLRS textbook (Cormen, Leiserson, Rivest, and Stein) is given below (assuming you have the Graph data structure above). You may download thegraph-template.pyfile and rename itgraph.py. It contains theGraphclass and the following DFS code.

WHITE=’white’GRAY=’gray’ BLACK=’black’

defDFS(G):

G.color= {} #color, whichisWHITE, GRAY,orBLACKG.pred={} # thepredecessor

foruinG.V(): G.color[u] = WHITE G.pred[u] = None

foruinG.V():

ifG.color[u] == WHITE: DFSVisit(G, u)

defDFSVisit(G, u): G.color[u] = GRAYforvinG.Adj(u):

ifG.color[v] == WHITE: G.pred[v] = u DFSVisit(G, v)

G.color[u] = BLACK

DFS can be used for cycle detection, but it does not do it automatically. You will need to know the right place to make the modification to detect a cycle. The two graphs in the above figures (a) and (b) have been input to the test case of the .py file.

What to turn in:graph.py, typescript1 showing the cycle has been detected or printed, or the empty list if there is no cycle.

    1. Banker’sAlgorithm

The Banker’s Algorithm by Dijkstra is a deadlock avoidance algorithm during resource allocation. To implement this in Python, it is easier to package things in a class and call a set of utility functions. You can download thebanker-template.pyfile and rename itbanker.py.There are two parts: the constructor and utility functions, Safety core algorithm, and the requestprocessing.

2.1 [10 points] Construtor and Utility Functions

The helper functions are

defsumColumn(M,col):# M is a rowmajor matrix;col is thecolumnindex.# returnsthescalarsum of thevaluesin thecolumn.

returnsum(list(map(lambdax:x[col], M)))# it is thesameas

# tot =0

# for row inM:

# tot +=row[col]# returntot

defIncrVec(A, B):

# helper functionto do A += B asvector, assuming len(A)==len(B)

defDecrVec(A, B):

# vectorA -= B,assuming len(A)==len(B)

defGtVec(A, B):

# vector A[i]>B[i]. trueif one ormore pairsaretrue.

defLeVec(A, B):

# vector A[i] <= B[i]. true if ALL pairs are true.

The code forsumColumn()is given to you, but you need to write the other four utility functions.GtVec()andLeVec()are the “greater-than” and “less-than-or-equal-to” functions comparing two vectors (represented as lists), respectively. Unlike the built-in > and <= operators on lists and tuples, which perform lexicographical comparison, what is required here is the pairwise comparison. Note the subtle point thatGtVec()isdisjunctivewhileLeVec()isconjunctive.

classBanker:

definit(self, alloc, max, totalRsrc): ”’

constructor for Banker class.

alloc is a vector of number of instances of m resource types.

maxisa matrixfor max #ofinstances thattheprocessmayrequest.totalRsrcisvectoroftotal#ofinstancesofeach typeofresource

”’

self.Allocation=alloc self.TotalResources=totalRsrc

self.n=len(alloc)#numberofprocesses self.m=len(totalRsrc) #numberofresources

# thefollowing if-max allowsthedeadlock detection algorithm# to beabletosubclass withoutmax(sinceitdoesn’t needit)ifmaxis notNone:

self.Max = max

self.Need = []# your code here to initialize the Need matrix.

self.Available= [] #your code heretocompute Availablevector.#hint: involves TotalResourcesandsumColumn() function,

# aboolean flagtoindicate whetherinSafety() functionyouwantto#printthetraced output.bydefault False,but can be set toTrue. self.traceSafety=False

Modify the testbench to call just theTestUtility()andTestConstructor()functions (provided) and make sure your code behaves correctly before moving on to the next subsections. You should output that looks like this:

Testing Utility Functions:

A = [1, 2, 1], B = [1, 0,2],

A+=Bis[2,2,3],expect[2,2,3]

A-=Bis[1,2,1],expect[1,2,1]

A > B isTrue, expect True;A <= B isFalse, expectFalse

A

= [1, 2, 3], B

= [2, 2, 4],

A

+= B is [3, 4,

7], expect [3,

4,

7]

A

-= B is [1, 2,

3], expect [1,

2,

3]

A > B isFalse, expect False;A <= B isTrue, expectTrue

A

= [2, 3, 3], B

= [2, 3, 3],

A

+= B is [4, 6,

6], expect [4,

6,

6]

A

-= B is [2, 3,

3], expect [2,

3,

3]

A > B isFalse, expect False;A <= B isTrue, expectTrue

b.Available=[3,3, 2],expect ([3,3,2],)b.Need=[[7,4, 3], [1, 2, 2],[6,

0,0],[0,1,1],[4,3,1]],expect[[7,4,3],[1,2,2],[6,0,0],[0,1,

1], [4, 3, 1]]

2.2.2 [10 points] Safety Algorithm (week 8 slide37)

The Safety algorithm finds a safe sequence of executing a set of processes such that the system never enters an unsafe state, or else it reports that such a safe sequence does not exist. It is implemented as a method in the Bankerclass.

defSafety(self):

ifself.traceSafety: print(‘Need=%s, Available=%s’%(self.Need, self.Available))

# step 1

Sequence=[] # usethis listtosavethesafesequenceFinish=[Falsefor i inrange(self.n)]

Work= [] #your codetoinitialize Workvector#step2

for_inrange(self.n):

foriinrange(self.n):

ifself.traceSafety: print(‘i=%d,’ % i,end=””)#followthepseudocodeonslide37

# may need to print #

# compare Need[i] with Work.

# -hint:you may useLecVec(A,B) for A <=B:#

# step 3

# update bookkeeping: Work, Finish, and add to sequence

#Hint:you maywantto useIncrVec()forWork+=Allocation#

#step4. returnthesequenceifthereisone,orNoneifnot.

Run theTestSafety()function (provided) in the testbench. Note that we include atraceSafetyflag, which will print the intermediate values as the code runs. You can expect to get output like the following:

i=0,

(Need[0]=[7,

4,

3])

<=

(Work=[3,

3,

2])

False, P0 must wait

i=1,

(Need[1]=[1,

2,

2])

<=

(Work=[3,

3,

2])

True, append P1

i=2,

(Need[2]=[6,

0,

0])

<=

(Work=[5,

3,

2])

False, P2 must wait

i=3,

(Need[3]=[0,

1,

1])

<=

(Work=[5,

3,

2])

True, append P3

i=4,

(Need[4]=[4,

3,

1])

<=

(Work=[7,

4,

3])

True, append P4

i=0,

(Need[0]=[7,

4,

3])

<=

(Work=[7,

4,

5])

True, append P0

i=1, Finish[1] True, skipping

i=2, (Need[2]=[6,0, 0]) <=(Work=[7,5, 5])True, appendP2

s is [1, 3, 4, 0, 2]

2.2.2 [10 points] Resource-Request Algorithm (week 8 slide 47)

The Resource-Request Algorithm is the outer code of the Banker’s algorithm that calls the Safety algorithm above to decide how to respond to the request by the process. Add the following method named Request() and a utility method named Release() to your Banker class:

defRequest(self,i,rqst): #slide47”’

called withtherequesting processi and theresourcevectorfor howmany instancesofeach resourcetorequest.

therqstis avectorof mlength.”’

# step 1

#hint:useGtVecofLeVectocompare request vector withNeed[i]#raiseanexceptionifoverclaimed

#

# step 2

# incaseofwait, simply returnNone#

# step 3

# pretend to allocate requested resource:

#save snapshotofAvailable, Allocation,andNeed#update Available, Allocation,andNeed

# call Safety()

# if a safe sequence exists, return it.

#otherwise, restore saved snapshotandreturnNonedefRelease(self,i):

”’

need this functiontoreleasetheresources allocatedtoP_iafterit hasfinished execution.

”’

#hint: update self.Available, self.Allocation,andself.Need.#hint:you maywanttocall utility functions IncrVec

# hint: but in which order? who goes first, last, or don’t care?

Run the TestRequest() code using the return values of the TestSafety() as provided in the template code. You can expect to get the output like this for this part:

Found safe sequence [1, 3, 4, 0, 2]

P1 allocated [2, 0, 0], requesting [1, 0, 2],

P1 releasing, available=[5, 3, 2]

P3 allocated [2, 1, 1], requesting [0, 1, 1],

P3 releasing, available=[7, 4, 3]

P4 allocated [0, 0, 2], requesting [3, 3, 0],

P4 releasing, available=[7, 4, 5]

P0 allocated [0, 1, 0], requesting [0, 2, 0],

P0 releasing, available=[7, 5, 5]

P2 allocated [3, 0, 2], requesting [3, 0, 0],

P2 releasing, available=[10, 5, 7]

    1. [20 points] Deadlock Detection Algorithm (week 8 slide53)

Write the deadlock detection algorithm. It is similar to the Banker’s algorithm, and code reuse including the utility functions and most of the constructor is possible, if you make minor adjustments. The differencesare

      • there is no Max and Need; instead, it has requests. => we pass None to the superclass’sconstructor,anditwillskipcapturingMaxandcomputingNeed.

      • it detects deadlock from the current allocation and request matrix, rather than checking existence of a safesequence.

Downloaddetect-template.pyand rename itdetect.py.It looks like the following: # Deadlock Detection, similar to Banker’s

from banker import Banker, sumColumn, IncrVec, DecrVec, GtVec

classDeadlockDetector(Banker):

definit(self, alloc, totalRsrc):

Banker.init(self, alloc,None, totalRsrc)

defdetect(self,Request): # seeweek8slide53”’detect deadlock withtherequest matrix”’#1(a) initialize Work= acopyofAvailable

# 1(b) Finish[i] = (Allocation[i] == [0, …0])

# optionally, you can keep a Sequence list

for_inrange(self.n):

foriinrange(self.n):

# Step 2: similar to safety algorithm

# ifthereis an isuch that (Finish[i]==False)

# andRequest_i<=Work, (hint: LeVec() could help)then# Step3:

# Work+=Allocation[i]# Finish[i]=True

# continue Step2

#Step4:either done iteratingor (nosuchiexists)# Finish vector indicates deadlockedprocesses.

# if allTrue thennodeadlock.

The testbench is included in the template file. There are two cases: one without deadlock and one with deadlock, both taken from the textbook. You can expect to see the following output:

Finish=[False, False, False, False, False]

i=0, (Request[0]=[0,0, 0]) <=(Work=[0,0, 0])True, appendP0

(+Allocation[0]=[0,1,0])=> Work=[0,1, 0],Finish=[True, False,False,False, False]

i=1, (Request[1]=[2,0, 2]) <=(Work=[0,1, 0])False,P1mustwait

i=2, (Request[2]=[0,0, 0]) <=(Work=[0,1, 0])True, appendP2

(+Allocation[2]=[3,0,3])=> Work=[3,1, 3],Finish=[True, False,True,False, False]

i=3, (Request[3]=[1,0, 0]) <=(Work=[3,1, 3])True, appendP3

(+Allocation[3]=[2,1,1])=> Work=[5,2, 4],Finish=[True, False,True,True, False]

i=4, (Request[4]=[0,0, 2]) <=(Work=[5,2, 4])True, appendP4

(+Allocation[4]=[0,0,2])=> Work=[5,2, 6],Finish=[True, False,True,True, True]

i=0, Finish[0] is True, skipping

i=1, (Request[1]=[2,0, 2]) <=(Work=[5,2, 6])True, appendP1

(+Allocation[1]=[2,0,0])=> Work=[7,2, 6],Finish=[True, True,True,True, True]

sequence = [0, 2, 3, 4, 1]

Finish=[False, False, False, False, False]

i=0, (Request[0]=[0,0, 0]) <=(Work=[0,0, 0])True, appendP0