面向对象第二单元总结

前言

第二单元的内容对我们的要求从总体上说是掌握多线程的编程能力，实际化到三次作业之中便是利用多线程模拟实现一个电梯运行和调度的作业。在三次作业的迭代过程之中，就我个人而言，从对多线程的生疏不了解到三次作业结束后能够在一定程度上对多线程的熟练运用，这之中少不了无数次的上网资料查询以及夜以继日的对bug代码检查。总的来说，这三次作业的复杂程度是由简到难，但是就编程体验来讲却是由难入简，我个人认为很大程度上还是由于对一个编程体系思路的提挈，一旦你明白了多线程编程的思路，其它的内容就是应用以前数据结构、面向对象等编程技巧的地方了。

三次作业内容提挈

第一次作业内容是模拟实现一部电梯在运行层间内携带乘客在目的层间移动的过程。对多线程还不了解的我花费了许久时间去上网查询资料，以及研究课上测试的官方代码，由于对锁的应用还不是很了解，故这在很大程度上阻碍了我第一次作业的完成速度。

第二次作业内容是模拟实现多部电梯在运行层间内携带乘客在目的层间的移动过程。这次作业是在第一次作业的基础之上进行迭代的，虽然第一次作业的思路比较乱，但是由于构建的类比较细致，故能够在其基础之上进行改造和迭代。这次作业由于对效率的追求，增加了调度器这一个线程用于协调生产者（投放输入线程）和消费者（电梯线程）之间的人员平衡。当然，这次作业也由于调度器的存在，在弱测、中测、强测过程中都出现了不可复现的多线程的线程安全问题，这也将在下文进行介绍。

第三次作业内容增加了对电梯的运行特点的要求（运行特定楼层、速度）。显然这次作业要求我们实现人员的换乘操作，这对调度器的设计提出了新的要求。由于第二次作业的bug修复后个人认为，目前的设计已经消除了线程安全的问题，在一定程度上来说架构是比较稳定可靠的，故本次作业仍然在上次的基础上进行迭代开发。这次作业的难度主要在于调度、换乘的算法的实现（当然，性能也在很大程度上却决于数据的极端性）。

三次作业中同步块的设置和锁的选择

基于ReentrantLock的阻塞队列（进程间同步和互斥）

由于这三次作业整体上来讲是一种典型的生产者消费者模式，故在调度队列（或者说是需求等待队列）类中主要封装了一个阻塞队列BlockingQueue，用于实现请求的获取、添加，判断请求队列是否为空等操作。BlockingQueue基于ReentrantLock，它的基本原理如下图所示。

通过一个共享的队列，可以使得数据由队列的一端输入，从另外一端输出，完全可以应用于经典的生产者消费者模式。多线程环境中，通过阻塞队列可以很容易实现数据共享，通过队列可以很便利地实现两者之间的数据共享。生产者线程需要把准备好的数据共享给消费者线程，利用队列的方式来传递数据。

阻塞队列的主要API介绍如下：

• 入队
  • put(E e)：如果队列满了，一直阻塞，直到队列不满了或者线程被中断 --- 阻塞
  • offer(E e)：如果队列没满，立即返回true； 如果队列满了，立即返回false --- 不阻塞
  • offer(E e, long timeout, TimeUnit unit)：在队尾插入一个元素,，如果队列已满，则进入等待，直到出现被唤醒、等待时间超时、当前线程被中断情况时 --- 阻塞
• 出队
  • take()：如果队列空了，一直阻塞，直到队列不为空或者线程被中断 --- 阻塞
  • poll()：如果没有元素，直接返回null；如果有元素，出队
  • poll(long timeout, TimeUnit unit)：如果队列不空，出队；如果队列已空且已经超时，返回null；如果队列已空且时间未超时，则进入等待，直到出现被唤醒、等待时间超时、当前线程被中断情况

三次作业的迭代过程中，对封装有BlockingQueue的请求队列类没有进行改动，把锁的操作封装在类的内部，对外留出“原子”操作的函数接口，这让它的对象的共享和实际代码编写过程中不必再考虑锁的编写，大大降低了编程的复杂度同时能够提高程序代码的正确性。

设Reminder类用于synchronized代码块锁与唤醒（进程间同步）

上述的阻塞队列主要解决了生产者和消费者之间实际应用中对共享变量的操作，同时能够控制进程的同步与互斥，而这一节中引入的一个空的Reminder类（没错，确实是一个空类，类内没有任何属性，也没有方法，仅仅一个壳子），主要是做一个标记用来实现进程之间的互相唤醒操作。

有了Reminder类的对象(reminder)我们可以再输入线程和电梯线程之间共享该变量，通过在输入线程中合适位置添加

synchronized (schedulerReminder) {
    schedulerReminder.notifyAll();
}

而在电梯线程中的合适位置添加

synchronized (reminder) {
    try{
        reminder.wait();
    } catch (InterruptedException e){
        e.printStackTrace();
    }
}

来实现两个线程之间的唤醒操作，通过这样的操作，我们仅仅锁住与Reminder相关的代码块（这部分代码块本质上不会联系到代码的其他部分，是解耦的）就可以避免轮询，并自主实现何时等待何时唤醒。

由于第一次和第二次作业中没有实现换乘，故调度器调度结束可以直接结束进程，而电梯继续接送属于自己的等待队列的乘客，故只需要共享一个reminder即可。正如上述的实现方法。

第三次作业中需要实现换乘，所以存在下面所述的问题：

换乘的实现方式中对于需要换乘的乘客在其送达换乘楼层时将其送出电梯并更改其起始楼层，此时该乘客将会被送回共享队列中（即调度器的共享队列），这将会带来一个问题：即便是输入乘客到文件末尾后仍可能因为人员的换乘操作重新唤醒调度线程，所以调度线程不能在输入结束后直接退出，而是需要等待，等待换乘的唤醒。为了解决这个问题，在输入环节结束后进入另一组循环，该循环内有判断电梯中是否结束工作（即是否还有未送达的乘客），判断结束后，在通知各个电梯进程并结束自己进程。

作业中的调度器设计，以及调度器和程序中线程的交互

对于调度器的设计，主要的问题在于是否要为其单独开辟一个线程。我在作业中原意是要为其单独开一线程，但由于第二次作业的线程安全类bug，还是放弃了这样的思路。将会在下文介绍。

第一次作业之中由于对于多线程的只是还不是很熟悉，上手写的思路比较混乱，又因为第一次作业的复杂度较低，故并未思考到调度器存在的作用，因此直接在输入线程中进行分配，由于只有一部电梯，再分配的时候只是按找输入的类型(Morning, Random, Night)进行了划分，并未做其它的处理。

第二次作业中开始的时候引入了一个新的线程用来安置调度器，主要的作用便是接收输入线程送来的数据并向各个电梯分发数据。在分发数据的过程中会考虑到对于各部电梯计算的权重，取最优的分配。这样的思路在本地测试过程中并未发现什么错误，但当提交之后，会发现一些摇摆的bug（有时AC有时WA）我意识到这应该是线程安全的问题，当时时间紧没有来得及改正，强测过后拿到测试数据和测试报错，发现报错提示在调度器线程中的一个for-each循环内循环的容器被修改，然而我在检查循环体时只有单一的读操作，并未修改，而后发现该方法是一个static方法，被多个线程同时调用，可能发生了电梯线程在循环中读操作，而输入线程恰向容器中写 的修改操作而造成该错误。在多次思考后发现调度器的存在主要作用只是用来按照权重进行分配，并未对输入有优化操作，故考虑到线程安全，将调度器线程和输入线程合并（即将调度器调整为一个普通的类），这样便可以在做到分配的同时保证线程安全。

在第三次作业中由于存在换乘，故对调度器又提供了新的要求，即在输入结束后不能够立即结束输入线程，因为调度器还要时刻待命以接受换乘的乘客调度，必须要等到各个电梯运行完毕进入到等待状态后才能够一并结束。此时需要在run方法的输入循环结束后进入到调度器的待命循环，调度器和电梯线程相互唤醒。

调度器和程序中线程的交互主要是通过共享阻塞队列对象，调度器把请求队列中的请求分配给各个电梯对象的等待队列，进入到电梯等待队列内以备接送。

从功能设计与性能设计的平衡方面，分析和总结自己第三次作业架构设计的可扩展性

UML类图

classDiagram class Runnable{ <<interface>> abstract run() } class Elevator{ <<abstract>> -Reminder reminder - int speed -int maxBear -int destLayer -Scheduler scheduler -EleStatus eleStatus +void run() } class InputThread{ -WaitRequest mainQueue -Scheduler scheduler -boolean isInputOver -boolean endFlag +void run() } class AElevator{ } class BElevator{ } class CElevator{ -boolean careLowLayer -boolean careHighLayer } class Type{ <<enum>> A, B, C } class OutputLogic{ +void initialize() +void println() } class WaitRequest{ -int MAX_INS -BlockingQueue<Person> waitRequest } class Scheduler{ -int NumOfEle -WaitQueue mainQueue -ArrayList<Integer> eleIdList -HashMap<Integer,WaitRequest> waitRequestMap -HashMap<Integer,Elevator> eleMap -HashMap<Integer,Reminder> reminderMap } class EleStatus{ -UPPING -DOWNING -int eleId -Type eleType -boolean careLowLayer -boolean careHighLayer -int curLayer -int curDir -ArrayList<Person> passengers -WaitRequest waitQueue } class MainClass{ +void main() +void mainFunc() } class Reminder{ } class Priority{ } class Person{ +Up +DOWN -int id -int begin -int dest -int dir } MainClass ..> InputThread : <<create>> MainClass ..> Scheduler : <<create>> MainClass ..> OutputLogic : <<create>> Scheduler *--> WaitRequest Scheduler ..> Person : <<create>> Scheduler *--> Reminder Scheduler ..> AElevator : <<create>> Scheduler ..> BElevator : <<create>> Scheduler ..> CElevator : <<create>> Scheduler ..> Elevator Scheduler ..> Type InputThread ..|> Runnable InputThread *--> WaitRequest InputThread *..> Scheduler InputThread ..> Person AElevator ..> WaitRequest AElevator ..> EleStatus AElevator ..> Reminder AElevator --|> Elevator BElevator ..> Reminder BElevator ..> WaitRequest BElevator ..> EleStatus BElevator --|> Elevator CElevator ..> Reminder CElevator --|> Elevator CElevator ..> EleStatus CElevator ..> WaitRequest Elevator ..|> Runnable Elevator *--> EleStatus Elevator ..> WaitRequest : <<create>> Elevator ..> OutputLogic EleStatus *--> WaitRequest EleStatus *--> Person EleStatus *--> Priority

UML Sequence DIagiram时序图

sequenceDiagram Note over MainClass : MainThread Note over InputThread : InputThread Note over Elevator : EleThread MainClass ->> InputThread : start InputThread InputThread ->> Scheduler : create Scheduler loop add elevator Scheduler ->> Elevator : add Elevator end alt if A Elevator ->> AElevator : add AElevator Elevator -->> AElevator : notify AElevator else if B Elevator ->> BElevator : add BElevator Elevator -->> BElevator : notify BElevator else if C Elevator ->> CElevator : add CElevator Elevator -->> CElevator : notify CElevator end loop input != NULL InputThread ->> Scheduler : read request in Scheduler ->> Elevator : spearPersonRequest Scheduler -->> Elevator : notify end loop wait AElevator -->> AElevator : no waitRequest & passengers BElevator -->> BElevator : no waitRequest & passengers CElevator -->> CElevator : no waitRequest & passengers end loop have waitings && passengers Scheduler -->> Scheduler : no spear needs Elevator -->> Scheduler : notify Scheduler -->> Elevator : spear requests end

UML和类图与UML时序图如上所示。

在实验中的功能设计方面比较明确：

• 电梯线程主要负责运送乘客的逻辑
• 调度器主要负责分配乘客的逻辑
• 输入线程负责读入控制台输入并格式化

本次实验的性能设计上主要采用的是改进的SCAN算法，通过对上下楼层的扫描的优化实现本实验算法。在SCAN算法基础上的优化如下：

• 没有乘客请求时，电梯进入等待，不运行
• 向上扫描时捎带同方向、同一侧的乘客，每一层询问是否有请求并更新需要到达的最高楼层
• 向下扫描决策同上

调度器向各个电梯的分配请求算法如下（下列优先级递减）：

• 符合电梯运行层数具有最高优先级
• 乘客在同方向同一侧的电梯优先
• 请求等待人数、电梯中乘客较少优先

判断电梯运行楼层算法如下：

• A：只接送乘客在3-18层之间。
• B：只接受乘客起始层数为奇数的乘客
• C：负责接送1-3层，18-20层乘客

目前来看算法的表现极大的受到极端数据的影响，从一定程度上来说甚至有时候随机算法也要比优化后的算法模拟结果要好，出现了负优化的现象。

还是印证了那句话，在任何情况下都最优的算法是不存在的，只能是说不断地寻找合适的算法。

分析自己程序的bug

逻辑上的bug：

在第一次作业中出现了为将相关人员送到对应楼层的bug。

由于此次编程模块化分工更明确，所以可以按模块来检查，能够发现问题出现在电梯运送逻辑中更新最高（低）目的楼层模块。

多线程相关bug：

本次作业的逻辑结构较为简单，难点在于对多线程高并发情况下程序稳定性的考验，也就是要防止出现线程安全的问题。

同上文所述，本次的实验bug主要出现在第二次作业的测试中，由于引入了调度器线程而引起一个共享变量被两个线程同时操作的问题，从而引发了线程安全问题。

本次作业出现问题的类是Scheduler类，在上文的“锁的选择”和“调度器设计”部分已经详细介绍过出现的bug以及修改方法，在此处就不再重复了。

本次作业中并未出现因死锁而导致的bug，由于在设计思想上只用了一个单一的reminder类（对象）来进行锁、等待、唤醒的操作故在一定程度上大大简化了线程逻辑代码的编写，在第一次作业中印象里编码的早期出现过一次线程死锁问题，主要表现为程序运行卡滞，在对多线程进行调试后能够轻松发现是同时锁住了两个互斥的线程而引发的。

在第三次作业中有关线程相关的问题主要出在如何设计来保证输入线程在接受控制台输入结束后仍然待命接受换成乘客输入，这个问题也在上文的调度器设计中做出了相关介绍。

分析自己发现别人程序bug所采用的策略

本单元的作业中在设计逻辑和线程并发上都可能存在漏洞。

一方面可以根据自己在调试过程中找到的bug先总结自己的bug所代表的错误类型，然后以此类型为例构造样例测试。比如在本单元实验中出现的因为电梯逻辑未更新最高（低）目的楼层而引发的bug，可以据此构造一组，出现在电梯同一侧，但目的楼层不规律变化的乘客需求去测试。又例如有的同学在Night、Morning模式下可能会等待输入多组或者输入结束后才开始调度器分配乘客，所以可以采用单给一个乘客或乘客间时间间隔很大的样例来测试其程序能否正常运行。

对于线程安全的测试分析，在某种程度上与测试样例无关，可以分析他人代码查找贡献变量所在区域锁的设置，从逻辑角度分析其线程安全性。

本单元的测试和第一单元的测试重点不同，第一单元的测试重点在于代码细节的正确性，给定输入能否得到正确的输出，而本单元的测试重点可能更在于代码的运行稳定性，这要求高并发状态下程序的高鲁棒性。

心得体会

本单元体会便是：入门极难，入门后豁然开朗（才不是

第一次作业编码真的好难，完全不知道如何下手，不知道该怎么组织多线程，现在回望来看，还好吧，但是多线程目前只是入门了，还有很多知识要去学习巩固。

线程安全方面：

对共享变量的出现的定位很重要，要明确的知道它们都出现在你的代码中的哪些线程中，从而去思考使用到它们的线程有没有考虑对相应代码块上锁以及上锁后有没有造成死锁的情况。还有一点就是用的共享变量尽量越少越好，以减少代码的编码复杂度。所以从这样一个角度来看，我这一单元的作业做的还是不错的，借助了阻塞队列和自己标志用的Reminder类来进行线程间的互斥和同步。

还有一点，也是在和大树助教沟通中了解到的，锁住的代码块要越少越好，第一次作业中因为锁住的代码块内包含有输入的逻辑，因而导致了奇奇怪怪的错误，表现为电梯线程总是在输入结束后才开始执行，以此为戒吧。

层次化设计：

本单元层次化设计是基于功能模块的，总体上分为三大模块，输入模块，调度模块、电梯模块。模块化的设计思想确实让整体思路边得比较清晰同时在编码时可以让你专注于一个模块而不需要有其它的顾及，模块本身是相对独立的，有自己的稳定性，各个模块各司其职，在模块内只需要完成本模块需要完成的任务并留出对外接口即可，对于模块外的其他任务并不关心，这大大简化了整体编程的复杂度。

总之，这单元作业完成的还比较顺利，虽然也没有可以的去要求自己编写面向对象的代码，但是还是完成了两次代码的迭代开发，多线程的知识通过上网的了解发现还有很多内容我都没有应用到，有关设计思想等等，我会自行去了解和探索，把Java的基础打扎实。