Solutions to Sample midterm exam
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?
- The transition of blocking takes the process from running to
It occurs when the process needs to wait for input or for a semaphore
or other synchonization condition.
- The transition of unblocking takes the process from blocked to
running. It occurs when the event for which the process is waiting completes:
either the input completes, or the semaphore is released.
- The transition of being selected takes the process from ready to
It occurs when the scheduler decides to run the process.
- The transition of preemption takes the process from running to
It occurs when a preemptive scheduler decides to run another process.
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.
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;
Operation A.1; Operation B.2;
Operation A.2; Operation B.3;
Which of the following statements are true (more than one may be true:)
- A. Operation A.1 cannot start until operation B.1 is complete.
- B. Operations A.1 and B.2 cannot execute simultaneously.
- C. Operations A.1 and B.3 cannot execute simultaneously
- D. Operations A.2 and B.3 cannot execute simultaneously
- E. The system may deadlock.
Answer: A and C are true; B,D,E are false.
Problem 4: What is spooling, and why is it used?
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
- A. A section that is executed very often, and therefore should
be written to run very
- B. A section of the program that must not be interrupted by the
- C. A section of the program that is susceptible to race conditions,
unless mutual exclusion is enforced.
- D. A section of the code executed in kernel mode.
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:
A. All processes get an equal share of the CPU.
B. If process P is ready, then it will be scheduled to run within time
NC + (N-1)Q.
C. If process P has just exhausted its time quota, then it will have to
wait for at least
time NC + (N-1)Q.
D. If process P is running and blocks, and process W is currently ready
then W will be
run before P runs again.
E. The efficiency of the system --- that is, the fraction of time that the
CPU is executing
a process --- is always equal to Q/(Q+C).
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
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.
- Shortest job next
- Shortest remaining time next
First come, first served
Time Process running
Shortest job next
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