Problem 1

Describe two ways in which the virtual machine that the OS presents to a user process differs from the actual machine. (Your answer should be brief -- one or two sentences for each difference -- but more than a single phrase. "I/O" or "Memory management" is not an acceptable answer.)


Problem 2

In UNIX, what does the "fork" system call do? What value does it return?

Answer: "fork" spawns a new process, which is a clone of the parent process. "fork" returns 0 to the child process. It returns the process ID of the new child to the parent process.

Problem 3

Suppose that process P is ready, and the scheduler decides to resume running it. How does it determine the address of the next instruction to run in P?

Answer: The address will have been saved in the process table entry for P when P last stopped running.

Problem 4

Threads may be implemented in user space or in kernel space. Describe one advantage of each approach.

Answer: The major advantages of a user space implementation are:

The major disadvantages of a user space implementation are:

Problem 5

Consider the following situation: Semaphore s has an initial value of 2. There are four active processes, A, B, C, and D. The following events happen in order:
A executes P(s)
B executes P(s)
C executes P(s)
D executes P(s)
A executes V(s)
Which processes are now blocked and which are unblocked? There can be more than one possible scenario, so I am looking for an answer of the following kind: "Either A,D are blocked and B,C are unblocked or B is blocked and A,C,D are unblocked."

Answer: A and B decrement s to 0, and C and D block on s. When A executes V(s) either C or D may unblock. Therefore at the end either A,B,C are unblocked and D is blocked or A,B,D are unblocked and C is blocked.

Problem 6

Consider the following situation. The OS uses a round robin scheduler. The FIFO queue of ready processes holds three processes A,B,C in that order. The time quantum is 18 msec. A context switch takes 2 msec. After running for 13 msec, B will block to do a disk read, which will take 30 msec to complete. Trace what will happen over the first 100 msec. What is the CPU efficiency over the first 100 msec?


Time      Activity                Ready queue
0-18      Run A                      B,C
18-20     Context switch             B,C,A
20-33     Run B. B blocks at 33      C,A  
33-35     Context switch             C,A
35-53     Run C.                     A
53-55     Context switch             A,C
55-63     Run A.                     C
63        B unblocks                 C,B
63-73     Continue to run A.         C,B
73-75     Context switch             C,B,A
75-93     Run C                      B,A
93-95     Context switch             B,A,C
95-100    Run B                      A,C
In the first 100 msec, the CPU is running a user process for 90 msec and doing context switch for 10msec. The CPU efficiency is therefore 90%.

Problem 7

What is starvation? Give an example of a scheduling algorithm that is susceptible to starvation. How can this algorithm be modified to avoid the problem?

Answer: Starvation occurs when one process is never run because the scheduler always prefers some other process. Starvation can occur in such scheduling algorithms as:

All such schedulers can be modified to prevent starvation by using priority aging. This requires that the age of the process -- that is, the time that it has been ready but not run -- be combined with whatever other criterion is used for scheduling in such a way that eventually the age of the process outweighs all other considerations.

Problem 8

Suppose you have the following deadlocked situation. There are three processes A, B, C, and four resources W,X,Y,Z.
A holds W and is requesting X and Y.
B holds X and Z and is requesting W.
C is requesting X.
D holds Y.
Which of the following actions, taken singly, will suffice to break the deadlock? (There may be more than one correct answer; list all correct answers. You need not explain your answer.) Answer: You can either kill A, kill B, reassign W to B, reassign X to A, or reassign X to C. Reassigning X to C gives a state that is unsafe because if C completes and X is then given back to B, the system will deadlock again, but it is not deadlocked , because if X is given to A after C completes, the system will run to completion.