完全影子电梯

发表于 分类于 阅读次数：

完全影子电梯：影子电梯，但是只有影子，没有电梯

电梯还是电梯线程？我都不要。

摘要

影子电梯是一种电梯分配策略，通过模拟电梯运行的过程实现对每个请求的局部最优分配，具有原理简单、目标清晰的特点。在目前的实践中，多是以电梯运行的结束时间作为衡量标准进行分配，将乘客的请求传递给电梯，然后电梯结合朴素 LOOK 运行策略或者量子电梯运行策略模拟现实电梯的运行过程并输出。这种做法已经被证明是一种可靠、高效的电梯分配策略，同时对不同的衡量标准具有良好的可拓展性，可以被运用于我们的代码中。

本文基于影子电梯提出了一种电梯调度 - 运行架构，即完全影子电梯。其在影子电梯的实现基础上，通过存储电梯每步状态改变的时间戳和对应的输出信息，在模拟结束后将计算出的信息交给输出线程进行输出来完成任务。这种做法在完成任务需求的基础上，实现了多线程运行结构的简化与代码的高效利用，极大程度的减少了线程安全问题的发生可能，同时在应对多轿厢问题时具有比较好的效率和可靠性。

基本思想

在阅读以下内容之前，请先对影子电梯和量子电梯有一些基础的了解。

完全影子电梯说是脱胎于影子电梯，其实更像是结合了量子电梯思想的影子电梯。

同学们在实现量子电梯的时候是否有思考过：量子电梯的原理是什么？为什么我们的电梯可以“既在这一层又在下一层”？

事实上，这一方法的根本在于 我们不关心电梯的真实状态，我们只关心你的输出 。但是我们的输出并不是和电梯的状态一一对应的，在我们的设计里，电梯状态是离散的而非现实世界一样连续的。我们自由发（魔）挥（改）的空间也就由此而来。

也就是说，如果上次输出是 ARRIVE-2，只要下次输出是 ARRIVE-3 就行了，哪怕电梯内存储的所在位置在 10 楼；同样，我们输出 ARRIVE 前等待 400ms 不是因为我们的电梯要运行 400ms，而是因为我们输出的间隙是 400ms。我们的目的不是让电梯运行，而是让评测机觉得它在运行。

这种做法有用吗？下面是某人的发言：

名字十分高端，学习起来十分锻炼思维，在日后的实际应用中不能说是至关重要，但至少也是毫无作用。

诚然，量子电梯也好，影子电梯也罢，将它们运用于现实的电梯运行控制是一件完全不可能的事情，但是这些做法实际上体现的是我们对于电梯问题的理解： 无论如何，我们都只是在输出一个运行在电脑里的虚拟电梯的状态，课程组的任务需求也只是让我们输出一个合法的状态转移队列。 现实意义？差不多得了，还不如去二次元里寻找真实感。

现在，抛开那些现实里电梯运行的常识。我们的问题是：如何计算这样的一个状态转移队列并将其合法地输出？

如果你没看懂上面的内容，那就别看了。问题不大。

工作流程

工作流程图如下

电梯工作流程

思考影子电梯的实现过程，我们不难发现，在我们模拟电梯运行的过程中就已经得到了电梯在某个时间应该输出什么信息，只是我们没有试图去利用这一点罢了。

现在，我们把这些信息利用起来。在每一个时间改变的地方（也就是电梯状态改变时），增加具体状态改变时应该输出的信息。也就是说，对于下面这段原始的影子电梯的代码：

1
2
3
4
5
6
7
8
9
private void execRun() {
    doorStat = leave(doorStat);
    doorStat = enter(doorStat);
    if (doorStat) {
        doorStat = false;
    } if (allClear()) { return; }
    atFloor += this.direction;
    time += speed;
}

在存储状态转移信息后：

1
2
3
4
5
6
7
8
9
10
11
private void execRun() {
    doorStat = leave(doorStat);
    doorStat = enter(doorStat);
    if (doorStat) {
+       infos.add(new PrintInfo.CloseInfo(time, atFloor, id, type));
        doorStat = false;
    } if (allClear()) { return; }
    atFloor += this.direction;
    time += speed;
+   infos.add(new PrintInfo.ArriveInfo(time, atFloor, id, type));
}

其中 infos 是一个 ArrayList，按顺序存储从模拟开始到结束的所有模拟得到的输出信息和他们的时间戳。由于模拟是按照时间顺序进行的，因此后生成的输出信息的时间戳一定在前面的输出信息之后，其对应的电梯状态也一定在前面的输出信息对应的状态之后。

在得到电梯的输出之后，将这些输出传递给输出线程，输出线程根据每个输出的时间戳计算每条输出之间的间隔并 wait(<gapTime>) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Override
public synchronized void run() {
    while (true) {
        while (!printInfo.isEmpty()) {
            PrintInfo info = printInfo.remove(0);
            info.print();
            long waitTime = waitTime(info);
            elevator.exec(info);
            if (waitTime != 0) {
                try { wait(waitTime); }
                catch (InterruptedException e) { e.printStackTrace(); }
            }
        }
        if (exit) { break; }
        try { wait(); }
        catch (InterruptedException e) { e.printStackTrace(); }
    }
}

其中要注意同步电梯的实际状态。也就是说，由于请求不一定是在输出结束后到来的，而新的请求需要重新模拟一次以得到对应的输出。在电梯模拟结束之后的状态和下一次模拟开始的状态是有可能不一样的，因此要在输出的过程中通过 twinElevator.exec(info) 的方式使电梯下次收到请求、模拟开始的状态和最后一次输出的状态一致。

考虑多线程交互的问题：哪些信息被共享？

你可能会说共享的信息很多，比如包含所有输出的 infos、包含电梯状态的 elevator 对象，但实际上我们注意到，在电梯模拟（更新输出信息）的时候输出进程是不能输出的、在输出进程输出的时候电梯是不能模拟的，因此我们只要锁住输出进程对应的对象（printer）即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
---------- Printer ----------
@Override
public synchronized void run() {
    while (true) {
        while (!printInfo.isEmpty()) {
            // ...
            wait(time);
            // ...
        }
        if (exit) { break; }
        try { wait(); }
        catch (InterruptedException e) { e.printStackTrace(); }
    }
}
---------- Elevator ----------
public void addPassanger(Passenger passenger) {
    synchronized (printer) {
        // update printInfos
    }
}

调度器工作流程

在收到请求后将请求分配给所有电梯的 simulate() 方法，比对返回值选取最优解。其中 simulte() 方法功能与 addPassanger() 方法大致相同，只是不要把输出真的传给输出线程。这只是模拟，可不要动了真感情哦~

RECEIVE 问题

对于 RESET 期间不能 RECEIVE，我实现了三个队列：toReceive、inQueue 和 inElevator，分别代表已分配的乘客、已经在等待列表里的乘客和在电梯里的乘客。

在 RESET 期间，只需要控制电梯无法从 toReceive 里获取即可；换乘时，只需要把 A（B）电梯的乘客加入 B（A）电梯的 toReceive 列表里即可。

事实上，在这种完全影子电梯模式下，只需要以下代码即可保证不可能产生 RESET 期间输出内容的问题：

1
2
3
4
5
6
info.print();
long waitTime = waitTime(info);
wait(waitTime);
if (info instanceof PrintInfo.ResetInfo) {
    ((PrintInfo.ResetInfo)info).printEnd();
}

也就是说，输出线程保证在输出 RESET_BEGIN 后的下一条一定是 RESER_END。这是因为我们的输出把握在我们自己手上，而不是电梯或者电梯线程手上。

线程共享与冲突

线程安全？不存在的。多线程问题已经退化为了单线程模拟问题。你只需要保证输出时不模拟、模拟时不输出，锁住 Printer 即可。输出进程锁的转换当且仅当输出列表为空或者处于上一条输出的 TIMED_WAITING 状态。

输出线程不会询问列表是否为空。线程控制模式是线性的，即 main 收到请求 - 分配电梯 - 电梯收到请求 - 执行（模拟）请求 - 更新输出列表 - 通知输出线程（释放输出线程锁），避免了轮询、死锁的可能。

同时，这种实现天然具有量子电梯的特性，这是因为我们的输出和电梯的状态弱绑定。假设我们的设计中在 ARRIVE 前要等待 400ms，只要没有输出 ARRIVE，我们的电梯就随时有可能再次开门接收乘客。这也回应了上文的内容：

完全影子电梯说是脱胎于影子电梯，其实更像是结合了量子电梯思想的影子电梯。

迭代需求的处理

对于双轿厢电梯，我的处理是所有的电梯初始都是双轿厢电梯，只不过有一个电梯（比如 B 电梯）初始时位于一个不存在的楼层，另一个电梯的工作范围为全楼层。这两个电梯都被掩盖在一个双子电梯内部，请求会由这个双子电梯分流给 A、B 两个电梯。从外部看来，就只有一个双子电梯。而 DoubleCarResetRequest 的功能也只是普通重置功能 + 设定两个轿厢的工作楼层。

在程序工作的过程中，main 方法从标准输入读入请求，然后调用调度器的 addRequest(Request request) 方法。在这里，请求被分流为乘客请求、普通重置请求和双轿厢重置请求。乘客请求将会调用每个双子电梯调度模拟器获取结束时间，并将请求分配给结束时间最早的一个双子电梯。重置请求将会越过调度器直接执行。（这里吐槽一句课程组的 ResetRequest 类底下啥方法也没有）

双子电梯得到请求后，对于乘客的请求则根据出发楼层和方向选择 A、B 电梯中的一个分配；对于重置请求则将请求同时传递给两个电梯。然后对于任意一种请求，都需要更新传递给输出线程的输出信息。在这个过程中，双子电梯将会在把请求传递给两台电梯之后，分别运行两个电梯的模拟方法，得到两个电梯的输出信息。在这个过程中，两个电梯都是孤立的，不知道另外一个电梯的状态，因此可能发生电梯冲突的情况，需要将两个电梯的输出信息合并使最后输出在控制台的信息合法。

如何合并输出？

这是完全影子电梯最为与众不同的一点。我们不通过电梯本身完成碰撞的避免，而是通过对输出内容进行检查来完成这个工作，相当于代码里有个评测机。

当我们检测到输出冲突的时候，冲突一定发生在换乘楼层。我们假设换乘楼层是 5 楼，A 先到达，B 后到达，此时检测到输出冲突：

  • 假如 A 后续会移动到 4 层，将 B 移动到 5 楼的行为（和后续 B 的所有行为）推迟到 A 移动到 4 层之后，这可以通过调整 B 输出信息的时间戳做到
  • 假如 A 后续没有移动的计划，则在 A 最后一次关门之后添加移动到 4 层的行为（即加入这样的一条输出），将 B 移动到 5 楼的行为（和后续 B 的所有行为）推迟到 A 移动到 4 层之后
  • 如果没有冲突，就将两者的输出按照时间戳的先后顺序合并

最后，把合并好的输出交给输出线程并释放锁，输出线程会根据时间戳自动计算出输出后需要等待的时间。

实现细节

完全影子电梯的实现细节很多，这里列举几个重要的。这些细节因人而异，在这里写的内容仅供参考，而且不会说的很清楚，只有读者遇到了相应的问题才会理解这些内容。同时，重复一遍上文的内容：

因此要在输出的过程中通过 elevator.exec(info) 的方式使电梯下次收到请求、模拟开始的状态和最后一次输出的状态一致。

具体来说，我们要记录当前电梯的实际状态来为下次模拟提供初始化的信息，但这又不能存储在单个电梯里（会随着模拟的过程丢失信息），因此一个绝佳的场所是掩盖了两个单电梯的双子电梯类里。每次模拟时，只需要把双子电梯存储的电梯实际状态作为参数传入单电梯即可。换句话说，单电梯只是模拟，双子电梯才是现实。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void exec(PrintInfo info) {
    if (info instanceof PrintInfo.CloseInfo) {
        // set door state
    } else if (info instanceof PrintInfo.OpenInfo) {
       // set door state
    } else if (info instanceof PrintInfo.InInfo) {
        // update inQueue & inElevator
    } else if (info instanceof PrintInfo.OutInfo) {
        // update inElevator & check is arrival or transfer
    } else if (info instanceof PrintInfo.ArriveInfo) {
        // update atfloor
    } else if (info instanceof PrintInfo.ResetInfo) {
        // excute reset action
    } else if (info instanceof PrintInfo.ReceiveInfo) {
       // update toReceive & inQueue
    }
}

RESET 的实现

RESET 不是在模拟到 RESET 的时候执行的，事实上，模拟到 RESET 请求之后不可能再有后续了（因为队列被清空了）。

RESET 生效应该是输出线程输出 RESET 后。

RECEIVE 之后 ARRIVE 可节约的等待时间

可以保留上一次 ARRIVE/CLOSE 的时间戳，在计算 ARRIVE 时间的时候计算差值即可。

OPEN 之后 CLOSE 太快

同上，保留上一次 OPEN 的时间戳即可。

其他

遇事不决，System.currentTimeMillis() 保留时间戳。

后记

这个想法应该是原创吧，反正我问了专精阅读博客的 wxm & zyt 都说没见过。也有可能写这种做法的人都很菜

这个做法看起来简单，实际上如果没有双轿厢那也确实简单。可恶的双轿厢。 不过如果没有双轿厢的需求我也不会有这种疯狂的想法并把它付诸实现的动力。

第二单元也结束了，希望以后还有人愿意尝试一下这种做法。

感谢陪伴在我身边的朋友们。感谢 @未新 审稿，提供了很多意见。

最后感谢 OS 课程组提供的服务器

最新消息：强测没挂，大家可以用！

知りたくなかった、失うのなら