BUAA-OO-第二单元总结

OO第二单元总结

一、第五次作业

1.1 设计策略与架构

• 第五次作业要求的是完成设计支持一架傻瓜电梯的电梯系统。考虑到需要数据结构存放所有的请求，因此构建了FloorRequests类用来存放所有的请求，其次存放请求与提取请求借鉴于生产者消费者模式，设计Input类用于不断地读入新请求并存储到队列中，设计Scheduler类用于提取队列中指令并且指挥电梯工作。Elevator类是一个纯电梯类，用于存放电梯的基本信息以及完成电梯的基本工作（例如开关门，上下人），具体工作需要Scheduler来指挥。
• 因此第五次作业总体设计了两个线程，Input线程用于往队列中存放请求，Scheduler线程用于从队列中拿取请求，并根据一定的调度原则指挥Elevator工作。Main函数仅完成启动两个线程的任务。具体类的设计原则见类图分析。
• 在调度工作策略上，考虑到后续电梯作业可能涉及的优化调度工作，因此在第五次作业事先将电梯设计为能够完成原子化动作的电梯，即能够一层一层移动并且look请求的工作，便于后续作业优化。同时也对FloorRequests类进行优化，使其能够完成楼层对请求的索引需求。

1.2 类图与分析

FloorRequests类：

• 属性：

  • floors为一个ArrayList，能够以楼层为索引，找出对应楼层的请求（为一个存放PersonRequest的HashSet)

• 方法：

  • init方法：初始化floors
  • isEmpty方法：返回列表是否为空
  • hasPerson方法：返回对应楼层是否有请求
  • pull方法：将某一楼层的请求从队列中取出
  • push方法：往队列里添加请求
  • findMinFloorRequest方法：寻找最低的请求楼层
  • findMaxFloorRequest方法：寻找最高的请求楼层

• 上述方法中init方法需要在线程开启前进行初始化，中间四个方法用于返回队列信息以供调度器控制电梯上下人，最后两个方法用于优化调度策略，寻找电梯主请求。

Elevator类：

• Elevator类设计之初便是想将其设计为一个单纯的电梯类，仅存放电梯的基本信息和完成一些简单的原子化操作，而不具备控制功能（即只是一个没有CPU的电梯），因此Elevator的属性和方法均设计的较为简单，仅是为Scheduler提供信息。

• 属性：

  • persons为一个ArrayList，储存结构类似于FloorRequest的floors，也是一个以楼层为索引的请求列表。
  • nowfloor为一个整型，代表电梯现在所处楼层。
  • state存储电梯当前状态，共有up，down，wait三种状态。

• 方法：

  • isWantToGo方法：返回电梯中是否有人去往某一层楼
  • move方法：电梯移动，根据state来做相应的原子化动作（上下一层）
  • changeState方法：改变电梯状态
  • getIn方法：将请求送入电梯
  • getOut方法：将请求送出电梯
  • findMaxFloorRequest方法：寻找电梯中的最高请求楼层
  • findMinFloorRequest方法：寻找电梯中的最低请求楼层

• 上述方法中前续方法均是为调度器Scheduler提供操作电梯的方法，最后两个方法返回值供调度器综合优化调度策略。

Scheduler类：

• Scheduler类是Scheduler线程类，完成电梯调度器线程的工作。

• 属性：

  • e1为调度器所注册的电梯
  • in存储Input线程，用于监视线程

• 方法：

  • begin方法：控制电梯从wait状态转变为up或down方法，即完成电梯从无指令到有指令的状态变化，并通过分析新来请求决定电梯启动方向。
  • work方法：控制电梯上下一层并且上下客，并且根据分析后续请求决定电梯下一时刻状态。
  • run方法：线程主方法，利用while true循环控制电梯完成原子化操作，并且监视Input及时结束线程。

Input类：

• Input类是Input线程类，完成读入请求的工作。

• 属性：

  • end保存Input是否已经结束

• 方法：

  • run方法：线程主方法，通过不断读取并且存入队列列表中。
  • isEnd方法：返回Input是否已经结束。

1.3 时序分析与多线程控制

• 第五次作业的时序问题主要在设计好Scheduler的时序。第五次作业并没有完全采用傻瓜调度策略，而是做了简单的捎带优化。首先Scheduler中控制电梯完成的是原子化操作，并且在每次完成完操作后会根据后续请求分析下一时刻电梯运行状态。run方法中的while true都在不断询问并且完成原子化操作。具体时序如下图：

• 关于控制第五次作业的线程安全问题，由于考虑到仅有一位生产者与一位消费者，并不会出现多个消费者争抢同一请求的情况，因此没有利用notify方式解决，而是利用while轮询来等待下一个请求输入，因此CPU时间开销大。
• 对于线程结束的控制，Input线程在读取到EOF后会设置标志位end并且break，Scheduler线程则通过while true中的每一次轮询来抓取end标识，当end有效并且队列为空并且电梯无人，Scheduler线程break。
• 因此第五次作业多线程控制上没有使用任何的synchronize和notify语句，而是利用大量CPU时间轮询的方式来保证线程安全。

1.4 分析bug与性能

• 第五次作业在公测和互测中均没有发现bug。
• 在性能上，缺陷在于通过牺牲大量CPU时间轮询来保证线程安全，浪费了一定的计算时间与CPU资源。其次没有对输入扰动做一定的处理。当在同一时刻发来多条从同一楼层出发的指令时，若电梯恰巧正在当前楼层，会立即开始工作，因此会导致部分指令尚在IO处理阶段，而电梯已经带着前半部分指令离开了楼层，导致后半部分指令不能被及时抓取并执行。
• 对于作业复杂度，部分复杂度分析表如下：

• 根据复杂度分析，可以得到复杂度较大的方法主要体现在Scheduler类的begin方法和run方法中。查看begin方法，由于begin方法实现的是设置初始电梯运作方向，根据算法需求，需要分析整个需求列表来决定初始化方向，因此if语句较多并且对else的处理并不完全。而对于run方法，由于需要不断的轮询以及判断是否运行到结束条件，因此while true语句中嵌套了许多if和while语句。但对于轮询使用while语句并不是必须的，因为外部就是一个while true语句，而在处理轮询前后均判断了一次是否需要break，这也是不必须的，因为while true必定会引导程序再次判断且间隔不远，因此在设计中这一点可以作为设计优化点，即减少轮询过程使用while语句以及在轮询前后不要重复判断是否需要break。

二、第六次作业

2.1 设计策略与架构

• 第六次作业在第五次作业的基础上新增了捎带要求，并且更改了楼层要求，同时要求CPU时间不能够超过10秒。因此总体上的架构和第五次架构基本一致，但做了一定量的架构优化。对于FloorRequests类构建成了单一对象的方式，在init后使用getInstance方法获得对象。并且在Elevator类和FloorRequests类添加了楼层到ArrayList索引映射的函数。
• Scheduler依旧完成调度电梯工作，并且调度算法同第五次作业一致，即捎带当前楼层所有请求并且控制电梯保持惯性移动，直到当前方向没有请求。具体调度策略见时序分析。但根据CPU时间要求，添加了synchronize语句以及wait方式来控制Scheduler在不需要的时候进入wait状态，而等待Input线程notifyAll进入下一步工作。

2.2 类图与分析

FloorRequests类：

• FloorRequests类的设计方式和第五次作业相似，在原有结构上新增了部分属性：

• 属性：

  • maxfloor和minfloor用于保存楼层的最高层和最低层
  • floors和第五次作业一致，但索引不是单纯的楼层，而是楼层的映射
  • floorRequest用于存储静态变量，保证单一对象

• 方法：

  • 方法与第五次作业基本一致，下述介绍新增方法
  • getInstance方法：返回静态FloorRequests对象
  • floorToIndex方法：private方法，用于完成楼层向列表索引的映射。

• FloorRequests类新增了楼层索引映射，和提供了单一对象的方式。

Elevator类：

• Elevator类的修改方向和FloorRequests类修改类似。

• 属性：

  • 新增maxfloor和minfloor，保存电梯能到达的最高楼和最低楼。

• 方法：

  • 新增floorToIndex方法，完成楼层到索引的映射。

• Elevator仅修改楼层映射，其余实现方式和第五次作业一致。

Scheduler类：

• Scheduler类依旧完成对电梯的调度控制工作，调度策略与上一次作业一致，但需要实现wait和notifyAll机制以免浪费CPU时间，因此在此前轮询的语句进行了修改。
• 此前仅不断轮询电梯状态和队列状态来判断是否结束，而本次作业需要在轮询时询问到不需要工作时，Scheduler需要进入wait状态，因此需要在满足非结束且电梯不需要工作的条件下对Scheduler线程进行wait。但为了保证线程安全性，在轮询判断语句之前需要加上synchronize锁，确保轮询时刻轮询的条件不会被改变，以免进入死wait状态。

Input类：

• 类似的，为了配合Scheduler类完成wait和notify机制，需要Input类在读取到新信息的时候对Scheduler进行notify，因此Input线程中，无论读取到新请求或是EOF，均需要对Scheduler进行notify，以提醒电梯工作以及结束。

2.3 时序分析与多线程控制

• 由于调度策略与上一次作业一致，采用同楼层捎带方式，因此时序一样。

• 关于捎带策略：采取的是捎带同楼层的所有请求，即捎带当前电梯所在楼层的所有请求。
• 关于运行策略：电梯在工作状态始终保持惯性进行运作，即假设当前状态为up，则电梯一致保持up状态进行运作并且捎带，直至电梯到达最高请求楼层
• 关于改变状态策略：当电梯到达最高请求楼层或者最低请求楼层后，会分析电梯内或队列是否还有未完成请求，若有，则改变电梯为相反方向，否则电梯进入wait状态。
• 关于电梯启动策略：对于启动后的方向，采用的是最短最远请求方向优先的方式。即遍历楼层请求，若楼层中的最低请求比最高请求离当前电梯近，则初始方向为down，否则为up。
• 对于多线程安全问题，由于此次作业采用了wait和notify机制来减少浪费CPU时间，因此在wait时候需要非常小心，防止出现死wait而叫不醒线程的情况，即要防止在判断完条件之后wait之前Input线程已经notify，从而造成没有及时接收到notify而造成死wait。防止出现这一情况，就需要在判断条件和wait锁在一起，避免中间线程调度调走。

2.4 分析bug与性能

• 第六次作业在公测和互测均没有发现bug。
• 在性能上，假设对于实际情况的模拟，在大量随机数据面前，而非构造数据，可以明显看出当前捎带算法效率比ALS较优，因为捎带原则为同楼层即捎带，而非ALS同方向捎带，因此可以减少电梯改变方向后对同一楼层开两次门上不同需求而锁浪费的时间。此外每次启动寻找最短最远距离启动，避免了走远路而浪费了时间。
• 在设计复杂度上，由于第六次作业和第五次作业设计基本一致，因此复杂度上面体现的问题基本相似，以下为部分方法复杂度分析表：

• 类似的，begin方法由于算法需要，if语句多，复杂度高，run方法由于轮询多，并且while true中嵌套while，复杂度高，work方法由于在判断转向时候需要分析楼层信息，if语句也比较多，对于不同情况改变形式不一样，因此复杂度也较高。

三、第七次作业

3.1 设计策略与架构

• 第七次作业需要支持多电梯，并且不同电梯停靠楼层不同，且有容量限制，因此较前几次作业，架构修改程度大。
• 首先对于不同电梯到达楼层不同的问题，需要修改Elevator类的persons结构，改为使用HashMap来存储，索引为楼层字符串。由于楼层不同会导致前往某一楼层使用一台电梯无法完成任务，因此需要对request进行拆分。根据实际模拟，拆分方式不由电梯调度决定，有人来决定，即重写PersonRequest类，构建RealPersonRequest类，将PersonRequest进行拆分，若能够直达，则不拆分，若不能直达，则根据最先到来的电梯进行拆分。具体方式见时序分析。
• 其次对于容量限制问题以及不同电梯的上升时间不同问题，需要在构建Elevator类对象时明确电梯种类，因此在构造方法中要支持对三种电梯的构造，并且为了支持电梯容量限制，需要构造isFull方法来供电梯调度器决定是否接着上人。
• 再者，由于此次作业为三部电梯，而非一部，因此原本的Scheduler类已经不能支持三部电梯，而只支持一部电梯，因此把Scheduler类改名为ElevatorCore类，即电梯内核类，其控制范围依旧是一部电梯，因此这样ElevatorCore类的结构不需要做太大的修改。
• 因此本次作业线程类为Input类以及三个ElevatorCore类对象，总共四个线程，Input线程用于往队列中加request，而ElevatorCore则指挥各自的电梯工作。指挥策略为若当前电梯可以完成队列中某一人的当前需求，则前往完成，若队列中没有需求电梯可以完成，则等待，因此大题架构和前几次作业相同。

3.2 类图与分析

• 本次作业类修改较大，重写了PersonRequest类，并且更改了Elevator存储request的构架，其他变动不大。

ReadPersonRequest类：

• 该类为PersonRequest的重写类，能够将PersonRequest进行智能拆分，并且能够返回当前状态request的需求。

• 属性：

  • e1，e2，e3为三个电梯对象，request能够监视电梯能够到达的楼层，来为自己的行程选择楼层，并且能够通知电梯为自己未来的行程做准备。
  • splitList为需求可能分割的列表，根据第一步接送的电梯来分割请求。
  • splitNotify为需求分割的notify电梯列表，根据第一部接送的电梯来告知第二部电梯做准备。
  • hastake为一个flag标识，代表该request已经被搭载过一次了（限制所有请求最多搭载两次）

• 方法：

  • getSplit方法为构建splitList列表方法，在构造方法中被调用，即决定该request可能的分割方向
  • check方法为电梯提供，询问该request当前是否可以搭乘该电梯
  • getInEle方法为修改request方法，表示该request已经进入电梯，需要修改hastake和当前行程。
  • getOutEle方法为修改request方法，根据上一次搭乘的电梯修改request下一行程。

• RealPersonRequest类的属性和方法设定主要是为了模拟现实生活中人的真正意愿。一个请求可以拆分为很多种方式完成，如果可以直达则直达，否则则拆分。request拆分灵活，根据第一部来接送他的电梯对请求进行拆分，决定自己当前的行程和下一时刻的行程，并且有getInEle动作和getOutEle动作，从而告诉自己也告诉电梯当前行程和下一时刻行程。

FloorRequests类：

• 根据重写的RealPersonRequest类，需要重新构建新的FloorRequests类。并且需要修改存储结构，满足对不同方向的请求的存储。

• 属性：

  • 修改floors存储结构，为一个ArrayList，以楼层映射到的索引为索引，每一个索引对应一个HashMap，HashMap中存储up的请求和down的请求，请求以ArrayList存储。

• 方法：

  • 修改hasPersons方法，支持对不同种电梯返回是否有可搭乘对象的方法，并且支持对方向的搜索
  • 修改pull方法，由于本次作业限制了电梯的容量以及电梯种类，因此pull过程中需要一个一个pull，而不能对一个HashSet一起pull。

• 总的来说FloorRequests类修改主要在方法能够支持对不同种类电梯的请求，并且能够支持对单个request对象的操作，以及对不同方向的操作。

Elevator类：

• 本次作业Elevator类也和之前设计有些许不同，主要改动在修改persons存储方式修改。

• 属性：

  • maxfloor和minfloor：电梯可以到达的最高层和最低层
  • upTime：电梯移动一层的时间
  • cango：电梯可以停靠的楼层列表
  • persons：存储电梯内的请求，为一个HashMap，以楼层字符串为索引，索引得到一个HashSet，存储请求。
  • maxcontain：表示当前电梯的最大容量
  • contain：表示当前电梯内人数

• 方法：

  • 修改构造方法，使其能够注册三种不同电梯
  • setTarget方法：设置虚目标，电梯空闲时往虚目标走。
  • getTarget方法：return vTarget
  • isFull方法：返回电梯是否已满
  • 其余方法和之前相似

• 电梯类的修改主要是为了能够满足注册不同种类的电梯，并且修改persons存储结构，满足支持不同注册楼层的列表，同时支持对容量限制。

ElevatorCore类：

• 本次作业的ElevatorCore类和前几次的Scheduler类相似，都是可以调度控制一架电梯，但又有不同在于可以监视其他电梯来达到结束线程的条件。每一个电梯各有一个Core，互不干扰，可以抢占同一个request，先到先得，前提是request同意乘坐该电梯。

• 属性：

  • 和前几次作业的Scheduler相似，增加e2，e3监视其他电梯工作状态。

• 方法：

  • 修改work方法，使捎带有条件，不仅不能是电梯超载，而且只能捎带同方向请求
  • closeToTarget方法：控制电梯靠近vTarget的方法
  • 修改run方法：若电梯空闲，则使其靠近vTarget

• 修改Core有两个目的，第一修改捎带方式为同方向捎带，并且在getIn时候要一个一个getIn防止电梯超载，其次在电梯在等待状态时，需要指挥电梯前往vTarget（vTarget设置为RealPersonRequest设置，意在告诉第二部电梯提前前往中转站）

Input类：

• 本次作业Input类设计和前几次相同，因此此处不再重述。

3.3 时序分析

• 第七次作业实现方式和前两次作业有些许不同。首先重写了PersonRequest，实现了request能够对自己的请求进行拆分，其次修改了电梯调度方式，将捎带更改为同方向捎带，再者线程增加为三个电梯线程和一个Input线程。鉴于之前的Scheduler类均是支持一个电梯的，因此本次不做太大改动，更改名称为ElevatorCore，依旧控制一台电梯，三个Core共存，互相监控争抢任务，实现本次作业。
• 首先对于指令拆分，本次作业为了实现简便，并且高度模拟现实，将request的拆分交给RealPersonRequest类完成，即请求自己拆分请求。拆分的规则规定为：若可以直达则不拆分，若不能直达则根据第一部前来接送的电梯进行拆分，最多仅进行一次拆分（即两程），考虑到这点的原因是尽可能实现动态拆分，从而从一定程度上提高性能。RealPersonRequest对象创建时就进行拆分，若不能直达，则构建一个拆分HashMap，索引为电梯编号，内容为拆分楼层（共四个，第一程出发与终点，第二程出发与终点）。再者RealPersonRequest类实现了check方法，供电梯询问自己是否可以接送该请求，条件是当前电梯可以满足该请求当前的行程（若拆分，则该电梯可以满足可能的第一个拆分请求）。实现getIn方法，根据第一部接送请求的电梯，对请求行程进行更改，即更改fromfloor和tofloor，使电梯能够满足请求，实现getOut方法，根据第一部将请求送出的电梯更改接下来的行程，即第二程的fromfloor和tofloor。从而实现电梯可以接送乘客并且能够动态改变请求行程。
• 其次对于电梯捎带，本次作业更改为同方向捎带，做此更改的目的是考虑到了实际情况，并且电梯有容量限制。实际情况中，若电梯正在上升，低楼层中有向下的请求，但提前上了电梯，而高楼层的向上的请求可能因为电梯人满而不能登上电梯而被阻塞，从而降低了效率，因此讲电梯更改为同方向捎带，以尽可能的较快完成最近的请求。
• 再者对于部分优化，是为拆分请求考虑的。若其中有一个请求需要拆分完成，而当三部电梯均空闲时，第一部电梯先行接送请求，完成第一个行程，之后第二部电梯才慢慢悠悠的从远处赶来完成第二个行程，这样一定程度上会降低效率。因此希望在电梯空闲时，若拆分请求已经上了第一部电梯，能够通知第二部电梯前来准备接送。因此为电梯类新增了一个属性vTarget，在请求上了第一部电梯后能够notify第二部电梯，前往vTarget做准备（vTarget为第一个行程的下电梯楼层），从而减少浪费时间。
• 因此完成请求任务的时序便如时序图所描述（描述的是一部电梯的时序）。
• 在线程安全上，首先要修改电梯线程break的条件，电梯线程break的条件是输入已经结束，并且当前队列为空，且三部电梯均在wait状态，才可以break。并且其中一个线程break之后要notify另外两个线程break。其次要保证队列安全，即要为push和poll方法以及查询方法加上锁synchronize，防止因为线程冲突而造成同时操作同一对象而出错。再者在电梯上下人时要加锁，因为电梯上下人是由两个过程实现，以上人为例，需要先从队列中提取请求，在push到电梯中，这两个过程必须锁在一起完成。

3.4 分析bug

• 本次作业在公测中自己发现一个bug，在互测中被发现一个bug
• 自己发现的bug是发现自己对锁的概念理解错误，一个对象中如果有一个小对象为其成员变量，一开始认为锁住了该对象小对象的操作就都会被阻塞，因此程序中有大量对大对象的加锁以为能够保证线程安全，此外还加了小对象的锁。但发现事实并不这样，小对象仍可以被访问和修改，只不过大对象中存储的小对象引用不能被更改而已。因此需要对代码中对锁进行修改。此外由于大小对象都有锁，可能会造成死锁。代码中有其中一个线程锁住了大对象，要访问小对象，而另一线程对小对象上了锁，想要notify大对象的锁，因此造成了死锁。（示例代码如下）修复bug时对所有的锁均更改为一个公用锁，凡是对队列进行push或poll或者询问是否达到break条件或者更改关键条件前，都要加上该锁，保证了线程安全性。
• 互测中发现的bug是发现自己在break条件判断前没有加上锁，从而导致了可能的线程不安全问题。

四、三次作业总结

4.1 总体构架问题

• 首先谈一下三次作业自己构架设计上的一些优点，首先实现了真正的纯电梯类，即只保存电梯基本信息和做简单的基本操作，而真正的操作电梯的是Core线程，减少了Elevator类构造的复杂度，并且提供了高度可继承性，而不用因为每一次作业更换捎带原则或者其他原则而需要更换调度算法重写电梯类，电梯类仅负责存储信息，每一次作业都适用，减少了每次作业的代码量。
• 对于框架问题，三次作业中有一个较大的构架问题，即没有实现真正的Scheduler类，而是一个电梯一个内核，并且电梯可以互相监视彼此，这个设计是不太合理的，应该得各自电梯Core仅能做自己的事，看自己所能看见的东西，从而减少耦合度，减少bug的发生和复杂度，监视应该交由Scheduler线程来完成，对三个电梯的监视，命令电梯何时工作，何时break。

4.2 线程安全问题

• 对于线程安全问题，三次作业基本上都是通过wait和notifyAll来解决CPU时间的浪费，并且通过对方法加synchronize关键字或者适用synchronize锁住一个公用锁来实现原子操作。但头两次作业对synchronize的具体作用了解不清楚，从而出现了可能的线程安全bug（见第七次作业bug分析）。总而言之，要保证线程安全性，最好的操作方式是尽量减少锁的个数，从而避免死锁，并且规定好锁的顺序，再者还要明确锁的范围，比如为了不出现死wait，要配合synchronize来进行wait，在进入wait条件之前需要先加上锁，并且在修改关键条件的地方也要加上锁，notifyAll语句也要加上锁，防止出现死wait情况。
• 对于互测中发现其他人的线程安全bug的方式，是通过阅读代码，查看其具体实现wait和notify的方式，查看是否有在关键条件判断或者修改前加锁，以及在对队列操作过程中有没有加锁避免线程安全出错。如果发现有问题，则使用输入黑箱接口（来自讨论区），并且结合Jprofiler，构造数据进行反复测试，若测出问题，则说明存在线程安全bug。

4.3 心得体会

• 经过多线程的学习，学会了synchronize语句和wait以及notifyAll语句的用法，明确了synchronize语句的真正作用，积累了经验指导怎样加锁怎样wait才能避免死锁和死wait。并且结合面向对象构造思想，学会了如何将多线程和面向对象构造相结合，学会了怎样构造类才能构造出合理的线程类，以方便完成任务，降低耦合度，提高线程安全性。