California Sate University, San Bernardino
CS 660 Operating Systems Concepts & Theory

Instructors : Dr. Tong Lai Yu

Partial Solution to Homework 1
April, 2008

1) CSP problems.

a) Use CSP commands to write a statement that does the following:

If x ≥ y, assign x to m; i f y ≥ x assign y to m; if both x ≥ y and y ≥ x, either assignment can be executed. ( Keep your statement as simple as possible. )

Solution:

[ x ≥ y → m := x y ≥ x → m := y]

b) Use CSP commands to write a statement that does the following:

On each iteration, accept either a V() signal from process X and increment val, or a P() signal from process Y, and decrement val. But the second alternative cannot be selected unless val is positive. The repetitive command will terminate when both X and Y are terminated, or when X is terminated and val ≤ 0.

Solution:

*[X?V() -> val := val + 1 val > 0; Y?() -> val := val - 1] 2) ( Textbook 3.2 ) Construct a general resource graph for the following scenario and determine if the graph is completely reducible: R1, R2, and R3 are reusable resources with a total of two, two, and three units. Process P1 is allocated one unit each of R2 and R3 and is requesting one unit of R1. Process P2 is allocated one unit of R1 and is requesting two units of R3. Process P3 is allocated one unit each of R1 and R2 and is requesting one unit of R3.

Solution:

The graph is reducible ....

3) ( Textbook 3.4 ) Show that the ordered request policy of Havender prevents deadlock.

Solution:

The ordered request requires processes to request resources in an increasing order

Let R = { R1, R2, ..., Rm } be the set of resource types

F: R → N ( set of natural numbers )

e.g.

    F ( tape drive ) = 1
    F ( disk drive ) = 5
    F ( printer ) = 12

Suppose a process first requests Ri, it can request Rj only if F(Rj) > F(Ri)

We want to prove that circular-wait does not exist under this constraint and thus no deadlock can occur.

Proof:

Assume the contrary that circular-wait exists and suppose circular wait holds for
{ P0, P1, ..., Pn }

Pi is waiting for Ri which is held by Pi+1

Because Pi+1 is holding Ri while requesting Ri+1, we have

    F( Ri ) < F( Ri+1 ) for all i
    => F( R0 ) < F( R1 ) < ... < F( Rn ) < F( R0 )
    => F( R0 ) < F( R0 )
which is impossible.
Thus circular wait does not exist.

4) Consider a computer system that has 4 identical units of resource R. There are 3 processes each with a maximum claim of 2 units of resource R. Processes can request these resources in any way, i.e. two in one shot or one by one. The system alwasy satisfies a request if the enough resources are available. If the processes don't request any other kind of resource, is deadlock possible in this system? Why? ( Show your steps clearly. )

Proof:

Deadlock is not possible in this system.

In the worst case P = R - 1, each process holds one unit and requests another one. Since there are only R - 1 processes, the system still has one unit available to be assigned to one of the processes; the process can then finish the task and returns the two units, which can then satisfy another two pending processes and so on. Eventually, all processes can be satisfied and the system is deadlock free.

5) ( Textbook 3.7 ) Assume a system has P processes and R identical units of a reusable resource. If each process can claim at most N units of the resource, show that the system will be deadlock free iff R ≥ P(N - 1) + 1.

Proof is similar to 4). Actually, 4) is a special case of 5) with N = 2.