McGill University
Department of Electrical Engineering
Operating Systems
304-427A

Midterm exam
Oct. 15, 1998.

Instructions

  1. (20 points)
    In an effort to decrease the overhead in UNIX process creation, someone suggests that the two system calls, fork() and execlp(), be replaced with the following new primitive:

    createProcess(char *prog, char *arg1, char *arg2, ... (char *) NULL)

    This function creates a process with the text of the program specified by the first argument and begins execution by supplying the remaining arguments. Explain the justification for this new function, specifically, what inefficiency does it address? Then, argue against this function and explain why we would not want it to replace the fork() and execlp() calls.

    The inefficiency of fork() is that it must copy the entire address space of the parent into a new area of memory allocated to the child. In the case that the child simply goes on to execlp() a new process, this effort is wasted, as the address space will be replaced by the execlp() call. However, as we learned from the readings, the point of keeping these two calls separate is that the child often needs to manipulate file descriptors inhereted from the parent before replacing the process image, for instance, opening as stdin a file created by the parent.

    A simple example illustrates this: 

    ...
datafd=open("datafile", O_RDWR|O_CREAT, 0644);
...
/* Some data is written by the parent to the file */
...
if (fork()==0)
{
    close(STDIN_FILENO); /* Only child's stdin is closed */
    open("datafile", O_RDONLY); 
    execlp("sed", "sed", (char *)0);
    perror("sed");
}
    which, of course, is more elegantly handled using the dup2() call.

  2. (20 points)
    Referring to the following state transition diagram, what purpose does differentiating the SUSP READY (suspend-ready) and SUSP BLOCKED (suspend-blocked) states serve that could not be satisfied by a single SUSPEND state? Is the activate transition from SUSP BLOCKED to BLOCKED unnecessary or does it serve some useful function? 
    
                              exit
                   RUNNING -----------> EXITED
                    ^   | \
                    |   |  \______ request
           dispatch |   |timeout  \_____
                    |   |               \
      admit         |   v complete       v
NEW ----------> READY <----------- BLOCKED
                ^   |               ^   |
                |   |      activate |   |susp
       activate |   | susp          |   |
                |   |               |   |
                |   v      complete |   v
                SUSP READY <-------- SUSP BLOCKED
    The suspend-blocked state is used when the address space of a process is copied from the more valuable (and in high demand) main memory to external storage while it waits on a resource request. Once the request is satisfied, the process can be moved to the suspend-ready state with minimal overhead. Differentiating these two states permits the scheduler to swap back to main memory (activate) a process that is known to be ready for the CPU rather than one that is still blocked on a resource request.

    The suspend and activate transitions between blocked and suspend-blocked permit a parent process to control the operation of a child through requests to the process manager, regardless of whether the child is blocked on a resource request. If the child is blocked and suspended, the parent may still swap it back to main memory (activate it), thus allowing the child to continue once the resource request is satisfied.

  3. (20 points)
    The following code is a frightening attempt to generate a number of child processes as specified by the user on the command line, each of which calculates the Fibonacci number corresponding to the loop counter, then sends the result over a pipe to the parent. Aside from the obvious inefficiency of starting a separate child process to calculate each Fibonacci number separately, there are at least 12 problems with the code, most of which will prevent correct execution. Identify these problems individually, and suggest appropriate solutions. Assume that the Fibonacci() function is provided and works correctly. Note that the line numbers are provided for your reference only; they are not part of the code. 
     
1	#include <stdio.h>
2	#define LINE_LEN 50

3	main (int argc, char *argv[]) {
4		int i, n, child_pid, c2p[2];
5		int nbytes, total_bytes_read;
6		char buf[LINE_LEN];

7		n = argv[0];
8		total_bytes_read = 0;	/* initialize variable */

9		for (i = 0; i <= n; i++) {
10			child_pid = fork();
11			if (!child_pid) {
12				/* I am the child: create a pipe to parent */
13				pipe (c2p);

14				/* fill buf with string of form: */
15				/* "Fib(13) = 377"   		 */ 
16				Fibonacci (buf, i);	
17				nbytes = write (c2p, (void *)buf, strlen(buf));
18			}

19			else {
20				/* I am the parent: read from child */
21				nbytes = read (c2p, (void *)buf, LINE_LEN);  
22				printf ("%s\n", buf);
23			}

24			total_bytes_read += nbytes;
25		}

26		printf ("I read a total of %d bytes\n", total_bytes_read);
27	}
    Problems are as follows:
    • line 7: argv[0] is program name - need to use argv[1] for first argument
    • line 7: should check that argc == 2 before examining argv[1]
    • line 7: argv[] array consists of strings -- must convert to int, for example, using atoi(argv[1])
    • line 9: no bounds check on n: what happens if user enters illegal number?
    • line 10: no test for failure on fork(): program can run out of process descriptors
    • line 13: pipe should be created outside of child, otherwise, parent won't see it
    • line 13: no test for failure on pipe(): program can run out of file descriptors (bonus for catching this one, since your instructor is guilty of skipping this test in his solutions to assignment #1)
    • parent and child should close unneeded ends of pipe for safety
    • lines 17, 21: read() and write() must use the appropriate index of the pipe's file descriptor array; c2p[0] for read and c2p[1] for write
    • lines 17, 21: string should be sent with terminating '\0' character or else added on receive end before printing
    • line 18: child must exit, otherwise, it will spill into parent's code (as well as hogging a much-needed process descriptor slot; but this requires parent to do a corresponding wait())
    • line 25: pipes should be closed at end of each loop iteration, otherwise we'll run out of file descriptors
    Note that the failure to include various system header files, especially strings.h is generally not a fatal problem, since these only provide the function definition (e.g. for strlen(), which is assumed implicitly to return int), rather than its implementation, which comes from stdlib.

  4. (20 points)
    A naive implementation of a context switcher for the Sparc processor is given below. Why won't it work? Indicate how the code can be corrected. 
    void ContextSwitch () {
	SAVE_REGS(); 	  /* save all registers on the stack */
        SAVE_CONTEXT();   /* save PC (%i7) and SP (%i6) of invoking proc. */

        QueueInsert(Active, ReadyQueue);
        Active = QueueDelete( ReadyQueue ) ;
        Active->inqueue = NULL ;

        RESTORE_CONTEXT(); /* set subroutine return address (PC of caller) 
			    * and current frame pointer (SP of caller)
			    * from newly selected Active thread */
	RESTORE_REGS(); /* load 'in' and 'local' regs from stack */
        return;
}
    There are two serious problems with this implementation. First, restoring all the 'in' and 'local' registers from the stack after RESTORE_CONTEXT() means that the register values set by RESTORE_CONTEXT() (i.e., %i7 and %i6) will be overwritten immediately. Thus, this version of ContextSwitch() will not perform a context switch at all!

    Simply reversing the order of RESTORE_CONTEXT() and RESTORE_REGS() will work, but is dangerous. If any local variables are declared within the function (they aren't here, but they could conceivably be introduced), their values are likely to be incorrect. Remember, the actual context switch doesn't occur until the function returns, thus replacing PC and SP with the values saved in %i7 and %i6 by RESTORE_CONTEXT(). If RESTORE_REGS() is invoked any time prior to the return statement, the register values that will be restored are the same ones that were just saved above the current stack pointer, not those of the new Active thread. Remember, the stack pointer itself doesn't get updated until the function returns.

    The correct solution requires that SAVE_REGS() and RESTORE_REGS() be performed in the calling function, as follows. This ensures that the local register values are restored from the correct stack pointer at the right time. Note that the in registers of CallingFunction() are already restored by the return from ContextSwitch(), so RESTORE_REGS() could be simplified to avoid this redundancy if it were only needed by this one function. 

    CallingFunction() {
	...
	SAVE_REGS(); 	/* save all registers on the stack */
	ContextSwitch();
	RESTORE_REGS(); /* load 'in' and 'local' regs from stack */
	...
}

void ContextSwitch () {
        SAVE_CONTEXT();   /* save PC (%i7) and SP (%i6) of invoking proc. */

        QueueInsert(Active, ReadyQueue);
        Active = QueueDelete( ReadyQueue ) ;
        Active->inqueue = NULL ;

        RESTORE_CONTEXT(); /* set subroutine return address (PC of caller) 
			    * and current frame pointer (SP of caller)
			    * from newly selected Active thread */
        return;
}

  5. [Bonus: 10 points]
    The Republicans have concealed 100 listening devices in Monica Lewinsky's apartment. Each of these has a simple on/off toggle; the first press activates the listener, the second press disables it, the third press re-activates it, and so on. Initially, all 100 listening devices are disabled.

    Ken Starr arranges for Linda Tripp to pay a visit to Ms. Lewinsky, and while there, she surreptitiously presses the toggle buttons on all 100 listening devices. However, the independent council is worried that Tripp might have missed some of the buttons, so he sends in a second agent, who toggles every second listening device, i.e., numbered 2, 4, 6, .. 98, 100.

    Obviously, this backfires. With only half of the devices now working, Starr misses portions of Monica's better conversations. Worried that this may affect the commercial success of his planned RealAudio web site release of the transcripts, he sends in a third agent, who toggles every third listening device, i.e., numbered 3, 6, 9, ... 96, 99, then another agent, who toggles every fourth device, i.e., 4, 8, 12, ... 96, 100, and so on and so on, until the final, hundredth agent, simply toggles the 100th listening device.

    Assuming that Ms. Lewinsky conducts most of her intimate conversations with the president on a telephone covered by listening devices 70 through 80 (inclusive), will Ken Starr's web site be a success?

    The answer to this question was actually discussed in class in relation to the largest divisor needed to verify primality of a candidate prime. Hint: Take a number and write out its list of factors. Then consider how the number of factors relates to whether or note the listening device will be turned on.