banderson623/Assignment 8.txt

## 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
	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