BUAA_2025_Unit2_多线程电梯调度

在正式开始之前，我们先简单回顾一下三次作业：

  • 输入指定电梯的乘客请求，利用生产者-消费模式实现乘客运算
  • 增加调度请求，不再指定乘客电梯，新增receive约束
  • 实现双轿厢电梯改造

第一次作业分析

1.1 UML类图

hw5

1.2架构分析

通过对指导书的分析，我们可以将任务分为三个线程：

  • InputHandler： 输入处理线程，将输入请求存储到主队列。
  • Schedule: 调度器线程，将主队列的请求分发至对应电梯的子队列
  • Elevator: 电梯线程，将乘客运送至目的地
调度器派发请求

本次作业中，虽然对于每一个请求均指定了对应的电梯，可以在InputHandler中就将对应请求派发至对应电梯对应等待队列。但是考虑到后续迭代可能得复杂性以及降低耦合度等考虑，我还是设计了一个调度器——Schedule,主要负责将主队列的请求分配至对应电梯的子队列。

1
2
3
public void dispatch(Person person) {
    subQueues.get(person.getElevatorId()).addRequest(person);
}
电梯线程与调度策略相分略

对于电梯我们进行了” 电梯类与策略类“的分离，策略类依据LOOK算法，接受当前电梯的楼层、电梯内部人数与运行方向等信息作为参数，向电梯传入运行指令MOVE/WAIT/REVERSE/OPEN/END等

LOOK电梯调度算法
  • 初始时候为电梯规定一个初始方向
  • 电梯到达某一楼层时候，首先判断是否需要开门(OPEN)
    • 如果电梯内有人到底目的楼层，则开门让乘客出去
    • 发现该楼层中有人想要上电梯，且电梯非满员，乘客想要移动方向与电梯当前方向相同
  • 接下来判断电梯内部是否有人
    • 如果电梯里面有人，则沿着当前移动方向继续移动到下一层(MOVE)
    • 如果电梯里面没人，则检查当前电梯所服务的请求队列是否为空
      • 如果请求队列为空，且当前子队列线程没有结束，则电梯停留等待(WAIT)
      • 如果请求队列未空，且当前子队列线程已经结束，则电梯线程结束(EOF)
      • 如果请求队列非空，且存在某请求的出发地是电梯“前方”(MOVE)
      • 如果请求队列非空，且所有请求的出发地是电梯“后方”或与电梯同楼层但是目的地在后方，则电梯转向(REVERSE)

具体在Stragety中实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Command getCommand(int curFloor, int direction, int personNumInElevator) {
    if (canPersonOut(curFloor, personNumInElevator)
            || canPersonIn(curFloor, direction, personNumInElevator)) {
        return Command.OPEN;
    }
    if (personNumInElevator != 0) {        // 电梯里面有人
        return Command.MOVE;
    }
    if (requestsQueue.isEmpty()) {   // 请求队列为空
        if (requestsQueue.isEnd()) {
            return Command.END;
        } else {
            return Command.WAIT;
        }
    } else {    // 请求队列不为空
        if (isAheadExistReq(curFloor, direction)) {
            return Command.MOVE;
        } else {
            return Command.REVERSE;
        }
    }
}

而电梯线程只需要按照策略类给出的指令执行即可

生产者-消费者模型与线程安全设计

在该情景中，InputHandler是生产者，提供需求。而Elevator是消费者，“消费请求”。所以主队列MainQueue和子队列SubQueue就是线程间的共享对象，为了保证线程安全性，我们需要对其进行加锁。

  • 在共享对象类中，我主要采用了synchronized对所有方法加锁以确保线程安全，并在方法结束前进行notifyAll()唤醒等待线程

    但是需要注意的是可能存在虚拟唤醒情况，在下述情况中wait可能被isEmpty()方法等虚拟唤醒，所以wait结束之后队列可能依旧为空，所以依旧有必要进行队列非空检查

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public synchronized Person removeFromMainToSub() {
         if (isEmpty() && !isInputEnd()) {
             // 暂时没有请求但是输入并没有结束，将锁交给其他线程inputHandler,为其增加请求
             try {
                 wait();
             } catch (InterruptedException e) {
                 throw new RuntimeException(e);
             }
         }
         if (isEmpty()) {
             notifyAll();
             return null;
         }
         ...
     }

  • 在电梯线程中，我采用的是synchronized对于对象加锁，例如在Elevator.java中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    else if (command == Command.WAIT) {
          synchronized (requestsQueue) {
                try {
                    requestsQueue.wait();
                  } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                  }
               }
             }

  • 同时为各类的非可变成员变量加上了final字段，进一步增强代码安全性

    • final 字段修饰非引用数据类型：该数据不可再被改变，适合一次赋值变量，例如id

    • final字段修饰引用数据类型：该引用不可变，但是引用所指向对象的内容可变。例如

      1
      2
      3
      4
      5
      6
      public class Holder {
          private final List<String> list = new ArrayList<>();
          // list引用不可变，但内容可变，需同步修改操作
              list.add(item); // 可以
          	list = new ArrayList<>(...); // 错误 
      }

    synchronized用法总结

  • 同步代码块（锁对象需显式指定）synchronized (lockObject) {// 临界区代码}

  • 实例方法（锁对象为当前实例 this）public synchronized void method() {// 临界区代码}

  • 静态方法（锁对象为类的 Class 对象,同一类的所有对象）public static synchronized void staticMethod() {// 临界区代码}

1.3性能优化

此次作业中我并没有进行过多性能优化(甚至可以说没有)

  • 在电梯对应的子队列中，按照请求优先级进对请求排序，优先处理优先级高的队列
  • 在电梯开门让到达目的地乘客出去之后，再次请求策略类电梯是否转向，再让乘客进入电梯。（减少电梯OPEN-OUT-CLOSE-(REVERSE)-OPEN-IN-CLOSE这种情况为OPEN-OUT-IN-CLOSE，减少耗电量)

实际上，含有一个可以优化的是如果电梯满员时候有优先级更高的人要上电梯，那么可以”踢出”已经在电梯内的优先级比较低的人换成优先级高的乘客。

1.4 Bug测试

在此次作业的强测和互测中，我均没有出现bug

在互测中，我hack了同房间的一位同学的bug,主要是产生了NullPointerException问题。

测试点如下：

1
2
3
4
5
6
7
[3.0]1-PRI-1-FROM-B1-TO-F3-BY-6
[3.0]2-PRI-2-FROM-B1-TO-F7-BY-6
[3.0]3-PRI-3-FROM-B1-TO-F7-BY-6
[3.0]4-PRI-4-FROM-B1-TO-F7-BY-6
[3.0]5-PRI-5-FROM-B1-TO-F7-BY-6
[3.0]6-PRI-6-FROM-B1-TO-F7-BY-6
[3.0]7-PRI-7-FROM-B1-TO-F7-BY-6

在观察代码之后，我发现该同学在电梯满员且有优先级更高的乘客想要上电梯时候

，会将电梯内部优先级低的乘客踢出去。

1
int numKick = getWantInRequest() + curNum - maxNum;

之后会才从电梯内部的乘客表类中删除numKick个乘客。但是如果是这种情况就会出错

1
2
3
getWantInRequest() = 10
curNum = 1;
maxNum = 6;

这就会导致出现numKick 大于curNum,在遍历删除更新该条请求信息时候可能会触发空指针错误。

自动化测试

在本次作业中，我第一次搭建了我的评测机，但是由于题目的并发性等特殊特点，我的测试效果并不是很好。

  • 测试时间长：利用官方包进行按时投放数据。那么每一次测试数据投放结束并获取输出可能需要50s左右。同时我又采取了串行测试，没有利用多线程测试，导致测试时间异常长。下一次作业我一定要采用多线程测试(…)
  • 并发性不好：在数据生成中，我采用了50s范围内生成70-100条数据，这就导致了同一时刻发出请求数很少，可能难以达到压力测试特点。在研讨课听了同学的分享之后，我计划采用分阶段测试：将测试点分为正常段和压力测试段。在压力测试端，缩小时间尺度并相对增大该时间尺度内的指令条数，可以增大测试点压力。

感谢研讨课同学有关自动化测试的分享，受益匪浅。

第二次作业分析

架构分析

此次作业主要新增了以下几点：

  • 乘客请求不再指定电梯，需要自行设计电梯分配策略
  • 新增临时调度请求
  • 新增RECEIVE约束，修改OUT指令输出格式

UML 类图

src.drawio (1)

**ElevatorManger**管家类的实现与调参分配

由于此次作业需要自行设计乘客分配策略，而在分配时需要综合各电梯运行情况（电梯内乘客数、电梯侯乘表人数等）进行分配，也就是需要掌握电梯的详细信息后并进行适当计算分析。而原有调度器作为线程类，我觉得不是承担此功能的良好角色，故在此基础上，我设计了ElevatorManger进行乘客请求分配，避免调度器线程直接与电梯线程进行交互

ElevatorManger采用单例模式，对外提供getInstance()方法,具体成员变量如下：

1
2
3
private static ElevatorManager elevatorManager;   
private final HashMap<Integer, SubQueue> subQueues;
private final HashMap<Integer, Elevator> elevators;

在调度器线程中调用ElevatorManger的dispatch(personRequest)方法，将待分发指令传递给ElevatorManger,同时实现calcPerformance()方法去对乘客请求与电梯运行情况的匹配度进行评分。根据评分具体决定乘客应该派发给哪部电梯。

1
double result = -1 * distance + 1 * isDirSame - 2.5 * perNumInEle - 2.5 * reqNum - 10 * isSche;   //电梯方向，电梯内部人数，电梯请求队列人数，电梯是否正在调度

由于时间原因，未进行参数调试，所以性能不佳

此外，我并未将电梯的电量因素纳入到性能评价函数中

调度请求的处理

我的调度请求处理流程如下：

  • scheRequest传递至电梯线程，strategy类发出SCHE指令

  • 输出begin

  • subQueue.removeReqFromSubtoMain，将电梯的侯乘队列的乘客(已经receive给对应电梯)重新移动到主队列进行调度，自动解除receive关系

  • 电梯移动至目标楼层

  • 输出OPEN指令，并removePersonInEleToMain()将电梯内乘客全都释放

  • 休眠1s后依次输出CLOSE和END

  • removeReqFromBufferToSub，将电梯缓冲区乘客移动至电梯侯乘子队列

Buffer缓冲区设置

由于电梯在执行调度请求期间不可以进行receive操作，同时为了避免6部电梯同时调度时候乘客请求无法及时分配需要新增wait操作(每加一个wait,都会让我对TLE多一份担心)。基于此，我对每部电梯均设置了缓冲区队列，即使电梯在调度，也会为其分配请求，只不过电梯会将其存入buffer中，在调度结束之后将buffer中乘客统一移动[removeReqFromBufferToSub]到换乘表中并输出RECEIVE

OUT处理

在电梯释放乘客时，检查当前楼层是否是乘客请求目标楼层。如若不是目标楼层，修改请求出发层，并将该条请求重新加入主队列中

由于主队列与多个线程与方法交互，我将其设置为了单例对象，方便调用

bug测试与优化

强测一个测试点5分，性能最多就能卷三四分。所以为了正确性保证，我将工作中心放在了测试上。事实上也确实测出了1个bug,所以赚啦

由于独自搭建评测机耗费了大量时间，以至于我没有进行参数调试以进行分配策略优化，所以性能分很低。（总之就是没有进行额外优化）

我的强侧与互测中均没有出现bug。在互测中利用评测机测出了房友bug，但无奈交到互测平台并没有成功

我在提交前自己测出了TLE的bug，主要是由于在从侯乘队列中取乘客时候，如果队列为空则执行了wait，而不会被正常唤醒

第三次作业分析

本次作业主要新增双轿厢电梯改造

UML 类图

src.drawio (2)

双轿厢电梯设计

调参函数特判

由于改造为双轿厢电梯之后，电梯不能到达所有楼层。例如目标楼层为4层且为上层电梯的话，则其不能接到出发楼层为3层及以下的乘客，所以需要在调度策略中保证乘客请求一定不会分发给对应电梯。否则对应乘客请求无法完成

1
2
3
if ((isA && personFromFloor < transferFloor) || (!isA && personFromFloor > transferFloor)) {
    result = -1 * Double.MAX_VALUE;
}

transferFloor与isA变量设置

为实现双轿厢电梯与普通电梯的统一管理，我们在原有电梯类中新增成员变量isA与transferFloor,isA为一个boolean类型变量，代表其是否为双轿厢电梯上层A电梯，transferFloor存储其作为双轿厢电梯的换乘楼层。其初始值为下：

1
2
this.isA = true;
      this.transferFloor = -100;

代表电梯初始可以到达-100层及F7层，符合普通电梯的运行范围。且在canPersonOut等的判断逻辑中，需要增加curFloor = transferFloor时的特殊判断，而由于普通电梯永远无法达到transferFloor,所以只需要在原有hw6基础作增加判断就可以了，不改变原有逻辑

同时性判断

由于改造为双轿厢的电梯存在共用换成层等行为，所以两电梯之间存在联系。我新建了工具类coordinate来完成双轿厢改造工作以及换乘层分配，将工具类作为成员变量在两电梯之间共享

由于一次双轿厢改造请求只能输出一组update_begin与update_end,所以需要在两电梯间进行同时性设置，begin之前两电梯均已做好准备工作，end前均已完成改造工作。具体伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void startUpdate(Update update, Coordinate coordinate) {
    	personInEleOut(); // 电梯内乘客出去
       coordinate.addAcceptCount();  // 告诉coordinate当前电梯线程已经准备好改造
       while(!coordinate.isReadyForUpdate()) {
           this.coordinate.wait();   // 如果另一电梯没有准备好则等待
       }
       coordinate.isBeginPrint();    // coordinate中无论该方法被调用多少次，只输出一次begin
       removeReqFromSubToMain();     // 取消已经receive相关请求
       resetStatus();                // 电梯状态重置
       coordinate.addFinishCount();  // 告诉coordinate当前电梯线程已经完成改造
       while(!coordinate.isFinishUpdate()) {
           this.coordinate.wait();   // 如果另一电梯没有完成则等待
       }
       subQueue.finishUpdate();       // 清除update指令
   }

共享楼层分配与锁的设置

为了防止配对电梯在共享楼层相撞，我们需要给共享楼层加锁，当电梯想要到达换乘楼层，调用coordinate中的lock方法(如若获取不成功，则等待)，而离开换乘楼层时调用unlock方法，同时唤醒等待线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public synchronized void lockransferFloor() {
    while (isOccupied) {
        try {
            wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    isOccupied = true;
}

public synchronized void unlockTransferFloor() {
    isOccupied = false;
    notifyAll();
}

为了避免双轿厢电梯在共享楼层时接到WAIT指令而一直占用共享楼层，我们在执行wait指令前特判当前楼层是否是共享楼层。如果是，则进行强制移动(题目中特意提到这不受receive约束，相比是为了提醒我们这件事吧)

bug测试

我在本次作业的强测与互测中均没有出现bug。

在课下自己debug中，我主要采取的TimbleOut.println("#日志"),即日志信息以”#”开头标记，在评测机的checker判断中忽略”#”开头的日志信息。在评测机判断输出错误时，会保留错误输出，自然其中也保留了当时的错误信息来帮助debug

迭代过程中的稳定与变化内容

在三次作业中，我并未进行重构工作，整体项目表现出了一定的稳定性。

稳定内容：

  • 策略类几乎不变。只在第三次作业加入双轿厢之后对于是否会有乘客进出进行了新的特殊判断(在共享楼层要将无法送达的乘客送出电梯)
  • 电梯原有的开关门，移动等的设计。我对一些基本的开关门以及移动等封装为了单独的函数。在加入调度与改造指令之后，我采用单个sche()方法等完全实现其指令，并未对原有部分进行修改。增量并非增改
  • …

变化内容：

  • 调度策略有所改变。第一次作业直接指定电梯，第二次作业中我新增了ElevatorManger实现电梯信息存储并调度其中的dispatch实现调参分配
  • 线程结束的标志改变：从输入线程结束且主队列为空到输入线程结束&&主队列为空&&调度指令结束到输入线程结束&&主队列为空&&调度指令结束&&改造指令结束&&乘客指令全部完成

时序图

image-20250420173218754

新的迭代场景

  • 乘客请求对关门时间的主观控制：参考现实乘梯经验，电梯关门往往是乘客按下关门按钮后触发关门操作的。可以为每条乘客请求增加是否会主动关门属性。如果电梯内乘客均不会主动关门，则在最大时间后电梯自动关门。否则依据电梯出入人次决定开关门时间，之后由乘客主动关门。这可能只需要在电梯线程的开关门操作openAndClose中对要出入的乘客属性与人次进行统计分析处理即可
  • 电梯在预设时间段内部分楼层不可达：可以在输入中新增电梯置位指令,例如Set-6-F1-F7-15-30指令可以使得6号电梯在15-30秒之间只可以到达F1-F7层。这可能需要为电梯增加最低楼层与最高楼层属性，并为ElevatorManger和Elevator增加与可达层范围设置相关的方法。

感觉想的这两个迭代场景都是小打小闹，并不会带来什么技术性的实现难度

程序结构度量

代码规模统计

image-20250413110917125

本次作业代码总计行数达到了1000行。第一次迭代约480行，第二、三次各约增量500行。其中三个线程类InputHandler约为50行，Schedule约为34行，但是Elvevator线程达到了350行。我个人认为作为线程对象，拥有这么多方法是不合理的，即使这可能是因为电梯本身业务比较多。一个好的解决办法可能是新建一个业务类，作为电梯线程的成员变量，在其中实现move,open等具体功能。可能由于我认为线程对象最好只实现run方法的偏见

其次，主队列与子队列作为各线程之间的信息传递者，承担功能多，不可避免的代码体积较多。

复杂度分析

image-20250413164059306

image-20250413164129051

  • Elevator.run()方法的复杂度是最高的，这主要是由于分支较多并且调用了众多其他方法导致的.此外我并没有想到什么好的办法或结构可以降低这个方法的复杂度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public void run() {
        while(true) {
            Command command = Strategy.getCommand();
            if(command == Command.MOVE){
                move();
            }else if(command == Command.OPEN){
                openAndClose();
            }else if(){
                ...
            }
        }
    }

  • Strategy.canPersonOut()方法的认知复杂度CogC复杂度较高，这可能是由于地三次迭代中双轿厢电梯的迭代引起的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for (Person person : personInElevator) {
        if(person.getToFloor == curFloor) {
            return true;
        }else if(curFloor == transferFloor && isA && person.getToFloor() < transferFloor) {   // 当前楼层为双轿厢电梯换成层且为A号电梯且乘客目标楼层在换乘楼层以下
            return true;
        }else if(curFloor == transferFloor && !isA && person.getToFloor() > transferFloor) {
            return true
        }
    }
    return false;

  • …

image-20250413165921591

而各类的加权平均复杂度也为Elevator和SubQueue最高

类间的耦合度分析

为了最大限度的降低两个线程间的耦合度（以防因为一个线程等待或睡眠而影响另一个线程），我在每两个需要交互的线程之间都设置了缓冲区，InputHandler(Thread) -- MainQueue -- Schedule(Thread) -- ElevatorManger -- SubQueue - Elevator(Thread)，由于调参策略需要六部电梯的信息，但是让6个电梯线程与调度线程交互的话线程间交互信息太多。所以我的ElevatorManger便起到了缓冲作用，同时降低两个线程之间的耦合度。

其次由于MainQueue中判断线程结束的条件为InputHandler.End()&&mainQueue.isEmpty()&&updateCount==0&&scheCount==0&&unfinishedPerson==0，所以在接受乘客请求与送达目的地，调度之后，改造前后均涉及到对主队列中的某些计数变量的修改，所以我将其设为了单例模式，方便各类对其访问。但这无疑增加了主队列与其他类之间的耦合度

心得体会

多线程编程中最容易出的问题就是线程安全问题。我个人采用的主要是synchornized对于共享对象的方法加锁与部分引用处synchronized(obj)加锁。通过本单元学习，我认为应该注意以下的线程安全问题：

  • 分清哪些对象是共享对象（即会被多个线程访问的对象）。然后根据需要判断是在共享对象类中采用方法块加锁或是synchronized(obj)加锁
  • 对于每一个wait()方法判断什么方法应该唤醒它，该方法处是否加了正确的notifyAll()，以及在while循环中使用wait等待，避免意外唤醒
  • 避免将容器作为参数或返回值传递，避免ConcurrentModificationExceptio问题
  • 线程的正常启动与结束
  • …

本单元的顶层是生产者和消费者模型,InputHandler输入，Schedule调度派发，Elevator完成消费者功能与输出。其次为了实现线程间的安全交互，我们在两个线程间设置了MainQueue和SubQueue等共享对象。同时为每个电梯实现自己的策略类，为一组双轿厢电梯实现相同的coordinate协作。

非常感谢学长的评测机分享，对我搭建评测机帮助巨大。

也感谢https://hyggge.github.io/与https://github.com/zhangyitonggg/BUAA-2024-OO两位学长的分享，我在代码架构设计过程中学习了其很多。

未来方向

我觉得电梯设计可以更考虑实际一点，比如开关们时间与电梯内要进出的乘客数量相关，且可以增加乘客请求属性，比如该乘客是否会主动按按钮关闭电梯，如若电梯内有此类乘客，可以缩小关门时间等。且某部电梯在某一个可能的高峰段（可能是预设的）只可可能在一个较小的区间运行（例如某部电梯在15-20s之间不会去地下楼层）

此外，是否有办法可以增强互测压力或者在为每个互测房间设置一个讨论区。由于多线程的随机性，我们的本地测试出错样例交到平台可能并不会触发错误，如果这时有互测房间的讨论区的话我们可以直接告诉房友其出错的样例点，避免可能单元结束其某个错误依旧没有被修正

个人仓库链接：含作业代码及评测机 https://github.com/KingCB0501/BUAA_2025_OO