BUAA OO第二单元总结

锁设计思路

如我之前在讨论区所发的思路，多线程程序锁的最大问题是死锁，而死锁的必要条件是各线程锁的获取顺序不唯一。因此，在本单元作业中，我充分考虑了所有线程获取锁的顺序的唯一性。

总体而言，涉及到的锁有如下几个：

电梯状态锁

每个电梯有自己唯一的锁，所有有可能改变电梯状态的操作前都需要获取该锁，从而避免分配器读取状态和分配请求之间电梯的状态改变。
总请求列表锁

输入线程向其中添加请求、分配器从中提取并分配请求、电梯Maintain或放人后将请求放回时均需要首先获取该锁。
楼层锁

由于第三次作业要求每个楼层同时开门的电梯数，故每个楼层有独立的semaphore锁，用来提供“开门资源”。

对于如上锁，在所有线程均按照相同的顺序获取，从而保证了理论上不存在顺序层面的死锁问题。

针对同步块，个人理解实际上synchronized(x)方法就是获取了对于x的锁，这与可重入锁和其他锁并没有任何差别，属于java为程序员提供的语法糖。因此只需要遵循一样的获取顺序即可。

值得注意的是，线程安全的对象不代各个线程不需要再手动获取对象的锁，这是很多同学没有考虑到的。线程安全的对象不等于线程安全，因为对象无法保证其他线程不会因为先判断后执行等符合操作破坏其线程安全性。如Elevator是线程安全的，但如果此时Manager先判断了电梯状态，后向电梯中添加请求，固然获取状态和添加请求操作都是原子操作，但是如果此时有另一个线程同时执行上述操作，就会发生线程安全问题。因此同步方法只能为线程安全提供基础的保证，而不能解决一切问题。

程序架构设计

在本单元作业中，我的设计从始至终保持一致，第一单元中我充分考虑到了迭代的要求，为调度器的输入设置requests共享对象，为每个电梯添加了taking表和与调度器共享的waiting表，由调度器将可稍带请求送往电梯，电梯只需要针对自己的两个表执行对应的机械操作。

调度器Manager从根本上来说，起到的是流水线中间级的作用，扫描输入“传送带”上的请求，以FIFO的原则根据调度策略向电梯分配请求。

UML图如下：

可见我的类设计非常简略，由此也导致我的类往往较为庞大，但这种不过度抽象的设计也使得思考和debug的难度大为降低，从某种程度上而言也具有一定的可取性。

三次作业具体迭代方案

由于再第一次作业中的设计较为全面，因此其后两次迭代都比较容易。第二次作业要求可以添加/删除电梯，因此我在输入线程中针对这两种在manager中添加了方法，添加电梯直接向elevators中添加即可，删除电梯我首先从elevators中移除电梯并设置电梯信号量ismaintain为True，电梯识别到自身被维护后会自发在下一层开门并将请求放回requests。

第三次作业要求电梯具有可达性，我在电梯中添加了map来保存每个电梯的可达性，在manager中使用floyd算法在增减电梯时维护一个电梯最短路径图。将每个楼层抽象为节点，节点之间取0.4+0.4*D/N为路径长度，其中D为楼层间隔，N为可以同时到达这两层的电梯数量，由此建立楼层图。通过在楼层图中运行最短路算法，可以求得考虑多电梯同时承载的最短路径。以一个例子为例，如果有一个1-11层的电梯和10个2-11层的电梯，面对20个1到11层的请求，最短换成数方案会全部交给正常电梯，而该方法可以使正常电梯在1-2层之间运行，而其他电梯在2-11层之间运行，有巨大的性能差距，可见该方法的优越性。

第三次作业同时要求楼层最大开门数量，我通过为每个楼层创建semaphore锁来实现开门资源的共享。只需要在电梯对应的open方法中进行判断、等待即可。

UML协作图

在程序中，我避免了所有轮询，完全基于wait/notify方案完成了程序的设计。实际上，我们只需要在所有关键节点进行notify即可保证程序能够正常运行。

出现过的bug

在第一次作业中，出现了分配问题，对于11到1的类似请求当接到一个请求后没有及时分配其他可稍带请求，导致每次只乘坐一人，引起RTLE超时。
第三次作业中，对于只接人电梯的判断出了问题，没有考虑到同一批人先下后上的情况，导致强测一个点WA

在本单元的学习中，我继续开发了上单元搭建的评测机框架，与同学合作完成了第一次、第二次作业的评测机开发，并以此基本满足了课程组要求。

心得体会

在本单元作业中，我们一步步设计了一个多线程协作的电梯系统。线程安全问题是多线程程序设计最为关键的问题，对此，我一方面通过理论学习和推导搞清了是什么导致死锁，什么时候需要上锁，从而依托wait/notify结构完成了本单元的作业。另一方面，我通过评测机的大量数据覆盖测试验证程序的无死锁，保证程序的正确性。

层次化设计是面向对象设计一以贯之的思路。在第一单元中，作业要求我们必须要通过抽象来实现表达式的化简，而第二单元中只需要满足多线程交互需求即可，过度的抽象实际上会增加自己的调试代价。