磁盘调度电梯算法
① 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么
先来先服务算法：这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。
最短寻道时间优先算法：要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
扫描算法：“电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个磁道的访问者。
.循环扫描算法：防止饥饿现象
② 磁盘调度算法
上文介绍了磁盘的结构，本文介绍磁盘的调度算法相关的内容。
本文内容
寻找时间（寻道时间） T s ：在读/写数据前，需要将磁头移动到指定磁道所花费的时间。
寻道时间分两步：
则寻道时间 T s = s + m * n。
磁头移动到指定的磁道，但是不一定正好在所需要读/写的扇区，所以需要通过磁盘旋转使磁头定位到目标扇区。
延迟时间T R ：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则 平均所需延迟时间T R = (1/2)*(1/r) = 1/2r。
传输时间T R ：从磁盘读出或向磁盘中写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则传输时间 T R = (b/N) * (1/r) = b/(rN)。
总的平均时间 T a = T s + 1/2r + b/(rN) ，由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。
算法思想： 根据进程请求访问磁盘的先后顺序进行调度。
假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
按照先来先服务算法规则，按照请求到达的顺序，磁头需要一次移动到55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498个磁道。响应一个请求平均需要移动498 / 9 = 55.3个磁道（平均寻找长度）。
优点： 公平；如果请求访问的磁道比较集中的话，算法性能还算可以 。
缺点： 如果大量进程竞争使用磁盘，请求访问的磁道很分散，FCFS在性能上很差，寻道时间长 。
算法思想： 优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短 。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）。
假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
磁头总共移动了（100 -18）+ （184 -18） = 248个磁道。响应一个请求平均需要移动248 / 9 = 27.5个磁道（平均寻找长度）。
缺点： 可能产生饥饿现象 。
本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求又来了一个18号磁道访问请求。如果有源源不断的18号、38号磁道访问请求，那么150、160、184号磁道请求的访问就永远得不到满足，从而产生饥饿现象。这里产生饥饿的原因是 磁头在一小块区域来回移动。
SSTF算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。为了防止这个问题，可以规定： 磁头只有移动到请求最外侧磁道或最内侧磁道才可以反向移动，如果在磁头移动的方向上已经没有请求，就可以立即改变磁头移动，不必移动到最内/外侧的磁道。 这就是扫描算法的思想。由于磁头移动的方式很像电梯，因此也叫 电梯算法 。
假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了（184 - 100）+ （184 -18） = 250个磁道。响应一个请求平均需要移动 250 / 9 = 27.5个磁道（平均寻找长度）。
优点： 性能较好，寻道时间较短，不会产生饥饿现象。
缺点： SCAN算法对于各个位置磁道的响应频率不平均 。（假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等待低头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应184号磁道请求了。）
SCAN算法对各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而 返回时直接快速移动至最靠边缘的并且需要访问的磁道上而不处理任何请求。
通俗理解就是SCAN算在改变磁头方向时不处理磁盘访问请求而是直接移动到另一端最靠边的磁盘访问请求的磁道上。
假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了（184 -100）+ （184 - 18）+（90 - 18）=322个磁道。响应一个请求平均需要移动322 / 9 = 35.8个磁道（平均寻找长度）。
优点： 相比于SCAN算法，对于各个位置磁道响应频率很平均。
缺点： 相比于SCAN算法，平均寻道时间更长。
③ 1000分求解
cccccc ,LOOK（查找）调度（电梯）电梯算法。磁臂仅移雀简拍动到请求的最外道就回转。反方向查找服务。磁头从53号磁道开始移动，按照65, 67, 98, 122, 124, 183, 14, 37的顺序依次查找，并将数据输入内存。
电梯问题需求分析文档 （讨论稿）
1．电梯的基本需求功能
每一架电梯都有一个编号，以方便监控与维修。每一架电梯都有一实时监控器，负责监控电梯上下，向电梯升降盒咐山发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障，还应向相应的电梯负责人发送求救信号。
2．电梯按钮功能分析
电梯（升降盒）上下来回地运动，电梯内部有一些按钮，每一个按钮代表一层楼，当按下按钮时，按钮的灯亮。电梯沿某一方向运动，在将要到达某一层楼时，实时监控器判断电梯内是否有乘客要在此层楼下电梯，若有，则发送信号给电梯升降架，让其减速，同时让电梯在此层楼的电梯入口处平稳地停下，电梯停下后，实时监控器让电梯内相应的按钮灯灭，让乘客出电梯，然后关闭电梯门，而且继续朝原方向运动，直至到达当前运动方向上，有乘客要求到达的最后一层楼为止（即如：若该建筑物有50层，电梯当前正向上运动，若有乘客要求到达的最高楼层为30层，则电梯运动到30层之后，若30层以上没有乘客发出请求，则电梯可根据电梯内是否“有人”而向下运动或停止）。
除底层和顶层只有一个按钮外，每个楼层有两个按钮，分别指示上楼和下楼请求，当按下后，按钮灯亮，并向实时监控器发送请求，实时监控程序负责判断乘客的上下楼请求是否与电梯的当前运动方向一致，若不一致，则暂顷羡不受理此请求，此时按钮灯继续亮；若一致，则实时监控器将相应的上下请求按钮灯熄灭，并让电梯平稳地停在此层楼的电梯入口处，让相应的乘客入电梯，而后继续朝原方向运动。若同时有两层或两层以上的楼发出请求，产生了冲突，则实时监控器调用冲突处理器进行抉择，受理其中的一个请求，并负责将各请求上下楼的按钮灯熄灭。
3．当电梯发生异常现象时的功能需求
若电梯发生故障时，则实时监控器立即将电梯置为“不可用”状态，并且忽略任何请求，同时向相应的电梯管理人员发送求救信号。待电梯修复后管理员可将电梯置为“工作”状态，然后恢复正常工作。磁头初始位于0磁道，磁盘请求以16、29、19、12、55、6、69柱面的次序到达磁盘驱动器
FCFS先来先服务：（顺序访问）
0——16——29——19——12——55——6——69
SSTF最短寻道时间优先(在把磁头移到远处为另外的请求服务之前，应先把接近于磁头当前位置的所有请求都服务完。SSTF选择的请求距当前磁头所在位置有最短的寻道时间)：
0——6——12——16——19——29——55——69
电梯算法(需要一个方向，因为初始位于0道，则肯定是从低位到高位的。磁头从初始处出发，向一端移动，遇到所需的磁道是就进行服务，直至到达最远的请求磁道上，如果当前方向上没有请求就会反过来继续服务)：
0——6——12——16——19——29——55——69
因为初始时位于0道，所以电梯算法和最短寻道算法一样，如果是从中间开始就会不同的。
我们上学期刚学过，如果你还有不懂得地方可以给我留言。
希望可以帮到你，呵呵
④ 若磁头的当前位置100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为:
磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。为了尽快的响应进程的磁盘请求，人们设计了磁盘调度算法。主要有四种磁盘调度算法。先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）。
运用最短寻道优先算法依次悄哗贺选择的磁道是：90、80、125、140、160、190、启派30、29、25、20、10。
运用电梯调度算法依次经过的磁道是：90、80、30、29、25、20、10、125、140、160、190。
我们根据算法的寻道序列可以得出：最短寻道优先算法的经过的煮面数为310个柱面，电梯调度算法经过的柱面数为270次。
(4)磁盘调度电梯算法扩展阅读：
每种磁盘调度算法的优缺点
先来先服务算法的优点会根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，芦铅且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
最短寻道优先算法的缺点每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期地被延迟，有些请求的响应时间将不可预期。
扫描算法的优缺点此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。
循环扫描算法的优点是这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。
参考资料来源：网络-磁盘调度算法
⑤ 操作系统的主要算法都有哪些
一、进程(作业)调度算法
l 先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。
l 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。
l 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。
l 优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。
l 响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。
l 多级队列调度算法
基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间
二、存储器连续分配方式中分区分配算法
n 首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。
n 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。
n 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。
三、页面置换算法
l 最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。
l 先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。
l 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。
l 最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。
四、磁盘调度
n 先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置
n 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题
n 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
n 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。