Homework 2 Solution

CS 502

Due:  November 10


  1. Consider Algorithm 3 of Chapter 6 in the book (6.2.1.3).  We want to extend the solution for n processes for n > 2.  Implicit in the algorithm as given is that the other process (j) is always equal to (1-i).  To generalize, let the statement turn:=j be replaced by turn:=(turn+1) mod n.  Evaluate this new algorithm with respect to the set of properties of a "good" solution.

The modified algorithm has shared data of:

var
    flag: array [0..n-1] of boolean;
    turn: 0..n-1

The code for process i is:

repeat
    flag[i] := true;
    turn := (turn + 1) mod n;
    while (flag[j] and turn = j) do no-op;

    /* critical section */

    flag[i] := false;

    /* remainder section */

until false

Let us consider a system with 3 processes, P0, P1, and P2.   Let turn be 0 initially.  Now let P0 go through the entry code and then enter its critical section.  We then have:

    flag[0] = true; flag[1] = false; flag[2] = false; turn = 1

If  goes through its entry section to the while statement, then we have

    flag[0] = true; flag[1] = true; flag[2] = false; turn = 2

Now, we can either fix j to be some process other than the current one (say 0), or we can try and "improve" the situation by having j range over all processes other than the current one (j = 0 or j = 2).  In either case, we fall through the while condition and enter the critical section, violating mutual exclusion.

  1. (aka 6.6)  Show that, if the wait and signal operations are not executed atomically, then mutual exclusion may be violated.

Suppose that the value of semaphore S = 1 and processes P1 and P2 execute wait(S) concurrently according to the following timeline:

  1. T0: P1 determines that value of S = 1
  2. T1: P2 determines that value of S = 1
  3. T2: P1 decrements S by 1 and enters critical section
  4. T3: P2 decrements S by 1 and enters critical section
  1. (aka 6.12)  Suppose that the signal statement can appear as only the last statement in a monitor procedure. Suggest how the implementation described in Section 6.7 can be simplified.

Since the signal statement can only appear as the last statement in a monitor procedure, the signaling process can exit the monitor immediately after executing the signal statement.  Thus, there is no need for the semaphore next and the integer variable next_count.

wait(mutex)
    body of F
signal(mutex)

x-count := x-count + 1;
signal(mutex);
wait(x-sem);
x-count := x-count - 1;

if x-count > 0
    then begin
        signal(x-sem);
        exit monitor
        end
    else
        signal(mutex)

  1. (aka 7.8)  Consider a system consisting of four resources of the same type, being shared by three processes, each of which needs at most two resources.  Prove that the system is deadlock free.

Proof by contradiction.  Suppose the system is deadlocked.  This implies that each process is holding (at least) one resource and is waiting for one more. (By the circular wait necessary condition.) Since there are three processes and four resources, one process must be able to obtain two resources.  This process requires no more resources and therefore it will return its resources when done.

  1. Consider the following snapshot of a system:
Available

A

B

C

D

2

1

0

0

 

 

Max

Allocation

A

B

C

D

A

B

C

D

P0

0

0

1

2

0

0

1

2

P1

2

7

5

0

2

0

0

0

P2

6

6

5

6

0

0

3

4

P3

4

3

5

6

2

3

5

5

P4

0

6

5

2

0

3

3

2

Answer the following questions using the banker's algorithm:

  1. What is the content of the matrix Need?

 

Need

A

B

C

D

P0

0

0

0

0

P1

0

7

5

0

P2

6

6

2

2

P3

2

0

0

1

P4

0

3

2

0

  1. Is the system in a safe state?  (If so, show a safe sequence; if not, be specific about the violating conditions.)

Yes. {P0, P3, P4, P1, P2}

  1. If a request from process P2 arrives for (0, 1, 0, 0), can the request be granted immediately? (Be sure and justify your answer.)

If the given request is granted, we have the following snapshot:

 

Allocation

A

B

C

D

P0

0

0

1

2

P1

2

0

0

0

P2

0

1

3

4

P3

2

3

5

5

P4

0

3

3

2

   

 

Need

A

B

C

D

P0

0

0

0

0

P1

0

7

5

0

P2

6

5

2

2

P3

2

0

0

1

P4

0

3

2

0

    and

Available

A

B

C

D

2

0

0

0

    We can add to the safe sequence {P0, P3, P4}, resulting in

Available

A

B

C

D

4

6

9

9

    but at this point neither P1 nor P2 can be completed, so if we grant P2's request we end up with an unsafe state, so the request cannot be granted immediately.