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

news/2024/4/15 8:06:46

磁盘结构:

 常见的机械磁盘是上图左边的样子,中间圆的部分是磁盘的盘片,一般会有多个盘片,每个盘面都有自己的磁头。右边的图就是一个盘片的结构,盘片中的每一层分为多个磁道,每个磁道分为多个扇区,每个扇区是 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()再调…

【Flutter】Flutter 使用 toggle_switch 实现切换按钮

【Flutter】Flutter 使用 toggle_switch 实现切换按钮 文章目录 一、前言二、安装和基本使用三、Toggle Switch 的基础示例四、Toggle Switch 的高级用法五、实际业务中的完整示例六、总结 一、前言 你好,我是小雨青年,今天我要为大家介绍一个非常实用的…

【IEEE会议】2023年第三届IEEE数字化社会与智能系统国际学术会议(DSInS 2023)

2023年第三届IEEE数字化社会与智能系统国际学术会议(DSInS 2023) 2023 3rd International Conference on Digital Society and Intelligent Systems 由西南交通大学主办,悉尼科技大学、四川大学、中南大学社会计算研究中心、西南财经大学、武汉理工大学…

系统架构设计高级技能 · Web架构

现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 Web架构 一、Web架构介绍1.1 Web架构涉及技术1.2 单台服务…

python开发--文件敏感信息识别

0x00 背景 文档中敏感信息识别。不限于word, pdf 等文件格式中的敏感信息及其中的图片敏感信息识别。 0x01 识别原理 以word文档为例 .docx文件有很多种结构,这些结构在python-docx中用3种不同的类型来表示:最高一层是Document对象表示文档&#xff0…

Spring Boot中通过maven进行多环境配置

上文 java Spring Boot将不同配置拆分入不同文件管理 中 我们说到了,多环境的多文件区分管理 说到多环境 其实不止我们 Spring Boot有 很多的东西都有 那么 这就有一个问题 如果 spring 和 maven 都配置了环境 而且他们配的不一样 那么 会用谁的呢? 此…

KVM虚拟化平台安装及创建虚拟机

文章目录 一、KVM 简介二、安装KVM虚拟化平台1、方式一:安装操作系统时,添加虚拟化功能2、方式二:基于现有系统,安装虚拟化功能3、验证KVM安装是否无误 三、创建虚拟机1、创建虚拟机前环境准备工作2、创建CentOS7.5系统虚拟机 一、…

P1786 帮贡排序

题目背景 在 absi2011 的帮派里,死号偏多。现在 absi2011 和帮主等人联合决定,要清除一些死号,加进一些新号,同时还要鼓励帮贡多的人,对帮派进行一番休整。 题目描述 目前帮派内共最多有一位帮主,两位副…

Day 84:网络结构与参数

单层数据 package dl;/*** One layer, support all four layer types. The code mainly initializes, gets,* and sets variables. Essentially no algorithm is implemented.*/ public class CnnLayer {/*** The type of the layer.*/LayerTypeEnum type;/*** The number of …

华为OD七日集训第2期 - 按算法分类,由易到难,循序渐进,玩转OD(文末送书)

目录 一、适合人群二、本期训练时间三、如何参加四、7日集训第2期五、精心挑选21道高频100分经典题目,作为入门。第1天、逻辑分析第2天、字符串处理第3天、数据结构第4天、递归回溯第5天、二分查找第6天、深度优先搜索dfs算法第7天、动态规划 六、集训总结1、《代码…

【JAVA】String 类

⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈Java 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 String 1. 字符串构造2. String对象的比…

配置Flink

配置flink_1.17.0 1.Flink集群搭建1.1解压安装包1.2修改集群配置1.3分发安装目录1.4启动集群、访问Web UI 2.Standalone运行模式3.YARN运行模式4.K8S运行模式 1.Flink集群搭建 1.1解压安装包 链接: 下载Flink安装包 解压文件 [gpbhadoop102 software]$ tar -zxvf flink-1.1…

经过卷积神经网络之后的图片的尺寸如何计算

经过卷积神经网络(Convolutional Neural Network,CNN)处理后,图片的尺寸会发生变化,这是由于卷积层、池化层等操作引起的。计算图片经过卷积神经网络后的尺寸变化通常需要考虑卷积核大小、步幅(stride&…
最新文章