CS 450 Update Log

Your solutions to this assignment must be typed up, printed, and submitted by July 22nd at the beginning of lecture. Internet students should submit their work via Blackboard by the same date.

1. Suppose that we would like to use a File Allocation Table (FAT) based filesystem to support a 4TB (4 x 10¹² byte) drive.

   • If files are to be allocated in 4KB (4096 byte) blocks (i.e., 4KB is the minimum granularity of allocation, and correspond to a single FAT entry), how large, at a minimum, must the FAT structure itself be? Justify your answer. (5 points)
   • If files are allocated in 1MB (2²⁰ byte) blocks, how large must the FAT structure be? (5 points)

2. Consider an i-node based filesystem such as UFS with the following properties:

   • Blocks are 8KB large
   • Block pointers are 64-bits in size

   • Each I-node consists of the following:

     • 4 single indirect block pointers
     • 2 double indirect block pointers
     • 1 triple indirect block pointer

   What is the maximum file size supported by the file system described above? Show your work. (10 points)

3. Assume that, in a RAID 3 system with byte level parity and a dedicated parity disk, that we have lost one of the 4 RAID-ed disk drives. Compute and fill in the column below with byte values recovered using the parity drive: (5 points)

   

4. Suppose that you’ve been asked by a database administrator to help recommend a RAID implementation to support a high throughput file system. Single drive failure must be tolerated, at a minimum. Due to limited funding, you are restricted to purchasing a maximum of 20 1TB drives, and it’s crucial that the final setup allow for at least 75% of the full capacity.

   Can you recommend a setup consisting of nested RAID levels, or a hybrid approach? Justify your answer. (5 points)

5. Consider a filesystem that supports the strategies of contiguous, linked, and index allocation. What criteria should be used in deciding which strategy is best used for a particular file? Use examples to justify your answer. (5 points)

6. Give an example of how Isolation (of the ACID properties) might be important in the context of a file system. (5 points)

7. Consider a filesystem with journaling support. Upon reboot following a crash, the following entries are discovered in the journal:

   <transaction>
     <del /home/lee/foo>
     <free 319>
     <free 12019>
   </transaction>
   <transaction>
     <del /home/lee/bar>
     <free 40
   

   Describe what must have happened before the filesystem crashed. What actions should be taken to ensure the filesystem is consistent? Is it possible to carry out any of logged transactions? (5 points)

8. Consider that the throughput of a file system implementation is closely tied to how well it allows for contiguous access to the data blocks of a file. While it is theoretically possible for both FAT and UFS filesystems to contain large amounts of fragmentation, the latter is typically seen as more “resistant” to the problem.

   What about the UFS filesystem makes it inherently easier to allocate file blocks in such a way as to lessen file fragmentation? What makes it more difficult when using FAT? (5 points)

9. Consider the following set of block address requests, arriving in the order specified, with a constant inter-arrival time of 5ms: 20, 11, 40, 19, 5, 6

   There is a single head, and there are 50 cylinders, each of which contains a single sector/block. Head movement (seek) time is linear in the number of sectors n to traverse, and can be described with the formula 5 + n; e.g., seeking across 4 cylinders requires 5+4=9ms. Access times are ignored for this problem.

   Given a current head position of 14, and that the previous block accessed was 8, compute the total seek time for each of the following head scheduling algorithms over the block requests given above.

   • SSTF (4 points)
   • LOOK (4 points)
   • C-LOOK (4 points)

The solutions to this assignment must be typed up, printed, and submitted by July 6th at the beginning of lecture. Internet students should submit their work via Blackboard by the same date.

Coded solutions must be properly formatted and indented.

1. Deadlock in the barrier non-solution

On page 25 of The Little Book of Semaphores (TLBoS) (in listing 3.4), a non-working solution to the barrier pattern is presented in which deadlock is likely to occur. It is, however, possible — though unlikely — that the code could be executed by multiple threads in such a way as to avoid deadlock. Describe such a path through the given barrier code for 5 threads.

2. Completing the Generalized Smokers Solution

The generalized solution for the smokers problem, as presented on page 119 of TLBoS (in listing 4.46), is incomplete — in addition to Pusher A, which is woken when tobacco is placed on the table, and the smoker holding tobacco (shown in listing 4.44), we need the code for Pushers B and C, and the smokers holding paper and matches to complete the solution.

Write up the code for Pushers B and C and the aforementioned smokers — you should adhere to the semaphore names and conventions established by the existing code.

3. The Dance Mixer Problem

At the Willowbrook Ballroom, the band is always playing a Waltz, a Tango, or a Foxtrot, and there is at all times a group of dancers (men and women) on hand, each of whom can dance two of these three dances.

Each dancer waits in a gender appropriate line for the dance he/she is capable of dancing until the corresponding music is played by the band. When the music starts playing, he/she waits to be paired up with a dancer of the opposing gender also waiting for the same dance. After they complete the dance, each dancer lines up for the next dance they are capable of dancing — the band continues to play the music until there are no couples on the dance floor. At this point the band starts to play music for the next dance, and the affair starts over again.

Implement a semaphore based solution (that avoids deadlock and race conditions) for the Dance Mixer problem.

Be sure to first list the variables used in your solution (names, types, and values), and then your coded solution. You should clearly identify each thread and what it represents (dancer, band, etc.) Comment the code to your satisfaction.

4. The Gaming Lab Problem

Bowing to popular demand, the residence hall association has invested in a “lab” consisting of 5 high-performance gaming PCs. Usage of the game lab is restricted, however, to students belonging to the Rho-Theta-Sigma (RTS), Rho-Pi-Gamma (RPG), and Phi-Pi-Sigma (FPS) fraternities.

At any given moment, the lab may be occupied by a group of no more than 5 students from a single fraternity, and as other students from the various fraternities arrive at the door they form separate lines waiting to enter the room. When the current group of students finishes their game and exits, another group of students formed from one of the lines enters. If the selected line has fewer than 5 students, all the students in that line will enter as a group, otherwise a group of 5 will be selected to enter.

Note that once a group of students enters the lab, no additional students may enter the room, regardless of the size of the group or which fraternity they belong to. It is also important to guarantee that no single fraternity is starved of the game lab — e.g., if RTS is currently using the lab and there is a mile-long line for RTS but one waiting student from RPG, the latter group will be allowed to enter.

Implement a semaphore based solution for the Gaming Lab problem.

Be sure to first list the variables used in your solution (names, types, and values), and then your coded solution. You should clearly identify each thread and what it represents (dancer, band, etc.) Comment the code to your satisfaction.