Final Exam: Comp. Sys. Org. II

Friday, May 9, 2003

Note: I will send mail to the class list when the exam and course grades are ready -- probably Monday or Tuesday next week. Send me email if you want to know your grades. Solutions to the exam will be posted on the Web some time next week.

Problem 1

(10 points)
Suppose that a disk read from file F completes; that process P is currently running; and that process Q has been blocked waiting for this read to complete. Some of the following events occur; others do not. State which events occur, and in which order they occur. Answer: This problem was a little more ambiguous than I intended, because I forgot to specify the scheduler. With some schedulers and in some states, such as round robin, P will resume as the active process once the interruption has been dealt with. With other schedulers and in other states, P will be preempted for Q; for instance, this will happen if the scheduler is "Shortest remaining time next" and the next CPU burst for Q is shorter than the remainder of P's current CPU burst. So either B or I can occur, though, of course, not both. Also, E and F can occur in either order, and, if I occurs, it can occur in any order relative to E and F. Finally, it is barely possible, though very unlikely, that A could occur before J.

That being said: The first two events must be H and G, in that order. These are followed by J and A -- almost certainly in that order, but possibly in order A,J. If control returns to P, then the next events are E and F, in either order, followed by B. If control is passed to Q, then E, F, and I occur in any order.

C and D do not occur. A very common error was to include C, but P is not blocked. It is interrupted by the kernel, and it may be preempted in favor of Q.

Problem 2

(10 points)
Suppose that a computer uses a paging system, with a page size of 4K Bytes, and that the current machine instruction references virtual address V. Suppose that the page containing V is currently in memory but not in the TLB. How is V translated into a physical address? Explain the translation at the level of bit manipulation.

Answer: The twelve low-order bits are the offset O; the higher-order bits are the page number P. The value of PageTable[P] is the frame number F. The physical address PA has F has its high-order bits set to F and its low-order bits set to O.

Problem 3

(15 points)

Problem 4

(16 points)
The problem of starvation is a potential danger at many different points in an operating system. Explain how the problem arises:

Mostly, errors on this problem were of two types. One was to confuse starvation with deadlock. The other was to confuse starvation with long waits, of one kind or another. Long waits are sometimes inevitable. Starvation is different; starvation is the situation, such as those above, in which logically the system could eventually run process P (unlike deadlock) but it never does run P because it always prefers to run something else.


Problem 5

(4 points)
Suppose that a block is 1K Byte and that a disk address is 4 bytes. Suppose that files are implemented using i-nodes, and that an i-node has the following structure: the last address in the inode is a third-level indirect block; the second-to-last address is a second-level indirect block; the third-to-last address is an indirect block; and the remaining addresses are data blocks. Approximately how large a file can this system support? You do not have to give an exact answer; just give a range between two consecutive powers of 2. (That is, the form of your answer should be "Between 2K and 2K+1 bytes," for some particular value of K).

Answer: Each block holds 28 = 256 addresses (= 1K Bytes / 4 Bytes). Therefore the third-level indirect block points to 28 second-level indirect blocks. Each of these points to 28 indirect blocks. Each of these points to 28 data blocks. Each of these holds 210 bytes. So the total size of the data indexed under the third-level indirect block is 28 * 28 * 28 * 210 = 234 bytes = 16 GBytes. The total size of all the other blocks is comparatively negligible (about 1/256 the size). So the answer is "Between 234 and 235 bytes."

Only one student got this correct, though three or four other students were within a factor of 100 or so.

Problem 6

(10 points)
Explain briefly (3 or 4 sentences) the difference between a hard link and a symbolic link, as implementations of shared files.

Answer: If one creates a hard link from the path name "/B/Y" to the file /A/X, then the directory B holds, under the name Y, the actual disk address of this same file. That is, the relation between the directory B and the file is exactly the same as the relation between the directory A and the file. If the file is deleted under the name /A/X it is still linked under the name /B/Y.

By contrast, if one creates a symbolic link from path name "/B/Y" to file /A/X, all this does is create a new file /B/Y which holds the name of the path "/A/X" plus some flag that this is a symbolic link. If file /A/X is now deleted, this link fails to refer. If a new file /A/X is created, this link now points to the new file.

Problem 7

(15 points)
Amy is running the following experiment to study the effectiveness of multiprogramming in her operating system: She has chosen a fixed, fairly large, program P. The experiment involves concurrently running N processes, each executing P on the identical inputs (so the behavior should be identical) for values of N ranging from 1 to 100, and making a variety of measurements.

One of the quantities that Amy is measuring is the number of blocks read from disk. When N=1, the process reads M blocks from disk. Amy expects, therefore, that in general N processes will read N*M blocks.

What she finds is quite different. For small values of N, the number of blocks read is much smaller than N*M; in fact, it's barely larger then M, regardless of N. For large value of N, the number of blocks read is much larger than N*M.

Explain these findings. (2 or 3 sentences is fine; in fact, I'm basically looking for two key words.)

Answer: The two keywords are "cache" and "thrash". Since all the processes are executing the same code at pretty much the same time, they will end up reading the same blocks of the same files at the same time. Hence, after the block has been first read by one process, it will almost certainly be available in the cache for all the other processes, so each block read done for a single process suffices for all the processes, as long as there are few processes.

However, if there are so many processes that the working sets for the processes exceed the size of physical memory, then the system will have to do a large amount of paging in and out (or swapping) to run the processes. This involves a large number of disk reads that were not needed when a single instance of the process was running.

Problem 8

(10 points)
Consider a color display controlled by 24-bit video RAM running in bitmap mode.

Problem 9

(10 points)
Briefly (2 or 3 sentences) describe the difference between the download/upload model and the remote access model in implementing a distributed file system. State one advantage of each technique.

Answer: In a download/upload model, the entire file is downloaded from server to client when the file is opened. When the file is closed, if it has been modified, it is uploaded from client to server. In a remote access model, blocks are downloaded as needed from server to client and uploaded when modified from client to server.

Advantages of download/upload: (1) Easier to implement. (2) More efficient if the client is actually going to read the entire file. (3) The client can continue to read the file if the server or the network connection subsequently crashes.

Advantages of remote access: (1) More efficient if the client is only going to read a small fraction of the file. (2) Much easier to maintain reasonable consistency if several clients are simultaneously working on the same file.