Spring 1989 Operating Systems Page 1 of 3 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. Monitors: 1A. In Mesa/Pilot, both monitor synchronization and process priority are supported. How would these two features interact? 1B. What are the advantages and disadvantages of concurrent pro- gramming using priorities? Breadth 2. File Locking: 2A. File servers often support locking functions. What problems can occur (related to locking) in a file server that would not occur in a local file system? 2B. What techniques can be used to deal with these problems? Feel free to use examples from existing systems. 2C. Support that you had a stateless file server (one that main- tained no state information between client requests). How would you support locking in such a system? Breadth 3. Mutual Exclusion: Discuss the following techniques for ensuring mutual exclusion. When would each of them be appropriate? 3A. An algorithm, such as the one attributed to Dekker, or Peterson's algorithm, that uses atomic reads and writes of shared memory. 3B. A busy-wait algorithm using a test-and-set instruction. 3C. Masking interrupts. 3D. Semaphores. 3E. Monitors. Breadth 4. Multiple File System Volumes: Each file in a given Unix file system volume has a unique inode number. A directory entry maps a file's human-readable name onto its inode number. However, different file system volumes use the same inode numbers, each volume starting with the number 1. This means that directory entries can not point outside their own volume, (there is a single exception that is used to glue multiple volumes together), and that utilities like mv and ln are res- tricted to operate within one file system volume at a time. 4A. How would you change file system data structures and adminis- trative procedures to remove this constraint on file naming and operations? 4B. Unix allows adding (mounting) and removing file system volumes at any time. Assuming you have removed the same-volume constraint, what file system integrity problems can be introduced by removing a volume, and how would you deal with it? Breadth 5. Memory Allocation: An operating system allocates physical memory by contiguous zones, starting at the beginning of memory, placing each zone next to the previous one, and without reusing hole (zones that have been released). When allocation becomes impossible, the whole memory is compacted, and the allocator starts at the beginning of memory again. Calculate the percentage of time taken for compaction, using the following definitions: M size of memory in words S mean size of a zone in words L mean lifetime of a zone T time to move (copy) a word of memory F mean fraction of unallocated memory This is the mean overhead of the system in equilibrium. Hint: In equilibrium, a zone is created every L time units (on average). Use this to deduce the time between two compaction operations. Breadth 6. Buffering: The amount of available buffering can have qualitative, as well as quantitative, consequences. Assume a single producer and a single consumer, and that they require mutually exclusive access to any given buffer. 6A. Describe the advantages of 2 buffers over 1 buffer; when they occur, and when they do not. 6B. Describe the advantages of 4 buffers over 2 buffers; when they occur, and when they do not. DEPTH QUESTIONS Depth 7. Capabilities: A capability-based system needs some way to prevent ordinary processes from accessing capabilities as arbitrary data. Briefly outline each of these three techniques, and discuss their relative merits: 7A. Flag each data word as capability or ordinary data. 7B. Group capabilities into special capability segments. 7C. Use encryption. Depth 8. Typed Messages: Most message-based operating systems support messages that are untyped byte streams. User code often has many lines of message packing and unpacking (which is tiresome to write and visually clutters the code). 8A. Support for typed messages can be placed in the language or the operating system (or in both). Discuss the trade-offs of where to put typed message features. 8B. How do heterogeneous architectures affect the design of a typed message system? Depth 9. Distributed Resources: Consider a distributed deadlock avoidance algorithm, similar to the Banker's Algorithm. At the beginning of a transaction, a pro- cess declares the list of resources it intends to use (this is a claim.) During a transaction, a process can only acquire a resource (by exclusive locking) if it appears in its claim. At the end of a transaction, all locked resources are freed. Define a relation delays between transactions, characterized by the following condition: Ti delays Tj == there exists a resource locked by Ti and claimed by Tj It should be obvious that the presence of a loop in the graph of the relation delays indicates the risk of a deadlock. We assume that resources are distributed over several sites, and that each site only knows claims concerning resources local to that site. A loop involving several sites can not be detected on any of these sites using local information alone. 9A. Assume a strict total order of transactions has been defined, by means of a relation > . Let the relation => be characterized by: Ti => Tj == (Ti delays Tj) or (Ti > Tj) Show that a global loop in the graph for the relation delays, must lead to a local loop, on at least one site, in the graph for the relation =>. Hint: In the global loop, consider the transaction T which is "greater than" all others (defined by >) and the transac- tion U which delays T. 9B. Deduce a deadlock prevention algorithm using only local information that avoids starvation. Hint: use time-stamps to implement the relation > . Depth 10. Datagram Fragmentation: When datagrams are transmitted through a series of networks con- nected by gateways, fragmentation is sometimes required. 10A. Why might it be necessary to fragment datagrams at gateways? 10B. Compare the relative merits of reassembling the datagrams at gateways versus doing the reassembly at the destination host.