Midterm Solutions

22C:116, Fall 2000

Score Distribution

   Mean = Median = 8.8
                                  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____
       2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 .10 .11 .12 .13 .14 .
Rough grades: -     C     + -     B     + -     A     +

Solutions

Which of the DreadcOS access rights are likely to be enforced the MMU hardware of a typical modern processor, and which will be enforced by software.
Typical MMU hardware enforces read and write access rights on pages. Typical MMU hardware is unaware of capability list objects, so all such objects will have to be marked as inaccessible so that software can be used to enforce rights and implement the semantics of the operations on these objects.
9 had good answers to this, 4 received no credit, and the reaminder received partial credit. Around 7 suggested that the operations on C-lists were likely to be protected by hardware, and around 4 suggested that the read and write operations on normal data pages must be protected by software.
Write a tiny code fragment (in clear pseudocode) to load the contents of the byte marked X in the figure (byte 3 referenced by capability 1 in page 2 of the virtual address space) into some directly addressable variable Y. Assume that page 1 of the virtual address space is initially invalid.
```
getc(address(1,0),address_c(2,1))
  -- make page 1 of the current address space point to
     the object pointed to by capability 1 in page 2 of
     the current address space
Y = *(address(1,3))
  -- get the data from byte 3 of page 1 of the current
     address space.
```
10 got no credit for this, 4 had answers containing a relevant kernel, and about 13 had the right idea, but bad notation. Nobody did really well on what I'd hoped was a fairly simple problem.

Assuming that all required pages are in main memory, assuming that current points to the page-table of the current process, write pseudocode for the get-c(a,b) system call.

getc(a,b)
   decompose a into pa and oa such that a = address_c(pa, oa)
   decompose b into pb and ob such that b = address_c(pb, ob)
   -- note, current is a pointer to a C-list
      and each capability has a rights field and a ref field, where
      the ref field will be treated here as a pointer to a C-list
   if Read-C in current[pb].rights
     then current[pa] = current[pb].ref[ob];
8 got no credit here, 13 had answers that contained a relevant kernel embedded in confusion, 4 had vague but not wrong answers, and a very few had the right idea but generally expressed it poorly.

What is the natural page size for this system, assuming that the virtual address space is 32 megabytes (2²⁵ bytes), and assuming that capabilities are 8 bytes long, and assuming that each C-list may be used to describe a complete address space.
With 2²⁵ bytes in the address space, a pointer must be 25 bits. If capabilities are 8 bytes long, this takes 3 bits of the address, leaving 22 bits. This 22 bit field can be broken in half, using 11 bits to select a capability in the current environment, and 11 bits to select a capability in a page of the current environment. Since each of these is 8 bytes long, this means a page contains 2¹⁴ = 16384 bytes.
11 did well on this, 3 gave no answer and 7 had strange and very small answers such as 8 bytes or 2⁸ bytes. Others had significant errors but were in the right ballpark.
Assume we've found a way to pass parameters on an enter() system call, but that the system contains no built-in return mechanism. Give a brief but clear justification for the convention that each domain always contains an enter capability for itself.
If there is no built-in return mechanism, but we can pass capabilities as parameters, then, if each domain has a capability to enter itself, it may pass this as a parameter when it enters another domain in order to allow that domain to return to the original domain.
12 gave good answers here, 10 gave either no answer or an answer that was, as nearly as I could determine, irrelevant. Perhaps five had confused answers that were worth partial credit.
Explain why it is necessary under DreadcOS to create a new domain for each process that might wish to execute a particular program.
Because DreadcOS stores the state of the current process in page zero of the domain of the domain of that process when it is not running, a new domain must be created for any program before a process uses the enter operation to execute that program.
12 had good answers for this, while 12 had bad answers. The most common error, a very severe one, was to confuse arguments of efficiency or probability with arguments of necessity. The arguments that it might be more efficient to create a new domain, or that the two processes may need different access rights, has no logical bearing on the question of necessity!
Assume DreadcOS C-lists are used to represent files and directories, so that all disk I/O occurs as a consequence of page faults, either those detected by the MMU or those detected by attempts to do put and get operations. What operating system characteristic determines the size of the queue of pending disk operations?
If all disk I/O is caused by page faults, then no process may have more than one outstanding disk request because no process may continue execution while one of its page faults is being serviced. Therefore, the length of the queue is limited by the number of processes that are not blocked awaiting non-disk activity.
2 gave good answers (mostly shorter than this!), and 2 more gave answers that were almost as good, but contained errors. 15 gave answers that were wrong. 3 talked about relevant secondary issues such as the effectiveness of the disk scheduler or the speed of the disk.
Assume all DreadcOS disk accesses are performed by the page fault service routine. Furthermore, assume that there is a disk scheduler. Does this imply that page faults cause CPU scheduler activity? Explain!
We would not add a disk scheduler to the system if we could not guarantee that there would sometimes be multiple pending disk I/O requests. If all disk I/O is caused by page faults, then no process may have more than one pending disk I/O request (because the process must be stopped until the page fault is serviced). Therefore, the only way to get multiple pending disk I/O requests is if each page fault causes the scheduling of another process while the page fault is being serviced. Therefore, this does imply that page faults cause CPU scheduler activity.
Nobody argued for the logical necessity of CPU scheduler activity as a consequence of the presence of a disk scheduler, in the style given above. 9 gave coherent yes answers based on the argument that performance would be better with CPU scheduling, while 8 gave coherent arguments that there was no necessity to schedule a new process during a page fault (but these did not notice that, in this case, the inclusion of a disk scheduler in the system is entirely foolish). 3 gave no answer, the remainder gave answers that were difficult to interpret or as much in error as correct.
Briefly describe an implementation of a UNIX-like fork operation under DreadcOS. Do not give pseudocode! That's far too much detail!
A new domain must be created for the new process. Then, the current domain can be scanned, copying all capabilities for read-only data pages into the new domain, and replicating all data pages that are read-write. If the caller's CPU state has already been saved in page 0 of the caller's domain, this will automatically replicate the caller's state, since page 0 must be a read-write page. If we assume open files are modeled with capabilities, we must copy all capabilities from the old domain into the new. Any object referenced by a capability with enter rights, however, should probably be replicated.
5 gave good answers, and a few suggested replicating all pages, including read-only pages, for a mild penalty. Some forced all pages to be shared, which seems to represent a misunderstanding of the UNIX fork. Only 3 gave no answer or a very bad answer. The remainder had poor or mediocre answers that were difficult to classify.
Under DreadcOS, shared objects and protected objects are implemented using capabilities, C-lists and an assortment of data pages. Why is this implementation undesirable for small objects such as typical linked list or binary tree elements.
Any item that must be protected separately from other items of the same type must be represented by a distinct page or pages. A binary tree element containing two pointers and, for example, an integer, will require, at minimum, a C-list for the two pointers plus a third pointer to a data page holding the number. The overhead of this representation (with a page size of 16K bytes) is immense!
3 gave good answers, one more gave a reasonable answer, 2 gave no answer, 5 gave very bad answers, and the remainder gave answers that were either vague or confused, and also, usually, very long.

Dreadco research announces that its product previously announced under the name DreadcOOL has been renamed

DrOOL: the Dreadco Object Oriented Language!

All the quality you've come to expect from the developers of DreadcOS!