? 优质资源分享 ?
| 学习路线指引（点击解锁） | 知识定位 | 人群定位 |
|---|---|---|
| ? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。 |
| ?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
北航OO第二单元（多线程实时电梯系统）总结
本单元的总体任务是维护一个ABCDE共5楼座、10层的目标选择电梯系统。需要接受乘客的请求和增加电梯的请求，并运行相应电梯将乘客送达目的地。输出所有的电梯运行以及上下人行为。
一、同步块和锁
第五次作业中只有竖向电梯，每座各有一个，均可达1-10层，乘客请求出发地和目的地楼座一定相同。
1、第五次作业
由于只有五部电梯，并且所有请求对应的电梯是明确的，所以没有设置全局调度器，而是选择由输入线程与所有电梯共享一个候乘表对象，电梯直接从候乘表中取出自己对应的请求。为了简化其他类的设计，这里直接将候乘表设置为线程安全类，同步块具体代码如下：
public synchronized void addRequest(PersonRequest request) {
char fromBuilding = request.getFromBuilding();
this.requests.get(fromBuilding).add(request);
notifyAll();
}
public synchronized PersonRequest getMainRequest(char nowBuilding) {
while (requests.get(nowBuilding).isEmpty() && (!close)) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (requests.get(nowBuilding).isEmpty()) {
return null;
}
return requests.get(nowBuilding).get(0);
}
public synchronized ArrayList getForm(char nowBuilding) {
return requests.get(nowBuilding);
}
public synchronized PersonRequest getNowFloor(char nowBuilding, int nowFloor) {
ArrayList list = requests.get(nowBuilding);
for (PersonRequest personRequest : list) {
if (personRequest.getFromFloor() == nowFloor) {
list.remove(personRequest);
return personRequest;
}
}
return null;
}
public synchronized void close() {
close = true;
notifyAll();
}
public synchronized boolean checkOver(char nowBuilding) {
if (!close) {
return false;
} else {
return requests.get(nowBuilding).isEmpty();
}
}
public synchronized void output(String in) {
TimableOutput.println(in);
}
可以看出，添加请求、电梯空时获取请求getMainRequest，策略类获取当前楼座候乘表getForm，电梯上人getNowFloor，输入结束close，检查是否结束线程的checkOver和输出output都在同步块内。在某电梯线程或输入线程访问时均会阻塞其他线程的访问，以此保证线程安全。特别的，当电梯无人且主请求为空时，会执行wait()等待，输入线程每当进行输入之后会执行notifyAll()唤醒所有空置等待的电梯，以此可以避免电梯空时轮询占用CPU资源的问题。
PS：现在第二单元结束之后需再看这段代码其实有一些问题，也有可以优化的地方。
- 首先是getForm很有问题，它直接将该共享对象的一部分的指针（？）暴露给了同步块之外的部分，电梯的策略类使用的时候如果输入线程对其进行了修改，很容易出现RunTimeError，不过强测居然全都过了现在想想也是幸运。
- 之后是方法冗余的问题，checkOver函数完全可以综合进getMainRequest中，比如使用null作为返回值标记线程结束，而不需要单独写一个方法。
2、第六次作业
第六次作业在第五次作业的基础上增加了横向电梯，横向电梯可以到达相应层的所有座。乘客请求在第五次作业的基础上可以发出出发和目的地相同层不同座的请求，且请求保证在该层添加电梯1s后（保证了电梯一定先被完成添加）。由于出现了新增电梯的请求，在输入线程设置了了两个共享对象，一个乘客请求总队列ScheduleQueue负责存储所有输入的乘客请求，一个电梯增加请求队列ElevatorAddingQueue负责存储所有添加电梯的请求。同时每楼座的纵向电梯和每层的横向电梯共享一个候乘表，由调度器进行分配。与上一次思路相同，为了减轻线程类的思维量，这里直接将所有的共享对象设置为线程安全类。
ScheduleQueue同步块代码如下
public synchronized void addRequest(PersonRequest personRequest) {
waitingRequests.add(personRequest);
notifyAll();
}
public synchronized PersonRequest getRequest() {
while (waitingRequests.isEmpty()) {
if (end) {
return null;
}
try {
wait();
} catch (Exception e) {
e.printStackTrace();
}
}
return waitingRequests.remove(0);
}
public synchronized void setEnd() {
end = true;
notifyAll();
}
与第五次作业的逻辑十分相同，只是作为总表仅有添加请求、获取请求和设置结束三个情况（读取结束在获取请求方法里一并进行）。
ElevatorAddingQueue与上文代码几乎完全一致，不再赘述。
RequestQueue代码如下（没有再展示添加请求和设置结束方法）：
public synchronized PersonRequest getRequestNowFloor(int nowFloor, int status) {
if (status >= 0) {
for (PersonRequest nowRequest : waitingRequests) {
if (nowRequest.getFromFloor() == nowFloor) {
if (nowRequest.getFromFloor() - nowRequest.getToFloor() < 0) {
waitingRequests.remove(nowRequest);
return nowRequest;
}
}
}
}
if (status <= 0) {
for (PersonRequest nowRequest : waitingRequests) {
if (nowRequest.getFromFloor() == nowFloor) {
if (nowRequest.getFromFloor() - nowRequest.getToFloor() > 0) {
waitingRequests.remove(nowRequest);
return nowRequest;
}
}
}
}
return null;
}
public synchronized PersonRequest getRequestNowBuilding(char nowBuilding) {
for (PersonRequest request : waitingRequests) {
if (request.getFromBuilding() == nowBuilding) {
waitingRequests.remove(request);
return request;
}
}
return null;
}
public synchronized boolean lookRequestNowBuilding(char nowBuilding) {
for (PersonRequest request : waitingRequests) {
if (request.getFromBuilding() == nowBuilding) {
//waitingRequests.remove(request);
return true;
}
}
return false;
}
public synchronized PersonRequest getRandomRequest() {
while (waitingRequests.isEmpty()) {
if (end) {
return null;
}
try {
wait();
} catch (Exception e) {
e.printStackTrace();
}
}
//System.out.println(waitingRequests.get(0));
return waitingRequests.get(0);
}
public synchronized boolean lookRequestNowFloor(int nowFloor, int status) {
//System.out.println(waitingRequests);
if (status >= 0) {
for (PersonRequest nowRequest : waitingRequests) {
if (nowRequest.getFromFloor() == nowFloor) {
if (nowRequest.getFromFloor() - nowRequest.getToFloor() < 0) {
return true;
}
}
}
}
if (status <= 0) {
for (PersonRequest nowRequest : waitingRequests) {
if (nowRequest.getFromFloor() == nowFloor) {
if (nowRequest.getFromFloor() - nowRequest.getToFloor() > 0) {
return true;
}
}
}
}
//System.out.println("false at look");
return false;
}
public synchronized int look(int status, int nowFloor, int id) { //-1表示结束，0表示原方向继续，1表示转向
//System.out.println("begin look"+id);
while (waitingRequests.isEmpty()) {
if (end) {
return -1;
}
try {
wait();
} catch (Exception e) {
e.printStackTrace();
}
}
for (PersonRequest personRequest : waitingRequests) {
//System.out.println(""+(personRequest.getFromFloor()-nowFloor>0)+status);
if ((personRequest.getFromFloor() - nowFloor > 0 && status == 1)
|| (personRequest.getFromFloor() - nowFloor < 0 && status == -1)) {
//System.out.println("panic at 0");
return 0;
}
}
//System.out.println("panic at 1");
return 1;
}
可以看出，电梯内部的策略方法被直接集成在了相应的请求队列中，同时所有逻辑加锁，防止某两个同座/楼层电梯同时获取请求的线程不安全导致一个人“分身”的情况。
3、第七次作业
第七次作业在第六次的基础上增加了可定制运行速度和限乘人数的电梯，横向电梯增加了可定制的可达楼座，并且需要支持需要换成的乘客请求。本次作业就是在调度器逻辑上做了扩展，共享对象和第六次作业几乎没有变化，只有增加了一个增加电梯线程和调度器线程之间的共享对象用于存储已有电梯信息方便调度器进行路径规划，同样封装成一个线程安全类。
二、调度器设计
1、第五次作业
本次作业本身考虑一开始对多线程的交互不熟，也没有电梯的增加并且每个请求只能由一步电梯处理，故没有使用调度器，而是直接由输入线程将请求扔进总表，电梯直接从总表获取自己想要的。
现在想想这其实是不太好的设计，直接让总表作为所有电梯的共享对象，就导致了只要任何一个电梯使用共享对象，都会阻塞其他电梯对共享对象的读取和使用。这使得不同的电梯虽然没有任何协同，却会阻碍彼此的运行。再一个，因为这一个表要存储所有种类的请求，导致使用了一个大Hashmap的复杂结构，这让这个类的方法理解上的复杂度升高，在写电梯自身的调度算法的时候增加了很多困难。
因为刚开始接触多线程，又使用了这么复杂的一个候乘表，导致我写本次作业时想不出如何设定一个请求为主请求，但是在接到主请求之前不删除候乘表类中的该请求。于是我在电梯内部的调度算法没有使用ALS，而是使用了相对简单粗暴的一个逻辑，完全电梯内部优先：如果电梯内部有人，那么电梯的方向就是其中距离最近的人要去的楼层方向；如果电梯内部无人，那么电梯的方向就是候乘表中任何一个请求的方向；每当电梯到达一个楼层之后，就会在容载量的前提下让所有人上电梯（不管请求方向）。这个调度策略的优势就是简单，而且会在一些特殊情况下超过ALS策略，但整体还是较慢。不过最终还是以正确性优先，于是在做了简单的时间测试发现除了在极端情况下，该策略不会比ALS慢很多的情况下进行了提交。
2、第六次作业
本次作业考虑到不涉及换乘问题，平均分配或是随机分配都不太能适配所有较优的情况，故最后选择了自由竞争的方法。自由竞争方法是所有同层/同座电梯共享一个请求等待队列，并且因为本次作业没有换乘，调度器的需要做的事只有从未分配请求队列中获取请求并存入对应层/座的队列更好的。
纵向电梯内部调度器采取look算法，与往年的look算法完全一致。横向电梯采用了第五次作业的调度策略，即内部优先最近策略。因为横向电梯只有5层且可以循环，所以内部优先策略在一般情况下比起横向电梯一直向一个方向转是有优势的。两种方法都用随机生成数据测试了之后发现确实内部优先策略好的次数高，就最终使用了该策略。
3、第七次作业
本次作业需要考虑多次换乘的问题，为此我添加了MyPersonRequest类，该类继承PersonRequest类，在新的类中添加了nowBuilding，nowFloor表示人目前所在位置，goToBuilding，goToFloor表示下一段乘坐电梯去的地方。调度器负责读取待分配队列scheduleQueue中的请求，根据他们的nowBuilding，nowFloor，与toBuilding，toFloor规划路径，将下一段需要乘坐电梯到达的位置填入goToBuilding，goToFloor，并将该请求放入对应的队列RequestQueue中。每当人出电梯的时候，判断当前位置与最终目的位置是否一致，如果不一致就再扔回待分配队列中，等待下一次调度器的分配。如此实现了请求分段的最优规划。为了方便调度器的规划，在调度器和电梯添加队列中添加了共享对象，一个三维数组path[11][6][6]，path[i][j][k]==1表示在i层有可以从j座直接到达k座的电梯。每当新增横向电梯时更新该数组，调度器传入当前请求信息并使用该对象的方法获取下一路径点。
电梯的内部调度器与第六次作业完全一致，只是将所有的fromFloor，fromBuilding，toFloor，toBuilding换成了相应的nowFloor，nowBuilding，goToFloor，goToBuilding。且横向电梯在查看外部请求时完全忽略自己不能运送到的请求。
三、架构模式
1、架构的迭代变化
hw5 使用一级托盘结构，所有电梯共享一个候乘表
本次作业架构相对简单，输入线程为Producer，直接将请求放入候乘表，电梯也直接从中读取。所有线程都由主线程启动。
hw6 实现了二级托盘结构，同时有了一个调度器雏形
本次作业的第一级托盘为ElevatorAddingQueue和ScheduleQueue，分别存储电梯添加请求和乘客请求；第二级托盘为每层/座的请求队列RequestQueue，电梯可以直接从队列中读取/移除请求。调度器仅仅负责把主队列的请求分类放入相对应的二级请求队列，具体电梯的请求取决于自由竞争的结果。
相较第五次作业，本次最特别的是可以动态增加电梯。为了实现这个能力，并且方便调度器监控电梯分布情况，选择了在调度器类的构造法方法中生成负责添加电梯的类ProcessElevator。为了增加可扩展性和电梯的一致性，不再在主线程中初始化电梯，而是在ProcessElevator类中添加init()方法来增加初始电梯，并建立二级请求队列和电梯的映射。
hw7 通过调度器实现了乘客当前路径的动态规划
可以看出相比第六次作业，增加了MyPersonRequest类扩展了原请求类，并增加了一个pathForm作为调度器和电梯增加队列的共享对象。这个共享对象的getPathToFloor方法会被调度器调用，并返回一个当前要去的楼层。调度器接收这个楼层，改写请求当前段要去的坐标并置入相应队列。
本次作业具有一定的可扩展性，电梯获取请求的策略被集成在了请求队列类中的方法，只需要修改对应方法即可更改电梯的内部策略。同时，调度器的设计使得每个电梯可以专注于该请求这一段的运输而不需要考虑别的，修改调度器的方法即可达到更多次换乘或是更改规划逻辑的需求。
2、UML协作图
主要分为四个部分：
- 主线程启动输入线程和调度器线程；调度器线程创建电梯添加线程，初始化电梯，启动线程。
- 输入线程将电梯请求放入电梯队列中，唤醒正在等待的电梯添加线程；电梯添加线程添加、启动一个电梯线程，并修改电梯表将添加电梯信息传输给调度器。
- 输入线程将乘客请求放入总表，唤醒正在等待的调度器；调度器获取请求、根据电梯信息规划下一步路径，将该请求放入电梯候乘表，唤醒等待的电梯线程；电梯线程处理该请求，到达后比对请求是否到达最终目的地，若未抵达目的地，请求重新放回总表，若抵达目的地，总表完成线程数+1。
- 输入线程结束，将总表、电梯添加队列的输入结束置为真并结束线程；总表完成线程数等于总线程数时检测是否输入结束，如果输入结束，将完全结束置真；电梯添加线程获取电梯输入队列的输入结束，如果为真则结束线程；调度器获取总表的完全结束信息，如果为真则将所有电梯候乘表的结束置为真，并结束线程；电梯在内部没有请求时检索候乘表，如果候乘表没有请求且结束为真，则结束线程。
四、程序bug分析
因为hw5作业运气好，然后后两次作业自己使用了随机数据评测机，所以三次作业的强测和互测我都没有出bug。所以就主要介绍一下自己本地测试时发现的bug。
PS：自己的评测数据可以写的强一些，比如每个时间一下子生成快一百个，然后一共特别多的电梯和特别多的请求一起发出，相当于对自己的程序做了个压力测试，debug效率特别高()
hw5的bug主要出现在线程结束和线程不安全上。首先是因为在一开始的电梯策略类调用的候乘表方法里面有2个wait()的位置，导致判定线程结束时可能一个notifyAll无法成功唤醒正在等待请求的电梯线程，后将检测结束和策略合并就完成了修复。再是线程不安全问题，因为我直接将候乘表封装成了一个线程安全类，所以没有在这里出现，而是因为输出包的线程不安全而产生了时间不递增问题。这个问题多亏了室友的分享，后来将输出包封装成了一个线程安全类，让每个线程去调用之后解决了问题，体现了开发中交流的重要性hhhhhh。
hw6的首个bug在纵向电梯的look算法，因为一开始设置的是除非拿到反向请求且没有当前方向请求才转向，导致了在没有请求时一飞冲天的问题。第二个bug非常隐蔽，是一个RTLE的bug，甚至当时没有找出来，而是误认成了有线程没有正常结束的问题。具体bug是横向电梯的调度问题，下面看一块代码
int near = requestsIn.get(0).getToBuilding();
for (PersonRequest request : requestsIn) { //找到最近的
if ((request.getToFloor() - nowBuilding + 5) % 5 < (nowBuilding - near + 5) % 5) {
near = request.getToBuilding();
}
}
这是横向电梯里找内部最近的请求的算法，乍一看可能没有什么问题。但是注意这里(request.getToFloor() - nowBuilding + 5) % 5实际上求到的并不是他的循环距离，而是当前位置到要去位置的某个方向的距离，比如当前在A，要去E，则会得到4，如果当前在E，要去A，则会得到1。而且最关键的是，后面与之比较的(nowBuilding - near + 5) % 5的当前位置和要去位置的加减号时反的，这导致了我实际上在拿顺时针运动的距离与逆时针运动的距离进行比较，如此导致了横向电梯在内部有特定顺序加入的请求的时候左右横跳（因为会出现比如说有去A和E的请求，可能会出现在B认为E近所以去C，然后再C认为A近所以去B的简谐运动）就是到达不了。这个bug在hw7的时候才找出来，之前还以为是调度器的问题而删掉了随机分配改成了自由竞争，真是可怜了调度器。也是幸好第六次的强测刚好没有卡到这个bug。
PS：感觉第六次本地没测出bug是因为数据生成器采用等概率的随机生成的问题，导致横向请求不够多也不够集中，就基本没能触发这个bug、
hw7的一开始有线程提前结束的bug，这个原因是继承了hw6的架构之后，输入线程结束的同时总表就被setEnd并且调度器和对应的没有请求的电梯也随之结束。但是有一些在电梯内部的请求仍需要换乘，所以调度器此时结束之后这些请求就被扔在了半路上。debug方法是在总表中加入了统计总请求数和当前完成请求数，只有输入结束并且完成请求数和总请求数相等才会关闭调度器和没有请求的电梯。第二个bug就是上文hw6的bug，这里本地测出来了我猜测是因为当时以为是多段调度的问题所以集中生成了所有请求都要换乘横向电梯的数据，故横向电梯被压力测试了，就显示了出来调度问题。debug就是把这里的near换成真正的最近
int near = requestsIn.get(0).getGoToBuilding();
for (MyPersonRequest request : requestsIn) { //找到最近的
if (Math.min((request.getGoToBuilding() - nowBuilding + 5) % 5,
(nowBuilding - request.getGoToBuilding() + 5) % 5) <
Math.min((nowBuilding - near + 5) % 5,
(near - nowBuilding + 5) % 5)) {
near = request.getGoToBuilding();
}
}
五、hack策略
1、测试策略与有效性
hw5我理解的主要问题就是线程不安全的问题，这里的测试策略就是生成时间非常集中，且调度了所有线程的数据。比如说在70s在每个座都一次性发出14个从10层去1层的请求，成功在第一次互测hack掉了两个线程不安全的程序，又意外之喜干掉了一个人员超载的。hw6之后因为代码实在太长，手造数据也非常费时间，就使用了评测机，与对自己程序进行压力测试不同，在互测时尽量生成满足互测要求的数据（不然本地干掉一个人还要改很久数据才能提交也太糟心x），但是依然保证请求的发出时间相对集中，可以顺带测试线程不安全的问题。hack掉了一个横向电梯调度有问题的。hw7同样使用评测机，而且发出的100%的数据都跨楼层，成功干掉三次换乘出问题的两人。
2、线程安全问题的hack
我的理解就是同时唤醒运行所有线程且激活几乎所有线程通信的数据可以最大几率干掉线程安全问题，比如同一时段发出添加电梯的请求和需要唤醒所有已存在电梯的请求。
3、与第一单元的差异性
测试的差异性主要体现在输入数据的集中构造，这里的很多bug是需要靠数据量堆起来才能反映出来的。
六、心得体会
1、线程安全
本章我体会到的保证线程安全最好的方法我个人认为是构造线程安全类，这样可以直接保证访问时的线程安全，可以避免在每个线程设计调用方法时再考虑是否会出现安全问题和上锁的情况，既能少死点脑细胞、又能最大程度上防止疏忽导致的线程安全问题。
2、层次化设计
对于第一单元偷懒将所有因子的解析赋给一个类，最后只用了4个类就完成的我，这一单元的12个类属实让我体会到了层次化设计的优势和重要性。这单元中除了hw6对电梯策略进行了修改外，其余部分都实现了迭代开发。可以说在明确了每个类负责的功能之后，对12个类的交互设计也就水到渠成，这可能就是层次化设计的美妙所在。其实在封装策略类接口上我并没有做到，而是将策略作为了请求队列的方法，可以依靠注释来切换，还有可以改进的空间。
-
- 一、同步块和锁
- 1、第五次作业
- 2、第六次作业
- 3、第七次作业
- 二、调度器设计
- 1、第五次作业
- 2、第六次作业
- 3、第七次作业
- 三、架构模式
- 1、架构的迭代变化
- 2、UML协作图
- 四、程序bug分析
- 五、hack策略
- 1、测试策略与有效性
- 2、线程安全问题的hack
- 3、与第一单元的差异性
- 六、心得体会
- 1、线程安全
- 2、层次化设计
__EOF__
gdfwj - 本文链接： https://blog.csdn.net/gdfwj/p/16197138.html
转载请注明：xuhss » 面向对象第二单元总结