Midterm

22C:116, Fall 1997

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).

1. Background: The virtual address space of a process under a typical UNIX system has 3 segments: a code segment, a stack segment and a data segment. Initially, the data segment contains all statically allocated variables in the program, including a statically allocated description of an empty heap. The sbrk(i) system call increases the size of the data segment by at least i bytes (the size is rounded up to the nearest multiple of the page size) and returns a pointer to the start of the newly allocated area. If for any reason the system cannot allocate memory, sbrk returns -1 (this is probably a minor design error, as NULL would be more appropriate in this context).

   Part A: Assuming that sbrk() operates exactly as described, write pseudocode to compute the page size of the system using two consecutive calls to sbrk(). (This takes 3 statements at the very most!) (1 point)

   Part B: There are 3 quite different reasons that sbrk() could fail. The one that depends on specific details of UNIX is: A failure will occur when a user attempts to allocate more memory than that user's resource limit. The other two reasons have nothing to do with UNIX and depend only on details of paged virtual memory. What are they? (1.5 points)

2. Background: Consider a machine with multiple virtual address spaces, one per process. Each process has a virtual address map (page table) that indicates, for each page, where that page is currently stored and what rights the process has to that page. Processes may share pages.

   Part A: What information must each entry in the page table contain? Emphasize any details that differ from the page table on a system with a single address space. (1.5 points)

   Part B: How would you change your answer above if all pages (whether shared or not) were organized into segments -- where a segment is defined as a sequence of pages that are inserted into consecutive virtual addresses of a user's address space on an all-or-nothing basis. (1.5 points)

   Part C: How would you change your answer if it was legal to open a file "into" the virtual address space of a process, as in MULTICS. (1.5 points)

3. Background: Consider a machine where each page in the virtual address space may either contain data or may contain capabilities for other pages. Each entry in the page table for a virtual address space is a capability. The access rights for data pages are the usual read and write. The access rights for pages that hold capabilities are read-cap and write-cap. A user with read-cap rights to a page may read a capability from that page into that user's page-table. A user with write-cap rights to a page may copy any entry from the user's page table into that page.

   Part A: What minimal condition guarantees that a user will not be able to create a capability for a random page in memory. (This condition will typically be violated in only one place -- the memory manager, which must be able to create capabilities for any page in memory.) (1.5 points)

   Part B: Suppose a user on this system wishes to pass a capability for a page to some other user. What prior condition must exist to allow this? (1.5 points)

   Part C: How can you model this system with an access matrix? Pay special attention in your answer to how the contents of the access matrix may be modified under this system! (1.5 points)

4. Background: Consider a minimal process manager for a small computer system (with no MMU to clutter up the picture). This would use a real-time-clock to allocate slices of processor time to processes, and it would allow the usual operations on processes.

   Part A: What is the minimal set of object classes this process manager should support and what are the basic operations applicable to members of these classes? (Note: In answering this question, a limited amount of object orientation is worth quite a bit, but excessive object orientation can get you bogged down in near-nonsense.) (1.5 points)

   Part B: What lower-level resource manager would need to be implemented first, in order to support the process manager? That is, what resource manager is required by one or more process manager operations. (1.5 points)

5. Background: Consider a system where all I/O involves use of a shared pool of buffers. To write to a disk, a user allocates a buffer from the pool, fills it, and then schedules that buffer for output to the disk; the disk interrupt service routine deallocates the buffer when the operation is complete. When a character arrives at the input interrupt service routine, a buffer is allocated, if needed and then the character is put in that buffer. When the buffer fills (or some other condition is met such as end-of-line), the buffer is placed in the serial input queue, ready to be handed to any user wishing to read serial input data. Users reading the serial input line await a buffer in this queue, process its contents, and then deallocate the buffer.

   Part A: Describe, in about as much detail as was given above, how a user would read the contents of a disk sector. Pay particular attention to questions of who allocates or deallocates buffers. (1 point)

   Part B: For the example given involving disk I/O, what goes in the disk request queue and how does this differ between input and output requests? (1.5 points)

   Part C: One specific design detail is not addressed in the background information above, but you may have accidentally solved it in your answers to parts A or B. Supposing that, on input, the disk interrupt service routine is responsible for allocating buffers, how would (or how did) you allow the user to learn what buffer had been allocated? (1.5 points)

   Part D: Does this system pose risk of deadlock? Explain! (1.5 points)