George Mason University
DEPARTMENT OF COMPUTER SCIENCE

CS571 Operating Systems Spring 2002

Extra Credit EC1
Group Project
5 points
Due Friday 4/12/02




This is an extra credit group assignment. It is optional. If your group completes this assignment, your group paper will receive a grade and then each of your will receive the paper grade. It will add up to 0.5 to your raw score at the end of the term. (The raw score S is the average of your course components, weighted as in the course overview, and is on a scale of 1 to 10.)


This question concerns Problem 3 of Q1, the locking of databases. The objective here is to come up with short, brief, concise, elegant responses. Lengthy responses, even if correct, will we worth less than brief correct responses. Quality, not quantity, will be a principal consideration during evaluation.

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 three 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.
  • LOCKED(r): returns true if record r is locked, false otherwise.
  • 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, LOCKED, 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 a protocol for obtaining the locks. Why it is deadlock free?

    (b) Specify a monitor (Hoare style with condition variables) for the Lock Manager with the "grain=database" policy. Do not worry about special steps for transactions seeking read-only access to records.

    (c) Specify a monitor for the Lock Manager with the "grain=record" policy. Do not worry about special steps for transactions seeking read-only access to records.

    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: 

    (A)    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).

    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: 

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


    (d) In the grain=record model (eqs. B), the database acts as a set of M parallel servers, one for each record. The user requests are equally likely to go to any of these servers. Write down the MVA equations for this system. Show how to reduce these MVA equations into eqs. A given above. This shows that the eqs. A are exact, not an approximation. Briefly discuss whether this model can be extended to deal with transactions that lock 2 records each.

    (e) Sketch the response time asymptotes (see queueing tutorial) for the grain=database and grain=record models. What happens to the system when M gets large (say, 100's or 1000's of records)?