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