Midterm

22C:116, Spring 1997

1. Background: Some modern disk drives have a variable clock rate, so that the data is recorded at a higher number of bits per second when recording the outer cylinders of the disk drive than is used on the inner cylinders. The disk rotates at a constant speed, so the result is a nearly constant linear information density (in bits per inch, for example). For modern file systems, the sector size is usually fixed over the entire drive, so the result is a variable number of sectors per track.

   Part A: (2 points) Given a linear disk address (sector number on disk), propose an appropriate class of algorithms to use for converting this to [cylinder, track in cylinder, sector in track] form on such a disk.

   Part B: (2 points) What impact does such a nonlinear data rate have on disk scheduling algorithms?

2. Background: In the Cambridge CAP file system, as in UNIX, there were two kinds of files, data files and directories. Data files contained uninterpreted byte strings, while directories contained file names and pointers (in a logical sense) to the named files. Unlike the UNIX file system, the access rights for a file on CAP were carried with the directory entry, so two different directories could confer different access rights to the same file. Also unlike UNIX, there was no requirement of a tree structure in the CAP file system, and in fact, once a user logged in, the root for all pathnames issued by that user was that user's home directory and not a global file system root.

   Part A: (2 points) How can instructional computing be managed on the CAP system? The instructor I and teaching assistant A should have access to all student files, but students should have no access to the instructor's or assistant's files. The instructor and assistant should share access to the gradebook, and the assistant should have no access to the exams the instructor is preparing.

   Part B: (2 points) How can user A give user B access to some specific file F on the CAP system, while avoiding giving the rights to F to user C? Assume that A, B and C each have a personal root directory, and that you are free to establish any initial set of subdirectories under A, B and C to allow this controlled transfer of rights.

   Part C: (2 points) Suppose user A on the CAP system has given rights to file F to user B. Now, user A wants to make changes to F that should not be seen by B. What should user A do? (Note that the above description of the CAP file system does not provide A with a way to take back a capability that has already been given to another user!)

3. Background: The UNIX pipe(fildes) system service returns a pair of open file descriptors; all data written on fildes[1] is put into a bounded buffer and can be read from fildes[0]. This pair of file descriptors and the bounded buffer connecting them is called a pipe. A read from an empty pipe blocks the reading process. A write to a full pipe blocks the writer. Traditionally, the capacity of a pipe is 512 bytes, but newer versions of UNIX have higher bounds.

   The UNIX read(p,buf,len) and write(p,buf,len) system services are atomic in their interactions with pipes. For example, once a process begins to read from pipe p, no other process will be able to read from that pipe until len bytes have been transferred to the buffer of the first process. The read() and write() operations return the number of bytes read or written; normally this is equal to len.

   The UNIX fork() system call causes the creation of a new child process. running in the same code segment as the caller, with a copy of the caller's data segment (stack and heap) and sharing all open files with the caller. On return from fork, parent and child processes have identical program counters, but the process ID of the child process is returned to the parent while zero is returned to the child.

   Part A: (2 points) Consider the following code fragment, where 2 processes are created that communicate through a pipe, where each process can both read and write that pipe. The specification for pipes given above makes it clear that each process can block the other in a few different ways.

   	pipe(fildes);
   	if (pid = fork()) { /* parent */
   		a: ...
   	} else { /* child */
   		b: ...
   	}
   

   Give sequences of instructions for the blocks of code labeled a and b above that lead to a deadlock.

   Part B: (2 points) On a UNIX system where all interprocess communication is through pipes as defined above, is deadlock detection feasible? (Note that such a system may not be useful, but that we are considering the possibility for academic purposes despite this.) You may want to consider the following subproblems: What deadlock model is applicable? What kind of deadlock detection algorithm applies to that model? Is the problem sufficiently well defined and well bounded that deadlock detection is feasible?

   Part C: (2 points) Do the definitons of the services given above suggest a natural action to take to resolve any deadlocks detected?

   
   
   
   
   
   
   
   
   

4. Background: Consider a system where the operating system provides a separate address space for each user process and manages the physical memory resources (page frames) of the process, but does not manage virtual memory resources. Instead, the system allowes user processes to use the following set of memory management services:

   r = alloc(va) causes a page frame to be allocated to the virtual address va in the caller's address space; the return value r is one of no_mem indicating that no page frame was available for allocation, no_need indicating that a page was already allocated for that virtual address, or success indicating that a new page was allocated. In case of success, the newly allocated page will contain unspecified data and will have its access rights set to read_write.

   r = set_ar(va,r) sets the access rights of the page at virtual address va to r, which must be one of read_only or read_write. The return value r gives the old rights to the page, or failure if no page frame was currently mapped to that address.

   r = dealloc(va) causes the page frame allocated to the virtual address va to be unmapped from the caller's virtual address space and returned to the system. The retun value r will be success if a page frame was allocated to that address, or failure if not.

   on_va_fault(proc) causes the caller's procedure proc(va) to be called when the user attempts to address a virtual address that is not currently mapped to a page in the caller's virtual address space. On entry to proc(), va gives the virtual address that was referenced to cause the fault, and proc() is called in such a way that, on return, it will restore the state of the computation to the state prior to the trap and retry the instruction that caused the trap.

   Part A: (2 points) Outline the structure of the fault handler proc() that a user could use to provide demand paged virtual memory for part of the address space of a process using a random-access disk file for backing storage.

   Part B: (2 points) Discuss the alternative page replacement policies your fault handler could use, with reference to such alternatives as using the mark-sweep algorithm or distinguishing between clean and dirty pages.