Median 6.9
Mean 7.2 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_X_X_X__________
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 .10 .11 .12 .13 .14 .
- C C C C + + - - B B B B + + - - A A A A + +
The above grade scale applies only to the midterm and should not
be viewed as doing more than clearly separating the best in class
from the worst! The grade scale taking into account homework scores
is far more useful:
Median 33.9
Mean 32.7
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_X_X_______X_
. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
- - C C C C C C + + - - B B B B B B + + - - A A A A A A + +
An Answer: Virtual addresses passed as parameters to the user's read routine must be translated to physical addresses before calling the internal read() routine, and these addresses must be validated; that is, the user's right to perform the required operation must be checked. About 20 mentioned the need for translation and about 15 mentioned the need for validation.Eight students went into detail about how the disk driver enqueues and schedules disk requests, and five mentioned checking the user's access rights to the file f. These are inappropriate answers because they are actions that belong inside the system's internal read routine.
Five went into detail about the system-call trap service routine, but the wording of the question both implies some of these details and excludes them from being required parts of the answer.
An Answer: The major shortcomings of this page-fault trap-service routine, in the presence of shared memory, are: First, it makes no changes to the page table of any process other than the one that caused the trap. So, if it brings in a page shared with some other process, that process is not informed. Second, if it evicts a page from a frame, it does not update the frame-table for that page until after the disk I/O is finished; during the disk I/O, a process that shares this page could access it, causing the copy on disk to be incorrect. 5 gave one or the other of these answers.A surprising 8 focused on the use of the local semaphore within the page fault trap service routine, suggesting that this would cause huge problems. While it is true that naive implementations of semaphore operations may not work in trap service routines, there is no theoretical reason they could not be used, and furthermore, many who focused on this aspect of the pseudocode seem to have assumed that all local variables are static and therefore shared with other processes. This is absolutely wrong.
A common problem, clearly illustrated by 6 answers, was focusing so tightly on a technical detail of read-write overlaps that the big picture fails to emerge. Typically, these answers went on at length about details of disk scheduling for page replacement. These answers were not so much wrong as obscured by their excessive detail and verbage. Another 7 gave answers that were simply vague without being obviously incorrect. These all received some credit.
An Answer: The representation of the process state must include both sets of registers along with the register select bit itself.
Part B: If, as an alternative, internal code within trap handlers is not allowed to call wait() on a semaphore, what consequences does this have for the representation of the state of a blocked process?
An Answer: The representation of the process state need only include the user-state registers and need not include the register select bit.This question was probably the hardest on the exam. 26 students received no credit, while the remainder received only partial credit. Many students were confused by the multiple uses made of the term process state. This can mean priveleged versus non-privileged, or it can mean ready, waiting, running, done, or it can mean the saved registers of a process when it is not running. Only for the final one of these does the phrase "representation of the state" have much meaning, and the fact that the background given specifically went on, at length, about multiple register sets and bits in the CPU status word should have reinforced this.
An Answer:
fork()
set return value to 0 prior to copying state
create new process record
for each page p in the caller's virtual address space
copy caller's page table entry for p into new page table
if page is not shared
allocate a new page
copy contents of page p into new page
fix new page table entry p to refer to new page
endif
endloop
duplicate state of current process in new record
set return value to process ID of new process
return
8 had good answers comparable to the above, although not always in as
much detail. A few more forgot to copy the non-shared pages or did the
entire thing from the perspective of a segmented memory model, apparently
forgetting the background context given at the start of the exam. Many
managed to completely avoid the required focus on memory address space
management. 8 earned no credit.
An Answer The transmit interrupt service routine. 13 gave this answer. 5 got partial credit for saying Q1, but queues are passive, so this is unlikely. 10 said either putchar or the user, but this means that the user cannot even try to fill q1 until the receiver's queue has capacity, so this is clearly wrong.
Part B What component listed above should detect the arrival of CTS and unblock the waiting component?
An Answer The receive interrupt service routine should do this, enabling the transmit interrupt service routine on receipt of CTS; 11 gave this answer. 12 said the transmit interrupt service routine should do this, and most of them identified the transmit interrupt service routine as being blocked at the time, and therefore, unable to take any action; this is a self-contradiction.
Part C What component listed above should detect the arrival of RTS and begin the computations that lead, eventually, to sending CTS?
An Answer The receive interrupt service routine should do this; 12 gave this answer. 5 more said Q2, earning partial credit. Disturbingly, 6 said that the hardware should do this.
Part D What component listed above should send CTS later, after RTS has been received and there is finally room for for N new characters of input.
An Answer Since calls to getchar make space in Q2, getchar can send the CTS when it makes sufficient space. 5 gave this answer, and one more said Q2 for partial credit. 10 said the receive interrupt service routine, although how it gets an interrupt when nobody is sending data to it is a mystery. Disturbingly, 9 said hardware.
An Answer The B-tree scheme outlined in the background replaces the disk addressing information contained in the I-node (and in the index blocks referenced by the I-node), but it does nothing about access rights or other accounting information stored in I-nodes. 15 said as much. 2 more only mentioned the first part of the above.The remainder earned little or no credit! Common sources of confusion involved discussions of the directory structure (an I-node contains only 1 bit pertaining to this, and the tree structure of an I-node or of the B-tree discussed here has nothing to do with the tree structure of a UNIX file system!)
Part B: For what kinds of file access patterns would you expect UNIX I-nodes to outperform the above scheme, and for what access patterns would the above scheme work better?
An Answer The UNIX scheme makes access to the first few sectors of a file efficient, while imposing extra costs to access later sectors of large files. Therefore, the B-tree scheme will work better for random access in large files, while the UNIX scheme will work better for access to initial sectors. Around 7 gave this answer, and 11 hinted at this.The common problem was to suggest that I-nodes are better for sequential access; 5 made this assertion. In fact, both schemes work well for sequential access, assuming that RAM cacheing is applied equally to I-nodes, index sectors and B-tree sectors.
An Answer Directory entries are analogous to capabilities, and directories themselves are analogous to capability lists. 14 got this right, and an equal number had either no answer or an answer that evidenced severe confusion. The remainder got partial credit for at least clearly understanding that they knew what a capability list was.
Part B: What is a protection domain under this scheme?
An Answer The simple answer is that a directory is a domain. A more accurate answer is that the set of all files and directories reachable by a user from that user's current and root directories is that user's domain, where reachable includes traversing paths from directory to directory. 10 gave one of these answers, while 17 gave either no answer or an answer that suggested severe confusion.
Part C: What operation in this scheme serves as a gate-crossing operation?
An Answer Gate crossing involves a change of domain, so operations like change root (Unix chroot) or change directory (Unix cd) count as gate crossing operations. 17 gave answers like this, which is surprising because many of those could not give a clear statement of what a domain is in this system.
Part D: As given here, does this scheme solve the mutual suspicion problem? Why or why not?
An Answer No, because to do chroot x or cd x, a user must have access to x, and this implies that the user's domain contains the domain of x. The mutual suspicion problem is only solved if you can change to a domain that a) includes items excluded not in your current domain, b) does not include some items in your domain, and c) includes some items that are in your domain. 14 simply said no, with wrong or unstated reasons, while 6 gave good reasons.