HOME

FILE SYSTEM IMPLEMENTATION

The file system provides the mechanism for on line storage and access to both data and programs. the file system resides permanentlt on secondary storage, which has the main requirement that it must be able to hold a large amount of data , permanently.

> File System Structure

Disks provide the bulk of secondary storage on which a file system is maintained. to improve I/O efficiency,I/O tranfers between memory and disk are performed in units of blocks. each block is one or more sector. depending on the disk drive , sectors vary from 32 bytes to 4096 bytes ; usually, they are 512 bytes . disks have two imp. charecteritic that make them a convenient medium for storing multiple files:

>They can be re written in place it is possible to read ablock from the disk,to modify the block , and to write it back into the same place.

We can access directly any given block of information on the disk thus , it is simple to access any file either sequetially or randomly and switching from one file to another requires only moving the read write heads and waiting for the disk to revolve.

And switching from one file to another requires only moving the read - write heads and waiting for the disk to revolve.

Free Space Management

Since there is only a limited amount of disk space, it is neccessary to reuse the space from deleted files for new files, if possible.(write ones optical disks only allow one write to any given sector, and thus such reuse is not physically possible.) to keeep track of free disk space, the system maintence a free space list. the free space list records all disk blocks that are free -- those not allocated to some files or directory. to create a file ,we search the free space list for the required amount of space, and allocate that space to the new file . thie space is then removed from the free space list. when afile is deleted its disk space is added to the free space list. the free space list , despite its name , might not be implemented as alist , as we shall discuss. Bit Vector : Frequently , the free space list is implemented as a bit map or bit vector. each block is reprewsented by one bit . if the block is free, the bit is 1 : if the block is allocated the bit is 0. The main advantage of this approach is that it is relatively simple and efficient to find the first free block, or n cosecutive free blocks on the disk. The calculation of the block no. is (no. of bits per word)*(no. of 0 - value words) + offset of first one bit. Linked List : Another approch is to link to gather allthe free disk blocks , keeping a pointer to the first free block in a special location on the disk and catching in it mem. this first block contains a pointer to the next free disk block ,and so on. usually , the o.s. simply needs afree block so that it can allocate that block to a file , so the first block in the free list is used note that the FAT method incorporates free block accountig into the allocation data structure. no seperate method is needed.

Grouping :

A modification of the free list approach is to stoer the add. of n free blocks in the first free block. the first n-1 of these blocks are actually free the last block contains the add. of another n free blocks, and soon. the importance of this implementation is that the addresses of a large no. of free blocks can be found quickly , unlike in the standard linked - list approach.

Counting :


Another approach is to take advantage of the fact that, generally, several contiguos blocks may be allocated or freed simultaneously, perticularly when space is allocatedw ith the contiguos allocation algorithm or through clustering. thus , rather then keeping a list of n free disk add. , we can keep the add. of the first free block and the no. n of free contiguos blocks that follows the first block . each entry oin the free space list then consist of a disk add. and a count. although each entry reqires more space then would a simple disk add., the overall list will be shorter, as long as the count is generally greater then 1.