This exam is worth 30 points; there are 7 questions divided into a total of 15 parts. This means that each part of each question is worth 2 points. Given that this is a 2 hour exam, this also means that each part of each question is worth about 8 minutes of your time.
___________________ ___________
|___________________|___________|
20 bits 12 bits
page number byte in page
This memory management unit contains an address translation cache with
48 bit entries that have the following format:
___________________ ___________________ _______
|___________________|___________________|_______|
20 bits 20 bits 8
page number frame number rights
and marks
The memory management unit performs an associative lookup, producing
a physical address by substituting the frame number for the page number
if there is a cache entry matching the virtual address presented and if
the rights on that cache entry allow the operation attempted. Otherwise,
the unit issues a page-fault interrupt. On page-fault interrupt, the
hardware returns to the handler the page number that would not translate
and nothing more.
Address translation cache management is totally up to software -- every register in the cache is directly accessable by the page fault manager. The bits in the rights and marks field in each cache entry includes the following bits:
read - read access is allowed
execute - instruction fetch is allowed
write - write access is allowed
The remaining fields are available to software.
Problem, part A: When a page fault occurs, it is possible that the page fault handler would have to replace an address translation cache entry. Given the hardware described above, a modified clock replacement algorithm would be the best choice for this. How could the software detect use of a cache entry in order to set the mark bit needed by the replacement algorithm?
Problem, part B: Suppose the higher level system model of the virtual address space is organized as follows:
_________ _________ ___________
|_________|_________|___________|
10 bits 10 bits 12 bits
segment page in byte in
segment page
What data structures would the system maintain to describe the address space
of a user process, and, in some detail, how would the information from these
structures be interpreted, by software, in order to compose the cache entry
for a page?
Recall that a char is syntactically a procedure that takes a message as a parameter. In addition to supporting the above kernel interface functions, the Amulet kernel acts as a main program, passing appropriate messages to user chars. On a uniprocessor, only one char is active at any moment.
On an Amulet system, interrupt handlers are very short stubs that call (pass a message to) some associated char. Thus, when a user presses a key on the keyboard, the keyboard interrupt handler would place a call to the keyboard char. When the Amulet kernel scheduled this char, the keypress would be handled.
Suppose you had to write a disk scheduler under Amulet. How would you structure it? Specifically:
Problem, part A: How would user code interact with your code? How would a user request a read or write, how would the data be communicated, and how would the user learn of the completion of the requested action.
Problem, part B: How would you structure your disk scheduler? What internal chars would be involved, and how would they interact?
enter_region(p) other = 1 - p; interested[p] = true; turn = p; while turn = p and interested[other] do nothing; exit_region(p): interested[p] = false;Here, turn and interested are shared variables, and the formal parameter p is a process id from the set {0,1}.
Problem, part A: If the above code is run on a multiprocessor where the different CPUs had different width paths to memory, so one CPU operated, for example, on 128 bit words, while another used a 32 bit path, and yet another used an 8 bit path. What would you have to guarantee about the allocation of the shared variables and the code used to fetch and store from them in order to guarantee that this algorithm would work correctly in this environment.
Problem, part B: Suppose you had a system with two processes communicating by messages using a blocking receive primitive, a buffered nonblocking send, and the possibility of using multiple threads. Suppose these processes need to achieve mutual exclusion and a decision is made to use Peterson's algorithm, based ont the following idea:
To enter a critical section, a process begins by sending "I am interested" to the other process. To leave the critical section, the process sends "I am no-longer interested". How does a process decide when it can enter the section, and how is the shared "turn" variable managed?
The server must check that the ACL for the given resource allows the specified client to perform the indicated operation before that operation is performed. The client-ID field of the message contains a globally unique identifier for the client's domain.
One special operation supported by all servers for all resources is "set access rights". This operation takes, as parameters, a second Client ID and the rights allowed to that client.
Problem, part A: What security risks are posed by this scheme.
Problem, part B: Explain the consequences of having clients use a different Client ID to deal with each resource, for example H(<Client_ID, Resource_ID>), where H is a one-way hashing function computed by the client, so that the server never knows the true identity of the client.
As in Demos MP, When a message is sent from machine A to machine B, intended for a process that once ran on B, but is now running on machine C, machine B sends a change of address notice to machine A. As a result, future future messages from A to the process in question will be sent directly to machine C. If machine A was itself forwarding the message, the forwarding address on machine A is reset to point to C instead of B.
Problem, part A: After a process has migrated from machine to machine over the whole network, visiting each machine at least once, and never sending or being sent any messages during that time, what is the topology of the directed graph composed of the forwarding addresses for that process? Subsidiary questions include such things as, will the graph contain cycles, will it be a connected, and how will the structure relate to the current location of the process?
Problem, part B: In graph-theoretic terms, what is the maximum possible impact on the directed graph of forwarding addresses when a single message is sent from some machine to the process in question (the one that has been everywhere). This graph transformation is fairly easy to describe!
Consider the following component of a garbage collection protocol: When a server receives the message probe(cap), it checks to see if the capability cap has previously been probed. If not, the server marks it as having been probed and then probes every capability contained in the data structures of that resource.
Problem, part A: What additions to this idea are necessary to build a complete garbage collector? Explain the added components of the protocol, and explain the top-level algorithm that drives the protocol and results in collection of unreachable objects.
Problem, part B: What problems would you expect to encounter in Amoeba with the implementation of such a protocol? In your answer, emphasize high level problems that might prevent the effective use of garbage collection in Amoeba.
Directory servers, of course, use files to store directories. Thus, when a user presents a capability to a directory server, it may have to access a file in order to make use of that capability.
Recall, also, that the standard on UNIX is that every directory contains two special entries, . (dot), a directory entry referring to itself, and .. (dot-dot), a directory entry referring to the parent directory. With the exception of the above special directory entries, A UNIX directory structure is a tree, with every directory being referenced from exactly one other directory, and exactly one root.
Problem, part A: Given that this distributed system makes an effort to accurately mimic the UNIX file system, what atomic transactions would you expect to be involved in creating and deleting files? In creating or deleting directories?
Problem, part B: Assuming two-phase locking, are these transactions prone to deadlock? To answer this question, you will have to identify the resources that each of the transactions you identified in part A locks, and then either propose a locking order for these resources that is deadlock free or identify a permissable sequence of locking operations that is prone to deadlock.
Problem, part C: To what extend do the transactions you have identified span multiple servers in the distributed environment described here? What kinds of commit protocols and deadlock detection protocols are implied by this?