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?


Problem 2:

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 process can contain multiple threads. Different threads within a process all share memory space, while different processes all have separate memory spaces. The thread table records primarily the state of execution: program counter, registers, and stack. The process table records in addition such information as address space, accounting information, parent and child processes, and open files.

Problem 3

(Multiple choice: Give all correct answers) Suppose there are two processes, A and B, which share semaphors 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:)

Answer: A and C are true; B,D,E are false.

Problem 4:

What is spooling, and why is it used?

Answer: In spooling a process writes its output to a temporary file rather than to an output device, such as a printer. When the output file is complete, a printer demon writes the file to the output device. This permits two or more process to generate output for the printer simultaneously.

Problem 5

(Multiple choice: 1 correct answer.) A ``critical section'' of code is

Answer: C.

Problem 6:

(Multiple choice: Give all correct answers) A given OS uses round-robin scheduling. The time quantum is Q and the time needed for context switch is C. Over an extended time period T, which is much greater than Q+C, there are N active processes; no processes begin or terminate during this period. Assume further that all these processes fit together in memory; no swapping or paging is needed. Which of the following statements are true:

Answer: B and D are true; A,C, and E are false. (Note: A and C are true if no processes ever block. E is true if there is always at least one ready process.)

Problem 7

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                Process running
0-12                     A
12-19                    B
19-21                    C
21-26                    D
26-28                    E
28-40                    F

       Shortest job next

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

       Shortest remaining time next

Time               Running     Remaining times at end
0-3                   A           A-9  B-7
3-6                   B           A-9  B-4  C-2
6-8                   C           A-9  B-4  D-5
8-9                   B           A-9  B-3  D-5  E-2
9-11                  E           A-9  B-3  D-5
11-12                 B           A-9  B-2  D-5  F-12
12-14                 B           A-9  D-5  F-12
14-19                 D           A-9  F-12
19-28                 A           F-12
28-40                 F