File storage space management
Partition and initialization of storage space
-
Division of storage space: divide the physical disk into file volumes (logical volumes and logical disks)
For example: install Windows When operating the system, a necessary step is--Partition a disk( C:Disk D:Disk E:Panel, etc.) as shown below
- Initialization of storage space: divide each file volume into directory area and file area.
The directory area mainly stores file directory information (FCB) and information for disk storage space management
The file area is used to store file data - Some systems support super large files and can support a file volume composed of multiple physical disks
- Initialization of storage space: divide each file volume into directory area and file area.
Storage space management
Free table method - applicable to "continuous allocation method"
- Free disk block table
| First free disk block number | Number of free disk blocks |
|---|---|
| 0 | 2 |
| 5 | 1 |
| 13 | 2 |
| 18 | 3 |
| 23 | 1 |
- How to allocate disk blocks: similar to dynamic partition allocation in memory management, allocate continuous storage space for a file. Similarly, first adaptation, best adaptation, worst adaptation and other algorithms can be used to determine which interval to allocate to the file.
- How to reclaim disk blocks: similar to the dynamic partition allocation in memory management, there are four situations when reclaiming a storage area - ① there is no adjacent free area before and after the reclaiming area; ② The front and back of the recycling area are free areas; ③ There is a free area in front of the recycling area; ④ After the recycle area is the free area** In short, attention should be paid to the consolidation of table items during recycling.
Free linked list method
-
Free disk block chain: a free chain is formed in disk blocks
The operating system stores the chain head and tail pointers How to allocate: if a document is applied for K If there are two disk blocks, remove them successively from the chain head K Allocate disk blocks and modify the chain head pointer of the idle chain How to recycle: the recycled disk blocks are hung to the tail of the chain in turn, and the tail pointer of the idle chain is modified ((consistent with linked list operation) Physical structure suitable for discrete allocation. Multiple operations may be repeated when assigning multiple extents to a file.
-
Idle extent chain: an idle chain is formed by taking the extent as a unit
Continuous free disk blocks form a free disk area The first disk block in the free disk area records the length of the disk area and the pointer of the next disk area How to allocate: a file application K For each disk block, algorithms such as first adaptation and best adaptation can be used to search from the chain head and find a matching disk according to the algorithm rules The required free extent is allocated to the file. If there is no suitable continuous free block, you can also allocate blocks from different extents to one file at the same time, Note that the corresponding chain pointer, disk size and other data may need to be modified after allocation How to recycle: if the recycle area is adjacent to an idle panel, you need to merge the recycle area into the idle panel. If the recycle area is not adjacent to any free area, it will be recycled The area is hung to the end of the chain as a separate free disk area.
Position diagram method
-
Bit diagram - continuous assignment and discrete assignment are applicable
Each binary corresponds to a disk block. In this example, "0" means that the disk block is free and "1" means that the disk block has been allocated.
Bit diagrams are generally represented by continuous "words". For example, in this example, the word length of a word is 16 bits, and each bit in the word corresponds to a disk block. Therefore, you can use (font size, tag number) to correspond to a disk block number.Formula for mutual conversion between disk block number and (font size, tag number) In this example, the disk block number, font size and tag number start from 0, if n Indicates the word length, then ((font size, tag number)=(i,j)Disk block number corresponding to the binary bit of b=ni+j b Font size corresponding to disk block No i=b/n，Tag number j=b%n
How to allocate: if necessary K A block, ①Scan bit diagram in sequence and find K Adjacent or non adjacent "0"; ②Calculate the corresponding disk block number according to the font size and tag number, and assign the corresponding disk block to the file; ③Set the corresponding bit to "1".
Group linking method
File sharing
Index node based sharing (hard link)
- Index node is a strategy to reduce the size of files and directories. Because only the file name is needed to retrieve the file, other information other than the file name can be put into the index node. In this way, the directory entry only needs to contain the file name and index node pointer.
- A connection count variable count is set in the index node to identify the number of user directory items linked to the index node.
- If a user decides to "delete" a file, only the directory entry corresponding to the modified file in the user directory will be deleted, and the count value of the index node will be reduced by 1.
Sharing mode based on symbolic chain (soft link)
- Record the storage path of shared files in a Link file (similar to shortcuts in Windows)
- Even if the shared file pointed to by the soft Link has been deleted, the Link file still exists. Just finding the shared file through the path in the Link file will fail (the corresponding directory item cannot be found)
- When accessing shared files by soft link, you need to query multi-level directories, and there will be multiple disk I/O
File protection
Password protection
Set a "password" for the file (e.g:abc1123)，The user must provide a "password" when requesting access to the file Advantages: the idle cost of saving the password is not much, and the time cost of verifying the password is also small Disadvantages: the correct password is stored in the system, which is not safe enough
Encryption protection
Use a "password" to encrypt the file. When accessing the file, you need to provide the correct "password" to decrypt the file correctly Eg: The simplest encryption algorithm -- XOR encryption Advantages: strong confidentiality, no need to store "password" in the system Disadvantages: coding/Decoding, or encryption/Decryption takes some time
access control
At the end of each file( FCB)Add an access control list in( ACL)，This table records what operations each user can perform on the file The implementation is flexible and can realize complex file protection functions
Hierarchy of file system
Disk structure
Disk, track, sector
-
The surface of a magnetic disk is made up of some magnetic materials, which can be used to record binary data
-
The disk tracks are divided into disk surfaces. A "circle" is a track
-
A track is divided into sectors, and each sector is a "disk block". Each sector stores the same amount of data.
-
The sector area on the innermost track is the smallest, so the data density is the largest
Read / write data on disk
- You need to move the "head" to the track where the sector you want to read / write is located
- The disk will rotate and the target sector will cross under the head to complete the read / write operation to the sector
Disk / cylinder concept
- The disk has multiple disks "stacked", and each disk has two disk surfaces
- The relative positions in all disk surfaces form a cylindrical surface from the same track
Physical address of the disk
- You can use * * (cylinder number, disk number, sector number) * * to locate any "disk block".
Disk classification
Depending on whether the head is movable
- Active head disk
The magnetic head that can move is called the movable head disk. The magnetic arm can stretch back and forth to drive the magnetic head to locate the track - Fixed head disk
A disk with a non removable head is called a fixed head disk. This disk has one head per track
Depending on whether the disc is replaceable
- Fixed disk
- Replaceable disk
Disk scheduling algorithm
Time required for a disk read / write operation
- Seek time (seek time) Ts: the time taken to move the head to the specified track before reading / writing data
① Moving the head arm takes time. Suppose the time is s;
② Moving the head also takes time. Assuming that the magnetic head moves at a uniform speed, it takes m to cross each track, and a total of n tracks need to be crossed. Then:
Seek time Ts=s+m*n - Delay time Tr: the time required to position the head to the target sector by rotating the disk. Set the disk speed as r (unit: r / s, or r / min), then the average required delay time Tr = (1 / 2) * (1/r) = 1/2r
- Transmission time Tt: the time spent reading or writing data from or to the disk. Assuming that the disk speed is r, the number of bytes read / written this time is b, and the number of bytes on each track is N. Then:
Transmission time Tt = (1/r) * (b/N) = b/(rN)