OO Unit2 Summary
hw5:
架构设计：
MainClass负责输入，并将对应的Request委派给RequestTable，对应楼座的电梯Elevator通过RequestTable获取请求。这里，我还额外将存储Request的容器封装为一个RequestTable类，这将有利于未来迭代时自由分配指派电梯id。输入线程为主线程，向RequestTable 输入请求，使用线程安全list存储，SafeOutput实现输出安全。
Contorler方法类控制电梯单独行为，获取目标楼层、电梯运动开门等。
生产者：输入线程MainClass
托盘：候乘表RequestTable
消费者：电梯线程Elevator
生产者输入线程获取输入，投放到候乘表RequestTable，消费者电梯线程自己运行，同时扫描RequestTable，找到对应id的乘客后运行。
协作图：
调度：
第一次作业不涉及电梯id的分配，只需考虑单电梯的运行策略。
look算法：
当电梯有乘客时，以乘客中目标楼层距离当前楼层最远的请求为主请求确定目标楼层
当电梯没有乘客时，首先按照原方向，寻找距离当前楼层最远的有请求的楼层，
找到则确定为目标楼层，这次寻找最终结果有可能会是当前层。如果寻找无果（
沿方向的所有层包括本层都没有请求）则改变方向，继续寻找。若最后没有找到，
则电梯进入空闲。
这里为了考虑进来乘客的优先级，定义一个修正距离（优先级乘以距离），用来平衡加权时间。
电梯协作行为及锁的设置：
电梯协作行为顺序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| action()
{
先判断是否开门（先存储出和进的人列表看是否为空）
先出后进
输出out:电梯内有人到
输出in:电梯有空位 有对应乘客要上 对应乘客顺路
关门
刷新获取目标楼层（look）
刷新方向
根据运动方向判断是否移动或者休眠
休眠：最好是一个时间戳的所有输入的输入时间
移动：到达方向下一楼层
}
|
销毁线程标识：输入得到ctrl + D结束信号时，调用所有RequestTable的setEnd()方法
电梯如果主线程输入结束（isend），表内无对应乘客，电梯空，销毁结束线程
1
2
3
4
5
6
7
| if (this.getPeoples().isEmpty()
&& this.getRequestTable().isend()
&& this.getRequestTable().getRequests().isEmpty()
&& !this.getRequestTable().hasRequestOf(this.getid())
){
break;
}
|
锁的设置：
使用读写锁，对RequestTable的写入和获取加锁，这里因为对读写锁不熟悉没有使用wait()-notify()来进行，而是使用sleep()进行轮询，实测只要时间足够长，不会超出cpu时间限制。
bug以及互测：
第一次作业强测互测都没有出现bug，也许是因为使用了sleep绕开了死锁的问题。
互测可以从短时密集请求入手。
hw6:
架构设计：
新添manager线程类对请求进行电梯id分配，从RequestTable实例TemprequestTable获取待分配请求，重新分配请求丢入TemprequestTable。
PersonRequetHasid存储没有id的请求和分配的id，ScheTable存储临时调度请求，Elevator新添sche方法
生产者：输入线程MainClass
托盘：ScheTable、RequestTable
消费者：电梯线程Elevator
生产者：输入线程MainClass、检修Elevator
托盘：TemprequestTable
消费者：manager—>RequestTable
协作图：
调度：
单部电梯采用look算法
id分配为最近同向可分配电梯，如果所有电梯队列和电梯内达到6人后阻塞分配
重新分配的进入TemprequestTable
1
2
3
4
5
6
7
8
9
10
11
12
| for (Elevator e : elevators.values()) {
if (!e.isInsche() && e.isAlive()) {
if (e.getPeoples().size() + requestTable.getRequestSizeOf(e.getid())
< e.getcapacity() &&
e.getDirection() * (from - e.getlocation()) >= 0 &&
Math.abs(e.getlocation() - from) < maxdis
) {
maxdis = Math.abs(e.getlocation() - from);
id = e.getid();
}
}
}
|
电梯协作行为及锁的设置：
电梯协作行为顺序：
先判断是否进入临时调度。
不进入调用action()
进入调用sche()
销毁线程条件：
电梯如果主线程输入结束（isend），表内无对应乘客，电梯空不在检修，无待重新分配请求，无检修请求，销毁结束线程
1
2
3
4
5
6
7
8
9
10
11
| if (this.getPeoples().isEmpty()
&& this.getRequestTable().isend()
&& this.getRequestTable().getRequests().isEmpty()
&& this.getTemprequestTable().getRequests().isEmpty()
&& this.getScheTable().getSches().isEmpty()
&& !this.isInsche()
&& !this.getRequestTable().hasRequestOf(this.getid())
) {
manager.setendadd();
break;
}
|
锁的设置：
对RequestTable、ScheTable、TemprequestTable的写入和获取加锁
电梯线程结束发送manager计数器加一，满6结束manager线程（注意加锁）
注意电梯里sche状态应该在输入线程里设置（accept后就不能分配。防止一些不必要的线程安全问题），end后再重新分配内外部取消的人，防止意外阻塞超过6s和错误输出。
bug以及互测：
第二次作业强测互测也都没有出现bug，本地测试时容易出错的是sche命令一开始没有写入一个表，导致了主线程阻塞，应该让电梯线程获取请求。
互测可以从密集请求接sche请求入手，卡出错误的重新分配。
hw7
架构设计：
新添UpdateTable存储升级双轿厢电梯请求。
Elevator新添update()方法，添加运行层限制和换乘层属性，伙伴电梯关系存储在UpdateTable（没有默认返回自身）。
生产者：输入线程MainClass
托盘：ScheTable、RequestTable
消费者：电梯线程Elevator
生产者：输入线程MainClass
托盘：UpdateTable
消费者：电梯线程Elevator
生产者：输入线程MainClass、检修Elevator
托盘：TemprequestTable
消费者：manager—>RequestTable
协作图：
调度：
单部电梯采用look算法
id分配为最近同向可分配电梯，如果所有电梯队列和电梯内达到6人后阻塞分配
同时只能分配给请求起始楼层在电梯运行范围内的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| for (Elevator e : elevators.values()) {
if (!e.isInsche() && !e.isInupdate() &&
e.isAlive() && e.isInfield(from)) {
if (e.getPeoples().size() + requestTable.getRequestSizeOf(e.getid())
< e.getcapacity() &&
e.getDirection() * (from - e.getlocation()) >= 0 &&
(((to - from) > 0 && e.isInfield(from + 1)) ||
((to - from) < 0 && e.isInfield(from - 1))) &&
Math.abs(e.getlocation() - from) < maxdis
) {
maxdis = Math.abs(e.getlocation() - from);
id = e.getid();
}
}
}
|
1
2
| (((to - from) > 0 && e.isInfield(from + 1)) ||
((to - from) < 0 && e.isInfield(from - 1)))
|
这段保证了起始在换乘楼层的乘客只能分配给能够送达的电梯。
电梯协作行为及锁的设置：
电梯协作行为顺序：
分开一些操作为单独的函数
1
2
3
4
| inout(e, requestTable, updateTable);
doubleinout(e, requestTable, updateTable);
setTarget(e, requestTable);
e.refreshDirection();
|
settarget更新空电梯判断防止送完人停在换乘楼层
1
2
3
4
5
6
7
8
| if (!r.hasRequestOf(e.getid())) {
if (e.isIntransfer(e.getlocation())) {
e.leavetransfer();
}
else {
e.setTarget(e.getlocation());
}
}
|
注意删除电梯内原有换乘请求时先分配完后再删，防止删除一瞬间两部电梯都为空判断线程结束
方向不为0，新添锁判断和离开transfer判断，保证电梯不在换乘楼层停留导致碰撞。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| if (!e.isIntransfer(e.getlocation())) {
if (e.isIntransfer(e.getlocation() + e.getDirection())) {
updateTable.getlockof(e.getid()).writeLock().lock();
}
e.setlocation(e.getlocation() + e.getDirection());
SafeOutput.println(String.format("ARRIVE-%s-%d",
floortostring(e.getlocation()), e.getid()));
}
else {
e.leavetransfer();
e.setlocation(e.getlocation() + e.getDirection());
SafeOutput.println(String.format("ARRIVE-%s-%d",
floortostring(e.getlocation()), e.getid()));
updateTable.getlockof(e.getid()).writeLock().unlock();
}
|
线程终止：
总信号判断结束，自身结束，伙伴电梯结束
（如果有双轿厢判断伙伴，防止换乘的重分配，没有默认返回自身）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public boolean isend() {
boolean total = this.getRequestTable().isend()
&& this.getRequestTable().getRequests().isEmpty()
&& this.getTemprequestTable().getRequests().isEmpty()
&& this.getUpdateTable().getUpdates().isEmpty()
&& this.getScheTable().getSches().isEmpty();
boolean self = this.getPeoples().isEmpty()
&& !this.isInsche()
&& !this.getRequestTable().hasRequestOf(this.getid());
boolean another =
this.manager.getElevator(updateTable.getanother(id)).getPeoples().isEmpty()
&& !this.manager.getElevator(updateTable.getanother(id)).isInsche()
&& !this.getRequestTable().hasRequestOf(updateTable.getanother(id));
return total && self && another;
}
|
锁的设置：
新建updatetable存储update命令，执行control 的update A/B函数
存储伙伴电梯id对，两个的统一锁，是否输出begin和end阻塞信号量，实现后进输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public void removeUpdate(UpdateRequest request, char type) {
if (type == 'A') {
this.getlockof(request.getElevatorAId()).writeLock().lock();
if (updates.get(request.getElevatorBId())) {
SafeOutput.println(String.format("UPDATE-BEGIN-%d-%d",
request.getElevatorAId(), request.getElevatorBId()));
try {
Thread.sleep(1000);
} catch (InterruptedException err) {
err.printStackTrace();
}
requestrwLock.writeLock().lock();
requests.remove(request);
requestrwLock.writeLock().unlock();
SafeOutput.println(String.format("UPDATE-END-%d-%d",
request.getElevatorAId(), request.getElevatorBId()));
updates.put(request.getElevatorAId(), true);
} else {
updates.put(request.getElevatorAId(), true);
}
this.getlockof(request.getElevatorAId()).writeLock().unlock();
} else if (type == 'B') {
this.getlockof(request.getElevatorBId()).writeLock().lock();
if (updates.get(request.getElevatorAId())) {
SafeOutput.println(String.format("UPDATE-BEGIN-%d-%d",
request.getElevatorAId(), request.getElevatorBId()));
try {
Thread.sleep(1000);
} catch (InterruptedException err) {
err.printStackTrace();
}
requestrwLock.writeLock().lock();
requests.remove(request);
requestrwLock.writeLock().unlock();
SafeOutput.println(String.format("UPDATE-END-%d-%d",
request.getElevatorAId(), request.getElevatorBId()));
updates.put(request.getElevatorBId(), true);
} else {
updates.put(request.getElevatorBId(), true);
}
this.getlockof(request.getElevatorBId()).writeLock().unlock();
}
}
|
结束后，同步等待，保证基本同时结束两部电梯inupdate状态：
1
2
3
4
5
6
7
8
9
10
11
| public void waitanother(char type, UpdateRequest updateRequest) {
if (type == 'A') {
while (!updateTable.inupdate(updateRequest.getElevatorBId())) {
try { Thread.sleep(10); }
catch (InterruptedException err) { err.printStackTrace(); } }
} else if (type == 'B') {
while (!updateTable.inupdate(updateRequest.getElevatorAId())) {
try { Thread.sleep(10); }
catch (InterruptedException err) { err.printStackTrace(); } }
}
}
|
sleep时间应该控制在不超时的尽量短，防止两部电梯取消update状态差距过大。
注意ele里update状态应该在输入线程里设置（accept后就不能分配。防止一些不必要的线程安全问题），end后再重新分配内外部取消的人，防止意外阻塞超过时间和错误输出。
bug以及互测：
第三次作业强测没有出现bug，互测被刀中一发死锁（1/83），本地难以复现，推测是waitanother()中sleep时间过长导致错误分配，后修改为10ms通过。
互测可以从密集请求接update请求入手，或者同时送往换乘楼层。
评测机搭建：
这个单元宿舍内合作完成了一个评测机，最终效果为可以对多个jar文件进行并行评测，不同组间也可以并行，可以指定请求数量，最大运行时间，组数和并行线程数，可以返回错误的信息，同时统计每组的课程组性能分和平均性能分。同时我为其做了一个简易的GUI和日志输出，可以方便的使用。
多线程心得体会
在本单元学习之前，我对多线程知之甚少，只有一些基础概念，但经过本单元的训练，我已经能够初步认识、设计和实现简单的多线程逻辑。
多线程会有一些单线程不会出现的问题，比如轮询、死锁等，我在作业中也出现过死锁的问题，一般都是由于没有考虑好多线程共用的资源区，导致线程沉睡或者无法结束。
本单元的电梯问题是一个经典的多线程问题，并且其没有最优调度的特点让我们能够更好地离开固有的单纯计算和查找最优解的思路，我们在真实工程需求中可能往往只需要一个局部最优解和一个“看起来性能达标”的策略即可以不差的性能满足设计要求。而在这之上，我们更多地需要考虑架构和设计层面的问题，不能为了性能上的一点点优化导致架构的极度复杂，放弃了对可迭代性、可维护性和鲁棒性的要求。
在三次的迭代中，我基本做到了只新加代码，对于之前的实现尽量不做大的修改，这也说了这个单元一开始结构设计的优越性。本单元作业中有一个有趣的点：课程组提供的输出类是不安全的。从这个角度我窥得大型工程开发的一角：绝大多数时候我们不可能从头开发或者直接重构一个已经安全运行多年的大型项目，而这时候我们会面临在这基础上迭代开发的需求。
