CS 140 Fall 2004 Final Solutions

Retrieving Exams

If you have not picked up your exam, it is available from Judy Polenta in Gates 351.

SCPD Students

We asked SCPD students who attended the exam to fill out an SCPD routing slip. If you did so, or if you're a remote SCPD student, we'll send it back to you through the SCPD. Otherwise we'll assume that you want to pick it up in person. You can email Judy Polenta if you change your mind.

Grading Errors

If you believe that part of your exam was graded in error, including arithmetic errors, please request a regrade by sending email to the staff list.

ProblemGrader
1, 2, 3, 4, 5, 6Mendel
7, 8, 9, 10, 11, 12Sameer
13, 14, 15, 16, 17, 18Ben

Early Exams

Questions on exams given early differed from the questions shown here. If you have questions about them, please bring them to the attention of the staff list.

Problem 1

Question

Assume you are given a disk that is possessed. On occasion the disk has random, non-deterministic errors that might:

a) Return a different block than was requested by the software (e.g. you read block 0 but the disk returns the contents of block 1).

b) Return the correct block but one or two bits in the block flipped. (e.g. you read block 0 and it returns the contents of block 0 with the 39th bit toggled).

The large majority of the time it returns the correct contents for the requested block. Describe how you as a file system designer would extend a Unix-like file system to handle such a misbehaving disk.

Answer

There are several ways of answering this question. The most common answer was to solve the errors as was done for networks. The suggestion was to modify the file system so that each disk block contained a header with the block number and a checksum of the block. This header enables the file system to quickly determine if an error has occurred when reading a block from disk. The block number will detect the case when the wrong block was returned and we should be able to find a checksum that detects the case of a few bits being flipped. When an error is detected we can simply retry the request until the correct block is returned.

Note that schemes that involved reading the same block multiple times on every read don't really work since the problem statement doesn't preclude the same error happening multiple times. That scheme would also have poor performance in the common case of no errors.

Problem 2

Question

Given the file system from question 1, how could you handle the case in which you determined that the errors were being introduced by a malicious attacker that was trying to confuse your file system. Under this threat model the attacker can return any data for a request but must return the correct contents most of the time.

Answer

Our scheme from question 1 doesn't handle a malicious attacker that would just return a bogus block with the correct header (e.g. request's block number and correct checksum). A simple modification we could make would be to encrypt the entire disk (or just the headers) with a key known to the file system but not to the disk. Since the attacker doesn't know the key they wouldn't be able to generate a proper header so any proper header we got must of come from something the file system wrote.

Note that simply replacing the checksum with a message digest like MD5 doesn't solve the problem since the attacker can just run MD5 to create a bogus block with the header that would look good to us.

Problem 3

Question

Would an operating system built with non-blocking or wait-free synchronization work correctly if run inside a virtual machine on a virtual machine monitor supporting multiple virtual machines at the same time? Justify your answer.

Answer

Since a virtual machine monitor exports an abstraction that looks just like the hardware so that any software will run on it, software with non-blocking or wait-free synchronization should run as well. After all it is just software. The only difference between running in the virtual machine and on the real hardware is the timing and non-blocking and wait-free synchronization isn't particularly timing dependent.

Problem 4

Question

Describe what would happen if an operating system running in a virtual machine decided to page out a process' page and that particular page had already been paged out by the virtual machine monitor.

Answer

Under a traditional virtual machine monitor (VMM), the OS running in the VM would initiate an I/O to the swap area for the particular page in question. In order to have this I/O precede the VMM would have to bring the page back in from its swap disk so that it could then be written out to the VM's swap disk. These events are sometimes referred as the double paging problem with virtual machine monitors.

Problem 5

Question

Assume you have two machines (A and B) sending datagram packets between one another using Internet Protocol (IP) over an internetwork. You notice from statistics being kept on the machines that machine A sent X packets to B and B received X packets from A. Machine B reports to have sent Y packets to A yet A reports to have received 4*Y packets from B. Explain how this is possible.

Answer

If machine A is connected to a network with a maximum transfer unit (MTU) that is four times the size of the MTU for machine B, all packets sent from B to A will be fragmented into 4 IP fragment packets before they get to A. Packets sent from A to B will not be fragmented. Hence the packet counts on the two machines will show the values dictated in the question.

Problem 6

Question

Your project partner builds a file system that with each file stores a list of a randomly generated 256-bit integers. In order to open a file you need to specify one of the integers in the open system call. Would this be considered an access control list or capability-based system? Justify you answer.

Answer

Although the 256-bit integers are stored in a list associated with each file, these integers act as capabilities that provide access to the file. This would be considered a capability-based system.

Problem 13

Question

fsck is the Unix file system crash recovery program. For each of the following fsck error messages, what do you believe fsck has seen in the crashed file system to generate the error message:

(A) File's inode link count is 1 should be 2.
(B) Free bitmap entry for block 3323 is 0, should be 1 (allocated).
(C) Cylinder group 4 - free block count is incorrect.

Solution

(a) Two directory entries in the file system point to the inode, but the inode's link count is just 1. Possible causes include partially completed link, rename, and remove operations.

(b) The free map indicates that block 3323 is not in use, but an inode or indirect block indicates that it is actually part of some file. Perhaps the system crashed during file growth or truncation.

(c) The free block count is a field in the cylinder group bookkeeping information. This message says that the free block group in cylinder group 4 doesn't match the number of bits set to 0 in the free bitmap for cylinder group 4. The system probably crashed between updating the free bitmap and updating the free block count.

Problem 14

Question

What are the advantages and disadvantages of a shortest seek time first (SSTF) disk scheduling algorithm when compared to an elevator algorithm

Solution

SSTF is likely to complete faster than the elevator algorithm because it always services the nearest request first, but it will starve requests for faraway sectors if requests for nearby sectors continue to arrive.

Problem 15

Question

Would a file system that used synchronous writes of all metadata blocks see more or less benefit from a disk scheduling algorithm than one that didn't use synchronous writes of metadata?

Solution

Consider the file system with synchronous metadata writes first. If only one process accesses the file system at once, then synchronous metadata writes will serialize most or all disk activity. Disk scheduling algorithms only help in the presence of multiple requests, so there would be little if any benefit to disk scheduling. If multiple processes access the file system simultaneously, then multiple metadata writes will occur simultaneously, giving the disk scheduling algorithm a chance to help. If there is enough activity across enough of the disk, disk scheduling may be of significant benefit.

Now consider a similar file system with asynchronous metadata writes. Disk scheduling is not going to help much in such a system under ordinary conditions, because processes don't have to wait around for disk writes to complete anyhow. (Under heavy I/O load, disk scheduling will be more helpful, of course, because in that case processes will probably have to wait.)

In conclusion, disk scheduling is likely to be of more benefit for a file system that writes metadata synchronously.

We accepted many answers for this question for full credit. Most students did not foresee all the cases above. We expected an answer based on file system performance, as described above, but we also accepted some answers that described other kinds of benefits.

Problem 16

Question

If someone gave you the source code of a file system and asked if it used index files or extent-based allocation, what would you look for in the code to answer this question?

Solution

Examine the inode data structure. Indexed files would include an array of pointers to data blocks and possibly pointers to other arrays. Extent files would include a starting block number and a count or an array of them. Many other answers were also accepted for full credit.

Problem 17

Question

Describe a denial of service attack that you could perform using the virtual memory subsystem of a modern operating system.

Solution

Drive the system to thrashing by consuming a large and ever-expanding amount of virtual memory. On a system that does global page replacement, this is sufficient. On a system that does local page replacement, it is helpful to use a large number of processes to do so, but it may not be necessary because a single large process thrashing may still unacceptably slow other processes attempting to use the disk.

Incidentally, a single large malloc, e.g. malloc(1024 * 1024 * 1024), is unlikely to have much effect by itself, because many systems do not actually reserve the pages of memory allocated with malloc until the first time each page is actually written.

Problem 18

Question

Explain why public key cryptosystems, where keys can be freely published, are frequently deployed using trusted servers that give out keys just like are used for shared key cryptosystems where keys must be kept secret.

Solution

The problem is one of authentication: this public key says it belongs to Alice, but how does Bob know it doesn't really belong to Mallory? Using a trusted server is one way to authenticate the key as Alice's. More typically, a trusted certificate authority (CA) signs Alice's public key with its private key, and Bob then verifies the signature with the CA's well-known public key.

Some students incorrectly claimed that the trusted server needs Alice's private key. Some students also claimed that the trusted server was needed to set up a session key or conversation key, which is also incorrect.


cs140-win0405-staff@lists.stanford.edu