Homework 4

22C:116, Spring 1997

Due Friday Feb. 21, 1997, in class

Douglas W. Jones

Per Brinch Hansen introduced an interesting idea in his RC4000 operating system (see his 1973 OS textbook). Instead of having interrupt routines do any work, all useful work was done in high-priority processes scheduled with the normal system scheduler. All interrupt service routines on the RC4000 did the following, and nothing more:

	interrupt service routine for device X:
		disable device X's interrupt request
		signal device X's semaphore
Typically, a device service process would await a signal to device X's semaphore and do the actual work; when this process wanted to allow device X to produce another interrupt, it would re-enable interrupts from device X.

  1. Brinch Hansen's system did not handle virtual memory, and so, all fault handlers could simply abort the offending process.

    Problem, part A: Propose a way to shift the burden of page fault service from the page-fault handler to a page fault service process, basing your solution on something akin to Brinch Hansen's model for interrupt service. This would allow a fault handler to interact with the disk handler and disk scheduler in the same way as user programs. Assume initially that there is only one user process that may cause page faults.

    Problem, part B: What is the easiest way you can find to allow your solution to part A to be generalized to allow multiple user processes, where one process may generate a page fault while the faults caused by other processes are still being handled.

  2. Consider the problem of handling a slow network data link where the arrival of each byte of data causes a separate interrupt, but bytes are organized into fixed size blocks where each block ends with an error correcting code (an ornate checksum allowing errors to not only be detected but usually also allows error correction). Higher level software posts requests to read blocks from the data link, where these requests resemble the requests posted in a disk interrupt queue; each request identifies a data buffer, a semaphore to be signalled when the buffer is filled, and a place to put a status report indicating whether the data in the buffer contains uncorrected errors.

    The problem: Outline, at a reasonable level of detail, the structure of the communications line input interrupt service routine needed for this system.

  3. The emphasis in both the lecture and in Brinch Hansen's discussion of disk scheduling (see section 5.3) is on what order to visit the different cylinders of the disk drive.

    The problem: Discuss the impact of order of service on total service time for pending I/O requests all in the same cylinder. Does this depend on whether the access requests are for whole tracks or for individual sectors? Propose an appropriate scheduling algorithms for dealing with the pending I/O requests in one cylinder.

  4. The problem: Discuss the performance differences you would expect between use of a RAM disk (see Tannenbaum's section 5.3.5) and the use of the request queue as a cache discussed in the lecture notes (lecture 11). Under what circumstances would they offer comparable performance. Under what circumstances would they differ, and why.