Solutions to sample midterm exam

Problem 1

In a multi-process system, at any moment every process is in one of three states: running, ready, or blocked. What are the transitions between these states, and when do they occur?

Answer: There are four transitions:

Problem 2

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 next value for the program counter will have been saved in P's process table entry.

Problem 3

Explain briefly (1 or 2 sentences) the major difference between a thread and a process. Name one type of state that is recorded in a thread table. Name one type of information that is saved in a process table but not in a thread table.

Answer: A thread is part of a process; a process may contain several different threads. Two threads of the same process share a good deal of state and are not protected against one another, whereas two different processes share no state and are protected against one another. Two threads of the same process have different values of the program counter; different stacks (local variables); and different registers. The program counter, stack pointer, and registers are therefore saved in the thread table. Two threads share open files and memory allocation; therefore, file information and memory information (e.g. base/limit register or page table) is stored in the process table.

Problem 4

(Multiple choice: Give all correct answers) Suppose there are two processes, A and B, which share semaphores R and S. At the starting time, R = 0, S = 1. A and B are entering the sections of code shown below:
Process A:                           Process B:
P(R);                                Operation B.1;
P(S);                                V(R);
Operation A.1;                       Operation B.2;
V(S);                                P(S);
Operation A.2;                       Operation B.3;
V(R);                                V(S);

Which of the following statements are true (more than one may be true:)

Problem 5

What is spooling, and why is it used?

Answer: Spooling is used to enforce mutual exclusion on the printer, without forcing processes to wait for this slow resource. It works as follows: user processes do not actually access the printer; their output directed to the printer is placed in a temporary file in a specified directory. A separate process, called the spooling demon reads through the files one by one and delivers them to the printer. The same technique can be used for any slow output device that requires mutual exclusion.

Problem 6

Suppose that jobs arrive according to the following schedule.
Process   Starting Time    Run Time
  A           0              12
  B           3               7
  C           6               2
  D           8               5
  E           9               2
  F          12              12
Trace the progress of the system if the scheduler used is

First come first served

Time        Running process    
0-12            A                
12-19           B
19-21           C
21-26           D
26-28           E
28-40           F

Shortest job next

Time       Running process
0-12           A
12-14          C
14-16          E
16-21          D
21-28          B
28-40          F

Shortest remaining time left

Time  Running process  Ready queue  (jobs labelled with time remaining at end)
0-3          A[9]        B[7]
3-6          B[4]        A[9], C[2]
6-8          C[0]        A[9], B[4], D[5]
8-9          B[3]        A[9], D[5], E[2]
9-11         E[0]        A[9], B[3], D[5]
11-12        B[2]        A[9], D[5], F[12]
12-14        B[0]        A[9], D[5], F[12]
14-19        D[0]        A[9], F[12]
19-28        A[0]        F[12]
28-40        F[12]       empty

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 if a low priority job, though ready, is never scheduled to run because there is always a higher priority job ready. The "shortest job next" and "shortest remaining time next" are both subject to starvation. Practically any scheduling algorithm can be modified to avoid starvation by using "priority aging", in which the overall priority of a job is a combination of its inherent priority together with the time that it has been waiting in the ready queue.

Problem 8

A particular system uses a page size of 1K bytes. A page table for a particular process begins as follows: [ 3, 4, *, 1, *, 8 ...] (Note: everything uses 0-based indexing.)