网站首页制作网站,wordpress开发 文档,减肥单页网站,做网站网页挣钱不【README】
1.本文内容总结自 B站 《操作系统-哈工大李治军老师》#xff0c;内容非常棒#xff0c;墙裂推荐#xff1b;
2.磁盘操作抽象
第1层抽象#xff1a;通过盘块号读写磁盘#xff08;或逻辑盘块号#xff09;#xff1b;第2层抽象#xff1a;用队列缓存多个…【README】
1.本文内容总结自 B站 《操作系统-哈工大李治军老师》内容非常棒墙裂推荐
2.磁盘操作抽象
第1层抽象通过盘块号读写磁盘或逻辑盘块号第2层抽象用队列缓存多个进程读写的盘块号第3层抽象文件或通过文件操作磁盘参见第25讲内容
3.盘块号调度算法
先来先服务- FCFS最短寻道优先-SSTF扫描调度-SCAN 电梯调度-C-SCAN推荐性能最优【1】磁盘工作原理
【1.1】 磁盘结构 【图解】
1磁盘由叠起来的盘片组成1个盘片的2个面都有磁材料都可以存储信息21个盘面划分为多个圆环每个圆环叫做磁道3每个磁道划分为多个扇区每个扇区固定512字节扇区是读写磁盘的基本单位4磁头每当有磁盘读写请求时在磁盘控制器下磁头就会移动去寻找磁道磁道再自身旋转进而定位到扇区【1.2】磁盘读写过程 【图解】
步骤1磁盘控制器控制磁头移动找到正确磁道 步骤2磁道自身旋转使得对应扇区旋转到磁头下方便磁头读写步骤3磁头把当前扇区的数据读入到内存缓冲区磁信号转为电信号步骤4程序把内存缓冲区中的某字节送入cpucpu修改字节内容并把数据返还到内存缓冲区步骤5把内存缓冲区中数据写出到磁盘同读磁盘相同写磁盘也需要磁头移动磁道自身旋转到对应扇区最后写操作电信号产生磁信号
小结
磁盘IO过程 磁盘控制器 - 磁头寻道 - 磁道旋转 - 传输读写操作【1.3】 使用磁盘
1根据上述内容我们知道磁盘工作原理即磁头移动找到对应磁道磁道自身旋转把对应扇区旋转到磁头下 补充
不同盘片且具有相同投影的圆环组成1个磁柱即不同盘片上的多个磁道组成1个磁柱所以cpu只需要把 磁柱号磁头号扇区号可以算出磁道号映射的内存地址连续读写的扇区数 等多个参数 送入磁盘控制器然后使用 DMA控制器 盗用总线把磁盘数据读入内存
2用out 指令 把上述4个参数送入磁盘控制器 【图解】 1符号表示 磁柱号 Cyl cylinder 磁头号 head 扇区号 Sect sector 内存地址
上述把多个参数直接送入磁盘控制器编码复杂太麻烦所以进行了如下抽象 【2】磁盘操作抽象
第1层抽象通过盘块号读写磁盘第2层抽象用队列缓存多进程读写的盘块号
【2.1】第一层抽象通过盘块号读写磁盘 图1 【图解】
1程序给出盘块号 block 送入磁盘驱动程序2磁盘驱动根据给定的盘块号block和磁盘参数计算出 磁柱 cyl 磁头号 head扇区号sec 等参数并送入磁盘控制器CHS参数3磁盘控制器操作 磁头盘面等进行工作
问题
如何把block 计算出 磁柱号磁头号扇区号即一维地址 推导出3维地址扇区号如何编址 为什么这样编址
设计思想
考虑到程序执行的局部性原理给定的block号相邻的盘块可以快速读出
1磁盘访问时间
磁盘访问时间 写入控制器时间 寻道时间 旋转时间 传输时间 时间类型 描述 耗时 写入控制器时间 磁盘驱动根据block推导出 磁柱号磁头号扇区号等参数并把上述参数送入控制器 寻道时间 磁头移动寻找到磁柱上的对应磁道 或移动磁臂时间 12ms 到 8ms 最耗时机械运动直线移动 旋转时间 磁道自己旋转使得对应扇区在磁头下 半周4ms 传输时间 磁头读写时间磁信号产生电信号或电信号产生磁信号 50M/秒约 0.3ms 小结
可以看到耗时最长的阶段是寻道时间所以在访存时我们应该减少寻道时间或减少寻道次数
2如何做到减少寻道时间或减少寻道次数
首先把相邻block的盘块放在同一个磁道上或相邻扇区上然后根据给定block盘块号把相邻盘块或相邻扇区一起读入到内存补充block是逻辑盘块号最终是要映射到物理磁盘扇区上的
3扇区编址 图2 【图解】综上根据以上分析我们对磁盘扇区就知道如何编址了。相邻扇区号是连续的 参见图1和图2。
若每个磁道7个扇区可以看到 0号扇区与7号扇区的投影是重合的如 0号扇区在盘片1的地址 0~512字节7号扇区在盘片2的地址0~512字节因为磁臂上的多个磁头每个盘片1个磁头是作为一个整体一起移动的即 盘片1的磁头移动到 0~512字节的扇区盘片2的磁头也移动到了 0~512字节的扇区......
4通过 CHS柱面号C磁头号H扇区偏移号S计算目标扇区号
目标扇区号 C*(heads*sectors) H *Sectors S 公式1其中 head 表示每个柱面的磁头数量sector 表示每个磁道的扇区数量
5每次读写的扇区数量增多读写速度会上升一定程度上 6每次读写1K 每次读写1M 区别如下表所示。 每次读写数据量 扇区数 读写速度 磁盘碎片 磁盘空间利用率 1K 2 100K/秒 0.5K 高 1M 2K 40M/秒 0.5M 低因为浪费多
目前磁盘容量可以做到很大完全可以用空间去换时间效率即把读写单位变大每次读写1M而不是1K7对应到读写扇区的高效方案是
每次读写多个相邻连续扇区这些扇区组成1个逻辑盘块而不是仅读写一个扇区
小结
操作系统把磁盘读写单位从扇区 转换为盘块提高了磁盘读写效率一个盘块是连续的几个扇区
【例】以盘块为单位读写磁盘重要
步骤1当操作系统收到 磁盘读写请求时首先把 盘块号 转为 多个连续扇区的扇区号步骤2磁盘驱动根据扇区号算出 CHS柱面号磁头号扇区号偏移并通过out指令把CHS值送入磁盘控制器步骤3磁盘控制器读写目标扇区号数据到内存缓冲区并返回给上层应用程序
综上应用程序可以通过盘块号来读写磁盘。 【图解】
Req-sector bh-b_blocknr 1 扇区号等于盘块号左移一位即乘以2 所以每个盘块会读写2个扇区数据Do_hd_request方法根据盘块号算出 公式1的变量如 CHS-柱面号磁头号扇区号偏移每个磁道的扇区数nsect每个柱面的磁头数量head等hd_out方法向磁盘控制器 发出out指令控制器根据参数读写目标扇区数据【2.2】第二层抽象用队列缓存多进程读写的盘块号
操作系统是多进程图像存在多个进程使用盘块号读写磁盘的情况。当有多个进程时需要使用缓冲队列存储不同进程的盘块号。 1盘块请求队列 【图解】 1请求队列用于存储不同进程访问磁盘的盘块号 2磁盘驱动什么时候从队列中取出盘块号
当磁盘驱动读写完上一个盘块号的数据就会发出磁盘中断则磁盘中断处理程序会从请求队列中取出下一个盘块号
3问题多个磁盘访问请求出现在请求队列怎么办
考虑用磁盘调度 。
4问题调度的目标是什么 调度时主要考察什么 ?
调度目标平均访问延迟小调度时考察寻道时间是主要矛盾
解决方法
在磁盘驱动中编写一个算法选择下一个要读取的盘块号使得磁盘工作速度快如 pptword都有读写盘块请求那如何让磁盘工作速度更快而磁盘读写最耗时的是寻道时间即如何最小化寻道时间
补充
生磁盘根据盘块号使用磁盘熟磁盘根据文件使用磁盘【3】磁盘调度算法如何选择盘块
【3.1】FCFS -磁盘调度算法
1FCFS 先来先服务即盘块调度顺序与盘块在队列的顺序一致 【图解】 1请求队列 请求队列 [ 98, 183, 37, 122, 14, 124, 65, 67 ] 队列里存储的是盘块号也可以理解为磁道号因为盘块号会被磁盘驱动计算出 磁头号柱面号扇区号偏移 。 2根据 FCFS 先来先服务的盘块调度算法盘块调度顺序与队列顺序一致。 磁头移动路径如上图折线所示总结如下磁头起始位置在53可以理解为在第53号磁道 调度盘块 98 183 37 122 14 124 65 67 移动磁道数量 45 85 146 85 108 110 59 2
小结磁头总共移动了 640 个磁道。 【3.2】 SSTF-最短寻道优先
1SSTF Shortest seek time first 最短寻道优先
选择与当前磁道距离最短的磁道进行访问【图解】 根据最短寻道优先算法选择与当前磁道距离最短的磁道访问请求显然盘块调度顺序与队列中的盘块顺序不一致。队列 [ 98, 183, 37, 122, 14, 124, 65, 67 ] 磁头移动路径如上图折线所示总结如下磁头起始位置在第53号磁道 调度盘块 65 67 37 14 98 122 124 183 移动磁道数量 12 2 30 23 84 24 2 59
小结磁头总共移动了 236个磁道。
2比较结果
显然 最短寻道优先算法 优于 先来先服务算法。
3最短寻道优先的问题
因为该算法是选择与当前磁道距离最短的磁道进行访问所以访问路径是在中间移动即磁头频繁在磁道中间位置而会造成 边缘磁道 长时间不访问的现象即 导致边缘磁道的饥饿问题。
所以需要对 最短寻道优先算法进行优化改进。 【3.3】SCAN-扫描调度算法
1SCAN扫描调度算法
SCAN算法是 SSTF最短寻道优先的变体是由 SSTF 中途不回折 的思想即 SCAN算法先是向某一边如左边移动直到边界移动同时访问盘块号然后在向另一边右边移动直到边界。【图解】 根据SCAN算法先向某一边移动直到边界然后向另一边移动直到边界。队列 [ 98, 183, 37, 122, 14, 124, 65, 67 ]。 则磁头移动路径如上图折线所示总结如下磁头起始位置在第53号磁道 调度盘块 37 14 65 67 98 122 124 183 移动磁道数量 16 23 51 2 31 24 2 59 总计磁头总共移动了 208个磁道。上图给出的是236原因在于它访问了 第0号磁道从第14号磁道到第0号磁道双向需要移动28个磁道 【3.4】C-SCAN-电梯调度算法
1C-SCAN现实生活中的电梯算法
SCAN算法是 SSTF的变体是由 SSTF 中途不回折 的思想
2步骤
步骤1C-SCAN算法中先是向某一边如左边移动直到边界移动的同时访问盘块号步骤2然后立即移动到另一边的边界如最右边183仅移动但不做任何盘块访问这是电梯调度算法与 SCAN算法的区别步骤3同步骤1类似以右边的边界为起点向左边移动并访问盘块号直到左边边界
补充同电梯类似电梯每次都会移动到到最高楼层接人并把人送达目的地直到最低楼层所以称电梯算法。 【图解】 根据SCAN算法队列 [ 98, 183, 37, 122, 14, 124, 65, 67 ] 则磁头移动路径如上图折线所示总结如下磁头起始位置在第53号磁道 调度盘块 37 14 183 124 122 98 67 65 移动磁道数量 16 23 169 59 2 24 31 2 总计磁头总共移动了326个磁道。但磁头从第14号移动到第183号磁道是非常快速的不做任何访问所以 326 - 169 157个磁道。 【小结】磁盘调度算法
盘块队列 [ 98, 183, 37, 122, 14, 124, 65, 67 ] 算法名称 移动磁道个数 性能 FCFS-先来先服务 640 SSTF-最短寻道优先 236 SCAN-扫描调度 208 C-SCAN-电梯调度 157 最优推荐 【4】多个进程共同使用磁盘 【图解】多个进程共同使用磁盘步骤重要*
步骤1多个进程在访问磁盘的时候多个进程要产生请求放入请求队列步骤2然后磁盘中断触发中断处理程序从队列中取出请求盘块号步骤3根据盘块号换算出CHS通过out指令发送给磁盘控制器以进行读写多个扇区
总结这就是使用生磁盘的完整故事
【代码】进程访问磁盘创建请求
// 进程访问磁盘创建请求
static void make_request
{...// 把盘块号换算为扇区号乘以2req-sector bh- b_blocknr 1;// 把盘块请求添加到队列中 add_request(major blk_dev, req);
}// add_request 把请求添加到队列
static void add_request(struct blk_dev struct *dev, struct request *req)
{cli(); // 关中断for(;temp-next; temp tmep-next) {if (( IN_ORDER(temp, req) || !IN_ORDER(temp, temp-next) ) IN_ORDER(req, temp-next)) break; }req-next temp-next; temp-next req; sti(); // 开中断
}// 补充 cli 与 sti 构建起临界区只允许一个进程进入。
// IN_ORDER 方法 判断 s1 小于 s2 (比较扇区号大小)
#define IN_ORDER(s1, s2)
{(( s1-dev s2-dev )|| (s1-dev s2-dev s1-sector s2-sector ))
}
【代码解说】
当 temp 小于req 且 req小于temp-next 或 temp 大于 temp-next 且 req小于temp-next 时循环退出【4.1】生磁盘的使用整理 【图解】 1进程得到盘块号 算出扇区号
如何得到盘块号 进程或程序是操作文件的那就是通过文件得到盘块号并根据盘块号算出扇区号因为一个盘块对应多个扇区所以可以看做是起始扇区号
2用扇区号 make req制作磁盘请求用电梯算法 add_request 选择下一个盘块号
用扇区号 make req制作一个磁盘扇区访问请求这个制作请求的代码包含了 内存缓冲区申请与管理的代码对真实磁盘读写性能提升非常大用电梯算法把该请求放入请求队列中
3进程sleep_on
用户进程把 磁盘访问请求 放入队列后就睡眠了磁盘具体的读写操作由硬件去完成 即进程间的相互协作
4磁盘中断处理
磁盘控制器执行完上一个请求后会发出中断中断处理程序会从请求队列中获取请求获取下一个盘块号
5do_hd_request 算出 柱面号磁头号扇区号
步骤1磁盘驱动根据 out 命令发出磁盘读写指令步骤2读写完成后或把数据读取到内存缓冲区会再次发出中断中断处理程序会调用 read_intr() 方法步骤3read_intr()方法会结束请求并唤醒进程步骤4进程被唤醒后就可以在内存缓冲区中读取想要的数据了进程就可以继续工作了从进程发出磁盘读写请求到被唤醒这段时间进程是阻塞或睡眠的显然读写磁盘的程序执行是比较慢的重要一点是磁盘寻道耗时长
6hd_out 调用 outp(...) 完成磁盘端口读写
小结到这里生磁盘的使用就完整介绍完了
我们把磁盘的使用抽象为盘块号然后再在此基础上抽象为 多进程共同使用磁盘的方式使得磁盘使用更加高效
补充如何得到盘块号
上文讲到通过文件来获取盘块号那通过文件如何来获取盘块号呢。所以引出了 生磁盘到文件 的内容参见第25章内容
