Final Exam Study Questions

22C:116, Fall 2000

Not Due Friday Oct 6, 2000

Note: Review the Midterm, including the study questions, the exam questions and their posted answers. Also review the homework questions and their posted answers. Some final exam questions will definitely be based on previous exam or homework questions!

Also, if you wish, review some of the exam questions from previous semesters. These will probably not be used, but they are good exercises, to help you build up your knowledge base and get a feel for the style of questions you're likely to receive.

Some study topics:

Consider a capability-based file system, where directories are C-lists with an attached textual name on each entry, and where, unlike UNIX, there is no restriction on the directory hierarchy. The create-file and create-directory services return capabilities for newly created files and directories. The name-file service takes the capability for a directory, a name, and a capability to put into that directory with that name. Nonblocking message passing is used for interprocess communication, and capabilities for files may be included in messages.
Things to think about: Some parts of the implementation of this system could be borrowed from a conventional system such as UNIX. What parts would have to be written from scratch?
Background: Consider a distributed mutual exclusion algorithm in a point-to-point network based on a broadcast with acknowledgement protocol. The underlying protocol propagates the request for critical section entry out through the network along a dynamically computed spanning tree, and then gathers the replies along the same tree, thereby minimizing the total number of messages required. The outgoing message carries a transaction ID that includes the process ID of the initiator, and it includes the lock ID.
On receipt of the message, all participants not contending for that lock reply immediately; any participant in a critical section using that lock replies on exiting that critical section, and all participants already awaiting responses their own requests to enter that critical section only reply immediately if their unique ID is less than the unique ID of the initiator of the current request.
Each participant may accumulate a list of replies that are to be sent when it finally exits the critical section, in case there are many participants awaiting entry. With this algorithm, the set of replies that each process has deferred tells it the set of processes that are blocked awaiting its exit from the critical section.
Some questions: How would you do deadlock detection on this system?
Background: In UNIX, the operations of creating and deleting files are atomic. Prior to the addition of the System V UNIX semaphore mechanism, this was used to implement mutual exclusion as follows:
```
    lock( char * L )
    {
         int fd;
         fd = open( L, O_CREAT|O_EXCL );
         while (fd < 0) {
              sleep( 1 );  -- delay 1 second
              fd = open( L, O_CREAT|O_EXCL );
         }
         close(fd);
    }

    unlock( char * L )
    {
         unlink( L );
    }
```
A question: Why has this kind of programming persisted on UNIX even though it has been over 20 years since the UNIX System V spec came out with a decent semaphore mechanism and over 10 years since this mechanism has been almost universally available?
Background: Consider two competing load balancing algorithms for a point-to-point network where all load transfers are between adjacent machines in the network.
All load transfers are initiated by overloaded machines. The overloaded machine seeks bids from machines willing to accept load from it, selects a target machine, and transfers an appropriate job to that machine.
All load transfers are initiated by underloaded machines. The underloaded machine seeks bids from overloaded machines, selects an appropriate job, and requests the transfer of that job to itself.
The basic problem: Compare these!
Background: DreadcOS was a marvelous idea, but seriously flawed. The next generation DreadcOS system, DreadcOS ME, is based on the same basic ideas as DreadcOS, but it has 3 built-in object types, the page (for data) with access rights read and write, the C-list (for capabilities), with access rights read-c and write-c, and a new type, the activation, with access rights enter, read, write, read-c and write-c.
Each activation object contains a CPU state (PC and other registers) plus a short C-list that we will refer to as the capability registers. Just as several of the registers in the CPU are specialized and essential to our model of a stored program computer, so are the capability registers specialized. These include the DC, or domain capability, designating the C-list used to represent the activation's domain, the RC or return capability, used to allow the running thread to return to its caller, and a pair of capabilities PC1 and PC2, used for passing capability parameters.
There is an operation, activate, that creates an activation object with all access rights. There are operations for reading and writing the data and capability registers in an activation, assuming the required access rights are present, and there is an enter operation allowing the transfer of control to an activation.
The enter operation will, optionally, pass the values from the caller's parameter registers to the new activation, and it will optionally pass a newly created return capability that allows entry to the caller's activation. The enter operation takes a parameter indicating which of these are to be passed, and the entered activation contains a field indicating which it expects to be passed. These must agree or the operation will fail.
As with DreadcOS, DreadcOS ME is not inherently a distributed system, but the proud developers at Dreadco are convinced that it can be easily incorporated into distributed systems.
Think about: gate crossing, implementing protected instances of classes such as stacks, queues, etc, and use of the DreadcOS ME kernel in a network environment.