程序员等电梯时竟然想这事儿

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

第一,在心里骂电梯慢;

第二,在心里暗算着电梯调度如何优化;

今天就为大家科普一下电梯调度算法,为在等电梯之余,打发时间做出一点贡献。(电梯调度算法可以参考各种硬盘换道算法,下面内容整理自网络)

传统电梯调度算法

1.1 先来先服务算法(FCFS)

先来先服务(FCFS-First Come First Serve)算法,根据乘客请求乘坐电梯的先后次序进行调度。它不仅仅没有对寻找楼层进行优化,也没有实时性的特征,是一种最简单的电梯调度算法。

优点是公平、简单,且每个乘客的请求都能依次地得到处理,不会出现某一乘客的请求得不到满足的情况。这种方法在载荷较轻松的环境下,性能尚可接受,但是在载荷较大的情况下,性能就会严重下降,甚至恶化。

1.2 最短寻找楼层时间优先算法(SSTF)

最短寻找楼层时间优先(SSTF-Shortest Seek Time First)算法,它注重电梯寻找楼层的优化;这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

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

1.3 扫描算法(SCAN)

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

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

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

1.4 LOOK 算法

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

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

1.5 SATF 算法

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

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

实时电梯调度算法

2.1 最早截止期优先调度算法

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

它响应请求队列中时限最早的请求,是其它实时电梯调度算法性能衡量的基准和特例。

2.2 SCAN-EDF 算法

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。它的效率取决于有相同 deadline 的数目,因而效率是有限的。

2.3 PI 算法

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

2.4 FD-SCAN 算法

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

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

电梯问题的需求分析

4.1 电梯的初始状态

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

(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层。

4.2 电梯基本功能

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

4.3 电梯按钮功能

电梯内部的楼层按钮:电梯内部对应每一个楼层的按钮成为楼层按钮。

电梯内部开门按钮:乘客按下开门按钮,电梯门将打开,让用户离开。

电梯内部关门按钮:乘客需要按下关门按钮,让电梯门关闭,使电梯进入运行状态。设置电梯的自动关门时间为8秒。

电梯外部向上按钮:此按钮表示上楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层。

电梯外部向下按钮:此按钮表示下楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层。

原文发布于微信公众号 - GitChat精品课(CSDN_Tech)

原文发表时间:2018-08-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android 开发者

[译] 建立一个像科幻小说一样的虚拟世界:设计一个全球性的虚拟世界

49430
来自专栏数据派THU

教你用Python爬虫股票评论,简单分析股民用户情绪

来源:大数据挖掘DT数据分析 本文长度为1500字,建议阅读7分钟 本文为你分享如何爬取分析股民评论数据,预测用户情绪走势。 一、背景 股民是网络用户的一大群体...

1.2K70
来自专栏PaddlePaddle

PaddlePaddle最全学习资源一览(内附直达链接)

上手PaddlePaddle,随便一搜“PaddlePaddle课程” ,官方和培训机构搜索结果倒不少,这可如何选择?

16220
来自专栏大数据和云计算技术

Automatic Management of Data and Computation in Datacenters

image.png 最近在研究数据中心的数据管理和性能优化,看了一篇2010的论文Nectar:Automatic Management of Data and...

365100
来自专栏大数据挖掘DT机器学习

【案例】SPSS商业应用系列第1篇:预测分析模型提高超市销量

Statistics 和 Modeler作为 IBM SPSS 软件家族中重要的成员,是专业的科学统计、数据挖掘分析工具,其具有功能强大,应用广...

57850
来自专栏软件

Lumion4.0安装图解

链接:https://pan.baidu.com/s/1ge7PaYv 密码:ast4 lumion4.0.2是一款辅助Quest3D的工具,主要作用是实现3d...

19650
来自专栏维恩的派VNPIE

使用TA-Lib在vn.py上开发CTA交易策略

作为一套被业界广泛应用的开源技术分析库(包含技术指标计算和K线模式识别等),TA-Lib自2001年发布以来已经有了十多年的历史。TA-Lib中一共包含大约12...

30350
来自专栏小樱的经验随笔

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)爆零记

昨晚一个瓜皮说今晚有cf,听说是晚间场,我瞅了一眼,娃,VK Cup,上分的好机会,看着比赛时间就有点心酸了,0:35,当时一直在纠结要不要打的问题,当时想着应...

26040
来自专栏数据小魔方

R语言数据地图——美国地图

之前有过一段时间,特别热衷于数据地图,也分享很多篇关于地图制作的教程(涉及到各种作图软件),但大多是整理拼凑,自己发挥的不多。 最近在看哈德利.威科姆的那本火遍...

60950
来自专栏数据小魔方

shiny动态仪表盘应用——中国世界自然文化遗产可视化案例

这一篇很早就想写了,一直拖到现在都没写完。 虽然最近的社交网络上娱乐新闻热点特别多,想用来做可视化分析的素材简直多到不可想象,但是我个人一向不追星,对明星热文和...

64970

扫码关注云+社区

领取腾讯云代金券