Skip to content

Instantly share code, notes, and snippets.

@banderson623

banderson623/Assignment 8.txt

Created March 29, 2013 03:12
Show Gist options
  • Save banderson623/5268513 to your computer and use it in GitHub Desktop.
Save banderson623/5268513 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Assignment 8.txt
Brian Anderson
ComS 352, Assignment 8
March, 28th, 2013
-------------------------------------------------------------------------------
1.A. Deadlock happens between the P1 and P2 during the following sequence.
P1 locks s1, 1.1
(p1 access x) 1.2
p2 locks s2 2.1
(p2 access y) 2.2
p2 locks s3 2.3
(p2 accesss z,y) 2.4
p1 is waiting for s2 1.3
p2 releases s2 2.5
p1 acquires s2 1.3
(p1 access y) 1.4
p2 waits for s1 2.6
p1 waits for s3 1.5 <-- DEADLOCK, it is held by p2
The following changes to p2 will prevent the deadlock and protect the acccess to the shared
variables...
(2.1) wait(s2);
(2.2) y = y*2;
(2.3) wait(s3);
(2.4) z = z - y;
(new) signal(s3)
(2.5) signal(s2);
(2.6) wait(s1);
(new) wait(s3);
(2.7) x = x + z;
(2.8) signal(s1);
(2.9) signal(s3)
Now the following sequence will happen:
Flow Lock held by: s1 s2 s3
---- -- -- --
P1 locks s1, 1.1 p1
(p1 access x) 1.2 p1
p2 locks s2 2.1 p1 p2
(p2 access y) 2.2 p1 p2
p2 locks s3 2.3 p1 p2 p3
(p2 accesss z,y 2.4 p1 p2 p3
p2 release s3 (new) p1 p2
p1 is waiting for s2 1.3 p1 p2
p2 releases s2 2.5 p1
p1 acquires s2 1.3 p1 p1
(p1 access y) 1.4 p1 p1
p2 waits for s1 2.6 p1 p1
p1 locks for s3 1.5 p1 p1 p1
(p1 access x,y,z) 1.6 p1 p1 p1
p1 release s3 1.7 p1 p1
p1 release s2 1.8 p1
p1 release s1 1.9
p2 locks s1 2.6 p2
p2 locks s3 (new) p2 p3
(p2 access x,z) 2.7 p2 p3
p2 release s1 2.8 p3
p2 release s3 2.9
-------------------------------------------------------------------------------
1.B. No Deadlock will happens between the P1 and P3. Here is only sequence
that can will actually execute.
Flow Lock held by: s1 s2 s3
---- -- -- --
P1 locks s1, 1.1 p1
(p1 access x) 1.2 p1
P3 locks s2 3.1 p1 p3
(p3 access y) 3.2 p1 p3
p1 waiting for s2 1.3 p1 p3
p3 locks s3 3.3 p1 p3 p3
(p3 access z,y) 3.4 p1 p3 p3
p3 release s3 3.5 p1 p3
p3 release s2 3.6 p1
p1 locks s2 1.3 p1 p1
(p1 access y,x) 1.4 p1 p1
p1 locks s3 1.5 p1 p1 p1
(p1 access x,y,z) 1.6 p1 p1 p1
p1 release s3 1.7 p1 p1
p1 release s2 1.8 p1
p1 release s1 1.9
p3 locks s1 3.7 p3
(p3 acccess x) 3.8 p3
p3 release s1 3.9
-------------------------------------------------------------------------------
2.A. What is the content of the matrix Need?
Need = Maximum Resources - Currently Allocated Resources
= Need =============
| A B C D
+ -------------
P0 | 0 0 0 0
P1 | 0 7 5 0
P2 | 0 0 2 0
P3 | 1 0 1 2
P4 | 0 6 4 2
-------------------------------------------------------------------------------
b. Is the system in a safe State? - SAFE, see work below
Safe Sequence is: P2, P1, P3, P4, P0
Work = Available = <1 5 2 0>
Operations | Available (after operation): A B C D
----------------------------------------------------------
Before... ("available") 1 5 2 0
P2 takes (C:2) 1 5 0 0
P2 terminates (release B:6,C:5,D:2) 1 11 5 2
P1 takes (B:7, C:5) 1 4 0 2
P1 terminates (release A:1,B:7,C:5,D:0) 2 11 5 2
P3 takes (A:1, C:1, D:2) 1 10 5 0
P3 terminates (release A:2, B:3, C:5, D:6) 3 13 10 6
P4 takes (B:6, C:4, D:2) 3 7 6 4
P4 terminates (release B:6, C:5, D:6) 3 13 11 10
P0 takes none 3 13 11 10
P0 terminate (release C:1, D:2) 3 13 12 12
Safe!
-------------------------------------------------------------------------------
c. If a request from process P1 arrives for (0, 4, 2, 0), can the request be granted immediately?
YES! (see work below)
The idea is to allocate the additional B:4, C:2 to P1 and see if the system is still in a safe state.
A B C D
Available (before P1) 1 5 2 0
--------------------------------------
P1's Allocation is now: 1 4 2 0
--------------------------------------
and the Need for P1 is: 0 3 3 0
--------------------------------------
Available is now: 1 1 0 0
Full need table
= Need =============
| A B C D
+ -------------
P0 | 0 0 0 0
P1 | 0 3 3 0
P2 | 0 0 2 0
P3 | 1 0 1 2
P4 | 0 6 4 2
Operations | Available (after operation): A B C D
--------------------------------------------------------------
Before... ("available") 1 1 0 0
P0 takes (nothing) 1 1 0 0
P0 terminates, releases (C:1, D:2) 1 1 1 2
P3 takes (A:1, C:1, D:2) 0 1 0 0
P3 terminates, releases (A:2, B:3, C:5, D:6) 2 4 5 6
P1 takes (B:3, C:3) 2 1 2 6
P1 terminates, release (A:1, B:7, C:5) 3 8 7 6
P2 takes (C:2) 3 8 5 6
P2 terminates, releases (B:6,C:5,D:2) 3 14 10 8
P4 takes (B:6, C:4, D:2) 3 8 6 6
P4 terminates, eleases (A:0,B:6,C:5,D:6) 3 14 11 12
@banderson623
Copy link
Author

I love ascii art!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment