(学习笔记-调度算法)磁盘调度算法

news/2025/2/18 11:32:32/

磁盘结构:

 常见的机械磁盘是上图左边的样子,中间圆的部分是磁盘的盘片,一般会有多个盘片,每个盘面都有自己的磁头。右边的图就是一个盘片的结构,盘片中的每一层分为多个磁道,每个磁道分为多个扇区,每个扇区是 512 字节。那么,多个具有相同编号的磁道形成了一个圆柱,称之为磁盘的柱面,如上图中间的样子。

磁盘调度算法的目的很简单,就是为了提高磁盘的访问性能,一般是通过优化磁盘的访问请求顺序来做到的。

寻道的时间是磁盘访问最耗时的部分,如果请求顺序优化的得当,必然可以节省一些不必要的寻道时间,从而提高磁盘的访问性能。

假设有下面一个请求序列,每个数字代表磁道的位置:

98,183,37,122,14,124,65,67

初始磁头当前的位置是在第 53 磁道。

接下来,分别对以上的序列,作为每个调度算法的例子,那常见的磁盘调度算法有:

  • 先来先服务算法
  • 最短寻道时间优先算法
  • 扫描算法
  • 循环扫描算法
  • LOOK 与 C-LOOK 算法

先来先服务

先来先服务(FCFS),先到来的请求,先被服务

按照这个序列的话:

98,183,37,122,14,124,65,67

那么,磁盘的写入顺序是从左到右,如下图:

 先来先服务算法总共移动了 640 个 磁道的距离,这么一看这种算法比较简单粗暴,但是如果大量进程竞争使用磁盘,请求访问的磁道可能会很分散,那先来先服务算法在性能上就会显得很差,因为寻道时间过长。


最短寻道时间优先

最短寻道时间优先(SSF)算法的工作方式是,优先选择从当前磁头位置所需寻道时间最短的请求,还是以这个序列为例子:

98,183,37,122,14,124,65,67

那么,根据距离磁头(53)最近的请求的算法,具体的请求则会是下列从左到右的顺序:

65,67,37,14,98,122,124,183

 磁头移动的总距离是 236 磁道,相比先来先服务性能提高了不少。

但这个算法可能存在某些请求的饥饿,因为本例子我们是静态的序列,看不出问题,假设是一个动态的请求,如果后续来的请求都是小于 183 磁道的,那么 183 磁道可能永远不会被响应,于是就产生了饥饿现象,这里产生饥饿的原因是磁头在一小块区域来回移动


扫描算法

最短寻道时间优先算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回移动。

为了防止这个问题,可以规定:磁头在一个方向上移动,访问所有未完成的请求,直到磁头到达该方向上的最后的磁道,才调换方向,这就是扫描算法

这种算法也叫做电梯算法,比如电梯保持按一个方向移动,直到在那个方向上没有请求为止,然后改变方向。

还是以这个序列为例子,磁头的初始位置是 53:

98,183,37,122,14,124,65,67

那么,假设扫描算法先朝磁道号减少的方向移动,具体请求会是下列从左到右的顺序:

37,14,0,65,67,98,122,124,183

 磁头先响应左边的请求,直到达到最左端后,才开始反向移动,响应右边的请求。

扫描算法性能较好,不会产生饥饿现象,但是存在这样的问题,中间部分的磁道会比较占便宜,中间部分相比其他部分响应的频率会比较多,也就是说每个磁道的响应频率存在差异。


循环扫描算法

扫描孙发使得每个磁道的响应频率存在差异,那么要优化这个问题的话,可以总是按相同的方向进行扫描,使得每个磁道的响应频率基本一致。

循环扫描(CSCAN)规定:只有磁头朝某个特定方向移动时,才处理磁道访问请求,而返回时直接快速移动至最靠边的磁道,也就是复位磁头,这个过程很快,并且返回中途不处理任何请求,该算法的特点,就是磁道只响应一个方向上的请求

还是以这个序列为例子,磁头的初始位置是 53:

98,183,37,122,14,124,65,67

那么,假设循环扫描调度算先朝磁道增加的方向移动,具体请求会是下列从左到右的顺序:

65,67,98,122,124,183,1990,14,37

 磁头先响应了右边的请求,直到碰到了最右端的磁道 199 ,就立即回到磁盘的开始处,但这个返回的途中是不响应任何请求的,直到到达最开始的磁道后,才继续顺序响应右边的请求。

循环扫描算法相比于扫描算法,对于各个位置磁道响应频率相对比较平均。


LOOK 与 C-LOOK 算法

前面说的扫描算法和循环扫描算法,都是磁头移动到磁盘 [最始端或对末端] 才开始调换方向。

其实这可以优化,优化的思路就是 磁头在移动到 [最远的请求] 的位置,然后立即反向移动

那针对 SCAN 算法的优化叫 LOOK算法,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中会响应请求

而针对 C-SCAN 算法的优化则叫做 C-LOOK,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中不会响应请求


http://www.ppmy.cn/news/1066270.html

相关文章

C++ STL 标准模板库

C STL 标准模板库 标准容器 顺序容器 vector vector 向量容器 底层数据结构:动态开辟的数组,每次以原来空间大小的2倍进行扩容。采用allocator进行空间开辟和释放,对象创建和析构的分离。具体如C模板学习笔记中简要实现C中的vector。 增…

ethers.js5:与智能合约交互

创建可写Contract变量 声明可写的Contract变量的规则: const contract = new ethers.Contract(address, abi, signer) 其中address为合约地址,abi是合约的abi接口,signer是wallet对象。注意,这里你需要提供signer,而在声明可读合约时你只需要提供provider。 你也可以利…

【管理运筹学】第 6 章 | 运输问题(2,表上作业法 | 初始可行解的确定)

文章目录 引言二、表上作业法2.1 初始基可行解的确定2.1.1 最小元素法2.1.2 伏格尔法 写在最后 引言 承接前文,在对运输问题有了基本的了解后,我们开始深入学习表上作业的具体内容。 二、表上作业法 2.1 初始基可行解的确定 2.1.1 最小元素法 基本思…

信息化发展1

信息的定义 1 、信息论的奠基者香农认为: 信息是用来消除随机不定性的东西。 2 、信息的目的是用来“消除不确定的因素” 。信息是抽象于物质的映射集合。 3 、香农用概率来定量描述信息的公式如下: 信息的特征 客观性:信息是客观事物在人…

4、什么是NoSQL

4、什么是NoSQL NoSQL NoSQL Not Only SQL,就是不仅仅是SQL的意思 泛指非关系型数据库,随着web2.0的诞生!传统的关系型数据库很难对付web2.0时代,因为web2.0时代又很多数据大爆炸新生的产物比如视频、音乐、大数据产生的其他的数…

js 类、原型及class

js 一直允许定义类。ES6新增了相关语法(包括class关键字)让创建类更容易。新语法创建的类和老式的类原理相同。js 的类和基于原型的继承机制与Java等语言中的类和继承机制有着本质区别。 1 类和原型 类意味着一组对象从同一个原型对象继承属性。因此,原型对象是…

java-Optional 类详解

目录 前言 Optional的构造方法 Optional的相关方法介绍 isPresent用法: get用法: filter用法: orElse用法: orElseGet用法 orElseThrow用法 map用法 flatMap用法: 前言 Optional 类是java8的新特性&#xff0…

Java之BigDecimal系列--去掉小数末尾多余的0

原文网址:Java之BigDecimal系列--去掉小数末尾多余的0_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍Java去掉BigDecimal小数末尾多余的0的方法。 概述 BigDecimal提供了stripTrailingZeros()方法可以实现去掉小数末尾的 0。 调用了stripTrailingZeros()再调…