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)

Problem 1:

In the "readers-writers problem" a resource may be accessed at a single time by

Answer: C.

Problem 2:

A process scheduler is pre-emptive if

Answer: B.

Problem 3:

Suppose that a file allocation table (FAT) is implemented in array A. Let J=A[I]. Then

Answer: D.

Problem 4:

An access control list enumerates

Answer: E.

Problem 5:

Let T be a translation lookaside buffer (TLB). The value of the Ith record in T is:

Answer: C.

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, specific answer. Do not give long explanations.

Problem 6:

Problem 7:

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.

Problem 8:

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:
Time Cylinder # Action
0 60 Read
15 50 Write
25 100 Write
45 90 Read
65 30 Write
75 40 Read
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 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.

Problem 9:

Problem 10:

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.