Use your textbook, your notes, local on-line Unix documentation, your brain, or your psychic powers, but don't use other people, books, or Internet resources.

1. When I taught this course in 1994, I asked the students to rewrite Peterson's solution on page 37 of Tanenbaum for N=3. A typical answer to this homework problem looked like this:

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

   The following is Peterson's pseudo-code for his own n-process solution, from the 1981 paper cited in Tanenbaum. There are n processes numbered 1 through n. Q[] and TURN[] are shared variables, while j and k are local to each process.

   
   /* Code for process i */
   
   /* Enter region */
   for j := 1 to n-1 do
   begin
   	Q[i] := j;
   	TURN[j] := i;
   	wait until (for each k<>i, Q[k] < j) or TURN[j] <> i
   end;
   
   /* Critical section */
   Critical section;
   
   /* Leave region */
   Q[i] := 0;
   

   • Show what's wrong with the first solution by giving me a sequence of events that would lead to two processes being in their critical regions simultaneously.
   • In Peterson's solution, how is the order in which competing processes enter their critical regions determined? Is it possible for Process 1 to enter, execute, leave, and enter its critical region all while Process 2 is waiting to enter? (I recommend concrete examples as an expository tool here.)
2. Do problems 11 and 15 on pages 142-143 of Tanenbaum.
3. Suppose an operating system uses inodes to keep track of files. Suppose further that each inode contains 8 direct block numbers, and the block numbers for one single indirect block, one double indirect block, one triple indirect block, and one quadruple indirect block. Suppose blocks are 512 bytes long, and block numbers are 32-bit unsigned numbers.
   • How many data blocks can be addressed by the inode structure for a file in this file system?
   • How many distinct block numbers can be addressed with a 32-bit block address?
   • How many blocks fit on a 4Gb hard drive?
   • So what limits file size most in this example: the inode structure, the block number size, or the physical hard drive?
4. Here are a few questions about processes in Unix. You can answer these questions by writing simple C programs. Do so, and include the programs (and output, if appropriate) with your answers.
   • If a child process modifies a global variable called N, is N also changed in the parent? How about vice versa?
   • Suppose the parent opens a text file for reading before calling fork(). Suppose the parent waits for the child to terminate, and in the meantime, the child reads one line of text from the file. If the parent reads a line from the file after the death of the child, will that line be the first or the second line of the file?

     For this question, you should use open() and read() rather than fopen() and the standard C I/O library functions.

   • A process can call getppid() to find the process ID of its parent. If the parent terminates before the child, what happens to the ppid of the child? (Who takes care of the orphans, that's what I want to know!)