面向对象第二单元总结博客

面向对象第二单元总结博客

homework 5

实现相关

核心目标是实现单部电梯在三种模式下完成对于乘客的运输。而且需要将总运输时间限制在他设定的标准时间（ALS）之内，也就是不能才用太慢的调度策略。

首先，指令的输送是实时的，也就是我们设计出的系统必须实时的处理请求。这就逼迫我们放弃一贯以来的一个线程的编程模式，设置多个线程处理模式。这与本单元的教学内容也是十分契合的。

对于这次作业来说，实际上仅需要两个线程就够了。实际上，在本次作业刚开始时，因为此前并没有接触过多线程编程，所以并不知道从何下手，主要有困惑的地方还是不知道如何实现线程之间的协同。这时，看了讨论区一位学长写的帖子后，我深受启发，决定采用 “生产品-消费者+桌子” 模式。

具体来说，我设置了一个Scanner 类，接受标准输入的指令序列，作为整个系统的 “生产者” ，设置了WaitQueue ，所有从输入线程得到的指令都会预先放在此类中。此外，我设置了一个Modifyer 类，作为整个系统的 “消费者” ，负责从WaitQueue 类中获取指令并完成。自此，系统已经结合 “生产者-消费者模式” 完成上述需求。

仅仅如此吗？当然不是，对于每个线程来说，都需要一些辅助类来支持它们的行动。我将它们大致分为 “信息存储类” 和 “决策类” ，所有的“信息存储类” 负责保存现在的情况，包括两个，elevator 类和WaitQueue 类，“决策类” Schemer 结合现在的情况做出决策，给电梯线程的下一步活动做出指示。同时，对于调度算法的实现，也主要靠对Schemer 类的设计实现。

下面讲讲我的调度策略：

• Night：所有人立即到达，实际上是一个离线的过程，从理论上来说，是存在一个最优解的，可以通过一些算法求出，但是因为我太（bu）懒（hui）了（qiu），我最后只是用了一个贪心的策略。我每次从队列中选出去往楼层最高的6个人，并将人放入电梯中，这样保证了大半部分情况下的最优。
• Morning：走一趟会花费很多时间，所以我一次尽量让电梯多送一些人，所以每次我会等电梯满员之后再送，除非此时输入线程已经停止运作。
• Random：我采取了一个每次挑选离当前距离最近的目标送或者接的策略，但是实际并没有产生良好的效果。

同步块与锁相关

• 我将 Elevator 和 WaitQueue 类都设置为线程安全类，也就是将其中的方法加锁，使它们成为线程安全方法，确保调用对象的这些方法时不会引发线程安全的问题。将方法加锁其实是一个十分无脑也是十分稳妥的做法，对方法加锁本质上就是将实例化此类的对象加锁，对于这些被多个线程共享的类来说，将方法加锁能有效防止多个线程同时修改类的情况出现。
• 同时，由于第一次作业中，我缺乏多线程编程经验，我在线程类中 \(\text{run}\) 方法中也使用了同步块进行加锁，但是因为这个我也出现了 bug，因为一个锁的范围不够全，导致出现死锁的隐患，这个 bug 直到 hw6 才解决。因为这次bug，我意识到，同步代码块实际上是存在很多的风险的，因为自己无法预知应该将锁的代码块扩展到多大才不会出现线程安全问题。但是，好在将锁的范围扩大在本单元作业中是没有多大损失的，所以最好的方法是将 \(\text{run}\) 方法分解成几个逻辑块并将所有逻辑块都加锁。当然，如果此逻辑块只涉及到一个对象的引用，将该逻辑封装成对象的线程安全方法是最稳妥的方法。

调度器相关

这次作业没有用调度器呢……

架构分析

• UML类图

  

  由于分了三种调度策略，每个策略类又享有所有信息存储类，所以产生了较多的依赖关系。

基于度量的复杂度分析

• Method Metrics

• Class Metrics

在策略类中，由于追求性能的优秀，我写了一些比较冗长复杂的代码（虽然最后好像并没有起什么作用），用了许多 if 特判，写的不是很面向对象，导致复杂度较高，但是由于策略类仅仅负责在电梯自己的请求队列中决定电梯的下一步行动，所以完全可以沿用至以后的几次作业。但是假如需要更改电梯的行动策略，那么还是需要做大量改动，所以其实策略这一部分其实不是很面向对象，可拓展性不高。

自己的bug

在本次作业的公测和互测中我均没有被测出bug。

其实本次作业是存在一个bug的，是我在判断电梯线程什么时候跳出循环时，加锁没有加全，导致存在一种执行顺序导致电梯线程进入wait后无法被唤醒，出现了死锁的隐患，但是这种情况发生的概率很低，确实也没有被测出。

这个 bug 被我在第6次作业测试的时候发现。出现这个bug，本质上是我代码设计的不够严谨，没有考虑到全部的情况，导致锁的范围过小并没有起到它的作用。解决这个办法很简单，如我上次所说，将该逻辑块封装成一个类中的线程安全类即可。

他人的bug

这三次的互测，我主要都是依靠评测机进行黑箱测试，在我的互测屋中我发现同组有位同学会死锁导致运行时间超时，所以我把他 hack 掉了。

homework 6

实现相关

本次作业与上次作业的区别就是电梯变多了，去掉了 ALS 的限制，还是送人，还是三种模式。我看到这个第一反应是我交第一次作业好像也能混过去，但是这么做可能会被助教锤。

言归正传，现在我们的需求是实现多部电梯的同步调度，这时候肯定不能只开两个线程了。首先，一个电梯肯定需要一个线程，收到第三次实验的启发，我决定设置一个调度器作为输入线程的 “消费者” ，同时也充当电梯线程的 “生产者”。上个作业设计的 “生产者-消费者” 模式在这次作业中还是可以继续使用，不过需要改成两个层次的 “生产者-消费者”模式。下面我用一张图来揭示一下我的大致流程图：

可以见到每个电梯设置了一个独一无二的等待队列。其实到这里可以发现，其实对于下面三个分支的每一个分支（“桌子”+电梯线程）都可以沿用上一次作业的写法，我真正需要去完善的只是设计调度器和连接调度器线程和输入线程的 “大桌子” 。事实上，我也并没有改变上一次写好的策略类 Schemer （因为考虑到上一次Random我自己设计的算法效率较低，所以我这次换成了 look 调度算法）。

下面谈谈策略：

正如上面所说，当我们将请求分给这个电梯后，剩下的需要执行的操作第一次已经全部完成，所以这里的策略实际上只是如何进行人的分配。

一开始我想单纯按照电梯中剩余人数从小到大排序然后每次将新来的人分配给人数最少的那个电梯，但是看到讨论区有大佬指出，其实按照电梯剩余运行时间来分配是最优的。那么问题是对于电梯的每一个状态，如何算出它之后还需要运行多长时间呢。从理论上来说，如果电梯严格按照一定的规则来运行，剩余时间一定是可以通过一些公式计算出来，对于 Morning 和 Night 模式来说，因为调度简单，这是可以计算的。但是对于Random来说，计算的复杂程度很高，可能会出现巨大的误差导致算法失效。经过观察之前的代码，我注意到，其实计算时间只需要将之前调度的过程模拟一遍即可，即去掉 sleep 这样的过程，模拟一边电梯送人直到没有人了的过程，实现也很简单，将调度器部分的代码复制一遍再简单修改一下（这就很面向过程了……）。

对于Night模式，我并没有才用上面的策略，考虑到 Night 模式一开始人会全部来齐，所以我就直接平均分配，每次分配完一轮之后计算最快的电梯运行完需要多久，然后让调度器线程等待这么久。但事实证明，平均分配并没有6个，6个分优秀，这也是我算法设计的失误之处。

同步块与锁相关

考虑到这次存在加电梯操作，所以我将所有的线程启动操作都放在了输入线程中。对于 Modifyer 线程和 queue 和 elevator 两个信息存储类的同步问题只要沿用上一次的代码就好了。

因为这次新设了一个RequestQueue 类，同样是被两个线程共享，所以我也将它的所有方法设置为线程安全的。正如上面所说的，由于将判断是否结束的逻辑写在了线程类中的 \(\text{run}\) 方法中， 在线程类中加锁范围不够，导致出现了死锁的隐患。所以这次我设计的时候，将大部分原本只加了一个锁的同步块尽量写成了该锁对应对象的线程安全方法。核心是将判断状态和修改状态结合封装，放在一个锁中。

同时，出了设置线程安全类的方法，为了防止运行代码时被参考的信息发生变化，可以在运行前就对目前的参考的信息类进行深拷贝，然后将深拷贝后的结果作为参考的结果。

但是有一种情况，是不得不用代码块同步的，就是代码块中涉及多个共享信息类时，这时候需要加多个。这时候为了保证不引发死锁，一种比较合适的方法是按照一定的顺序加锁，这样可以避免出现循环加锁的情况出现。

调度器相关

本次作业的调度器通过每个电梯独自的请求队列 WaitQueue 来与电梯进行交互，具体体现为向每个电梯的请求队列输送请求，将该请求设置为只有该电梯可见的。同时接受来自输入线程 Scan 的请求序列。

因为这次的层次化结构，导致一些信息需要被层次化传递。比如结束信号，我就设置成由输入线程传给调度器后最终传给电梯线程。

架构分析

• UML类图

基于度量的复杂度分析

• Method Metrics

• Class Metrics

方法复杂度分析太多比较占篇幅，我就挑了几个复杂度较高的部分出来单独分析，发现几个复杂度比较高的地方主要还是策略类中判断是否开门，向上走或是向下走的代码块和用于计算Night和Morning模式下电梯此时的剩余运行时间的代码，其中都有比较多的 if-else 语句做判断，有的还出现了循环嵌套，导致圈复杂度增加。但是这也是将调度算法单元化封装之后的结果，实际上在不修改电梯调度策略的情况下，在生产者消费者架构的支撑下，整体架构的可拓展性还是很高的。

自己的bug

本次我的互测和强测中均没有出现bug，但是在课下调式的时候出现了死锁问题，原因我在上面已经说过了，经过了较长时间的调式才最终解决。

他人的bug

本次互测我才用的主要的测试方法还是基于自动评测机的黑盒测试，最终找到房间中有两个人会出现死锁，其中一位同学我hack了很久也没有成功，但是有一位同学（Caster）在我最后一发提交后出现死锁，被我成功hack。

对于线程安全类问题，如果此类问题导致了他程序出现错误，会直接被判断为错误。对于死锁问题，如果程序出现死锁，程序在超出运行时间限制后会自动停止。但是在评测机中只着重检查了程序的正确性，并没有专门针对线程安全问题进行测试。实际操作过程中，我会开许多个评测进程同时运行来模拟真实的强测环境（其实数量还是远远比不上强测时的规模）。

本单元测试的时候除了需要一个数据以外，还需要考虑定时投放的问题，如何设计评测机使得它可以做到在某个准确的时间投放样例是一个问题。这就要求评测机也需要和程序代码一样实现多线程，实时的检测输出是否正确，实时的投放数据。

homework7

实现相关

本次作业增加了一个条件，每种电梯都不一样，速度和容量有不同的限制，其实这些都不是主要的变化。最重点的变化是电梯可停靠楼层发生了变化，意味着不能用一直以来的 “分配完就不去管” 的逻辑来操作了，也就是我们需要实现电梯的换乘。

实现电梯的换乘本质上是在刚才的数据传递通路中增加一个回调的通路，就是将无法处理完成的指令从电梯线程中回调回调度器中。我增加了一个数据通路，在进行开门出人操作后判断那些人是否已经到达目的地，如果没有到达，就将其放回大请求队列 RequestQueue 中。同时，需要改写电梯的参数以及相应的调度策略函数，由于本次作业模拟场景复杂度和不确定度较高，所以我将作业 6 中许多优化都删去了所有电梯一律采用一种调度此策略，即 Look 模式。为了适应本次作业的要求，我调整了开门关门，上下行等判断函数使其适应了每个种类的电梯的需求。

下图呈现出了大体结构模式

下面谈谈调度器设计策略：

这次主要的设计难度在于换乘算法的设计，我大致采取了以下的策略：

• 电梯按 C，B，A 排序。
• 如果当前电梯无法到达当前人的起点位置。不去考虑这个电梯。
• 如果当前电梯可以到达当前人的起点位置，则将人送到距离终点最近的位置。
• 找出所有满足条件的电梯，按照运行时间排序，选运行时间最少的那个（hw6）。

上述策略会产生比较大的换乘间隙，虽然在有些时候可能会造成大量的时间浪费，但是在大部分情况下，这样的调度器分配算法还是可以取得比较优秀的结果的。

同步块和锁相关

这次作业在前述设计模式下，需要完善的线程同步问题就是保证回调时不会出现问题。回调的需求会产生两个问题：

• 回调指令相当于给大队列中输送请求，所以可能也会有唤醒调度器线程的需求。但是由于之前我将 RequestQueue 类中接收指令的方法getpersonRequest 设置成了线程安全类，所以这里直接调用即可解决该问题。
• 在上一次作业中，我调度器停止运行的条件是，RequestQueue 中已经没有未处理的请求且从输入线程传来了停止输入的指令。但是这次由于存在回调，所以，在判断 RequestQueue 空，并且输入线程结束之后，还需要判断所有的电梯以及它对应的等待队列也为空时，才能结束输入线程，否则还是需要进入等待。有等待就会有 notify，最初我将 notify 加在了，小等待队列 WaitQueue 的 checkEnd 方法中，因为我是在这个方法中判断当前是否为空，然后进行电梯线程的等待。但在这个函数中又对 RequestQueue 类的加锁，结果导致出现了循环加锁的问题（因为在线程类中我又有一个 RequestQueue -WaitQueue 的加锁顺序）。之后经过反思，我决定将这个锁和 notify 直接加在了线程代码的最前面，与其他对象的锁隔开，解决了这个问题。

经过上述的 debug 的问题，我总结出了加锁了几点经验：

• 尽量将每个锁隔开加，每个锁之间间隔开，尤其涉及到 wait 和 notify 的加锁代码。
• 如果一定要同时对多个对象加锁，我们可以一开始就设定一个恰当的加锁顺序，并严格按这个加锁顺序来执行，这样可以有效的防止循环加锁的问题。

调度器相关

调度器的策略前面已经说了，这里不再赘述。

这里主要谈谈调度器与其他的线程的协同的。首先，调度器是输入线程开启的，这与第 6 次作业是一致的。Random和Morning模式下的调度器在运行期间，按照上述策略向电梯分人，如果 RequestQueue 变为空，则调度器等待。输入线程传来停止运行信号，调度器切换工作模式，开始接受各个电梯电梯线程的停止信号（为空）。如果所有电梯为空，则向所有电梯线程传结束信号，结束调度器线程。

架构分析

• UML类图

可以看到类与类之间依赖关系比较强，主要体现在 Elevator ， WaitQueue 和RequestQueue 可以被多个类构造和传参，主要原因是这个两个类充当了信息中介的作用，我需要这些类向各个线程和策略类传递信息。因此多个类与这三个类产生联系。

• UML协作图

这是最终版的UML协作图，由于最具有代表性，我就只画了这一个。

基于度量的复杂度分析

Method Metrics

Class Metrics

与上一次作业相同，这次我也只是展示方法中复杂度较高的一部分，其中复杂度比较高的方法出了和上两次作业相同的策略类中和线程类中的 \(\text{run}\) 方法，还有一些卸载信息存储类中用于决策参考的方法，因为在这次作业中，电梯的规格发生了比较大的变化，所以对于 look 调度算法的实现方式，我也做出了改变，在诸如判断人是否能够下电梯等地方，使用了比较多的 if 判断语句，导致复杂度较高。这说明我的代码中很多地方封装度不够，大方向上使用了面向对象的思维，但是没有真正从细节上理解面向对象的精髓，对于很多小方法的实现上还是使用了面向过程的思维。

但是我这种设计模式我自认为可拓展性还是很高的，虽然一些方法实现上较为麻烦，但是这些方法都是一劳永逸的，如果修改电梯可停靠楼层的参数，我只需要较少的修改就可以完成目标，因为我没有用电梯的型号属性来区分电梯的可停靠楼层，而是用一个 boolean 型数组来表示，这样就大大提升了代码的灵活性。

自己的bug

在中测强测互测中均没有出现过bug。

但是在本地测试时候，因为加了换乘操作但是没有考虑修改调度器结束条件而造成了大部分人出了电梯就进不去了，之后加了相关逻辑后就出现了我在 “同步块和锁相关” 部分说过的问题，这里我就不写了。

他人的bug

继续基于评测机进行黑箱测试，我的互测房间中竟然出现了 4 个人死锁，但是我却一个也没有 hack 掉，好难受。所以我觉得评测机制有待完善，比如一个测试点多跑几遍啥的，不然我感觉多线程死锁问题大部分情况下会被逃过。

反思与总结

在本单元中，我第一次接触到了多线程编程，明白了原来程序也不是一段时间只能干一件事的，而是可以几件事情一起干。除此之外，我也了解到了一些新的 bug，死锁和线程安全问题引发的信息不一致，深感作为一名还未成熟的程序猿，以后会经历的东西（bug）还有很多很多。

线程安全

这个我感觉我前面的长篇大论中已经讲了很多了，这里就提纲挈领的讲几点吧。

信息安全

• 将被多个线程共享的类设置为线程安全类（很重要，不然线程安全 bug 调都调不完）。
• 保证引用每种信息存储类的对象的线程尽量不超过两个。
• 线程类 run 方法中尽量引用线程安全的方法，如果逻辑上不方便将所有行为包装。如何保证信息一致和线程安全？
  • 对信息存储类深拷贝，将拷贝的结果用于参考。
  • 将主要的几个被多线程共享的对象加锁，加锁时严格按照一定的预设顺序。

死锁

• 大部分情况下发生概率非常的小，如果实在特殊的死锁其实可以不用管它

• 做好分析，找准加 wait 和加 notify 的地方，加一个 wait 就加一个 notify。

• 拒绝循环加锁，避免它的最好办法就是按顺序对对象加锁。

• 将包含 wait 和 notify 的逻辑封装在线程安全类的方法中，为了防止忘记将条件判断语句包含在锁里（整体加锁）。

层次化设计

一个好的架构 \(>>\) 性能。

这三次作业中支撑起我整个代码最核心的部分就是我的架构。从一开始的第一次作业简单的生产者消费者模式，到最后层次化的架构，这样一个稳定的架构保证了整个程序具有相当高的稳定性，再次基础上，进行修改，优化，debug 都变得方便了很多。当编码者创造出一个清晰的架构并明白每一个部分都承担了什么样的职责后，剩下的所有事情都变得方便了许多，因为无论做什么养的修改，他都能精确的找到位置，而且每个部分都相对独立，不会产生藕断丝连的影响。

面向对象第二单元总结博客

原文：https://www.cnblogs.com/iuiou/p/14698323.html