BUAA_OO第二单元总结

锁与同步块

第一次作业

我设计了两个共享类：WaitQueue和ProcessMap。

WaitQueue被InputThread和Scheduler共享：InputThread作为读入线程，从标准输入获取PersonRequest，然后将其送入WaitQueue队列；Scheduler作为调度线程，从WaitQueue获取PersonRequest，然后将其送入电梯等待队列ProcessMap（调度器的设置在第一次作业中并无太大作用，主要为了后续作业中的拓展）。WaitQueue的锁我就选择了它本身，每次在InputThread线程要往WaitQueue里加入PersonRequest或者Scheduler要从WaitQueue里取出PersonRequest，我都会锁住WaitQueue，进行线程同步。

ProcessMap被Scheduler和Elevator共享：Scheduler作为调度线程，往ProcessMap里加入PersonRequest，为电梯提供等待人；Elevator作为电梯线程，对ProcessMap的操作有两个：①通过读取ProcessMap里等待人状况进行判断上行、下行等操作。②从ProcessMap中获得等待人，放入电梯内设置的passengers。ProcessMap的锁我也选择了它本身，每当Scheduler线程往ProcessMap里加入PersonRequest或者Elevator根据ProcessMap进行判断和获取等待人的时候，我会锁住ProcessMap，进行线程同步。

第二次作业

因为第一次作业设计具有良好的拓展性，我在第二次作业中仅仅增加了Scheduler线程的功能。由于Scheduler线程需要通过访问各个电梯的情况再进行分发乘客，所以我在这次作业中增加了共享对象Elevator（此Elevator与第一次作业中的不一样，仅仅是类，不是线程）。

（WaitQueue和ProcessMap与第一次作业基本一致）

Elevator被Scheduler和ElevatorManagement共享。Scheduler线程通过访问Elevator获取电梯的现在状态，然后进行乘客分发；ElevatorManagement用来管理Elevator，通过访问ProcessMap计算出目的层数，然后对电梯进行上行、下行等操作。锁与同步块，我选择了对象本身。我将Elevator设置为线程安全类（所有的synchronized都放在了Elevator类里面）。

第三次作业

第三次作业中，我设计了三个的共享类：WaitQueue、Elevator、RecycleQueue。

WaitQueue被InputThread、Scheduler和RecycleThread共享。InputThread对WaitQueue的访问与第一次作业中基本一致；Scheduler线程从WaitQueue中获得乘客，判断乘客是否到达乘客目的楼层，如到达则不进行分配，否则进行分配；RecycleThread线程主要将RecycleQueue中的乘客送回WaitQueue ，让Scheduler线程判断乘客是否到达目的地。

Elevator的共享情况与第二次作业中基本一致。

RecycleQueue被Scheduler和RecycleThread共享。Scheduler线程需要通过访问判断RecycleQueue是否为空进行线程结束；RecycleThread负责将RecycleQueue中的Person一直转移到WaitQueue。我将其设置为了线程安全类。（顺带一提，RecycleQueue我设置为了守护线程（其他线程结束，此线程才结束，避免产生“哲学家进餐问题”的死锁））

在锁与同步块这方面，我出现了一个比较大的问题：ElevatorManagement在管理电梯的时候：一开始的设计中，我在管理电梯的过程把Elevator锁了起来（即sleep的时间也不放开锁），导致Scheduler访问电梯的状态出现了延迟，导致分发乘客不及时，电梯出现了多次折返，系统运行时间增加了很多。后来的设计，我只锁住了对Elevator属性进行操作的过程（即sleep过程不锁，楼层加一或减一的时候锁起来），这样子更加方便Scheduler的及时调度。

调度器设计

第一次作业

第一次只有一部电梯，Scheduler仅仅将乘客从WaitQueue转移至ProcessMap。

第二次作业

第二次作业中，Scheduler分配的主要思想是将被分配乘客分配至与被分配乘客相匹配并且等待乘客数量最少的电梯，若不存在这样的电梯，那么将其分配至等待乘客最少的电梯。

乘客与电梯相匹配有以下情况（电梯有两个boolean变量表示其四个状态）：

电梯	乘客
wait:true up:true	上行乘客
wait:true up:false	下行乘客
wait:false up:true	上行乘客且Fromdoor大于等于电梯的floor
wait:false up:false	下行乘客且Fromdoor小于等于电梯的floor

第三次作业

第三次作业中，Scheduler分配的主要思想是将被分配乘客分配至与与被分配乘客相匹配并且等待乘客数量最少（若等待乘客数量相同，则将其分配至优先级最高的电梯【优先级:C>B>A】）的电梯。

在介绍乘客与电梯相匹配的情况前，先介绍一下三类电梯乘客目的楼层的计算方法

电梯种类	计算方法
A类电梯	①若乘客Fromfloor为奇数且Tofloor和Fromfloor的差值大于10，则目的楼层为最近的技术楼层。②其他情况为Tofloor。
B类电梯	①Tofloor为奇数，目的楼层为Tofloor。②Tofloor为偶数，目的楼层为Tofloor±1（具体看乘客上行还是下行）。
C类电梯	①若Tofloor在1到3或者18到20，目的楼层为Tofloor。②其他情况，目的楼层为3或者18（最近的那层）。

基于以上的计算方法，介绍乘客与电梯相匹配的情况（以上计算方法记为AToFloor、BToFloor、CToFloor）。【图表中的①②为满足其一即可】

电梯	乘客
A类电梯	任何
B类电梯	出发楼层为奇数 并且 ①目的楼层为奇数②BToFloor和出发楼层差值大于等于5
C类电梯	出发楼层在1到3或者18到20 并且 ①目的楼层在1到3或者18到20②CToFloor与出发楼层大于等于10且CToFloor与乘客目的楼层差值小于等于2.

架构设计

第一次作业

UML类图与UML协作图

架构设计

第一次作业架构比较简单，如上图我觉得就可以说明整个流程了。

我主要介绍一下我的电梯状态转移和运行策略（电梯运行采取一步一步进行【即根据情况，上行一层、下行一层或开门，然后再进行判断下一次的运行】）：

电梯状态	即将接送的乘客
wait:true	最低层上行乘客或者最高层下行乘客（离电梯近的优先）
wait:false up:true	出发楼层大于等于电梯所在楼层的上行乘客或者电梯内的乘客（同样离电梯近的优先）
wait:false up:down	出发楼层小于等于电梯所在楼层的下行乘客或者电梯内的乘客（与前者一样）

第二次作业

UML类图与UML协作图

架构设计

第二次作业主要对Scheduler进行了重新设计，使得其可以通过访问电梯的状态获得与乘客匹配的电梯序列，随后将乘客放入人数最少的电梯中。此外，我还将运行电梯和电梯的存储属性分开，方便管理。

在完成此次作业之后，我发现ProcessMap（存放电梯即将接送的乘客序列）这个类是有点多余的，我可以将其放入Elevator这个类里面，在后续的换乘设计中方便管理。

第三次作业

UML类图与UML协作图

架构设计

最后一次作业对第二次作业的问题进行了处理，将电梯即将接送的乘客序列放入了Elevator这个类里面，并且对调度器进行了重新设计（上面已经介绍过了）。

这里主要介绍换乘的设计：

首先我增加了一个继承PersonRequest的类：Person，增加了两个属性出发楼层和目的楼层（下面使用Fromdoor和Todoor表述原有属性）。出发楼层记录了乘客的出发层（ElevatorManagement线程在将到达目的楼层的乘客其扔进RecycleQueue时，会将乘客的出发楼层改为电梯所在楼层），目的楼层记录了电梯要将乘客送至的楼层。

其次我在Scheduler线程中增加了一个TreeMap，它记录仍在这个系统中未到达Todoor的乘客。每当Scheduler线程进行分配乘客时，会先判断其出发楼层是否与Todoor相等，若相等则在TreeMap中取出此乘客，否则将此乘客继续分配。这样的设计可以非常优雅地判断Scheduler线程是否需要结束，结束条件：WaitQueue结束 && WaitQueue空 && TreeMap空 && RecycleQueue空。

我在这样的设计时出现了一个问题：形成“环”的线程容易设计成死锁。因此，我将流程比较简单的RecycleThread线程设置成了守护线程（只需不停地将RecycleQueue中的乘客扔回WaitQueue），这样子就避免了环形“哲学家进餐问题”。

BUG分析

这三次作业在强测和互测中并没有发现bug。

HACK策略

这一单元中，我并没有成功hack，但在第三次作业中，我主要尝试了n个乘客从4楼到20楼的较为极端数据测试，但没有成功。

心得体会

这三次作业，我主要觉得第一次作业时多线程入门比较难，后面的两次作业只需增加功能和改变设计即可。

总体来说，我觉得我的三次作业核心就是“生产者-消费者”模型，在生产者和消费者之间增加一个作为中转站的分配器。此外，让我收获颇丰（与舍友讨论了挺久）的是第三次作业中对换乘的处理：用一个Treemap对乘客进行记录，若到达，则将乘客id从Treemap中remove掉，否则则更新；电梯每次送完乘客，都会将乘客扔进RecycleQueue，通过守护线程将其扔回待分配队列中。这个设计大概是除了多线程另一个让我收获颇丰的地方。

通过这个单元的训练，我对多线程有了更深入的理解，掌握了线程间同步、互斥的方法，保证线程的安全性，设计架构的能力也有了不小的提升，希望在以后的OO学习中收获更多的知识和技巧。