OO第二次博客作业——电梯调度

 

oo第二次博客作业——电梯调度

前言

最近三周，oo课程进入多线程学习阶段，主要通过三次电梯调度作业来学习。从单部电梯的傻瓜式调度到有性能要求的调度到多部电梯的调度，难度逐渐提升，对同学们的要求逐渐变高，我们对线程的理解也逐渐加深。下面笔者将对三次作业分别进行总结。

一、单部多线程傻瓜调度（fafs）电梯

说明：本次作业需要模拟一个多线程实时电梯系统，从标准输入中输入请求信息，程序进行接收和处理，模拟电梯运行，将必要的运行信息通过输出接口进行输出。本次作业对性能要求非常宽松，不需要进行优化处理。

  

构思：由于不考虑性能，在main中每收到一个输入，新开启一个request线程，request线程调用电梯类elevator的work方法。其中work方法是synchronized的方法，所以一个请求未处理完前其他请求被阻塞。

程序复杂度：

由于算法简单，复杂度较低。

程序依赖：

在依赖上表现良好。

 

评价：在线程安全性上很完美，并且完成了所有功能，没有bug。缺点在于性能不够优秀xd。这次作业算是多线程的一次小练手，熟悉了多线程编程方法。

 

二、单部多线程可捎带调度（als）电梯

说明：本次对电梯性能有一定要求，需要我们自行设计算法或使用a little smart算法。

构思：考虑到对性能的要求，使用的是类look算法。具体而言，电梯扫描同一方向的请求至无同向，然后反向。根据这一思路，设计了5个类。main创建controller和elevator两个线程。controller负责接收输入，并向requestlist中存入请求。elevator扫描requestlist并取出请求。

 

程序复杂度：

平均复杂度尚可，在电梯类中有少数方法复杂度稍高。主要是遍历请求列表和while循环电梯上下运行导致的，不可避免。

依赖：

代码行数：

 

评价：在强测中出现了一个bug：同时间输入大量请求，而调度器未能全部同时接受导致超时。分析：电梯上下楼、开关门时白白占用requestlist的锁，应该让调度器继续运作。调整了锁的分配，如关门时让电梯wait一定时间，此时调度器可以占用锁。

总结：由于对锁的分配没有思考到位，没有最大化优化临界资源使用率，导致在极端情况下性能出现问题。

 

三、多部多线程智能（ss）调度电梯

说明：本次作业有多部电梯，对性能要求放松了，将重点放在线程安全和同步的设计上，在于最大限度降低耦合，每个对象只应该管自己该管的事。

构思：延续上次作业的思路，对每个电梯分配一个请求队列，调度器可以观察3个请求队列，并选择性写入。电梯在乘客换乘时调用调度器进行添加请求。这样一来，就最大限度地降低了耦合。只有请求队列是共享资源，容易处理线程的同步。

类图：

 

 复杂度：

在遍历请求列表时复杂度变大，总体较好。

依赖：

controller与elevator共享请求队列。

行数：

评价：

强测出现bug，发生了死锁。排查后发现问题在于在添加请求这一方法上偶然出现互相持有资源导致。调整synchronized的范围，使死锁的必要条件消失（请求资源前放弃资源）解决了bug。

总结：

在设计程序时没有预防死锁这一bug的出现，说明对线程同步的考虑仍然不够周到。然而失败是最好的老师，在这一次作业完成后，认识到构思程序时，应更加谨慎、全面地考虑线程安全问题。

 

bug攻防

采用测评机发现bug，在最后一次阅读代码发现了bug。

 

心得体会

（1）保证线程安全。

　　做好资源的分配，尤其是预防死锁的出现。

（2）集中化数据管理。

　　将一组单独写成一个类便于管理，例如电梯的状态。

（3）在底层类实现方法，提供接口，顶层类直接调用，让自己的代码更有层次感、