Operating Systems Depth Exam

	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
Operating Systems Exam		Fall 2009

Instructions: There are six questions on this exam; answer all six questions.

Question 1. Memory Management

Consider a system that does not contain hardware support for setting or clearing dirty bits.

A) Explain the benefits of knowing if a page is dirty or clean.

B) Describe how setting and clearing dirty bits can be efficiently emulated by the OS. To make your answer clear, specify any changes in how the page tables are used and any new data structures that are needed. Explain what happens on a read and write to a given page; if some read or write operations act differently than others, explain each case.

C) Imagine that you would also like to implement copy-on-write. Explain copy-on-write and give a specific example of where it is particularly useful.

D) Describe how copy-on-write could be incorporated into this system (i.e., a system with no hardware support for dirty bits).

Question 2. RPC

Suppose you want to compete with Google and Microsoft and build large, distributed applications that will run in the cloud. You learned about RPC in your graduate school operating systems class, and are thinking about using it as the basic mechanism for writing your distributed services.

A) One key component of any RPC system is stub generation. Describe the process of stub generation, and how it eases the process of distributed application development. What types of problems are avoided by automating this process?

B) Reliability is a big concern in large-scale distributed systems. What is the RPC failure model? What can fail, and how are such failures reported?

C) Is the RPC failure model appropriate for a large-scale system with thousands of machines, where hardware, network, OS, and software failures occur frequently (although perhaps not frequently on any given machine)? If so, why? If not, why not?

Question 3. Kerberos

Kerberos makes use of secret key authentication: users and services share a secret key with a Key Distribution Center (a KDC) that can provide initial tickets and user tickets.

A) Why does the Kerberos protocol separate out the process of getting an initial ticket from getting service tickets?

B) Suppose an attacker can sniff the network of a system using Kerberos. Can the attacker subvert the system and access services as an authenticated user? If so, explain how. If not, explain how Kerberos prevents this attack.

C) Suppose you believe that biometrics are the way to go and want to let people log in by fingerprint instead of with a username/password. Can this be accomplished with a variation of the Kerberos protocol? If so, how

Question 4. Caching

Caching is a common technique in system design and is used within many different systems, such as local file systems, distributed file systems, virtual memory systems, and virtual machines. Read all parts of this question before answering.

A) Provide an example where caching improves system performance. Your example should concretely describe a scenario that applies to one of the following: a local file system, a distributed file system, a virtual memory system, or a virtual machine.

B) Provide an example where caching hurts system performance for a specific workload. Your example should be applied to a different system than you considered in Part A.

C) Provide an example where caching hurts the system dependability. Your example should be applied to a different system than you considered in Parts A and B.

Question 5. Consistency

One of the most important aspects of file system design and implementation is consistent update of on-disk structures. For example, when an application appends data to a file, a few different on-disk structures are dirtied, including (for example), the inode of the file, a data bitmap, and of course the data block that holds the newly-appended data. The file system, using whatever consistent-update strategy it has, tries to ensure that either all of the updates occur on disk, or none, in an atomic fashion.

A) What hapens if the system uses no such strategy, and just writes the dirty blocks to disk in some arbitrary order? What problems can arise?

B) Journaling (or write-ahead logging) is one major technique used to perform a consistent update, and is used by many file systems including Linux ext3 and Windows NTFS. The basic idea is to have a separate log where updates are first written; once that operation is complete, the main structures of the file system can be updated. How would journaling solve some of the problems you discussed in part A? What are its strengths and weaknesses as a technique?

C) Copy-on-write (or shadow paging) is another technique used to perform consistent update, and is used by file systems such as Locus, LFS, and Sun's ZFS. Describe how copy-on-write works. What are its strengths? What are its weaknesses? How does it compare to journaling?

Question 6. Synchronization

Proper synchronization, often achieved by using locks and condition variables, is not that hard to achieve once one understands how to program with such primitives correctly. However, using such techniques and getting high performance out of an application can be quite an interesting challenge. In this question, we will explore a few scenarios where non-standard synchronization techniques are used and evaluate their performance and correctness.

A) One place where such optimizations might occur is in the locking code itself. For example, a test-and-set instruction can be used to build a simple lock as follows:

void mutex_lock(mutex_t *m) {
    while (TestAndSet(&m->flag) == 1) 
        ; // spin
}
void mutex_unlock(mutex_t *m) {
    m->flag = 0;
}

However, sometimes clever programmers build what is called a "test-and-test-and-set" lock, as follows:

void mutex_lock(mutex_t *m) {
    do {
        while (m->flag == 1) 
            ; // spin
    } while TestAndSet(&m->flag) 
}
void mutex_unlock(mutex_t *m) {
    m->flag = 0;
}

Does this lock work correctly? Discuss.

B) Different locking implementations are often used to improve performance, particularly under contention (concurrent access by many threads). Does the new "test-and-test-and-set" lock improve performance? Why or why not? Describe.

C) In this example, fd is a shared variable among multiple threads which is the file handle for a file that a group of threads might wish to read. However, sometimes the file will not yet be opened (and fd will be 0), so each thread must first check if fd is 0, and if so, reopen the file for subsequent reading. Here is the code snippet used originally:

mutex_lock(&lock);
if (fd == 0) 
    fd = open("file", O_RDONLY);
mutex_unlock(&lock);

And here is the code snippet they used in an "optimized" version.

if (fd == 0) { 
    mutex_lock(&lock);
    if (fd == 0) 
        fd = open("file", O_RDONLY);
    mutex_unlock(&lock);
}

Does the optimized version work correctly? Why or why not? Describe.

D) Does the optimized version perform better? Why or why not? Describe.