UGC NET CSE | Junet 2015 | Part 3 | Question: 53

Question

In _____ allocation method for disk block allocation in a file system, insertion and deletion of blocks in a file is easy

• A. Index
• B. Linked
• C. Contiguous
• D. Bit Map

Answer 1

ans should be B  linked 

Just like linked list where insertion , deletion of blocks is easy . In linked allocation only pointer needs to be changed 

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.

With linked allocation, each directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a file removes the first free block and writes to that block. This new block is then linked to the end of the file. To read a file, the pointers are just followed from block to block.

There is no external fragmentation with linked allocation. Any free block can be used to satisfy a request. Notice also that there is no need to declare the size of a file when that file is created. A file can continue to grow as long as there are free blocks.

Linked allocation, does have disadvantages, however. The major problem is that it is inefficient to support direct-access; it is effective only for sequential-access files. To find the ith block of a file, it must start at the beginning of that file and follow the pointers until the ith block is reached. Note that each access to a pointer requires a disk read. 
Another severe problem is reliability. A bug in OS or disk hardware failure might result in pointers being lost and damaged. The effect of which could be picking up a wrong pointer and linking it to a free block or into another file.

Comments

Isn't the answer supposed to be indexed allocation? In indexed allocation, for insertion all we need to do is add a free block into the index block entry. For deletion we need to remove the specific entry in the index block. So only one block access i.e. index block access.

While in case of linked allocation we need to sequentially access the blocks until we get to the desired block and then change the pointers. So in worst case we need to access the entire file (i.e. all the blocks of that file).

Answer 2

in Linked allocation

they didn’t say anything particular about pointer so by default we have to assume that it only has pointer of starting block of file. so to add or delete we have to go through all the blocks in file in linked allocation.

and also if you also assume the possibility of last node pointer then there will be many I/O operation

like first writing the new block second reading last block file and then writing node pointer in node. total I/O operation will be 3 

but In index allocation

there will be only 1 write operation in creating new block and index will be updated in main memory.

here is very good reference i found http://www2.cs.uregina.ca/~hamilton/courses/330/notes/allocate/allocate.html