March 12, 2003
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
- A. Kernel mode runs faster than user mode.
- B. Kernel mode is internal to the CPU; it does not require accessing
memory in RAM.
- C. Some operations are permitted in kernel mode that are prohibited
in user mode.
- D. Address translation is not needed in kernel mode.
- E. Kernel mode is written in assembly language.
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
- A. The program counter in P does not have to be saved.
- B. There is no need to switch to kernel mode.
- C. The process should do a DOWN on a semaphore.
- D. There is no need to call the process scheduler.
- E. An interrrupt should be issued.
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
- A. There is no pair [G,F] in the transition lookaside buffer.
- B. G is larger then the number of frames in memory.
- C. G is a page in some other process.
- D. V is an address in kernel space.
- E. O is larger than the page size.
- F. The page table entry PageTable[G] indicates that page G is not
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:
- A. P and Q are both reading.
- B. P and Q are both writing.
- C. Either P or Q or both is reading
- D. Either P or Q or both is writing
- E. P is reading and Q is writing, or vice versa.
- F. Either P and Q are both reading or P and Q are both writing.
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:
- A. When P terminates.
- B. When P blocks.
- C. When another process unblocks.
- D. When another process enters.
- E. When the time quantum is exhausted.
- F. When the priority of some other process exceeds the priority of P.
Part II Problems are worth 15 points each.
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.
- A. What is the placement problem in a system that uses
Answer: The placement problem arises in the case when a process
enters and there is more than one consecutive block of free space large
enough to hold the process. The problem is to have a policy for choosing
one of these blocks.
- B. Name two algorithms for solving the placement problem. (You need
not describe them; just name them.)
Answer: First fit; Best fit; Circular first fit.
- C. The placement problem does not arise in a system that uses paging.
Explain why not.
Answer: In a paging system, the frames occupied by a single
process do not need to be consecutive. Therefore, the choice of frames
makes no difference. As long as there are enough free frames for the
process pages needed, these can be used wherever they are located in memory.
Suppose that the operating system is running a round-robin scheduler with
a 50 msec time quantum. There are three processes with the following
Process A enters the system at time 0. Process B enters at time 10 msec.
Process C enters at time 20 msec.
- Process A runs for 60 msec, blocks for 100 msec, runs for 10 msec and
- Process B runs for 70 msec, blocks for 40 msec, runs for 20 msec, and
- Process C runs for 20 msec, blocks for 80 msec, runs for 60 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.
Time Running process Events
0-50 A B enters at time 10. C enters at time 20.
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.
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?
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.
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
Critical section of A Critical section of B
Is it possible for both processes to be in their critical sections
simultaneously? Explain your answer.
The two processes cannot be in their critical section simultaneously.
Suppose that A executes DOWN(S) before B does. B can only get to its
critical section after it executes DOWN(S). B can only proceed past
the execution of DOWN(S) after A has executed UP(S), which is not until
after A has completed its critical section.
Is it possible for the two
processes to deadlock? Explain your answer.
Answer: Yes. Suppose that A executes DOWN(S), is preempted,
and B executes DOWN(T). Then when A is continued, it will execute
DOWN(T) and block; when B is continued, it will execute DOWN(S) and block.
Neither can proceed until the other executes an UP, so they are deadlocked.