Continuous distribution

Continuous allocation requires each file to occupy a continuous block on the disk.

Advantages: support sequential access and direct access (i.e. random access); files allocated continuously are the fastest in sequential access.

Disadvantages: inconvenient file expansion; Low utilization of storage space will cause disk fragmentation.

Link assignment

Link allocation adopts discrete allocation, which can allocate discrete disk blocks to files. There are implicit links and explicit links.

Implicit / explicit link assignment is not specified in the test questions. The default refers to the link assignment of implicit links.

Implicit link - except for the last disk block of the file, there is a pointer to the next disk block in each disk block. The file directory includes a pointer to the first block and a pointer to the last block of the file.

Advantages: it is very convenient for file expansion, there will be no fragmentation problem, and the utilization rate of external memory is high.

Disadvantages: only sequential access is supported, random access is not supported, search efficiency is low, and the pointer to the next disk block also consumes a small amount of storage space.

Explicit link - the pointers used to link the physical blocks of the file are explicitly stored in a table, namely, the file allocation table (fat). A disk will only establish a file allocation table. When starting up, the file allocation table will be put into memory and resident in memory.

Advantages: it is very convenient for file expansion, no fragmentation problem, high utilization of external memory, and supports random access. Compared with implicit links, there is no need to access the disk during address translation, so the file access efficiency is higher.

Disadvantages: the file allocation table needs to occupy a certain storage space.

Index allocation

Index allocation allows files to be discretely allocated in disk blocks. The system will establish an index table for each file, The index table records the physical blocks corresponding to each logical block of the file (the function of the index table is similar to the page table in memory management - establishing the mapping relationship between logical pages and physical pages). The disk blocks stored in the index table are called index blocks, and the disk blocks stored in file data are called data blocks.

If the file is too large and there are too many index table entries, the following three methods can be adopted:

1、Link scheme: if the index table is too large to fit one index block, multiple index blocks can be linked and stored. Disadvantages: if file is large and index table is long, many index blocks need to be linked. If you want to find index block I, you must read index blocks 0 ~ I-1 in turn, which leads to excessive disk I / O times and low search efficiency.

2、 Multi level index: build multi-level index (the principle is similar to the multi-level page table). Make the first layer index block point to the second layer index block, and then establish the third and fourth layer index blocks according to the file size requirements. If the k-layer index structure is adopted, and the top-level index table is not transferred into memory, it only needs K + 1 disk read operations to access a data block. Disadvantages: even for small files, K + is still required to access a data block Read the disk once.

3、Hybrid index: a combination of multiple index allocation methods. For example, the top-level index table of a file contains both direct address indexes (directly pointing to the data block), one-level indirect indexes (pointing to the single-layer index table) and two-level indirect indexes (pointing to the two-layer index table). Advantage: for small files, less disk reads are required to access a data block.

Super important test sites: 1) learn to use the structure of multi-layer index and mixed index, Calculate the maximum length of the file (key: the maximum number of index tables at all levels cannot exceed one block); 2) analyze the number of disk reads required to access a data block by yourself (key: there will be a pointer to the top-level index block in the FCB, so you can read the top-level index block according to the FCB. Each time you read the next level index block, you need to read the disk. In addition, pay attention to the problem condition -whether the top-level index block has been transferred into memory).