Midterm

22C:116, Fall 2000

This exam is open-book, open-notes, closed neighbor!

NOTE: Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here!

This exam is worth 1/5 of the final grade (20 points; allocate 2 minutes per point).

Background: The DreadcOS system allows each page of the virtual address space to be marked with some subset of the rights {Read, Write, Read-C, Write-C, Enter}.

• Recall that get-c(a,b) reads a capability into address a of the virtual address space from a C-list entry designated by b.
• Recall that enter(a) if permitted, causes the current process to abandon the domain it is currently executing in, and enter the domain referenced by the capability in the addressed page-table entry. On entry, the initial process state is loaded from the first part of page zero of the new domain.
• Recall that DreadcOS stores the current process state in the first part of page zero of the address space of a domain whenever a process in that domain changes from running to ready or waiting.
• Assume that current points to the page-table of the current process.
• Assume that address(page,byte) composes an address from the page number and byte-in-page.
• Assume that address_c(page,cap) composes an address from the page number and capability in page.

              cap ______                    byte______ 
  current ---> 0 |_R__W_|    cap ______      0 |______|
               1 |______|     0 |______|     1 |______|
               2 |__RC__|---> 1 |_R__W_|---> 2 |______|
               3 |      |     2 |______|     3 |__X___|
                   :  :       3 |      |     4 |      |
                                  :  :           :  :  

1. 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. (2 points)

2. 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. (2 points)

3. 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. (2 points)

4. 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. (2 points)

5. 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. (2 points)

6. Explain why it is necessary under DreadcOS to create a new domain for each process that might wish to execute a particular program. (2 points)

7. 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? (2 points)
   

   
   

8. 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! (2 points)

9. Briefly describe an implementation of a UNIX-like fork operation under DreadcOS. Do not give pseudocode! That's far too much detail! (2 points)

10. 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. (2 points)

Coming soon from Dreadco: DreadcOOL,
the Dreadco Object Oriented Language!
All the quality you've come to expect from the developers of DreadcOS!