Midterm

22C:116, Spring 2002

Douglas W. Jones

Please write your answers on the paper provided. Make sure your name is on the front page, in the same form as it appears in the official class list! Illegible and overly long answers are very difficult to grade. Please leave margins around your answers! This exam is open-book, open-notes, closed neighbor!

NOTE: Excessively long answers will be penalized. Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here! Stop and think before writing at any length!

This exam is worth 1/5 of the final grade (20 points; allocate 2 minutes per point).

  1. Background: Consider an operating system in which each user process has an independent virtual address space. The kernel of this system consists of a collection of interrupt and trap handlers, plus various support routines for those handlers; the kernel runs with the memory management unit turned off, while it must obviously be turned on whenever user code is running. Kernel services include tools for process creation and synchronization, input-output and all of the other functions you would expect in a typical commercial operating system.

    System calls such as read will block until any necessary input/output operations are done. While the system call is blocked, other user processes may execute.

    Part A: Some kernel code is only executed as part of the execution of user processes, while other kernel code never executes on behalf of a user process. Give an example of each. (2 points)

    Part B: There is a heap in the kernel's address space. Given examples of the kinds of objects the kernel might allocate on this heap. (2 points)

    Part C: The physical memory of the machine is divided into page frames. At any instant, some of these page frames are assigned to user address spaces and some of them are free. What page frames that are not assigned to any user address space yet are not free? (2 points)

    Part D: When the kernel's heap manager runs out of memory, what does it do to get more? As a result, does the kernel heap manager face any special problems that a user's heap manager would not face? Explain briefly. (2 points)

    Part E: A careless programmer forgets to deallocate objects on the heap that are no-longer needed. When the programmer fixes this, the program runs much faster. Why? (2 points)

  2. Background: Like most other operating systems, IBM's VM operating system offers a virtual machine to each user process. The difference between IBM's VM system and the vast majority of its competitors is that the virtual machine VM offers to a user process has identical semantics to the machine on which VM runs, except, of course, that it is a bit slower and has fewer resources. In order to offer this, VM relies on a memory management unit in order to virtualize memory, and it relies on the fact that a program's access to non-memory resources outside the CPU is through privileged instructions, such that attempts to use these in user mode cause a trap.

    On the physical machine, assume that IN and OUT are privileged instructions that transfer data between a designated CPU register and the designated device register. Assume that the MMU control registers are accessed this way. Assume an old-fashioned MMU that has an address-map-pointer register.

    Part A: A program running under VM tries to write a byte to the printer data register. VM has assigned an interprocess FIFO queue to that process as a virtual printer. Explain how VM goes about putting the user's byte in this queue. (2 points)

    Part B: A program running under VM does not write a byte to the printer data register until it has first checked the printer status register to see if the printer is ready for the next byte. VM has assigned an interprocess FIFO queue to that process as a virtual printer. What is the use of the printer-ready bit in the virtual printer status register for that process. (2 points)

    Part C: The program running under VM tries to turn on the MMU (by changing one bit in the MMU control register). What happens in the physical MMU? Hint: Was the physical MMU already turned on? If so, how does VM simulate the turning on or off of the virtual MMU? (2 points)

  3. Background: The original UNIX system had no user-accessible semaphore mechanisms; these were added as afterthoughts later in the development of UNIX. As a result, many of the older UNIX utilities use various kluges to achieve mutual exclusion. The most popular of these kluges is the lock-file. A lock-file is an empty file, the presence of which indicates that a process is in a critical section. On entry to a critical section, a process creates a lock file; to exit the critical section, the process deletes the lock file.

    In UNIX, the open() kernel call can create a file. Calling the open() service with the O_CREAT and O_EXCL flags causes open to create the file if it does not already exist and return an error indicator if it exists.

    A UNIX pipe is a FIFO queue with an interface that makes it look like a pair of open files. One of these is a write-only file that enqueues data in the pipe, the other is a read-only file that dequeues data from the pipe.

    Part A: Aside from file-system overhead (which is significant), what is the worst feature of this mutual exclusion mechanism, from the point of view of system performance, and how could you reduce the impact of this feature. (Hint: Try writing quick and dirty pseudocode for the lock operation used to enter a critical section.) (2 points)

    Part B: Given that all processes involved in some activity can read and write a particular pipe, we could use the pipe as a lock -- read one character from the pipe to enter the critical section, write a character to the pipe to exit. How is a user process blocked while it is waiting to enter the critical section? Compare this with your answer to part A. (2 points)