OO第二单元作业分析

前言

---

这一单元关于线程安全的作业结束了，在助教提供的接口的帮助以及老师提供的设计模型的指导下，这三次作业还是相对轻松地完成了，中间也没有出现什么bug，可能就是因为简单的逻辑不容易出错吧，可惜两次都由于性能分与a组失之交臂，或许在后续作业中还是应该多在性能优化下做一些工作。

---

第一次作业

---

设计思路

---

这次参考了老师所给的生产者消费者问题，主要设计了电梯类，控制器类，输入器类，主类，电梯类只负责向调度器请求指令，并根据接收到的指令进行上下楼接送人操作，输入器类只负责接受指令并向调度器塞入指令，控制器类负责按照时间顺序从输入器抓取指令，并发送给电梯，这里采用的是傻瓜算法，即做完一条指令再发送下一条指令。同时控制器类还负责电梯类的线程结束。这里让线程安全结束的方法是，输入器类只要接收到文件结尾就结束输入 器线程，并设置一个布尔变量作为输入结束的标志，当输入结束并没有指令继续存在时，电梯线程结束。

---

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

---

程序结构

---

正如设计思路中所说，采用生产者消费者模式：电梯作为消费者，输入器作为生产者，调度器作为托盘，就构成了整个程序的结构

---

度量分析

可以看到由于采用的是是简单的傻瓜调度，所以这个程序各个类之间的耦合度非常低，相对来说耦合高一点儿的只有调度器和电梯、调度器和输入器之间关于指令传输的方法。

---

其他

---

总的来说这次作业难度不大，主要精力花费在如何在各种输入条件下平稳结束各个进程，采取的方式如前文所说，通过设置表示输入结束以及表示指令队列为空的变量，作为break的条件，跳出while循环，从而结束线程

---

第二次作业

---

设计思路

---

这次仍然要求的是一部电梯，要求电梯能够实现捎带算法或者其他更快的算法。由于电梯的请求到来的情况具有不确定性，导致各种算法都存在性能十分差的极端情况，所以在写这次作业的时候果断选择了按照指导书上的捎带算法：主要是定义了主请求、捎带条件

主请求是：当电梯请求队列不为空时，主请求是到达电梯请求队列时间最长的请求，当电梯请求队列为空的时候，主请求是到达调度器时间最长的请求

捎带条件是：当前主请求与该请求的目的地处于电梯当前位置的同一侧，即可以成为捎带请求

为了能够不混淆会令主请求的人乘坐时间过长的捎带请求，我在程序中规定：电梯只能添加满足捎带条件并且出发楼层与电梯当前位置相同的捎带请求

这样的话电梯的工作流程就是：

主请求为空时：向调度器申请主请求，并去接主请求发出者

每到达一层楼，判断是否需要停留（有无人上下电梯、有无当前楼层可添加的捎带请求）

每当主请求下电梯时就更新主请求

当电梯为空时又重复第一步

同时需要注意的是由于现在一个电梯可装载多个请求，为了避免电梯在装到人之前就下人的情况：

我为每个人设置了状态，上电梯之前的“not in”，上电梯之后是“already in”从而避免了bug出现。

---

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

---

程序结构

---

由于这次的电梯本质上只需要更改调度器向电梯派发指令的策略，添加判断是否应该停靠、派送捎带请求的方法，所以整个程序总体上结构没有太大变化，代码也基本沿用第一次作业的代码，只做了少量修改。

---

度量分析

---

由于基本沿用了上一次作业的代码所以各个类之间的耦合度还是比较低，唯一高一些的是pusubcmd方法，这是由于这个方法要求调度器能够知道电梯当前的位置即已经装载了的指令的情况，所以与电梯类的耦合度较高。

---

其他

---

总的来说这次作业难度不大，主要精力花费在如何设计捎带算法的实现，让电梯运行的时候面对各种指令情况不会出现吃人、造人、不停开关门的bug，解决的方法是：

只装载电梯当前位置的捎带指令。

为人设置是否进入电梯的变量。

---

第三次作业

---

设计思路

---

这次要求能够支持三部电梯，并且对电梯定义了运动速度，容量，以及可停靠楼层。难点在于根据每个电梯的可停靠楼层，将无法一次乘坐到达的请求，进行拆分，从而到达。

我采取的策略是：通过逐层分析，所有不能一次到达的请求，都能拆分成两次到达，所以我的拆分策略是拆为出发楼层到离当前最近的中转楼层与从中转楼层到目的楼层。

同时由于拆分后的后半部分指令必须在前一半指令结束后才能执行，所以我采取的策略是将其放入一个暂不可执行队列，当前半部分执行完成后，发送信号将后半部分加入可执行队列。

至于运动速度、容量、可停靠楼层等，都可以通过在电梯类中增加相应的成员变量，与判断条件来实现。

同时这次仍采用和第二次一样的捎带算法。

---

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

---

程序结构

---

除了增加与指令拆分相关的代码与容量速度等新成员变量，整个程序总体上结构没有太大变化，基本沿用第二次作业的代码，只做了少量修改。

---

度量分析

---

这一次的代码耦合情况就不像前两次那么令人乐观了，可以看到又四个方法爆了红：

可以看到向电梯发送指令的两个方法pushmiancmd与pushsubcmd的模块复杂度和循环复杂度都较高，这是由于两者在向电梯发送指令前都需先对调度器内部是否还存在符合各电梯要求的指令进行判断，然后根据电梯可去楼层集判断可否推送该指令，最后还需遍历更新当前调度器内符合各电梯可去楼层集的指令状况。所以需要频繁访问电梯的位置信息、可去楼层集、是否超载，以及循环判断指令情况，所以导致这两项复杂度过高。想要解决这一办法可考虑将这两个方法中的部分代码另写代码封装起来。

同时loadcmd的循环复杂度较高，这是由于我在这部分实现了电梯指令的拆分，由于我是暴力枚举的所有拆分情况，所以判断层数多，循环复杂度很高，可以考虑实现一个一般化的拆分方法，不过可能性能就没有暴力枚举的最佳拆分那么好。

---

其他

---

这次的难点在于指令拆分，坑点在于指令拆分后，后半部分指令必须等前半部分执行完后才能进入队列，同时考虑是否已经执行完所以指令时必须考虑被放入暂不可执行队列的指令，否则可能会出现电梯提早被kill的情况。

---

分析自己的bug

---

由于采用的都是指导书给出的算法和模型，并且在处理时模拟了真实电梯的各种行为而不是只输出结果，所以这三次作业没有被测出bug。可见简单的算法加贴近实际情况的模拟会使代码十分可靠。

---

找他人bug的策略

---

这次找他人bug的策略主要是首先提交自己在写代码过程中出现的bug，看他人是否犯了同样的错误，其次是针对于线程安全可能出现的常见问题，比如不能平稳结束、提前结束等进行测试。此后采用的是选取两三份代码风格不佳的代码，阅读分析其思路，然后反向找逻辑错误。可惜由于这几次在的组都是属于，简单思路与实现，导致代码逻辑显得坚不可摧，所以找bug的效果并不太好。

---

心得与体会

---

事实证明，简单明了的算法与模拟现实生活的思路能够构造非常可靠的代码，这也是这几次没出bug的原因。只是可惜，由于性能的缘故，后两次作业的分组情况都不是很理想，后续可能考虑在保证可靠性的情况下，采取一些高性能但复杂的算法，来挑战自己！