姓名：
学号：
[TOC]
- 学习调度算法
- 通过实现电梯调度，体会操作系统调度过程
- 学习特定环境下多线程编程方法
- 开发环境：Chrome+VS Code
- 开发语言：HTML+CSS+JavaScript
- 第三方框架：Element UI、Vue.js、Webpack
某一栋楼20层，有5部互联的电梯。基于线程的思想，编写一个电梯调度程序。
五部电梯门口的按钮是互联结的，即当外部请求按钮按下去时，需要操作系统选择一部电梯来响应这个请求。
所有电梯初始状态都在第一层，无按钮被按下。每个电梯如果在它的上层或者下层没有相应请求情况下，则应该在原地保持不动。
-
项目在线预览地址（需联网）：https://xuedixuedi.github.io/Elevator-dispatching-demo/dist/
-
或克隆本仓库/进入作业文件夹后，在终端输入以下命令预览：
# install dependencies
npm install
# serve with hot reload at localhost:8080
npm run dev
# build for production with minification
npm run build
# build for production and view the bundle analyzer report
npm run build --report 打开浏览器，输入 http://localhost:8080/ 预览
| 组件 | 内容 | 负责逻辑 |
|---|---|---|
| Home | 盛放Inside和Outside的父组件 | 处理电梯外部调度逻辑 |
| Inside | 每部电梯的内部 | 处理电梯内调度逻辑 |
| Outside | 每层楼的外部按钮 | 处理每层楼按钮逻辑 |
电梯内部：
-
楼层数字键
-
开门/关门键
-
报警键、紧急通话键
-
当前楼层及运行方向显示
电梯外部：
- 每层楼对应上下行键
| 系统 | 功能 |
|---|---|
| 监控系统 | 每一个最小时间间隔汇报并修改一次电梯状态 |
| 交互系统 | 接受来自电梯内外用户按下按钮的指令 |
| 调度系统 | 调度系统负责实现电梯运行的主要逻辑 |
| 变量 | 作用 | 值/类型 |
|---|---|---|
| running | 描述电梯在是否在运行中 | bool |
| going_up | 描述电梯当前状态是向上或向下（对应内部显示方向） | bool |
| door | 描述当前门是打开或关闭 | bool |
| current_floor | 描述电梯当前楼层位置 | Number |
| outside_up[] | 楼层数对应下标存放外部向上的呼梯信号 | 1或0 |
| outside_down[] | 楼层数对应下标存放外部向下的呼梯信号 | 1或0 |
| inside[] | 楼层数对应下标存放内部呼梯信号 | 1或0 |
| call[] | 存放内外所有呼梯信号 | 呼梯楼层数 |
| button_click[] | 楼层数对应下标存放内部按钮是否被按下，关联内部显示样式 | 1或0 |
| 函数 | 功能 |
|---|---|
| dial(floor) | 将按下的按钮加入call[]队列并将队列从大到小排序，并更新当前电梯状态 |
| checkStatus() | 接受来自电梯内外用户按下按钮的指令，并及时更新running 和 going_up的值 |
| run() | 判断运行中的电梯当前楼层是否存在内外呼叫队列中，如果存在，改变电梯运行状态并更新当前状态 |
| ding(floor) | 暂停计时器，开门，关门，重新开启计时器 |
| calculateDistance(press_floor) | 计算当前外部按下的楼层应该加入哪一部电梯的等待队列 |
核心算法：LOOK算法
电梯调度的核心是 SCAN 算法，这是操作系统用于磁盘调度的算法之一。SCAN 算法的核心思想非常简单，就是在一条路上来来回回的走，一个方向上走到头之后换反方向再走到头。
LOOK算法是SCAN算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。
要实现这个算法，主要需要两样东西：一个数组，以及一个“LOOK”的算法。
1. 等待队列
dial(floor) {
console.log("现在按下第几层？", floor)
this.call.push(floor)
this.call.sort()
console.log("现在的队列是：", this.call)
if (!this.running) {
this.checkStatus()
}
// }
},我用一个数组 call 来保存所有被按下的楼层，无论是在电梯外还是电梯内按的。 dial() 函数同样适用于电梯内外的所有楼层按钮，只要按下，都按照其中的逻辑添加到 queue 中。但一个数字最多在数组中出现三次：内部请求，外部向上请求，外部向下请求。
sort() 这一步很关键，它确保了前进方向上楼层都是以楼层数为序的，而不是以添加顺序为序（这是电梯调度算法的特点）。这里因为数据量不大，因此不深究排序算法的复杂度，直接使用Array类的原生方法。
同时，需要维护inside[]，outside_up[]，outside_down[]三个数组，用来判断队列中的数字是来自哪里的请求。
2. LOOK算法
checkStatus() {
//判断呼叫队列是否还有东西，修改运行状态
this.running = this.call.length > 0 ? true : false
//是否在底层
if (this.current_floor == this.min_floor) {
this.going_up = true
//是否在顶层
} else if (this.current_floor == this.max_floor) {
this.going_up = false
} else {
//在中间层的状态判断
this.going_up &&
(!this.running ||
this.current_floor <= this.getMaxInQueue(this.call))
? (this.going_up = true)
: (this.going_up = false)
!this.going_up &&
(!this.running ||
this.current_floor >= this.getMinInQueue(this.call))
? (this.going_up = false)
: (this.going_up = true)
console.log(this.getMaxInQueue(this.call), this.going_up)
}
},checkStatus() 用于更新一些状态变量的取值，用于决定电梯是否开始运行，以及什么时候该回头了。 running 用于记录当前电梯的运行状态，初始状态为 false，因为假定它停在一楼。只要有任何一层楼被按下，即数组 queue 非空，电梯就处于运行状态。 going—_up 用于记录电梯是上行还是下行，上行为 true，下行为 false，初始状态为 true，因为假定它停在一楼，向上的可能性最大。在顶层和底层时固定回头，对于中间的楼层，就看当前前进方向上时候存在于请求队列的楼层，如果有，就继续走，否则回头。对于停止状态下的电梯，暂时不管它的状态。
3. 主函数
设定了一个定时器，每秒钟运行一次主函数run()，执行电梯的移动和判断当前是否需要停靠等动作。
对于运行中的电梯， run() 函数首先检查当前楼层时候被按下，即 current_floor 是否存在于数组 call 中，存在则调用 ding(floor) 函数，暂停计时器，熄灭该楼层按钮的灯光，将该楼层从数组中移除，开门，关门，重启计时器。否则根据行进方向向上或向下移动一层，并更新楼层计数器。注意：由于 JavaScript 本身并不支持类似 sleep(milis) 这种用于暂停的函数，而回调机制又都是异步的，因此只能通过嵌套的 setTimeout() 来实现延时触发的效果，好在这里只有两个动作需要回调，否则代码的嵌套深度会达到惊人的程度。
运行函数：
run() {
var need_stop = false
if (this.running) {
if (this.call.indexOf(this.current_floor) > -1) {
//到达内部呼叫楼层
if (this.inside[this.current_floor] == 1) {
this.removeFromQueue(this.call, this.current_floor)
this.inside[this.current_floor] = 0
this.button_click[this.current_floor] = 0
need_stop = true
}
if (this.going_up) {
if (this.outside_up[this.current_floor] == 1) {
console.log("到达外面呼叫：", this.current_floor)
this.removeFromQueue(this.call, this.current_floor)
this.outside_up[this.current_floor] = 0
this.updateOutsideUp(this.current_floor)
need_stop = true
}
if (
this.outside_down[this.current_floor] == 1 &&
this.current_floor == this.getMaxInQueue(this.call)
) {
this.removeFromQueue(this.call, this.current_floor)
this.outside_down[this.current_floor] = 0
this.updateOutsideDown(this.current_floor)
need_stop = true
}
} else {
if (this.outside_down[this.current_floor] == 1) {
this.removeFromQueue(this.call, this.current_floor)
this.outside_down[this.current_floor] = 0
this.updateOutsideDown(this.current_floor)
need_stop = true
}
if (
this.outside_up[this.current_floor] == 1 &&
this.current_floor == this.getMinInQueue(this.call)
) {
this.removeFromQueue(this.call, this.current_floor)
this.outside_up[this.current_floor] = 0
this.updateOutsideUp(this.current_floor)
need_stop = true
}
}
if (need_stop) {
console.log("stop:", this.current_floor)
this.ding(this.current_floor)
} else {
this.going_up ? this.moveUp() : this.moveDown()
}
} else {
this.going_up ? this.moveUp() : this.moveDown()
this.updateFloorInfo()
}
this.checkStatus()
}
},停靠函数：
//暂停计时器，熄灭该楼层的灯光
ding(floor) {
let _this = this
let that = this
//需要电梯停下，就把timer清空
if (this.timer) {
clearInterval(this.timer)
}
this.openDoor()
//不会重复执行的延时函数
setTimeout(function() {
_this.closeDoor()
setTimeout(function() {
that.timer = setInterval(that.run, 1000)
}, 3000)
}, 4000)
},this.timer = setInterval(this.run, 1000)外调度主要考虑外部1-20楼按下的电梯请求，需要5部电梯中的哪一部来解决，本系统采用的方法是：在每一次外部按钮被点击时，得到五部电梯的运行方向与当前楼层，以及等待队列中有哪些楼层，通过计算每一部电梯到达当前楼层的时间，综合中间需要停顿的时间，得到到达发送请求楼层时间最短的电梯，并将该请求加入电梯的请求队列。一旦一部电梯接受了这个请求，其他电梯将不再考虑这个请求。
计算某层按下向上的按钮时应该加入哪部电梯的代码：
//计算应该放入哪个电梯
calculateUpDistance(press_floor) {
var maxDistance = 2 * this.floor_count //可能出现的最小距离
var distance = 0
var elevatorToPush = 1
for (var i = 0; i < this.ele_count; i++) {
if (!this.running[i]) {
distance = Math.abs(press_floor - this.current_floor[i])
} else {
var minInQueue = this.getMinInQueue(this.call[i]) //找出呼叫队列中最小的
var maxInQueue = this.getMaxInQueue(this.call[i]) //找出呼叫队列中最大的
if (this.current_floor[i] <= press_floor) {
if (this.going_up[i]) {
console.log("电梯向上，按键比当前高")
distance =
press_floor -
this.current_floor[i] +
5 *
this.betweenCount(
press_floor,
this.current_floor[i],
i
)
} else {
console.log("电梯向下，按键比当前高")
distance =
this.current_floor[i] -
minInQueue +
press_floor -
minInQueue +
5 *
this.betweenCount(
minInQueue,
press_floor,
i
)
}
} else {
if (this.going_up[i]) {
console.log("电梯向上，按键比当前低")
distance =
maxInQueue -
this.current_floor[i] +
maxInQueue -
minInQueue +
Math.abs(minInQueue - press_floor) +
5 *
this.betweenCount(
maxDistance,
maxInQueue,
i
)
console.log(
"distance:",
distance,
"max:",
maxDistance
)
} else {
console.log("电梯向下，按键比当前低")
distance =
this.current_floor[i] -
minInQueue +
Math.abs(minInQueue - press_floor) +
5 *
this.betweenCount(
this.current_floor[i],
minInQueue,
i
)
}
}
if (distance < maxDistance) {
maxDistance = distance
elevatorToPush = i + 1
}
}
}
console.log(
press_floor + "上楼将要放入第" + elevatorToPush + "电梯"
)
this.up = true
return elevatorToPush //得到按下按键的楼层即将放入哪个电梯
-
初始界面
-
运行界面截图
-
紧急通话&报警
-
电梯运行
-
由于对js语言不甚熟悉，在
setTimeout()函数中传入函数时，函数会指向window对象，而不是当前组件对象。为了解决这个问题，在代码中加入
let this = that重命名this即可解决，或采用ES6中的箭头函数即可。
- 采用了响应式布局，保证了在多种分辨率和大小的浏览器，包括PC端和手机端上运行均能保持较为美观的用户界面。
- 布局到了GitHub Pages，使该项目的体验只需要具备一款主流浏览器即可，不需要额外环境负担。
- 采用高度组件化的开发，代码低耦合高内聚，在需要修改电梯数量和总楼层数量时，仅需要对代码进行简单修改即可实现。
- 纯粹采用前端开发，没有在本次项目中采用与后端通信的方式，而是将所有逻辑写在前端中。由于需要在多组件中传值，没有对传值做足够的优化，导致了部分代码的冗余。
- 在外部调度中，即按下的按钮需要分配给哪部电梯的算法中，使用的算法是对到达时间粗略的估计，没有考虑当电梯需要在某层楼长期开门停靠时，当前电梯等待队列可能出现的饥饿情况。后查找资料发现，目前电梯的控制技术已经进入了电梯群控的时代。陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。这些能更好的解决出现的问题