## 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:

• A. Quantum
• B. Response time
• C. Rotational latency
• D. Seek time
• E. Turnaround time

Definitions:

• t. Delay between the time that a process blocks and the time that it unblocks.
• u. Maximum time a process may run before being preempted.
• v. Time between the submission and completion of a process.
• w. Time for a user to get a reaction to his/her input.
• x. Time for the disk arm to move to the desired cylinder
• y. Time for the disk to rotate to the desired sector.
• z. Time required to switch from one running process to another.

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.
• A. What are the values of the base and limit registers?
Answer: Base register = 10,000. Limit register = 10,000.
• B. What physical address corresponds to a virtual address of 3,000?
• C. What happens if the process refers to a virtual address of 15,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:
• A. Process Q blocks.
• B. Process Q unblocks.
• C. Process P blocks.
• D. Process P unblocks.
• E. The value of the program counter at the time of the interrupt is saved by hardware.
• F. The value of the program counter at the time of the interrupt is saved by an assembly language procedure.
• G. Data is transferred from the disk controller's buffer to main memory.
• H. Data is transferred from main memory to the disk controller's buffer.
• I. The R-bit is set.
• J. The i-node for the file is updated and written to disk.

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.
• A. For each of the following virtual addresses, state whether they are in memory, and, if so, give the corresponding physical address: 50, 5000, 10000.
Answer: 50 => 8242. 5000 is not in memory and gives a page fault. 10000 => 14096.
• B. The hardware that carries out the address translation does not need to invoke the arithmetic logic unit to carry out an integer divide, an integer multiply, or an integer addition. Explain how the physical address can be computed from the virtual address without using these operations.
```1) offset = V % pagesize;
2) pagenumber = V / pagesize;
4) physical = framenumber*pagesize + offset
```
Since the page size is 4K = 212, we can carry out the above steps as follows:
```1) offset = mask out all but the last 12 bits of virtual.
2) pagenumber = bitshift V right 12
3) unchanged.
4) bitshift framenumber left 12 places and do a bitwise OR with offset.
```
• C. What is a translation lookaside buffer (TLB)? What information does it hold? How is it used in address translation?
Answer: The TLB is an associative memory chache built in very fast memory. It holds pairs of the form < page#, frame# >. Given a page number, the TLB can find the associated frame number much more quickly than would be required to look up the pagetable, which reside in main memory.

### Problem 7

In the above paging system, suppose that page 0 has R-bit=0 and M-bit=1.
• A. What do these values imply about previous events in the process and the OS?
Answer: Page 0 has modified since it was read in, but has not been referenced since the last clock tick.
• B. If page 2 has R-bit=1 and M-bit=0, which is considered the better candidate for replacement in an NRU page replacement algorithm: page 0 or page 2?
Answer: Page 0. The R-bit is more important than the M-bit.
• C. Explain why the M-bit is considered significant in choosing a page for replacement.
Answer: If the M-bit is 1 --- that is, the page has been modified --- then two I/O operations are required to replace it; the old page must be written out to disk and the new page must be read in. If the M-bit is 0, then the old page need not be written out to disk; the current copy on disk is valid. Therefore, the PRA prefers to replace pages for which the M-bit is 0.

### 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.)

```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.)