Name: ________________________________ Login: _____________

Comp111 Midterm Exam
Oct 30, 2013 - open books and notes

No electronic devices of any kind allowed, including cellphones, calculators, pagers, etc. Please turn these off and store them out of sight before beginning the exam.

Please show all work on these pages. Make sure that your work for each problem is clearly marked. These pages will be graded and returned electronically, like exercises. Feel free to use the backs of pages as needed.
1a 10
1b 10
2a 10
2b 10
2c 10
2d 10
3a 10
3b 10
3c 10
3d 10
4 10
total 100

    Name: ________________________________ Login: _____________

  1. Consider the following resource allocation matrix:
    Requested Granted Deficit
    R1R2R3R4 R1R2R3R4 R1R2R3R4
    P13 0 0 0 - P13 0 0 0 = P10 0 0 0
    P22 1 1 1 P20 1 1 1 P22 0 0 0
    P30 3 3 3 P30 0 0 0 P30 3 3 3
    Total Available
    R1 R2 R3 R4
    3 3 3 3
    1. (10 points) Is this a safe situation? Why or why not?

    2. (10 points) Suppose that P1 has a bug that causes it to go into an infinite loop. Does the Banker's Algorithm prevent deadlock in this case? Why?

    Name: ________________________________ Login: _____________

  2. Consider the following code:
        struct rlimit res; 
        res.rlim_cur = res.rlim_max = 70; 
        setrlimit(RLIMIT_NPROC, &res); 
        while (1) fork(); 
    1. (10 points) What is the state of the machine while the fragment is running?

    2. (10 points) If one kills all of these processes but one, exactly what happens?

    3. (10 points) In most shells, the kill command is a built-in function instead of being implemented as an executable program like, e.g., ps. What would happen if kill were an executable program and the owner of the above process tried to use the kill program to kill it?

    4. (10 points) Exactly what happens when one runs:
          struct rlimit res; 
          res.rlim_cur = res.rlim_max = 70; 
          setrlimit(RLIMIT_NPROC, &res); 
          while (1) if (!fork()) exit(0); 
      Compare this behavior with that of the prior example.

    Name: ________________________________ Login: _____________

  3. In some modern experimental operating systems, deadlock is avoided by preventing schedules of execution that cause deadlock from happening. When a deadlock is detected, the schedule of locking that caused the deadlock is recorded, and that specific schedule of locking is prevented in the future by constraining the order of locks in one or more processes so that this particular schedule never again occurs.

    Suppose that the following is executed in process X:

    lock(C); lock(A); lock(B);
    do something(); 
    unlock(A); unlock(B); unlock(C); 
    and that the following is executed in another process Y:
    lock(B); lock(A); lock(C); 
    unlock(C); unlock(B); unlock(A); 
    1. (10 points) Give a schedule for these two processes that deadlocks.

    2. (10 points) Demonstrate how to prevent this schedule from occurring via lock ordering limits of the form "locking Q in X must precede locking R in Y".

    3. (10 points) Why is a deadlock-free set of limits always possible to define using this scheme?

      Name: ________________________________ Login: _____________

    4. (10 points EXTRA CREDIT) What record-keeping in the OS is required in order to implement this deadlock prevention scheme?

  4. (10 points) It is considered poor programming practice to write a single-threaded program that dups both the input and the output of an arbitrary child process. Why?