CAOS 07

Let's now talk about File System Organization. The file system first defines how the units are managed. The system identifies a physical block through the use of drive/cylinder/track/sector numbers. For example, a Block can be 4 sectors, while each sector is 4096 bytes.
Next, the File System performs I/O control to translate the high level physical commands "retrieve physical block 5" to a low level hardware specific commands.

Finally, the File Organization Module translates high level logical commands to physical commands, like "retrieve logical block 1 of file A" to "retrieve physical block 5" for the I/O control.

Files need to be allocated to the disk in some way. The main focus of the allocation methods is to make the best and efficient use of the disk space, and to allow the files to be accessed as quickly as possible.

In the recommended text, we discuss three ways of allocating files. The first is the contiguous file allocation. This allocation is the simplest. We simply need to specify the start of the file in block number, followed by the length in blocks as shown:


(From recommended text)

Like contiguous memory allocation, each file occupies a set of contiguous blocks on the disk. This supports fast sequential and direct access, but does not make good use of disk space, resulting in high external fragmentation. The system would have trouble finding space for a new or resized files, and we would not be able to determine size requirements of a file.

Another method is the Linked Allocation. In Linked Allocation, each file is stored as a Linked List of Blocks. Each Block belonging to the file would have a pointer to the next Block to be read. The Blocks may exist anywhere on the disk, like this:


(From recommended text)

This method solves the external fragmentation problem as well as the provision for disk space. This is also perfect for sequential access since the Blocks MUST be accessed in sequence. However, due to that very same reason, it does not support direct access efficiently.

As the overhead of pointers may get large, a solution is to allocate clusters of contiguous blocks instead of single blocks. There is also a possibility of link breakages. In this case, richer links should be used.

Notice that the last block has a pointer to -1. It signifies an EOF (End-of-File).

To allow non-contiguous allocation (to solve disk and file size allocation issues) as well as direct access, a method known as the Indexed Allocation is used. In Indexed Allocation, the blocks scattered through the disk is recorded in sequence in an Index block. In this case, you would not have to go through EVERY block to get to the next. We can simply skip ahead in the Index block. The ith entry in the Index points to the ith block of the file.


(From recommended text)

This method is great as it is the best of both worlds. However, it is wasteful if the file only takes up two blocks. The Index is allocated in blocks, so the unused space are flagged as -1. This causes great wastage.