File Allocation - Free MCQ Practice Test with solutions, GATE CSE (CSE)

File allocation methods:

The major file allocation technique is
i. Contiguous allocation
ii. Linked allocation/chain allocation
iii. Index allocation

So non-contiguous is not a type of file allocation methods

Indexing
Indexing is a way to optimize the performance of a database by minimizing the number of disk accesses required when a query is processed.
It is a data structure technique that is used to quickly locate and access the data in a database
There are the following type of Indexes

Primary index
It is maintained for the anchor value of block i,e one key-value per block maintained in Index file.

Clustering index
It is basically a mixed sort of Indexing i,e Dense as it is maintained for unique value (key)  and Sparse as it is not maintained for every value.

• In memory management, swapping creates multiple fragments in the memory because of the processes moving in and out.
• Compaction refers to combining of all the empty spaces together and processes.
• Compaction helps to solve the problem of fragmentation, but it requires a lot of CPU time.
• It moves all the occupied areas of storage to one end and leaves one large free space for incoming jobs, instead of numerous small ones.
• In compaction, the system also maintains relocation information and it must be performed on each new allocation of job to the memory or completion of job from memory.

Dak:
All communication received/issued by an office/department through dak.

Classified dak:  
Dak bearing security grading confidential, secret, etc. is called Classified dak.

The FAT system stores the list of all files in the system and the locations in which they are allocated. A single file may not be allocated in continous memory blocks. Instead it is stored as a linked list, as a result the FAT is also implemented as a linked list.

Indexed file allocation:
In Indexed file allocation, If a file requires n blocks then n+1 blocks are used where the first block contains index information(pointers to data blocks).

• The Indexed file allocation table contains a separate one-level index for each file.
• The index has one entry for each portion allocated to the file.
• The file allocation table contains the block number for the index.

Hence the correct answer is Indexed file allocation.

• At the time of formatting, the FAT is statically allocated. The table is a linked list of entries for each cluster, a contiguous area of disk storage.
• FAT table is used in MSDOS for linked list allocation. 
• The File Allocation Table is used by the file system to define chains of data storage areas associated with a file (FAT). At the time of formatting, the FAT is assigned statically. Each cluster, or contiguous area of disc storage, is represented by a linked list of entries in the table.​

Hence the correct answer is FAT.

Index addressing modes:
Index addressing modes facilitates access to an operand whose location is defined relative to the beginning of the data structure in which it appears.

• In the indexed addressing mode, the content of a particular index register is appended to the address component of an instruction to obtain the effective address.
• The index register refers to a particular CPU register that contains an index value. The address field of an instruction specifies the starting address of any data array in memory.
• Using the index addressing mode, we get flexibility for specifying several locations of the memory.

Hence the correct answer is Index.

Contiguous allocation:
Contiguous allocation occurs when the blocks are allocated to the file in such a way that all of the file's logical blocks are assigned to the same physical block on the memory.
For contiguous allocation,
we have 100 blocks, in contiguous allocation first, we push the 100th block to 101 th block (we need two access), then we push the 99 th block to the 100 th block (we need two access again) and so on up to 51 th block. Now, 51 block is empty, then we push new block to 51 position list need one access).
So, Total access are= 50 read operations+ 50 write operations+1 operation to write the newly inserted block.
Total access are=101 operations (nA)

Linked allocation:
In this scheme, each file is a linked list of disc blocks that do not have to be contiguous. Disk blocks can be placed anywhere on the disc. The directory entry includes a reference to the beginning and end of the file block. Each block carries a reference to the next block occupied by the file.

For linked allocation,
we need to access the block from 1 to 50, new block access that should insert between 50 and 51 blocks, and access 51 blocks. So, the total access is 52.

Total access are= 50 read operations+ 1 operation delete next pointer of 50 th element +1 operation to connect it to the 51 th element.

Total access are=52 operations (n_B)
Total operations are required= n_A+ n_B
Total operations are required= 101+52
Total operations are required= 153.
Hence the correct answer is 153.