BUAA-OO-第二单元:电梯调度

【小女子废话较多,总是“有感而发”地“抒情”,这些不重要的话用“【】”标注出来了,可以尽情跳过~】

前言

​ 电梯调度问题是课程组为多线程学习设置的课下作业,是OO课程的重难点之一,对于第一次编写多线程的同学是一个巨大的挑战。【小女子非常悲催地被多线程攻击到了,hw5非常无奈创造了最低单次OO作业成绩】

​ 建议寒假认真学习课程组的OO公众号(oolens)推送的关于“多线程学习”的文章,最好能有基本的编程多线程代码的练习经历。【只是眼睛看,而不上手操作真的是“镜花水月”“空中楼阁”,说多了都是泪哇~】

​ 相比OO第一单元的表达式解析作业,本单元的代码编程量明显有大幅度下降,但是更多地需要思维分析,突破过去编程经历习惯的单线程思想,养成并行思维。同时,线程安全问题CPU运行时间控制问题在编写代码时也是两个不容忽视的难点。【小女子就败在了CPU运行时间控制问题,哭唧唧~】

预习知识

​ 如下依次给出几个我用的基本知识点学习的文章,仅供参考:【可以有其他更好的教程哇~ 欢迎留言浇浇小女子呀呀~】

【上面三篇文章学了基本就可以完成hw5,而下面的知识点可以在hw6、hw7中使用,如果不想大幅度重构代码也可以不用下面两个知识点 ~小女子偷了懒就没有大幅度改动~】

  • 读写锁学习
  • 原子变量
  • 信号量 Semaphore

第五次作业

​ 本次作业需要模拟一个多线程实时电梯系统。系统基于一个类似北京航空航天大学新主楼的大楼,电梯可以在楼座内 1~11 层之间运行。系统从标准输入中输入请求信息,程序进行接收和处理,模拟电梯运行,将必要的运行信息通过输出接口进行输出。

​ 具体而言,本次作业电梯系统具有的功能为:上下行,开关门,以及模拟乘客的进出。电梯系统可以采用任意的调度策略,即在任意时刻,系统选择上下行动,是否在某层开关门,都可自定义,只要保证在电梯系统时间不超过系统时间上限的前提下将所有的乘客送至目的地即可。电梯每上下运行一层、开关门的时间为固定值,仅在开关门窗口时间内允许乘客进出。电梯系统默认初始在 11层有六部电梯。

UML

类图

hw5UML

时序图

OO电梯调度第一次作业

代码架构

​ 由于课程组的性能评分中加入了耗电量 指标,因此推荐使用生产者-消费者模式,策略使用LOOK算法,我的代码架构是最为基础的实现方式,并没有引入过多超出课程组提示的知识点和思路。

  • 生产者-消费者模式

    参考*《图解Java多线程设计模式》*可以得到如下简单的模板:

    java
    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
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    public class MainClass {
    public static void main(String[] args) {
    Buffer buffer = new Buffer();
    new Producer(buffer).start();
    new Consumer(buffer).start();
    }
    }
    class Producer extends Thread {
    final Buffer buffer;
    public Producer(Buffer buffer) {
    this.buffer = buffer;
    }
    @Override
    public void run() {
    for (int i = 0; i < 10; i++) {
    buffer.push();
    }
    }
    }

    class Consumer extends Thread {
    final Buffer buffer;
    public Consumer(Buffer buffer) {
    this.buffer = buffer;
    }
    @Override
    public void run() {
    for (int i = 0; i < 10; i++) {
    buffer.pop();
    }
    }
    }
    class Buffer {
    int cnt = 0;
    boolean haveGoods = false;
    public synchronized void push() { // 生产者放入商品
    if (haveGoods) { // 有货物,消费者取出商品
    try { // 生产者等待消费者消费
    this.wait();
    } catch (InterruptedException e) {
    e.printStackTrace();
    }
    }
    if (!haveGoods){ // 被消费者通知生产
    cnt ++;
    System.out.println("Producer put:" + cnt);
    haveGoods = true;
    try {
    sleep((int)(Math.random()*100));
    } catch (InterruptedException e) {}
    this.notifyAll(); // 通知消费者消费
    }
    }

    public synchronized void pop() { // 消费者取出商品
    if (!haveGoods) { // 没有货物,生产者生产商品
    try { // 消费者等待生产者生产
    this.wait();
    } catch (InterruptedException e) {
    e.printStackTrace();
    }
    }
    if (haveGoods) { // 被生产者通知消费
    System.out.println("Consumer get:" + cnt);
    haveGoods = false;
    this.notifyAll(); // 通知生产者生产
    }
    }
    }
  • LOOK算法

    参考 Hyggge 学长的博客得到如下解释:

    • 首先为电梯规定一个初始方向,然后电梯开始沿着该方向运动。
    • 到达某楼层时,首先判断是否需要开门
      • 如果发现电梯里有人可以出电梯(到达目的地),则开门让乘客出去;
      • 如果发现该楼层中有人想上电梯,并且目的地方向和电梯方向相同,则开门让这个乘客进入。
    • 接下来,进一步判断电梯里是否有人。如果电梯里还有人,则沿着当前方向移动到下一层。否则,检查请求队列中是否还有请求(目前其他楼层是否有乘客想要进电梯)——
      • 如果请求队列不为空,且某请求的发出地是电梯"前方"的某楼层,则电梯继续沿着原来的方向运动。
      • 如果请求队列不为空,且所有请求的发出地都在电梯"后方"的楼层上,或者是在该楼层有请求但是这个请求的目的地在电梯后方(因为电梯不会开门接反方向的请求),则电梯掉头并进入"判断是否需要开门"的步骤(循环实现)。
      • 如果请求队列为空,且输入线程没有结束(即没有输入文件结束符),则电梯停在该楼层等待请求输入(wait)。
      • 如果请求队列为空,且输入线程已经结束,则电梯线程结束。

数据结构

​ 相比第一单元的复杂数据结构,本单元作业数据类大致只涉及两个:PersonRequestTable ,其中 Person 的各个信息需要由官方包获得,需要提前仔细阅读官方包的输入输出接口文档

Person

​ 用于存储每一个请求的人员信息,是多线程之间的共享数据类型:

java
1
2
3
4
5
6
7
//Person.java
public class Person {
private int id;
private int fromFloor;
private int toFloor;
//方法......
}
RequestTable

​ 该数据类是本次作业的重点之一,它是多线程之间的共享对象,存有共享数据类型Person

java
1
2
3
4
5
6
7
//RequestTable.java
public class RequestTable {
private boolean endFlag;
private int requestNum;
private HashMap<Integer, ArrayList<Person>> requstMap;//出发地在Interger的所有Person
//方法......
}

​ 对于共享对象RequestTable 中方法,为了保证线程安全,需要都加上锁synchronized,其中有两个需要重点实现的方法:

  • public synchronized void addRequest(Person person)

    java
    1
    2
    3
    4
    5
    6
    //RequestTable.java
    public synchronized void addRequest(Person person) {
    //把person请求加入容器requstMap
    requestNum++;
    notifyAll();
    }
  • public synchronized void delRequest(int mapKey, int arrayNum)

    java
    1
    2
    3
    4
    5
    //RequestTable.java
    public synchronized void delRequest(int mapKey, int arrayNum) {
    //把“容器requstMap中的mapKey的value的第arrayNum个person”删掉
    requestNum--;
    }

注意:

  1. ​ 起初我不是很能理解为什么要设置变量 boolean endFlag ,也不明白为什么要设置public synchronized boolean isEnd()public synchronized boolean isEmpty() 两个方法,在后续编程过程中,才理解到这是因为我没有带入多线程思维,上述这些都是为了控制线程结束的。

    ​ 要明白由于我们的请求是实时发送的,所以请求空了 ≠ 请求结束,它可能隔了很久很久才有一个请求,那么在这个请求之前只能让线程等待(请求为空),但不能让线程结束(请求结束)

  2. ​ 不能肆意滥用 notifyAll() 方法,否则会导致CPU时间爆掉,我的 hw5 中一共只有两个方法只适用了notifyAll() ,分别是:

    • public synchronized void addRequest(Person person)
    • public synchronized boolean isEnd()

流程架构

  • 首先,我们需要分清三个概念:线程,调度器,策略方法:

    • 线程:

      ​ 可以看做是一个任务窗口,或者一个社畜打工人,它仅仅是一个平台供我们可以同时完成一些任务,彼此之间在逻辑上不相互干扰(当然了,这个不干扰的安全性需要我们自己实现,这是我们多线程必须保证的)。

    • 调度器:

      ​ 可以看做是指挥家,把一个个请求按照“指挥家”的想法(即调度策略),分配给某个电梯,至于电梯怎么完成这个请求任务,调度器并不关心(本质是单一职责原理)。

    • 策略方法:

      ​ 可以看做是单个电梯自己的大脑,在每个时刻告诉电梯现在该做什么,例如:开门,关门,上下行。

  • 接着,具体分析本次作业的架构——我一共涉及了三类线程:1个InputThread 输入线程,1个Schedule 调度线程,6个Elevator 电梯线程。Schedule 调度线程实现调度器的功能。Elevator 电梯线程有 Strategy类为电梯提供策略

InputThread

​ 输入线程拥有一个总表 mainRequestTable 用于管理所有“从官方包中得到输入request”。注意要先阅读输入输出接口文档 得到如下的模板格式:

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//InputThread.java
public class InputThread implements Runnable {
private RequestTable mainRequestTable;

@Override public void run() {
try {
ElevatorInput elevatorInput = new ElevatorInput(System.in);
while (true) {
PersonRequest request = elevatorInput.nextPersonRequest();
if (request == null) {
//标志mainRequestTable的endFlag
break;
} else {
//向mainRequestTable中加入request
}
}
elevatorInput.close();
} catch (IOException e) {
//...
}
}
//方法......
}
Schedule

​ 调度线程拥有一个管理所有电梯表的容器 requestTables ,一个管理所有电梯的容器 elevatorMap ,与 InputThread共享的对象 mainRequestTable

java
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
//Schedule.java
public class Schedule implements Runnable {
private RequestTable mainRequestTable;
private ArrayList<RequestTable> requestTables;
private HashMap<Integer,Elevator> elevatorMap;

@Override public void run() {
try {
while (true) {
if (mainRequestTable.isEmpty() && mainRequestTable.isEnd()) {
//标志所有电梯表的endFlag
return;
}
Person person = //...从mainRequestTable中得到一个request
if (person == null) {
//若mainRequestTable没有结束,则让mainRequestTable进入wait()
continue;
}
int num = bestElevator(person);
//将person需求加入合适的电梯表
}
} catch (InterruptedException e) {
//...
}
}

public int bestElevator(Person person) {
//...
}
}
  • 电梯调度方法

    ​ 电梯拥有许多不同的调度方法,具体实现就在 public int bestElevator(Person person) 中进行,如下给出四种常用的调度方法:

    1. 分配给花时间最少的电梯

      ​ 用 模拟电梯(影子电梯/幽灵电梯) 保证局部最优解的策略,在输入线程获得一个请求时,深克隆电梯类进行模拟从而将请求分配各所花费时间最少的电梯;

      (具体可以参考 Thysrael 学长的博客 BUAA-OO-U2-电梯

    2. random 随机分配给电梯

    3. 均匀分配给6个电梯

      ​ 用一个全局变量一次记录所有输入需求是第几个,然后加入 i%6 电梯;

    4. 自由竞争

      所有电梯共用输入线程的请求队列,当输入一个请求时,所有电梯都努力去获取这个请求。

Elevator

​ 在本次作业中我采用了 “电梯类和策略类分离” 的设计,其中有如下几点说明:

  1. 电梯等待时运行方向不变

    ​ 在我的设计中,运行方向是电梯的一个状态量而不是过程量,用来表示下一次move时的方向。当有新请求进入请求队列时,电梯被唤醒,此时电梯的运行方向仍然是电梯wait前的方向。

  2. 策略类仅给出建议但未必执行该建议

    ​ 每次 while 会调用策略类的getAdvice()方法来询问建议,并根据建议做出反应,但是有可能被打断而不执行了。

java
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
//Elevator.java
public class Elevator implements Runnable {
private int id;
private int nowNum;
private int nowFloor;
private int direction; // 0表示上升, 1表示下降
private HashMap<Integer, ArrayList<Person>> destMap; //目的地在Interger的所有Person
private RequestTable requestTable;
private Strategy strategy;

@Override public void run() {
try {
while (true) {
Advice advice =
strategy.getAdvice(nowFloor,nowNum,direction,destMap);
if (advice == Advice.OVER) { //电梯线程结束
//...
} else if (advice == Advice.MOVE) { //电梯沿着原方向移动一层
//...
}
else if (advice == Advice.REVERSE) { //电梯转向
//...
}
else if (advice == Advice.WAIT) { //电梯等待
//...
}
else if (advice == Advice.OPEN) { //电梯开门
//...
}
}
} catch (InterruptedException e) {
//...
}
}
//方法......
}
  • Strategy

    ​ 策略类(Strategy)可以获得当前电梯和请求队列的当前状态,并基于LOOK策略向电梯提供建议,建议包括OVER, MOVE, REVERSE, OPEN, WAIT五种,可以将这些建议封装到枚举类Advice中。

    java
    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
    //Strategy.java
    public class Strategy {
    private RequestTable requestTable;

    public Advice getAdvice(int nowFloor, int nowNum, int direction,
    HashMap<Integer, ArrayList<Person>> destMap) {
    if (canOpenForOut(nowFloor, destMap)
    || canOpenForIn(nowFloor, nowNum, direction)) { //判断是否开电梯门
    return Advice.OPEN;
    }
    if (nowNum != 0) { //若电梯里有人
    return Advice.MOVE;
    }
    else { //若电梯里没有人
    if (requestTable.isEmpty()) { //如果请求队列中没有人
    if (requestTable.isEnd()) { //如果输入结束,电梯线程结束
    return Advice.OVER;
    } else { //如果输入未结束,电梯线程等待
    return Advice.WAIT;
    }
    }
    if (hasReqInOriginDirection(nowFloor, direction)) { //若电梯表有人
    return Advice.MOVE;
    } else { //否则,电梯转向(仅状态改变,电梯不移动)
    return Advice.REVERSE;
    }
    }
    }
    //方法......
    }

第六次作业

​ 本次作业需要完成的任务为:

  1. 固定的电梯->参数可变的电梯
    • 固定数值 ->设置电梯属性
  2. 电梯数量一定->电梯会新增/维护
    • main类初始化电梯 -> 新增电梯类 + Maintain维护电梯类

UML

类图

hw6UML

时序图

OO电梯调度第二次作业

代码架构

数据结构

​ 本次作业在上一次的基础上迭代,原来的 Person 类不需要改变,RequestTable 类只需要加一个方法来满足 Maintain 维护电梯的要求。

RequestTable

​ 在一个电梯 Maintain 之后,需要把电梯自己原来的需求表电梯中的位达目的地需求重新扔回总表mainRequestTable,具体由如下方法实现:

  • public synchronized void receiveMaintainRequest(RequestTable requestTable)

    java
    1
    2
    3
    4
    //RequestTable.java
    public synchronized void receiveMaintainRequest(RequestTable requestTable) {
    //把requestTable的requstMap内容添加到mainRequestTable的requstMap中
    }

流程架构

​ 本次作业在上一次的基础上迭代,三类线程:InputThread 输入线程,Schedule 调度线程,Elevator 电梯线程都需要修改。

InputThread

​ 输入线程一共会收到三种不同类型的 request ,用instanceof 来判断区分,并进行不同的操作;其中,对于 ElevatorRequestMaintainRequest 需求我们都需要对于电梯容器进行操作,因此向 InputThread 类中加入共享变量 schedule

java
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
//InputThread.java
public class InputThread implements Runnable {
private RequestTable mainRequestTable;
private Schedule schedule;

@Override public void run() {
try {
ElevatorInput elevatorInput = new ElevatorInput(System.in);
while (true) {
Request request = elevatorInput.nextRequest();
if (request == null) {
//标志mainRequestTable的endFlag
break;
} else {
if (request instanceof PersonRequest) {
//向mainRequestTable中加入request
} else if (request instanceof ElevatorRequest) {
//向schedule的elevators容器中加入request
//start()新的电梯线程
} else if (request instanceof MaintainRequest) {
schedule.maintainElevator(
((MaintainRequest) request).getElevatorId());
}
}
}
elevatorInput.close();
} catch (IOException e) {
//...
}
}
}
Schedule

​ 调度线程新增两个方法分别用于完成新增电梯和维护电梯两个要求:

  • public synchronized void addElevator(RequestTable requestTable, Elevator elevator)

    java
    1
    2
    3
    4
    5
    6
    public synchronized void addElevator(
    RequestTable requestTable, Elevator elevator) {
    //向电梯容器中新增电梯
    //向电梯表中新增电梯表
    //改变电梯elevatorNum
    }
  • public synchronized void maintainElevator(int id)

    在调度线程中维护方法主要进行下面几个步骤:

    1. 将维护电梯的 maintainFlag 标记好;

    2. 等待适当的时间,让被维护电梯可以把电梯内剩余的人全都放回自己的电梯表中;

      经过大佬们的测试,似乎 0.5s 是相对最优的等待时间,但是具体还有待验证【欢迎评论区浇浇~】

    3. receiveMaintainRequest 将被维护电梯表中的 request重新投回mainRequestTable;

    java
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public synchronized void maintainElevator(int id) {
    for (int i = 0; i < elevatorNum; i++) {
    if (elevators.get(i).getId() == id) {
    elevators.get(i).setMaintainFlag(true);
    while (!requestTables.get(i).isEnd()) { //注意是否会超CPU
    Thread.sleep(500);
    }
    mainRequestTable.receiveMaintainRequest(requestTables.get(i));
    //在电梯容器中删去被维护的电梯
    return;
    }
    }
    }
Elevator

​ 本次电梯线程的策略 Strategy 类不需要改变,只需要增加一些自己的特殊属性和用于维护电梯的方法:

java
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
//Elevator.java
public class Elevator implements Runnable {
private int id;
private int capacity;
private double speed;
private int nowNum;
private int nowFloor;
private int direction; // 0表示上升, 1表示下降
private boolean maintainFlag;
private HashMap<Integer, ArrayList<Person>> destMap; //目的地在Interger的所有Person
private RequestTable requestTable;
private Strategy strategy;

@Override public void run() {
try {
while (true) {
Advice advice =
strategy.getAdvice(capacity, nowFloor, nowNum,
direction, maintainFlag, destMap);
if (advice == Advice.MAINTAIN) {
if (nowNum != 0) {
//...
maintain();
Thread.sleep(400);
//...
}
//...
requestTable.setEndFlag(true);
break;
} else //...
} catch (InterruptedException e) {
//...
}
}
//方法......
}
  • 维护电梯的方法主要涉及两个:

    1. public void setMaintainFlag(boolean maintainFlag)

      java
      1
      2
      3
      4
      5
      6
      public void setMaintainFlag(boolean maintainFlag) {
      this.maintainFlag = maintainFlag;
      synchronized (requestTable) {
      requestTable.notifyAll();
      }
      }

      **注意:**本次作业中一共有三个方法用到了 notifyAll() ,分别为addRequest()delRequest()setMaintainFlag()

    2. public void maintain()

      java
      1
      2
      3
      4
      public void maintain() {
      //当toFloor == nowFloor时,直接输出OUT
      //当toFloor != nowFloor时,输出OUT之后,把电梯中的这个人重新投入本电梯表
      }

优化方法

​ 如下给出两种简单的的优化方法:

  • 新增电梯时,将其他电梯内等待队列所有请求返回总队列进行重新调度;
  • 维护电梯时,若电梯线程在开门状态中被通知 maintain ,则直接放所有人离开电梯,并维护。

第七次作业

本次作业需要完成的任务为:

  1. 全能电梯->只能到达部分楼层的电梯

    • Person 增加中间态到达楼层
    • 调度算法改变
    • 乘客出电梯即到达目的地->需判断 nowFloor = toFloor,若否返回请求队列重新调度
  2. 楼层停靠自由 ->楼层停靠服务电梯数限制

    • 电梯开门前需判断楼层停靠状态,获取和释放资源

UML类图

hw7UML

  • 本次作业的UML时序图与HW6一致OO电梯调度第二次作业

代码架构

数据结构

​ 本次作业在上一次的基础上迭代,原来的 RequestTable 类不需要改变,Person 类需要加一个新的变量,来满足换乘电梯规划路径的要求。

Person

​ 增加一个变量 nextFloor ,用于存储规划换乘最短路径时,电梯需要将人送到的下一个楼层。

注意: 下一个楼层 ≠ 最终目标楼层

java
1
2
3
4
5
6
7
8
//Person.java
public class Person {
private int id;
private int fromFloor;
private int toFloor;
private int nextFloor;
//方法......
}

流程架构

​ 本次作业在上一次的基础上迭代,三类线程:InputThread 输入线程,Schedule 调度线程,Elevator 电梯线程都需要修改。

  • 线程终止条件

    • 问题:当某台电梯被维护将请求返回请求队列但电梯线程均已结束时,没有电梯相应请求

    • 解决方法:

      当输入线程结束并处理完成所有请求后结束调度和电梯线程

      • 设置单例模式的计数器
      • 判断 总队列 + 电梯队列 + 电梯内 是否都为空
InputThread

​ 输入线程需要改变两个条件:

  • 终止条件:从官方包得到的request为空 + 所有的电梯表和电梯内都空
  • 等待条件:从官方包得到的request为空 + 电梯表或电梯内有人
java
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
//InputThread.java
@Override public void run() {
try {
ElevatorInput elevatorInput = new ElevatorInput(System.in);
schedule.updateGragph();
while (true) {
Request request = elevatorInput.nextRequest();
if (request == null && schedule.allEmpty()) {
//标志mainRequestTable的endFlag
break;
} else if (request == null) {
synchronized (mainRequestTable) {
mainRequestTable.wait();
}
} else if (request instanceof ElevatorRequest) {
//向schedule的elevators容器中加入request
//start()新的电梯线程
schedule.updateGragph();
} else //...
}
elevatorInput.close();
} catch (IOException e) {
//...
}
}
Schedule

​ 调度线程增加三个二维变量,用来构建图,方便计算最短路径:(这里优先选择换乘数最少的路径,认为它最短,因为这样可以最大程度避免 Maintain 带来的时间代价)

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//Schedule.java
public class Schedule implements Runnable {
private RequestTable mainRequestTable;
private ArrayList<RequestTable> requestTables;
private ArrayList<Elevator> elevators;
private int elevatorNum;
private double[][] graph;
private int[][] dis; // dis[i][j] 从i点到j点要搭乘电梯数量
private int[][] path; // path[i][j] 从i点到j点的路径

public synchronized int bestElevator(Person person) {
int num = -1;
if (dis[person.getFromFloor()][person.getToFloor()] != 0) {
bfs(person.getFromFloor(), person.getToFloor());
}
int next = getNextPoint(person.getFromFloor(), person.getToFloor());
for (int i = 0; i < elevatorNum; i++) {
//将该请求加入能同时到达fromFloor和nextFloor的电梯
}
person.setNext(next);
return num;
}
//方法......
}

​ 此外,调度线程还需要增加两个地方:

  • 电梯调度方法

    • 深度优先搜索:搜到一条可达路径,就更新请求路径,把请求放入相应电梯。

    • 广度优先搜索:搜索满足最少换乘数的可达路径.

    • 加权最短路:考虑换乘数电梯已有的请求数经过的楼层数等因素进行合适的权重分配,求解加权最短路。

    • 路径更新:

      • 静态路径更新:对于每个新请求,在调度时记录完整路径,仅当路径中电梯被维护时重新规划。
      • 动态路径更新:每次路径规划仅记录 nextToFloor ,当请求下电梯但未到达目的地时,就放回总队列重新调度
    java
    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
    //这里我的设计选择了“深度优先搜索”调度方法
    public synchronized void updateGragph() {
    for (int i = 1; i <= 11; i++) {
    for (int j = 1; j <= 11; j++) {
    dis[i][j] = -1;
    path[i][j] = -1; // 电梯elevators是从0开始的
    graph[i][j] = 0;
    }
    }
    for (int i = 0; i < elevatorNum; i++) {
    int access = elevators.get(i).getAccess();
    for (int j = 1; j <= 11; j++) {
    for (int k = 1; k <= 11; k++) {
    if (j == k || graph[j][k] != 0) {
    continue;
    }
    if ((access & (1 << (j - 1))) != 0
    && (access & (1 << (k - 1))) != 0) {
    graph[j][k] = 1;
    graph[k][j] = 1;
    }
    }
    }
    }
    }

    public synchronized void bfs(int from, int to) {
    dis[from][from] = 0; //起点

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(from);
    while (!queue.isEmpty()) {
    int tfloor = queue.poll();

    for (int i = 1; i <= 11; i++) {
    if (dis[from][i] == -1 && graph[tfloor][i] != 0) {
    dis[from][i] = dis[from][tfloor] + 1;
    path[from][i] = tfloor;
    queue.offer(i);
    }
    }
    }
    }

    private synchronized int getNextPoint(int from, int to) {
    if (path[from][to] == from) {
    return to;
    } else {
    return getNextPoint(from, path[from][to]);
    }
    }
  • public synchronized boolean allEmpty()

    java
    1
    2
    3
    4
    5
    6
    public synchronized boolean allEmpty() {
    for (int i = 0; i < elevatorNum; i++) {
    //遍历电梯表和电梯内都空
    }
    return true;
    }
Elevator

​ 电梯线程中使用信号量 Semaphore ,来实现楼层停靠服务电梯数限制:

  • outAndInSemaphore 初始值为 4
  • inSemaphore 初始值为 2
java
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
//Elevator.java
public class Elevator implements Runnable {
//...
private int access;
private ArrayList<Semaphore> outAndInSemaphore;
private ArrayList<Semaphore> inSemaphore;

@Override public void run() {
try {
while (true) {
Advice advice =
strategy.getAdvice(capacity, nowFloor, nowNum,
direction, maintainFlag, destMap);
if (advice == Advice.MAINTAIN) {
if (nowNum != 0) {
tryMaintain();
}
//...
break;
} else if (advice == Advice.OPEN) {
try {
outAndInSemaphore.get(nowFloor).acquire();
if (!destMap.containsKey(nowFloor)) {
try {
inSemaphore.get(nowFloor).acquire();
printOpenAndClose();
} finally {
inSemaphore.get(nowFloor).release();
}
} else {
printOpenAndClose();
}
} finally {
outAndInSemaphore.get(nowFloor).release();
}
} else //...
}
} catch (InterruptedException e) {
//...
}
}

public void printOpenAndClose() throws InterruptedException {
//使用官方包中输出接口
}

public void printMaintain() throws InterruptedException {
//使用官方包中输出接口
}
//方法......
}
  • public void out()

    需要注意的是out()要服从下面的执行顺序,否则会出现逻辑错误:

    1. 遍历将nowFloor != toFloor 的人重新加入mainRequestTable
    2. 改变nowNum ,从desMap中删除 nowFloor 的需求;
    3. 唤醒mainRequestTable
    java
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public void out() {
    for (int i = 0; i < destMap.get(nowFloor).size(); i++) {
    //...
    if (destMap.get(nowFloor).get(i).getToFloor() != nowFloor) {
    synchronized (mainRequestTable) {
    Person person = destMap.get(nowFloor).get(i).clone();
    person.setFromFloor(nowFloor);
    mainRequestTable.addRequest(person);
    }
    }
    }
    nowNum = nowNum - destMap.get(nowFloor).size();
    destMap.remove(nowFloor);
    synchronized (mainRequestTable) {
    mainRequestTable.notifyAll();
    }
    }
  • public void tryMaintain()

    java
    1
    2
    3
    public void tryMaintain() throws InterruptedException {
    //类比advice == Advice.OPEN的使用信号量的操作
    }

复杂度分析

​ 最终版代码复杂度如下:

Class OCavg OCmax WMC
Strategy 4.5 8.0 27.0
Schedule 4.1 11.0 41.0
RequestTable 1.8 4.0 18.0
Person 1.0 1.0 11.0
MainClass 3.0 3.0 3.0
InputThread 4.0 7.0 8.0
Elevator 2.263157894736842 11.0 43.0
Total 151.0
Average 2.559322033898305 6.428571428571429 18.875

​ 其中有几个方法的复杂度格外高,是不足之处,也是有待优化之处:

Method CogC ev(G) iv(G) v(G)
Elevator.in() 16.0 5.0 7.0 9.017.0
Elevator.run() 20.0 4.0 10.0 12.0
RequestTable.getOneRequest() 4.0 4.0 3.0 4.0
Schedule.bestElevator(Person) 33.0 1.0 12.0 16.0
Schedule.run() 13.0 4.0 8.0 9.0
Schedule.updateGragph() 19.0 5.0 2.0 10.0
Strategy.canOpenForIn(int, int, int, int) 8.0 5.0 5.0 8.0
Strategy.getAdvice(int, int, int, int, boolean, HashMap>) 17.0 8.0 4.0 9.0
Strategy.hasDesInOriginDirection(int, int, HashMap>) 12.0 6.0 4.0 6.0
Strategy.hasReqInOriginDirection(int, int) 12.0 6.0 4.0 6.0

测试

  • 本单元作业在测试运行时,不能直接使用 IDEA 的运行窗口,而是要用课程组给的官方投喂包,具体使用方法在 datainput使用说明 中。

  • 大佬们的评测机~

    如下给出几种常见的定位bug的方法:

死锁 + Real时间超时 + CPU时间超时

  • 有两种常见的检查多线程安全问题的方法:
    1. 在线程中输出
    2. Jconsole 插件
在线程中输出

​ 在线程不同地方输出相应语句,在运行窗口中看一直卡着无限输出的语句,就是问题所在之处。

Jconsole插件

IDEA 中自带的 Jconsole 插件,它可以帮助检查死锁CPU时间超时的问题 :

  1. 首先运行插件工具,在 cmd 命令行执行 jconsole 命令;

    如果未找到该命令,则可以手动查找正确版本的 java 安装目录下的 bin 目录,将该目录加到系统Path 环境变量中或者直接在该目录下运行 jconsole.exe

  2. 接着单击连接自己正在本地运行的代码 .jar 包,选择不安全的连接,等待连接成功;

    1

  3. 连接成功后得到如下窗口

    2

    • 概览:查看线程数量、类数量、堆内存使用量等数据

    • 内存:查看各内存各部分的占用比例,可以手动触发GC

    • 线程:多线程调试的关键,可以手动查看各个线程的运行状态,并且可以通过堆栈跟踪分别查看每个线程目前执行位置,这正是我们可以用来查找死锁的方式。点击下方检测死锁可以一键筛选死锁线程进行进一步分析

      3

    • VM概要:可以查看进程CPU时间,对于轮询sleep等方案的调试可以进行数据构造和检查以排查CPU-TLE

强测Bug

HW5

  • hw5强测我一共有两个bug,修改之处如下:

    bug

    • 没有在mainRequestTable变量 wait() 前面加一个 if 判断 !isEnd()

    • CPU时间爆掉

      在我的 public int bestElevator(Person person) 方法中,有一个 while ,它虽然不会死循环,但是会执行很多次无用的循环,故而它爆掉了CPU时间。

HW6

  • 对于ArrayList 的变量当需要遍历删减元素的时候,需要逆序遍历判断并删除:

    java
    1
    2
    3
    4
    5
    6
    7
    public void in() {
    int sum = requestTable.getRequstMap().get(nowFloor).size();
    for (int i = sum - 1; i < 0; i++) { //逆序遍历判断并删除
    if(/*条件*/)
    //remove
    }
    }

HW7

  • hw7强测我一共有一个bug:把每一个需求分配给电梯的时候,我们选择将 nextFloor 作为desMap 的“小阶段目的地”,但是我并没有把原来hw5、hw6的遗留的 getToFloor 方法迭代成getNextFloor

反思

​ 在测试debug的时候,我们不能单纯地依赖于大佬们的评测机,还是要自己把整体的代码从头到尾一行行仔细浏览一遍,才能确保每个细节都完成的迭代,毕竟人脑难以一下子考虑出所有纷繁复杂的细节,不能偷懒!【小女子面壁思过ing 哭唧唧~】

后记

​ 第二单元总体来说是非常有挑战的,但是同样收获也非常多,我们不仅学习了多线程、锁、线程安全、读写锁、原子变量等等新知识点,还接洽了 OS 课程,本学期的两门课程都涉及到了多线程的重点学习,因此融会贯通也将给我们带来更大的收获。