Stanford Operating Systems Quals

2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

2000 Problem Set

The objective of the exam is to find out what you know about operating systems and to assess your ability to identify and develop solutions for problems that arise in operating systems. Note that the questions may have many "right" answers so be sure to justify your answers. In particular, state any assumptions you make. Point form answers are acceptable. Grammar optional. Problem 1 -- Fascist vs Happy-go-lucky Resource Allocation (10 Points) Resources can either be allocated in fixed portions (I get 10% of disk, you get 90%) or on demand in response to need, e.g., senders on Ethernet transmit henever the link is idle rather than at fixed times. Compare and contrast these two approaches, giving several advantages and disadvantages of each, as well as two concrete situations where you would (sensibly) prefer one over the other (and why). Problem 2 -- Stacks-R-Fun (15 Points) Assume you are building a user-level threads system that manages multiple threads in the same address space. Each thread has its own stack. For ease of use, you want your system to transparently grow thread stacks dynamically.

1. (10 Points) Please give a high level sketch of what virtual memory support the OS should provide so that you can (1) detect when a thread's stack has been exceeded and (2) grow the thread's stack. (And, of course, how you'd use this functionality to do these two acts). Additionally, please briefly discuss the tradeoffs around where you decide to place thread stacks in virtual memory.

2. (5 Points) What do you have to be prepared to do to dynamically grow a thread's stack. What complication does taking the address of a stack variable create? How can you fix this in the virtual memory system.
Problem 3 -- Speed! Speed! Speed! (15 Points) Most operating systems allow files to be accessed either with raw file read and write operations or with memory mapping.

1. (5 Points) State what artificial limitations both interfaces place on the performance of the copy. What similar limitation shows up in reliable network protocols like TCP?

2. (10 Points) Sketch an interface specialized to allowing applications such as Unix "cp" to craft their own blindingly fast file copy. Eliminate as many OS overheads as possible.
Problem 4 -- Consistency is the Hobglobin of the Successful (20 Points) You want to atomically update a file "my-enemies-list.txt". Unfortunately, you know from bitter experience that there exists little purple men that can crash your machine (otherwise, why would you need this file?).

1. (4 Points) What will happen if you crash while writing the file out? For typical disks, are there any interesting special cases whre you will be okay?

2. (16 Points) Explain how you can synthesize an atomic update using only (1) your file system's ability to (non-atomically) create, delete, and copy files and (2) the "sync" system call which returns after writing out all dirty blocks to disk (in any order). Try to minimize the operations you do (but keep it simple), making sure to describe how to recover from a crash. Please state any assumptions you are making about how the file system lays out directories. (As a completeness hint: remember that a crash can happen any time).

Maintained by Gurmeet Singh Manku