George Mason University
DEPARTMENT OF COMPUTER SCIENCE

CS571 Operating Systems Spring 2002

Q1 Midterm Exam (Take-Home)

100 points (final weight 15%)

Due 3/19/01



Notices

(1) Do this exam on your own. On the first page of your paper, include the honor pledge and sign it: "I have neither given nor received aid on this exam." Any evidence of copying or other forms of collusion will be grounds for failure of this exam.

(2) Be brief in your responses. But justify your answers. Without justification I cannot see what you have in mind and I cannot award partial credit.

(3) Prepare your responses with a word processing program.

(4) Use these resources:

Problem 1 (30 points) -- Semaphore Invariant

Consider the operations WAIT and SIGNAL on semaphores. We know from the definitions that WAIT(sem) may introduce a delay between the call to WAIT and the return; the length of the delay depends on the length of the waiting queue and the rate of new signals; there is no delay if the count of sem is larger than 0 at the time of call. We also know that SIGNAL(sem) does not delay; SIGNAL appears as a single event in the caller's context.

For the repeated use of a semaphore, we can capture the events implied by the definitions with the following variables for a given semaphore.

c(t) is the number of calls on WAIT(sem) through time t. (c(0)=0)

r(t) is the number of returns from WAIT(sem) through time t. (r(0)=0)

s(t) is the number of SIGNAL(sem) through time t. (s(0)=0)

I is the initial count of the semaphore (I >= 0).

A designer of concurrent programs claims that this statement is invariant (always true):

r(t) = min{c(t), s(t)+I}

 

(a) Prove that this invariant statement is true.

(b) Use this invariant statement to prove that the standard semaphore protocol for mutual exclusion is safe. The standard protocol is: 

        WAIT(mutex)
        CRITICAL SECTION
        SIGNAL(mutex)


where I(mutex)=1.

(c) Apply this invariant statement to prove that the synchronization protocol for the bounded buffer producer-consumer problem works correctly. Recall that the standard solution has this form: 

    P:  produce              C: WAIT(full)
        WAIT(empty)             remove item
        insert item             SIGNAL(empty)
        SIGNAL(full)            consume
        repeat                  repeat


where I(empty)=N and I(full)=0, and the steps "remove item" and "insert item" are mutually excluded. The correctness criterion can be expressed as follows:
0 <= p(t)-q(t) <= N
Where "<=" means "less than or equal", p(t) is the number of times the producer reachers its repeat statement, and q(t) is the number of times the consumer reaches its repeat statement. You should confirm that this inequality is the proper correctness criterion for the bounded buffer problem.

 

Problem 2 (20 points) -- Virtual Machines

Consider this line typed to a command line shell with the grammar described in the "Shell" slides of the Art of OS on-line book. 

     
     outfile < cat | pipe -pipe | infile -cat > cat

(a) Is this a valid command according to the shell grammar? If not, show why. If so, draw a diagram showing all the VMs active after this command is started. Include the login and shell VMs and show all parent, child, and sibling links.

(b) Write out the script produced by the parser as it interprets this command line. (See "Shell" slides for the format and syntax of scripts.)

 

Problem 3 (50 points) -- Locking Protocols

Let us consider some design problems of databases in which transaction threads must lock records before they can update them. There is a special server called the Lock Manager used by the transaction threads to lock and unlock records. The Lock Manager offers two operations:

  • LOCK(r): waits until record r is unlocked, then locks it and returns to the caller. The caller will be delayed until the requested lock is granted to this caller.
  • UNLOCK(r): unlocks record r and wakes up one thread waiting for r, if any are waiting.

    • We will study some methods for implementing LOCK and UNLOCK and the effects on performance caused by the "granularity of locks." The "grain=database" policy will lock the entire database and make transactions queue up whenever any record is already locked. The "grain=record" policy puts individual locks on the records and makes transactions queue up only when they want the same record.

    (a) A transaction thread requiring records r1,...,rk must acquire all the locks before reading or updating any of the records. In terms of Lock Manager operations, outline the protocol for obtaining the locks. Show why it is deadlock free and why it must precede the transaction's updating of records.

    (b) Specify a monitor (Hoare style with condition variables) for the Lock Manager with the "grain=database" policy. Include a correctness argument with your monitor.

    (c) Specify a monitor for the Lock Manager with the "grain=record" policy. Include a correctness argument with your monitor.

    Let us now investigate the relative performance of the two "grains" of locking defined above. For this analysis, we assume the simplest case, that all transactions lock a single record, chosen randomly from among all the records in the database.

    We will use the Mean Value equations (MVA) from queueing models to compute throughput, response time, and queue length for the grain=database policy. (For more context, refer to the queueing network tutorial linked to the CS571 Web page.) The model is as follows. A community of 100 users can request transactions against the database of M records. The user think time Z, which is the average time one user takes from completion of a transaction to initiation of the next transaction, is 60 sec. The mean service time of a transaction is S = 1 sec; S does not include queueing time in case of contention for the same lock. The metrics of this system are:

  • R(N) = response time of system (time from initiation of a transaction request to its completion, includes queueing time and service time),
  • X(N) = throughput (transactions completed per second), and
  • Q(N) = mean number of transactions waiting for a response from the system.

    • The Mean Value equations for calculating the three metrics are: 

           R(N)  =  S*(1+Q(N-1))
       X(N)  =  N/(R(N)+Z)
       Q(N)  =  X(N)*R(N)


    These values can be computed iteratively in a table with rows corresponding to N=1,2,...,100 and columns for N, Q(N), X(N), and R(N). Starting with Q(0)=0, the rows are computed one at a time. When the calculation is done, you will have a column of table giving the values R(1), R(2), ..., R(100), which is the response time function for up to 100 users.

    (d) Calculate the response time function R(N) for N=1,...,100, using the parameters and method quoted above. A spreadsheet is sufficient for this calculation.

    (e) The model above gives the response time versus N of the database for the grain=database policy. For the grain=record protocol, we can make an approximation. Since there are M queues, one for each record, the queueing faced by a single transaction is 1/M of the total queueing in the system. We can represent this in the mean value equations with a simple change: 

           R(N)  =  S*(1+Q(N-1))
       X(N)  =  N/(R(N)+Z)
       Q(N)  =  X(N)*R(N)/M


    Calculate R(N) for this policy and N=1,...,100 with M=10 records. Compare the two policies by plotting the two R(N) functions on the same graph. How would you characterize the differences between the grain=database and grain=record policies? For each policy, what is the largest N (user community size) so that the response time is not more than twice the service time?