2000 Problem Set
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).