Final Exam: Comp. Sys. Org. II

 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.

• A. An assembly-language routine saves the current value of the registers.
• B. Control returns to process P.
• C. P is blocked.
• D. P traps to the kernel, invoking the top of the disk driver.
• E. Process Q is unblocked.
• F. The data is copied from the buffer in the disk controller into Q's user space.
• G. The hardware saves the current value of the program counter.
• H. The interrupt controller issues an interrupt.
• I. There is a context switch from P to Q.
• J. Using the interrupt vector, control jumps to the bottom of the disk driver.

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)

• A. The least recently used (LRU) page replacement algorithm tends to yield fewer page faults than the not recently used (NRU) algorithm. Explain why. Answer: Both algorithms are based on the assumption that pages that have not been recently referenced are likely not to be referenced again soon. The LRU measures the time of the most recent reference exactly. The NRU measures the time of the most recent reference only crudely, dividing it into two categories: since the last clock tick and before the last clock tick. Thus, much less information is available for choosing a page to replace, so the quality of choice is inferior.
• B. Nonetheless, the LRU algorithm is rarely if ever implemented for paging systems. Why not? Answer: Implementing LRU requires that the page be time-stamped at each memory reference (i.e. two such time-stamps per machine instruction.) The hardware to support this is certainly expensive and probably non-existent.
• C. The optimal algorithm cannot be implemented, since it involves predicting the future. What, then, is the significance of this algorithm? Answer: It can be used, after the fact, to establish a lower bound on the minimum number of page faults, which can be used to gauge how well the actual page replacement algorithm is working.
  Almost everyone got part (C) correct, which surprised me a little, as it is a comparatively abstract and minor point.

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:

• A. In the process scheduling algorithm. Answer: If the choice of the next process to run is based strictly on the properties of the process, such as assigned priority or expected running time, then a steady stream of high-priority/short jobs may prevent a low-priority/long job from ever being chosen.
• B. In the disk arm scheduling algorithm. Answer: If the ``shortest seek time'' algorithm is used, then a steady stream of requests close to the disk arm may prevent a request far from the disk arm from ever being serviced.
• C. In choosing a process to unblock when a semaphor is released. Answer: Much the same as part (A). If there are several processes waiting for a given semaphore, then the OS must choose among them one to run. If the choice is on the basis of priority, and there is a steady stream of high-priority processes being blocked for this semaphor, then a low-priority process may never be chosen.
• D. In the readers/writers problem. Answer: In the standard solution to the readers/writers problem, if the resource is currently being read, then new readers are allowed to enter, but writers are not. Therefore, if there is a steady stream of readers, no writer will ever get access to the resource.

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.
Answer:

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 2^K and 2^K+1 bytes," for some particular value of K). Answer: Each block holds 2⁸ = 256 addresses (= 1K Bytes / 4 Bytes). Therefore the third-level indirect block points to 2⁸ second-level indirect blocks. Each of these points to 2⁸ indirect blocks. Each of these points to 2⁸ data blocks. Each of these holds 2¹⁰ bytes. So the total size of the data indexed under the third-level indirect block is 2⁸ * 2⁸ * 2⁸ * 2¹⁰ = 2³⁴ bytes = 16 GBytes. The total size of all the other blocks is comparatively negligible (about 1/256 the size). So the answer is "Between 2³⁴ and 2³⁵ 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.

• A. What does video RAM "look like" from the point of view of the CPU? Answer: Video RAM, though physically separate, from the point of view of the CPU is just part of the same physical address space as ordinary RAM. That is, there is a fixed range of physical addresses that refers to video RAM.
• B. How does the content of video RAM correspond to the display? Answer: For each pixel in the display there is a corresponding set of 3 (or 4) bytes in video RAM. These hold 3 8-bit integers between 0 and 255, expressing the intensity of the three colors red, blue, and green.

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.

Solutions to sample questions

 Solutions to sample questions

Short problems

Problem 1:

An OS uses the elevator algorithm to schedule the disk-arm. I/O requests are currently pending for blocks on tracks 1, 3, 8, 11, 15, and 16. The disk arm is currently at track 9 and moving upwards. In what order will these requests be handled? Answer: 11, 15, 16, 8, 3, 1

Problem 2:

An OS uses a paging system with 1Kbyte pages. A given process uses a virtual address space of 128K and is assigned 16K of physical memory. How many entries does its page table contain? Answer: 128

Problem 3:

Consider a file system that uses an FAT. The state of the directory is

 
File name | First block | Size in bytes 
---------------------------------------
  AA               5           1350
  BB               7           2200

(The other information in the directory is omitted.) The current state of the FAT is

 0  -- FREE
 1  -- FREE
 2 --  -1
 3 --   4
 4 --  -1
 5 --   2
 6 --  FREE
 7 --   3 
 8 --  FREE

The system uses a block size of 1 Kbyte. What is the last block of file BB? How many bytes of that block are used? (Useful fact: 1K=1024). Answer: The blocks of BB are 7, 3, 4. Since BB has length 2200 and blocks 7 and 3 hold 2048 bytes, there are 152 bytes used in block 4.

Problem 4:

A particular system uses a page size of 1K bytes. A page table for a particular process begins as follows: [ 3, 4, *, 1, *, 8 ...]

• A. What physical address corresponds to the virtual address of 50?
• B. Name a virtual address that will generate a page fault.

(Note: everything uses 0-based indexing.) Answer:
A. 3*1024+50 = 3122.
B. Any virtual address between 2048 and 3071 or between 4096 and 5119.

Problem 5:

Consider a Web browser and Web server that are communicating in HTTP layered over TCP layered over IP. For each of the following functionalities, state whether it is (i) implemented at the level of HTTP (ii) implemented at the level of TCP, (iii) implemented at the level of IP; (iv) carried out by the DNS; or (v) none of the above.

• A. Forwarding packets from one router to another. Answer: IP.
• B. Requesting retransmittal of a packet whose data is garbled. Answer: TCP.
• C. Maintaining a cache of web pages. Answer: HTTP.
• D. Assembling and disassembling a large file into packets. Answer: TCP.
• E. Translating URL's into IP addresses. Answer: DNS.
• F. Assembling the HTML file and the imbedded images into a display. Answer: none of the above (it's up to the browser.)

Long Problems

Problem 6

What is swapping? Why is it used in systems with variable-length partitions? Why is it used in systems with paging? Answer: In swapping, a process is entirely removed from main memory and its state is stored on disk. Swapping is used in an OS that uses variable-length partitions in the case there are active processes that are ready to run but do not fit into any free segment of main memory (either because the total memory requirements of the active processes is too large, or because space has been wasted in external fragmentation.)
In an OS that uses pages, swapping may be used when the sum of the working set sizes for the processes currently in memory is greater than the size of physical memory. When this happens, thrashing -- frequent page faults -- is almost inevitable, as the processes are competing for a resource (frames) that is inadequate to their combined needs. The only solution in such a case is to swap out (suspend) one or more of the processes.

Problem 7:

A user program has opened a file for reading and been reading sequentially through the program for some while. It now attempts to read the next byte, and finds that this byte belongs to a new block, and that this block is not in memory. Describe the major steps that are involved in the passage of control from the user program, which wants to read the byte, to the disk, which must carry out the read, and in the passage of information from the disk to the user program. In particular, your answer should discuss the operations of the device driver, the device-independent software, the actual disk, and the disk controller, in both directions. You may assume that the program is running on a single-process system. At any point, if there are different options for implementation, you can pick one to describe; you need not describe all the options. Answer: (Note: this is a lot more detail than I would expect on an exam answer. Also, the exact steps and the division of the steps among components of the system can vary a lot from one system to another.)
The device-independent software passes to the device driver the number of bytes to be read, the address in user space to read them into, and the file pointer. It then traps to the kernel. The kernel blocks the process and calls the device driver from the top. The device driver determines that the next byte is on a block B not in memory. It finds the address of B from the i-node (presumably in memory). It issues a request to the device controller to read B into memory. The device controller translate the block number of B into a set of consecutive sectors on a track, and instructs the actual disk to read those sectors. The disk moves the arm to the correct track, waits for the disk to rotate to the proper sectors, and reads the information, putting the output into the disk controller's buffer. The disk controller issues a interrupt. The interrupt handler in the kernel sends control to the bottom of the disk driver. The disk driver transfers the block of data from the disk contoller's buffer to the file cache, and transfers the byte of data to the specified address in user space. The kernel unblocks the process and schedules it to run. The device-independent software finds its data where it expects, and returns control to the user process.

Problem 8

On CD-ROM, each file occupies a physically contiguous section of memory.

• A. Name two advantages of this arrangement over the use of i-nodes.
• B. Name two reasons that this system is not used on hard disks.

Answer:

• A. First, it minimizes seek time. If a file is read sequentially (the usual case) then seek time is kept to an absolute minimum. Even if the file is read out of sequence, with contiguous storage, the blocks of the file are at least all in the same part of the disk whereas with non-contiguous storage they are (in general) scattered randomly around the disk. Second, it requires less space, because the i-node need not be kept. An i-node based system generally requires an extra block for the i-node; if there are a lot of small files, this is a substantial cost.
• B. Contiguous storage can only be used for files that are unchanging. If a file is expanded, then it will no longer fit into its place, and, at best, has to be copied in its entirety to some other part of the disk, leaving a large hole. If a file is deleted or reduced in size, then a hole opens up in memory. Unless this hole happens to be filled exactly, you end up with wasted space due to external fragmentation.

Problem 9

A. Explain in 1 or 2 sentences the difference between non-preemptive and preemptive scheduling.
Answer: In a non-preemptive scheduler, a process stops running only when it blocks; it never transitions from "running" to "ready". In a preemptive scheduler, the scheduler may preempt a running process and put it on the ready queue, B. Name one preemptive scheduling algorithm and one non-preemptive scheduling algorithm. (Just the names; you do not have to describe them.)
Answer: Of the scheduling algorithms we have discussed, shortest remaining time first, round robin, selfish round robin are preemptive; first come first served and shortest job first are non-preemptive.
C. Even if all jobs are CPU-bound, a preemptive scheduler may give a better average turnaround time than a non-preemptive scheduler. Give an example that illustrates this.
Answer: Suppose that process P, with one CPU burst of 100 sec, enters at time 0, and the process Q, with one CPU burst of 1 sec, enters at time 1. Then a non-preemptive scheduler will run first P from time 0-100 and then process Q from time 100-101 for an average turnaound time of 100. By contrast, assuming a small quantum and ignoring time lost to context switches, a preemptive scheduler will complete process Q at time 3 and process P at time 101, for an average turnaround time of 52.

Problem 10:

Consider a paging system that uses the "Not Recently Used" (NRU) page replacement algorithm.

• 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?

Answer: The R bit is 1 if the page has been referenced since the last clock tick. The M bit is 1 if the page has been modified since it was read in. At each machine instruction, the R bit for any page of any virtual address referenced is set to 1. The M bit is set to 1 if the process writes to that page. The R bit is reset to 0 at each clock tick. The M bit is reset to 0 when the page is written out to disk. In the NRU algorithm, pages are divided into 4 categories:

• 1. R=M=0.
• 2. R=0, M=1.
• 3. R=1, M=0.
• 4. R=M=1.

A page is chosen for replacement from the lowest of these categories. If there is more than one page in that categories, one is chosen at random.