Midterm Comments and Solutions

22C:116, Fall 1997

Grade Distribution 

Median = 5.5         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. 15.

Solutions

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

    	i = sbrk(1)
	j = sbrk(1)
	pagesize = (int)j - (int)i
    This answer was fairly common, but about half the class gave entirely nonfunctional code or extremely complex algorithms to solve this problem.

    Part B: There are 3 quite different reasons that sbrk() could fail:

    There were many students who began going into great detail about page faults in response to this question. Few were able to organize a coherent answer. although a quarter of the class did fairly well.
  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.

    This question was almost a trick question. The big differences between a system with one address space and a system with many address spaces are in the frame table, not in the page table entries. Students who did not understand the distinction between frame table and page table gave some very complex answers!

    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.

    Here, a small number of students proposed, correctly, that a two-level table structure was appropriate, where the access rights would be handled at the segment level, while the page table would only show locations of pages. Some students gave elaborate diagrams of virtual address structure, implying something sensible, without saying much.

    Again, the major impact of this design approach would be on the frame table and on the data with each segment (not in the page table) used to keep track of what processes have access to what segments.

    Some students proposed that each page table entry should give segment number and offset in segment for that page. This is an unconventional but very useful idea, and it allows the address space to be segmented without interpreting some range of bits in the virtual address as being the segment number.

    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.

    Few students gave answers here that were worth even partial credit. Those that did were in the final group listed above. They proposed that each page table entry could have a bit to indicate whether the page was part of a file, and in that case, the location of the page would be in terms of i-node number and page-number in file.

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

    This should have been an easy question, but nobody received full credit and only a few received partial credit. The solution is that no user should have both write-data and read-cap rights to a page. A surprising number of students asserted that no user should have read-cap rights to any page, a solution that makes the entire system useless.

    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?

    Again, this should have been easy, but only 4 students had workable answers. To pass a capability from process A to process B, process A must have write-cap rights to a page, and process B must have read-cap rights to that page.

    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!

    Each page is an object, with a column in the table; each user has a row in the table corresponding to that user's virtual address space, but because the user is allowed to perform operations on the user's space, the space is also an object.

    The rights applying to pages are read-data, write-data, read-cap and write-cap. The rights applying to the user's address space are also read-cap and write-cap. The the read-cap and write-cap rights are always present for the user's own address space. The read-cap operation copyies capabilities from a page to the user's C-list, and the write-cap operation does the reverse.

    A remarkable number of students simply drew an access matrix and provided no interpretive text to help relate this to the question.

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

    The most obvious class is process, with operations create and destroy.

    If you want to support the classic states of a process, you need a second class, semaphore, with operations wait and signal.

    The implementations of semaphores and processes are entangled in a manner that is poorly suited to the object oriented paradigm.

    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.

    The most crucial resource manager on which this rests is a memory manager so that storage for the representations of processes and semaphores can be allocated.

    While not strictly necessary, a queue manager would be handy, since queues of processes are central to the implementation of both the scheduler's ready list and to the implementation of semaphores.

    A low level interface to the real-time clock is needed for preemption, but it's not clear that this is a resource manager; in fact, the real-time-clock interrupt service routine could be the scheduler's preempt mechanism, with no further management required!

    Nothing in the problem statement mentioned I/O or file systems, yet many students listed considerable detail in that area, severely distracting themselves from the central issues of the question.

  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.

    The user could allocate a buffer and schedule it for reading; the disk interrupt routine would initiate reading into this buffer, and when complete, it would signal the user that the read is done. The user would then process the data and deallocate the buffer.

    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?

    The final field listed above is needed only on read, since the write routine takes the buffer and deallocates it.

    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?

    The above answers do not anticipate the above suggestion at all. Here is an alternate answer to parts A and B that anticipates this:

    The user could schedule a read request; the disk interrupt routine would allocate a buffer and initiate reading into this buffer, and when complete, it would signal the user that the read is done. The user would then process the data and deallocate the buffer. The disk queue entries would look like the following: