Make-up Final Exam: Comp. Sys. Org. II

Friday, May 10, 2002

Short Problems

Short problems are worth 5 points each.

Problem 1

Suppose we are implementing a uniprocess OS. There is only one active process at a time; no new process can be started until the last one has terminated. Of the following issues and techniques, which might still be useful, and which are entirely irrelevant: (You need not explain your answer.)

Answer: D, F, and G are relevant; A, B, C, and E are relevant only where there are multiple processes.

Problem 2

What is the difference between an absolute path name and a relative path name for a file? How is the absolute path name computed from the relative path name?

Answer: An absolute path name shows the path of directories from the root to the file. A relative path name shows the path of directories from the current working directory to the file. The absolute path name can be computed by appending the relative path name onto the path of the working directory.

Problem 3

Give an example to show how the "shortest seek first" algorithm for disk arm scheduling can lead to starvation.

Answer: Suppose that initially the disk head is at cylinder 1, and there are requests for 1 and 100. Suppose that a constant stream of requests for blocks in cylinders between 1 and 10 arrive, each one arriving before the last one has been completed. Then shortest seek first algorithm will always send the disk arm to the request between 1 and 10, and the request at 100 will never be served.

Problem 4

In disk backups, what is the difference between a physical dump and a logical dump ? Answer: In a physical dump, the disk is read in physical order, starting on the first track and ending at the last. In a logical dump, the dumping procedure does a systematic search through the directory structure.

Problem 5

Consider an OS that uses paging with a page size of 2K. At some particular moment, the page table for the currently running process holds the following sequence of frames: [-1, 2, 0, 3, ...]. -1 is a flag that the page is not in memory. For each of the following virtual addresses, state whether they are in memory, and, if so, give the corresponding physical address: 50, 2100, 5000, 6150.

(Note: this is an ordinary page table, NOT the inverted page table we used in Lab 3. All indexing is 0-based. Some useful values: 2K=2048, 4K=4096, 6K=6144.)

Answer: 50 is not in memory. 2100 => 4148. 5000 => 904. 6150 => 6150.

Long Problems

Long problems are worth 15 points each.

Problem 6

Consider an OS that is doing paging using the NRU page replacement algorithm. Suppose that there is memory contains five frames. At a certain stage, pages 1, 2, 3, 4, and 5 are in memory, and all R-bits and M-bits are 0. The following events then occur:
Time     Event
1:    Write to page 1.
2:    Read from page 2.
3:    Write to page 3.
4:    Read from page 4.
5:    Write to page 6.
6:    TICK (reset R-bits)
7:    Write to page 2
8:    Read from page 7.
9:    Read from page 5.
10:   Read from page 3.
11:   Write to page 8.
12:   TICK (reset R-bits)
13:   Read from page 4.
List all the page faults that occur, and state which page is chosen for replacement. If there is a tie in the page replacement algorithm, you may choose any one arbitrarily. On your answer, you do NOT have to list the values of the R-bits and M-bits over time.

Answer: Any of the following answers is correct:

Answer 1:
At time 5, fault; replace page 5.
At time 8, fault; replace page 4.
At time 9, fault; replace page 6.
At time 11, fault; replace page 1.
At time 13, fault; replace either page 5 or page 7

Answer 2:
At time 5, fault; replace page 5.
At time 8, fault; replace page 4.
At time 9, fault; replace page 3.
At time 10, fault; replace page 1.
At time 11, fault; replace page 6.
At time 13, fault; replace page either 3, 5, or 7.

Answer 3:
At time 5, fault; replace page 5.
At time 8, fault; replace page 4.
At time 9, fault; replace page 3.
At time 10, fault; replace page 6.
At time 11, fault; replace page 1.
At time 13, fault; replace page either 3, 5, or 7.

Answer 1:
At time 5, fault; replace page 5.
At time 8, fault; replace page 4.
At time 9, fault; replace page 6.
At time 11, fault; replace page 1.
At time 13, fault; replace either page 5 or page 7

Problem 7

A. The disk drive is rarely, if ever, a resource involved in a deadlock. Why not?

Answer: The disk drive is preemptable. If two processes wish to use the disk drive, they can take turns. If one process has been using the disk drive and is then blocked, there's no reason that the

B. If two processes P and Q both wish to write to file F, it is generally necessary to enforce mutual exclusion on these two writes. If two processes P and Q both wish to read from file F, it is not generally necessary to enforce mutual exclusion on these two reads. Explain the difference.

Answer: If process P makes one set of modifications to some of F's blocks and process Q makes other modifications to other of F's blocks, then the net result may be inconsistent garbage, reflecting neither P's nor Q's intentions. By contrast, having two processes reading F does not create any inconsistency.

C. If two processes P and Q both wish to write to two files F and G, a deadlock may occur. Explain how this can happen.

Answer: Suppose that P opens F and Q opens G. Now P wishes to write to G as well, but must wait for Q to close G in order to achieve the mutual exclusion described above. Q wishes to write to F, but must wait for P to close F for the same reason. Thus there is a deadlock.

Problem 8

A. A process may page fault twice for a single instruction. Explain.
Answer: The simplest scenario is that the instruction itself is on a page that is not in memory, and that it references a memory address that is on a different page, also not in memory. There are also other, more outre possibilities: Some instructions in some assembly languages have references to two memory addresses. In some systems, an instruction and a memory location can cross a page boundary. Thus, in an extreme case, there could be up to six page faults in a single instruction.

B. A page fault generally gives rise to at least two traps to the kernel; (A) one at the time of the page fault, and (B) one when the input of the new page has completed. For each of the following events, state whether it occurs during trap A, during trap B, or both. (You need not explain your answer; just give a list of the form "i at A; ii at B; iii at A and B;" etc.)

Let Q be the process that has generated the page fault.

Answer: i at A; ii at B; iii at A; iv at A and B; v certainly at A, optionally at B as well; vi at A.

Problem 9

A. Explain in 1 or 2 sentences the difference between non-preemptive and preemptive scheduling.
Answer: In a non-preemptive scheduler, a process stops running only when it blocks; it never transitions from "running" to "ready". In a preemptive scheduler, the scheduler may preempt a running process and put it on the ready queue,

B. Name one preemptive scheduling algorithm and one non-preemptive scheduling algorithm. (Just the names; you do not have to describe them.)
Answer: Of the scheduling algorithms we have discussed, shortest remaining time first, round robin, selfish round robin are preemptive; first come first served and shortest job first are non-preemptive.

C. Even if all jobs are CPU-bound, a preemptive scheduler may give a better average turnaround time than a non-preemptive scheduler. Give an example that illustrates this.
Answer: Suppose that process P, with one CPU burst of 100 sec, enters at time 0, and the process Q, with one CPU burst of 1 sec, enters at time 1. Then a non-preemptive scheduler will run first P from time 0-100 and then process Q from time 100-101 for an average turnaound time of 100. By contrast, assuming a small quantum and ignoring time lost to context switches, a preemptive scheduler will complete process Q at time 3 and process P at time 101, for an average turnaround time of 52.

Problem 10

On CD-ROM, each file occupies a physically contiguous section of memory.