CS307
Midterm
Ondich
Due in class on Friday, May 3, 2002

This exam is open-book, open-notes, open-computer, open-Internet, but closed-other-people. You may, however, ask Jeff Ondich questions.

Explain your answers.

Don't use prism.

1. (8 points) Consider Peterson's solution to the mutual exclusion problem, as shown in Figure 2-21 on page 106 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. (4 points) What Unix commands would you use to:

   • determine which processes are running under your user name
   • terminate a process running under your user name
   • determine whether there are shared memory segments and/or semaphores associated with your user name
   • remove shared memory segments and/or semaphores associated with your user name

   Please make clear the complete commands you would use, including, if appropriate, command-line arguments. (This is intended to be not a difficult exercise, but rather a formal reminder of how to clean up after yourself.)

3. (8 points) Suppose we are using a 2-level page table system in which each second-level page table takes up exactly one page, and we have a 32-bit virtual address space with 4KB pages and 4 bytes per page table entry.

   • How many bytes will each program need to use to store the first-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?
   • Why must the first-level page table always be in memory? What would happen if it weren't?

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

5. (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 betterpingpong.c, which is a slightly changed version of badpingpong.c. This one works better, but 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.