Consider a file system that uses contiguous allocation to define the set of blocks allocated to each file, as shown in Figure 10.34. There are 8192 bytes on this disk made up of 256 blocks, where each block is 32 bytes. This file system is used to record important "black box" information. Therefore, the file system is initialized to empty when the device is manufactured. Each time the system is turned on, a new file is created. While running, important data are stored into that file (open file, append data at the end, close file). Files are never deleted. Block 0 contains the directory and is not available for data. Each directory entry has three fields: name, block number of the first block, and total number of bytes stored. The example in Figure 10.34 shows File A with 3 allocated blocks (1,2,3 containing 32,32,8 bytes), File B with 2 blocks (4,5 containing 32,32 bytes), and File C with 7 blocks (6,7,8,9,10,11,12 containing 32,32,32,32,32,32,8). All 32 bytes of each data block can contain data for the file.

a) Does this file system have any external fragmentation? Justify your answer.

b) Assume a file has n data blocks. It takes one block read to fetch the directory. On average, how many more block reads does it take to read a single byte at a random position in the file? What is the maximum number of additional block reads that it takes to read a single byte in the file (worst case)?

c) Describe a simple mechanism to manage free blocks in this system. Be as explicit as possible, describing how many bytes in the directory are needed to manage the free space. Describe what the free space looks like after the disk is erased/formatted. Describe what the free space looks like when the disk is full.

d) File names are a single character. How many files can be stored? Justify your answer.

e) Assume you have n files each with of random size. Quantify the number of wasted bytes due to internal fragmentation. You may assume n is less than the number determined in part d).

Figure 10.34