Final Exam Solutions

22C:116, Fall 2000

Douglas W. Jones

Score Distribution

Mean   = 16.0                     X
Median = 16.0                     X
                                  X
                                  X
                          X       X
                          X X   X X         X
____________________X_X_X_X_X_X_X_X_X_X___X_X_____X_X_____________
   1 2 3 4 5 6 7 8 9 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
  1. Background: Consider a capability-based file system, where the create-file and create-directory services return capabilities for newly created files and directories, which need not be named until later. Nonblocking message passing is used, 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.

    First, of course, the root of the permanent directory structure. Second, the capabilities held by processes for files and directories that they may not have inserted into the permanent directory structure. Finally, capabilities included in messages currently in transit must also be checked!

    Many correctly noted the first; fewer noted the second, and only one noticed the importance of the capabilities in messages in transit.

  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.

    The question said software, so we'll start enumerating just above the physical layer. Obviously, we need the link layer to use each outgoing link, and we need the network layer to forward messages across the gateway. We cannot infer the need for any other layers from this question.

    At least 10 had perfect scores. Many did well, but surprisingly, 7 felt compelled to include the transport layer, and a few argued that event he presentation and application layer must be included.

  3. Background: Suppose an Amoeba programmer wanted to implement a semaphore server, offering the services create-sem, wait, signal and delete-sem.

    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.

    Create-sem must be addressed using the server's widely known public capability. All other operations are addressed to specific semaphores using the capability returned by create-sem.

    About 8 did well. This was supposed to be an easy question, and the failures were shocking.

    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.

    In the normal Amoeba multithreaded server architecture, the number of threads equals the number of clients currently being served. For the semaphore server, this means that each clients blocked in wait() awaiting a signal from some other client will require one thread. If there is a limit on the number of threads the server is allowed to spawn, some client may be blocked as it attempts to wait or signal, not because of the semantics of the semaphores offered by the semaphore server, but because the limit on the number of threads has been exceeded.

    This was expected to be a hard problem. 2 students gave essentially this answer. About 10 suggested that the server allocate one thread per semaphore. This was given full credit, despite the fact that it is difficult to build a semaphore server this way under Amoeba.

  4. Background: Consider a distributed mutual exclusion algorithm in a point-to-point network based on a broadcast protocol that uses a dynamically computed spanning tree. Any participant in a critical section 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 wins.

    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.

    Each process keeps a list of the processes waiting for it; this list gives information similar to that in the waitfor graph, except that the directions on all of the edges have been reversed.

    Around 4 did well here, many commented that processes don't know what process holds a lock, and this is true, but not central to the problem. Far more disturbing are those who said that, unlike the waitfor graph, this graph provides no global view. A waitfor graph only provides a global view if you store it in a centralized place, so this answer has no real merit.

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

    No. Processes know who is waiting for them, and, at a deeper level, processes know which neighbors in the spanning tree used to implement the broadcast protocol have not yet replied, but the nodes that have not replied are not necessarily the same nodes that are blocking the request, and the nodes blocking the request may be blocking because they hold the lock or because they have higher priority.

    About 13 got this right and 5 received no credit.

    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.

    While the directed graph we have has its edges reversed from the traditional waitfor graph, any cycle in the traditional waitfor graph will be a cycle in this graph, and this graph will have no cycles that aren't in the waifor graph, so, to see if there is a deadlock, send out a message on outgoing edges; each vertex receiving this message should forward it to all processes waiting for it, and if the message ever gets back to the original sender, there is a deadlock.

    About 9 did well here. Several others gave the kernel of a good algorithm but omitted major details so could only receive partial credit.

    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?

    The spanning tree constructed during the broadcast request to claim a lock does not dissapear immediately; those parts of the tree between the root and the verices that are not giving immediate permission to claim the lock must persist until permission is granted. Therefore, each node must hold local tree topology information for each spanning tree in which it is participating.

    About 5 did well here, and an equal number received no credit. About 6 gave answers that focused on the answer to part C instead of focusing on the original problem; these received modest partial credit.

  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 using busy waiting for lock files.

    Problem A: Why the sleep command? What would happen if it was omitted?

    Without the sleep command, the cost of the polling loop would be too high.

    Over half did well here, but several managed to write such long answers that a penalty seemed appropriate. 5 received no credit.

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

    The primary cost is the overhead of file creation and deletion. Opening or unlinking a file takes, typically, two disk accesses per component of the path-name of the file.

    Equal numbers did well and poorly here, with very few in between.

    Problem C: Suppose code that uses this approach to locking is compiled on an Amoeba system. Does this imply that Amoeba uses a sophisticated distributed atomic transaction protocol for elementary operations on files? Explain why or why not!

    No. A directory server could rely on the natural semantics of a single threaded server to provide the necessary mutual exclusion, and nothing in the Amoeba design demands that the servers provide fault-tolerance.

    About 7 did well here, and a few more received no credit. The fact that files under Amoeba's bullet file server are immutable earned a few people partial credit, but this seems generous, since the protocol in queston never actually writes anything into the lock file.

  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, one where overloaded machines solicit bids for machines willing to accept extra work, and one where underloaded machines solicit bids for work that needs doing.

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

    Bids from underloaded machines mention their capacity to accept more work. Bids from overloaded machines mention the job or jobs they are willing to offload.

    For bids solicited by overloaded machines, about 15 did well, while 7 more got partial credit and very few got none. For bids solicited by underloaded machines, the situation was worse, with only 11 doing well, 3 earning partial credit, and the remainder receiving none. At least a few of those who missed the second half of the question seem to have done so through carelessness.

    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?

    Yes! If overloaded machines solicit bids, an isolated underloaded machine will not receive work if its neighbors are not overloaded, while it will receive work if it solicits bids. Similarly, if underloaded machines solicit bids, an isolated overloaded machine will not be relieved if its neighbors are not underloaded, while it will be relieved if it is allowed to solicit bids.

    About 1/3 did well here, 1/3 gave weak explanations, and 1/3 did not address the issue.

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

    In general, overloaded machines should not be required to do extra administrative work, so algorithms that place the burden on underloaded machines seem desirable. The one risk here is that underloaded machines might tie up network resources with requests for work, but it should not be difficult to throttle such excessive zeal.

    About 11 did well here, and another 3 got partial credit.

  7. Background: DreadcOS ME has 3 built-in object types, the page, the C-list, and the activation. 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.

    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.

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

    An Amoeba RPC involves two transfers, call and return, that are comparable to the DreadcOS ME enter operaton, in that, conceptually, these transfer a thread of control (with parameters) into and then out of the protection domain of a server.

    At least 9 did well here, and an equal number received no credit. The few that remain gave various vague answers.

    Problem B: Consider the problem of implementing protected queues in DreadcOS ME. Users have 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 it.

    The user of queues must have a capability for an activation; to create a new queue, the user enters this activation, expecting it to return a capability or capabilities for a newly created queue object.

    About 8 did well here and an equal number received no credit, The remainder gave various vague or muddled answers.

    Problem C: Consider the problem of implementing protected FIFO queues in DreadcOS ME. How is a queue represented, and what does the create queue operation return to the user?

    A queue object must have its representation hidden in a private domain; this domain would be accessible to the activation that performs the operations on queues. If there is a need to protect the right to perform different operations separately, each operation could be packaged as a different activation. In that case, the create operation might return a C-list containing the capabilities for each of these activations. In the other case, the create operation could simply return a capability for the activation that is able to perform all of the operations on the queue.

    About 7 did well here, while another 4 did reasonably. For half credit, about 6 listed all of the pieces without indicating how they were connected, while a number gave minimal answers such as "A C-list" or "A domain".

    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.

    The user must enter some local domain, where that local domain communicates over the network with a peer on the machine hosting the target activation. The peer then enters the target activation. This is analogous to an RPC protocol.

    About 6 did well here, and 5 more did reasonably. 5 earned no credit, and another 4 gave answered so muddled that very little credit could be given. The remainder were inbetween.

    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?

    Simple scalar parameters, passed in registers, are easy. If we have a global representation for capabilities, it is equally easy to pass them in Capability-registers. Use of capabilities for data on remote machines poses more problems! If a capability is passed that offers read-only access to a page or C-list, that page can be easily copied. If an enter capability is passed, a stub such as that suggested in problem D could be constructed. Shared read-write pages or C-lists pose major problems and may be impossible.

    Only 1 did very well, 1 did very poorly and the remainder were spread out inbetween.