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

1. (12 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 2 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 2 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?

2. (12 points) Scheduling in Linux. You're going to need to dig through some code, but you might also consider using the web to get some help.

   • Which fields of the task_struct type (see sched.h) are involved in scheduling?
   • Summarize the scheduling algorithm used by Linux. Where relevant, provide references to the code (file names and line numbers).
   • Does the scheduling algorithm include anything to cause quick scheduling of processes that have been blocked waiting for input that has now arrived? If so, describe relevant parts of the algorithm. If not, sketch a plan to add this feature.

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 8KB, 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 half of its entries are valid, how many bytes of memory in our virtual address space actually reside in physical memory?

5. (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.)

6. (12 points) Take a look at the program badpingpong.c. This program is trying to use signals to cause the child and the parent to print alternating messages to stdout. The parent prints a message and then signals the child, then the child catches the signal, prints a message, and signals the parent, etc. Unfortunately, when I compile and run this program, it doesn't work.

   • Try running badpingpong.c and watching the parent and child processes using top. (Once top is running, you can type a capital A to sort the processes by age, which brings the badpingpong processes to the top of the list.) What happens? Are the two processes busy waiting or blocked? How can you tell?
   • Add some code that will help you determine which process gets scheduled first after the fork. Who goes first?
   • Use the information you've accumulated so far to explain why this program isn't working.
   • Consider badpingpong2.c, which is a slightly changed version of badpingpong.c. This one attempts to fix the order in which the processes get to do stuff, but it still has a problem. Run this program, describe its behavior, and explain why it is failing.
   • Go back to the original badpingpong.c, delete the pause() and kill() calls, and add two semaphores. Change the code to perform down and up operations on the semaphores in such a way that pingpong works, and it doesn't matter which process goes first. Call this bestpingpong.c, submit it via HSP, and submit a hard copy of the whole thing.