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.)

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?

Answer:

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.