编程知识 cdmana.com

Operating system review notes Chapter 11 file system implementation

  • 11.4 Distribution method
    • 11.4.1 Continuous distribution
      • The continuous allocation method requires each file to have a set of contiguous blocks on disk . The disk address defines a linear sequence for the disk .
      • The continuous allocation of files can be defined by the disk address of the first block and the number of consecutive blocks . If the document has n Block length and from position b Start , Then the file will occupy the block b,b+1,b+2…,b+n-1. The directory entry of a file includes the address of the start block and the length of the area allocated by the file ,
      • Access to a contiguous distribution file is easy . To access in sequence , The file system remembers the disk address of the last block accessed , Read in the next piece if necessary . To access a slave block directly b Start the file block i, You can access blocks directly b+i. Therefore, sequential allocation supports sequential access and direct access .
      • problem : External debris
      • How to determine how much space a file needs .
      • resolvent : Terminate the user program And add the appropriate error message . The user has to allocate more space and run the program here . These repetitions can be costly . Another possibility is to find a bigger hole , Copy the contents of the file to the new space , Release the old space .
      • Modified continuous allocation scheme : Start allocating a contiguous space , When there is not enough space , Another piece of contiguous space called an extension is added to the original allocation , such , The location of the file block is called the start address 、 Number of blocks 、 The next extension of the pointer .
    • 11.4.2 Link assignments
      • Link assignments All the problems of continuous distribution are solved . Use link assignment , Each file is a linked list of disk blocks ; Disk blocks are distributed anywhere on the disk . The directory includes pointers to the first and last block of the file .
      • Connection assignment create file , You can simply add a new entry to the catalog , For link assignment , Each directory entry has a pointer to the first block of the file . When creating a file , There is no need to specify the file size , As long as there are free blocks , The file can be enlarged . therefore , No need to merge disk space .
      • shortcoming : Can only be effectively used for sequential access to files . Can't effectively support direct access to files . At the same time, the pointer needs space .
      • resolvent : Cluster multiple fast (cluster) Allocate by cluster, not by block
      • A variant of the link allocation method is the file allocation table FAT Use
    • 11.4.3 Index allocation
      • Link allocation solves the problem of external fragmentation and size declaration of continuous allocation . however , If not FAT, Then link assignment cannot support direct access effectively , This is because the block pointer is distributed along with the block across the disk , And must be read in order . Index allocation (indexed allocation) By putting all the pointers together , This problem is solved by index block .
      • Index allocation supports direct access , And there's no external fragmentation problem , This is because any block on the disk can meet more space requirements . Index allocation wastes space . Index block pointers are usually more expensive than link allocation pointers . Imagine, in general , Each file is only one or two long . Use link assignment , Only one pointer is wasted per block . Using index allocation , Although only one or two pointers are non null , A complete index block must also be allocated .
      • The solution to the problem of index allocation :
      • Link scheme Multiple index blocks link
      • Multi level index
      • Combination plan
    • 11.4.4 performance
      • performance : Without consumption , Just consider the benefits / efficiency
      • efficiency : The income of unit resource harvest
  • 11.5 Free space management
    • To record free disk space , The system needs to maintain a linked list of free space .(free-space list) The free space list records all the free disk space , Space not allocated to a file or directory . When you create a file , Search the free space list to get the required space , And assign it to a new file . These spaces are removed from the list of free spaces . When you delete a file , Its disk space will be added to the free space table . The free space list is called a linked list , But it doesn't have to be a linked list ,
    • 11.5.1 Bit vector
      • Usually , The free space table is implemented as a bitmap (bit map) Or a bit vector (bit vector). Each piece is represented by a bit . If a piece is free , Then its position is 1; If a piece has been allocated , Then its position is 0.
      • The main advantage of this method is to find the first free block on the disk and n Continuous free blocks are relatively simple and efficient .
    • 11.5.2 Linked list
      • Another way to manage free space is to connect all the free space disk blocks with a linked list , And save the pointer to the first free block in a special location on the disk , It's also cached in memory .
      • however , The efficiency of this scheme is not high ; To traverse the entire table , Every piece needs to be read in , It takes a lot of I/O Time . Fortunately, traversing the entire table is not a regular operation . Usually , The operating system simply needs a free block to allocate to a file , So you can allocate the first block of the free table .FAT Method combines the calculation of free blocks into the allocation data structure , There's no need for another way .
    • 11.5.3 Group
      • One improvement to the free list is to make n Addresses of free blocks exist in the first free block . Of these blocks n-1 It's really empty , And the last piece contains something else n Addresses of free blocks , Go on like this . The addresses of a large number of free blocks can be found quickly , This is different from the standard linked list method .
    • 11.5.4 Count
      • Another way is to take advantage of the fact that : Usually , There are multiple contiguous blocks that need to be allocated or released at the same time , This is especially true when using continuous allocation and clustering . therefore , It's not a record n Addresses of free blocks , Instead, it can record the address of the first block and the number of consecutive free blocks immediately following the first block n. such , Each entry in the free space table includes the disk address and number . Although each item will need more space than before , But the total length of the table will be shorter , This is because the number of contiguous blocks is often greater than 1.

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[The struggling rabbit of florist]所创,转载请带上原文链接,感谢

Scroll to Top