当我们乘电梯的时候，我们在乘什么

Posted on Edited on Disqus:

背景

  • 对电梯调度发生兴趣的起源前公司在 2018 年对办公楼做过一次电梯系统改造，改造后的乘梯体验是：用户选择到达楼层，系统告知几号电梯被呼叫到。

电梯调度为什么复杂

先问是不是，再问为什么。操作系统原理的本科课程一般都会提到 I/O 调度问题，多个 I/O 请求可能同时到达但磁盘控制器同一时间只能执行一次 I/O 操作；不同 I/O 操作在磁盘上的远距离会导致磁盘臂的较大移动；
磁盘访问时间(Disk Access Time) = 寻址时间(Seek Time) + 旋转延迟(Rotational Latency) + 数据传输时间(Transfer Time)

I/O 调度就是为了降低磁盘访问的整体时间，其中的扫描算法(SCAN)也被叫做电梯算法(elevator algorithm)。磁盘臂往一个方向的旋转相当于电梯的上升或下降，

听起来还是比较简单的对吗，下面我们分别用 Java 和 Python 实现一下。

  • 最小化磁盘寻址时间
  • 优先处理特定 I/O 请求
1
2
3
4
5

public static void main(String[] args) {
    return 0;
}

1
def scan(requests, start)

电梯组数多起来后性质发生了什么变化呢

看起来对 SCAN 的理解和实现都比较简单，那么电梯调度的复杂究竟在哪里呢。

群控电梯。

在 2001 年《控制与决策》上的一篇文章就提到

国内使用的先进的电梯群控系统基本上都是国外电梯公司制造的…国内自主版权的控制方法和技术在实际中的应用还未见报道。…国外已有的先进控制技术, 很多都掌握在各个大电梯公司手中, 其核心技术是不公开的…

确定研究对象，得出结论

平均等待时间
专家系统，模糊逻辑

这里介绍一下什么是 NP-Hard 问题，已经了解了的可以跳转下一节。
凡是有计算机基础的都应该听说过 P/NP 问题，但是要从。
得到问题的解和验证一个解是否正确，这个快速就是说的多项式时间，是

图灵机，。不确定性图灵机

  • 影响电梯调度复杂度的参数，数学公式
  • 介绍 NP-hard

实际上，在一个 k 层楼，n 台电梯的系统中，一共有 n^k 中状态。

与线程调度的关系

或许是快手总部的楼层数和电梯数都不够多，电梯调度的复杂程度好像离我们比较远

  • 为什么没有进程调度
  • 线程调度的两个类型
  • CPU

其他经典调度问题

Google 查询 “scheduling problem” 时，排名靠前的是其他，我们也做一些简单的介绍。

结语

以上是我对电梯调度及相关问题的简单介绍，

我觉得，也对这些市场规模相对较小的工程领域充满了敬畏之心。

延伸阅读

有过算法学习经历的同学一般都了解旅行商问题(Traveling salesman problem)。
“给定义一组城市和每对城市间距离，求访问每个城市恰好一次并能回到起始城市的最短路径”

  • NP-hard，旅行商问题

部分网页不能正常显示的需要下载文件查看。

体会