The exam was graded on a 30 point scale, with either 2 or 3 points assigned to each part of each problem.
The average exam score was 13; the grades were distributed as follows:
X
X X X
__X_________X___X___X_______X_X___X_X___X_____________X________
0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
Problem, part A: Write example code for a process that reads and copies data from one pipe to another. (3 points)
Answer: Given that src and dst are variables allocated at the virtual addresses of the pages assigned to the source and destination pipes,
repeat
dst := src;
forever
4 students got this right, many wrote code that relied on unimplementable semantics.
Problem, part B: How would you handle the problem of special pipe operations such as writing an end-of-file mark on the pipe, and how would your implementation signal end-of-file to users reading from a pipe. (2 points)
Answer: One option would be to have the page fault trap service routine interpret references to word zero of a page that represents a pipe as the location from or to which data is copied, while writing word one could write an end-of-file, and reading word one could return status information (such as whether the pipe was empty or whether the end of file had been reached).
Nobody suggestd the above answer, but 6 students proposed designating a special character as an EOF mark, to be written to or read from a pipe to signal the end of a file.
Problem, part C: Give a brief outline of how the page fault service routine would implement this pipe interface. (2 points)
Answer:
page fault service routine:
if type of faulty map entry is pipe
if the instruction is load
read from pipe to designated register
advance the program counter beyond the instruction
else if the instruction is store
write to pipe from designated register
advance the program counter beyond the instruction
else
report an invalid operation on the pipe
endif
else it is a normal page fault
handle page fault conventionally
endif
At least three students correctly described all of the above, with the
exception of incrementing the program counter after emulating the load
or store instruction. Many students managed to somehow suggest that an
actual page frame was somehow mapped to the page, but this does not lead
to a workable implementation.
Problem, part A: What are the resources this system allows to be locked and what deadlock model applies? (2 points)
Answer: The resources are individual bytes of files. The deadlock model is either the single resource model (if processes lock bytes one at a time, in sequence), or the and model (if processes attempt to lock all requested bytes as a single atomic operation).
9 students correctly answered this, while 5 more got partial credit.
Problem, part B: Assuming that only one file server is involved, what problems would you encounter in implementing a reasonable deadlock detection algorithm for the server. (3 points)
Answer: The obvious implementation of a deadlock detection algorithm requires that space be allocated to store the status of each resource (free or in use, and if in use, by whom). The straightforward implementation of this would require room for something like a process ID associated with each byte of each file -- more than doubling the storage requirements of all files!
3 students said essentially this. 7 more said something like ``there are many files with many bytes'', implying that they understood something like this without coming out and saying it.
Problem, part A: What behavior would you expect from this (2 points):
S: semaphore with S.count=0
loop
read(b,S)
delay(1.0,S)
wait(S)
process(b)
end loop
Answer: The first execution of this loop will either read one thing
or delay 1 second before processing, but whichever it does, the other
operation will still be waiting to signal the semaphore. In fact, for
every iteration of the loop, two signal operations will be scheduled for
some future time, but only one wait operation will be performed; as a result,
as the iterations advance, more and more signals will be received from
read or delay operations scheduled in previous iterations.
6 students answered this correctly, while 2 more correctly described the behavior of the code during the first iteration.
Problem, part B: Will the following version operate correctly (2 points):
loop
S = pointer to new semaphore with S.count=0
read(b,S^)
delay(1.0,S^)
wait(S^)
process(b)
end loop
Answer: This code corrects one problem with the original version.
Each semaphore is discarded after one iteration, so future iterations will
only depend on the read and delay operations issued in that iteration.
However, there is another problem! The read operations issued during
iterations that time-out are not cancelled or discarded. As a result,
those read operations will still be performed, reading into the correct
buffer, but signalling a semaphore that has been forgotten.
6 students clearly understood how discarding the semaphores corrected some of the problems with the original, but they did not notice the bug that remains.
Answer: The order in which processes run is influenced, in part, by the other activity in the system, including interrupts and other processes. Thus, even though the scheduling decisions are deterministic, in terms of the set of ready processes at one instant, and even though the CPU itself is deterministic, the results will vary from run to run.
6 students answered this correctly; many others said that it is nondeterministic because it contains fork operations, but that answer was not judged sufficient.
Answer: User level thread packages can outperform kernel threads or conventional processes on a shared memory multiprocessor, but they cannot do so in a network environment or uniprocessor. In both of the latter, all interprocess communication must involve entry into the system kernel, either for access to the network or for context switching; as a result, user threads on distributed or uniprocessor systems will generally offer no advantage.
4 students did well on this, and 2 more gave confusing but essentially correct answers.
The problem, part A: What storage management problems must the user and system face in using this capability system? (2 points)
Answer: The system cannot know which pages are currently reachable by some user, so it cannot automatically reclaim memory, but must rely on users to call killpage when they no-longer need pages. When users forget to do so, the result will be that memory will be lost. This problem cannot be solved by the system as defined, and as a result, it would be very likely that large scale applications implemented under this system will always crash eventually, running out of memory. For this reason, I would not rely on this system.
Clearly, the encrypted capability given to a user cannot contain the address where the page is stored at some moment, but must contain a name for that page that is permanently meaningful. This requires that there be some kind of global index structure to relate names of pages to their current addresses, in main memory or disk.
Only one person gave a really good answer to this question, although 3 or 4 gave reasonable partial answers.
The problem, part B: Propose a representation of the capabilities given to the user by getcap. (2 points)
Answer:
___________ ________ _______ |___________|________|_______| | page name | rights | check |The check field might, for example, be derived from a random number associated by the system with the named page, using some kind of trapdoor function to incorporate the access rights so they can be checked. There are many reasonable alternative schemes.
One student gave a good answer, and 5 outlined general capability encryption schemes, but made mistakes with the contents. The most common mistake was to replace the page name with the virtual address of the page. The virtual address of a page depends on where it is in the user's map; the services given clearly allow pages to be moved about, within one map or between maps, so virtual addresses are not useful as globally meaningful names for pages.
The problem, part A: Explain how you would implement one under DEMOS or Amoeba. (2 points)
Answer: A virtual file server would be a process that responds to messages using the same protocol as the real file server under the system in question. Instead of actually implementing files, however, this process would make use of other file servers to actually store the files. The virtual server could, for example, maintain duplicate copies of files, perhaps to assure fault tolerance.
3 students gave good answers; a few more gave vague but reasonable answers.
The problem, part B: Explain how you would design the system so that a user process would be unable to tell whether it was running under a real or virtual file server. (2 points)
Answer: Under both Amoeba and DEMOS, the process that holds a capability is generally unaware what server that capability references. Thus, if a user program is given a capability for a file server, it must take it on faith that that capability represents a particular server; in fact, the program could be given the capability for a virtual server one time it is run, and for a real server the next time, with out the program being aware of the difference.
Under Amoeba, the situation favors virtual servers even more, since directories merely associate names with capabilities, and the capability itself includes an encoding of what file server should be used to access that file. Thus, a program accessing two different files may easily find itself using two different file servers, one or both of which may be virtual.
3 students did well here, and a few more gave reasonable answers.