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

Problem 9:

Consider a paging system that uses the "Not Recently Used" (NRU) page replacement algorithm.

Answer: The R bit is 1 if the page has been "recently referenced"; that is, referenced since the last clock tick. The M bit is 1 if the page is dirty. The R bit is set by hardware whenever there is a memory reference to the page. It is cleared at each clock tick. The M bit is set whenever the page is written to. It is cleared when the page is written out to disk. Pages are chosen for replacement according to the following descending order of priority:

1. Pages where R=0 and M=0.
2. Pages where R=0 and M=1.
3. Pages where R=1 and M=0.
4. Pages where R=1 and M=1.