Final Exam

Name: ________________________________________________

ID Number: ___________________

Please write your answers in the space provided! Make sure your name is in the same form as it appears on your University ID card! Illegible and excessively long answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam is worth 1/5 of the final grade (20 points; allocate 2 minutes per point).

1. Background: Consider the problem of implementing macros -- whether in assembly language, a high-level language preprocessor, or a command language, it doesn't matter.

    

   • i - One way to do this, discussed at length in the notes, is to store the macro body in RAM (for example, in the string pool). In this case, the macro symbol table associates the macro name with the memory address where the macro body is stored.

   • ii - Another way to do this is to "bookmark" the source file at the point where the macro body begins, for example, by saving the offset in bytes from the start of the source file where the macro begins. In this case, the macro symbol table associates the name with this offset.

   a) What difference in processing speed would you expect between these two, and why? (if it matters, assume lots of macro calls, no macro parameters and no disk cache) (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

   b) One of these models does not allow preprocessing of the macro body in order to speed the substitution of macro actual parameters for macro formal parameters. Which does not, and why? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

    
   

2. In a buddy system heap manager, you need to compute 2ⁱ frequently. What expression computes this efficiently in C, C++ or Java? (the answer is the same in all three.) (1 point)

   ______________________________________________________________

    
   

    
   

3. Background: Consider an operating system where, when a page fault occurs, the running process is simply stopped, and a message is delivered to that process's supervisor telling it that this happened (and nothing more). The supervisor of a proces is just another process, but because it is the supervisor, it has the right to perform the following opertions on the process it supervises:
   • start it,
   • stop it,
   • peek into its memory address space,
   • poke new values into its memory address space,
   • attach a new uninitialized frame to a specific page of its address space,
   • detatch a frame from a specific page and make it free,
   • inspect all of its registers, and
   • modify any of its registers.

   The supervisor of a process on this system can implement demand paged virtual memory, even though the supervisor cannot directly access the MMU or access any MMU registers.

   a) With reference to the above operations and normal file system operations, how does the supervisor clean a page frame and transfer its contents to disk? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

   b) What page replacement policies can the supervisor implement, and what feature of this system prevents it from implementing better policies. the supervisor would perform in response to a page fault message. (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

   c) What does the supervisor do in order to determine the specific page in the process's address space that caused the fault? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

   d) What does the supervisor do at the point where a normal page-fault service routine would return to the process that caused the fault? (1.0 point)

   ______________________________________________________________

    
   

4. The expression (i ^ (i - 1)) >> 1 in C, C++ and Java, gives a result with ones in each bit position where the variable i had trailing zeros, and zeros elsewhere. Where would this be useful in the implementation of a buddy-system heap initializer? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

    
   

    
   

5. Background: Consider a classical Unix file system where each file is described by an i-node. Assume all files and directories are small (1 sector), and assume that none of the relevant data is in RAM to start with.

   a) The program executes int fd = open("/a/b.txt", O_RDONLY); how many disk accesses are required? (1.0 point)

   ______________________________________________________________

   b) And then, the program executes read(fd, buf, 1); how many additional disk accesses are required? (1.0 point)

   ______________________________________________________________

   c) When the user process does read(fd, buf, 1);, it only reads one byte of data. Does the DMA hardware directly read from disk to the user's buffer buf? If not, how does the data get there? (1.0 point)

   ______________________________________________________________

    
   

6. Background: Consider two different allocation policies for a heap manager:
   • i - first fit, with no separate free-list and the search always starting from the beginning of the heap.

   • ii - circular scan, with a separate free-list linking only free blocks.

    
   a) Which policy is likely to improve the locality of reference in a demand-paged virtual memory environment for applications that make intensive use of the heap? Why? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

   b) Which policy is likely to lead to faster searches for a large enough free block if there are no page faults, and what slows down the other policy? (1.5 points)

   ______________________________________________________________
   
   ______________________________________________________________
   
   ______________________________________________________________

    
   

7. Background: Assume a disk with 12 sectors per track. With no interleaving, which is the same as one-way interleaving, these are in the order 0-1-2-3-4-5-6-7-8-9-A-B.

   a) Aside from one, what interleaving factors make sense here? (1.5 points)

   ______________________________________________________________

   a) Show the order of the sectors with the smallest of these. (1.5 points)

   ______________________________________________________________