Linux磁盘调度

待我称王封你为后i 2023-10-03 00:54 37阅读 0赞

### 一、磁盘结构 ###

##### 1.1 磁盘结构 #####

磁盘主要由磁道、扇区、柱面以及磁头构成  
![image-20210829143537835.png][] ![image-20210829143608841.png][] ![image-20210829144457948.png][]

*  磁道：能被磁头访问一组同心圆
 *  扇区：磁道上的区域，数据存放的基本单位
 *  柱面：所有盘片同一磁头下的磁道集合(不同盘片的相同磁道的磁头是一起旋转的)

对于磁道的划分有两种方式：每条磁道上的扇区数相等、每条磁道上的数据密度相等(外围的磁道有更多的扇区)

磁道划分方式的不同，对应这磁头旋转速度的不同

*  恒角速度(内外磁道磁头转动的速度一样)
    
    适用不同磁道密度不同，但转速恒定
 *  恒线速度(内外磁道磁头转到的距离一样)
    
    磁道密度相同，但转速根据磁道变化而变化，内圈转速块，外圈转速慢

`恒角速度的好处是实现简单,但浪费磁盘空间;恒线速度好处是充分使用了磁盘,但实现复杂;硬磁盘采用恒角速度的方式,DVD/CD采用恒线速度的方式`

##### 1.2 磁盘格式化 #####

*  低级格式化(Low-level formating)
    
     *  低级格式化也称为物理格式化(Physical formating)，
     *  为每个扇区适用特殊的数据结构进行填充，包括一个头部、数据区域和尾部
     *  头部和尾部包含一些控制信息，如扇区号、ECC码(校验码)等
    
    `低级格式化相当于把一个很大的楼分隔成大小相等的房间的过程,磁盘就是这栋大楼,每个房间就是一个扇区,每个房间的门牌号就是扇区号`
 *  高级格式化(high-level formating)
    
     *  高级格式化称为Logical formating
     *  构件文件系统，在磁盘上初始化文件系统数据结构，如空闲和已分配空间表、一个空目录等
    
    `我们通常对U盘就行格式化的时候,就是做高级格式化,为U盘选择一种文件系统`
    
    `选择文件系统就相当于选择大楼来做什么,作为医院,每个房间就变成了病房或者医生办公室;如果作为警察局,房间就变成了拘留室或审讯室`
    
    常用的文件系统：NTFST(Windos)、ext3和ext4(Linxu)、HFS(Mac)以及支持这三种操作系统的exFat文件系统

### 二、磁盘性能 ###

##### 2.1 磁盘性能指标 #####

查找一个物理块(扇区)的顺序：柱面号、磁头号、扇区号

*  寻道时间Ts
    
    将磁头定位到正确磁道(柱面)上所花的时间，与盘片直径和传动臂速度相关，平均20ms
 *  旋转延迟Tr
    
    所查找的扇区转到磁头下所用的时间，与磁盘的旋转速度有关，一个10000/m的磁盘平均旋转延迟为3ms
 *  传送时间T
    
    传送扇区内的数据的时间，同样取决于磁盘的旋转速度，T = b/(rN)(b为要传送的字节数，N为一个磁道中的字节数，r为转速)

总的平均时间：Ta = Ts + Tr + T

##### 2.2 实例分析：磁盘性能 #####

*  条件假设
    
     *  平均寻道时间为5ms，平均旋转时间为4ms
     *  传输速度为4MBytes/s，扇区大小为1KBytes
 *  如果随机访问一个扇区
    
    Ta = 5ms + 4ms + 1k/4M s ≈ 10ms
    
    总的存取速率 = 1KBytes / 10ms = 100KBytes/sec
 *  如果要访问的扇区位于同一柱面
    
    Ta = 4ms + 1k/4M s ≈ 5ms
    
    总的存取速率 = 1KBytes / 5ms = 200KBytes/sec
 *  如果访问的扇区位于同一磁道
    
    Ta = 1k/4M s = 0.25ms
    
    总的存取速率 = 1KBytes / 0.25ms = 4MBytes/sec

### 三、磁盘调度 ###

无论进程需要从磁盘读取还是向磁盘写入，都将向操作系统发起一个系统调用，系统调用的请求包含以下数据：

进程是从磁盘读还是写、传输的磁盘地址(柱面、磁道、扇区)和内存地址以及扇区数量

##### 3.1 Disk Scheduling #####

对于有很多进程的多道程序系统，每时每刻都有很多进程发起I/O调用，操作系统会把这些I/O请求放入到磁盘队列里面，磁盘队列里面可能有很多未处理的请求，然后当一个I/O请求处理完成后，操作系统该选择哪一个I/O请求进行处理，就是磁盘调度算法要做的事情

![image-20210829161140176.png][]

##### 3.2 磁盘调度算法 #####

###### 3.2.1 FCFS SCHEDULING(先来先服务) ######

假设磁盘队列里面存放的是柱面号，每两个柱面号之差看作柱面的寻道时间(单位：ms)

磁盘队列Disk Queue = \{98，183，37，122，14，124，65，67\}

磁头Head starts at 53

FCFS算法的队列访问流程如下：  
![image-20210829161605133.png][]  
采用FCFS的方案，处理完Disk Queue里面的I/O请求后，磁头寻道时间共用了640ms

###### 3.2.2 SSTF SCHEDULING ######

SSTF(Shortest-Seek-Time First)最短寻道时间有限，磁盘调度器每次处理距离当前柱面号最近的一个柱面的I/O请求

SSTF算法的队列访问流程如下：  
![image-20210829162751070.png][]  
采用SSTF的方案，处理完Disk Queue里面的I/O请求后，磁头寻道时间共用了236ms

这种方案的弊端是有可能会造成”磁臂粘连“现象(饥饿现象)，即磁盘队列后面到来的请求如果都是距离当前柱面比较近的，就会导致队列中距离当前柱面比较远的柱面的I/O请求总是得不到处理。

###### 3.2.3 SCAN SCHEDULING(扫描算法) ######

因为磁头在做寻道时，需要前后摆动，扫描算法则让磁头从当前位置往一个方向移动(向前或向后)，假设一共有200个柱面，磁头从53号开始，向前面0号柱面移动，到达0号柱面之后在向后面200号柱面移动，移动过程中，判断当前柱面是否在磁盘队列的请求里面，当移动到某个柱面后，磁盘队列没有请求了，磁头就悬浮在当前柱面不再移动

如果磁盘队列里面一直有数据，SCAN算法会让磁头来回折返，依次往复

SCAN算法的队列访问流程如下：  
![image-20210829164506561.png][]  
采用SCAN的方案，不会出现饥饿现象，负载均衡的效果非常好

###### 3.2.4 C-SCAN SCHEDULING ######

C-SCAN扫描算法相比与SCAN算法，它的扫描顺序是固定的，不像SCAN算法是来回折返扫描，其他都是一样的，它总是从0往最大柱面号方向扫描

C-SCAN算法的队列访问流程如下：

![image-20210829170107989.png][]

###### 3.2.5 LOOK SCHEDULING ######

LOOK算法是基于SCAN算法的，与SCAN算法不同的是，它向某个方向扫描的时候，会判断磁盘队列里面是否还有这个方向的柱面，如果队列里面已经没有这个方向的柱面，继续扫描，就纯属浪费时间了，LOOK算法会及时调整它的扫描方向，并不是等磁道一直扫描到首个柱面或最后一个柱面才调整方向

LOOK算法的队列访问流程如下：

![image-20210829171929846.png][]

`还有一种C-LOOK的算法,C-LOOK是基于C-SCAN实现`

###### 3.2.6 调度算法的区别 ######

*  FCFS算法是最简单实现的
 *  SSTF算法是比较常用，但是它会导致饥饿现象
 *  SCAN和C-SCAN算法在对磁盘负载比较重的系统中表现比较好

##### 3.3 Linux I/O调度 #####

###### 3.3.1 查看Linux系统采用的磁盘调度算法 ######

#可以看到linux虚拟机使用的调度算法是mq-deadline,同时还支持none算法
    root@Dog-li:/home/lizhi# cat /sys/block/sda/queue/scheduler 
    [mq-deadline] none
    
    #阿里云的Linux服务器使用的调度算法
    [root@iZwz9gptd6bqapsj3bih7iZ vda]# cat /sys/block/vda/queue/scheduler 
    [mq-deadline] kyber bfq none
    
    #更改本地虚拟机调度算法
    root@Dog-li:/home/lizhi# echo none > /sys/block/sda/queue/scheduler 
    root@Dog-li:/home/lizhi# cat /sys/block/sda/queue/scheduler 
    [none] mq-deadline

###### 3.3.2 Linux I/O调度算法 ######

*  noop
    
    使用FCFS策略，对于SSD有更好的性能，因为固态硬盘没有磁道这些概念
 *  deadline
    
    创建两个队列：一个读队列和一个写队列，每一个IO请求都包含一个过期时间的时间戳，当某个IO请求快到达过期时间时，这个请求将会赋予很高的优先级，保证能在时间之前初期该IO请求。创建两个队列的原因是因为读的优先级和写的优先级是不一样的。
 *  cfq
    
    操作系统为每一个进程创建一个IO队列，CFQ为每个进程分配IO请求的轮询时间片，当进程获得IO时间片后，就可以读取磁盘扇区数据，当时间片用完之后，CFQ再给其他进程分配时间片

[image-20210829143537835.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829143537835.png
[image-20210829143608841.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829143608841.png
[image-20210829144457948.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829144457948.png
[image-20210829161140176.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829161140176.png
[image-20210829161605133.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829161605133.png
[image-20210829162751070.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829162751070.png
[image-20210829164506561.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829164506561.png
[image-20210829170107989.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829170107989.png
[image-20210829171929846.png]: https://raw.githubusercontent.com/sermonlizhi/picture/main/image-20210829171929846.png