北航OO第二单元——电梯调度
2024-09-17 22:00:56
三次作业要求简介
特点：目的选层电梯
- 在电梯的每层入口，都有一个输入装置，让每个乘客输入自己的目的楼层。电梯基于这样的一个目的地选择系统进行调度，将乘客运送到指定的目标楼层。
第一次：
- 在任意时刻输入一个或多个请求，包括出发层、目的层、乘客的id（每一个乘客有独有的id，且我们设计的系统是直到这个id的）
- 电梯可以控制谁能出电梯、谁能进电梯
- 在到达楼层、开门关门、出人进人时输出
- 第一次作业是单电梯，电梯能够在1-20楼运行
第二次：
- 初始有3部电梯，可以通过指令增加1-2部电梯
第三次：
有三种电梯
型号 到达楼层 移动速度 限乘人数 A 1-20 0.6s/层 8 B 奇数层 0.4s/层 6 C 1-3，18-20 0.2s/层 4 初始状态有A、B、C三种型号各一部，可以通过指令增加任意类型的电梯
设计过程分析
我认为，这一单元的主要设计难点有二：
- 确定线程数量和各线程控制的类
- 确定使用何种形式对电梯进行控制
一旦确定了这两点，经过第一单元训练的你应该就能很轻松的做好类的规划，并写出整个作业了。我想你应该对我是如何得出最终设计没有兴趣，所以下面来直接说说我的设计
作业设计
类图
类的关系概要
MInputThread- 正如其名，这个类主要用来不断地从标准输入读取指令，并将其加入指令队列
MRequestQueue中 - 这是一个线程
- 正如其名，这个类主要用来不断地从标准输入读取指令，并将其加入指令队列
MDispatcher- 指令分配器。使用单例模式，整个系统只有一个分配器
MDispatcher持续尝试从MRequestQueue中获取新的请求，并决定将这个请求分配给哪一个电梯的MController- 注意：我的算法是直接将请求分配过去，而不是将一条指令分配过去。电梯控制器接收到该请求如何执行是
MController的事情 - 在第三次作业中，这个类还先尝试将指令拆分，实现乘客的换乘
- 这是一个线程。当
MInputThread在等待下一条输入时，可以继续利用CPU，实现指令的分配
MController- 电梯控制器，从维护一个
MRequestList，从MDispatcher接受请求，控制电梯的移动 - 一个电梯有一个电梯控制器
- 电梯控制器，从维护一个
MElevator- 电梯类，在本单元作业中仅仅存储电梯的最大人数、运行一层的时间、开门关门的时间等。
- 我们并不控制实际存在的电梯，为了充分的可拓展性，设立
MElevator - 在第三次作业中，此类被设置为抽象类，并编写了三个不同类型电梯的子类
MOutput- 类如其名，输出类，简化算法中输出语句的复杂度
MSeparator- 拆分指令的类，其中只包含静态方法，因为没有自己的成员变量。
MRequestQueue- java的
Queue的包装类，并增加了isClose()方法，标记输入是否已经结束，从而结束各个线程
- java的
MRequestList- 每一个电梯控制器拥有一个
MRequestList，存放着要处理的请求 MRequestList中存放了两个链表upList和downList，分别存放上楼的请求和下楼的请求，并按照起始楼号排序- 有一个
head，指向下一条要处理的指令 - 注意：以上三条仅适用于单一的运行算法，若有其他算法可以在此类中调整
- 每一个电梯控制器拥有一个
算法设计
以下算法之间是相互独立的，可以更改任意一个不影响其他算法的运行。这也是符合面向对象程序设计思想的
请求分配算法
MDispatcher负责该算法，采用贪心算法进行请求分配- 每当得到一条请求，遍历所有电梯（第三次作业中，变为能够运行该请求的电梯），将其
clone两份，一份保持原状运行到电梯内的MRequestList为空且电梯内没有人的总时间，一份添加该请求后再计算总时间。两个时间的差值为运行该指令需要增加的时间。找到所有电梯中增加时间最小的，将该条请求分配给他 - 注意：
- 在
clone之后，电梯的状态可能已经发生了变化，但是可能性相对较小，因此及时产生误差也不要紧，可以将指令继续分配给相应的电梯 - 此处贪心贪的是增加的时间，也可以贪增加该请求后的运行时间，从理论无法证明两种贪心哪一种好，但是实践证明前者好一些
- 在
电梯运行算法
采用基础的捎带原则，和常见的电梯一致
每次电梯保持一个方向运行，沿路捎带同方向的请求，直到该方向上没有请求且电梯内的人已经全部离开，再调转方向
该算法是通过由
MRequestList中维护的特殊循环链表实现的，将所有请求适当排序，每一次的head指向的位置就是该算法下电梯下一个要处理的请求注意：
要时刻注意可拓展性，减少单个方法的复杂度。比如
MController（电梯控制器）的run()方法大概可以写成public void run () {
if (hasPersonIn || hasPersonOut) {
openDoor();
outPerson();
inPerson();
closeDoor();
}
if (hasNextMission()) {
goNextFloor();
}
}
这样可以最大程度保留可读性和可扩展性，不需要注释就能看懂整个算法的框架
请求拆分算法
- 我没有采用一些能在理论上达到最短路的算法，而是手动计算各种常见情况，判断是否需要拆分指令换乘
- 具体拆分算法如下：
- 条件：能用B、C电梯承载的就不换乘；换乘至多一次
- 因此将请求分为不换乘、通过AB换乘、通过BC换乘、通过AC换乘四种情况
- 对于需要换乘的请求，计算通过AB、BC、AC换乘和不换乘（也就是只通过A）所需的时间（如果不能换乘则返回
Long.MAX_VALUE），选择时间最短
- 换乘方法如下：
MSeparator将指令拆分为一个ArrayList<PersonRequest>数组返回给MDispatcher，如果数组长度大于1，则将第一项作为key，第二项作为value加入一个HashMap中，第二项和第三项等等以此类推- 每当电梯让一个请求出电梯时，使用观察者模式通知并将该请求传递给
MDispatcher，MDispatcher拿到后去HashMap中寻找，如果找到对应的value，则将新的value分派给电梯，并将此键-值对删除
多线程的经验
在看以下的内容之前，建议你最好已经自己动手写完了电梯，进行了一定的试错和碰壁后，再阅读或许能够有更大的收获
摘要
synchronized块能多小就多小！
一定要保证在不得不用的那一行再使用
synchronized，而且一旦在逻辑上不再需要该对象，或者是该对象改变了也不影响的时候，就赶紧退出synchronized，把锁释放掉不要一个
synchronized把整个方法都框起来，这样极大地降低了运行效率；另外，不要随便
wait()!wait()极其容易产生死锁，一定要自己充分考虑后再使用wait()
bug分析
- 第一次作业卡点交上去结果全部TLE，原因是产生了死锁
- 后期分析原因，是因为
wait() notifyAll()的组织方式出现了问题，很可能在没有wait的时候notify了，从而产生notify信号丢失。 - 这是由于算法中对
synchronized块的使用过于简单粗暴，该释放的时候没有释放掉，一直拿着锁，从而使运行逻辑产生奇妙的变化 - 互测阶段并没有看或者测别人的代码，因此没有相关经验
心得体会
线程安全：
- 在上面的 多线程经验 已经说过
层次化设计
- 多线程的层次设计要比多项式困难的多，因为是三个线程同步运行，大大增加了设计难度。
- 我自认为设计的比较有层次性，能保留扩展性的地方都保留了，三次作业并没有大的重构过
- 然而，模块之间的关系还是有一些丑陋，不是完全的面型对象。比如在贪心算法中，
MDispatcher调用MController的clone()，将其拷贝一份再调用拷贝对象的getRunTimeWithRequest(PersonRequest)方法（获得加上一个请求后的运行时间）获得运行时间 - 这一段的代码逻辑总让我决定不美，但我无法说出哪里不美，也不知道该如何修改。如果你能看出来，可以告诉我
- 邮箱：13061262721@163.com
三个周的时间，让所有人的多线程设计能力、面向对象设计能力同时得到极大提高，不得不说课程组真是高啊
最新文章
- linux系统的初化始配置
- css3 妙味
- SBT Assembly - Deduplicate error & Exclude error
- python发送邮件方法
- cocos2dx 3.x（Button传统按钮）
- Linux服务器集群系统（一）--转
- POJ2752 Seek the Name,Seek the Fame KMP算法
- CentOS查看系统信息-CentOS查看命令
- NFC规范学习之一 ---整体结构
- 移动web经验积累
- STL库list::sort()实现深度解析
- jQuery 双击事件（dblclick）时，不触发单击事件(click)
- Oracle表连接总结
- UFLDL接听教程练习（来自编码器和矢量编程疏）
- 利用maven install jar到项目当中
- JWT是什么鬼
- 如果往错误的NEO地址转账会发生什么
- 事件&表达式
- 【转】c语言中的#号和##号的作用
- django----常用功能