我来补这学期欠下的坑了，比起博客园，里面的文章会更侧重于关于做题的思路，因此有可能直接以最后一次题目来分析了(毕竟迭代开发)，有关面向对象相关的内容，比如类、对象、方法、属性等等或许相对少。对于本单元来说，不会纠结于线程安全的设计和线程安全的数据结构，这些在博客园中有涉及。
博客园链接
电梯月
题目
题意
系统基于一个类似北京航空航天大学新主楼的大楼，大楼有 $A,B,C,D,E$ 五个座，每个楼座可以对应多台电梯，可以在楼座内 $1-10$ 层之间运行。本次作业每个乘客的起始位置和目的位置可以在楼层和楼座上都不同。同时，本次作业新增电梯定制化功能，对纵向电梯的运行速度、可容纳人数，横向电梯的运行速度、可容纳人数、可开关门信息进行定制。
系统从标准输入中输入请求信息，程序进行接收和处理，模拟电梯运行，将必要的运行信息通过输出接口进行输出。
具体而言，本次作业电梯系统具有的功能为：
$1、$楼座对应的电梯：上下行，开关门，以及模拟乘客的进出。 $2、$楼层对应的电梯：左右行，开关门，以及模拟乘客的进出。 电梯系统可以采用任意的调度策略，即在任意时刻，系统选择上下（左右）行动，是否在某层开关门，都可自定义，只要保证在电梯系统时间不超过系统时间上限的前提下将所有的乘客送至目的地即可。
电梯每纵向（横向）运行一层（座）、开关门的时间为固定值，仅在开关门窗口时间内允许乘客进出。
电梯系统默认初始在 $A,B,C,D,E$ 五个楼座的 $1$ 层中有一个容量为 $8$ 人，运行速度为 $0.6$ s/层的纵向电梯。
电梯系统默认初始在 $A$ 座的 $1$ 层中有一个容量为 $8$ 人，运行速度为 $0.6$ s/座，可以在全部楼座停留的横向电梯。
电梯参数说明
$1、$可到达楼层：1-10层 $2、$纵向电梯初始位置：各座1层 $3、$横向电梯初始位置：A 座各层 $4、$数量：最初5部纵向电梯、1部横向电梯，可增加 $5、$编号：最初5部电梯中 A 座为1号，B座为2号，依次类推，最初的横向电梯为6号；新增的电梯编号自定义，但不可与之前的重复 $6、$移动一层（座）花费的时间：可定制 $7、$开门花费的时间：0.2s $8、$关门花费的时间：0.2s $9、$限乘人数：可定制 $10、$横向电梯可停靠楼层：可定制
电梯请求说明
本次作业的电梯，为一种比较特殊的电梯，学名叫做目的选择电梯。
大概意思是，在电梯的每个入口，都有一个输入装置，让每个乘客输入自己的目的位置。电梯基于这样的一个目的地选择系统进行调度，将乘客运送到指定的目标位置。
所以，一个电梯请求包含这个人的出发楼座、出发楼层、目的楼座和目的楼层，以及这个人的id（保证人员id唯一），请求内容将作为一个整体送入电梯系统，在整个运行过程中请求内容不会发生改变。
输入数据说明
$1、$每行输入数据可分以下三类： $(1)、$请求信息： $a、$格式为：[时间戳]乘客ID-FROM-起点座-起点层-TO-终点座-终点层 $b、$输入保证 $[$起点座 $==$ 终点座$] + [$起点层 $==$ 终点层$ ]\ \ne 2$，即楼座和楼层不会同时相同。 $c、$乘客 $ID$ 唯一，且满足$ID$是 int 类型数据 $(2)、$为一个楼座动态增加纵向电梯的指令： $a、$格式为：ADD-building-电梯ID-楼座ID-容纳人数V1-运行速度V2 $b、$输入保证楼座 $ID \in [A,B,C,D,E]$ $c、$电梯 $ID$ 唯一 $d、$新建电梯默认处于对应楼座 $1$ 层 $e、$输入保证容纳人数 $V1 \in [4,6,8]$ $f、$输入保证运行速度 $V2 \in [0.2, 0.4, 0.6]$ $(3)、$为一个楼层动态增加横向电梯的指令： $a、$格式为：ADD-floor-电梯ID-楼层ID-容纳人数V1-运行速度V2-可开关门信息M $b、$若满足 ((M » (X-‘A’)) & 1) == 1 ，则代表该电梯在楼座 $X$ 可开关门。$(X \in [A,B,C,D,E])$ $c、$输入保证 $\sum_{i=0}^4 ((M » i)\&\ 1) \ge 2$.即至少有两个可到达楼座。 $d、$输入同时保证 $1 \lt M \lt 32$，即不包含无意义的二进制位。 $e、$输入保证楼层 $ID \in [1,2,3,4,5,6,7,8,9,10]$ $f、$电梯 $ID$ 唯一 $g、$新建电梯默认处于对应楼层 $A$ 座 $h、$输入保证容纳人数$V1 \in [4,6,8]$ $i、$输入保证运行速度$V2 \in [0.2, 0.4, 0.6]$
算法分析
大体构建
先对整个的题目进行一个大体的分析，可以将其拆解为有人要请求电梯-驱动电梯接人-搭电梯去目的地的过程。其中会穿插着增加电梯的动态操作。我采用了消费者-生产者模式，有一个输入线程，一个调度器线程，五个电梯线程。输入线程和调度器线程共享一个等待队列requestQueue，输入线程为生产者，调度器线程为消费者。里面存着input得到的投喂的请求。而调度器在获得请求后，根据其所在楼座放到每个电梯线程的等待队列中outside:Demand。这个类是一个ConcurrentMap，是一个保证原子操作线程安全的Map。它的key值要上去的楼层，Value为request。But这样就会丢失请求添加的顺序，因此还需要另外一个RequesrQueue（本质就是上锁的ArrayList加上一个停止标识）来依照时间顺序记录队列。这个Outsider和queue就是由调度器和电梯共享，此时调度器变为了生产者，电梯为消费者。
结束条件
多线程的一个重难点便在于什么时候该通知一个线程可以结束了，要不然程序会一直跑下去。在中途可以换乘的条件后，结束会稍微复杂一点。先考虑如果不能换乘，那么调度器线程结束后，并且等待队列为空并且电梯空闲下来的时候，就可以结束了。但如果可以换乘，在满足上述条件的情况下，仍然可以因为需要换乘从而再次被调用。 因此这里，我用了计数器单例模式(感谢实验)，来判断是否将每一个乘客都送到目的地了。输入线程发现一个乘客请求就++，当电梯发现把请求送到目的地了就–，如果没有就再次加入的请求队列中。
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
// Thread input
if (request instanceof PersonRequest) {
Count.getInstance().increase();
}
// Thread elevator
request.update(high, current);
if (request.isArrive()) {
// update the request information and check whether arrive
Count.getInstance().decrease(); // count--,and the count is single-thread model
if (Count.getInstance().isCleared()) {
requests.lock();
try {
requests.signalAll();
}
finally {
requests.unlock();
}
}r
} else {
// if not arrive， then add a new request
PersonRequest personRequest = new PersonRequest(request.getTranFloor(),
request.getToFloor(), request.getTranBuilding(),
request.getToBuilding(), request.getPersonId());
requests.lock();
try {
requests.add(personRequest);
requests.signalAll();
}
finally {
requests.unlock();
}
}
计数器单例如下
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
44
45
46
47
48
49
50
51
52
53
54
55
56
// Count thread
// import file is ignored
public class Count {
private static int count;
private final ReentrantLock locker;
private final Condition condition;
private static final Count COUNT = new Count();
public Count() {
count = 0;
locker = new ReentrantLock();
condition = locker.newCondition();
}
public static Count getInstance() {
return COUNT;
}
public void increase() {
locker.lock();
try {
count++;
condition.signalAll();
} finally {
locker.unlock();
}
}
public void decrease() {
locker.lock();
try {
while (true) {
if (count > 0) {
count--;
break;
} else {
condition.await();
}
}
} catch (InterruptedException e) {
throw new RuntimeException(e);
} finally {
locker.unlock();
}
}
public boolean isCleared() {
locker.lock();
try {
// System.out.println(count);
return count == 0;
} finally {
locker.unlock();
}
}
}
换乘
所有的乘坐情况可以用下面这张图来表示：
具体配合掩码来说，操作如下
1
2
3
4
5
6
7
8
9
10
11
12
13
if (myRequest.getFromBuilding() == myRequest.getToBuilding()) {
chooseElevator(building, counter.get((int) building), myRequest);
} else {
int transparent = transparentFloor(myRequest);
int transparentFloor = transparent / 10000;
//get the transparentFloor
if (transparentFloor != myRequest.getFromFloor()) {
myRequest.setFrom(myRequest.getFromFloor());
myRequest.setDestination(transparentFloor);
chooseElevator(building, counter.get((int) building), myRequest);
} else {
chooseElevator(transparent, counter.get(transparent), myRequest);
}
有上述可知，一个完整请求最拆解成3个原子操作。
载客与调度
电梯调度也是一直就有着很多种算法，这边我偷懒基本按照基准思路做的，即ALS。和其他同学对了一下，应该用SCAN的效率是最高的。
具体来说，要先确定主请求
- 如果电梯内部为空，就再等待队列的队首
- 电梯内部有乘客，就选择最快到达，在本题下，就是电梯内部的请求的目标楼层和当前楼层距离最近的。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (MyRequest request : outside.get(current)) {
// to see if there is someone can be taken with
// or the main request is waiting
if (num == capacity) {
if (outside.get(current).contains(mainRequest)) {
// reach the max num, need to change the main request
mainRequest = null;
selectMainRequest();
}
break;
}
if (high == 5 || isCarry(request)
|| (request.getDestination() < current && direction == -1)
|| (request.equals(mainRequest) && inside.isEmpty()) || mainRequest == null) {
// do something
} else if (request.equals(mainRequest) && (!inside.isEmpty())) {
// means mainRequest's direction is opposite to the current direction
// then we need to switch another mainRequest
mainRequest = null;
selectMainRequest(high);
}
}
再者是允许电梯载客的原则， 先聚焦在不超载的情况
- 对于当前楼层想要去往请求目标楼层的方向和当前电梯和电梯方向一致 （因为采用时即时交互，因此可以获得到的请求的到来时间必定不早于电梯到达的时间）
- 此请求为主请求，且电梯内部为空。
这样就会遇到一个情况，就是主请求要去的方向和电梯接到主请求的方向不一致，且电梯内部已经有人，比如一个主请求要求是FROM-5-TO-8， 点滴从第10层，它在下来的路上捎带了一些人，这些人的目标楼层均小于5层，我的处理方式，是从在电梯里面的那些人中重新选一个主请求。
此外，从上述表达中也可以看到，这里会存在着一种情况，就是电梯再接主请求的路上就已经满载了，这时应该即时更换主请求，要不然可能会导致主请求一直卡着，没有被接到，从而电梯死机了。
此外，对于可定制开关门的横向电梯，我将同一层楼，同样的关门信息的电梯都放在一个map里面，因此我的key值为(floor) « 5 + switchInfo。而我选择中转楼层的方式，则是优先遍历起始楼层和终点楼层之间的楼层是否存在可作为中转的横向电梯，没有再像两侧衍生开。遍历楼层时，我的做法是将switchInfo从0-31其是否满足中转要求并且存在着这样的电梯。但这也会存在的毛病，就是如果一个人要从A-C， 有switchInfo为5和7的，这样就会一直选择5的，因此我记录下了上次选择的switchInfo，如只有这样的switchInfo满足条件那就用它，否则就换一个。
横向电梯还有一个注意的事项，在于因为其是环形的，且只有5栋楼，捎带并不严格，即同向不同向影响不大，反而有可能因为一直要等到心仪的方向从而一直等待导致超时。
其余就是线程安全、多线程需要注意的点，这个单元调试上会比较痛苦，毕竟错误结果不可复现。
