[BUAA-OO] 第二单元：电梯调度

[toc]

概述

​ 面向对象第二单元的主题是电梯调度，主要学习的内容是多线程调度与线程安全。具体体现为维护六个电梯线程以及主线程，调度线程的协同工作。第二单元共有三次作业，分别是：

  • 乘客指定电梯的接送实现
  • 自定义分配方式和实现临时调度（SCHE）
  • 实现双轿厢（UPDATE）

​ 与第一单元相比，第二单元的码量有所下降，在实现的时候也相较来说更容易上手一些。但是第二单元的难点在于调试和debug，具体来说：多线程下，程序错误可能难以复现。可能存在潜在的轮询，特定情况下死锁等不易察觉和修改的问题。一句话说就是这单元debug会特别痛苦。另一个难点就是电梯的调度策略，实现一个调度策略比较简单，但是实现一个性能特别好的调度策略很难。

​ 下面我们具体来回顾一下第二单元的作业。

UML 类图与协作图

image-20250415203216271

OO_U2

b1a8ed2290ec35e722487abe172b0ad

OO_U2

第一次作业分析

​ 第一次作业的难点在于实现一个电梯调度算法。

​ 电梯调度算法指的是单电梯如何高效地完成已分配给他的所有请求。总所周知，电梯调度算法本身没有最优解，一个算法可能在某种情况下效率比较高，但总会出现一种情况使得该算法的开销和性能远远落后于别的算法。因此我们希望选取一个平均性能较好且比较稳定的算法，出于此考虑，我选择了往届学长推荐的LOOK算法。

LOOK算法

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
// LOOK算法，传入当前电梯状态和任务表，返回对当前电梯的建议( WAIT / OVER / MOVE / REVERSE / OPEN )
public Advice getAdvice(Elevator elevator, RequestTable requestTable) {
        int curNum = elevator.getCurNum();
        int curFloor = elevator.getCurFloor();
        int direction = elevator.getDirection();
        int capacity = elevator.getCapacity();
    	ArrayList<Person> myGuest = elevator.getMyGuest();
        ArrayList<Person> inElevator = elevator.getInElevators();
    
if (curNum == 0) {
            // 如果电梯里没人，先沿着当前方向寻找有无请求
            if (canOpenForIn(curFloor, curNum, capacity, direction, myGuest, inElevator)) {
                return Advice.OPEN;
            }
            if (myGuest.isEmpty()) {
                if (reqTable.isOver()) {
                    return Advice.OVER; //如果输入结束，电梯线程结束
                } else {
                    return Advice.WAIT; //如果输入未结束，电梯线程等待
                }
            }
            if (hasReqInOriginDirection(curFloor, direction, inElevator, myGuest)) {
                return Advice.MOVE; //如果有请求发出地在电梯前方，则前当前方向移动一层
            } else {
                return Advice.REVERSE;
            }
        }
        else {
            //当电梯有乘客时，沿当前方向运行，直到送完电梯内所有乘客
            if (canOpenForOut(curFloor, inElevator)) {
                return Advice.OPEN;
            } else if (byTheWay(curNum, capacity, direction, curFloor, inElevator, myGuest)) { // 捎带开门
                return Advice.OPEN;
            } else {
                return Advice.MOVE;
            }
        }

我们采用的算法是一种基于look算法的改进算法：

我们规定上电梯的乘客必须与当前电梯运行方向相同。

  • 当电梯内无人时，电梯先判断当前楼层是否需要开门接乘客，如有需要，开门接乘客（OPEN），进入有人状态；如不需要，判断是否该电梯是否有未完成的任务，如果没有未完成的任务，则等待（WAIT）或结束（OVER）。否则说明有未完成的任务，查询当前方向是有无请求，有则前进（MOVE），否则掉头（REVERSE）。
  • 当电梯内有人时，因为乘客的方向一定与电梯方向相同，因此电梯应当沿着当前方向运行。我们只需要分别判断是否需要开门让乘客下电梯和是否需要开门捎带同方向乘客，如有需要，开门（OPEN），否则前进（MOVE）。

第二次作业分析

​ 第二次作业的难点在于实现一个乘客分配算法。

​ 在乘客不指定电梯的情况下，我们需要有一个分配线程（Dispatch）将乘客请求分配到每部电梯执行，实现一个怎样的分配算法使得电梯系统能够尽快送达乘客是这次作业的重点。

​ 一个很自然也很简单的想法是随机均匀地分配任务到每部电梯，这样能保证一个较好的运行效率。但是问题也很明显：

  • 该算法可能会出现不必要的调度增加整个系统的开销。例如：六个人从一楼到七楼，只用一部电梯一次将六人送达是显然的最优解。
  • 随机分配会给系统带来不确定性。例如：如果随机分配给一部电梯的两个请求距离很远，或者很不顺路，就会使系统运行时间更长。

​ 实践检验，使用随机均匀分配任务的算法也能够较好的完成本次作业，但是在时间上和耗电量上会劣于下面这种算法。

影子电梯

​ 所谓影子电梯，是指假设将当前请求分配给电梯 $i$ ，然后假设此后再没有别的请求，模拟六部电梯接下来的运行过程，计算结束的时间，记为 $cost_{i}$ 。当 $i$ 取遍所有当前能工作的电梯时，我们选出 $cost$ 最小的那个，即为最终决策出的接收请求的电梯。可以看出，影子电梯是一种基于贪心的分配算法。

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
int cost = MAXCOST;   // 宏定义的一个大数
int eleId = -1;       // 最终选中的电梯
        for (Elevator elevator : availElevators) {
            // 为当前电梯深克隆一个影子电梯，将当前乘客加入该影子电梯
            final int id = elevator.getId();
            final int curFloor = elevator.getCurFloor();
            final int direction = elevator.getDirection();
            final int curNum = elevator.getCurNum();
            ArrayList<Person> myGuests = new ArrayList<>();
            myGuests.addAll(elevator.getMyGuest());
            myGuests.add(person);
            ArrayList<Person> inElevator = new ArrayList<>();
            inElevator.addAll(elevator.getInElevators());
            
            ShadowElevator shadowElevator =
                new ShadowElevator(id, 6, curNum, curFloor, direction, myGuests, inElevator);
            Thread shathread = new Thread(shadowElevator);
            shathread.start();
            try {
                shathread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            
            int shadowCost = shadowElevator.getCost();
            if (shadowCost < cost) {
                cost = shadowElevator.getCost();
                eleId = id;
            }
        }

​ 其中，影子电梯线程的 run 方法与电梯线程的 run 方法几乎完全相同。区别在于影子电梯只用处理乘客请求而不需考虑临时调度请求（因为正在处理SCHE的电梯不会参与分配，而影子电梯的基本假设是当前请求为最后一条请求，因此此后也不用考虑临时调度）。

第三次作业分析

​ 第三次作业增加了双轿厢电梯，难点在于双轿厢电梯的安全协作：

  • 保证双轿厢电梯不会相撞
  • 保证乘客能乘坐双轿厢电梯正常到达目的地

双轿厢安全

​ 保证电梯不会相撞的办法是每次进入中间层都会判断中间层有无电梯（midFloorIsBusy）。如果有则等待，如果没有则进入，且电梯在中间层执行完任务后无条件离开中间层。同时每个电梯维护一个能去到的最高层和最底层，以保证低层电梯不会去到高层，高层电梯不会去到底层。

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 eleMove(int duration) {
        ...
        // 修改reqForMid
        if (isHighEle == 1 && nextFloor == bottomFloor) {
            reqForMid = true;
        } else if (isHighEle == 0 && nextFloor == topFloor) {
            reqForMid = true;
        } else if (isHighEle == 1 && reqForMid && curFloor == bottomFloor) {
            reqForMid = false;
        } else if (isHighEle == 0 && reqForMid && curFloor == topFloor) {
            reqForMid = false;
        }
        // 如果想要进入中间层，需要请求
        if (reqForMid) {
            while (midFloorIsBusy()) {
                try {
                    sleep(40);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        }
        try {
            sleep(duration);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        curFloor = nextFloor;
        ...
    }

public boolean midFloorIsBusy() {
        // 以下情况不允许进入中间层 需要等待
        if (this.reqForMid && partnerElevator.inMidFloor) { // 中间层有电梯 等待
            return true;
        } else if (this.isHighEle == 0 && this.reqForMid && partnerElevator.reqForMid) { 
            // 上下层电梯同时请求 下层等待
            return true;
        }
        // 允许进入中间层
        this.inMidFloor = true;
        return false;
}

博客作业问题回答

  • 总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系

​ 在本单元作业中，我只采用了同步块（synchronized）这一种保护线程安全的方法，这样一般来说线程安全的逻辑不会太复杂，结构也比较清晰。

​ 锁与同步块中的处理语句关系如下：

​ 我们通常使用 synchronized 关键字来实现锁机制，synchronized 可以修饰方法或者代码块，示例如下：

1
2
3
4
5
6
7
8
9
10
public class LockExample {
    private static final Object lock = new Object();
    public static void main(String[] args) {
        // 使用 synchronized 代码块
        synchronized (lock) {
            // 这里是线程安全的代码区域
            System.out.println("线程获取到锁，进入同步代码块");
        }
    }
}

​ 在上述代码中，当一个线程进入 synchronized 代码块时，它会获取 lock 对象的锁，在执行完代码块中的代码后，会释放该锁。这就保证了同一时刻只会有一个线程在操作和修改 lock 对象的属性。

  • 总结分析三次作业中的调度器设计，并分析调度器如何与程序中的线程进行交互；总结分析三次作业中的调度策略，并分析自己的调度策略是如何适应时间、电量等多个性能指标的。

​ 在我的设计中，调度器的核心是一个静态方法函数

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
// Dispatch.java
public static int alloc(Person person) { 
        int eleId = -1;
        // 先随机选一个不在检修状态的电梯
        ArrayList<Elevator> availElevators = new ArrayList<>();
        for (int i = 1; i <= 6; i++) {
            Elevator elevator = elevators.get(i - 1);  
            if (isAvailable(elevator, person)) {
                eleId = i;
                availElevators.add(elevator);
            }
        }
        // 如果所有电梯都在检修或已经满载，返回异常
        if (eleId == -1) {
            return -1;
        }
        // 选取代价最小的电梯
        int cost = MAXCOST;
        for (Elevator elevator : availElevators) {
            // 通过影子电梯决策出最合适的电梯
            ...
            ShadowElevator shadowElevator =
                new ShadowElevator(id,6, curNum, curFloor, direction, myGuests, inElevator);
            Thread shathread = new Thread(shadowElevator);
            shathread.start();
            ...
        }
        // 分配给代价最小的电梯
        return eleId;
    }

​ 获得person对应的电梯号后，调用requestTable的addPerson方法即可。

1
2
3
4
5
6
// requestTable.java
public synchronized void addPerson(Person person, int ele) {
        // 把person加入ele的电梯的列表
        ele2personMap.get(ele).add(person);
        notifyAll();
}

  • 结合线程协同的架构模式（如流水线架构），分析和总结自己三次作业稳定的内容和易变的内容，并加以分析

    ​ 第一次作业构建起了接受任务——分发任务——执行任务的框架，整个框架在三次作业中是稳定的。第二次作业仅在电梯线程类中新增了一个handleSche方法来处理临时调度请求，第三次作业在电梯线程中新增了handleUpdate方法来处理双轿厢升级请求。同时，第二次作业在分发任务的板块还新增了调度策略方法。（详细代码见上文）

    ​ 总的来说，整个处理的流程是稳定的。二，三次作业都是通过新增方法的形式来实现功能拓展。

BUG分析

​ 在本单元的三次作业中，在与室友合作的测评机的帮助下，我侥幸仅在互测中出现了一处Bug，具体分析如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Elevator
@Override public void run() {
        // 先处理请求表，如果请求表中没有该电梯的任务，则该线程wait
        while (true) {
            reNewMySche();     // 更新sche列表
            reNewMyUpdate();   // 更新update列表
            reNewMyGuests();   // 更新乘客列表
            if (isEnd) {
                break;
            } else {
                if (!myUpdate.isEmpty()) {
                    handleUpdate(myUpdate.get(0));
                    myUpdate.remove(0);
                } else if (!mySche.isEmpty()) {
                    handleSche(mySche.get(0));
                    mySche.remove(0);
                } else {
                    Advice advice = strategy.getAdvice(this, requestTable);
                    ansAdvice(advice);
                }
            }
        }
    }

​ 在我的设想中，电梯线程每次在最开始更新自己的Sche列表，Update列表和Guest列表。然后根据当前三个列表状态进行处理。

​ 事实上可能存在这样的情况，最后一条乘客请求恰好出现于reNewMyGuest与getAdvice之间，导致在寻求建议（get Advice）时，电梯由于myGuest里没有该乘客，于是进入WAIT状态。但由于所有请求没有完成，因此线程不会结束，而是进入无限的等待。

​ 解决方法是在将getAdvice和reNewMyGuest用同步块包裹成一个原子操作，即：

1
2
3
4
synchronized (myGuests) {
    reNewMyGuests();
    Advice advice = strategy.getAdvice(this, requestTable);
}

​ 多线程的 debug 是痛苦且漫长的，我采用的方法主要是通过print的方法检查线程是因为不满足哪条终止条件而没有结束，再进一步地检查为什么不满足该终止条件。这样做可能效率比较低，但最终还是能解决问题。

心得体会

本单元学习给我的启示如下：

  • 高内聚低耦合：通过分离方法的形式降低单个方法或者代码块的复杂度，使得每个方法的内部逻辑尽量简单，接口清晰。这样会增加代码的可读性，同时也不容易出错。
  • 写测评机：本单元的三次作业均写了测评机，在本地经过了充分的测试，因而得以顺利通过三次强测（对比上个单元没写测评机强测爆了两次…）。
  • 层次化设计：在第一次作业的时候设计一个清晰的框架。每个层次只完成一步简单的处理，然后通过清晰的接口传递信息到下一层次。后两次作业仅通过增加类或方法实现功能拓展。
  • 线程安全：在多线程的设计中，处理临界资源时要格外慎重，每次访问或者修改临界资源都要考虑会不会出现线程安全问题。同时还要考虑数据是否存在时间差。