第一单元总结博客

一.历次作业分析

• 第一次作业

  (1)同步锁的设置和锁的选择

  第二单元第一次作业是一部ALS可稍带单电梯的设计。我使用了两个线程，一个处理输入的输入请求创建线程，还有一个电梯线程，这两个线程共享一个公共的等待队列。由于线程间的交互比较简单，所以我没有使用调度器，而是在电梯中直接进行调度。

  指导书给出了ALS的捎带要求：首先确定主请求，这个过程可以分为当前电梯内有乘客或者当前电梯无乘客两种情况；如果当前电梯有人则选取电梯内最早进入的乘客的请求作为主请求，否则选取当前请求队列中请求到达时间最早的作为主请求。当主请求确定以后，就可以在主请求执行的情况下进行捎带：如果当前请求队列中某一个请求的目的楼层与当前电梯运行方向一致就可以进行捎带。这样就实现了一个符合ALS的电梯。

  这里要着重讲一下同步锁的位置。我的第一版过中测的电梯，直接在电梯的run()方法中全部用synchronized关键字进行加锁，但这样直接导致自己强测裂开，结果是没有实现我预想中的捎带。那么这里的问题在哪呢？其实就是这个synchronized同步锁的位置和范围问题，试想，如果当前电梯里面有了一个请求，那么由于run()方法的同步锁一直没有释放，所以输入线程一直无法得到这个锁，只能一直等待电梯运行完当前电梯里面的请求才能继续处理输入，这样我的电梯实际上就成为了一个“傻瓜”电梯，只能一个乘客一个乘客地带。在同学的协助下发现了这个问题后，我将synchronized的位置细化，只有真正用到共享的这个等待队列的时候，我才用synchronized加锁，而在电梯正常运行的时候是可以释放这个同步锁的，这样，评测机在跑的时候就可以直接实现实时输入，这样就可以由电梯自己决定是否捎带，从而就实现了ALS电梯。

  (2)调度器的设计

  如前文所述，由于第一次作业的线程较少，只有一个输入处理线程和一个电梯线程，所以我没有设计调度器，而是由电梯本身来进行调度，这样还是实现地比较高效的。

  (3)UML类图和UML协作图

  

   

   

   

  在这里我一开始是想使用三种电梯，通过继承电梯父类，实现三种模式的功能，但是后来发现，其实只需要在处理输入的时候对电梯确定调度策略就好了，而且我将三种模式中的Random和Morning合为了一种（每次读入一个请求就打入共享的等待队列），Night模式单独为一种（读入ctrl + D以后全部加入等待队列），所以最后的实现中没有三种电梯，只有一种电梯。同时可以非常清晰地看出，电梯和输入请求部分共享了一个公共的RequestList，这也就是这次多线程宏的核心——共享数据，我们所有的锁，还有wait()和notifyAll()都是基于这个“共享”的特性所做的操作。

  

   

   

   

  可见main主线程创建了共享队列，也创建了输入分析线程和电梯线程，整体结构还是比较简单的。

  (4)bug分析

  • 自己的bug：第一次作业可谓全面翻车，强测基本没对几个，互测还被hack一个点；主要存在两个问题，一个就是前文提到的同步锁的位置太大，导致自己的电梯并没有实现捎带；第二个就是存在一些乘客在电梯中时间过长，这是因为我采用主请求的方法进行运行，所以在执行主请求的中途并不会下乘客，这就使一些捎带请求可以下电梯的时候并没有下，这就最终导致电梯运行超时。

  • 发现别人bug的策略：在互测中没有发现别人的bug

• 第二次作业

  (1)同步锁的设置和锁的选择

  第二单元第二次作业是多部电梯的实现，初始时为3部，随后可以动态增加到5部，要求我们实现多部电梯的调度。这次作业中我将所有电梯都单独看成一个线程，每部电梯都有自己的等待队列，调度器线程完成将总请求队列中的请求分配到每个电梯中的任务。在这里我的同步锁主要设置在这几个地方：首先还是电梯的内部run()方法中，在所有需要用到电梯本身的等待队列的区域我都上了锁；然后就是在调度器中对对应的等待队列进行加锁。锁的选择上我都是使用synchronized同步锁。

  (2)调度器的设计

  第二次作业比第一次复杂度上升了不少，调度器的实现显得非常重要。我采用了“平均分配”的调度算法，每来一个请求进入共享的请求队列，调度器就将这个请求按照电梯顺序分配下去，进入到每一个电梯的等待队列，这个队列是每个电梯独有的，然后由电梯自己实现捎带（这次电梯我换成了SCAN算法）。同时，当输入线程识别到null时，在调度器中通知所有电梯的等待队列，为所有电梯的等待队列设置结束标志，这压根每个电梯就可以在当前电梯内请求完成后结束线程。

  (3)UML类图和UML协作图

  

   

   

  可见，共享的公共等待队列是由RequestProdecer和Scheduler共享的，每一个电梯的等待队列是与Scheduler共享的，这样就可以实现这三个线程之间的通信，实时地反馈请求的变化，实现了请求的调度。同时，电梯我实现了SCAN算法，这是比ALS更加高效的一个算法，直接进行扫描，电梯在最底层和最高层之间上下运行，扫描所到楼层的请求，进行上乘客和下乘客。同时我的输入请求线程也进行了修改，主要是增加了对添加电梯请求的处理，分为了两种情况：如果是加电梯请求，就在当前输入处理线程中创建一个新的电梯线程；如果是正常的请求，则将其加入等待队列。

  

   

   

  可见main主线程创建了共享队列，也创建了初始时的三个电梯线程，最后创建了调度器和输入处理线程，同时，在过程中还有可能由RequestProducer创建电梯线程，这些线程取决于输入的请求类型。

  (4)bug分析

  • 自己的bug：第二次作业最开始通过中测的版本我只大概添加了不到5行，也就是加电梯请求的处理，至于调度，我直接使用线程间的不确定性进行调度，根本没有使用调度器。抱着试一试的态度提交，没想到通过了中测，不过我怀疑是线程的随机性让我碰上了这种lottery，于是重新提交了一遍，还是过了，我就开始思考这其中我没有弄清楚的奥秘。

    按道理这种线程之间随机抢请求的调度是不太合理的，按照正常逻辑的话，很有可能会出现大部分请求都被一个电梯抢走的情况。但我经过思考发现其实并不会出现这样的问题，其中的原因就在于，我在notifyAll的时候，如果一个电梯已经有人的话，是不会被考虑到这个*竞争的队伍中来的，只有当前没有乘客正在wait的电梯可以进行竞争，那这样其实是与我最后实现的平均调度是一样的；当所有电梯都有乘客以后，按照随机竞争实现的效果与平均分配的效果实际上差不多，根据随机性，肯定是平均分配到多部电梯，这就是为什么不写调度器也可以过中测的原因。

    当然为了苟过强测，我还是写了调度器，也就是前文提到的平均分配的算法。在这里我的bug主要是性能问题，我的最开始的ALS电梯跑得太慢，所以我直接改成了SCAN算法，最后通过了强测。

  • 发现别人bug的策略：在互测中没有发现别人的bug

• 第三次作业

  (1)同步锁的设置和锁的选择

  第二单元第三次作业是多部分型号电梯的实现，初始时为3部，随后可以动态增加到5部，要求我们实现多部电梯的调度，同时当一部电梯不能直达时，要求实现换乘。这一次我还是将所有电梯单独看成一个线程，与上一次相比加入了一个共享类ProcessQueue主要用于存放电梯的等待队列和相应电梯的型号。这个类由Scheduler和Ele和RequestProducer共享，实现请求的实时更新。

  在这里同步锁的位置就更多了，首先在前两次作业中是没有这个ProcessQueue类的，所以加入了这个共享类就意味着需要加更多的锁，我在调度其中需要加上更多的锁，保证同步性，同时这里还需要注意一个问题，那就是加锁的时候是给ProcessQueue这个大的整体加锁，还是给ProcessQueue中的每一个具体的RequestList加锁？在这里只能够对具体的电梯的RequestList加锁，因为我们无论是分配请求的时候还是处理请求的时候，都会将这个请求加入到一个具体的电梯的等待队列中，那么这个时候，如果ProcessQueue加锁，其他的电梯有可能在并不需要加锁的时候被上锁，这样就会使得其他电梯的运行不正常——类似我第五次作业中所的位置太大的错误。

  (2)调度器的设计

  第三次作业的调度器实现主要有这几个方面的考虑：

  1. 对于每一个请求，怎么确定将其加入到哪一部电梯

  2. 如果某一个请求加入了一部不能直达的电梯，怎么处理换乘

  首先对于第一个问题，我还是采用的类似第六次作业中的算法，平均调度，只是在这里会有一个该请求能否通过这部电梯的问题，所以在这里调度器需要判断一下这个请求能否上这个电梯（因为不同类型的电梯可停靠楼层是完全不一样的），如果不行的话，就顺次找下一个，直到这个请求可以被带走。

  当这个请求分配到了某一部电梯以后，调度器需要判断这个请求能否直达。我在这里采用的是将请求拆分的方法：当确定这个请求可以上这一部电梯之后，立马判断是否可以直达，如果可以，直接将其加入相应的电梯的等待队列；否则，将其拆分成两个请求，改写两个请求的出发楼层和目的楼层，并设置一个标记位，在电梯运行的时候，只有这个标记位为1的时候才进行处理，否则忽略，这是因为拆分请求的情况下，只有前一个请求完成以后才能继续完成下一个请求。所以电梯在下乘客的时候，需要对当前ProcessQueue中的所有请求遍历，如果有跟这个请求的ID相同的，将其标记位置为1，也就实现了第二段请求的加入，同时也不会出现后一段请求先执行的错误。

  这样，就解决了上述的两个问题。

  (3)UML类图和UML协作图

  

   

   

  可见，共享的公共等待队列是由RequestProdecer和Scheduler共享的，除此之外，为了实现前文所述的电梯下乘客的时候将拆分请求的后一段请求标记位有效，电梯也必须和Scheduler和RequestProducer共享一个ProcessQueue。同时在这里我们需要重写请求类，实现可以改写出发楼层和目的楼层的目的；另外也就是一个很重要的问题，有助教在讨论区提出来：输出类是线程安全的吗？乍一看，这个好像没啥影响，但仔细一想，有大问题啊！因为所有的电梯共享了输出包，但在之前的作业中我们并没有对这个输出包加锁，恰恰我又实现了换乘，也就是说，同一个请求拆分以后，如果输出不是线程安全的，很有可能会发生时间戳错乱的情况，所以我重新加了一个Output类，并对其中所有的方法加锁，实现了一个线程安全的输出类。

  

   

   

  

   

   

  可见main主线程创建了共享队列和共享的ProcessQueue，也创建了初始时的三个电梯线程，最后创建了调度器和输入处理线程，同时，在过程中还有可能由RequestProducer创建电梯线程，每个电梯的类型取决于输入，这些线程取决于输入的请求类型。

  (4)bug分析

  • 自己的bug：第三次作业基本是稳稳地通过，没有什么bug，强测也拿到了90+（第一次拿到90+，枯了orz），总体感觉还是需要有一个较强的整体思维才能稳稳通过

  • 发现别人bug的策略：在互测中没有发现别人的bug

  (5)第三次作业的可拓展性

  通过三次的迭代开发，我最终实现的这个多部不同类型可稍带电梯系统的可拓展性还是非常强的。例如，我们作业中一共是有三种到达模式，Random、Morning、Night，那么如果现在有更多的模式，比如Noon等模式加入，我的架构应该怎么融合呢？很简单，只需要修改输入处理的部分中对于请求加入等待队列的处理（实际上，我的架构有可能会把很多种的到达模式进行统一，所以基本不用太多改动）。再比如，如果我们需要实现请求优先级的情况，我可以利用我自己重写的请求类，进行排序，达到实现优先级的效果。除了这些需求，其他的需求对于我的这个架构，基本上可以说是不用太多改动的。但值得一提的是，电梯的算法确实是可以继续改进的，我这次没有使用改良的SCAN算法——LOOK算法,如果使用了LOOK算法的话，我的电梯性能还会提升。

   

二.心得体会

• 第二单元是多线程的电梯作业。刚刚接触多线程并不了解其中的奥妙，甚至第一次作业中我都不知道队列要共享，还是在同学的提醒下“java中全是指针”，一语点醒梦中人，为什么要多线程并且加锁呢？——因为存在多个线程同时对一个数据对象进行操作并且每次只能有一个线程操作这个共享的数据。这算是我对多线程理解的第一步：共享数据和互斥访问。

• 之后就是对于同步锁的理解。我对于同步锁最开始是没有任何概念的，单纯地以为是对共享了数据的多个线程的run()方法全部上锁，这也就是我第一次作业的错误，直接导致我的电梯不能实现捎带功能，后来终于在同学的点拨下（没错，学习OO有一帮hxd是非常重要的，时刻给你解答疑惑，提高效率orz）体会到，只需要对用到了共享数据的地方加锁就可以实现互斥访问了，于是我在后面的作业中都特别注意了这个问题，尤其是加入了ProcessQueue这个复杂的共享类的时候，我所有的加锁都是具体到每一部电梯的等待队列，而不是对整个大的ProcessQueue上锁，这也是我对于多线程理解的第二步：正确的同步锁位置和正确的同步锁设计。

• 最后就是对于多线程的线程安全的理解。在这里特别值得一提的是，我们无论是在中测还是强测或者是自己测试的时候几乎都体会过线程不安全带来的问题，最明显的就是：同一组数据，可能这一次运行出来是正确的，但是下一次运行的结果就不一样了，这是多线程中非常正常的问题，因为设计的不周全，我们的程序很有可能在某些线程运行下是正确的，但是在某些线程运行顺序下又是错误的，这也深刻提醒了我们线程安全对于程序稳定的重要性。这里也就是我对于多线程的第三点理解：线程安全是影响程序稳定的最重要因素，我们必须通过静态代码分析和动态黑箱测试结合的手段修改所有不符合线程安全的设计，这样的架构才是一个合格的多线程架构

• 在第二单元的学习中还是深刻地体会到了多线程的趣味性，它看起来不是很难，可是实现起来又让我们总是摸不着头脑。但多线程绝不仅仅是我们在面向对象这门课上的收获这么简单，多线程是一个在现实世界中非常有意义的思想，多线程并行的操作提高了我们的效率。

• 总体来说，第二单元的OO学习给了非常大的提升，从完全无法理解多线程到对于多线程的实现细节、同步锁等的概念有比较深的理解，我觉得自己还是有很大的进步。希望在接下来的OO学习中，继续探索面向对象思想的奥妙，各位同学共勉！