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