Final Exam: Comp. Sys. Org. II
Tuesday, May 4, 2004
Part I: Multiple choice
For each of the following give the single correct answer.
(5 points each)
Suppose that there are three processes P, Q, and R, and two semaphors
s and t. Initially s=1 and t=2. The following operations occur:
P executes DOWN(s)
Q executes DOWN(t)
Q executes DOWN(s)
R executes DOWN(t)
R executes DOWN(s)
P executes UP(s)
P executes DOWN(t)
Which of the following is a possible state of the system
after these operations?
- A. All three processes are blocked.
- B. P is blocked; Q and R are not blocked.
- C. P and Q are blocked; R is not blocked.
- D. P and Q are not blocked; R is blocked.
- E. None of the above.
Answer: C. When P executes UP(s), either process Q or process R
may be unblocked. If the semaphor uses a FIFO queue, then Q would unblock;
but a semaphor is not required to use FIFO queue.
To switch from reading one track to reading another track on the same
cylinder in a hard disk requires:
- A. Moving the disk arm.
- B. Rotating the disk.
- C. Switching the disk head currently in use.
- D. Signalling an interrupt.
- E. Clearing the disk controller buffer.
Consider a UNIX operating system that implements files using i-nodes.
Suppose that there is a hard link from filename /Y/G to filename /X/F.
- A. There exists a file /Y/G, which contains the path name "/X/F"
and has a flag set indicating that it is a link.
- B. There exists a file /Y/G, which contains the disk address of the
i-node of /X/F and has a flag set indicating that it is a link.
- C. There exists a file /Y/G, whose i-node is an exact copy of
the i-node of /X/F. (That is, it has the same attributes and
contains pointers to the same
data blocks, indirect blocks, etc.)
- D. The directory /Y contains a record of the form "[G ; /X/F]".
- E. The directory /Y contains a record of the form "[G ; D]" where
D is the disk address of the i-node of /X/F.
Problem 4: One common security hole is exploited by calling
a systems routine with an extremely long argument (e.g. a file name
with thousands of characters). The effect of this is that
- A. The file name table will overflow, and the file protections
will be overwritten.
- B. The file name will be written into the executable file, thus
inserting a virus.
- C. The systems program will crash, leaving the system in kernel
- D. The stack will be overwritten, and the systems routine will execute
the file name as code.
- E. The directory will overflow, leaving the file system in an
Problem 5: In the TCP/IP protocol for Internet communication,
which of the following is true:
- A. A message is sent in one or more packets.
Each packet consists of the IP header, followed by the TCP header,
followed by the data.
- B. A message is sent in one or more packets.
Each packet consists of the TCP header, followed by the IP header,
followed by the data.
- C. A message is sent in one or more packets.
Each packet consists, either of a TCP header followed by the
data, or of an IP header followed by the data.
- D. A packet contains a number of messages. The packet begins with
an IP header; each individual message consists of a TCP header followed
by the data.
- E. A message is sent in one or more packets.
The first packet in a message consists of an IP header followed by
a TCP header followed by data; the subsequent packets consist just
of an IP header followed by data.
Part II: Long questions
15 points each.
NOTE: In any of the following problems, if you are asked to
"explain" something or another, I am looking for a concise,
Do not give long explanations.
An OS designer is trying to decide between using a round-robin
scheduler with a 50 msec quantum and a first-come-first-served (FCFS)
scheduler in his
operating system. He tries out the two scheduling algorithms with
three separate collections of 20 jobs, C1, C2, and C3. All jobs enter
the system simultaneously at t=0.
In each experiment
he measures two quantities: The average
time to completion and the total time to completion (i.e. the time
at which the last job completes.) Note: None of the problems
below requires that you actually calculate the specific values of these
A. In collection C1, all the jobs are CPU-bound and consist
of a single, 1 minute long, CPU-burst. Which scheduling algorithm
has the lower average time to completion? Which has the lower
total time to completion?
Answer: FCFS will have a much lower average time to completion.
In FCFS the first job will complete after 1 minute, the second
job after 2 minutes and so on, for an average completion time of 10.5
minutes. In round-robin all the jobs will finish within 1 second of
one another after 20 minutes, for an average completion time of
slightly less than 20 minutes. The total completion time for FCFS will
be very slightly less than for round-robin, because there much
less time required for context-switching.
B. In collection C2, all the jobs consists of 1000 cycles in which
a CPU burst of 5 msec is followed by a 100 msec delay waiting for I/O.
Which scheduling algorithm has the lower average time to completion?
Which has the lower total time to completion?
Answer: In this situation no job every exhausts its quantum. Hence
FCFS executes jobs in exactly the same order as round robin, so the
two are equal in both measurements.
C. In collection C3, all the jobs are CPU-bound. One job requires
20 minutes of CPU time; the other 19 each require 10 seconds of CPU
time. The experimenter finds that
Explain these observations.
- i. Both algorithms do well in terms of maximum time to completion, but
FCFS reliably does a little better.
- ii. Running the experiment several times, round-robin reliably
has an average time to completion of about 4 minutes.
- iii. Running the experiment several time, FCFS has a very variable
average time to completion, ranging from about 2.5 minutes to about 21.5
- i. FCFS does better because of the reduced overhead for context-switching.
- ii. Round-robin begins by running all the jobs in pseudo-parallel.
It will therefore finish all the short jobs after about 200 second =
3.33 minutes. It will then complete the long job, which has (20 minutes
- 10 seconds) to run, and which will therefore finish at aboht the
23 minute mark. The average time is therefore about 4 minutes.
- iii. With FCFS, it depends on the order in which the jobs are
run, which is random, since they entered at the same time.
If the big job is executed first, then it will finish at the 20 minute
mark, and then the remaining jobs are executed over the next 3 minutes,
giving an average of 21.5 minutes. If the big job is executed last,
then the short jobs will finished over the first 3 minutes, then the
big job will finish after 23 minutes, giving an average of 2.5 minutes.
For intermediate placements of the big job, the averages are
- A. In a page replacement algorithm, other things being equal, is
it preferable to replace a clean page or a dirty page? Why?
Answer: A clean page, since a dirty page must be read
out to disk before the new page can be read in.
- B. In the NRU algorithm, given a choice between replacing
a page where the R bit is 1 and the M bit is 0 versus a page
where the R bit is 0 and the M bit is 1, which does the algorithm choose?
Why is this the right choice?
The algorithm chooses to replace the one with the R bit = 0 and
the M bit = 1. If it made the other choice, then a page PM with an
M bit = 1 would never be replaced as long as there was a steady stream
of pages with M bit = 0, regardless of how long it had been since PM
had been referenced.
- C. What is the advantage of the ``aging'' PRA over the NRU PRA?
Answer: NRU divides the recency of pages very crudely into two
categories: those that have been referenced since the last clock tick
and those that have not. Aging keeps information about the references
about references during the last K clock times, and thus allows
the scheduler to make a much more informed choice.
What is the advantage of the aging PRA over the LRU PRA?
Aging PRA needs only to carry out actions at every clock
tick, when there is going to be an interrupt to the kernel in any
case. LRU would require hardware to time-stamp a page at each
memory reference. Such hardware is not practical.
Suppose that user process P is running and page faults; it needs
page H, currently at disk address Y. Let us suppose
that there are no free pages; that the page replacement algorithm
decides to replace page Z of process P, currently resident in frame F;
and that page Z is currently clean. Suppose that the scheduling
algorithm decides to run Q, which is ready to run.
the following steps take place before P begins to run again
and in what order do they take place?
- A. The kernel instructs the disk controller to write out the contents
of frame F.
- B. The kernel instructs the disk controller to read from disk address
Y into frame F.
- C. The disk controller issues an interrupt to the kernel,
signalling that the read is complete.
- D. The value of the PC in P is saved by hardware.
- E. The kernel uses the interrupt vector to jumps to the page fault
- F. The page replacement algorithm is run.
- G. The protection is reset to user mode.
- H. Process Q unblocks.
- I. Process P unblocks.
- J. The page table for Q is made the active page table.
D, E, F, B, J, G, C, I. Events A and H do not occur.
Consider an OS that uses i-nodes to implement files. Suppose that
a user process P opens a file F in directory D for reading.
Suppose that directory D is currently in memory, but F is not.
- A. How does the file system locate the disk address of the i-node
- B. How does the file system locate the first data block in F?
- C. Name one other major responsibility of the file system in
carrying out this task, other than those mentioned in parts A and B.
- A. Directory D has a record of the form ["F", disk address of
- B. The first disk address in F' i-node, after the file atributes,
will be a pointer to the first data block of F,
- C. Checking that the user has read permission on this file.
The simplest implementation of a free list for blocks on disk as a linked list
is to store in each free block the address of the next block on the free list.
The address of the first block on the free list is held in a fixed address
Describe a disadvantage of this implementation and a more sophisticated
of a free list that avoids it. (Do not describe the use of a bit
Answer: A disadvantage of this implementation is that a block
on the free list has to read before it is written to, in order
to get the address of the next block on the list. A better
implementation is to use a linked list of index blocks, where each
block is full of addresses of free blocks. Since the current block
of addresses is kept in memory, extra disk operations need occur
only when the current index block is emptied out.