操作系統文件分配策略
分配方法 (Allocation Method)
The allocation method defines how the files are stored in the disk blocks. The direct access nature of the disks gives us the flexibility to implement the files. In many cases, different files or many files are stored on the same disk. The main problem that occurs in the operating system is that how we allocate the spaces to these files so that the utilization of disk is efficient and the quick access to the file is possible. There are mainly three methods of file allocation in the disk. Each method has its advantages and disadvantages. Mainly a system uses one method for all files within the system.
分配方法定義文件如何存儲在磁盤塊中。 磁盤的直接訪問特性使我們可以靈活地實現文件。 在許多情況下，不同的文件或許多文件存儲在同一磁盤上。 操作系統中出現的主要問題是我們如何為這些文件分配空間，以便磁盤利用效率高，并且可以快速訪問文件。 磁盤中主要有三種文件分配方法。 每種方法都有其優點和缺點。 主要是系統對系統中的所有文件使用一種方法。
Contiguous allocation
連續分配
Linked allocation
鏈接分配
Indexed allocation
索引分配
The main idea behind contiguous allocation methods is to provide
連續分配方法背后的主要思想是提供
Efficient disk space utilization
高效的磁盤空間利用
Fast access to the file blocks
快速訪問文件塊
連續分配 (Contiguous allocation)
In this scheme, a file is made from the contiguous set of blocks on the disk. Linear ordering on the disk is defined by the disk addresses. In this scheme only one job is accessing the disk block b after that it accesses the block b+1 and there are no head movements. When the movement of the head is needed the head moves only from one track to another track. So the disk number that is required for accessing the contiguous allocation is minimal. Contiguous allocation method provides a good performance that’s why it is used by the IBM VM/CMS operating system. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2,..., b+n-1. This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file. For a contiguous allocation the directory entry the address of the starting block and Length of the allocated portion.
在這種方案中，文件是由磁盤上連續的塊集組成的。 磁盤上的線性順序由磁盤地址定義。 在此方案中，只有一個作業正在訪問磁盤塊b，之后它才訪問塊b + 1，并且沒有磁頭移動。 當需要頭部移動時，頭部僅從一個軌道移動到另一軌道。 因此，訪問連續分配所需的磁盤數量最少。 連續分配方法提供了良好的性能，這就是IBM VM / CMS操作系統使用它的原因。 例如，如果一個文件需要n個塊，并以b作為起始位置，則分配給該文件的塊將為： b，b + 1，b + 2，...，b + n-1 。 這意味著給定起始塊地址和文件長度(以所需的塊數為單位)，我們可以確定文件所占用的塊。 對于連續分配，目錄條目的起始塊的地址和分配部分的長度。
The file 'A' in the following figure starts from block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.
下圖中的文件“ A”從塊19開始，其長度= 6個塊 。 因此，它占用19、20、21、22、23、24個塊。
Each file in the disk occupies a contiguous address space on the disk.
磁盤中的每個文件都占據磁盤上連續的地址空間。
In this scheme, the address is assigned in the linear fashion.
在此方案中，以線性方式分配地址。
The is very easy to implement the contiguous allocation method.
實現連續分配方法非常容易。
In the contiguous allocation technique, external fragmentation is a major issue.
在連續分配技術中，外部碎片化是一個主要問題。
Advantages:
優點：
In the contiguous allocation, sequential and direct access both are supported.
在連續分配中，同時支持順序訪問和直接訪問。
For the direct access, the starting address of the kth block is given and further blocks are obtained by b+K,
對于直接訪問，給出第k個塊的起始地址，并通過b + K獲得其他塊，
This is very fast and the number of seeks is minimal in the contiguous allocation method.
在連續分配方法中，這非常快并且搜尋次數最少。
Disadvantages:
缺點：
Contiguous allocation method suffers internal as well as external fragmentation.
連續分配方法遭受內部和外部碎片。
In terms of memory utilization, this method is inefficient.
在內存利用率方面，此方法效率低下。
It is difficult to increase the file size because it depends on the availability of contiguous memory.
很難增加文件的大小，因為它取決于連續內存的可用性。
Example:
例：
| File | Start | Length |
|---|---|---|
| Count | 0 | 2 |
| Tr | 14 | 3 |
| 19 | 6 | |
| List | 28 | 4 |
| 文件 | 開始 | 長度 |
|---|---|---|
| 計數 | 0 | 2 |
| Tr | 14 | 3 |
| 郵件 | 19 | 6 |
| 清單 | 28 | 4 |
鏈接分配 (Linked allocation)
The problems of contiguous allocation are solved in the linked allocation method. In this scheme, disk blocks are arranged in the linked list form which is not contiguous. The disk block is scattered in the disk. In this scheme, the directory entry contains the pointer of the first block and pointer of the ending block. These pointers are not for the users. For example, a file of six blocks starts at block 10 and end at the block. Each pointer contains the address of the next block. When we create a new file we simply create a new entry with the linked allocation. Each directory contains the pointer to the first disk block of the file. when the pointer is nil then it defines the empty file.
鏈接分配方法解決了連續分配的問題。 在這種方案中，磁盤塊以不連續的鏈表形式排列。 磁盤塊分散在磁盤中。 在此方案中，目錄條目包含第一個塊的指針和結束塊的指針。 這些指針不適用于用戶。 例如，六個塊的文件從塊10開始，到塊結束。 每個指針都包含下一個塊的地址。 當我們創建一個新文件時，我們只需創建一個帶有鏈接分配的新條目。 每個目錄都包含指向文件第一個磁盤塊的指針。 當指針為nil時，它將定義空文件。
Advantages:
優點：
In terms of the file size, this scheme is very flexible.
就文件大小而言，此方案非常靈活。
We can easily increase or decrease the file size and system does not worry about the contiguous chunks of memory.
我們可以輕松地增加或減少文件大小，并且系統不必擔心連續的內存塊。
This method free from external fragmentation this makes it better in terms of memory utilization.
此方法沒有外部碎片，因此在內存利用率方面更好。
Disadvantages:
缺點：
In this scheme, there is large no of seeks because the file blocks are randomly distributed on disk.
在這種方案中，由于文件塊是隨機分布在磁盤上的，因此不需要大量查找。
Linked allocation is comparatively slower than contiguous allocation.
鏈接分配比連續分配要慢。
Random or direct access is not supported by this scheme we cannot access the blocks directly.
此方案不支持隨機或直接訪問，我們無法直接訪問塊。
The pointer is extra overhead on the system due to the linked list.
由于鏈接列表，指針在系統上會產生額外的開銷。
索引分配 (Indexed Allocation)
In this scheme, a special block known as the index block contains the pointer to all the blocks occupied by a file. each file contains its index which is in the form of an array of disk block addresses. The ith entry of index block point to the ith block of the file. The address of the index block is maintained by the directory. When we create a file all pointer is set to nil. A block is obtained from the free space manager when the first ith block is written. When the index block is very small it is difficult to hold all the pointers for the large file. to deal with this issue a mechanism is available. Mechanism includes the following:
在此方案中，稱為索引塊的特殊塊包含指向文件所占據的所有塊的指針。 每個文件都包含其索引，該索引采用磁盤塊地址數組的形式。 索引塊的第i個條目指向文件的第i個塊。 索引塊的地址由目錄維護。 創建文件時，所有指針都設置為nil。 當第一個第i個塊被寫入時，將從可用空間管理器中獲得一個塊。 當索引塊很小時，很難保存大文件的所有指針。 解決此問題的機制是可用的。 機制包括以下內容：
Linked scheme
鏈接方案
Multilevel scheme
多級方案
Combined scheme
組合方案
Advantages:
優點：
This scheme supports random access of the file.
該方案支持文件的隨機訪問。
This scheme provides fast access to the file blocks.
該方案提供對文件塊的快速訪問。
This scheme is free from the problem of external fragmentation.
該方案沒有外部碎片的問題。
Disadvantages:
缺點：
The pointer head is relatively greater than the linked allocation of the file.
指針頭相對大于文件的鏈接分配。
Indexed allocation suffers from the wasted space.
索引分配遭受空間浪費。
For the large size file, it is very difficult for single index block to hold all the pointers.
對于大文件，單個索引塊很難容納所有指針。
For very small files say files that expend only 2-3 blocks the indexed allocation would keep on the entire block for the pointers which is insufficient in terms of memory utilization.
對于很小的文件，例如僅消耗2-3個塊的文件，索引分配將保留整個塊的指針，這在內存利用率方面是不夠的。
翻譯自: https://www.includehelp.com/operating-systems/file-allocation-method.aspx
操作系統文件分配策略
