Midterm

22C:116, Fall 1999

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: Several questions on this exam relate to an operating system with the following structure:

Each process has a distinct virtual address space. A UNIX-style fork() system call is used to create processes, and the share(a) system call will marke the page containing virtual address a as shared. This sharing takes place with all subsequent fork operations applied to that process or one of its descendants. A single disk (or virtual disk) must be designated as holding the "swap space" for all processes.

Users access the file system using a UNIX-style read(f,buf,len) system call, where f designates an open random-access stream, buf is the virtual address of a buffer, and len is the length of that buffer in bytes.

System calls force a trap. This trap changes the protection system from user state to system state. In user state, the memory management unit is turned on and addresses issued by programs are interpreted as virtual addresses. In system state, the memory management unit is turned off and addresses issued by programs are interpreted as physical addresses.

Inside the system, there is a UNIX-style read(f,buf,len) function, where f designates an open stream, buf is the physical address of a buffer, and len is the buffer length in bytes. User calls to read() are translated by the system-call trap service routine into calls to this system-level function.

The disk I/O driver itself supports post_request(q,buf,sect,op,done), where, q names the request queue of a disk drive, buf is the physical address of a buffer in memory, sect is the disk address of a sector on disk, op is either read or write, and done is a semaphore that the I/O driver signals when the transfer is complete.

1. A Question: For the example system, what must be done between the time the system-call trap service routine determines that the trap was caused by a user calling read() and the time that routine calls the internal read() function? (2 points)

2. Background: Consider the following outline for a page-fault-handler for the example machine:

   	page fault handler:
   	   s = local semaphore, initially 0
   	   va = virtual address that caused fault
   	   p = process running at time of fault
   	   op = operation (read or write) attempted
   	   if op not permitted by p.page_table[va.page]
   	      send signal to process p
   	      abnormal return from handler
   	   f = frame to replace
   	   post_request( swap_space, frame_address(f),
   	                 frame_table[f].sector, write, s)
   	   wait(s)   
   	   post_request( swap_space, frame_address(f),
   	                 page_table[va.page].sector, read, s)
   	   wait(s)
   	   frame_table[f].sector = page_table[va.page].sector
   	   page_table[va.page].valid = true
   	   inform mmu of changes (if this is needed)
   	   normal return from handler
   

   The above pseudocode is intended to correctly represent something workable in the context of a single-user system.

   The Problem: The above pseudocode will not work correctly in the presence of shared memory. Why? (2 points)

3. Background: The hardware supporting the example operating system has two complete sets of registers in the CPU (not counting the program counter), with a bit in the processor status word that selects between these. In user state, it is illegal to change the register-set-select bit. In system state, this bit may be freely changed.

   Part A: If, as in the previous problem, internal code within trap handlers is allowed to call wait() on a semaphore, possibly suspending the current process, what consequences does this have for the representation of the state of a blocked process? (1.5 points)

   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? In this case, if a system call must block, it must put the user process in a blocked state and then schedule some other process. The remainder of the work required by the system call would have to be passed to interrupt service routines or to independently scheduled system processes. (1.5 points)

4. A question: Give high level pseudocode for the fork() system call, emphasizing the issues surrounding address space management and shared memory. (3 points)

5. Background The RTS/CTS flow-control protocol relies on two characters, RTS and CTS, that are exchanged between the sender and receiver of data. Prior to sending the next N bytes of data from A to B over a bidirectional communications line, A must send RTS and then await CTS. On receipt of RTS, B will respond with CTS, but the response will be delayed until there are N bytes of free space in B's input queue.

   At each end of the communictions line, we have the following components:

      user    ||        driver       ||     hardware
              ||                     ||
              ||              transmit|
   	putchar()  --q1--  interrupt
              ||              routine||
              ||                     ||----- line
              ||              receive||
   	getchar()  --q2--  interrupt
              ||              routine||
   

   Part A What component listed above should send RTS and block awaiting CTS? (1 point)

   Part B What component listed above should detect the arrival of CTS and unblock the waiting component? (1 point)

   Part C What component listed above should detect the arrival of RTS and begin the computations that lead, eventually, to sending CTS? (This component may enqueue CTS for immediate transmission immediately if there is already space for N characters.) (1 point)

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

6. Background: Consider a file system where access to sector n of file i is accomplished by looking up the key [n,i] in a B-tree for the entire disk. The B-tree associates a sector-number with each key. Assume that the pair [n,i] is 64 bits, with 32 bits for each field.

   Assume that disk addresses are also 64 bits, and that each sector holds 4K bytes. If the B-tree uses one disk sector per node, each leaf node holds 256 keys and their associated data, and each internal node holds pointers to up to 256 other nodes. Therefore, if there are n allocated sectors in the file system, access to any particular sector of a file, given that file's number i, will take log₂₅₆n disk accesses.

   Part A: What functions of the UNIX I-node does the above scheme replace, and what functions of the UNIX I-node are not addressed by the above scheme? (1 points)

   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? (1 point)

7. Background: Consider a UNIX-like file system where the access rights field of each I-node is eliminated, and where the information stored there is stored, instead, in each directory entry referring to that file. Thus, directory entries now consist of triples [name,i-number,rights], and we have the possibility that the rights a user obtains to a file might depend not only on who the user is but on the path the user takes to the file.

   Assume that we eliminate the owner/group/other scheme of UNIX and list, for each file, only one set of rights, the rights granted by that path to the file.

   Note also that the chroot() command under UNIX changes the root of the file system to some subtree of the file structure initially accessible to the caller.

   Part A: This scheme contains features analogous to capabilities and capability lists. Explain what these are! (1 point)

   Part B: What is a protection domain under this scheme? (1 point)

   Part C: What operation in this scheme serves as a gate-crossing operation? (1 point)

   Part D: As given here, does this scheme solve the mutual suspicion problem? Why or why not? (1 point)