OS-Non Contiguous Allocation

Files tend to grow or shrink over time so generally we go for dynamic noncontinuous storage allocation systems instead of contiguous allocation systems.

SECTOR-ORIENTED LINKED ALLOCATION:

Files consists of many sectors which may be dispersed throughout the disk. Sectors belonging to a common file contain pointers to one another, forming a linked list. A free space list contains entries for all free sectors on the disk. When a file needs to grow, the process requests more sectors from the free space list. Files that shrink return sectors to the free space list. There is no need for compaction.

The drawbacks in noncontiguous allocation is that the records of a file may be dispersed throughout the disk, retrieval of logically contiguous records can involve lengthy seeks.

BLOCK ALLOCATION:

One scheme used to manage secondary storage more efficiently and reduce execution time overhead is called block allocation. This is a mixture of both contiguous allocation and noncontiguous allocation methods.

In this scheme, instead of allocating individual sectors, blocks of contiguous sectors (sometimes called extents) are allocated. There are several common ways of implementing block-allocation systems. These include block chaining, index block chaining, and block –oriented file mapping.

In block chaining entries in the user directory point to the first block of each file. The fixed-length blocks comprising a file each contain two portions: a data block, and a pointer to the next block. Locating a particular record requires searching the block chain until the appropriate block is found, and then searching that block until the appropriate block is found, and then searching that block until the appropriate record is found. Insertions and deletion are straightforward.

With index block chaining, the pointers are placed into separate index blocks. Each index block contains a fixed number of items. Each entry contains a record identifier and a pointer to that record. If more than one index block is needed to describe a file, then a series of index blocks is chained together. The big advantage of index block chaining over simple block chaining over simple block chaining is that searching may take place in the index blocks themselves. Once the appropriate record is located via the index blocks, the data block containing that record is read into primary storage. The disadvantage of this scheme is that insertions can require the complete reconstruction of the index blocks, so some systems leave a certain portion of the index blocks empty to provide for future insertions. 


In block-oriented file mapping instead of using pointers, the system uses block numbers. Normally, these are easily converted to actual block addresses because of the geometry of the disk. A file map contains one entry for each block on the disk. Entries in the user directory point to the first entry in the file map for each file. Each entry in the file map for each file. Each entry in the file map contains the block number of the next block in that file. Thus all the blocks in a file may be located by following the entries in the file map.
The entry in the file map that corresponds to the last entry of a particular file is set to some sentinel value like ‘Nil’ to indicate that the last block of a file has been reached. Some of the entries in the file map are set to “Free” to indicate that the block is available for allocation. The system may either search the file map linearly to locate a free block, or a free block list can be maintained. An advantage of this scheme is that the physical adjacencies on the disk are reflected in the file map. Insertions and deletions are straightforward in this scheme.
Share this article :
 
Copyright © 2012. Best Online Tutorials | Source codes | Programming Languages - All Rights Reserved