Sample questions on the second part of the course
The final exam will take place on Thursday May 9, 2:00 - 3:50 in
room 703, Main Building. It will be closed book and closed notes.
It will be cumulative, covering material from the entire course, but
emphasizing more the material from the second half (since the first
half was already tested in the midterm.)
The following are some sample questions that might be asked about the
material in the second half of the course. This is NOT a sample exam;
the real exam will have some questions from the first half, and fewer
questions from the second half.
An OS uses the elevator algorithm to schedule the disk-arm. I/O requests are currently
pending for blocks on tracks 1, 3, 8, 11, 15, and 16. The disk arm is currently at
track 9 and moving upwards. In what order will these requests be handled?
An OS uses a paging system with 1Kbyte pages. A given process uses a virtual address
space of 128K and is assigned 16K of physical memory. How many entries does its
page table contain?
A user is typing input to a program at a keyboard,
and hits the following sequence of twelve keys:
`T', `h', `r', `e', `e', Delete key, Delete key, Delete key, `e', `r', `e',
If keyboard input is in raw mode, how many characters are passed to the user
What if it is in cooked mode?
Consider a file system that uses an FAT. The
state of the directory is
File name | First block | Size in bytes
AA 5 1350
BB 7 2200
(The other information in the directory is omitted.)
The current state of the FAT is
0 -- FREE
1 -- FREE
2 -- -1
3 -- 4
4 -- -1
5 -- 2
6 -- FREE
7 -- 3
8 -- FREE
The system uses a block size of 1 Kbyte.
What is the last block of file BB? How many bytes of that block are used?
(Useful fact: 1K=1024).
A particular system uses a page size of 1K bytes. A page table for a particular
process begins as follows: [ 3, 4, *, 1, *, 8 ...]
(Note: everything uses 0-based indexing.)
- A. What physical address corresponds to the virtual address of 50?
- B. Name a virtual address that will generate a page fault.
The linker, which converts an object file into an executable
file, has the task of choosing the placement of the code for different
subroutines. Ordinarily, subroutines are simply placed in order in
contiguous sections of virtual address space. However, linkers in a paging
take the alternative approach of placing subroutines so that each subroutine
lies within as few pages as possible.
For example, suppose that the page size is 1Kbyte, and the program contains
routines ``main'' of 750 bytes; ``a'' of 1000 bytes; ``b'' of 1200 bytes;
and ``c'' of 200 bytes. Ordinarily, the linker would place ``main'' in
bytes 0-749; ``a'' in 750-1749; ``b'' in 1750-2949; and ``c'' in 2950-3150.
However, a linker sensitive to paging might put ``main'' in 0-749; ``c''
in 750-950; ``a'' in 1024-2023; and ``b'' in 2048-3247. (Note: 1K = 1024;
2K = 2048; 3K = 3072.)
Name one advantage and one disadvantage of this placement scheme.
Problem 7: A user program has opened a file for reading and
been reading sequentially through the program for some while. It now
attempts to read the next byte, and finds that this byte belongs to
a new block, and that this block is not in memory. Describe the major
steps that are involved in the passage of control from the user program,
which wants to read the byte, to the disk, which must carry out the read,
and in the passage of information from the disk to the user program.
In particular, your answer should discuss the operations of
the device driver, the device-independent software, the actual disk, and the
disk controller, in both directions. You may assume that the program
is running on a single-process system. At any point, if there are different
options for implementation, you can pick one to describe; you need not
describe all the options.
In many operating systems, every process occupies a contiguous
section of core memory. There are few if any operating systems in which each
file occupies a contiguous section of disk. Give two reasons for this difference
between these two storage media.
What is the "Translation Lookahead Buffer" (TLB) and how is it used?
Consider a paging system that uses the "Not Recently Used" (NRU) page
- What is the significance of the "R bit" and the "M bit"?
- When are the R bit and M bit set and reset?
- How is a page chosen for replacement?