This exam is open-book, open-notes, open-computer, open-Internet, and closed-other-people.

1. (5 points) Consider Peterson's solution to the mutual exclusion problem, as shown in Figure 2-8 on page 37 of Tanenbaum. Suppose you try to modify it to handle three processes by changing N to 3, and changing enter_region to look like this:

   
       void enter_region( int process )
       {
           int other1 = (process+1) % 3;
           int other2 = (process+2) % 3;
           interested[process] = TRUE;
           turn = process;
           while( turn == process  &&  (interested[other1] == TRUE || interested[other2] == TRUE) )
           {
           }
       }
       

   Using processes numbered 0, 1, and 2, describe a sequence of events that would cause a race condition with this version of enter_region.

2. (10 points) Suppose we have a collection of processes, each of which does ten iterations of the following sequence: wait 1 second for file input, and then do 3 seconds of computation. Furthermore, suppose context switches take 10 milliseconds. Assuming a round-robin scheduling algorithm, answer each of the following questions for 1 process, 2 processes, and 10 processes, and for quantum sizes of 100 milliseconds and 500 milliseconds (yes, that's six cases). Assume that all processes are ready to run at time zero.

   • What is the CPU efficiency? (That is, the percentage of time the CPU is doing the "do 3 seconds of computation" part of some process.)
   • What is the throughput? (That is, the number of jobs completed per time unit of your choice.)
   • What is the average time to completion for all the processes.
   • What are the morals of the story? More precisely, what can you say about the relative merits of smaller and larger quanta, and of more or fewer processes?

3. (8 points) Questions about fork(). Don't just answer the questions; provide some evidence for your answers.

   • Suppose your program is called with a command like "yourprogram | wc", and then yourprogram calls fork(), and both the parent and the child print to standard output. Which process or processes, if any, send data to wc?
   • Suppose your program opens a file for reading and then calls fork(). If both the parent and the child read from the open file, do their read operations interfere with each other?
   • Same question as the previous one, but this time, suppose the file is open for writing.

4. (8 points) Suppose we are using a 2-level page table system in which logical addresses are 32 bits long, each second-level page table entry takes up exactly 32 bits, and each second-level page table takes up exactly one page. Suppose further that the page size is 16KB, and the paging system supports LRU page replacement.

   • Show a diagram of the second-level page table entries. What assumptions about physical RAM does this system make?
   • How big is the top-level page table?
   • Assuming that exactly one second-level page table is in memory and exactly one quarter of its entries are valid, how many bytes of memory in our virtual address space actually reside in physical memory?

5. (5 points) The Unix System V-based file system for Linux uses i-nodes that contain 10 direct block pointers, 1 single-indirect block pointer, 1 double-indirect block pointer, and 1 triple-indirect block pointer. If each block is big enough to hold 1024 32-bit block pointers, what is the maximum file size?

6. (5 points) Create a Unix file A. Then create a hard link B to A (using a "ln A B"), create a soft link C to A ("ln -s A C"), and finally delete A ("rm A"). Now execute "cat B" and "cat C". What happens in each case, and why?

7. (2 points) I've got some extra professional development money I need to spend in the next month, and I want to spend it on computer books. What's your favorite computer-related book? (It's okay if I already own it--I'm also curious about what books you like.)

8. (10 points) Write a program that creates two child processes. Call the three processes A, B, and C. Arrange for the three processes to produce output in this order: A, B, C, B, A, B, C, B, A, B, C, etc. with enough delay between the output statements that it's easy to watch the output flow by (maybe two lines of output per second or so).

   Here's the trick, though. I want you to do the synchronization entirely with binary semaphores. Nothing like a mutex plus a "whose turn is it?" sort of variable. Just processes going to sleep by doing a down on some semaphore, and waking up when some other process does an up on the same semaphore. Elegance will be rewarded on this one, so try to figure out a system that uses as few semaphores and as little code as possible.

   Hand in via HSP.