Allocation Methods

Allocation Methods

• The primary issue of file implementing file storage is how to keep track of file blocks. File consists of a collection of blocks.

File allocation

• Following issue are considered for file allocation:

1. After creation of new file, whether the required maximum space for the file is allocated at once or not?

2. Portion Space is allocated to a file as one or more contiguous units.

3. Data structure or table used to keep track of the portion which is assigned to a file.

• Three major methods of allocating disk space are in wide use,

1. Contiguous   2. Linked      3. Indexed.

Contiguous Allocation

• When user creates a file, system allocates a set of contiguous blocks on disk. This is a pre-allocation method that uses portion of variable size. Contiguous allocation is simple method to implement. It only search free list of correct number of consecutive blocks and mark them as used block.

• Disk address is a linear ordering on the disk. Because of linear ordering, accessing block b + 1 after block b normally requires no head movement. Here head movement is only one track. Fig. 6.10.1 shows contiguous allocation.

• Contiguous allocation of a file is defined by the disk address and the length of the on first block.

• If the file size is "n" blocks and starting location is "L", then it occupies blocks L, L+1, L+2, L+3, ......, L+(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.

• Sequential and random access can be supported by contiguous allocation.

• It is easy to retrieve single block. To improve the I/O performance of sequential processing, multiple blocks can be brought in one at a time. It supports sequential access very well because files entire data is stored in adjacent block. This method bra also supports random access.

• Contiguous allocation also suffers from external fragmentation. Small free disk spaces are created after allocation free block and deleting files.. External fragmentation means there will require free space available but that is not contiguous. To solve the problem of external fragmentation, compaction method is used.

• One more problem is that how to calculate the space needed for a file. It is difficult to estimate the required space.

• This method is good for storing data on CD-ROM.

Characteristic of contiguous file allocation :

1. It supports variable size portions.

2. Pre-allocation is required.

3. It requires only single entry for a file.

4. Allocation frequency is only once.

Advantages:

1. It supports variable size portion.

2. Easy to retrieve single block.

3. Accessing a file is easy.

4. It provides good performance.

Disadvantages:

1. It suffers from external fragmentation.

2. Pre-allocation is required.

Linked Allocation

• Linked allocation is also called chained allocation. Operating system keeps an ordered list of free blocks. File descriptor stores pointers to the first block and each block stores pointer to the nest block.

• Fig. 6.10.2 shows linked allocation. The disk blocks may be scattered anywhere on the disk. The directory contains a pointer to the first and last blocks of the file. No space is lost to disk fragmentation.

• Creation of new file is easy. For new file, simply create new entry in the directory. Reading a file is straightforward. User simple read blocks by following pointers from block to block. There is no external fragmentation with linked allocation.

• To write to file, system finds a free block, and this new block is written to and linked to the end of the file.

• While creating a new file, it is not necessary to declare the size of the file. A file can contiguous to grow as long as free blocks are available.

• Compaction can be used so that blocks of one file are located continuously on the disk. It optimizes disk access.

• File allocation table is an extension of the linked allocation method. Instead of putting the pointers in the file, keep a table of the pointers around. This pointer table can be quickly searched to find ant random block in the file.

• Fig. 6.10.3 shows the file allocation table. All blocks on the disk must be included in the table. This method is used by windows operating system.

(Refer Fig. 6.10.3 on next page)

Characteristics

1. It supports fixed size portions.

2. Pre-allocation is possible.

3. File allocation table is one entry for a file.

4. Allocation frequency is low to high.

Advantages:

1. There is no external fragmentation.

2. It is never necessary to compact disk space.

3. Pre-allocation is not required.

Disadvantages:

1. Files are accessed only sequentially.

2. Space required for pointers.

3. Reliability is not good.

4. Can not support direct access.

Indexed Allocation

• Indexed allocation method solves the problem of both contiguous and linked allocation. It uses concept of index block. Index block stores the entire pointer in one location. But the index block will occupy some space and thus could be considered as an overhead of the method.

• OS keeps a list of free blocks. It allocates an array to hold pointers to all the blocks used by the file. It allocates blocks only on demand. Fig. 6.10.4 shows indexed allocation.

• In indexed allocation, each file maintains its own index block. It contains an array of disk sector of addresses. For example: The n^th entry in the index block points to the n^th sector of the file. The directory contains the address of the index block of a file. To read the n^th sector of the file, the pointer in the n^th index block entry

• It supports direct access and without suffering from external fragmentation. Any free block anywhere on the disk may satisfy a request for more space.

• Indexed allocation does suffer from wasted space. The pointer overhead of the index block is generally greater than the pointer overhead of linked allocation. Advantages:

1. It supports sequential and direct access.

2. No external fragmentation.

3. Faster than other two methods.

4. It supports fixed and variable size blocks.

Disadvantages:

1. Indexed allocation does suffer wasted space.

2. Pointer overhead is generally greater.

Comparison of Contiguous, Linked and Indexed File Allocation

1. What are different allocation methods in disk storage? Explain with neat sketch.   AU: Dec.-17, Marks 8

2. What are the various disk space allocation methods. Explain any two in detail.  AU May-18, Marks 13

3. Explain in detail the various allocation methods with their pros and cons.  AU May-19, Marks 8

4. How disc space is allocated in contiguous Allocation method? What is the drawback of this method?  AU May-22, Marks 13