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.

Short problems

Problem 1:

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?

Problem 2:

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?

Problem 3:


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

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

Problem 5:

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.

Long Problems

Problem 6

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

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.

Problem 8

On CD-ROM, each file occupies a physically contiguous section of memory.

Problem 9

A. Explain in 1 or 2 sentences the difference between non-preemptive and preemptive scheduling.

B. Name one preemptive scheduling algorithm and one non-preemptive scheduling algorithm. (Just the names; you do not have to describe them.)

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.

Problem 10:

Consider a paging system that uses the "Not Recently Used" (NRU) page replacement algorithm.