等这么久了, 电梯怎么还没来??? 一定是电梯调度有问题! 那就让我给它设计一个电梯调度算法.
电梯调度与操作系统中的磁盘调度是有联系的. 我大概在三年前就想过电梯调度的问题, 那时我刚搬入高层住宅, 然而当时我的专业功底还不够扎实, 也没有深入研究. 直到现在我接触了操作系统中的磁盘调度算法, 我才联想到了电梯调度算法. 异曲同工, 殊途同归, 无非都是调度. 在磁盘调度中, 移动的是磁头指针(相对的说), 而在电梯调度中, 移动的是电梯.
timg.gif
那么电梯调度算法有哪些呢? 它们都适用于哪些情况呢?
先来先服务算法的简称是 FCFS, 是 First Come First Serve 的缩写. 顾名思义, 就是先来到电梯门前的 (或者说先按下电梯上下按钮的) 乘客先体验电梯的服务.
举个例子, 李大爷在 1 楼按下了向上的按钮, 在此之后张大爷在 15 楼按下了向下的按钮, 在此之后王大爷又在 8 楼按下了向下的按钮. 王大爷跟张大爷约好要一起去菜市场买菜.
那么此时, 无论电梯现在在几楼, 都会先去 1 楼接李大爷.
李大爷进入电梯后, 无论他要去几楼 (假设李大爷要去 20 楼), 到达目的地(20 楼) 之后, 电梯就会去 15 楼接张大爷.
张大爷在 15 楼上了电梯, 他要去菜市场买菜, 因此他要到 1 楼, 他进了电梯就按下了 1 楼的按钮.
于是电梯呼呼呼开始下行, 此时还在 8 楼的王大爷眼睁睁地看着电梯经过了 8 楼继续向下运行, 竟然无视了他!!!
张大爷顺利到达 1 楼, 此时电梯才向上来到 8 楼接王大爷, 王大爷这才坐电梯到 1 楼与张大爷会和.
这可把王大爷气坏了, 心里不是在骂物业傻 X, 就是在骂写电梯调度的程序员傻 X......
先来先服务算法的弊端在上面这个例子中显露无遗, 但是它也有优点呀, 优点就是简单, 程序员省事! 开玩笑的, 优点就是相对来说比较公平, 乘客得到电梯服务的顺序一定是先来后到的, 不会被人插队.
最短寻道时间优先算法的简称是 SSTF, 是 Shortest Seek Time First 的缩写, 顾名思义, 就是距离当前电梯位置最近的乘客, 会最先得到电梯服务.
大爷们是否能得到电梯的服务, 与电梯当前的位置有关.
还是举上面那个例子, 假如在大爷们来到电梯门口前电梯停在 1 楼. 李大爷起初在 1 楼, 无疑是距离电梯最近的, 他先上电梯. 李大爷来到 20 楼下了电梯. 电梯此时在 20 楼, 距离 20 楼最近的服务请求来自 15 楼的张大爷, 于是电梯呼呼呼下行来到 15 楼接上张大爷, 此时电梯在 15 楼, 距离 15 楼最近的服务请求来自 8 楼的王大爷, 这一次电梯没有无视王大爷, 接上了王大爷后, 王大爷和张大爷一起开开心心坐到 1 楼去菜市场买菜去了. 王大爷和张大爷一边说着物业费没白交, 一边夸着写电梯调度的小伙子技术高.
王大爷和张大爷开心了, 可把住在 30 楼的钱大爷气坏了. 原来在三位大爷按完按钮之后 (电梯刚接上 1 楼的李大爷) 就按了按钮, 可是钱大爷看着电梯上行到 15 楼就改下行了...... 电梯到达 15 楼时, 所有请求 (包含服务请求和目的地到达请求) 有这些: 张大爷请求到 1 楼, 8 楼的王大爷请求上电梯, 再就是 30 楼的钱大爷请求上电梯了. 钱大爷距离电梯还差着 15 层楼呢, 按照最短寻道时间优先算法电梯肯定要先去 8 楼接王大爷. 接完王大爷电梯肯定离着目的地 1 楼最近, 也不会上去接钱大爷.
按照这样想下去, 如果此时 3 楼的赵大妈想下楼买菜, 钱大爷还得眼睁睁看着电梯从 1 楼上行到 3 楼再改下行, 估计要是真这样钱大爷连搬家的想法都有了......
最短寻道时间优先算法的弊端在上面这个例子中暴露无遗, 那就是距离电梯较远的乘客, 可能永远不会得到服务(如果电梯附近的楼层一直有服务请求).
扫描算法的简称是 SCAN,SCAN 算法是电梯调度中使用最广泛的一种算法. SCAN 算法与当前电梯移动的方向有关(上行 / 下行), 当前移动方向上距离电梯最短的请求将最先得到服务. 电梯调度与操作系统磁盘调度不同的是, 磁盘调度仅仅是为了读写磁盘, 并没有目的地这一说, 而电梯调度是有目的地的. 乘客进入电梯后按的楼层, 就是目的地到达请求的楼层.
image
这就是为什么现代化的电梯门口都有两个按钮, 一个上行, 一个下行, 乘客按了上行按钮表示乘客想要上楼, 乘客按了下行按钮表示乘客想要下楼.
image
因此在 SCAN 算法中, 仅仅在电梯的移动方向上还不行, 目的地方向也要与电梯移动方向一致的乘客才有资格先上电梯. 这样在电梯向上行的时候, 就只处理向上的服务请求 (还有距离最远的向下的服务请求) 和向上的目的地到达请求, 等到上行方向上不再有任何请求(包括服务请求和目的地到达请求), 电梯再换向成下行.
下行也是如此, 在电梯向下的时候, 就只处理向下的服务请求 (还有距离最远的向上的服务请求) 和向下的目的地到达请求, 等到下行方向上不再有任何请求(包括服务请求和目的地到达请求), 电梯再换向成上行.
在最短寻道时间优先算法举的例子中, 问题得到了相对完美的解决. 电梯送李大爷到了 20 楼, 就立刻去 30 楼接钱大爷, 接到张大爷后电梯转为下行, 去 15 楼接了张大爷, 又去 8 楼接了王大爷. 李大爷, 张大爷, 王大爷, 钱大爷都很满意, 电梯的利用率也较高. 这一次, 程序员不再背锅.
磁盘调度与电梯调度有相同的地方, 也有不同的地方. 我不知道是先有的磁盘调度还是先有的电梯调度, 但我能肯定的是, 他们两者之间肯定存在着相互借鉴.
每一种算法都不能让所有人都满意, 比如在扫描算法中, 因为有钱大爷在 30 楼请求下楼, 8 楼的王大爷就要眼睁睁地看着电梯经过了 8 楼上行到 30 楼再回来接他, 15 楼的张大爷也是眼睁睁地看着电梯经过了 15 楼上行到 30 楼再回来接他, 但是这样可以让钱大爷, 张大爷, 王大爷都相对满意.
在这样一种应用情景下, 先来先服务算法和最短寻道时间优先算法都会让其中的一位大爷或几位大爷强烈不满.
针对不同的应用场景, 设计或选择合适的算法, 也是优秀程序员的优良品质之一.
用计算机科学领域的算法看待生活中的实际问题, 也许就是计算思维的体现吧.
来源: http://www.jianshu.com/p/a0ea45040a5c