Midterm

22C:116, Fall 2001

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: 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: In the ExamOS operating system (invented for this exam), each process has its own demand-paged address space, most of which is available for unrestricted use by the application. To transfer control to a kernel function, an application program executes a function call to an address in a page reserved for the kernel interface; the specific address in that page determines which kernel function is called.

   Part A: Which trap service routine dispatches kernel calls. (1 point)

   Part B: What other traps does this service routine handle. (1 point)

   Part C: How does this service routine distinguish between kernel calls and the other traps it handles. (1.5 points)

   Part D: How does the kernel-call trap service routine return. Hint: It does not simply do a return-from-trap, as is done on return from a page-fault-trap; the saved program counter is wrong! (2 points)

2. Background: The UNIX shell command "rmdir x" performs a sequence of unlink operations to remove a directory named x from the UNIX tree-structured directory hierarchy. This command is only legal if x is an empty directory. Recall that each UNIX directory contains links named .. (parent) and . (self).

   Part A: Give these unlink operations in the correct order. (1.5 points)

   Part B: What actually causes the reclamation of the storage space occupied by the directory x? (1.5 points)

3. Background: When Bell Labs released System V UNIX, they added an interesting afterthought the lockf() system service:

   lockf(fd, ... ,size)

   manipulate mutual exclusion locks on a range of bytes within the file fd. The range begins at the current position in the file, and the range includes size bytes of the file.

   lockf(... ,F_LOCK, ...)

   Block the caller until no byte in the indicated range is locked, and then lock all bytes in the indicated range. If the caller has previously locked some bytes in the range, this service will wait for and claim locks on the remaining bytes in the range.

   lockf(... ,F_ULOCK, ...)

   Unlock the caller's locks on the indicated range. Closing a file also unlocks all of the caller's locks on that file.

   Conceptually, the lock function is atomic; it either locks all the bytes not previously claimed by the caller in the range, or it locks none of them. Aside from this, the semantics of locks are as if there was a semaphore associated with each byte of the file!

   Part A: What deadlock model is applicable to interprocess communication using this service? (The notes for lecture 8 covered this subject best.) (1.5 points)

   Part B: Some kind of lock data structure must be attached to files. Where does this go? (For example, is it attached to the data sectors on disk? Is it part of the process's table of open files? If not, where does it go?) (2 points)

   Part C: The conceptual model suggested in the background is not an appropriate implementation. Suggest an appropriate lock data structure. (2 points)

4. Background: The mmap() kernel service maps the contents of a file to a range of virtual addresses, very much in the spirit of the "make virtual" service of the homework assignment and the third study question for this exam. This was another afterthought added to the System V UNIX.

   Given this and flock() as defined in the previous problem, consider the problem of implementing message passing interprocess communication, where messages are addressed to individual processes. Note that the getpid() kernel call allows a process to find its own process ID, and the fork() kernel call returns the process ID of a newly created process. These process ID's can be used, for example, to do things like creating a unique file name per process.

   Part A Suggest a representation, at a coarse level of detail, for an bounded buffer implementation of an interprocess message passing communication channel. (2 points)

   Part B Given the process ID of the receiving process, outline at a coarse level of detail how a process can send a message to the recipient. (2 points)

   Part C Something is missing in the set of primitives that have been given. What? To find the answer, consider how a process awaits a message in the channel you have built. (2 points)