BUAA OO UNIT2

(1)总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句直接的关系

在本次作业中，我通过共享 乘客队列 的方式来进行线程间的通信。

为了保证线程安全，在每次访问共享的变量时，都会通过 synchronized 关键字来进行同步控制。（为了安全起见，我没有使用不熟悉的 lock）

为了减小单个线程对共享变量的占用时间，我没有采用在方法前加 synchronized 关键字的方法，而是全部使用了临界区的方法，从而减小了临界区的大小，使得并发效率提高（但是也造成了一些的编程上的困难）

此外，对于共享的队列，只有调度器一个写者，队列又分为公共队列和私有队列，公共队列由所有电梯共享，所以调度器会采用 notifyAll 的方法唤醒所有电梯，让各个电梯去争抢乘客。对私有队列，只需要用 notify 唤醒对应的电梯即可。

同步块中的处理语句应该尽量都是访问临近资源的语句或在执行时共享变量不应发生变换的语句。

在保证正确性的前提下，尽量减小临界区大小可以提高程序并发访问的效率。

(2)总结分析三次作业中的调度器设计，并分析调度器如何与程序中的线程进行交互

第一次作业

第一次作业中，我的调度器基本上是一个“摆设”，由于只有一个电梯，所以调度器只负责从输入线程中将 request 传递给电梯，只起到了倒手的功能，具体的接送乘客的策略，由电梯自己决定。

调度器与电梯线程的交互方式为通过共享变量 WaitQueue 进行数据共享。

第二次作业

第二次作业有了多部电梯，调度器的重要性得到了凸显。

我对不同模式的设定是这样的：

对 Morning 模式 和 Night 模式，我选择让调度器将任务分到具体的电梯，防止因为电梯间的争抢而产生内耗。

具体的分配策略是：

对 Night 模式，现将任务按前往楼层按从高到低排序再依次派发，对 Morning 模式，按照任务的到达时间来排序。具体分配时的顺序是 1,2,3,3,2,1 这样可以防止先出发的电梯因为楼层高而积攒任务，成为性能的瓶颈。

对 Random 模式，我将所有任务都加入公共队列，并通知所有电梯，让电梯们进行自由争抢，这样可以保证接到乘客的电梯是离乘客最近的，在一定程度上保证了运行的效率。

第三次作业

第三次作业中，我只在 morning 模式采用了换乘机制。即当 B 或 C 类电梯接到乘客时，会将乘客送到目标附近的可达楼层，在由处于 Random 模式的 A 类电梯进行最后的运送。

对 Night 模式和 Random 模式，我采用了类似于第二次作业的算法，区别是每部电梯只接收不需换乘就可完成的任务。（其实我本来是写了换乘算法的，但是经常出现一个人反复进入同一个电梯的 bug，在解决了上述 bug 后又产生了电梯 wait 没有被唤醒的 bug，所以我删除了换乘的算法）

(3)从功能设计与性能设计的平衡方面，分析和总结自己第三次作业架构设计的可扩展性

• 第三次作业的UML类图如下：

  

  可以看到，我建立了名为 Elevator 的抽象类来统一管理各个电梯（但是由于不能使用 protected 类型的变量，为方便起见，我将很多本来应该在抽象类中的属性下放到了各种电梯中。

  此外，还有输入线程 InputThread 负责将输入传递给 调度器线程 Scheduler，Scheduler 又会将任务传递给相应的电梯，由电梯来处理指令。

  传递指令的方式是通过 WaitQueue 类，其中封装了很多搜索满足一定条件（如从某个楼层出发，向上走或向下走，到达楼层在某个范围内等等）的指令的方法。

  电梯由调度器创造并管理，主线程中只创造输入线程和调度器线程。

   

• 画UML协作图(sequence diagram)来展示线程之间的协作关系（别忘记主线程）:

  主线程：

• 

  可以看到，main 线程只创造了 InputThread & Scheduler 两个线程，和用于这两个线程通信的 Requests

  InputThread：

  

  这个线程任务简单，只负责将接受到的输入传给调度器。

  Scheduler：

  

  可以看到，这个线程明显复杂了许多，因为它负责了所有请求的接收和分发。 Scheduler 的功能主要有：

  1. 创建初始的 3 部电梯

  2. 在接受到电梯指令时，根据指令内容创建电梯。

  3. 接受到人员请求时，将人分发到对应的电梯的等待队列中。

  电梯线程（以 B 类为例）：

  

  由于对人员上下电梯和换乘的策略都由电梯来决定，所以电梯的方法很多，逻辑较复杂。 但是，电梯所有的指令都是从 WaitQueue 中得到的，这在很大程度上保证了线程的安全。

可拓展性：

我认为我的第三次作业可以从以下两个方向进行拓展和优化：

1. 调度器层面：

   为了达到尽可能优秀的性能，可以考虑在每个请求到达时，读取各个电梯的所在楼层和运行方向，构造各个楼层之间的带权连通图，通过 Dijkstra 算法计算出耗时最短的运人策略，将请求拆分，发送给对应的电梯进行处理。

   为此，需要给被拆分出来的任务加上一个标记，保证执行的顺序不出现错乱。

2. 电梯层面：

   由于时间的限制，我只在 Morning 模式中实现了换乘，所以一个可能的优化方向就是在另外两个模式中也实现换乘。

   目前我想到的一个相对可靠的方案就是，在编程前先通过图论算法计算出一个相对优越的静态换乘表，让各部电梯按照换乘表所示进行人员的接、送。

    

(4)分析自己程序的bug

• 分析未通过的公测用例和被互测发现的bug：特征、问题所在的类和方法

• 特别注意分析那些与线程安全相关的问题（特别要注意死锁的分析）

第一次作业：

在第一次作业中，我的程序陷入了死循环。陷入死循环的原因是： 在我的代码逻辑中，电梯一次向上或向下的路程中，只会在电梯内人员清空的前提下回头。这本来是没有问题的，因为电梯只会捎带同方向的人，但是由于我的失误，在电梯要上乘客的楼层，我忘记了同时判断是否有人要下电梯。这导致如果有人要在这层下电梯，他会被困死在电梯中，而电梯会一直向上/下行进，无法停止。

修正方式： 在接乘客时先判断是否有人要下电梯，再接乘客（这样还能防止“伪满员”的现象）

第二次作业：

本次作业中未发现 bug

第三次作业：

第三次作业的 bug 比较愚蠢，是由于在设定判断电梯是否满员时，B 类和 C 类 误把 >= 写作了 >，导致电梯超员。

总结

三次作业中都没有出现线程相关的 bug。取而代之的是，发生了多次由于粗心导致的 bug。 在今后的作业中，还应该更加细心，多做测试。

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

• 列出自己所采取的测试策略及有效性

  由于本次作业的侧重点在 “多线程” 上，所以我的测试手段也主要集中于多线程。 测试时，样例方面，我采用了 python 随机生成的样例，而由于测试输出正确性较难判断，所以我只判断了程序是否能正常结束（即是否发生了死锁或 wait 未被唤醒等 bug）

• 分析自己采用了什么策略来发现线程安全相关的问题

  为了更加有效的测试线程安全相关的 bug，我选择同时运行几十到几百个测试程序，增加处理器负担，模拟测评机的行为。

• 分析本单元的测试策略与第一单元测试策略的差异之处

  本次作业的测试和第一单元的主要区别在于，本次作业的测试更加看重线程安全，而不是输出的正确与否。所以采用的样例和测试程序的数量应该不同。 相同点在于，都可以使用自动化的程序来生成测试数据并运行测试程序。

   

(6) 心得体会

• 从线程安全和层次化设计两个方面来梳理自己在本单元三次作业中获得的心得体会

1. 线程安全

   通过本次作业，我初步了解了 java 的多线程使用方法以及保证多线程安全的几种常用方法。

   为了保证线程安全，我基本上仿照了实验课中提供的生产者——消费者模式来架构我的程序，在这个过程中我了解到了符合某种设计范式的重要性。

   对于死锁的防范，使我处处小心，最终，终于没有在线程安全方面出现问题 (却在阴沟里翻了船) ，以后在设计程序式还要在各个方面都多加小心，万万不可顾此失彼

2. 性能与设计风格

   在这次作业中还有大量关于性能和设计风格的权衡。 在这几次作业中，每当这两者发生冲突，我都会选择采用更优的设计风格，而不是更优的性能。这样可以在最大程度上减少 bug 出现的概率。

   关于层次化设计，坦言，本次我的作业的层次化设计并不是很好。更好的方式应该是将判断电梯接送哪个人员的策略做成一个策略类，电梯只选择策略类即可。

3. 遗憾与待改进之处

   这次作业的一个遗憾就是没有把电梯调度策略单独作为一个类封装起来，而是都堆在了电梯类中，造成了电梯类复杂，不美观。 根据 dalao 们的反应，如果把电梯当做一个单纯的状态机，而让其中填写的策略类来决定状态转移的方式可以达到最优化的分层设计。

   其次就是本次作业中出现了大量由于粗心而失误的地方，在之后的作业中，必须多加小心，不可再出现类似将大于等于写成大于这样愚蠢的错误了。