Question

How do directories access eachother in a direct accessed allocation file system (i. E where I nodes access data blocks directly). So if the directory test wanted to access the directory Foo, what steps would have to be taken using blocks and writing to disk?

Answer 1

There are three types of allocation:

1. contiguous allocation
2. linked allocation
3. indexed allocation.

The contiguous allocation method requires each file to occupy a set of contiguous address on the disk. Disk addresses define a linear ordering on the disk. When a file has to be stored on a disk, system search for contiguous set of blocks as required by the file size i.e. system waits till it finds required number of memory blocks in sequence. When space is available system stores the file in the disk and makes an entry in the directory.

With this ordering, accessing block b+1 after block b normally requires no head movement. Contiguous allocation of a file is defined by the disk address and the length of the first block. If the file is n blocks long, and starts at location b, then it occupies blocks b, b+1, b+2, …, b+n-1. The directory entry for each file indicates the address of the starting block and the length of the area allocated for this file.

In linked allocation, each file is a linked list of disk blocks. The directory contains a pointer to the first and optionally the last block of the file. For example, a file of 5 blocks which starts at block 4, might continue at block 7, then block 16, block 10, and finally block 27. Each block contains a pointer to the next block and the last block contains a NIL pointer. The value -1 may be used for NIL to differentiate it from block 0.

Linked allocation does not support random access of files, since each block can only be found from the previous. Indexed allocation solves this problem by bringing all the pointers together into an index block. One disk block is just used to store DBAs (disk block addresses) of a file.