1. Continuous distribution:
Continuous allocation is to allocate a group of continuous blocks on the disk to store a file. Each block of the disk has an address and is arranged linearly. Then the computer only needs to store the file name, file header address and file length.
The advantages of this allocation method are: 1. Easy access; 2. Because the file system will remember the address of the last access, this method supports direct access and sequential access.
Disadvantages are:
1) New file allocation and expansion: When a file is created, we need to allocate space according to the size of the file, but during the use of the file, the file may become larger or be deleted. If the documents cling to each other, it is difficult to expand; One solution is: when there is not enough space, add an expansion pointer to the last block to expand to another empty block, and so on.
If we allocate a certain expandable space to each file, but when users stop expanding some files, space will be wasted.
2) External fragmentation (the whole block can't be used): In the process of constantly adding and deleting files, some concentrated small blocks can't be used, the files around them don't expand, and no such small files can be stored in them, which will cause waste. One solution is to periodically merge these small fragments, and move the positions of other file blocks to concentrate these small fragments into a large block for later use. However, this method has a serious time cost, and it will make the computer unable to work during this period.
2. Link allocation:
The idea of this allocation method is similar to linked list, each block is a node, and the tail of each block stores the address of the next block. When accessing a file, when accessing the end of a block, get the address of the next block, so as to access the next block. When accessing the file, the address of that block is a specific terminator, so the directory structure of the file only needs the file name, starting address and ending address.
The advantages of distribution are:
1) There will be no external fragmentation problem, because this allocation method has no position limitation, and any block can point to any block or be pointed by any block.
2) Easy to expand: If a file needs to be expanded, it only needs to add a node at the end of the file chain and modify the original end node and the ending address of the file directory.
But link allocation also has its own defects:
1) Only sequential access: due to the linked list used in this disk allocation method, only sequential access is allowed. To access the I-th block of the file, you must start from the beginning and follow the pointer to find the I-th block.
2) Pointer wastes memory: Because each block needs to store extra pointers, it wastes space. One optimization method is: multiple blocks share one address, which is regarded as a block and called a cluster. This can effectively reduce the number of pointers, but if the last cluster can't be used up, for example, a cluster contains 4 blocks, but the file+pointer needs 13 blocks in total, then 4 clusters are needed, but only one block is used in the last cluster, and one cluster shares an address, so the other three blocks can't be allocated and can only be wasted.
3. Index allocation:
In order to solve the above two problems, index allocation can be adopted. Index allocation simply means that the pointers assigned by the links are stored in a block in a centralized order, so the file directory only needs to store the file name and the address of the index block, and then access it in this block in turn according to the address. Of course, you can also directly access it after you directly query the address you want to access through the offset.
There is a problem with this access method: the number of index addresses stored in a block is limited, so how to grasp the allocation? Mechanisms for this purpose include the following:
1) Link scheme: Simply put, the index block is expanded by link allocation. When one index block is used up, it is linked to the next block through a pointer.
2) Multi-level index: Just like a tree, the index block of the directory points to the root node, and then the address in the block points to another block, which is the second-level index, and so on.
3) Combination scheme: For example, an index block contains 15 pointers (direct block plus indirect block), of which the first 12 pointers are direct blocks; That is, they include the addresses of blocks that can store file data. Therefore, small files do not need other index blocks. The first-level indirect block is the two-level index structure, the second-level indirect block is the three-level index structure, and the third-level indirect block is the four-level index structure. By this layered way, files of different sizes can be allocated to the appropriate index structure.