Median = 65 X
X X
X X X X X X X X X X
_____X_X_________X_X___X_X_X_X_X_X_X_X_X___X_X___X_X___X_____
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
5 6 7
- - - C C C C + + + - - - B B B B + + + - - - A A A A + + +
Median = 15.0 X
X X X
XX X XX XXXX X
______________X_____XX_XXX___XX__XXXXX_XXXX__________________
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
1 2
Part B: Is this mechanism leak free? Assuming that a server periodically remembers to age all of its objects, yes, all garbage will eventually be reclaimed.
Recall that the UNIX command "ln x y" creates a new link named "y" for a preexisting file reached by the name "x", and that the UNIX command "rm x" deletes the link named "x". Recall also that each directory contains a link to itself, named "." and a link to its parent, named ".."; the "mkdir" and "rmdir" commands maintain these structures.
Part A: Why, under UNIX, must "rm" and "ln" be restricted, so that "rm" may not be used to delete the link to a directory? Because the directory will not be reclaimed until the reference count reaches zero, and the . link of the directory and the .. links of its children will prevent an unreachable directory from being reclaimed if rm were allowed to simply delete the link to the directory. In contrast, rmdir assures that no .. links to a directory exist, then deletes the . link, then deletes the link to the directory, allowing the reference count to properly reach zero so the directory will be reclaimed.
Why is it that "ln" may not be used to create a link to a directory? Because freely allowing users to create a link to any directory to any other directory would allow users to create arbitrarily constructed cycles in the graph of links, and these cycles would circular linkages that rmdir could not remove. As a result, unreclaimable and unreachable directories could accumulate and fill the file system.
Part B: If UNIX used a mark-sweep garbage collector to reclaim unreachable files instead of the reference count algorithm outlined above, would your answer to part A be different? Absolutely! A mark-sweep collector would remove any unreachable file or directory, so there would be no limit on the use of ln to create arbitrarily complex linkages, nor would there be limits on the use of rm to delete arbitrary links.
In contrast, with capability lists, the of finding all users who could do something is difficult -- the set of capabilities held by each and every user must be scanned to find who has capabilities for the indicated resource.
On an attempt to read or write an object, if that object is locked in such a way that the read or write must block, the user can be sent a message saying wait. The user, after waiting a modest interval, can initiate deadlock detection by sending a probe message to the locked object.
On receiving a probe, a locked object forwards the probe to the process that holds the lock. If the object isn't locked, it sends a reply to the originator of the probe saying no deadlock.
On receiving a probe, a blocked process (or the agent of the process, or the kernel hosting that process) forwards the probe to the object on which the process is blocked. If the process is not blocked, it replies to the originator of the probe saying no deadlock.
Termination in case of deadlock requires that each probe carry with it some identification. Either each process or object receiving a probe must retain a record of the probes it has received, in order to recoginze that this probe has already been there before, or each probe must carry a record of all processes and objects it has visited, to allow recognition of multiple visits. In either case, when it is detected that a probe has visited some process or object twice, the probe is discarded and a message is returned to the originator of the probe saying deadlock.
On receipt of a notice of deadlock, a process aborts the current transaction. (4.0 points)
Part B: Addressing messages to actual user process participating in the protocol would cause problems if those processes are blocked. It is unlikely that a blocked process could receive a probe and act on it, since it is not currently running and able to do so.
If probes are addressed to the agents of processes instead of to those processes themselves, replies are practical. Similarly, the system hosting a process could itself act as the agent for probe handling, although this is rare!
page fault handler
-- given va = virtual address, with field va.page and va.word
-- given pc = user's pc at the time of the fault
if page_table[va.page].type = page_object
-- handle fault as a normal page fault
else if page_table[va.page].type = dequeue_object
-- this fault involves a dequeue
instr = *pc;
if is_load_instruction_at(instr)
if va.word = 0
t = dequeue_head( va.page );
simulate_load_instr(instr,t);
pc = pc + 1;
else if va.word = 1
t = dequeue_tail( va.page );
simulate_load_instr(instr,t);
pc = pc + 1;
else if va.word = 2
t = get_dequeue_size( va.page );
simulate_load_instr(instr,t);
pc = pc + 1;
else
error
endif
else if is_store_instruction_at(instr)
if va.word = 0
enqueue_head( va.page, simulate_store_instr(instr,t) );
pc = pc + 1;
else if va.word = 1
enqueue_tail( va.page, simulate_store_instr(instr,t) );
pc = pc + 1;
else
error
endif
else
error
endif
else
... other object types?
endif
return
Part B: A reasonable set of operations on capability lists, as a class of non-page objects, would be:
This solution is predicated on the idea that each capability list is fixed size, holding a number of capabilities no greater than the number of bytes per page.
The next problem to address is how the user can put one of these capabilities into the virtual address map itself, allowing addressing of the object referenced by the capability. Here are two solutions: Either we could, by convention, make page zero of each address space be a reference to the capability list representing that address space, or we could add new supervisor calls to allow a user to insert a capabilty into a designated slot in the address space. If address spaces are large, the former solution is cleaner. If they are small, so that each slot is precious, the latter would be preferable.
Part C: I'd use jump(A+n) to transfer control from the current domain to the domain modeled by capability n in the capability list at A in my address space.
I'd use call(A+n) to do a procedure-call like transfer from the current domain to the destination, delivering a capability to the destination that could be used to re-enter the calling domain.