BUAA面向对象迭代开发总结-多线程与电梯管理

shiki2025-04-192025-04-19

面向对象第二次迭代作业——电梯管理与多线程

作业任务

本次作业主要实现一个有6部电梯的电梯管理系统，每部电梯并行运行，因此考虑使用多线程编程

本次作业含有三次迭代，分别要求实现满足如下几点要求的程序：

乘客指定自己要乘坐的电梯并指明自己的起始楼层和目标楼层。
乘客不再自己指定电梯，由程序为其分配电梯，并加入了电梯的临时检修调度状态。
加入双轿厢电梯改造，指定两部电梯，指定两部电梯的公共楼层，并改造为双轿厢（共用一个电梯井，一个电梯在共享楼层以下运行，另一个在共享楼层以上运行）。

三次迭代架构

第一次迭代

UML类图如下：
UML协作图如下：
类的设计：
- Input：继承Runnable，读取输入，传给CentralControl，输入结束后结束线程。
- CentralControl：继承Runnable，终端控制线程，接收输入线程传入的电梯请求，根据其指定的电梯将各个请求分发给对应电梯，输入线程结束，所有电梯完成所有作业后，结束线程。
- Threads：统一管理电梯线程的创建和结束。
- Elevator：电梯线程，接受终端控制线程分发的任务并根据一定策略将乘客运输至相应楼层。
- Output：通过同步块实现顺序输出。
- Passenger：乘客类，维护乘客优先级，目标楼层等信息。

第二次迭代

UML类图如下：
UML协作图如下：
类的设计：

多数类同第一次迭代，新增如下类：
- Strategy：封装电梯运行的策略。
新增一些方法：
- CentralControl：乘客不再指定电梯，故新增分配策略，新增电梯临时调度任务的分配方法。

第三次迭代

UML类图如下：
UML协作图如下：
类的设计：

多数类同第二次迭代，新增如下类：
- FloorMap：实现输入的电梯楼层（String类型）与为了方便而设计的电梯楼层整数表示（int类型）之间的映射，并封装（这个部分其实应当在第一次迭代就完成）。
- ExchangeFloor：双轿厢改造后的共享楼层，维护了在共享楼层上方和下方运行的电梯id，双轿厢改造是否准备开始和是否完成的标识，是否有电梯正处于共享楼层。

多线程模型

采用两层生产者-消费者模型

Input作为生产者，CentralControl作为消费者
CentralControl作为生产者，Elevator作为消费者

主要思路为输入线程只负责解析输入，将解析后的结果交给终端控制线程，终端控制线程只负责将收到的请求根据一定分配策略分发给各个电梯线程，至于电梯线程如何执行任务终端控制线程不做任何干涉，电梯线程只处理终端控制线程分配给其的任务，完成所有任务后结束，其余不再考虑。通过这种设计思路，实现了输入线程，终端控制线程，电梯线程的内聚，避免各种线程之间的耦合。

同步锁

生产者-消费者模型中的同步锁

由于生产者线程和消费者线程之间的并发处理，他们必然需要访问任务列表这一共享资源，为了保证线程安全，使用`synchronized``同步代码块实现代码同步，示例如下：

// 生产者
while(true) {
    synchronized (taskes) {
        if (isFull) {
            tasks.wait();
        }
        // 生产
        ss.notifyAll();
    }
    if (couldEnd()) {
        break;
    }
}

// 消费者
while(true) {
    synchronized (taskes) {
        if (isEmpty) {
            tasks.wait();
        }
        // 消费
        ss.notifyAll();
    }
    if (couldEnd()) {
        break;
    }
}

执行双轿厢改造过程中的同步锁

为了保证两个电梯在并发完成改造前置条件之后，同时开始改造任务，同时结束改造任务，使用同步锁使两个线程实现同时开始改造任务。此部分介绍将在后面的双轿厢电梯同步改造和安全运行部分详细展开。

防止双轿厢电梯相撞使用同步锁

当一个电梯进入双轿厢共享楼层时，先判断是否有伙伴电梯在共享楼层中，如果有则wait，等待伙伴电梯离开共享楼层后唤醒，否则直接进入共享楼层。此部分介绍将在后面的双轿厢电梯同步改造和安全运行部分详细展开。

调度器与策略

调度器策略

电梯运行性能主要有3个指标：

总运行时间：电梯完成所有任务程序结束的时间。
任务平均完成时间：根据电梯乘客优先级的运输时间加权平均数。
电梯总耗电量：与电梯移动次数和开关门次数有关。

综合考虑上述3个指标，此处采用优先分配空闲电梯，其次分配运行方向相同的电梯，最后分配距离最近的电梯。优先分配空闲电梯避免短时间大量乘客进入导致一个电梯任务繁重而其他电梯空闲。其次分配运行方向相同的电梯使电梯的捎带功能发挥，节省时间和电量。最后分配距离最近的电梯是在无满足上述两种情况的电梯时的迫不得已之举，选一个最近的电梯，比选其他距离很远的电梯有优势。

但是这种策略还有一些问题，下面介绍这些问题和解决方法：

调度和改造过程中不可以被分配任务：给电梯加一个标识，表示其是否在进行调度或是否进行改造，如果是则直接跳过，不给其分配任务。
电梯满员：电梯满员时再为其分配任务，其也不能再继续接纳乘客，因此判断电梯是否满员，如果是则直接跳过。
集中分配问题：每部电梯都有少量任务（不空闲），此时短时间内接收大量乘客，且这些乘客在上述三种分配条件约束下只能分配给同一个电梯，这会导致所有乘客全部被分配给同一个电梯，导致某一电梯任务繁重，因此为电梯设置任务数量上限，超过这个上限则不为其分配任务。
没有一部电梯满足导致乘客未被分配：这种情况下可以先不给乘客分配电梯，等待有符合条件的电梯出现时再分配。
双轿厢电梯部分楼层无法到达：根据乘客起始楼层和目标楼层可知其行动区间为\([x_1,y_1]\)，其中\(x_1=min\{fromFloor,toFloor\}\)，\(b_1=max\{fromFloor,toFloor\}\)。同理可知电梯运行区间\([x_2,y_2]\)，为该电梯分配乘客时，需要满足如下条件：

\[ max\{x_1,x_2\}<min\{y_1,y_2\} \]

电梯运行策略

此处主要采用look算法，即电梯在上升时需要上升到顶层或上方的所有楼层均没有需要接收的乘客或没有需要运输至上方楼层的乘客时（电梯下降时同理），判断其是否需要调转方向，如果是则改变方向，否则停止。

电梯捎带策略

电梯到达某一层时，先判断其是否需要下乘客，下客结束后，判断该层乘客中是否有行动方向（例如：从低楼层到高楼层为向上）与电梯运行方向相同的乘客，如果有，则上电梯，其余乘客在该层等待不上电梯。如果此时出现了超员现象，则对需要需要上电梯的乘客和电梯内的乘客根据优先级排序，对于优先级高的乘客，如果他不在电梯内则进入电梯，并将优先级最低的乘客移出电梯，使其进入调度器等待再分配。

双轿厢电梯同步改造和安全运行

双轿厢改造

部分代码如下：

// 完成前置条件
synchronized (exchangeFloor) { // 同步开始
    if (!exchangeFloor.isReady()) {
        exchangeFloor.setReady();
        try {
            exchangeFloor.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    } else {
        exchangeFloor.outBegin();
    }
    exchangeFloor.notifyAll();
}
// 改造过程
synchronized (exchangeFloor) { // 同步结束
    if (exchangeFloor.isReady()) {
        exchangeFloor.serUnready();
        exchangeFloor.outEnd();
        try {
            exchangeFloor.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    exchangeFloor.notifyAll();
}

阅读上述代码可知，假设1号和2号完成前置条件开始改造，若1号先完成，则会wait，2号电梯完成前置条件后进入同步块，由于1号电梯设置了ready信号，2号电梯不会进入if语句，进入else语句中输出开始后唤醒1电梯，同步结束同理。

避免双轿厢电梯相撞

此处采取的策略为，尽量不在共享楼层停留，即进入共享楼层完成任务后，立刻离开共享楼层。部分代码如下：

synchronized (exchangeFloor) {
    if (exchangeFloor.isIfOccupied()) {
        try {
            exchangeFloor.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    exchangeFloor.occupy();
    // 进入共享楼层完成任务并离开
    exchangeFloor.unoccupy();
    exchangeFloor.notifyAll();
}

阅读上述代码可知，在进入共享楼层时，如果共享楼层已经有电梯在工作了，则wait，等待其完成任务后唤醒，否则，进入共享楼层完成任务后离开，并唤醒正在等待进入共享楼层的电梯。

在共享楼层完成任务时需要注意：若下电梯的乘客未到达目标楼层，需要将其交给调度器，由调度器重新分配。

发现的Bug与debug

Bug的发现

本次作业中第一次迭代和第三次迭代未发现bug，第二次作业中发现了一处死锁。

死锁产生的原因：在嵌套锁中，如果两个线程嵌套顺序不同，则会产生死锁，具体过程为：假设线程1中锁A在外层，锁B在内层，线程2中反转嵌套顺序，线程1先进入锁A，占有锁A，线程2接着进入锁B，占有锁B，此时线程A不能获得锁B，被阻塞，线程2不能获得锁A，被阻塞，死锁产生。

debug策略

使用测评机，但是为了更容易发现bug，生成的数据应当在投喂时间内的几个离散的时间点上分别输入大量请求。
编写TestMain类，在该类中可输出各个线程的状态，通过各个线程的状态判断此时是否出现死锁，死循环，线程未正确结束等问题。

心得体会

线程安全：对于多个线程都会访问和修改的资源，需要在访问和修改时使用同步锁进行保护，例如：一个线程使用迭代器遍历某个列表，另一个线程此时正在删除列表中的元素，如果不使用同步锁进行保护，则第一个线程产生数组越界异常，使用同步锁使读写某个共享资源的操作同步，即可避免这种情况的产生。
层次化设计：在本次设计中，明确输入线程只负责输入，调度器线程只负责分配，电梯线程只负责处理被分配给自己的任务，之后的设计只需要逐项完成各个部分的要求，并给其他线程留出需要的接口，即可清晰地完成整个项目的设计，同时，层次化设计带来的清晰的逻辑结构也使bug数量大大减少。