scan磁盘调度算法C语言链表,操作系统期末考点

scan磁盘调度算法C语⾔链表,操作系统期末考点操作系统期末考点1.进程调度算法2.银⾏家算法3.连续分配算法(划分空间)4.虚拟存储管理页⾯置换算法5.输⼊输出系统6.磁盘调度算法7.⽂件管理8.PV原语9.物理块地址转换下图CSDN博客链接内容1.进程调度算法进程调度算法先来先服务FCFS短作业优先SJF⾼响应⽐优先HRN时间⽚轮转RR

scan磁盘调度算法C语⾔链表,操作系统期末考点操作系统期末考点1.进程调度算法2.银⾏家算法3.连续分配算法(划分空间)4.虚拟存储管理页⾯置换算法5.输⼊输出系统6.磁盘调度算法7.⽂件管理8.PV原语9.物理块地址转换下图CSDN博客链接内容1.进程调度算法进程调度算法先来先服务FCFS短作业优先SJF⾼响应⽐优先HRN时间⽚轮转RRHRRN⾼响应⽐优先调度算法(HRRN)⾼响应⽐优先调度算法则是既考虑了作业等待的时间，⼜考虑了作业运⾏时间的调度算法，因此既照顾了短作业，⼜不致使长作业的等待时间过长，从⽽改善了处理机的调度能⼒。R1=1+等待/服务=1+(开始-到达)/服务算法实现优先权的变化规律：优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间由上式可以看出：1.如果等待时间相同，则要求服务的时间越短，其优先权越⾼，类似短作业。2.要求服务时间相同时，作业的优先权⼜取决于等待时间，类似先来先服务。3。对于长作业的优先权，可以随等待时间的增加⽽提⾼，当其等待时间⾜够长时，也能获得处理机。例题：

HRRN⾼响应⽐优先调度算法(HRRN)⾼响应⽐优先调度算法则是既考虑了作业等待的时间，⼜考虑了作业运⾏时间的调度算法，因此既照顾了短作业，⼜不致使长作业的等待时间过长，从⽽改善了处理机的调度能⼒。R1=1+等待/服务=1+(开始-到达)/服务算法实现优先权的变化规律：优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间由上式可以看出：1.如果等待时间相同，则要求服务的时间越短，其优先权越⾼，类似短作业。2.要求服务时间相同时，作业的优先权⼜取决于等待时间，类似先来先服务。3。对于长作业的优先权，可以随等待时间的增加⽽提⾼，当其等待时间⾜够长时，也能获得处理机。例题：注意：对于⾼响应⽐优先算法(⾮抢占)，第⼀个先到进程直接运⾏到结束，余下进程每次都要计算响应⽐，⽐较后响应⽐最⼤的那个进程先运⾏，依次到进程全部运⾏完成。时间⽚轮转:Q＝1各时间点就绪队列1.A2.BA

注意：对于⾼响应⽐优先算法(⾮抢占)，第⼀个先到进程直接运⾏到结束，余下进程每次都要计算响应⽐，⽐较后响应⽐最⼤的那个进程先运⾏，依次到进程全部运⾏完成。时间⽚轮转:Q＝1各时间点就绪队列1.A2.BA3.ACB4.CBDA5.BDAEC6.DAECB7.AECBD8.ECBDA9.CBDAE10.BDAECB完成11.DAECD完成12.AECA完成13.EC14.CE15.EC16.CE17.ECE完成18.CC完成2.银⾏家算法1.银⾏家算法2.安全性算法掌握例题3.连续分配算法(划分空间)连续分配算法1⾸次适应FF2循环⾸次适应3最佳适应BF4最坏适应WF例：给定主存空闲区，按照地址从⼩到⼤排列位：100KB，500KB，200KB，300KB，600KB。现有⽤户进程依次为212KB，417KB，112KB，426KB。(1)分别⽤⾸次适应算法，最佳适应算法和最坏适应算法将他们装⼊主存的哪个分区？(2)哪个算法能最有效的利⽤主存？解：按题意地址从⼩到⼤进⾏分区如图所⽰。

3.ACB4.CBDA5.BDAEC6.DAECB7.AECBD8.ECBDA9.CBDAE10.BDAECB完成11.DAECD完成12.AECA完成13.EC14.CE15.EC16.CE17.ECE完成18.CC完成2.银⾏家算法1.银⾏家算法2.安全性算法掌握例题3.连续分配算法(划分空间)连续分配算法1⾸次适应FF2循环⾸次适应3最佳适应BF4最坏适应WF例：给定主存空闲区，按照地址从⼩到⼤排列位：100KB，500KB，200KB，300KB，600KB。现有⽤户进程依次为212KB，417KB，112KB，426KB。(1)分别⽤⾸次适应算法，最佳适应算法和最坏适应算法将他们装⼊主存的哪个分区？(2)哪个算法能最有效的利⽤主存？解：按题意地址从⼩到⼤进⾏分区如图所⽰。(1)1⾸次适应算法212KB选中分区2，这时分区2还剩288KB。417KB选中分区5，这时分区5还剩183KB。112KB选中分区2，这时分区2还剩176KB。426KB⽆分区能满⾜，应该等待。(2分)2最佳适应算法212KB选中分区4，这时分区4还剩88KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。(2分)3最坏适应算法212KB选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB⽆分区能满⾜，应该等待。(2分)(2)对于该作业队列，最佳适应算法能最有效利⽤主存。4.虚拟存储管理页⾯置换算法虚拟存储管理页⾯置换算法1最佳置换算法OPT2先进先出算法FIFO(队列思想)3最近最久未使⽤LRU(栈的思想)好的页⾯置换算法，应具有较低的页⾯更换频率最佳置换算法：保证获得最低的缺页率。7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1先进先出置换算法：淘汰最先进⼊内存的页⾯7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

(1)1⾸次适应算法212KB选中分区2，这时分区2还剩288KB。417KB选中分区5，这时分区5还剩183KB。112KB选中分区2，这时分区2还剩176KB。426KB⽆分区能满⾜，应该等待。(2分)2最佳适应算法212KB选中分区4，这时分区4还剩88KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。(2分)3最坏适应算法212KB选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB⽆分区能满⾜，应该等待。(2分)(2)对于该作业队列，最佳适应算法能最有效利⽤主存。4.虚拟存储管理页⾯置换算法虚拟存储管理页⾯置换算法1最佳置换算法OPT2先进先出算法FIFO(队列思想)3最近最久未使⽤LRU(栈的思想)好的页⾯置换算法，应具有较低的页⾯更换频率最佳置换算法：保证获得最低的缺页率。7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1先进先出置换算法：淘汰最先进⼊内存的页⾯7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1LRU(最近最久未使⽤)置换算法：选择最后⼀次访问时间距离当前时间最长的⼀页并淘汰之。计算缺页中断次数＋页⾯置换次数＋缺页率(由于运⾏进程太多，⽆法满⾜要求，频繁换进换出产⽣抖动现象)5.输⼊输出系统引⼊硬件引⼊软件控制器，通道，中断驱动程序6.磁盘调度算法磁盘调度算法1先来先服务FCFS(按照先后顺序访问)2最短寻道时间优先SSJF(要访问的与当前磁道最近)3扫描算法SCAN(电梯调度算法)4循环扫描算法CSCAN(当前⼀直移动到最⼤然后直接跳到最⼩的)

LRU(最近最久未使⽤)置换算法：选择最后⼀次访问时间距离当前时间最长的⼀页并淘汰之。计算缺页中断次数＋页⾯置换次数＋缺页率(由于运⾏进程太多，⽆法满⾜要求，频繁换进换出产⽣抖动现象)5.输⼊输出系统引⼊硬件引⼊软件控制器，通道，中断驱动程序6.磁盘调度算法磁盘调度算法1先来先服务FCFS(按照先后顺序访问)2最短寻道时间优先SSJF(要访问的与当前磁道最近)3扫描算法SCAN(电梯调度算法)4循环扫描算法CSCAN(当前⼀直移动到最⼤然后直接跳到最⼩的)例题：设某磁盘有200个柱⾯,编号为0,1,2,…,199,磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进⾏读写：86，147，91，177，94，150，102，175，130，试分别求FCFS，SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。答：FCFS算法的调度顺序与请求顺序⼀致。SSTF算法总是先完成距当前存取臂最近的柱⾯上的输⼊输出请求。SCAN算法是存取臂从磁盘的⼀端出发,向另⼀端移动,遇到需要访问的柱⾯就完成访问请求,直⾄到达磁盘的另⼀端。到达磁盘的另⼀端后,存取臂的移动⽅向就倒转过来,继续完成这⼀⽅向的访问请求。(1分)磁道号(排序后)177175150147143

例题：设某磁盘有200个柱⾯,编号为0,1,2,…,199,磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进⾏读写：86，147，91，177，94，150，102，175，130，试分别求FCFS，SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。答：FCFS算法的调度顺序与请求顺序⼀致。SSTF算法总是先完成距当前存取臂最近的柱⾯上的输⼊输出请求。SCAN算法是存取臂从磁盘的⼀端出发,向另⼀端移动,遇到需要访问的柱⾯就完成访问请求,直⾄到达磁盘的另⼀端。到达磁盘的另⼀端后,存取臂的移动⽅向就倒转过来,继续完成这⼀⽅向的访问请求。(1分)磁道号(排序后)177175150147143开始130102949186(1)采⽤FCFS算法调度时,磁头移动顺序为:143→86→147→91→177→94→150→102→175→130(1分)磁头移动总距离为:(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565(1分)(2)采⽤Sstf算法调度时,磁头移动顺序为143→147→150→130→102→94→91→86→175→177(2分)磁头移动总距离是162(柱⾯)(1分)(3)采⽤SCAN(电梯)算法调度时,磁头移动顺序为:143→147→150→175→177→130→102→94→91→86(2分)磁头移动总距离是125(柱⾯)。(1分)(4)采⽤NSCAN(循环扫描)算法调度，磁头移动顺序为：143→147→150→175→177→86→91→94→102→130磁头移动总距离是169(柱⾯)。7.⽂件管理逻辑结构/物理结构索引索引顺序连续链接描述当前磁盘中物理块的使⽤情况空闲表空闲链表空闲分区位⽰图8.PV原语9.物理块地址转换(1)程序空间的⼤⼩为32KB，32kb=２５X２10=215因此逻辑地址的有效位数是15位。(2)内存空间的⼤⼩是16KB，16kb=２4X２10=214因此物理地址⾄少需要14位。

开始130102949186(1)采⽤FCFS算法调度时,磁头移动顺序为:143→86→147→91→177→94→150→102→175→130(1分)磁头移动总距离为:(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565(1分)(2)采⽤Sstf算法调度时,磁头移动顺序为143→147→150→130→102→94→91→86→175→177(2分)磁头移动总距离是162(柱⾯)(1分)(3)采⽤SCAN(电梯)算法调度时,磁头移动顺序为:143→147→150→175→177→130→102→94→91→86(2分)磁头移动总距离是125(柱⾯)。(1分)(4)采⽤NSCAN(循环扫描)算法调度，磁头移动顺序为：143→147→150→175→177→86→91→94→102→130磁头移动总距离是169(柱⾯)。7.⽂件管理逻辑结构/物理结构索引索引顺序连续链接描述当前磁盘中物理块的使⽤情况空闲表空闲链表空闲分区位⽰图8.PV原语9.物理块地址转换(1)程序空间的⼤⼩为32KB，32kb=２５X２10=215因此逻辑地址的有效位数是15位。(2)内存空间的⼤⼩是16KB，16kb=２4X２10=214因此物理地址⾄少需要14位。1.⼗六进制表⽰逻辑地址：已知：⽤户编程空间共３２个页⾯，２５＝３２得知页号部分占５位，由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，２^４＝１６得知块号占4位。(1)⼀般情况页⾯⼤⼩占10位即2^10=1K，2~6位表⽰页号，后10位表⽰偏移量如下图(2)若说明页⾯⼤⼩占11位即2^11，1~5位表