Solutions to sample questions
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?
Answer: 11, 15, 16, 8, 3, 1
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?
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).
The blocks of BB are 7, 3, 4. Since BB has length 2200 and blocks 7 and 3
hold 2048 bytes, there are 152 bytes used in block 4.
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.
A. 3*1024+50 = 3122.
B. Any virtual address between 2048 and 3071 or between 4096 and 5119.
Consider a Web browser and Web server that are communicating in HTTP layered
over TCP layered over IP. For each of the following functionalities,
state whether it is (i) implemented at the level of HTTP (ii) implemented
at the level of TCP, (iii) implemented at the level of IP; (iv) carried
out by the DNS; or (v) none of the above.
- A. Forwarding packets from one router to another. Answer: IP.
- B. Requesting retransmittal of a packet whose data is garbled.
- C. Maintaining a cache of web pages. Answer: HTTP.
- D. Assembling and disassembling a large file into packets.
- E. Translating URL's into IP addresses. Answer: DNS.
- F. Assembling the HTML file and the imbedded images into a display.
Answer: none of the above (it's up to the browser.)
What is swapping? Why is it used in systems with variable-length
partitions? Why is it used in systems with paging?
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.)
In an OS that uses pages, swapping may be used when the sum of the working
set sizes for the processes currently in memory is greater than the size
of physical memory. When this happens, thrashing -- frequent page faults --
is almost inevitable, as the processes are competing for a resource (frames)
that is inadequate to their combined needs. The only solution in such
a case is to swap out (suspend) one or more of the processes.
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.
Answer: (Note: this is a lot more detail than I would
expect on an exam answer. Also, the exact steps and the division of
the steps among components of the system can vary a lot from one
system to another.)
The device-independent software passes to the device driver the number of
bytes to be read, the address in user space to read them into, and
the file pointer. It then traps to the kernel. The kernel blocks the process
and calls the device driver from the top. The device
driver determines that the next byte is on a block B not in memory. It
finds the address of B from the i-node (presumably in memory). It issues
a request to the device controller to read B into memory. The device
controller translate the block number of B into a set of consecutive
sectors on a track, and instructs the actual disk to read those sectors.
The disk moves the arm to the correct track, waits for the disk to rotate
to the proper sectors, and reads the information, putting the output
into the disk controller's buffer. The disk controller issues a
interrupt. The interrupt handler in the kernel sends control to the
bottom of the disk driver. The disk driver transfers the block of data from
the disk contoller's buffer to the file cache, and transfers the
byte of data to the specified address in user space. The kernel
unblocks the process and schedules it to run. The device-independent
software finds its data where it expects, and returns control to
the user process.
On CD-ROM, each file occupies a physically contiguous section of memory.
- A. Name two advantages of this arrangement over the use of i-nodes.
- B. Name two reasons that this system is not used on hard disks.
- A. First, it minimizes seek time. If a file is read sequentially
(the usual case) then seek time is kept to an absolute minimum. Even if
the file is read out of sequence, with contiguous storage, the blocks of
the file are at least all in the same part of the disk whereas with
non-contiguous storage they are (in general) scattered randomly around the
Second, it requires less space, because the i-node need not be kept.
An i-node based system generally requires an extra block for the i-node;
if there are a lot of small files, this is a substantial cost.
- B. Contiguous storage can only be used for files that are unchanging.
If a file is expanded, then it will no longer fit into its place, and,
at best, has to be copied in its entirety to some other part of the disk,
leaving a large hole. If a file is deleted or reduced in size, then
a hole opens up in memory. Unless this hole happens to be filled exactly,
you end up with wasted space due to external fragmentation.
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.)
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.
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?
The R bit is 1 if the page has been referenced since the last clock tick.
The M bit is 1 if the page has been modified since it was read in.
At each machine instruction, the R bit for any page of any virtual address
referenced is set to 1. The M bit is set to 1 if the process writes
to that page. The R bit is reset to 0 at each clock tick. The M bit is
reset to 0 when the page is written out to disk. In the NRU algorithm,
pages are divided into 4 categories:
A page is chosen for replacement from the lowest of these categories.
If there is more than one page in that categories, one is chosen at
- 1. R=M=0.
- 2. R=0, M=1.
- 3. R=1, M=0.
- 4. R=M=1.