Problem 1:

• Can a 700MiB disk drive be formatted with a FAT16 file system using 4KiB clusters?

  No -- FAT16 allows a maximum of 2¹⁶=65536 clusters, and that many clusters of 4KiB each gives a total of only 256MiB.

• What is the smallest cluster size that would allow full use of the drive from (a)?

  16KiB

• How much space would be used by each FAT from your answer to (b)?

  We need 42725 clusters. At 16 bits = 2 bytes per FAT entry and 1 entry per cluster, we need 42725 * 2 = 85450 bytes, which will occupy 167 sectors on the disk.

Problem 2: Consider a file system similar to the Second Extended File System (ext2) in which the inodes contain 16 double-indirect addresses, each block is 8KiB, and each block address takes up 4 bytes. What is the largest file size possible using this system (assuming that the inode contains a sufficiently large field to record the file size itself)? What would the largest file size be if using 16KiB blocks?

Each block can hold 8096/4 = 2048 block addresses. Each double-indirect address in the inode then links to 2048² = 2²² (about 4 million) data block addresses. So the largest possible file has 16 * 2²² blocks, or 16 * 2²² * 8192 bytes = 512GiB.

Problem 3: Which file system, ext2 or FAT16, allows for a more efficient implementation of the lseek system call? Explain your answer.

To retrieve data at an arbitrary position in a file, we need to determine what block (or cluster) that position is in. With FAT16, we would have to traverse the linked list of clusters in the FAT to make that determination. In the worst case, we would have to traverse the entire list. Ext2, on the other hand, requires us to follow at most 3 linkes: from the inode we get the triple-indirect bloc, in which we can determine the correct double-indirect block to examine, in which we can determine the correct single-indirect block, from which we can get the correct block.

Problem 4: Consider a system that uses a file system that spans two disk drives (so that the data for a single file can be spread over both drives). Suppose the first half of a file exactly fills one track on one drive. Where would you put the next half of the file?

Putting the second half of the file on a track on the other disk allows the two disk heads to be positioned simultaneously, after which we read the first half from one disk and then the second half from the second disk. If the entire file is on two tracks on the same disk then we have to (in sequence) position the head, read, reposition the head, and read. Since positioning the head is an expensive operation, it is better to be able to do the positioning in parallel.

Problem 5: Suppose the data for a file occupies n clusters. In the best case, how many sectors must be written to delete the file on a FAT16 file system? How many sectors must be written to delete the file on an ext2 file system?

FAT16: We must mark the directory entry as deleted (1 sector), then we must mark all the FAT entries as free. In the best case, all n FAT entries are in n/256 consecutive sectors (each entry is 2 bytes, so 256 fit in each sector).

Ext2: We must remove the directory entry (1 sector), update the entries in the inode table (1 sector) and the inode index (1 sector), and update n entries in the block index. In the best case, all n entries are in n/4096 sectors (each entry is 1 bit, so 4096 fit in each sector).

Problem 6: Prof. Goofus got a great deal on a batch of unreliable drives. These drives have a 25% chance of failing in a given year. He plans to use the drives in a 4-drive RAID 5 configuration. Is this more reliable than a single-drive configuration?

This RAID configuration fails if two or more of the drives fail. P(2 or more fail) = 1 - (P(0 fail) + P(1 fails)) = 1 - (¹/₄)⁴ - 4*(³/₄)³ * ¹/₄ = 0.26171865 (assuming the failures are independent). So the proposed configuration is more likely to fail.

Problem 7: Consider a system with three processes and three resource types. The following table gives, for each process, how many of each resource is currently allocated to it and what its maximum total need is for each resourse type. Suppose that the number of available (unallocated) resources for each type is 1 1 x. What is the lowest value of x for which this is a safe state? Explain your answer.

x = 0 is not safe because no maximum request could be satisfied. x = 1 is not safe because, although A's maximum request could be satisfied, after that neither B's nor C's could be satisfied. x = 2 is safe: A's maximum request can be satisfied, then B's, and finally C's.

Problem 8: Consider the following three threads.

=== Thread A ===
pthread_mutex_lock(&lock1);
pthread_mutex_lock(&lock2);
pthread_mutex_lock(&lock4);
...
pthread_mutex_unlock(&lock4);
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);

=== Thread B ===
pthread_mutex_lock(&lock2);
pthread_mutex_lock(&lock3);
pthread_mutex_lock(&lock1);
...
pthread_mutex_unlock(&lock1);
pthread_mutex_unlock(&lock3);
pthread_mutex_unlock(&lock2);

=== Thread C ===
pthread_mutex_lock(&lock3);
pthread_mutex_lock(&lock1);
pthread_mutex_lock(&lock4);
...
pthread_mutex_unlock(&lock4);
pthread_mutex_unlock(&lock1);
pthread_mutex_unlock(&lock3);

• Show how these threads can become deadlocked in a preemptive system.

  Thread A acquires lock1 and is preempted in favor of Thread B, which acquires lock2 and is preempted for Thread C. Thread C acquires lock3. Now C is waiting for A to release lock1, A is waiting for B to release lock2, and B is waiting for C to release lock3.

• Rewrite the code to elimiate the possibility of deadlock. Assume there are other threads that use the mutexes and those other threads use the mutexes one at a time.

  Make all three threads acquire the locks in numeric order.

Problem 9: Is it possible to write a program that, given any two programs that use mutexes, determines if it is possible for those two programs to deadlock? Explain your answer.

Take CS478 Spring 2009.

If we could solve this problem we could solve the Halting Problem. To determine if M halts on input w, we could determine if the following two programs can reach deadlock.

mutex1.lock();
run M on w
mutex2.lock();

mutex2.lock();
run M on w
mutex1.lock();