# CS 3423 Operating Systems Assignment 7 solution

\$24.99

Original Work ?

## Description

1. [40 points] Problem Set
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 the transaction() function. Fix the transaction() function to prevent
void transaction(Account from, Account to, double amount) {
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);
}
2. [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 deadlock free.
2. [60 points] Programming Exercise
In this programming exercise, you are to implement a number of deadlock detection and
avoidance algorithms.
2.1 [10 points] Cycle Detection in Graphs
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 graph G(V, E) can be represented in adjacency-list format, which has space
complexity closer to O(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 vertex v, simply do G[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
class Graph:
def __init__(self, G):
self.G = G
self.vertices = list(G.keys())
for i in self.G[v]:
yield i
def V(self):
for i in self.vertices:
yield i
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 the
graph-template.py file and rename it graph.py. It contains the Graph class and the
following DFS code.
WHITE = ‘white’
GRAY = ‘gray’
BLACK = ‘black’
def DFS(G):
G.color = {} # color, which is WHITE, GRAY, or BLACK
G.pred = {} # the predecessor
for u in G.V():
G.color[u] = WHITE
G.pred[u] = None
for u in G.V():
if G.color[u] == WHITE:
DFSVisit(G, u)
def DFSVisit(G, u):
G.color[u] = GRAY
if G.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.
2.2 Banker’s Algorithm
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 the banker-template.py file and rename it
banker.py. There are two parts: the constructor and utility functions, Safety core
algorithm, and the request processing.
2.1 [10 points] Construtor and Utility Functions
The helper functions are
def sumColumn(M, col): # M is a row major matrix; col is the column index.
# returns the scalar sum of the values in the column.
return sum(list(map(lambda x: x[col], M)))
# it is the same as
# tot = 0
# for row in M:
# tot += row[col]
def IncrVec(A, B):
# helper function to do A += B as vector, assuming len(A) == len(B)
def DecrVec(A, B):
# vector A -= B, assuming len(A) == len(B)
def GtVec(A, B):
# vector A[i]>B[i]. true if one or more pairs are true.
def LeVec(A, B):
superclass’s constructor, and it will skip capturing Max and computing Need.
● it detects deadlock from the current allocation and request matrix, rather than
checking existence of a safe sequence.
# Deadlock Detection, similar to Banker’s
from banker import Banker, sumColumn, IncrVec, DecrVec, GtVec
def __init__(self, alloc, totalRsrc):
Banker.__init__(self, alloc, None, totalRsrc)
def detect(self, Request): # see week 8 slide 53
”’detect deadlock with the request matrix”’
# 1(a) initialize Work = a copy of Available
# 1(b) Finish[i] = (Allocation[i] == [0, …0])
# optionally, you can keep a Sequence list
for _ in range(self.n):
for i in range(self.n):
# Step 2: similar to safety algorithm
# if there is an i such that (Finish[i] == False)
# and Request_i <= Work, (hint: LeVec() could help) then # Step 3: # Work += Allocation[i] # Finish[i] = True # continue Step 2 # Step 4: either done iterating or (no such i exists) # Finish vector indicates deadlocked processes. # if all True then no deadlock. 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, append P0 (+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, P1 must wait i=2, (Request[2]=[0, 0, 0]) <= (Work=[0, 1, 0]) True, append P2 (+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, append P3 (+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, append P4 (+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, append P1 (+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, append P0 (+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, P1 must wait i=2, (Request[2]=[0, 0, 1]) <= (Work=[0, 1, 0]) False, P2 must wait i=3, (Request[3]=[1, 0, 0]) <= (Work=[0, 1, 0]) False, P3 must wait i=4, (Request[4]=[0, 0, 2]) <= (Work=[0, 1, 0]) False, P4 must wait i=0, Finish[0] is True, skipping i=1, (Request[1]=[2, 0, 2]) <= (Work=[0, 1, 0]) False, P1 must wait i=2, (Request[2]=[0, 0, 1]) <= (Work=[0, 1, 0]) False, P2 must wait i=3, (Request[3]=[1, 0, 0]) <= (Work=[0, 1, 0]) False, P3 must wait i=4, (Request[4]=[0, 0, 2]) <= (Work=[0, 1, 0]) False, P4 must wait deadlock