Mid-Term Exam

March 12, 2003

Part I

Multiple choice. 5 points per question. Note: Problems 1-4 each has a single correct answer. Problem 5 has several correct answers; you are supposed to give all the correct answers. You need not explain your answers.

Problem 1

(One correct answer)
One difference between kernel mode and user mode is Answer: C.

Problem 2

(One correct answer)
If process P executes a non-blocking system call -- that is, a call to the kernel of a type that can always be satisfied immediately -- then Answer: D.

Problem 3

(One correct answer)
Consider a system that uses paging. Suppose an instruction in process P references virtual address V, which is located in page G, offset O. A page fault occurs if Answer: F.

Problem 4

(One correct answer)
In the readers-writers problem, processes P and Q are allowed to simultaneously access the shared resource if and only if: Answer: A.

Problem 5

(Several correct answers) Suppose that the operating system is running a non-preemptive scheduler and that process P is currently running. A context switch can occur: Answer: A,B.

Part II

Problems are worth 15 points each.

Problem 6

When control is transferred from a user process to the operating system, it is necessary to save the current value of the program counter. If the transfer of control is caused by the process executing a system call, this saving of the PC is implemented in software. If the transfer of control is caused by an interrupt, the saving of the PC has to be done by hardware. Explain the reason for the difference.

Answer: If the process is executing a system call, then it ``knows'' that control is going to be transferred, so it can save the return value of the PC before doing the call. In the case of an interrupt, the process doesn't know that the transfer will occur, and it won't work to have the interrupt handler code save the value of the PC, because, by the time it's gotten to the interrupt handler, the PC is, of course, pointing to the interrupt handler. So the saving of the PC has to be done at a lower level than the standard execution cycle. 1

Problem 7

Problem 8

Suppose that the operating system is running a round-robin scheduler with a 50 msec time quantum. There are three processes with the following characteristics: Process A enters the system at time 0. Process B enters at time 10 msec. Process C enters at time 20 msec.

Trace the evolution of the system. You should ignore the time required for a context switch. The time required for process P to block is the actual clock time between the time that P blocks and the time that it unblocks, regardless of anything else that is happening.

Answer:

 
Time    Running process     Events
0-50        A                  B enters at time 10.  C enters at time 20.
50-100      B
100-120     C                  C blocks until time 200.
120-130     A                  A blocks until time 230.
130-150     B                  B blocks until time 190
150-190     Idle               B unblocks at time 190
190-210     B                  C unblocks at time 200. B terminates at time 210
210-260     C                  A unblocks at time 230.
260-270     A                  A terminates at time 270.
270-280     C                  C terminates at time 280.

Problem 9

What is the "Transition Lookaside Buffer"? What information does it hold? A TLB is an "associative memory": What does that mean, and why is it important?

Answer: A Transition Lookaside Buffer is a very fast, small, associative memory device. The TLB holds pairs of page numbers and the associated frame numbers for pages very recently accessed. "Associative memory" means that the device is given the page number and immediately returns the associated frame number, rather than having to search through the pairs. This is important, since the TLB has to be extremely fast, as the translation from page number to frame number has to be done at each memory reference.

Problem 10

Suppose that there are two processes A and B running the following code:
Semaphores S and T are initially both equal to 1.

    Process A                        Process B
    DOWN(S)                          DOWN(T) 
    DOWN(T)                          DOWN(S)
    Critical section of A            Critical section of B
    UP(T)                            UP(S)
    UP(S)                            UP(T)