Operating Systems Qualifying Exam Spring 1999

This is a closed-book, closed-note exam. You have 60 minutes to complete the problems. Be sure to justify your answers.

  1. Synchronization: You have been given the task to secure an intersection with a 4-way stop sign. The usual rules of the road apply: the first to come to the stop sign gets to cross the intersection and there can only be one car in the intersection at any one time. If cars are lined up at each incoming road, they take turns. There apparently is no rule who goes first if four cars happen to arrive at the intersection sign from four different directions, so you can define your own rule. Be careful to state your assumptions on your synchronization primitives, as not all implementations have the same behavior. "Implement" your solution using pseudo-C.
    Your solution has to take into account that cars are not served in the order of arrival, but rather round-robin, with queues at each incoming street. There are several ways to organize the code. In the example below, we execute functions on arrival and departure, with a time delay function called drive() representing the time it takes to cross the intersection. Alternatively, one could have a program executing the behavior of the intersection and "scheduling" cars. (This is probably true in general for these types of problems, where one can usually design a program executed by arriving resource consumers or one executed by the resource itself.) The program has to make sure that a car doesn't wait if the intersection is empty.

    We assume that threads waiting on a condition variable are awakened in the order of their arrival. (This is common, but not universal.) 

    semaphor b;              // protect global variables
condition street[4];     // each street
q[] = {0,0,0,0};         // number queued
int empty = 1;           // intersection is empty

// car arrives at street i, i=0,..,3
arrival(int i)
{
  b.p();
  if (empty) {
    empty = 0;
    b.v();
    drive(i);
  } else {
    q[i]++;
    b.v();
    street[i].wait;
    drive(i);
  }
}

// departure of car from intersection
departure(int i)
{
  // pick next intersection
  b.p();
  q[i]--;
  if (q[0] + q[1] + q[2] + q[3] > 0) {
    do {
      i = (i + 1) % 4;
    } while (q[i] == 0);
    street[i].signal;
  } else {
    empty = 1;
  }
  b.v();
}

drive(int i)
{
  sleep(5); // not exactly the best connotation for a car
  departure(i);
}
    (20 pts.)
  2. Describe the advantages and disadvantages of DMA. Consider a system that needs to service both time-sharing and real-time tasks.
    Direct Memory Access (DMA) allows the transfer of data between an I/O device and memory (or two I/O devices, one of which is memory-mapped), without passing through the CPU. Generally, this is significantly faster than copying, but it does block the memory bus, thus slowing down the CPU if it needs to access data outside its cache. This can be a particular problem for real-time tasks, as their execution may be delayed by an unrelated I/O operation executing a DMA transfer.
    (10 pts.)
  3. Describe priority inversion and how one might prevent it.
    From Silberschatz/Galvin, p.143: "But what happens if the higher-priority process needs to read or modify kernel data that is currently being accessed by another, lower-priority process? The high-priority process would be waiting for a lower-priority one to finish. This situation is known as priority inversion. ... This problem can be solved via the priority-inheritance protocol, in which all of these processes (the processes that are accessing resources that the high-priority process needs) inherit the high priority until they are done with the resource in question."
    (10 pts.)
  4. Consider a multi-level feedback queue in a single-CPU system. The first level (queue 0) is given a quantum of 8 ms, the second one a quantum of 16 ms, the third is scheduled FCFS. Assume jobs arrive all at time zero with the following job times (in ms): 4, 7, 12, 20, 25 and 30. Show the Gantt chart for this system and compute the average waiting and turnaround time.
    Gantt chart for multi-level queue

    Since all jobs enter the system at time 0, the turnaround time is the time of completion: (4 + 11 + 47 + 59 + 92 + 98)/6 = 311/6 = 51.83.

    The waiting time is simply the turnaround time minus the execution time. The average execution time is (4 + 7 + 12 + 20 + 25 + 30) / 6 = 98/6 = 16.33. Thus, the average waiting time is 35.5.

    (20 pts.)
  5. You have three hosts and one router:
    host IP address/subnet mask Ethernet address
    play.cs.columbia.edu 128.59.21.100/22 8:0:20:21:c6:8f
    www.cs.columbia.edu 128.59.16.166/22 8:0:20:9f:5a:cc
    vortex-gw.net.columbia.edu (router) 128.59.16.1/22 0:0:c:f:7e:f8
    www.cs.umass.edu 128.119.41.114/16 8:0:2b:bd:fb:91

    You, using play, are retrieving web pages from both www.cs.columbia.edu (CU) and www.cs.umass.edu (UMass). Draw the basic packet structure, indicating the layers and the addresses in each layer. Hint: the web port number is 80. You do not need to worry about the details of each layer beyond addressing information.

    packet layout
    Note that the IP address of the router does not appear in the packet at all.
    (20 pts.)
  6. A system is composed of four processes, p1 through p4, and three types of consumable resources, R1 through R3. There is one unit each of R1 and R3 available.

    Show the consumable resource graph to represent the system state. Which, if any, of the processes are deadlocked in this state?

    In a consumable resource graph (see, e.g., Nutt, Operating Systems - A Modern Perspective, p. 281f), edges from process to resource indicate a request, edges from resource to process are producer edges.
    resource graph for consumable resources
    The system is not deadlocked, since the following execution sequence holds:
    1. p1 acquires R1 and R3 and terminates;
    2. p2 produces R1 and R3 and wait on R2;
    3. p3 consumes R1 and R3 and terminate;
    4. p4 produces R2 and wait on R3;
    5. p2 consumes R2 and terminates.
    (20 pts.)

Last updated Sat May 08 13:09:59 1999 by Henning Schulzrinne