电梯算法又称

1. 电梯调度算法...

不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。

每天早上，那些差5分钟就迟到的程序员，在等电梯时，一般会做两件事：

前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。本文对“骂电梯”不给予任何指导性建议。

但说起电梯调度算法，我觉得还是可以给大家科普一下，好为大家在等电梯之余，打发时间而做出一点贡献。

（电梯调度算法可以参考各种硬盘换道算法，下面内容整理自网络）

先来先服务（FCFS-First Come First Serve）算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。

它根据乘客请求乘坐电梯的先后次序进行调度。此算法的 优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况 。

这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。

人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：

最短寻找楼层时间优先（SSTF-Shortest Seek Time First）算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是 最短寻找楼层的时间。

这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大 ，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“ 饿死”现象 。

扫描算法（SCAN） 是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

它进行寻找楼层的优化，效率比较高，但它是一个 非实时算法 。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的。

所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成， 免去了电梯频繁的来回移动 。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小， 从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定 。

LOOK 算法是扫描算法（SCAN）的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。

但 当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向 ，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

SATF（Shortest Access Time First）算法与 SSTF 算法的思想类似，唯一的区别就是 SATF 算法将 SSTF 算法中的寻找楼层时间改成了访问时间。

这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进， 但是电梯的运行当中等待乘客上梯时间却不是人为可以控制 。

SATF 算法考虑到了电梯运行过程中乘客上梯时间的影响 。

最早截止期优先（EDF-Earliest Deadline First）调度算法是最简单的实时电梯调度算法，它的 缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。

它与 FCFS 调度算法类似，EDF 算法是电梯实时调度算法中最简单的调度算法。 它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。SCAN-EDF 算法先按照 EDF 算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照 SCAN 算法服务每一个请求。它的效率取决于有相同 deadline 的数目，因而效率是有限的。

PI（Priority Inversion）算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。

FD-SCAN（Feasible Deadline SCAN）算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次 SCAN 的方向。

并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。

这种算法忽略了用 SCAN 算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。

以上两结介绍了几种简单的电梯调度算法。

但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。

随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。

由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。

本人设置的电梯的初始状态，是对住宅楼的电梯的设置。

(1)建筑共有21层，其中含有地下一层（地下一层为停车场）。
(2)建筑内部设有两部电梯，编号分别为A梯、B梯。
(3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。
(4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。
(5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。
(6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。
(7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层。

每一架电梯都有一个编号，以方便监控与维修。每一架电梯都有一实时监控器，负责监控电梯上下，向电梯升降盒发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障，还应向相应的电梯负责人发送求救信号。

电梯内部的楼层按钮：

这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。

电梯内部开门按钮：

如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。

电梯内部关门按钮：

电梯外部向上按钮：

电梯外部向下按钮：

你肯能意识到 哪个算法都不是一个最佳方案，只是它确实解决了一定情况的问题 。但是对一个优秀的程序员而言，研究各种算法是无比快乐的。也许你下一次面试，就有关于调度算法的问题。

2. 磁盘调度算法

  上文介绍了磁盘的结构，本文介绍磁盘的调度算法相关的内容。
   本文内容

   寻找时间（寻道时间） 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算法，平均寻道时间更长。

3. 电梯调度和scan算法区别

电梯调度和scan算法没有区别。经查询相关资料信息配或得知，scan算法通常称为电梯调度算法，两者是早卖清陆前一样的，没有区别。

4. 习题精编上 磁盘寻到算法中的LOOK 和 C_LOOK 是啥意思啊

LOOK 和 C_LOOK 分别是回看的扫描和循环扫描，它与scan ,cscan不通之处是scan扫描是要回到磁道最外出或最里处才返回，而LOOK只需要到达要访问的磁道最外或最里处就会返回。比如磁道1—1000，分别要访问150,300,800道的内容，那如果现在在500磁道，向磁道小的方向访问的话，scan 算法会移到磁道1后再返回，LOOK算法移到磁道150或就会返回了了。同理 C_LOOK 与cscan的不同之处类似

5. 电梯算法是怎样的

电梯算法是通过操作系统学术名为SCAN算法。磁臂仅移动到请求的最外道就回转。反方向查找服务。

如果请求调度的磁道为98, 183, 37, 122, 14, 124, 65, 67，磁头从53号磁道开始移动，磁头就会按照65, 67, 98, 122, 124, 183, 37,14 的顺序依次查找，并将数据输入内存。

电梯（升降盒）上下来回地运动，电梯内部有一些按钮，每一个按钮代表一层楼，当按下按钮时，按钮的灯亮。

电梯沿某一方向运动，在将要到达某一层楼时，实时监控器 判断电梯内是否有乘客要在此层楼下电梯，若有，则发送信号给电梯升降架。

电梯是指服务于建筑物内若干特定的楼层，其轿厢运行在至少两列垂直于水平面或与铅垂线倾斜角小于15°的刚性轨道运动的永久运输设备。

也有台阶式，踏步板装在履带上连续运行，俗称自动扶梯或自动人行道。服务于规定楼层的固定式升降设备。垂直升降电梯具有一个轿厢，运行在至少两列垂直的或倾斜角小于15°的刚性导轨之间。

轿厢尺寸与结构形式便于乘客出入或装卸货物。习惯上不论其驱动方式如何，将电梯作为建筑物内垂直交通运输工具的总称。

6. 操作系统的主要算法都有哪些

一、进程(作业)调度算法
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）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。