Midterm Study Questions

22C:116, Fall 2001

1. Background: Consider a machine with a supervisor state and a user state, where all dangerous operations can only be performed in supervisor state. Attempting to perform such an operation in user state will cause a trap. This machine also has a memory management unit that supports paged address translation; an attempt is made to access a page that is currently not mapped to a physical memory address will cause a trap.

   Note that under many operating systems, including UNIX, some processes running under the kernel are allowed to execute dangerous operations. This allows certain essential system functions to be handled by code outside the kernel. These processes must be allowed to run in supervisor state.

   Things to think about: Think about all the possible ways to implement calls to kernel services on this machine. Two different traps were mentioned. Think about how each of these traps could be used to transfer control to the kernel.

   Which kernel-call model allows kernel calls to be coded identically in processes that run in user state and in supervisor statep, and why must kernel calls be coded differently under the other model?

2. Background: The UNIX file system is basically tree-structured, but it has self-links and up-links added to the tree structure. Consider the alternative of a completely unconstrained graph-structured file system, where each directory is allowed to contain links to arbitrary files or directories. If a user wants to use this as a tree structured file system, the user would be free to do so (most users probably would!) but there would be no limit on the linking of files into other more general graph structures if the users wanted to do so. (The Cambridge CAP distributed file system did this!)

   One reason for the tree constraint in UNIX is that it allows straightforward detection of the fact that a file is no longer accessible. With each UNIX file, the system maintains a count of the number of links to that file from various directories. When this count reaches zero, the space occupied by the file can be reclaimed. The UNIX unlink() kernel cal (and the rm shell command) handles this.

   Things to think about: Why does the reference-count scheme used by UNIX, in conjunction with the self-links require that a special privileged rmdir utility (a shell command) be used to delete directories, and why is it illegal to use unlink() or rm to delete a link to a directory?

   What problem must the CAP file system have solved in order to allow users to construct arbitrarily tangled graphs of links between directories? (Hing: The Java language raises exactly the same problem with regard to objects in the heap!)

3. Background: Consider the problem of interprocess communication in a system with one virtual address space per process, where opening a disk file simply inserts the sectors of that file into a range of virtual addresses in the address space of the process that opened the file.

   Things to think about: What interprocess communication problems does this mechanism solve, and what problems does it leave to the user to solve?

   Suppose you, as a user, wanted a message passing model for interprocess communication, where each message was addressed to a particular process; how would you implement this?

   Suppose you, as a user, wanted to use UNIX style pipes for interprocess communication, where each pipe could have multiple producers and multiple consumers; how would you implement this?