Midterm Examination from Spring 2000

This was a similar course, but not exactly the same schedule, syllabus, or text

1. How large should a quantum be?

Suppose we are using preemptive process scheduling. Choosing the correct quantum size (how long a process is allowed to run) is important to the effective operation of the operating system. Consider a single processor operating system that supports a large number of interactive users. Each time a process gets the processor, the interrupt clock is set to interrupt after the quantum Q expires. Assume that the same quantum is used for all processes.

1. What is the effect of setting the quantum to a very large value, say ten minutes?
2. What is the effect if the quantum is set to a very small value, say a few processor cycles?
3. Your answers to parts a) and b) should suggest that an appropriate quantum must be in between these extremes. Suppose you could turn a dial (or drag a slider bar) and vary the quantum. How would you know when you had chosen the "right" value? What factors make this value right from the user's perspective? What factors make it right from the system's point of view?

2. Mutual exclusion with Test-and-Set

Consider the Test-and-Set instruction described in our text on page 164. Let process P1 and process P2 running concurrently be two copies of the code suggested in Figure 6.7, page 165, where lock is a shared memory location.

1. Is deadlock possible? Explain.
2. Is indefinite postponement possible? Explain.
3. Why is indefinite postponement unlikely?
4. Describe circumstances and an example application for which this is an acceptable technique to enforce mutual exclusion
5. Describe circumstances and an example application for which this is NOT an acceptable technique to enforce mutual exclusion

3. Interprocess communication by send and receive

Suppose an operating system implements interprocess communication with blocking send and blocking receive primitives. That is, a process Q executing

     send (P, message);

     receive (Q, message);

     receive (Q, message);

     send (P, message);

1. Does this usually work? Give a possible sequence of events in which process Q successfully sends a message to process P, and both are able to continue processing.
2. Show four different scenarios under which deadlock occurs
3. Can such deadlocks occur with non-blocking send and receive calls? Explain
4. Propose a modification to blocking calls that avoids such deadlocks

4. Recovery from deadlock

Suppose that we recover from a deadlock by killing that process (or those processes) with the lowest cost(s) of deletion. This (these) processes are restarted and once again allowed to compete for resources.

1. What potential problems are posed by such an algorithm?
2. How would you solve these problems?

5. Waiting

Management of waiting is an essential part of every operating system. The text and I have discussed often the ready and blocked waiting states.

1. ready state
   1. List several ways a process could have gotten into the ready state
   2. What is the process waiting for?
   3. Could the process get "lost" waiting indefinitely?
2. blocked state
   1. List several ways a process could have gotten into the blocked state
   2. What is the process waiting for?
   3. Could the process get "lost" waiting indefinitely?
3. What features could an operating system incorporate to deal with the possibility that processes could start to wait for an event that might never happen?