Linux教程
操作系统磁盘的结构&磁盘的调度算法
本文主要是介绍操作系统磁盘的结构&磁盘的调度算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、磁盘的结构
(一)磁盘、磁道、扇区的概念
磁盘的表面由一些磁性物质组成,可以用这些磁性物质来记录二进制数据。
(二)如何在磁盘中读/写数据
需要把“磁头”移动到想要读/写的扇区所在的磁道。
磁盘会转起来,让目标扇区从磁头下面划过,才能完成对扇区的读/写操作。
(三)盘面、柱面的概念
(四)磁盘的物理地址
可用
(柱面号,盘面号,扇区号)
来定位任意一个“磁盘块”。在“文件的物理结构”小节中,我们经常提到文件数据存放在外存中的几号块,这个块号就可以转换成(柱面号,盘面号,扇区号)的地址形式。
可根据该地址读取一个“块”
①、根据“柱面号”移动磁臂,让磁头指向指定柱面;
②、激活指定盘面对应的磁头;
③、磁盘旋转的过程中,指定的扇区会从磁头下面划过,这样就完成了对指定扇区的读/写。
(五)磁盘的分类
二、磁盘调度算法
(一)一次磁盘读/写操作需要的时间
1. 寻找时间
2. 延迟时间
延迟时间T
R
:通过旋转磁盘,使磁头定位到目标扇区所需要的时间。设磁盘转速为 r (单位:转/秒,或 转/分),则平均所需的延迟时间
T
R
= (1/2)*(1/r) = 1/2r
1/r 就是转一圈需要的时间。找到目标扇区平均需要转半圈,因此再乘以 1/2
硬盘的典型转速为5400 转/分,或 7200转/分
3. 传输时间
总的平均存取时间 T
a
= T
S
+ 1/2r + b/(rN)
延迟时间和传输时间都与磁盘转速相关,且为线性相关。而转速是硬件的固有属性,因此操作系统也无法优化延迟时间和传输时间。
但是操作系统的磁盘调度算法会直接影响寻道时间
(二)磁盘调度算法
1. 先来先服务算法(FCFS)
根据进程请求访问磁盘的先后顺序进行调度。
假设磁头的初始位置是100号磁道,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
按照 FCFS 的规则,按照请求到达的顺序,磁头需要依次移动到 55、58、39、18、90、160、150、38、184 号磁道
磁头总共移动了 45+3+19+21+72+70+10+112+146 = 498 个磁道
响应一个请求平均需要移动
498/9 = 55.3 个磁道(平均寻找长度)
优点:
公平
;如果请求访问的磁道比较集中的话,算法性能还算过的去
缺点:如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS在性能上很差,
寻道时间长
。
2. 最短寻找时间优先算法(SSTF)
SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短,但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想,只是选择眼前最优,但是总体未必最优)
假设磁头的初始位置是100号磁道,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
磁头总共移动了
(100-18) + (184-18) = 248 个磁道
响应一个请求平均需要移动
248/9 = 27.5 个磁道(平均寻找长度)
优点:
性能较好,平均寻道时间短
缺点:
可能产生“饥饿”现象
Eg:本例中,如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求,处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的 18号、38号磁道的访问请求到来的话,150、160、184 号磁道的访问请求就永远得不到满足,从而产生“饥饿”现象。
产生饥饿的原因在于:磁头在一个小区域内来回来去地移动
3. 扫描算法(SCAN)
SSTF 算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。为了防止这个问题,可以规定,
只有磁头移动到最外侧磁道的时候才能往内移动,移动到最内侧磁道的时候才能往外移动
。这就是
扫描算法(SCAN)
的思想。由于磁头移动的方式很像电梯,因此也叫电梯算法。
假设某磁盘的磁道为 0~200号,磁头的初始位置是100号磁道,且
此时磁头正在往磁道号增大的方向移动
,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道.
磁头总共移动了
(200-100) + (200-18) = 282 个磁道
响应一个请求平均需要移动
282/9 = 31.3 个磁道(平均寻找长度)
优点:
性能较好,平均寻道时间较短,不会产生饥饿现象
缺点:
①、只有到达最边上的磁道时才能改变磁头移动方向,事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
②、SCAN算法对于各个位置磁道的响应频率不平均
(如:假设此时磁头正在往右移动,且刚处理过90号磁道,那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后,很快又可以再次响应 184 号磁道的请求了)
(1)LOOK调度算法
扫描算法(SCAN)
中,只有到达最边上的磁道时才能改变磁头移动方向,事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
LOOK 调度算法
就是为了解决这个问题,
如果在磁头移动方向上已经没有别的请求,就可以立即改变磁头移动方向
。(边移动边观察,因此叫 LOOK)
假设某磁盘的磁道为 0~200号,磁头的初始位置是100号磁道,且
此时磁头正在往磁道号增大的方向移动
,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道.
磁头总共移动了
(184-100) + (184-18) = 250 个磁道
响应一个请求平均需要移动
250/9 = 27.5 个磁道(平均寻找长度)
优点:比起 SCAN 算法来,
不需要每次都移动到最外侧或最内侧才改变磁头方向,使寻道时间进一步缩短
4. 循环扫描算法(C-SCAN)
SCAN算法对于各个位置磁道的响应频率不平均,而
C-SCAN 算法
就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求,而
返回时直接快速移动至起始端而不处理任何请求。
假设某磁盘的磁道为 0~200号,磁头的初始位置是100号磁道,且
此时磁头正在往磁道号增大的方向移动
,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
磁头总共移动了
(200-100) + (200-0) + (90-0)= 390 个磁道
响应一个请求平均需要移动
390/9 = 43.3 个磁道(平均寻找长度)
优点:比起SCAN 来,
对于各个位置磁道的响应频率很平均。
缺点:
只有到达最边上的磁道时才能改变磁头移动方向
,事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了;并且,磁头返回时其实只需要返回到18号磁道即可,不需要返回到最边缘的磁道。另外,
比起SCAN算法来,平均寻道时间更长。
(1)C-LOOK 调度算法
C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向,并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。
如果磁头移动的方向上已经没有磁道访问请求了,就可以立即让磁头返回,并且磁头只需要返回到有磁道访问请求的位置可
。
假设某磁盘的磁道为 0~200号,磁头的初始位置是100号磁道,且
此时磁头正在往磁道号增大的方向移动
,有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
磁头总共移动了
(184-100) + (184-18) + (90-18)= 322 个磁道
响应一个请求平均需要移动
322/9 = 35.8 个磁道(平均寻找长度)
优点:比起 C-SCAN 算法来,
不需要每次都移动到最外侧或最内侧才改变磁头方向,使寻道时间进一步缩短
这篇关于操作系统磁盘的结构&磁盘的调度算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
您可能喜欢
Linux部署Scrapy学习:入门级指南
09-11
Linux部署Scrapy:入门级指南
09-11
【Linux】分区向左扩容的方法
08-21
【Linux】gnome桌面环境切换KDE Plasma
08-21
如何安装 VMware Tools (macOS, Linux, Windows)
08-19
Linux部署Scrapy教程:入门级指南
08-15
linux命令行下好用的性能监控工具atop
07-29
Linux系统上离线升级SSH服务的具体操作步骤-icode9专业技术文章分享
07-04
00-macOS和Linux安装和管理多个Python版本
06-06
[译]漫画SELinux概念
03-30
linux 移动文件
03-29
linux .so file
03-28
Linux 磁盘管理
03-28
Linux学习笔记(十三)磁盘管理(一):磁盘分区
03-28
linux 创建 文件
03-26
栏目导航
前端开发
HTML5教程
CSS教程
Javascript
jQuery教程
AJAX教程
Node.js教程
XML教程
正则表达式
后端开发
Go教程
C/C++教程
消息队列MQ
Net Core教程
Asp.net教程
Java教程
PHP教程
移动端开发
微信公众号开发
小程序开发
Swift教程
IOS教程
Kotlin教程
Android开发
数据库
Redis教程
MongoDB教程
PostgreSQL教程
Oracle教程
MariaDB教程
SqLite教程
MySql教程
SqlServer教程
服务器运维
Kubernetes
Docker容器
linux shell
Nginx教程
网站安全
PowerShell教程
Linux教程
人工智能
TensorFlow教程
Python教程
机器学习
人工智能学习
区块链
区块链技术
游戏开发
游戏编程
Unity3D教程
网站运营
网站策划
网站优化
建站知识
大数据/云计算
云计算
Hadoop教程
软件工程
软件/开发工具使用
Git教程
资讯