程序猿在等电梯时都在想什么?

作者 : 开心源码 本文共2386个字,预计阅读时间需要6分钟 发布时间: 2022-05-13 共135人阅读

等这么久了,电梯怎样还没来???肯定是电梯调度有问题!那就让我给它设计一个电梯调度算法。

电梯调度与操作系统中的磁盘调度是有联络的。我大概在三年前就想过电梯调度的问题,那时我刚搬入高层住宅,然而当时我的专业功底还不够扎实,也没有深入研究。直到现在我接触了操作系统中的磁盘调度算法,我才联想到了电梯调度算法。殊途同归,异曲同工,无非都是调度。在磁盘调度中,移动的是磁头指针(相对的说),而在电梯调度中,移动的是电梯。

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楼再回来接他,但是这样可以让钱大爷、张大爷、王大爷都相对满意。

在这样一种应用情景下,先来先服务算法和最短寻道时间优先算法都会让其中的一位大爷或者几位大爷强烈不满。

针对不同的应用场景,设计或者选择合适的算法,也是优秀程序员的优良品质之一。

用计算机科学领域的算法看待生活中的实际问题,也许就是计算思维的表现吧。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 程序猿在等电梯时都在想什么?

发表回复