第二单元总结

• 第二单元总结
  • 1. 作业分析
  • 2. 架构设计
    • 2.1 请求拆分的流水线架构
    • 2.2 电梯类与控制器类的协作
    • 2.3 面向可扩展性的设计
  • 3. 线程安全与线程协同
    • 3.1 线程安全
    • 3.2 线程协同
  • 4. 调度器
    • 4.1 纵向电梯调度方案
    • 4.2 横向电梯调度方案
    • 4.3 请求拆分策略
  • 5. bug分析
    • 5.1 锁占用过多
    • 5.2 死锁
  • 6. 测试
  • 7. 心得体会
    • 7.1 关于软件开发
    • 7.2 关于形式化工具
    • 7.3 关于OOP

1. 作业分析

模拟多线程实时电梯系统，支持换乘。

2. 架构设计

对每个楼层、每个楼座单独构建一个等待队列（PassengerGroup的实例），5个座、10层，共构建15个等待队列。每个等待队列负责该楼层或楼座的全部乘客，该楼层或楼座的所有电梯共享一个等待队列。

Controller是电梯内部的控制，用于控制电梯的全部行为，调度策略也包含其中。电梯每执行一部操作后，均询问电梯所持有的Controller实例，Controller实例向电梯发送指令，之后电梯按照指令进行工作。不同类型的电梯将拥有Controller不同子类的实例，通过继承Controller可新增电梯类型或调度策略。

InstructionListener表示电梯的按钮，即请求的输入端口，是一个线程。它将请求输入给电梯系统总控制器SystemCtrl，用于控制每个乘客所乘坐的电梯、换乘、以及电梯系统的终止。

类图如下：

2.1 请求拆分的流水线架构

在第7次作业中使用了流水线架构。对于一个乘客，在他按下电梯按钮时，InstructionListener将收到其请求，将该乘客的请求发送给系统控制器SystemCtrl。系统控制器接下来的工作为：

1. 将请求拆分成若干个简单请求（无需换乘的请求）
2. 将该乘客的第一个简单请求分发给对应的等待队列
3. 该简单请求执行完毕，乘客下电梯时，该乘客的信息发回系统控制器，系统控制器将下一个简单请求分发给其对应的等待队列中
4. 不断重复3，直到请求输入结束

2.2 电梯类与控制器类的协作

电梯在进行一部操作后，都要询问Controller实例下一步操作。因此，我们需要找到一种电梯类Eleavtor与策略类Controller间协作、通讯方式，需要让这两种类型的对象间可传递“电梯行为”的信息。

首先将电梯的行为分成以下6个：

1. Open
2. Close
3. GetOn
4. GetOff
5. Move
6. WaitOnQueue

受第一单元启发，我首先尝试使用构造范式的方法来对“电梯行为”进行规范。虽然上面只列出了6种行为，但是有些行为需要有一些参数。例如，Move操作需要指明移动方向。GetOn操作需要指明上电梯的乘客。因此，构造一个范式较为困难。

因此，我构造了一个Movement接口，为每种不同操作单独构造一个类，并实现Movement接口，使用Movement实例来表示一次电梯的操作。

在Movement接口中，定义了execute方法，电梯每次调用Controller实例的nextMovement方法，该方法返回一个实现了Movement接口的实例，电梯调用返回的实例的execute方法来执行该操作。即，电梯线程的行为可大致描述如下：

for (;;) {
    if (/* condition */) {
        break;
    }
    controller.nextMovement().execute();
}
return;

2.3 面向可扩展性的设计

在上面介绍的对象协作方法中可以看出，对于这种架构，新增一种电梯操作是非常简单的，只需要为新增的电梯操作编写一个类，并实现Movement接口即可。不过这种可扩展性好像用不出大，因为电梯除了开关门，上下乘客，移动之外，也不会有什么其他操作了，否则它就不是实际意义上的电梯了。不过，使用实例进行信息传输的这种方式仍可在命令种类较多，且可能新增时还是有一些意义的。

另外，Controller是一个抽象类，可以被多种调度策略、电梯类型所继承，也有很高的可扩展性。

3. 线程安全与线程协同

3.1 线程安全

本次作业中，可以使用两种方法保证线程安全，一种是使用或开发线程安全类，另一种是访问共享对象时使用同步块。

可以将所有与线程相关的操作全部封装至同请求队列类中，即自己开发一个线程安全类，由该类保证访问时线程互斥，使用时无另作线程安全的处理。

本次作业中，需要保证“控制器一次决策+电梯对等待队列的一步操作”是原子操作。决策时需反复访问等待队列，以根据策略给出电梯下一步操作的指令。部分电梯操作也需要访问等待队列，如人员进出、等待。因此，在我的架构下，用第二种方法保证线程安全更好。若使用自己开发线程安全类的方法，则需要将上述的“决策+操作”这一原子操作封装至等待队列中，这与我的架构是不符的。

由于进行原子操作时，线程会持有锁，因此sleep务必不能再原子操作内部（详见bug分析部分）。因此，我将电梯的操作分为两部分：
不需要锁的操作：

1. Open
2. Close
3. Move

需要锁的草走：

1. WaitOnQueue
2. GetOn
3. GetOff

对于需要锁的操作，将其与nextMovement放在一个同步块中，以保证电梯的操作+决策是原子操作。下面是电梯类的run方法的部分代码。由于movement是一个不可变对象，因此两次调用movement.needLock()的结果一定相同。

for (;;) {
    synchronized (waitQueue) {
        if (waitQueue.getEnd() && waitQueue.getSize() == 0 &&
                passengers.getSize() == 0 &&
                !controller.getStatus().equals(ElevatorStatus.OPENED) &&
                !controller.getStatus().equals(ElevatorStatus.GETOFFED) &&
                !controller.getStatus().equals(ElevatorStatus.GETONED)) {
            return;
        }

        movement = controller.nextMovement(this);
        if (movement.needLock()) {
            movement.execute();
        }
    }
    if (!movement.needLock()) {
        movement.execute();
    }
}

3.2 线程协同

在三次作业中，我都使用了生产者-消费者模式。该模式的精髓是在生产者、消费者间新增一个中间类暂存数据，解决了生产者和消费者吞吐速度不匹配的问题。 该设计模式也给实现上带来了很多便利，只需保证中间类（即本单元中的等待队列）的线程安全即可。

第三次作业中，我使用了实验课中用到的流水线模式，使用单例模式的SystemCtrl类对整个电梯系统的请求进行控制。在每一个简单请求执行完毕后（即人员下电梯后），调用SystemCtrl类中的addRequest方法，将该乘客的下一个简单请求投入对应的等待队列中。详见UML协作图：

4. 调度器

4.1 纵向电梯调度方案

纵向电梯的调度使用look策略。look策略将尽量减少电梯换向次数，只捎带和电梯运动方向相同的乘客，这种乘客不存在时更换方向。宏观看来，look策略就是让电梯不断在低层和高层间移动。一开始从底层像高层移动，捎带全部向上的请求。在所有向上的请求处理结束之后，电梯折返，从高层向低层运动，捎带全部向下的请求。

为了实现look策略，纵向电梯控制器中需要维护当前电梯的运行方向。在每次捎带决策时，需要根据当前电梯运行方向进行判断。

4.2 横向电梯调度方案

由于只有5个楼座，而且在第六次作业中横向电梯速度较快，因此对横向电梯设计最优调度方案的投入产出比较低。因此我使用了较为简单的调度策略：

• 电梯内随机固定一个乘客的请求为主请求，该乘客下电梯后重新确定主请求
• 主请求存在时，按照主请求的最优移动方向移动
• 主请求不存在，且该层有待处理请求时，生成一个随机的移动方向
• 主请求不存在，且该层没有待处理请求时，就地等待

4.3 请求拆分策略

在第七次作业中，请求的起点和终点可能位于不同楼座、楼层，因此需要将请求拆分成若干个简单请求，分配给不同楼层或楼座的等待队列。请求拆分的方式主要有两种：

1. 使用最短路算法，构造出最优的请求拆分方案
2. 使用基准策略，只寻找一个中转楼层进行中转，一个请求最多拆分成三个简单请求

若使用最短路算法，难点之一在于路径权值的动态更新。显然，权值与当前时刻该路径上的电梯数量、承载量、排队人数、电梯内人数、电梯速度等都有关系，这些影响因素有些是可以事先确定的（例如电梯速度、电梯承载量），但有些是会动态变化的。这给这种请求拆分方法带来了不小困难，因此我没有采用。

我是用了第二种方法，即基准策略。在选择中转楼层时，有时若干个“距离”相同的中转楼层，这时我随机选择一个，以保证人员分配较为平均。

5. bug分析

第一次作业由于没有进行足够的测试，调度方案出现了一个巨大bug，即在电梯人数已满后，无法及时换向，导致电梯一直向某一个方向移动。修复时，在调度器的状态转移逻辑中增加一个判断即可。下面列出在测试和互测中发现的几个有趣的问题。

5.1 锁占用过多

上面已经提到，一次nextMovement的调用（即一次决策），和需要访问等待队列的操作执行需要同步进行。然而，有些操作的执行过程中需要延时，即调用sleep方法，若将该函数放在同步块中，会导致某线程执行延时操作时，一直占用着其所在楼层或楼座的等待队列，其他电梯线程无法访问，输入线程也无法向其投放请求。由于延时时长远大于程序其他部分的运行时长，若运行了这种错误代码，看上去的效果是输入线程卡顿明显，每次只能输入一两个乘客的请求。

为了解决这个问题，必须要将sleep方法放在同步块之外。由于我的整体架构中，Elevator和Controller仅通过nextMovement方法返回的实现了Movement接口的实例进行通讯，具体执行逻辑封装在了Movement类内部的execute方法中，sleep方法的调用也包含在内，因此为了避免电梯线程长时间占用等待队列的锁，需要将controller.nextMovement().execute()放在同步块外。可是，为了保证执行与决策相匹配，决策和执行又必须处于同步块内步。程序的设计仿佛进入了瓶颈，以nextMovement方法为特点的这种架构可能需要修改，将延时操作从execute方法中分开。

幸运的是，通过进一步分析可以发现，每种电梯操作要么有延时、要么访问等待队列，两者不会共存：

因此，我只需要在所有的Movement子类中增加一个属性needLock，以表示其是否需要使用等待队列的锁。在执行时判断movement.needLock，若需要锁则放在同步块内执行，否则在外部执行。

但是，这种方案仅仅对于延时和访问等待队列不同时出现时奏效，更好的方法是在所有Movement的子类中增加waitTime属性，每次调用nextMovement后，记录当前操作的waitTime，在同步块内执行execute，退出同步块后延时waitTime。

5.2 死锁

在测试时，我发现我的程序在某些情况下无法正常退出。经过分析，是发生了死锁。

发生死锁时，电梯线程的退出条件是：

1. 电梯位于可退出状态（已关门，无人在电梯内等）
2. 等待队列为空
3. 系统控制器SystemCtrl的结束标签为true

问题出现在条件3上。系统控制器SystemCtrl的结束标签设置是由GetOff指令完成的，而GetOff指令需要
访问等待队列。由于系统控制器SystemCtrl是单例模式的，因此该实例的isEnd属性的访问需要保证线程互斥，将getEndTag和setEndTag设置成了同步方法。因此，若一个电梯获取了等待队列的锁，在执行GetOff指令后要将系统控制器SystemCtrl的标签设置为true，此时就导致了死锁。

为了解决这个问题，只需要将电梯线程推出条件删除等待队列为空，直接判断系统控制器的结束标签，并且使用实验课中的方法，增加RequestCounter，即可解除死锁。

6. 测试

吸取了第一次作业大翻车的教训，在后两次作业中，基于Arthuring同学为第一次作业编写的评测脚本，我们一同对其进行了迭代开发，最终的评测脚本支持了多文件、单次生成、多进程评测。下图是评测脚本的部分输出信息，以及合作开发记录。

为了提升测试数据的覆盖率，我们对数据的构造工作进行了整体规划。与第一单元不同的是，本单元需要针对线程安全进行一些数据的构造。我们的测试数据中，也因此增加了HighConcurrency一类数据，用于测试大量人员同时出现在等待队列中，以及大量电梯同时竞争少数乘客的测试集。

以下是部分测试样例的文件树：

|-
|-Multi
│  |-Horizontal
│  │  |─DifferentDirection
│  │  |─HighConcurrency
│  │  |─MorePassenger
│  │  |─OnePassenger
│  │  \─Stop
│  \─Vertical
│      \─High
-MultiElevatorInfo
│  |─Horizontal
│  │  |─cap
│  │  |─openPosition
│  │  \─speed
│  \─Vertical
│      |─cap
│      \─speed
|─Single
│  |─Horizontal
│  │  |─DifferentDirection
│  │  |─High_concurrency
│  │  \─longWait
│  \─Vertical
│      \─hack
\─Transfer
    |─LessTransferElevators
    │  \─ManyPassengers
    \─MoreTransferElevators
       \─ManyPassengers

最终我们共构造92个测试点，可在10分钟内生成并测试完毕。

7. 心得体会

7.1 关于软件开发

软件开发中合作是很重要的。本单元的测试工具和方案由我和龚悦同学合作完成，合作过程中，我有以下体会：

1. 合作者要及时知晓进度，避免重复工作
2. 要做好版本管理，细心处理合并冲突，方便交流和追溯
3. 分工时要尽量将任务解耦，减少相互依赖的情况
4. 每个人要分别完成自己负责部分的测试，因为对某部分最了解的人是作者本人

在此要特别感谢龚悦同学，没有她的合作，我们的测试工具和数据就不能达到现在的完善程度。

7.2 关于形式化工具

形式化程度较高的工具是一把双刃剑。形式化工具保证的是实现和设计的一致性。一方面，它可以大大简化实现，但另一方面，它对设计提出了更高的要求。在实现复杂度和设计复杂度之间，开发人员需要进行trade-off。

以本单元为例，可以完全使用状态机进行调度方案的设计，此时程序的实现难度非常小，可直接使用switch语句进行实现。但是，状态转移间的条件会比较复杂，而转移条件时设计的工作，因此这种方法的设计难度较高。

在上一个单元中，可以使用正则表达式对输入字符串进行解析，这也是一种形式化的工具。这种方法的实现难度更低，只需输入正则表达式即可，但给设计带来了极大的困难。设计者必须对表达式的每种情况都进行考虑，才能写出正确的正则表达式。

形式化工具，不仅对开发是双刃剑，对于程序的测试工作而言，也是有利有弊。某些形式化工具给测试带来了遍历，例如本单元使用状态机进行调度方案设计，我们只需要形式化地证明我们构造的状态机是正确的（即符合一系列限制），即可保证我们程序正确。然而，在第一单元中，由于正则表达式可读性极差，基于 设计 的测试就变得非常复杂。

7.3 关于OOP

在第一单元中，我体会到面向对象思想的优势之一在于程序员可以直接站在实际问题的角度进行编程，只需对真实世界进行抽象、规范，而无需进一步转化为计算机角度的抽象。由于真实世界中问题的复杂程度非常高，各种过程会穿插交错，因此必须使用层次建模方法，将实际问题划分层次，进一步抽象后编写代码。

真实世界中，问题的复杂性体现在逻辑和时序两个维度上，多线程的程序设计自然迎合了实际问题对时序的要求。真实世界中经常会出现需要互斥访问的情况，人们所说的“一心二用”便是在描述没有保证多个事务互斥进行的后果。在编写多线程程序时，为了保证时序的正确，我们往往需要付出更多的努力，例如使用同步块保证互斥访问等。这些额外的努力，也是实际问题中所不能避免的。

使用多线程进行编程，一方面可以利用任务并行提高程序性能，另一方面是保持程序与真实问题的一致性。

因此，我们通常需要将真实问题中，同时发生、同时进行的模块抽象成单独的类，让这些类作为线程在计算机中运行。本次作业中，电梯和输入时同时发生的，人员的到来和电梯的运转时共同发生的事件，因此我们将输入单独作为一个类，每个电梯单独作为一个类，并使用它们启动线程。