Final Exam: Comp. Sys. Org. II

Thursday, May 9, 2002

Short Problems

Short problems are worth 5 points each.

Problem 1

Match each term below with its definition. Note: There are two more definitions than terms, so two of the definitions are unused.

Terms:

Definitions:

Answer: A=u. B=w. C=y. D=x. E=v.

Problem 2

Let P and Q be processes and let s and t be semaphores. Initially, both s and t are 1. The two processes execute the steps shown below. Show a sequence of steps that leads to deadlock.
         P                                       Q
Step P1: DOWN(s)                       Step Q1: DOWN(s)
Step P2: DOWN(t)                       Step Q2: DOWN(t)
Step P3: Critical section PA           Step Q3: Critical section QA
Step P4: UP(s)                         Step S4: UP(t)
Step P5: DOWN(s)                       Step S5: UP(s)
Step P6: Critical section PB       
Step P7: UP(s)
Step P8: UP(t)

Answer: If the steps are executed in the order P1, P2, P3, P4, Q1, Q2, P5, then P is blocked waiting for Q to release s and Q is blocked waiting for P to release t, so there is a deadlock.

Problem 3

Suppose that the OS uses variable-length partitions for memory management. At some particular time, the running process occupies a partition between physical addresses 10,000 and 20,000.

Problem 4

What is a checksum and how is it used?

Answer: A checksum is the sum of the bits in a body of data. Checksums are used for error correction in reading from disks. The checksum for each block is stored together with the block, and is read in when the block is read. The checksum for the data as read is compared to the stored checksum. If an error has been made in reading the data, then with high probability the computed checksum will not be equal to the stored checksum.

Problem 5

Suppose that process P requested to read a block of a file from disk; that the read is completed while process Q is running; and that the disk controller issues an interrupt. Which of the following events occur in response to the interrupt, and which do not:

Answer: D, E, G occur; the rest do not.

Long Problems

Long problems are worth 15 points each.

Problem 6

Consider an OS that uses paging with a page size of 4K. There is a 32-bit virtual address space. At some particular moment, the page table for the currently running process holds the following sequence of frames: [2, -1, 3, 0, ...]. -1 is a flag that the page is not in memory. 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: 4K=4096. 2*4096=8192. 3*4096=12288.

Problem 7

In the above paging system, suppose that page 0 has R-bit=0 and M-bit=1.

Problem 8

Consider the following situation: There are three active processes: P, Q, and R. The OS is running a round robin scheduler with a time quantum of 10msec. Ignore the time for a context switch. Initially P is running and Q and R are on the ready queue in that order.

The disk driver uses the elevator algorithm, and is initially at track 0. The seek time is 5 msec per track. Assume that the rotational delay and the data transfer time are 0.

The three processes carry out the following operations:
P: Run a CPU burst of 15 msec, block for disk I/O at track 2, run a CPU burst of 15 msec, terminate.
Q: Run a CPU burst of 5 msec, block for disk I/O at track 8, run a CPU burst of 25 msec, terminate.
R: Run a CPU burst of 15 msec, block for disk I/O at track 11, run a CPU burst of 15 msec, terminate.

Trace the progress of the system. (Note: I have worked out the numbers so that no unrelated events ever occur simulataneously, and therefore there is no ambiguity in what happens. If, in your calculations, two events happen simultaneously --- for example, one process unblocks at the same time that another completes its quantum --- then (a) you have made a mistake and (b) you may resolve the ambiguity whichever way you choose.)

Answer:

Time 0-10. P is running. Q,R are ready.
Time 10-15. Q is running. Q blocks for I/O at time 15. 
Time 15-25. R is running. P is ready
Time 25-30. P is running. P blocks for I/O at time 30. 
Time 30-35. R is running. R blocks for I/O at time 35.
Time 35-55. Idle. Q's I/O request completes at time 55. Q unblocks.
  At this point there are outstanding disk requests for track 2 and track 11.
  The elevator algorithm continues moving upward to track 11.
Time 55-65. Q is running for one quantum.
Time 65-70. Q continues running.  R's I/O request completes at time 70. 
  R unblocks.
Time 70-75. Q completes its quantum.
Time 75-85. R is running.
Time 85-90. Q runs for 5 msec, then terminates.
Time 90-95. R runs for 5 msec, then terminates.
Time 95-115. Idle. P's I/O request completes at time 115.  P unblocks.
Time 115-130. P runs (through a quantum and a half) then terminates.

Problem 9

Suppose that the OS implements its files using i-nodes. Suppose file F is in directory D. Explain the organization of the data structures that lead from directory D to the first data block of file F.

Answer: The directory holds pairs of the name of the file together with the disk address of the i-node. After a preamble of file attributes, the i-node holds a sequence of disk addresses of the data blocks of F. The first of these is first data block of F.

Problem 10

What is swapping? Why is it used in systems with variable-length partitions?

Answer: In swapping, a process is entirely removed from main memory and its state is stored on disk. Swapping is used in an OS that uses variable-length partitions in the case there are active processes that are ready to run but do not fit into any free segment of main memory (either because the total memory requirements of the active processes is too large, or because space has been wasted in external fragmentation.)