2022-OO-Unit2

mashiroly

1. 总体思路

​ 本单元的需求是模拟多部电梯的调度，重在设计出多线程安全并发协作的架构。基本思路仍是“生产者-消费者”(Producer-Consumer)模式，固定“生产者”和“消费者”，面对不同功能构造不同“盘子”。电梯的运行策略经历了ALS策略到LOOK策略的迭代。在此基础上，通过对线程安全的精心设计，弱化调度、强调自由竞争，以面对非真实场景（指数据或随机或针对性构造，无特征可言）提高性能。

2. 架构迭代

2. 1 第1次作业

思路概述

在拿到题目之初，曾想过设计一个“单例集中式上帝调度器”，电梯只是一个无情的工具人，只需知道自己往哪走就足够了，而生成这一方向信息完全由调度器负责。
但仔细想想实现：在一次循环中，调度器要完成1. 取出一个或所有输入的请求；2. 根据电梯状态完成调度。可能带来的问题有：1. 线程类作为另一个线程的属性是不合理的设计，这就需要分离“电梯状态”（用于共享）与“电梯线程”；2. 似乎将“调度”与“请求输入”同步了，调度器也没必要作为线程；3. 所有复杂度都交给调度器，循环内耗时大，请求不能及时调度。总觉得三个问题叠加后显得这个架构不够具象，还是回到经典的“生产者-消费者”模式吧。

在我的理解中，请求输入—调度、调度—电梯行为都是异步关系，两组关系的前者均不关心后者状态如何、如何处理。参考Training代码，构造两组“生产者-消费者”。图示如下。

flowchart LR subgraph Producer A[InputThread] C[Scheduler] end subgraph Tray W[waitQueue] F[processList] G[processQueue1] H[processQueue5] K[...] end subgraph Consumer B[Scheduler] I[ElevatorThread1] J[ElevatorThread5] end F-.->K A---> W --->B C ---> F -.-> G-->I F -.->H-->J

架构说明

类图：

说明：

1. RequestQueue:需求队列，PersonRequest的聚合。共享对象waitQueue和processQueue均是RequestQueue.

​ 待处理队列processQueue由“按电梯划分”和“按楼座划分”的思路（本次作业两者是相同的）。从上一张图也可以看出，我们这里“按电梯划分”，每个电梯ElevatorThread独享一个processQueue。

2. processQueue的聚合processList由调度器Scheduler直接管理。

​ Scheduler:调度器。其实所谓“调度”不过是把输入的请求根据电梯ID分配到共享对象processQueue中，称为“Dispatcher”也未尝不可。

3. ElevatorThread:电梯，自行负责开关门dealIO(),选择运行方向selectStatus(),运行move()，将从属于电梯的行为尽可能内聚。由于对PersonRequest的处理是“人进入电梯，则从processQueue中删除，因此还需用waitTable保存电梯内的人。

​ 此外，dealIO()时需要对processQueue遍历时删除。查阅资料及讨论区，采用迭代器可以完美解决。

调度策略

本次作业采用基准策略ALS，根据指导书描述实现。指导书对ALS的描述看起来很奇怪，其实只有两部分：1. 确定主请求，方向(moveStatus∈{UP, DOWN, STOP})由主请求决定；2. dealIO()时判断稍带。

        if (iter.getFromFloor() == nowFloor
                && !waitTable.containsKey(iter.getPersonId())
                && (getRequestDirection(iter).equals(moveStatus)
                || getRequestDirection(iter).equals("STOP")
                || moveStatus.equals("STOP"))
                && !this.isFull()) {
            //PersonIn
        }

线程安全问题

本次作业还是比较严格的”生产者-消费者“，线程安全问题主要出现在对共享对象的互斥操作。在共享对象类RequestQueue中，对所有读写方法（我的实现中，所有方法都是）设置synchronized同步块，加方法锁。

对于互斥操作涉及多个方法和复杂逻辑（典型如需要遍历processQueue的dealIO())，自然是同步块加对象锁保证互斥。

线程不安全的官方输出需要加方法锁，封装成类，保证调用的互斥。

轮询问题

同步块内wait-notify用于避免轮询。具体而言，如果所有处理未结束，则Scheduler中使用synchronized同步块对waitQueue上对象锁，如果为空则wait()；ElevatorThread对ProcessQueue上锁，如果和waitTalbe均为空则wait()。

只有putRequest()和setEnd()可以notifyAll()，前者是有请求输入，后者是输入结束，以提醒各个线程处理完成后退出。也就是说，只出现两个notifyAll()，保证正确而极大减少轮询。

2.2 第2次作业

思路概述

增加横向电梯？不过是体力劳动罢了。（逃）
同一楼座多部电梯的协作是这次作业的主要问题。为了避免过于复杂的调度器类和调度方法，导致奇怪bug太多、互斥同步复杂，最终还是选择自由竞争，把Request分配给同一楼座的所有电梯、抢不到人就消除请求，就只需解决同步问题了。为此增加了新的共享对象outPassengers.

flowchart LR subgraph Producer A[InputThread] C[Scheduler] L[Scheduler] end subgraph Tray W[waitQueue] F[processList] G[processQueue1] H[processQueue5] K[...] M[outPassengers] end subgraph Consumer B[Scheduler] I[ElevatorThread1] J[ElevatorThread5] N[ElevatorThread1..n] end F-.->K A---> W --->B C ---> F -.-> G-->I F -.->H-->J L --> M M --> N

此外，上周的ALS策略性能不妙，本周改写了LOOK策略。

架构说明

类图：

说明：

整体上变化不大。

1. ProcessTree类：和上一次作业的processList功能相同，都是待处理队列的聚合。由于自由竞争需要检索同一楼座的所有电梯，涉及遍历，这个类目的就在于构建多级索引减少遍历次数。（后来才发现最多只有15部电梯，直接遍历可能还更快吧）
2. ExPersonRequest：拓展的需求类。
3. Scheduler：负责分配载人请求和直接处理增加电梯请求。（仅一个方法，没必要再加一个电梯管理类）
4. ElevatorThread：横纵电梯集成在一个类，由type切换模式。纯粹是方便拓展横纵可切换的电梯。”按电梯划分“processQueue的优点在这里体现出来了，每部电梯对请求的处理独立，无需手动阻塞避免冲突。
5. OutPassengers：处于电梯外的人。”电梯外“针对全局而非某一楼座，也因此共享对象outPassengers是所有电梯和调度器共享的。和”按楼座划分电梯外的人“相比，全局的“电梯外”牺牲的是访问共享对象时会阻塞所有线程，换来的是避免大量复杂的线程控制，以及方便拓展”换乘“。而“牺牲”可以通过读写锁缓解。

调度策略

纵向：LOOK策略，主请求定方向，记录楼层极值，到当前极值后停下/转向；

横向：类LOOK策略，主请求定方向（最短路径方向），记录目标楼座，到达后停下/转向；

线程安全问题

仍是通过synchronized同步块实现对共享对象outPassengers的互斥读写。

2.3 第3次作业

思路概述

横向电梯新增可达性约束，电梯需要参数化，真的很麻烦呢。

增加换乘需求是主要问题。将所有PersonRequest划分为“纵-横-纵”三阶段，用状态机更新PersonRequest本身，如果未完成则放回waitQueue中。

flowchart LR subgraph Producer A[InputThread] C[Scheduler] L[Scheduler] O[ElevatorThread1..n] end subgraph Tray W[waitQueue] F[processList] G[processQueue1] H[processQueue5] K[...] M[outPassengers] end subgraph Consumer B[Scheduler] I[ElevatorThread1] J[ElevatorThread5] N[ElevatorThread1..n] end F-.->K A---> W --->B C ---> F -.-> G-->I F -.->H-->J L --> M M --> N O --> W

仍采取自由竞争+LOOK策略。

架构说明

类图：

顺序图：

说明：

其实可以发现，waitQueue和processQueue虽然都是RequestQueue类的对象，但两者的行为、在架构中的位置已然分道扬镳，完全可以再加一层封装或采用多态，各自实现的方法。时间所限没有这样做。

1. requestQueue新增属性count及相应的加减方法，供waitQueue使用，表示请求未完成的人数。如果没有这一计数，电梯线程将提前被调度器调用的setEndAll()终止。
2. ExPersonRequest内部实现状态机，根据“纵-横-纵”三阶段划分，对外暴露当前阶段的起终点。被电梯线程处理时直接更新本体，放回waitQueue的也是本体。也就是说需求的数量是不变的，变的只有对外暴露的”接口“。
3. Scheduler：由于可信赖的自由竞争，调度器最终也没有实现一开始规划的复杂”调度“任务。不如就叫DIspatcher吧。
4. ElevatorThread：最终也没有出现斜向电梯和类型可变电梯。集成两种类型的电梯就当减少类图工作量吧。

调度策略

中转楼层的选择根据官方策略，遍历所有楼层取有可达电梯的最近楼层。

”按电梯划分“ProcessQueue依然非常适合自由竞争。

线程安全问题和轮询问题

秉持锁最小化的思路，尽量缩减同步块的范围，并避免嵌套，至少绝对不出现:

synchronized(A) {
	synchronized(B){
	notifyAll()
    }
notifyAll()
}

针对不同情况的wait后能正确被唤醒， 在RequestQueue类的subCount()方法增加了第三个notifyAll()，与setEnd()方法的notifyAll()功能完全相同。

3. 度量分析

直接看第3次作业的度量分析。

method	Cogc	ev(G)	iv(G)	v(G)
Scheduler.addPersonRequest(ExPersonRequest)	16.0	6.0	6.0	7.0
ElevatorThread.checkIn(ExPersonRequest)	6.0	3.0	6.0	7.0
ElevatorThread.lookUpdown()	13.0	2.0	6.0	8.0
InputThread.run()	10.0	3.0	6.0	6.0
ElevatorThread.run()	15.0	5.0	8.0	10.0
Scheduler.run()	15.0	4.0	9.0	10.0
ElevatorThread.dealIO()	27.0	4.0	12.0	12.0
Total	186.0	87.0	136.0	164.0
Average	3.0	1.40	2.19	2.64

除了run()方法，look策略、dealIO均有遍历并操作，addRequest有多级索引检索，dealIO、checkIn/Out涉及复杂的判断、分支，因此复杂度较高。

class	OCavg	Ocmax	WMC
SafeOutput	1.0	1.0	1.0
RequestQueue	1.0	1.0	13.0
ProcessTree	1.625	4.0	13.0
OutPassengers	1.125	2.0	9.0
MainClass	2.0	2.0	2.0
InputThread	3.0	5.0	6.0
ExPersonRequest	1.84	5.0	24.0
ElevatorThread	4.91	9.0	59.0
Scheduler	4.25	7.0	17.0
Total			144.0
Average	2.32	4.0	16.0

ElecatorThread的复杂符合设计预期。Scheduler的复杂度来自一次循环对多个共享对象操作、反复进行多级索引检索。

4. Bug分析

本单元手工构造数据只能覆盖几种明显的边界情况，主要依靠随机数据生成，参考讨论区和自己的理解造了简陋的评测机。只要开多个终端，我也实现多进程评测了对吧。（雾）

第1次作业的bug是输出线程不安全，输出时间戳顺序不递增。用线程安全的SafeOutput类封装输出解决。

第2次作业的bug是电梯线程对outPassengers的访问涉及两步两个方法，没有加锁，导致线程安全问题。

第3次作业的bug真是欲哭无泪。直接贴修复文档吧。只能说第2次作业的开门逻辑拓展性太差，第3次没多想直接沿用就爆炸了。

修改了电梯在自由竞争中的开门逻辑问题。

1. 横向电梯接人时只考虑起点能开门，没有考虑终点也需要能开门。

   举例说明：对某换乘Request选择中转层时，依据某层起终点均可达的电梯Ele 1；但自由竞争中，可能出现中转层另一部电梯Ele 2，对该Request起终点不可达却成功接人。

   修改方案：加上对终点的判断条件。

2. 自由竞争时，未被电梯接走的人用共享对象outPassengers保存。但有关该共享对象的分支和修改放在了if(checkin)分支内，即：先确定能进入，再确定有无此人，如果没有则说明其他电梯接走了，删除Request。

   在hw6中，由于Request不可变，即使某部电梯已接走人，同层（座）其他电梯总能进入if(checkin)并正确删除。

   在本次作业中，我的实现是修改Request本身，而非继续将Request作为不可变对象、new新的Request加入调度。因此，当”building”请求变为“floor”请求（或相反），电梯再也不能进入if(checkin)，该Request始终无法删除，电梯陷入死循环。

   修改方案：调整if(checkin)和查询outPassengers的顺序。

5. 心得体会

纵观三次作业，迭代拓展主要体现在增加实现新功能”共享对象“，经典的”生产者-消费者“模式一招鲜吃遍天下。可以说，想明白了”共享对象“后才真正感觉设计掌握在自己手中。对于outPassengers，可以采用”读者-写者“模式优化。

感觉对比往年作业，今年弱化了调度、强调多线程设计的正确性。为什么这么说呢？因为既没有要求多策略切换，请求集合也没有贴近现实场景的”特征“（也许数据有，但题目中从未提及），实在很难找到某种调度策略应对如此随机和针对性的数据（就好像分支预测永远失败的CPU） ，看似摆烂的自由竞争成为挺不错的选择。在”调度优化“和”多线程设计“两种培养目标的权衡之间，至少我觉得重点放在”多线程设计“体验还不错。