## Mid-Term Exam

March 9, 2004

### Problem 1: (15 points)

Suppose that a system is running a round-robin scheduler. At some particular time, the running process P is preempted and Q is chosen to run instead. Which of the following events occurs, and in what order?
• A. The clock issues an interrupt.
• B. The operating system jumps to the interrupt handler.
• C. Process P blocks.
• D. Process Q unblocks.
• E. Process P is saved on disk.
• F. The registers for P are saved in the process table.
• G. The scheduler is run to choose a new process.
• H. The system switches to kernel mode.
• I. The system switches to user mode.

Answer: A, H, B, G, F, I occur in that order. (The order of G and F could be reversed.) C, D, and E do not occur.

### Problem 2: (25 points)

Suppose that there are three processes, P, Q, and R, with the following characteristics:
P will run for 60 msec, block for 70 msec, run for 10 msec, and terminate.
Q will run for 20 msec, block for 40 msec, run for 30 msec, and terminate.
R will run for 110 msec and terminate.
P enters the system at time 0, Q enters at time 15, and R enters at time 40.

Trace what happens (A) with a first-come first-served scheduler; (B) with a round-robin scheduler using a 50 msec quantum.

First-come first-served scheduler
Time Running process Ready queue Event at end
0-15 P empty Q enters.
15-40 P {Q} R enters.
40-60 P {Q,R} P blocks until 130
60-80 Q {R} Q blocks until 120
80-120 R empty Q unblocks
120-130 R {Q} P unblocks
130-190 R {Q,P} R terminates
190-220 Q {P} Q terminates
220-230 P empty P terminates

Round robin scheduler.
Time Running process Ready queue Event at end
0-15 P empty Q enters.
15-40 P {Q} R enters.
40-50 P {Q,R} P is preempted for Q.
50-70 Q {R,P} Q blocks until 110.
70-110 R {P} Q unblocks
110-120 R {P,Q} R is preempted for P
120-130 P {Q,R} P blocks until 200.
130-160 Q {R} Q terminates.
160-200 R empty P unblocks.
200-210 R {P} R is preempted for P.
210-220 P {R} P terminates
220-230 R empty R terminates

### Problem 3: (10 points)

Consider a system with two semaphors, X and Y, and three processes, P, Q and R. The processes execute the following code:
Process P              Process Q             Process R.
DOWN(X)                Q.1                   DOWN(X)
P.1                  DOWN(Y)                 R.1
DOWN(Y)                Q.2                   UP(X)
P.2                  DOWN(X)
UP(X)                  Q.3
P.3                  UP(X)
UP(Y)                 UP(Y)
Initially X=Y=1.
• A. Give a sequence of steps that ends with all three processes being deadlocked.

P: DOWN(X)          X=0
P: P.1
Q: Q.1
Q: DOWN(Y)          Y=0
Q: Q.2
Q: DOWN(X)          Q blocks
P: DOWN(Y)          P blocks
R: DOWN(X)          R blocks.

• B. Is it possible for P.1 and Q.2 to run concurrently?
Answer: Yes. They do in the above sequence.
• C. Is it possible for P.2 and Q.3 to run concurrently?
Answer: No. Mutual exclusion is enforced by both semaphors X and Y.
• D. Is it possible for P.3 and R.1 to run concurrently?
Answer: Yes. P can execute its code down to step P.3, and then since X will be 1, R can execute DOWN(X) and R.1.

### Problem 4: (10 points)

A programmer is trying to convert single-threaded code into multiple-threaded code in an open-source OS with no built-in support for threads. He has the choice of implementing his threads at the user level or at the kernel level. Mark each of the following considerations true or false.
• Transfer of control between threads can be done more efficiently using a kernel call than at the user level.
False.
• It is desirable to allow one thread of a process to block while another thread of the same process continues running. This is easier to achieve at the kernel level than at the user level.
True.
• Modifying the kernel is generally easier work than writing user-level code.
False.
• It may be desirable to allow different types of processes to use different types of scheduling among their threads. This is easier to achieve at the kernel level than at the user level.
False.
• A kernel-level thread scheduler can choose from among all threads of all processes, whereas a user-level thread scheduler can only choose from among threads of the currently running process.
True.

### Problem 5: (10 points)

In order for a deadlock of processes on resources to occur, four conditions, known as Coffman's conditions, must be met. Which of the following are among Coffman's conditions (the list below does not necessarily include all of Coffman's conditions:)
• A. Busy wait.
• B. Circular wait.
• C. External fragmentation.
• D. Hold and wait.
• E. Interrupts.
• F. Resources that cannot be preempted.
• G. Processes that cannot be preempted.
• H. Semaphors.

Answer: B, D, and F are among Coffman's conditions.

### Problem 6: (10 points)

A paging system uses pages of size 1KByte. At some particular time, the page table begins as follows: [3, *, 0, 4, 2, * ...]. (* means that the page is not in memory.) The (very small) TLB is
Page number Frame number
2 0
3 4
For each of the following virtual addresses, state whether the memory translation involves a TLB hit, a page table lookup, or a page fault, and what, if anything, is the corresponding physical address.
(Note: 2*1024-2048. 3*1024=3072. 4*1024=4096. 5*1025=5120.)

### Problem 7: (5 points)

The advantage to using a multi-level page table as opposed to a single level page table is that
• A. It allows fewer process pages to be kept in memory.
• B. It allows less of the page table to be kept in memory.
• C. It makes it easier to find a free frame.
• D. It reduces the number of page faults.
• E. It speeds up address translation.

### Problem 8: (15 points)

Suppose an operating system uses paging. At some particular time, pages 0-4 of a given process P are in memory and are clean. The following events then occur:
• 1. P writes to page 3.
• 2. P writes to page 2.
• 3. P reads from page 4.
• 4. There is a clock tick that resets all R bits.
• 5. P writes to page 1.
• 6. P reads from page 2.
• 7. P reads from page 0.
• 8. P page faults trying to write to page 5.
• A. Suppose that the system uses the NRU (not recently used) page replacement algorithm. What are the N and R bits for pages 0-4? What page is chosen for replacement?