第二单元作业的完成史，就是一部心酸的血泪史……

多线程的出现为我（们）打开一片广阔的天地，我也在这方天地摸爬滚打，不断成长！如果说第一单元之前还对Java语法有所了解的话，那么这单元学习多线程则完全是从0积累的一个过程。每一步，都走得很艰难！虽然我犯过很多错，但我很庆幸，我坚持到了最后！

写在前面

单线程：Java程序在虚拟机上运行，一个Java程序对应一个JVM实例，同时对应一个主线程（即main），程序入口从main进入，运行完毕从main退出。

多线程：顾名思义，即不止一个main线程，main线程有JVM创建，其他线程为用户自己创建，创建的方法包括继承Thread类extends Thread或者实现Runnable接口implements Runnable同一时刻程序中可能有多个线程在运行。

多线程的出现是为了提高效率，比如在一个程序中可以有两部分同时工作，而不必等待一个工作完成后再开始另一个工作。如果这两个线程之间没有交互，即相互之间可以各运行各的，这当然是最好的情况，但我们都知道物以稀为贵，好情况当然不容易出现，所以在我们的程序中经常会需要不同线程之间的交互。而除此之外，同样带来的还有线程安全问题。

多线程交互之生产者消费者模式：托盘是传播信息的媒介和完成控制线程的功能，生产者向托盘对象存入生产的货物，消费者从托盘里取走相应的货物 ，“货物”的放置和提取控制均由托盘的状态来决定。

多线程交换之单例模式：static关键字保证了程序运行中只存在一个由此创建的对象，那么所有涉及此对象的的方法都是基于同一个对象在进行。

互斥控制：任何时刻只允许一个线程获得访问/执行权限，使用synchronized关键字，修饰对象时表示任意时刻只能允许一个线程对此对象做操作；修饰方法时，表示任意时刻只允许一个线程调用此方法。

多线程编程的详细设计策略

从第三次作业讲起：

第三次作业是我这三次作业中架构比较清晰，却也翻车最严重的一次作业。

强测38.25分的成绩，真的像极了讽刺！

线程：

• 共五个线程。

• 主线程main程序中创建了Input线程和Dispatcher线程，在Dispatcher线程中另外创建了三个电梯Elevator线程。

存储队列：

• 首先创建了一个全局类Waiting类，本质上是Vector队列，用于存储所有读进来的请求。Input线程向Waiting队列内添加请求元素，Dispatcher线程负责从Waiting类中取元素，然后根据请求分发给不同的电梯线程。

• 每个电梯线程中有两个队列，一个队列用于存储从分配器分配到电梯线程的所有请求队列，一个队列用于存储电梯线程中正在处理的请求队列。

结束条件的判断：

• 主线程main函数结束：main函数主要用于创建新的线程和存储队列，程序是从上往下执行的过程，执行完成后即退出。

• Input线程结束：当读入结束时request == null，同时Input线程传递出一个读入结束信号。

• Dispatcher线程结束：三个电梯线程均处理完毕；Input线程读入结束；同时存储所有请求队列的Waiting序列为空。

• Elevator线程结束：三个电梯均处理完成；Input线程读入结束；同时存储所有请求的队列中的Waiting序列为空。

多线程设计：

• 线程内部采用while(true) + sleep(sleepTime)结构

• Input线程负责接受输入请求，将请求加入Waiting队列中；

• Dispatcher调度器线程负责分发请求，即从队列中移出请求到电梯队列中；

• 电梯队列负责处理从Dispatcher调度器分发来的进程，处理完毕后即处理完毕，否则，如果是需要换乘的请求要将其重新加入Waiting队列中。所以电梯线程和其他线程耦合度比较高，既需要处理请求，还可以新增请求。

• 线程安全：各线程同时运行，在涉及到访问Waiting队列的操作时（包括add和delete），需要将Waiting内部的Vector队列加锁（synchronized）。保证add和add不能同时进行，add和delete不能同时进行，delete和delete不能同时进行。另外，在获得Waiting队列中元素数量时（或者是判断当前队列是否为空时），也不能同时进行add或delete操作。

Dispatcher调度器的分发机制：

• 当一个请求可以被一个电梯单独完成且此电梯容量未满时，将请求加入这个电梯

• 第一步进行完后，判断如果一个请求需要借助电梯换乘才能完成，那么判断此请求开始楼层在哪部电梯的运行区间内，如果此电梯容量为满，则将该请求加入此电梯

• 通过上面两个条件可以看出，电梯的分配策略十分简单。每个电梯内处理的请求包括它自己能单独完成的请求和必须需要电梯换乘完成且出发楼层在该电梯运行范围内的请求

电梯的工作机制：

• 电梯实时记录当前楼层。即通过stay变量记录电梯执行完请求后停留的位置，stay初始化为1，之后在电梯运行过程中不断更新。

• 电梯首先加入第一条要处理的请求，此请求的选取是所有请求的出发楼层中离当前楼层最近的一条请求。

• 在加入第一条请求后，判断之后电梯要运行的方向，上行或者下行，电梯在运行过程中捎带请求。

• 上行则将要一直上升到顶层，在此电梯正在处理的请求队列为空时跳出；同理，下行则将要一直下降到最底层，在此电梯正在处理的请求队列为空时跳出。

• 在运行到1层或者15层时，判断当前处理请求队列中有无换乘请求，有的话弹出请求，重新加入Waiting队列中，之后就交给Dispatcher调度器重新处理了。我处理换乘请求的方式真的非常无脑

第二次作业：

本次作业和第三次作业在处理策略上最大的不同在于调度器没有单独作为一个线程，由于只有一部电梯，且这部电梯没有类似第三次作业的一些限制，因此读进来的请求直接读入电梯中，交由电梯内部处理（这也导致我第三次作业重构的非常爽）。

线程：

• 共三个线程。

• 主线程main程序中创建了Input线程和Elevator线程，Input线程负责读入请求，Elevator线程负责处理请求。

存储队列：

• 在程序中存在一个调度器类，此调度器类不是一个线程，甚至可以把它只当作一个中间媒介，或者说是一个用来存储所有已读进请求的队列。

• 每个电梯内部有一个队列，用来存储电梯中正在处理的所有请求。

结束条件的判断：

• 主线程main函数结束：main函数主要用于创建新的线程和初始化时间戳，程序是从上往下执行的过程，执行完成后即退出。

• Input线程结束：当读入结束时request == null，同时Input线程传递出一个读入结束信号。

• Elevator线程结束：当电梯所有请求处理完毕，且调度器队列中请求为空，且输入完成则线程结束。

多线程设计：

• 线程内部采用while(true) + sleep(sleepTime)结构；

• 强行使用单例模式；

• Input线程负责接受输入请求，将请求加入Dispatcher队列中；

• Dispatcher调度器只作为一个队列存储所有读进来未处理的请求

• 电梯队列负责处理从Dispatcher调度器取用请求，然后电梯内部进行处理。

• 线程安全：由于本次设计中采用单例模式，所有线程的操作都是基于同一个对象在处理，因而将创建出的单例对象加锁即可保证线程安全，在任意时刻只保证有一个线程对此单例对象做修改。

电梯的工作机制：

• 此次作业要求是ALS可捎带调度电梯。

• 电梯每次从Dispatcher队列中首先取出第一个请求，第一个请求的选择是选择所有请求出发楼层中离当前电梯最近的一个请求。

• 由取到的第一个请求电梯选择上行或者下行，在上行或者下行的过程中一直上行或者下行，运行过程中不断加入新的请求，直至当前处理队列为空。

• 重新开始第二步，直到线程结束。

第一次作业：

第一次作业说起来比较复杂，也很羞愧。由于刚开始接触时对多线程理解不深，所以自己首先写出一个程序，但实际上这只是一个简单的单线程程序，后来自己又撸出来一个多线程程序，也成功过了课下测试，但由于当时对自己写的多线程程序不自信，所以最后还是提交的单线程。由于第一次作业真的比较简单（强测满分，互测无问题真希望这样的作业多来几沓），考虑课程组只是为了让我们熟悉多线程，所以本部分只简单说下我的思路吧。

• 两个类，Elevator类和Request类

• Elevator类用于处理请求，Request类用于储存请求

• 主线程main函数中用于接受输入请求

基于度量的程序结构分析

名词解释：

类：

• Ocavg：平均方法复杂度

• WMC：带权方法平均复杂度

方法：

• ev(G)：核心圈复杂度，表示一个方法的结构化程度，值越大则程序结构越病态

• iv(G)：方法设计复杂度，表示一个方法与其调用的其他方法的紧密程度，值越大则越紧密

• v(G)：圈复杂，表示一个方法穷尽每一条路径所需要的次数，也就是循环复杂度

第一次作业：

1. 类图

1. 协作图

　　3. 度量分析

Class	OCavg	WMC
Elevator	1.29	9
Main	3	3
Request	1.25	5

Method	ev(G)	iv(G)	v(G)
Elevator.Elevator(PersonRequest,int)	1	1	1
Elevator.doorClose(int)	1	2	2
Elevator.doorIn(int)	1	1	1
Elevator.doorOpen(int)	1	2	2
Elevator.doorOut(int)	1	1	1
Elevator.elevatorMove(int,int)	1	3	4
Elevator.run()	1	1	1
Main.main(String[])	3	3	3
Request.Request()	1	1	1
Request.addRequest(PersonRequest)	1	1	1
Request.getRequest()	1	1	1
Request.getStay()	2	2	2

第二次作业：

1. 类图

1. 协作图

1. 度量分析

Class	OCavg	WMC
Dispatcher	1	7
Elevator	3.22	58
Input	2	4
Main	1	1
Singleton	3	3

Method	ev(G)	iv(G)	v(G)
Dispatcher.addRequest(PersonRequest)	1	1	1
Dispatcher.deleteQueue(PersonRequest)	1	1	1
Dispatcher.getEnd()	1	1	1
Dispatcher.getQueue()	1	1	1
Dispatcher.getRequest(int)	1	1	1
Dispatcher.isEmpty()	1	1	1
Dispatcher.setEnd()	1	1	1
Elevator.Elevator(Dispatcher)	1	1	1
Elevator.PopCurRequest(int)	1	4	4
Elevator.addOrDeleteRequest(int,int)	1	4	4
Elevator.arrive(int)	1	1	1
Elevator.close(int)	1	2	2
Elevator.getFirstRequest()	1	9	10
Elevator.getSubRequest(int,int)	1	7	7
Elevator.in(int,int)	1	1	1
Elevator.isGetSubRequest(int,int)	6	5	8
Elevator.isPopCurRequest(int)	3	2	3
Elevator.move()	1	2	2
Elevator.open(int)	1	2	2
Elevator.out(int,int)	1	1	1
Elevator.run()	4	11	12
Elevator.work(int,int)	3	1	3
Elevator.workDown()	3	2	3
Elevator.workStart(int,int)	1	2	2
Elevator.workUp()	3	2	3
Input.Input(Dispatcher)	1	1	1
Input.run()	3	4	4
Main.main(String[])	1	1	1
Singleton.getInstanceof()	1	1	3

第三次作业：

1. 类图

1. 协作图

1. 度量分析

Class	OCavg	WMC
Dispatcher	3.14	22
Elevator	3	72
End	1	10
Input	3	3
Main	1	4
Waiting	1	6

Method	ev(G)	iv(G)	v(G)
Dispatcher.Dispatcher()	1	2	2
Dispatcher.analyse(int,int,int,PersonRequest)	2	4	4
Dispatcher.dispatchTaskToElevator()	4	10	11
Dispatcher.getWaitingQueue()	1	1	1
Dispatcher.isEndAll()	1	1	1
Dispatcher.isInArray(int,int)	3	1	3
Dispatcher.run()	4	11	11
Elevator.Elevator(int,int,int,Dispatcher)	1	1	1
Elevator.addRequest(PersonRequest)	1	1	1
Elevator.arrive(int)	1	1	1
Elevator.changeElevator(int)	3	5	6
Elevator.checkAtFloor(int,int)	5	19	21
Elevator.close(int)	1	2	2
Elevator.getFirstRequest()	1	4	4
Elevator.getStatus()	1	1	1
Elevator.getStay()	1	1	1
Elevator.in(int,int)	1	1	1
Elevator.isEmpty()	1	2	2
Elevator.isEnd()	1	1	1
Elevator.isFull()	1	1	1
Elevator.isInArray(int)	3	1	3
Elevator.move()	1	2	2
Elevator.open(int)	1	2	2
Elevator.openFirst(int,int)	1	9	10
Elevator.out(int,int)	1	1	1
Elevator.run()	4	10	10
Elevator.setEnd()	1	1	1
Elevator.workAtFloor(int,int)	3	3	6
Elevator.workDown(PersonRequest)	3	3	5
Elevator.workFromToFirst(int,int)	1	6	6
Elevator.workUp(PersonRequest)	3	3	5
End.getEndElevator1()	1	1	1
End.getEndElevator2()	1	1	1
End.getEndElevator3()	1	1	1
End.getEndInput()	1	1	1
End.getEndWaiting()	1	1	1
End.setEndElevator1(boolean)	1	1	1
End.setEndElevator2(boolean)	1	1	1
End.setEndElevator3(boolean)	1	1	1
End.setEndInput(boolean)	1	1	1
End.setEndWaiting(boolean)	1	1	1
Input.run()	3	5	5
Main.getEnd()	1	1	1
Main.getWaitingRequests()	1	1	1
Main.main(String[])	1	1	1
Main.setEnd()	1	1	1
Waiting.addRequest(PersonRequest)	1	1	1
Waiting.deleteRequest(PersonRequest)	1	1	1
Waiting.deleteRequest(int)	1	1	1
Waiting.findRequest(int)	1	1	1
Waiting.isEmpty()	1	1	1
Waiting.size()	1	1	1

基于SOLID原则的评价

1. 单一职责原则（SRP）：一个类有且只有一个职责，将类变得简单灵活。

   我认为此原则在我的程序中有较好的体现，通过定义的方法名即可轻松判断出该函数实现的功能。

   但通过上面的度量分析也可发现问题，即每个线程中run方法承载的功能较多，因为我在写程序过程中run作为线程的入口，为它赋予了太多的功能。

2. 开放封闭原则（OCP）：一个类应该对扩展开放，对修改关闭。

   当某个类功能需要拓展时，应该对这个类进行扩展而不是对类进行修改。我最这个原则理解不深，但我认为自己在这方面有所注意（或者说之后着重理解下）。以第三次作业为例，我的三个电梯由是同一个类产生的，只不过根据传入电梯构造函数的参数不同所以创建出的电梯有所不同。

3. 里氏替换原则（LSP）：派生的子类应该是可替换基类的，也就是说任何基类可以出现的地方，子类一定可以出现。

   我的程序中只在创建线程时用到继承Thread类，其他地方没有用到继承。

4. 接口隔离原则（ISP）：类不应该*依赖他们不使用的方法，也就是说一个接口应该拥有尽可能少的行为，它是精简的，也是单一的。

   为不同的场景设置不同的接口，而不是设置一个接口然后在接口内部根据不同的场景实现不同的功能。在本次作业中，没有用到接口的使用。

5. 依赖倒置原则（DIP）：高层模块不应该依赖低层模块，相反，他们应该依赖抽象类或者接口。

   如果高模块紧耦合低层模块，那么当低层模块改变时，高层模块也会对应改变。通过上面度量图分析，还是发现run模块中和其他模块耦合度较高。

自己程序的BUG

第一次作业

第一次作业没有出现任何bug；

第二次作业

第二次作业强测出现1个bug，互测没有出现bug。

分析强测bu*生的原因：其实是个非常大的问题，但由于自己的程序其他地方设计的还不错，而且强测数据没有很大地卡到我程序的这个bug，因而只出现一个bug。

这个bug是因为我采用了半暴力轮询的方式，强测第三组数据爆炸，当时我没有意识到这可能是存在的暴力轮询，而是以为自己的优化策略太差所以导致超时，于是我在bug修复阶段加入了简单的倒车功能，成功修复此bug。（没有认识到第二次作业bug的本质是导致我第三次作业翻车的根本原因）

第三次作业

第三次作业的成绩真的哭了，强测38.25分，所有点全都卡在CPU_TIME_LIMIT_EXCEED，包括互测被测出的bug也全都是因为CPU_TIME_LIMIT_EXCEED。

由于偷懒，自己采用的是while(true) + sleep()的方式，而我sleep的情形只在if条件成立的情况下sleep，这就导致如果程序一直在跑但没有执行完无法处理新的请求情况下，程序会在while(true)里面一直循环而没有sleep，就导致了暴力轮询的错误。

互测策略

觉得当代码提升复杂度之后，我越读代码越来越懒了，而且由于自己水平有限，在阅读代码时只是去学习别人代码中认为写的不错的地方，而不是在找他们逻辑上的bug，自己找出的别人的bug都是通过手动搭的评测姬扫出来的。

第一次作业

第一次作业考虑到作业的简单性，没有试图去找别人bug；

第二次作业

第二次作业搭建一个简单的评测姬，评测标准在检测程序是否能正常执行完毕和人进出楼梯的操作是否在开关门之间进行；互测阶段找到别人6个bug，但最后只得到1.53333分，也说明了通过评测姬扫出的bug可能包含许多同质bug……

第三次作业

第三次作业搭建了很水的评测姬，生成随机数据然后检测程序能否正常运行结束，如果报异常或者无法运行结束则说明程序出现bug。由于自己第三次作业处于C组，所以大家程序可能问题确实比较多，关于为什么会报异常或者无法正常运行结束应该是出现了线程安全的问题。

心得体会

线程安全

• 线程安全是在多线程中极容易出现的一个问题，关键在于理清同步互斥的逻辑关系

• 线程安全通常出现在访问共享对象或者同时对某个共享对象做修改，这就要求我们像类似add和delete的操作不能同时对共享对象做操作，必须加锁锁住共享对象或者方法。

  以下面我对Waiting共享对象的操作代码为例：

  public synchronized void addRequest(PersonRequest request) {
          synchronized (waitingQueue) {
              waitingQueue.add(request);
          }
      }
      
      public synchronized void deleteRequest(PersonRequest request) {
          synchronized (waitingQueue) {
              waitingQueue.remove(request);
          }
      }
      
      public synchronized void deleteRequest(int key) {
          synchronized (waitingQueue) {
              waitingQueue.remove(key);
          }
      }
      
      public boolean isEmpty() {
          synchronized (waitingQueue) {
              return waitingQueue.isEmpty();
          }
      }
      
      public int size() {
          synchronized (waitingQueue) {
              return waitingQueue.size();
          }
      }
      
      public PersonRequest findRequest(int key) {
          synchronized (waitingQueue) {
              return waitingQueue.get(key);
          }
      }

设计原则

• 高内聚，低耦合

• 基于SOLID原则

耦合性：块间联系。模块间联系越紧密，耦合性越强

内聚性：块内联系。模块内各元素联系越紧密，内聚性越强

在用程序写一段模块时，首先需要思考三个问题，并不是内聚性越强、耦合度越低就一定越好。

• 模块的功能

• 模块的逻辑

• 模块的状态

设计原则需要考虑

1. 线程安全

2. 避免无谓的加锁

3. wait，notify是比轮询或者while(true) + sleep更有效的方法（在我看来）

其他

OO真是一门多学科交叉的学科滑稽，我们在写评测姬测程序的过程中，即使只是简单的评测姬也在锻炼我们写脚本或者python程序的能力（

这次多线程作业真的吃了大亏，不过现在自己对多线程有了一定认识，也认识到多线程的奇妙之处，一次作业的终结也是下一次作业的开始，学习永远在路上。路还很长，加油吧！