Operating Systems Depth Exam

	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
Operating Systems Depth Exam		Spring 2004

Instructions: There are seven questions on this exam; answer any six of the following questions.

Question 1. Kernels and Security:

The Xerox Pilot operating system design was based on the premise that it implemented protection and security to deal with accidental, not malicious, violations. As an operating system for a single user, desktop machine, it was thought that security could be enforced, logically, at the network and not inside the kernel.

Does this argument make sense for current desktop machines? Describe your reasons why or why not and justify each one.

Question 2. Internet Architecture:

Internet today is a world wide infrastructure consisting of thousands of autonomous networks and millions of end hosts. Since its inception, Internet development has been driven by dynamic market forces that have often left both the network operations and network research communities scrambling to catch up.

List three basic tenants of Internet architecture that enable it to accommodate both dramatic growth and extreme diversity (from the perspectives of systems and applications). Briefly justify each answer.
List three significant weaknesses in today's Internet that have the potential to limit future growth and diversity. Briefly justify each answer.

Question 3. Inferring Resources and OS Properties:

You have been given a user account on a remote machine to which you are porting some "high performance application". All you know about this machine is that it supports the posix interface; you have no useful documentation, no one is answering your e-mail about the machine, and any interfaces you know of for acquiring information about the machine appear to be broken.

To obtain reasonable performance for your application, you believe that it would be useful to know the following properties about the machine or OS:

Number of CPUs
Page size (in bytes)
Amount of physical memory (in bytes)
How memory is allocated between the virtual memory system and the file cache; specifically, is a fixed amount of memory given to each or does the amount vary?

For each property, give a brief but precise description of a benchmark program you develop that allows you to infer each property. Also, clearly state any assumptions that you are making about the machine or OS and any limitations of your benchmark.

Question 4. Implementing a Lottery Scheduler:

You are to implement a basic lottery scheduler. You are implementing the lottery scheduler within an existing OS that has support for different scheduling classes (this happens to look somewhat like Solaris); therefore, you do not need to worry about the low-level mechanism of dispatching processes. Your lottery scheduling class is called when the following events occur:

process_start(p,t): Process p has been started and given t tickets.
process_exit(p): Process p has been terminated.
process_sleep(p): Process p has blocked on an event and is no longer scheduled.
process_wake(p): Process p has just woken from an event and is now runnable.
timer_expire(p): A 10 ms timer has expired while process P is running (you do not need to handle restarting this timer).

Your lottery scheduling class can also access two useful procedures:

gettimeofday(): A high-resolution, low overhead timer reporting the time of day in milliseconds
schedule(p): Tells the dispatcher to schedule process p next and to deschedule any other process that was running; handles saving and restoring the state of those processes.

Briefly describe your implementation of the lottery scheduling class; that is, sketch out high-level pseudo-code for the routines: process_start(), process_exit(), process_sleep(), process_wake(), and timer_expire(). You should provide a time-slice of 100 ms. You should not provide support for currencies or ticket transfers between processes. You can assume that no other scheduling classes are installed; state any other assumptions that you make.

Question 5. Log Structured File Systems:

For many years, processor speed and the capacities of RAM and Disk have been improving exponentially while disk performance, particular disk latency, has been falling further and further behind.

Most of the design of the original Unix file system and the Berkeley Fast File System (FFS) was based on the expectation that read-only access to files is more common than updates. The authors of The Design and Implementation of a Log-Structured File System (LFS) argue that because of "...increasing memory sizes ... disk traffic will become dominated by writes." Explain why this should be so.
LFS changes the layout of a file system on disk so that all writes are appends to large regions called segments. Briefly outline how the disk data structures in LFS differ from those in the earlier FFS.
The LFS designers state, "The most difficult design issue for log-structured file systems is the management of free space." A large part of the paper is devoted to segment cleaning policies. In particular, experiments and simulations demonstrated the importance of choosing which segments to clean first. Summarize the key results.

Question 6. NUMA:

Consider a system that has Non-Uniform Memory Access (NUMA). On this type of multiprocessor system, physical memory is distributed across each node, such that a load or store to "local" memory is noticeably faster than a load or store to "remote" memory.

Assume you have a multi-threaded process running across the machine, and that a single page in the address space of that process is being concurrently accessed by many of the threads of the program. What could the operating system do (transparently) to improve read performance to that page?
Now assume that for the same program, a single page is being heavily updated (written to) concurrently by many threads of the program. Does your solution for part (a) work here? Why or Why not? What should the OS do differently for this type of write-intensive page (again, transparent to the application)?

Question 7. AFS:

In this question, we discuss a modified version of AFS, say calle AFS'. In "classic" AFS, when a client opens a file, the entire file is fetched from the servers and brought into the local (disk) cache. In AFS', however, when a file is opened, only the first 64KB chunk of the file is brought over and put in the cache, and other chunks of the file are only fetched (and cached) on demand. When a file is closed, only dirty chunks are flushed back to the server (if there are any).

First, we will discuss performance differences between classic AFS and AFS'. Describe a workload (using some combination of open(), read(), write(), close()) that will perform much better on AFS' than on AFS.
Now we will discuss consistency. Describe the consistency guarantee that applications and users can expect from classic AFS.
Discuss how AFS' changes the consistency semantics of AFS. What do you think of AFS' semantics as compared to AFS semantics.