Final Exam: Comp. Sys. Org. II
Thursday, May 9, 2002
Short problems are worth 5 points each.
Match each term below with its definition. Note: There
are two more definitions than terms, so two of the definitions
- A. Quantum
- B. Response time
- C. Rotational latency
- D. Seek time
- E. Turnaround time
- t. Delay between the time that a process blocks and the time that it
- 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.
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.
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.
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?
Answer: An error is raised.
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.
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
- 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 are worth 15 points each.
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.
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.
Let V be the virtual address.
Conceptually, the physical address is computed as follows:
1) offset = V % pagesize;
2) pagenumber = V / pagesize;
3) framenumber = pagetable[pagenumber]
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
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.
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
- 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.
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
no unrelated events ever occur simulataneously, and therefore there is no
ambiguity in what happens. If, in your calculations, two events
--- 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
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.
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.
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.
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.
What is swapping? Why is it used in systems with variable-length
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.)