To improve I/O efficiency, I/O transfers between memory and disk are performed in units of blocks. the usual size is 512 bytes.

文件系统的分级结构

I/O control:负责主存与磁盘间的信息传输。需要一个 driver 作为 translator

basic file system:组织发送给 driver 的命令,管理 buffer, cache

file-organization module:的层次有文件块或物理块的概念。can translate logical block addresses to physical block addresses for the basic file system to transfer

also includes the free-space manager, which tracks unallocated blocks and provides these blocks to the file-organization module when requested

logical file system:管理元数据信息

Metadata includes all of the file-system structure except the actual data (or contents of the files). The logical file system manages the directory structure to provide the file-organization module with the information the latter needs, given a symbolic file name. It maintains file structure via file-control blocks.

A filecontrol block (FCB) (an inode in UNIX file systems) contains information about the file, including ownership, permissions, and location of the file contents. The logical file system is also responsible for protection

The I/O control and sometimes the basic file-system code can be used by multiple file systems. Each file system can then have its own logical file-system and file-organization modules.

文件系统实现

operating systems implement open() and close() systems calls for processes to request access to file contents

Severalon-disk and in-memory structures are used to implement a file system

On disk

  • A boot control block (per volume) can contain information needed by the system to boot an operating system from that volume. If the disk does not contain an operating system, this block can be empty. It is typically the first block of a volume. In UFS, it is called the boot block. In NTFS, it is the partition boot sector.
  • A volume control block (per volume) contains volume (or partition) details, such as the number of blocks in the partition, the size of the blocks, a free-block count and free-block pointers, and a free-FCB count and FCB pointers. In UFS, this is called a superblock. In NTFS, it is stored in the master file table.
  • A directory structure (per file system) is used to organize the files. In UFS, this includes file names and associated inode numbers. In NTFS, it is stored in the master file table.
  • A per-file FCB contains many details about the file. It has a unique identifier number to allow association with a directory entry. In NTFS, this information is actually stored within the master file table, which uses a relational database structure, with a row per file.

in-memory

  • mount table : contains information about each mounted volume.

磁盘调度算法

假设有很多进程想要访问磁盘,访问的磁盘位置各不相同。我们希望平均 IO 时间最小,同时不能让进程等太久,就需要合理调整访问的顺序。这就是磁盘调度算法。

On a disk drive with 5000 cylinders, numbered from 0 to 4999 , the last request served was at cylinder 125 , and the head is at cylinder 143. The queue of pending request, in FIFO order, is

86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests in the queue, for the following disk scheduling algorithms? It is required that the procedure of the arm moving to serve the requests should be illustrated by a figure.

(1) SSTF

143, 86, 130, 913, 948, 1022, 1470, 1509, 1750, 1774

距离:

(143-86)=57
(86-130)=44
(130-913)=783
(913-948)=35
(948-1022)=74
(1022-1470)=448
(1470-1509)=39
(1509-1750)=241
(1750-1774)=24
57 + 44 + 783 + 35 + 74 + 448 + 39 + 241 + 24 = 1745

(2) C-SCAN

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130

143 -> 4999 -> 0 -> 130

(4999 - 143) + (4999) + 130 = 9985

(3) SCAN

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86

143 -> 4999  -> 86

4999 - 143 + (4999 - 86) = 4769

(4)LOOK

143 -> 1774 -> 86

1774 - 143 + 1774 - 86 = 3319

(5)C-LOOK

143 -> 1774 -> 86 -> 130

1774 - 143 + 1774 - 86 + 130 - 86 = 3363
算法 介绍
FCFS 先来先服务
SSTF 最短查找时间优先
SCAN 来回扫描,朴素电梯算法
C-SCAN 循环扫描
LOOK 改进 SCAN,提前折返,正常电梯算法
C-LOOK 环形 LOOK

https://blog.csdn.net/tjuyanming/article/details/77945887

例子 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

a. FCFS

调度顺序为:143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130,总寻求距离为 7081。

b. SSTF

调度顺序为:143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774, 总寻求距离为 1745

c. SCAN

调度顺序为:143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86, 总寻求距离为 9769

d. LOOK

调度顺序为:143, 913, 948, 1022, 1470, 1509, 1750, 1774,

130, 86, 总寻求距离为 3319

e. C-SCAN

调度顺序为:143, 913, 948, 1022, 1470, 1509, 1750, 1774,

4999, 86, 130, 总寻求距离为 9813