Operating Systems Qualifying Exam Fall 1998

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

  1. Synchronization: A bar has N stools and two entrances, with a hostess posted at each. The hostess, represented by a thread, locates the right number of stools for arriving parties (This is a bar intended to mix up groups; the hostesses ignore the fact that parties want to be seated next to each other). Make sure that two hostesses don't pick the same stool or a stool that is already occupied. Write C-like pseudo code for the operation performed by each hostess, using semaphores with operations P() and V(). A boolean array stool[] indicates whether the stool has been taken or not. Unfortunately, the bar is only dimly lit (plus, all the customers wear black), so that checking for empty stools is somewhat time-consuming. You should only check for stools if there are indeed empty ones and you should not block the second hostess from looking for seats while the first one tries to find a seat.
  2. CPU scheduling: Five batch jobs with running times of 10, 6, 2, 4, and 8 minutes. They are scheduled round-robin with equal priority and only require the CPU (no I/O). Compute the average waiting and turn-around time for these jobs. []
  3. Virtual memory: Both LRU and FIFO demand paging replaces the "oldest" page in some sense. What distinguishes them? For the page reference string 0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6, compare the page faults experienced by both mechanism, for a memory with 3 frames. Use the table below. []
    FIFO 0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6
    1                                          
    2                                          
    3                                          
    LRU 0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6
    1                                          
    2                                          
    3                                          
  4. We have seen several types of resource allocation: memory (malloc), pages for virtual memory systems, disk space for files, and CPU cycles. Briefly compare their properties:
  5. Networks: Time and space divsion multiplexing are used in communications and in operating systems, if somewhat differently. Give two examples of time division multiplexing in operating systems and describe how their properties.
  6. Disk scheduling: What is the difference between the C-LOOK and LOOK algorithm? Why might one prefer one over the other?
  7. Deadlock: A system has four processes, P1 through P4, and three types of resources, R1 (3 units), R2 (2 units) and R3 (2 units). Process P1 holds 1 R1 and requests 1 R2. Process P2 holds 2 R2 and requests one each of R1 and R3. P3 holds 1 unit of R1 and request 1 unit of R2. P4 holds 2 units of R3 and requests 1 unit of R1.

    Draw the resource graph for this system. Is there a danger for deadlock? If there is the danger of deadlock, is there a sequence of process completions that lets all processes finish?

Last updated Tue Dec 15 08:55:16 1998 by Henning Schulzrinne