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

    Instructors : Dr. Tong Lai Yu

    Homework 2
    Due May 13, 2008 ( Tue )

  1. ( Textbook 2.3 )
    Explain what the following path expressions do:
    1. path {open + read}; close end
    2. path {openread ; read} ; {openwrite ; write} end

  2. Suppose we use the following to denote a resource graph: Pi : process i
    Rj: resource type j; can have 1 or more units
    Pi → Rj : Pi is making a request for resource Rj
    Pi ← Rj : one unit of resource Rj has been assigned to Pi     Consider the following resource graph: R1 has two units, R2 has two units, and R3 has one unit,

    Draw the graph. Give an example of a knot in the graph and explain why it is a knot. If you find that there's no knot in the graph, express the answer as an empty set.

  3. Consider the state of a system with processes P1, P2, and P3, defined by the following matrices.

    max-Avail A = ( 5 2 4 )

    Max-Claim B =
    2 2 2
    1 2 2
    3 1 3
    Allocation C =
    1 1 0
    1 0 1
    1 1 1

    a) Find the available matrix D and need matrix E in this state.

    b) Suppose now process P1 makes a request with

    F1 = ( 0 0 1 )

    If the request were granted, what would be the D, C, and E in the resulted state?

    c) To ensure the system be safe, should the request be granted? Why? Give your reasons in detail.

  4. ( Textbook 5.2 )
    If each process uses a different value for d in the Lamport's clock and vector clock equations, will the logical clocks and vector clocks schemes satisfy the total order relation => and the relation:

  5. Suppose Process P1 has events e11, e12, e13, e14, e15 P2 has events e21, e22, e23, e24, e25, P3 has events e31, e32, e33, e34, e35 There are message transits from e12 to e22, e23 to e15, e34 to e24. Suppose the vector time clocks for e11, e21, and e31 are
    1
    0
    0    		 ,      0
    1
    0    		 ,      0
    0
    1
    respectively.