Operating Systems Instructions: For the BREADTH exam: Answer any 4 of questions 1-6. For the DEPTH exam: Answer any 4 of questions 1-6 and 3 of ques- tions 7-10. You are expected to spend about two hours on each half of the exam. BREADTH QUESTIONS Breadth 1. Virtual Memory: (1a) What parts of the Working Set (WS) page-replacement algorithm are expensive to implement? (1b) Compare WSClock with WS. How does WSClock get (nearly) the same benefits as WS? Why is it cheaper to implement? Breadth 2. Copy-on-Write Copy-on-write is a way for processes to share pages (or segments) that are logically distinct. When one process sends some data to a second process with copy semantics, nothing needs to be copied immediately, or perhaps ever. (2a) Explain how standard memory-management hardware can be used to implement copy-on-write cheaply. (2b) Describe how this method can be used to improve system per- formance for: (i) message passing, (ii) forking a new process, and (iii) file I/O operations. Breadth 3. Process Scheduling: In a demand paging system, it is discovered that a significant amount of processor time is lost while computations wait for slow peripherals. The scheduling algorithm is therefore modified as follows: When idle processor time has exceeded a certain limit, an additional computation is started. Comment on this proposal. Breadth 4. Monitors: The Mesa language has processes, monitors, and preemptive schedul- ing based on process priority. (The running process is always the ready process with the highest priority. Processes waiting to enter a monitor are not ready while the monitor is occupied.) Hardware interrupts are turned into signal operations on so-called naked condition variables (condition variables that can be sig- naled from outside the monitor). (4a) Explain how to write and install an interrupt handler in Mesa/Pilot. What operation inside a monitor should you use to dismiss (i.e., return from) an interrupt? (4b) A process inside a monitor has mutual exclusion until it per- forms a wait or signal operation. At that time, it may be preempted by a higher priority process. Therefore, a process must put monitor protected data into a clean state before it signals. Why isn't this sufficient in a Mesa monitor with a naked condition variable? Suggest a fix. Breadth 5. Process Synchronization: Operating systems provide a variety of system calls that synchron- ize processes with each other or with the operating system. These calls perform such primitive functions as o Test whether an event has occurred. o Wait until an event has occurred. o Authorize an event to occur. o Associate an interrupt handler with an event. o Delete an interrupt handler. o Prevent an even from causing an interrupt. o Allow an event to cause an interrupt. o Wait for a specified length of time. Usually, a system call performs several of these functions at once. For example, the standard Unix read system call authorizes an event (the transfer of data from a device or network connection to a buffer in the process' address space) and waits for the event to occur. (5a) Cite at least three other examples of system calls from any systems you know about (actual or proposed) that do more than one primitive synchronization function. In each case, indi- cate which functions are packaged together. (5b) Is there any reason to group these primitive functions together other than programming convenience? In other words, what would be wrong with providing these facilities in raw form and requiring the programmer to call each one separately (perhaps grouping them together in library routines)? (Hint: Consider race conditions.) Breadth 6. File Systems The Unix operating system associates with a file a set of bytes (the file contents) and a small set of attributes, including size, time of last modification, and others. (6a) Name at least three other properties that the Unix kernel associates with a file. (6b) Name at least two properties that Unix does not record, but which are supported by other operating systems. (6c) The MacIntosh HFS file system associates a so-called data fork with a file. The data fork is a property-list, which associates four-character property names with values. Cer- tain well-known property names are registered with Apple Com- puter, but new names can be added at any time. Outline how Unix filesystem organization would have to be changed to sup- port such a feature. DEPTH QUESTIONS Depth 7. Capabilities: (7a) Discuss the various ways a capability-based operating system can protect the integrity of capabilities and prevent processes from circumventing the protection they provide. To what extent do the different approaches allow processes to treat capabilities like ordinary data (store them in data structures, etc)? (7b) Capabilities tend to be quite a bit longer than memory addresses. Why? What sort of data has to be contained in a capability? (7c) The large size of capabilities can make them awkward to mani- pulate. For example, a multi-segment data structure can be traversed much more efficiently if pointers between segments are virtual addresses rather than capabilities. Discuss techniques to automatically convert between heavy-weight capabilities and a short internal representation. Depth 8. File Servers: Consider a file server that is serving many (hundreds or thousands) of client machines. Depending on the architecture of the system, it may or may not be important for the server to detect when a client crashes. (8a) Give an example of a design where it is important to detect a client crash. What causes the need to detect the crashes? How is this problem handled in some system (your choice) that you have read about? (8b) Same as part (8a), but give an example where detecting client crashes is not important. Explain why. In answering this question, consider such issues as the granular- ity of data transfer, idempotency, and immutability. Depth 9. Encryption in Networks: Where in the 7-layer OSI stack should data encryption go? The naive answer is at the presentation level, since it has to do with data format conversion. However, there are many good reasons for putting encryption at other layers of the stack. List as many layers as you can think of where encryption might go, and give arguments why it belongs in each one. Depth 10. Process Scheduling Any practical virtual memory management strategy must have some way of dealing with overcommitment, which occurs when the combined memory demand of all runnable processes exceeds available space. In such a situation, the scheduler must swap out some process. The choice of a victim process depends on such factors as process size, resources consumed, externally-supplied priority, and other considerations (suggest some). Discuss how these factors should be used by an algorithm to choose a process to be swapped out. Be sure to consider the overall goals of the operating system in which this algorithm is to be deployed. Specifically, how would your answer be different for a batch system, an interactive sys- tem, or a real-time system?