Operating Systems: Homework 1

Spring 1999

G22.2250

Instructor: Professor Krishna Palem

T.A. Suren Talla

Grading The questions vary in difficulties. Here's how much each question is worth:

   Question  Points                      
   1.7        3                            
   1.10       3                           
   2.3        3
   2.5        3
   3.1        3
   3.2        3
   3.5        3
   4.5        3
   4.6        3
   4.8        9 
   5.2        3
   5.4        9  (3 for each subproblem)
   5.5        6  (2 for each subproblem) 
   5.8        8  (2 for each subproblem) 
   5.10       9  (3 for each subproblem) 
   6.1        3
   6.12       7 
   6.13       7
   6.20       3
   6.22       9
   Total    100

Criteria For many questions that require descriptive answers, there are no right ones. So sometimes I let things slide when it's clear that you understand the concepts, even though they don't match the correct answers. For questions that require you to show a piece a code or a proof, you don't get any credit for reciting text.

Brief (i.e. one sentence) and correct answers get more points than verbose and incorrect ones. You don't get partial credit for verbosity.

Grade distribution The average grade is 72.

Answers

4.8 Producer-consumer question. Most of you miss the point of this question. The main aspect everyone is forgeting is that statements are not executed atomically. For example, suppose you have a statement such as:

   counter := counter + 1
where counter is a variable in shared memory. Executing this statement requires a memory read and a memory write (we can assume that the read and write are performed atomically) to the shared variable counter. Typically this can be implemented in machine code as:
   (1) register <- load counter  
   (2) register <- register + 1
   (3) store register, counter
Depending on how your program is written, other processes or threads may be able to read from or write to the variable counter between the read in instruction (1) and the write in instruction (3).

For example, suppose the shared variable counter is initialized to 0, and two threads A and B are to execute the following statements (a) and (b) concurrently. (The order of evaluation is indeterminate.)

   A: counter := counter + 1   (a)
   B: counter := counter - 1   (b)
One would naively expect the value of counter to be zero after the two statements finish, since the effects of executing (a) before (b) and executing (b) before (a) are identical. However, this is not correct. For example, consider the following sequence of interleaving atomic actions and their effects:

               
                              t1 t2  counter
   A: t1 <- load counter      0      0 
   B: t2 <- load counter      0  0   0
   B: t2 <- t2 - 1            0  -1  0 
   B: store t2, counter       0  -1 -1
   A: t1 <- t1 + 1            1  0  -1 
   A: store t1, counter       1  0   1 

Here, the final value of counter is 1.

Another possible interleaving gives a different final value:

               
                              t1 t2  counter
   B: t2 <- load counter         0   0 
   A: t1 <- load counter      0  0   0
   A: t1 <- t1 + 1            1  0   0 
   A: store t2, counter       1  0   1
   B: t2 <- t2 - 1            1  -1  1 
   B: store t2, counter       1  -1  -1  

In general, we have to be aware of the effects of multiple threads writing to the same shared variable. Most of you did not take this into account and thus did not get any points for your answers.

So a correct solution is not the obvious one. Here's a typical, obvious, but wrong solution for this problem:

    var counter : 0..n   := 0; (* number of items *)
    var in      : 0..n-1 := 0;
    var out     : 0..n-1 := 0;
    var buffer  : array[0..n-1] of item;

    Producer:

       ...
       while counter = n do nothing;
       buffer[in] := nextp;
       in := in + 1 mod n;
       counter := counter + 1;  (* a *)
       ...

    Consumer:

       ...
       while counter = 0 do nothing;
       nextc := buffer[out];
       out := out + 1 mod n;
       counter := counter - 1;  (* b *)
       ...
The intuition most of you try to use is that the counter keeps track of how many items are in the buffer. Seems obvious, right? What's the problem?

The problem is that the producer and the consumer can both try to update the variable counter at the same time. However, as we have seen above, this can lead to unexpected results. For example, the consumer may read the value of counter into a register, subtract this value by one in the register. However, in the meantime, the producer may already have incremented the value of counter in shared memory a few times, before the consumer stores the old and out-dated value of counter back into memory. This results in various race conditions .

Other solutions proposed include adding a flag indicating whether the queue is full (or empty). These solutions suffer from the same problem as the above.

In general, any solutions that include the use of the a shared variable concurrently writable by both the consumer and the producer are incorrect.

Okay, here's the correct solution provided by the book's instructor manual. There are other alternatives.

    var in      : 0..n-1 := 0;
    var out     : 0..n-1 := 0;
    var buffer  : array[0..n-1] of item;
    var full    : array[0..n-1] of boolean;  (* initially all false *)

    Producer:

       ...
       while not full[in] do nothing;
       buffer[in] := nextp;
       full[in] := true;    (* a *)
       in := in + 1 mod n;
       ...
       

    Consumer:

       ...
       while full[out] do nothing;
       nextc := buffer[out];
       full[out] := false;    (* b *)
       out := out + 1 mod n;
       ...
full[i] is true iff the ith item is on the queue. Note that when statements (a) and (b) are executed concurrently, variables in and out must have different values (can you see why?). This implies that we never try to write to the same location in the array full at the same time.

Another potential solution that I come up with is this:

    var in      : 0..2n-1 := 0;
    var out     : 0..2n-1 := 0;
    var buffer  : array[0..n-1] of item;

    Producer:

       ...
       while ((out - in) mod 2n) = n do nothing;
       buffer[in mod n] := nextp;
       in := in + 1 mod 2n;
       ...

    Consumer:

       ...
       while in = out do nothing;
       nextc := buffer[out mod n];
       out := out + 1 mod 2n;
       ...
Here, the expression ((out - in) mod 2n) = n tests that the producer is not ahead by n entries (i.e. the buffer is not full). The expression in = out tests that the buffer is not empty. Why does this work (or doesn't work)? Note the similarity with the original code. In particular, the producer does not write to the variable out and the consumer does not write to the variable in.

5.4

  Process Arrival Time   Burst Time
  ---------------------------------
   P1     0.0            8
   P2     0.4            4 
   P3     1.0            1
FCFS:
   Time  Process  Turnaround
   -------------------------------
   0     P1       8 - 0    = 8
   8     P2       12 - 0.4 = 11.6
   12    P3       13 - 1   = 12
   13    
   -------------------------------
                   avg = 10.533
SJF:
    Time  Process  Turnaround
   -------------------------------
   0     P1       8 - 0    = 8     <- at time 0 only P1 has arrived
   8     P3       9 - 1    = 8
   9     P2       13 - 0.4 = 12.6
   13    
   -------------------------------
                    avg = 9.53
SJF with 1 sec idle time. <
    Time  Process  Turnaround
   -------------------------------
   0     idle
   1     P3        2 - 1    = 1     <- at this time P1 P2 and P3 have arrived
   2     P2        6 - 0.4  = 5.6
   6     P1       14 - 0.0  = 14
   14    
   -------------------------------
                    avg = 6.86
This is a straight forward question, but you have to know the definition of turnaround time.

6.22 Show a history that is possible under two phase locking (2PL) but not under time-stamp ordering (TO), and one that is possible under TO but not 2PL.

We'll assume that transaction T1 starts before T2, therefore TS(T1) < TS(T2). Here's a schedule that is possible under 2PL but fails under TO. Note: rl(y) means acquire a read lock on y, and wl(x) means acquire an exclusive (write) lock on x. ul(x) means unlock x.

   T1       T2
   -------------
   r(x)
            w(y)
   r(y)
This fails under TO because TS(T1) < W-timestamp(y) = TS(T2) when T1 attemps to read y.

With locking annotations, we have the following feasible 2PL history:

   T1       T2
   --------------
   rl(x)
   r(x)
            wl(y)
            w(y)
            ul(y)
   rl(y)
   r(y)
   ul(x)
   ul(y)

Similarly, the following is a history that is feasible under TO but fails under 2PL.

   T1    T2
   ---------
   w(x)
         w(x)    <- T2 cannot get exclusive lock on x.
   w(y)   
         w(y)
   w(z) 
         w(z)