OO Unit2 总结

OO课Unit2电梯仿真项目技术回顾

BUAA.1823.邓新宇

2020/4/17

从多线程的协同和同步控制方面，分析和总结自己三次作业的设计策略

第一次作业

关于共享资源，主要是单例模式的Building，其内部为每一个楼层建立一个Floor实例，分上行和下行保存正在该层等待电梯的乘客。

整体的逻辑分为三个部分：

1. 输入器，单独一个线程。
2. 控制器，单例模式，单独一个线程。有一个请求队列和一个等待队列，暂时无法处理的请求会添加到等待队列。
3. 电梯，单独一个线程。是控制器的子线程，由控制器控制电梯的启动和结束。

由于猜测到后续可能需要增加电梯数目，在设计控制器的时候，就考虑了多部电梯时的调度。总体分为2个部分：

1. 控制器从请求队列中以阻塞方式取出一个请求调度的电梯，通过电梯内部乘客信息和Building的信息判断电梯下一步动作，并设置电梯状态以告知电梯调度结果，唤醒电梯；若当前没有外部请求，电梯内部也无乘客，就将电梯加入电梯等待队列，此时不唤醒电梯。电梯获得新的状态后，先进行（或不进行）开门、上下乘客、关门，再进行上下转移。到达新的楼层后，电梯将自己添加到控制器的请求队列，并等待控制器设置新状态。
2. 输入器获得新的请求，创建Passenger对象，将其移交给Building，Building将该Passenger添加到正确的等待队列中，并通知控制器。控制器收到通知后，将所有等待队列中的电梯加入到请求队列。

这两个部分都是一个生产者-消费者模式。在第一部分中，电梯是生产者，控制器是消费者，电梯产生调度请求，控制器对这个请求进行响应。第二部分中，输入器是生产者，控制器和电梯是消费者，输入器产生乘客请求，控制器和电梯来处理这个请求（我不认为这是work thread模式，因为是电梯来决定具体处理哪些请求，而不是由控制器来决定的）。

关于程序的终止，输入器结束输入后，向控制器发送中断信号，控制器收到中断信号后，进入准备退出模式，此时如果等待队列中的电梯数量和电梯总数相等时，就会结束全部电梯线程，然后结束控制器线程。

电梯的控制器权在电梯线程和控制器线程间交替转移，在第一次作业中其实是完全可以不进行这种交替转移的，但是这样的交替转移可以应付电梯数量增加时的情形。

第二次作业

第二次作业中，主要是为电梯增加了对自己本身的控制。多数情况下，电梯的运行方向、是否开关门仅通过电梯本身的状态和Floor的状态就可以确定，这个时候就没必要请求外部进行调度了。也就是说，仅仅是电梯为空/电梯即将为空且当前楼层没有乘客的时候，才需要请求外部调用。此时，原先的控制器不再精细地控制每个电梯的每一步动作，所以将其更名为调度器。其余部分基本不变。

此时，主体逻辑变成如下两个部分：

1. 控制器从请求队列中以阻塞方式取出一个请求调度的电梯，通过电梯内部乘客信息和Building的信息判断电梯下一步动作，并设置电梯状态以告知电梯调度结果，唤醒电梯；若当前没有外部请求，电梯内部也无乘客，就将电梯加入电梯等待队列，此时不唤醒电梯。电梯获得新的状态后，先进行（或不进行）开门、上下乘客、关门，再进行上下转移，上下转移的过程中，通过目的楼层的Floor和电梯中乘客信息，设置本身的下一个状态。到达新的楼层后，电梯检查是否已经设置了新的状态，若已经有了新的状态，就继续开门、上下乘客、关门的循环，否则将自己添加到控制器的请求队列，并等待控制器设置新状态。
2. 输入器获得新的请求，创建Passenger对象，将其移交给Building，Building将该Passenger添加到正确的等待队列中，并通知控制器。控制器收到通知后，将所有等待队列中的电梯加入到请求队列。

仅仅是多了一步电梯的自调度。只需要获取电梯本身状态和某一Floor的状态时，进行电梯的自调度，当需要整个Building状态时，调度器进行调度。调度器每次调度都需要获取Building和所有Floor的锁，并且一次只能调度一个电梯的在某一层的行为，若电梯的所有行动前都需要调度器调度，将导致很大的开销，所以需要不需要Building信息的调度转移到电梯本身。

第三次作业

第三次作业依旧没有改动Building的结构，也没有改动输入器-乘客请求-调度器&电梯这个生产-消费者模式的内容。对于新增电梯这种请求，由于所有电梯线程都是调度器的子线程，所以这种请求的消费者应当是调度器，所以为电梯-调度请求-调度器这个生产者-消费者模式，添加了新的生产者——输入器。

此时调度器的运行方式变为：

• 以阻塞方式从请求队列获取一个请求，判断该请求时电梯调度请求还是电梯增加请求。对于电梯调度请求，通过Building和电梯信息进行调度；对于电梯增加请求，将该电梯的线程启动。

还有一个较小的改动是，当输入器通知调度器有新的乘客请求时，调度器只将可以到达该楼层的电梯从等待队列添加到请求队列中。

关于换乘的调度，通过为Passenger包装一个PassengerRequest（本段简称Request），Request有一个换乘策略Map，创建Request实例的时候，会利用当前楼层和乘客目标楼层信息查询换乘策略，进而确定当前的目标。

---

从功能设计和性能设计的平衡方面，更新和总结自己第三次作业架构设计的可扩展性

电梯设计

电梯部分我选择将电梯拆分为若干部分，分别控制电梯的不同功能：

类名

作用

控制器Controller

电梯自己进行运行方向决定、上下乘客控制

容器Container

管理乘客

门Door

开关门

电机Motor

管理楼层状态

而Elevator类基本上只是把这些部件组合在一起，Elevator的所有方法其实都是对不同部件的调用。

我没有选择通过继承的方式来区分ABC三种电梯，因为它们数据的结构和行为方式几乎是一样的，只是有些参数不相同。我将这些不相同的参数打包保存至ElevatorType中，这样，如果要增加仍旧是参数不同的新的电梯类型，只需要为ElevatorType增加新的成员即可。

把电梯的各个组件拆分，可以配合工厂模式，选配不同的控制器/容器/门/电机，进而可以增加更多类别更加不同的电梯，大大提高了扩展性。

信息传递结构

调度器、电梯的控制器都可能需要获得Building、Floor、Container的信息，而如果直接对这些实例进行查询，但是根据我观察，调度器和控制器所需要的信息大概是“去X层的请求有多少”、“都有去那些层的请求”、“X层是否有乘客请求”、“以X层为目的地的请求有多少”、“在X层下客之后还有多少空间”之类的，这些信息在楼层->人数或者类似的Map中查询和计算更为方便，但是Floor和Container都是通过一维的列表进行存储的（否则可能需要多加不少锁）。

于时如果要直接对Floor/Container/Building进行查询，每次不同的查询都需要重新进行一次遍历，而一次调度可能需要查询各类信息，所以会带来不小的损耗。

于是我通过辅助的信息载体类，即若干内部Info类进行传递信息，它在创建的时候，遍历外部类的容器，存储为更利于查询计算的形式，同时抛弃一些不必要的信息。调度器/控制器通过调用Floor/Building/Container的getInfo()方法获取Info对象，然后对Info对象调用getSpaceAfterPull()、hasTargetCompareTo()、isEmpty()、getNearestRequest()等方法就可以快速查询相关信息，并且查询的过程是在Info类内实现，一方面简化了调度器和控制器的计算，另一方面也让这一部分查询计算的过程得以封装。

调度策略优化和相关结构调整

换乘策略

换乘策略主要是在PassengerRequest类中实现。为了提高复用性，换乘策略通过(起始地, 总目的地)-> 小目的地的键-值对保存在一个Map实现的策略矩阵中，当创建PassengerReqest时，会查询该矩阵，并保存小目的地信息。

电梯和调度器进行上下客选择时，只关注小目的地即可。

当调用getOff()方法时，会判断是否到达总目的地，如果没到达，就会向Building中添加新的PassengerRequest。

当更改电梯的可到达楼层时，只需更改策略矩阵即可，扩展性比较高。

A型电梯的优化

观察三个电梯的可停靠楼层，我们可以发现两个现象：

1. A类型电梯，其可停靠楼层为最低的几层和最高的几层
2. 所有电梯都可以在F1、F5停靠

从第一点，我们可以知道，A类型电梯从低楼层到高楼层之前往复移动的代价是十分高昂的，而中间一部分又可以通过BC两类电梯进行换乘，所以可以通过如下策略提高性能：

• 当存在多部A型电梯时，一部分A型电梯只在低层运行，另一部分只在高层运行，即将A型改为A_LO或A_HI型，而低层到高层的运输，通过在F1和F15两次换乘来完成。

要实现这样的策略，需要在A型电梯数量从1变到2时进行两方面调整：

1. 原先的那一部A型电梯需要更改类型至A_LO或A_HI型
2. 所有的PassengerRequest需要更改目的地

先讲第二个方面，更改策略矩阵即可让新创建的PassengerReques获得新的换乘策略，但是旧的PassengerRequest的更改就有问题了，由于为了加快访问速度，创建PassengerRequest对象时，就查询换乘策略矩阵，保存目的信息，而非调用PassengerRequest对象的getTarget()方法时才查询，这就需要更新旧的PassengerRequest的数据。

最开始打算主动让每一个PassengerRequest刷新，但是这就需要获得每一个PassengerRequest的引用，可是旧的PassengerRequest分布在Floor、Elevator中，十分杂乱，如果要保证线程安全就需要挂起几乎全部线程；如果让每一个新建的PassengerRequest都添加到一个static的列表中，又带来删除的问题；更重要的是，会导致线程安全问题，又需要大量加锁。

所以采用了被动刷新，即更改策略矩阵后，调用getTarget()方法时进行刷新。需要增加两个标志位，一个static标志位needFresh，标志着策略矩阵已更改，一个实例对象内部的标志位freshed标志着本实例是否刷新过。当调用getTarget()方法时，当needFresh && ！freshed时就查询策略矩阵更新目的地。

而关于第一方面，由于更改类型的时机只有电梯本身才可以掌握，所以我选择让调度器通知电梯改变类型，电梯来决定合适更改类型、更改为A_LO还是A_HI型。我采用了如下策略：调度器收到添加第二个A型电梯的时候，为已经在运行的A型电梯发送请求，这个请求是一个单独的对象，然后更改PassengerRequest换乘策略矩阵并设置needFresh标志位，同时启动两个线程：

1. 等待请求完成，然后根据A型电梯更改后的类型，更改新的电梯的类型，并启动这个新电梯的线程。
2. 周期性检查原先的A型电梯是否在调度器的等待队列中，如果在，将其移动到请求队列中，当原先的A型电梯完成类型改变后结束这个线程。

这两个线程启动后调度器就可以继续处理下一个请求了，而不必等待A型电梯完成类型改变和新电梯添加完毕。当A电梯数量不低于2时，再添加新的A型电梯时，只需要启动1号线程即可。

这一部分更新的确增加了相关部分的耦合度，但是增加耦合度的地方也大多是直接涉及业务逻辑的，也不是不可以接受。关于电梯更改类型的请求，由于这个请求是一个抽象类，要求一个抽象方法来判断更改成何种类型的电梯，所以这一部分结构调整其实可以修改为任何电梯类型的更改策略，扩展性也不低。

---

基于度量分析自己的程序结构

statistic统计

文件名

总行数

代码行数

代码占比

注释行数

注释占比

空行数

空行占比

ElevatorDispatcher.java

316

264

0.835

28

0.089

24

0.076

ElevatorType.java

240

212

0.883

0

0.0

28

0.117

Elevator.java

222

183

0.824

5

0.0225

34

0.153

Container.java

198

163

0.823

10

0.051

25

0.126

Floor.java

181

154

0.851

8

0.044

19

0.105

PassengerRequest.java

158

138

0.873

1

0.006

19

0.120

Controller.java

182

134

0.736

30

0.164

18

0.099

Motor.java

109

98

0.899

0

0.0

11

0.101

Building.java

87

70

0.805

2

0.023

15

0.172

FloorNumber.java

81

70

0.864

0

0.0

11

0.136

FloorNumberMap.java

81

68

0.840

0

0.0

13

0.160

Tester.java

75

67

0.893

3

0.04

5

0.067

TargetInfo.java

77

66

0.857

0

0.0

11

0.143

Passenger.java

69

56

0.812

0

0.0

13

0.188

ElevatorID.java

63

53

0.841

0

0.0

10

0.159

TrafficInput.java

58

51

0.879

2

0.034

5

0.086

MainClass.java

49

46

0.939

0

0.0

3

0.061

DispacherRequest.java

51

42

0.824

0

0.0

9

0.176

UnorderedPair.java

47

39

0.830

0

0.0

8

0.170

Door.java

55

38

0.691

8

0.145

9

0.164

Logger.java

43

33

0.767

3

0.070

7

0.164

ElevatorFactory.java

31

27

0.871

0

0.0

4

0.129

TypeChangeRequest.java

26

20

0.769

0

0.0

6

0.231

ElevatorIsFullException.java

19

15

0.789

0

0.0

4

0.211

Total:

2518

2107

0.837

100

0.040

311

0.124

写的有点太多了，这导致两个问题：

1. 没时间写评测机
2. 到处都是一些小bug

看来以后确实要注意控制代码量。设计架构的时候，要设计简单实用一点。

而且注释写的不是很多，虽然通过很长的变量名和函数名使得看代码也很快能明白啥意思，但是还是注释更直观一些吧。学习一下javadoc注解也应该提上日程了。

matrics方法分析结果

matrics分析所有方法，基本复杂度≥4的方法如下：

方法

基本复杂度

设计复杂度

圈复杂度

traffic.building.ElevatorDispatcher.setStatus(Elevator)

8.0

10.0

10.0

traffic.building.elevator.Controller.checkNextStep(FloorNumber,Floor,TargetInfo)

5.0

10.0

10.0

traffic.building.Floor.passengersGetOn(Elevator,boolean)

5.0

5.0

8.0

traffic.building.Floor.hasNoRequest(List)

4.0

2.0

4.0

traffic.building.elevator.Motor.nextFloor(boolean)

4.0

4.0

4.0

null.preferToWaitAt(FloorNumber)

4.0

1.0

4.0

traffic.TrafficInput.run()

4.0

6.0

6.0

traffic.building.elevator.Motor.go(boolean)

4.0

7.0

8.0

traffic.building.FloorNumber.valueOf(int)

4.0

3.0

4.0

traffic.building.Floor.freshInfo(List)

4.0

3.0

4.0

Total

297.0

351.0

393.0

Average

1.332

1.574

1.762

前两个是调度器和控制器的核心方法，都是分析Floor/Building/Container的信息来为Elevator设定新的状态的方法，和Floor/Building/Container都有较高的耦合，三个复杂度都很高。

第三个passengersGetOn确实是比较纠结的点，一方面，每一层的乘客信息应当都是Floor进行管理的，passengersGetOn应当是Floor的方法，但另一方面，Floor应当只是一个容器，不应该承担这些逻辑控制工作。想了好久也没有更好的解决方案了。

matrics类分析结果

类名

平均圈复杂度

总圈复杂度

traffic.TrafficInput

3.0

6.0

traffic.building.ElevatorDispatcher

2.727

30.0

traffic.building.ElevatorDispatcher.AwakeUntilGet

2.5

5.0

traffic.building.Floor

2.375

19.0

traffic.building.elevator.Motor

2.375

19.0

traffic.building.PassengerRequest

1.923

25.0

traffic.building.elevator.Controller

1.909

21.0

traffic.tools.FloorNumberMap

1.9

19.0

traffic.building.Floor.Info

1.857

13.0

traffic.building.elevator.ElevatorType

1.818

40.0

traffic.building.elevator.Container

1.769

23.0

traffic.building.Building

1.6

8.0

traffic.building.elevator.ElevatorID

1.5

9.0

traffic.building.ElevatorDispatcher.ChangeToDoubleAMode

1.5

3.0

traffic.building.Building.Info

1.5

9.0

traffic.building.elevator.TargetInfo

1.375

11.0

traffic.building.FloorNumber

1.333

12.0

traffic.tools.UnorderedPair

1.333

8.0

traffic.building.DispacherRequest

1.333

8.0

traffic.tools.Tester

1.333

4.0

traffic.building.ElevatorDispatcher.AddNewA

1.25

5.0

traffic.building.Passenger

1.2

12.0

traffic.building.elevator.Elevator

1.129

35.0

traffic.building.elevator.Controller.Info

1.0

3.0

traffic.building.elevator.TypeChangeRequest

1.0

3.0

traffic.tools.Logger

1.0

4.0

traffic.building.elevator.ElevatorIsFullException

1.0

4.0

traffic.building.elevator.Container.Counter

1.0

8.0

traffic.building.elevator.Door

1.0

6.0

MainClass

1.0

1.0

traffic.building.elevator.ElevatorFactory

1.0

3.0

Total

376.0

Average

1.6

12.129

总体的复杂度控制的还不错。

总圈复杂度前三为：ElevatorType（40）、Elevator（35）、ElevtorDispatcher（30）

ElevatorType的总圈复杂度较高，但平均圈复杂度并不高，该类集合了A、B、C、A_HI、A_LO五种电梯类型的参数信息，还涉及A型电梯的优化，总圈复杂度高不出意料。

Elevator是一个组装类，自然和部件之间耦合较高。

调度器需要获取Building、Floor、Elevator信息进行综合判断，还承载着电梯线程的管理工作，这个圈复杂度确实不算高，甚至有点低出我的意料之外了。

总调度器和电梯的控制器的圈复杂度都不高，而它们其实都需要大量Floor/Building/Container类的信息，我觉得这应该归功于各个Info内部类（上一章节提到过）。

---

主要都是因为代码规模过于庞大导致的细节地方被忽略了。比如PassengerRequest的needFresh忘记置位之类的。

还出现过一个本地无法复现，提交后随机出现的bug，虽然很快就被我修复了。这个出现在第三次作业，增加了前文提到的A型电梯的优化后出现的。由于本身过程比较复杂，我将出现问题的一部分抽象出来：

class A {
    public void f() {
        /*     */
    }
}
public class B {
    private A a;
    private ExecutorService executor = Executors.newCachedThreadPool();

    private void go() {
        executor.submit(() => a.f());
    }

    public void g(A newA) {
        go();
        a = newA;
    }
}

关注class B，在该类的g()方法中，我本希望提交旧的a的f()作为新线程，然后更改a。在本地没有问题，但是提交后就会出现实际提交的是新的a的f()。这是因为go()中的lambda表达式，其实现方式其实是匿名内部类，意味着它是一个普通的内部类，它实现了Runnable接口，但是它是通过B.this.a获取的a对象，并没有a的副本，也就是说它获取的是运行时B中的字段a指向的对象，而不是go()函数调用时B中的a对象，那么B中a更改后，这个匿名内部类的a也会更改。

但是这有什么问题呢？问题就在于，确实是这个线程先被提交，后更改a，但是却无法保证这个线程先开始运行，后更改a。在本地测试的时候，由于我的PC资源比较充足，所以新的线程刚被提交就开始执行了，没有问题；但是评测机分配给我的程序的资源就没有那么充足，刚刚提交的线程可以没开始运行，a就先发生了改变。

怎么解决呢？我的方法是改写了go()方法：

private void go() {
    executor.submit(new Runnable() {
        private A a = B.this.a;

        @Override
        public void run() {
            a.f();
        }
    });
}

这样虽然还是匿名内部类，但是为它增加了a的副本这样的字段，这样，调用go()的时候会实例化这个匿名内部类，此时就会保存一份a的副本，这样在它被执行的时候，就会准确调用旧的a了。更好的方法应当是创建静态的内部类，这样可以节省一个B.this的字段的空间，但是这样的话代码不够简洁。

另外，我认为这样也许也是可行的，但是我没有进行过评测机那样的测试，不过在本地运行没有问题。

private void go() {
    A copy = a
    executor.submit(() => copy.f());
}

因为这样会强制Java为lambda表达式生成闭包时创建一份a的副本。

---

分析自己发现别人程序bug所采用的策略

由于没空写评测机，就只好挑一些边界条件。

第三次作业，与3层相关很容易出现bug，尤其是3层到2层的换乘。因为3层只有C电梯可以到达，而C只停留奇数层，所以3→2就不得不3→1→2或者3→5→2，3和2相邻却不得不换乘一次。

---

我到现在都不知道为啥不知不觉就写了那么多，也写了好多文件，停下来看一眼行数统计的时候就发现写的有点太多太复杂了。不过的确很多类都是几乎不需要再更改的，所以洋洋洒洒拆分了很多文件确实在寻找实现的时候很快。

这次作业写的时候思路确实有点乱，没有想清楚哪些是共享对象哪些不是，就开始写了。以后涉及多线程的时候，一定要先考虑清楚哪些是共享对象，哪些不是，有了清楚的规划，才能写出高内聚低耦合、简结高效的代码。