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)
In the "readers-writers problem" a resource may be accessed at a
single time by
- A. Only one process, whether reading or writing.
- B. At most one reading process and at most one writing process.
- C. Either multiple reading processes or one writing process.
- D. Multiple reading processes and one writing process.
- E. Either multiple writing processes or one reading process.
- F. Multiple writing processes and one reading process.
A process scheduler is pre-emptive if
- A. A process can be swapped in and out of memory.
- B. A process can change from the "running" state to the "ready"
- C. A process runs for a fixed time quantum.
- D. No process experiences starvation.
- E. The scheduler is run whenever a process enters or unblocks.
Suppose that a file allocation table (FAT) is implemented in array A.
Let J=A[I]. Then
- A. Block I is the Jth block of some file.
- B. Block J is the Ith block of some file.
- C. Block I is in the Jth file in the file table for some process.
- D. Block J follows block I in some file.
- E. Block I follows block J in some file.
An access control list enumerates
- A. The resources held by some particular process.
- B. The machines located on a particular network.
- C. The frames used by a particular process.
- D. The files owned by a particular user.
- E. The users that have permission to use a particular object
and the kind of permission that they have.
Let T be a translation lookaside buffer (TLB). The value of the Ith
record in T is:
- A. The frame holding page I.
- B. The page in frame I.
- C. A pair [P,F] where P is a page and F is the frame holding P.
- D. 1 if page I have been recently used.
- E. 1 if page I is dirty.
- F. 1 if page I is in memory.
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.
- A. Explain the difference between a local and a
global page replacement algorithm.
Answer: In a local page replacement algorithm, only pages
belonging to the process that has page faulted are considered
for replacement. In a global PRA, pages considered by any
process are considered.
- B. What is the working set of a process?
Answer: The set of pages that a process is ``currently'' using;
that is,the set that it has used within some window of time.
- C. "In an environment with processes whose working sets tend to
vary widely in size over the lifetime of the process, a local
page replacement algorithm will work better than a global PRA."
True or false? Explain your answer.
False. The reverse is true. With a local replacement algorithm,
the number of frames that a process holds never changes, so
if the working set shrinks the process will hold onto more frames than it
uses, and if the working set grows, then the process
will not be able to get as many frames as it needs. With a global
replacement algorithm, frames that one process is done with gradually
get reassigned to a process that needs them, so if the working set
for one process shrinks and the working set for another process expands,
the frames will gradually move other from one to the other.
Consider a OS in which files are implemented using i-nodes,
that the free list is implemented as a bit vector,
and that blocks are 2 KBytes.
Suppose that a user process creates a new file /D/F, writes 1K bytes
of data to it, and closes it. Assume that the number of blocks in D
does not need to change. Suppose that the first few free blocks
on the free list are blocks 8, 12, 15, 19, 21, 30.
- A. How many new blocks must be allocated? What are they used for?
Answer: Two new blocks, one for the i-node and one for the data block.
- B. How are these new blocks (or this new block) found?
They are the first two blocks on the free list. You search through
the free list until finding two indices whose free list value of 0. Those
are the two new free blocks.
- C. What changes are made to the free list?
Bits numbers 8 and 12 are set to 1.
- D. What changes are made to the directory?
A record of the form ["F",8] is added to the directory.
- E. How is the file structured, in terms of blocks?
The i-node (block 8) contains a point to the data block (block 12)
as the first disk address, in the place immediately after the attributes.
- F. Name four attributes that would typically be recorded for this
Answer: Size, owner, times of creation, last modification, and last
access, access capabilities list, bit indicating whether this file
is a symbolic link.
How would they be recorded?
Answer: At the beginning of the i-node.
Consider a disk controller which is servicing requests. Suppose
that the seek time between cylinder C and cylinder D is (D-C)*10 msec,
that rotation times can be ignored, and
that the time needed to read or write a block can be ignored.
Assume that the arm scheduling algorithm is run only at the end of
a disk operation; that is, if the disk performs an operation
at cylinder I, and decides that the next operation it will perform
will be at cylinder J, then it will move directly to J, regardless of
any requests that are received while moving to cylinder J. Such requests
are considered only after the disk has completed the operation at J.
Suppose that at time 0, the disk arm is at cylinder 30
and that the request queue is empty before time 0.
Suppose that the following sequence of requests is received:
Trace the actions of the disk arm from time 0 until the time that all
these request are complete, assuming that the disk is running:
| Time || Cylinder # || Action
| 0 || 60 || Read
| 15 || 50 || Write
| 25 || 100 || Write
| 45 || 90 || Read
| 65 || 30 || Write
| 75 || 40 || Read
- A. The elevator algorithm. Assume that initialy the disk arm
is "moving upward."
| Time || Action || Pending Requests || Next Cylinder
| 30 || Read 60 || 50, 100 || 100
| 70 || Write 100 || 50, 90, 30 || 90
| 80 || Read 90 || 50,30,40 || 50
| 120 || Write 50 || 30, 40 || 40
| 130 || Read 40 || 30 || 30
|| || 150 || Read 30
- B. The shortest seek-time first (SSTF) algorithm.
| Time || Action || Pending Requests || Next Cylinder
| 30 || Read 60 || 50, 100 || 50
| 40 || Write 50 || 100 || 100
| 90 || Write 100 || 90, 30, 40 || 90
| 100 || Read 90 || 30, 40 || 40
| 150 || Read 40 || 30 || 30
| 160 || Write 30.
- A. What is swapping?
Answer: Moving an active process entirely out of RAM onto disk, and
- B.Suppose that your system uses variable-length partitions for
memory management. Describe
one circumstance in which one would choose to bring a process into RAM
without swapping any process out.
Answer: You bring a process into RAM when a partition opens up which is
large enough for it.
- C. Suppose that your system uses paging. Describe one circumstance
in which one would choose to swap a process out from RAM
without swapping any process in.
Answer: When the page fault rate becomes excessive, that indicates that
the total size of the working sets for the processes in memory is
larger than RAM can hold. This can be alleviated by swapping out
one or more process.
- D. Could it ever be worthwhile to swap out a single thread of a process,
while leaving the rest of the process in RAM? Explain your answer.
Answer: Since each thread has its own stack, swapping out a thread could
conceivably free up substantial amounts of space. I don't actually know
if this is ever done -- it may not be worth the bookkeeping costs.
Describe briefly one technique that a virus-detection program might use
to detect whether a given file has been infected, and one technique that
a virus writer could use to try to evade this kind of detection.
Answer: There are many solutions: See chapter 9 of the textbook.
One answer is that virus detection program looks for specific patterns.
A polymorphic virus, which makes changes to its own form that do
not affect its functionality each time it spreads itself, can to
some extent avoid this kind of detection.