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?
There are four transitions:
- 1. Preemption changes a process from running to ready. It occurs
when a preemptive scheduler decides to interrupt the current process to
run a different process. For example, with a round-robin scheduler, it
occurs when the running process has exhausted the time quantum.
- 2. Blocking changes a process from running to blocked. This occurs
when a process must wait for some external event (e.g. a read from an
I/O device) in order to proceed.
- 3. Unblocking changes a process from blocked to ready. It occurs
when the process has been blocked waiting for an event, and the event
- 4. Being selected to run changes a process from ready to running.
It occurs when the previous process either is preempted or
blocks or terminates, and
the scheduler chooses this process to run; or when no process is running
and this process either enters or unblocks.
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?
The next value for the program counter will have been saved in P's 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 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;
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.
Answer: True. Process A cannot complete its call to P(R), and
therefore cannot start operation A.1, until
process B executes V(R). B does not execute V(R)
until after it completes operation B.1.
- B. Operations A.1 and B.2 cannot execute simultaneously.
Answer: False. After B has executed V(R), A can proceed with
executing P(R), P(S) and enter operation A.1, and B can simultaneously
enter operation B.2.
- C. Operations A.1 and B.3 cannot execute simultaneously
Answer: True. Mutual exclusion between A.1 and B.3 is enforced
by the semaphore S. Both A.1 and B.3 are preceded by P(S) and followed by
- D. Operations A.2 and B.3 cannot execute simultaneously
Operation A.2 is protected by semaphore R while operation B.3 is
protected by semaphore S.
- E. The system may deadlock.
Answer: False. Process B does not do any "hold and wait", so deadlock
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
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 Running process
Shortest job next
Time Running process
Shortest remaining time left
Time Running process Ready queue (jobs labelled with time remaining at end)
0-3 A B
3-6 B A, C
6-8 C A, B, D
8-9 B A, D, E
9-11 E A, B, D
11-12 B A, D, F
12-14 B A, D, F
14-19 D A, F
19-28 A F
28-40 F empty
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.
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.)
- A. What physical address corresponds to the virtual address of 50?
Answer: Virtual address 50 = page 0 offset 50 = frame 3 offset 50
= physical address 3122
- B. Name a virtual address that will generate a page fault.
Answer: Any address on page 2 --- that is, between 2048 and 3071 ---
or on page 4 -- that is, between 4096 and 5119.
- C. Suppose that the machine has 256M of RAM and that processes
use a 4 GByte address space. How many entries are there in the page table?
Answer: 4 GByte divided by 1 K Byte = 4M (4 * 220 =
Consider a paging system that uses the "Not Recently Used" (NRU) page
- What is the significance of the "R bit" and the "M bit"?
- When are the R bit and M bit set and reset?
- How is a page chosen for replacement?
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.