While taking this exam, you may use books, computers, the Internet, your own brain, and any divine guidance which may be available to you. You may, in addition, ask Jeff Ondich questions and expect at least a cordial "I can't tell you that." Otherwise, don't talk to other people about the content of the exam.

Have fun.

1. (12 points) Elmo wrote the following a long time after bedtime. He intended for this code to be a busy waiting solution to the mutual exclusion problem for an arbitrary number of processes.

   
   	// Shared global variable, initialized to 0.
   	int		lock = 0;
   
   	void EnterCriticalRegion( void )
   	{
   		while( lock == 1 )
   		{
   			lock = 1;
   		}
   		lock = 1;
   	}
   	
   	void LeaveCriticalRegion( void )
   	{
   		lock = 0;
   	}
   

   The next morning, Zoe, having had a full night's sleep, read Elmo's code. The orange fur was flying as Zoe ran to Elmo's cubicle, poured out all his remaining cans of Mountain Dew, woke him up, sent him home, signed him up for a software engineering workshop, and sent him e-mail telling him that if he ever held another all-night coding session, he could start looking for a new job.

   When Elmo returned from the workshop a few days later, he found a hard copy of his code taped to his monitor, with a hand-written note from Zoe saying "Busy waiting, races, deadlock, and starvation, all in 16 lines of code (including blank lines and comments). Brilliant!"

   Explain how Elmo's code can lead to race conditions, deadlock, and starvation. That is, list a possible (and, preferably, plausible) sequence of events that would cause a race condition. Then do the same for deadlock and starvation.
   
   

2. (15 points) Answer the following questions about context switching in Linux on an 80x86. You may wish to look at the code in /Accounts/courses/cs307/linux/kernel/sched.c and /Accounts/courses/cs307/linux/include/asm-i386/system.h, and maybe others. Please include file and line number references in your answers.
   • How does the page directory (that is, the top-level page table) get switched?
   • Is there a global variable of some kind that keeps track of the current process? If so, what is its name, and where does it get changed during a context switch?
   • What sort of data structure is used to keep track of non-running processes? (Linked list? Heap? Something else?)
   • Where in this data structure does the previously running process get placed?
   • Where does the state (registers, program counter, page directory address, etc.) of the previously running process get stored?
   
   
   
3. (5 points) Discuss the following argument against threads. "Threads are often referred to as 'light-weight processes,' and are praised for their support of very fast context switching. But this fast context switching only occurs while the parent process of a group of threads remains in control of the processor. As soon as some other process needs to be scheduled, we're back to slow context switches. Since processes need to be scheduled just as often in a threaded system as in a non-threaded system, there's no performance benefit gained from adding the thread abstraction to the system."
   
   
4. (3 points) For you seniors and juniors, here's one last chance to tell me a joke. For the rest of you, maybe you'll get another chance in 1999-2000.
   
   
5. (12 points) UNIX, MacOS, and Windows 95 all have ways to refer to a file by a name different from its original name. You can create UNIX hard links with the ln command, UNIX soft links with ln -s, MacOS aliases using the File menu's "Make Alias" item, and Windows 95 shortcuts using the File menu's "Create Shortcut" item. For each of these four cases, answer the following questions.
   • What happens if you move the original file and try to access the link/alias/shortcut (by running "cat linkname" or by double-clicking on the alias/shortcut icon)?
   • What happens if you move the link/alias/shortcut before trying to access it?
   • What happens if you remove the original file and try to access the link/alias/shortcut?
   • Of what does the link/alias/shortcut consist? How does your answer to this question explain the differences in behavior you observed above? (This question is going to require a little research. Bach's UNIX book and the Files volume of Inside Macintosh are available on closed reserve in the Math Skills Center. To get Windows 95 information, you'll probably need to check out Microsoft's developers' Web site.)
   
   
   
6. Have a great summer and beyond. Keep in touch.