Final Exam

22C:116, Fall 2000

Douglas W. Jones
Please write your answers on the paper provided. Make sure your name is on the front page, in the same form as it appears in the official class list! Nothing but name and address information (see below) should be on the cover sheet of your exam.

This exam is open-book, open-notes, closed neighbor!

NOTE: If you want your final grade sent to you by E-mail, put your E-mail address on the front of the exam book. If you want your graded exam mailed to you, put a postal address on the front of the exam book. Otherwise, graded exams will be available for pick-up during the first two weeks of next semester.

NOTE: Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here! Illegible and overly long answers are difficult to grade. Please leave margins around your answers!

This exam is worth 3/10 of the final grade (30 points; allocate 4 minutes per point).

  1. Background: 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.

    Problem: Assume mark-sweep garbage collection is used. What roots must be checked by the marking phase. (2 points)

  2. Background: Consider a gateway machine. This machine serves only one function, to connect two subnetworks into one network, allowing messages from an entity on either subnet to be received by an entity on either subnet.

    Problem: What layers in the ISO OSI protocol hierarchy must be present in the software running on the gateway machine. (2 points)

  3. Background: Suppose an Amoeba programmer wanted to implement a semaphore server, offering the services create-sem, wait, signal and delete-sem. Recall that the Amoeba RPC protocol is a blocking synchronous protocol.

    Problem A: Which of these services would be addressed using the server's widely known public capability, and which would be addressed to objects in the server's internal object table. (2 points)

    Problem B: Explain the relationship between the system's limit on the number of threads per process and the number of semaphores this server can safely instantiate. Include an explanation of the problems that might arise if the server instantiates too many semaphores. (2 points)

  4. 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.

    Problem A: How does this information differ from that presented by the traditional waitfor graph, as used in introductory discussions of deadlock detection algorithms. (1 point)

    Problem B: Does this algorithm give a blocked process the information it needs to determine what process currently holds the lock it is awaiting? (1 point)

    Problem C: Give a very high level description of a deadlock detection algorithm suitable for use on this system, given your conclusions from parts A and B. Contrast this algorithm with the classical algorithm based on the waitfor graph. (1 point)

    Problem D: Aside from the list of deferred replies stored with each process currently in a critical section, what other information must be stored in this network on behalf of blocked processes? Where is it stored? (1 point)

  5. 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 );
        }
    

    Problem A: Why the sleep command? What would happen if it was omitted? (1 point)

    Problem B: What computational cost would you expect to be associated with critical sections that use this kind of lock? (1 point)

    Problem C: Suppose code that uses this approach to locking is compiled on an Amoeba system. (In fact, this is usually the case when UNIX utilities such as mailers and web browsers are ported to Amoeba.) Given that the Amoeba file system is distributed, does this imply that Amoeba uses a sophisticated distributed atomic transaction protocol for elementary operations on files? Explain why or why not! (1 point)

  6. 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.

    Problem A: What kind of information does each load balancing scheme require to be included in a bid? (2 points)

    Problem B: Are there situations where these two algorithms will lead to different load transfers even though the criteria for offloading jobs and accepting jobs are made as nearly identical as possible? Why? (2 points)

    Problem C: Generally, is there a reason to prefer one of these algorithms? Why? (1 point)

  7. 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.

    Problem A: The enter operation is a gate crossing operation. What operation in Amoeba comes closest to having similar semantics? (2 point)

    Problem B: Consider the problem of implementing protected FIFO queues in DreadcOS ME. Obviously, you need to give potential users of such queues access to a capability that allows the user to create a new queue. What kind of object does this capability refer to, and how does the user use that object to create a queue. (2 points)

    Problem C: Consider the problem of implementing protected FIFO queues in DreadcOS ME. How is a queue represented (what collection of DreadcOS objects must be involved, and how do they relate to each other), and what does the create queue operation return to the user? (2 points)

    Problem D: Consider a network of DreadcOS ME systems, where a user program running on one machine needs to enter an activation on a different machine. To what local object must the user's capability refer, and how can we make actions on this local object have the net effect of transferring control to the remote activation. (2 points)

    Problem E: Consider a network of DreadcOS ME systems, where we have solved the problem of implementing a remote enter operation. What kinds of parameters will be easy to pass, what kinds may be difficult to pass, and what kinds are likely to be impossible to pass? (2 points)