第五次作业

本次作业由两个大的任务组成：

  • 电梯运行策略
  • 多线程设计

电梯运行策略

想必大家在等电梯的时候，都会疑惑电梯是怎么调度的，甚至想「这方案太（）了，假如（），肯定效率更高」

原本想实现一个最优方案，在尝试查找电梯调度方面的论文后，
却发现不同的策略在不同的情况下有不同的优势，很难说有一种最优的方案。

仔细想想也确实如此。电梯是一个实时响应的系统，它不能预测未来，故只能选择当前条件下的最优结果，也就是「局部最优」。而事实上我们想要的是总时间和耗电量尽可能小的「全局最优」。

可悲的人类在时间线上永恒地单向蠕动着，我们的短视导致两个「最优」间产生了冲突，这是无法调和的矛盾。那么，我们能做的，就是祈祷我们的方案尽可能逼近「全局最优」，「局部最优」则降格为逼近「全局最优」的一种方案

阅读往年博客，可以发现电梯运行策略分为两大板块：

  • 请求分配策略：将用户请求分配给具有竞争关系的电梯的策略
    • 调度器
    • 自由竞争
    • …
  • 电梯处理请求策略：电梯处理自身请求的策略
    • look
    • als
    • …

请求分配策略

为了方便，我们定义以下符号：

  • $e$：某个电梯
  • $r$：某个请求
  • $E$：电梯集合
  • $R$：请求集合
  • $S$：电梯状态（楼层，开关门状态，…）

请求分配策略：$f(S,R)={(e_1, R_1),(e_2, R_2),\cdots,(e_n, R_n)},\bigcup_{i}R_i=R$

调度器： $f(S,R)={(e_1, R_1),(e_2, R_2),\cdots,(e_n, R_n)},R_i\cap R_j=\emptyset,\bigcup_{i}R_i=R$

自由竞争：$f(S,R)={(e_1, R),(e_2, R),\cdots,(e_n, R)}$

写得好的调度器是能够达到局部最优的，比如说 影子电梯，即在调度器内维护电梯的 数字孪生，进行不同的尝试并选择 代价最小 的方案

但事实上由于全局最优的不可达性，写个简单的自由竞争就可以摆了

电梯处理请求策略

look：电梯向某个方向走，遇到同方向的请求就捎带上，直到电梯内部无请求且当前方向没有能捎带的请求，转向，如此循环

大家基本上都实现的这个就没啥讲的

一些优化

由于自由竞争的效率很高，以至于后面大家基本全写自由竞争了。
课程组为了卡掉自由竞争（至少让调度器有出场的机会）加入了耗电量的指标。

由于自由竞争在遇到较少的请求的时候也会一起动，
所以原版的自由竞争在耗电量上的表现很差。

引入标记的概念：每个请求有标记和未标记两种状态。
新请求插入时为未标记状态，
当它被某个电梯作为 target request 后转变为标记状态，
不可被其他电梯作为 target request。

当内部没有乘客时，电梯被 target request 驱动运动。
直到接到第一个乘客（可能是 target，可能是捎带），行为和 look 一致。

在这样的设计下，较少的请求将最多触发等量的电梯，从而减少耗电。同时由于请求较少，在层数不多的情况下性能损失不明显。而在请求较多时，该方案退化为自由竞争，从而保证效率

多线程设计

多线程中对于共享资源的访问是一个坑点。
首先不能让存/取数据的进程为了同一个数据打架（线程安全），所以需要引入 同步（synchronization）
其次不能让等不到想要资源的进程一直请求（线程协作），所以需要引入 wait-notify 等机制

以 RequestQueue 中对于共享资源 notFlaggedRequests 的操作为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public synchronized PersonRequest getTargetRequest(int floor, boolean isMoveUp) {
    while (notFlaggedRequests.isEmpty()) {
        if (isEnd) {
            return null;
        }
        try {
            wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    PersonRequest request = null;
    requset = a request in notFlaggedRequests;
    return request;
}

首先使用 synchronized 块（异步转同步）保护 getTargetRequest 不被其他写操作影响，其次在 while 块中尝试获取资源，若获取不到，则进入 wait 状态，释放锁和系统资源，直到某个向 notFlaggedRequests 写入的操作使用 notify 重新唤醒 wait 的 getTargetRequest 方法

在设计的过程中，需要注意 wait 的进程在什么情况下需要被唤醒

整体架构

整体架构
整体架构

InputThread

输入线程，从官方提供的数据接口获取数据

OutputThread

输出线程，包装官方输出接口以保证线程安全

RequestQueue

请求队列池

Elevator

电梯实体进程，负责上下移动，接送乘客

DicisionMaker

电梯控制器接口，用于控制电梯

LookDecisionMaker

电梯控制器具体实现，基于 LOOK + 有标记的自由竞争策略

第六次作业

新增需求

电梯扩建 & 电梯维护

自由竞争下完成电梯扩建和电梯维护较为简单，需要新增一些数据通路

注意维护时请求（真实请求和 target request）的释放与重入

整体架构

整体架构
整体架构

ElevatorController

使用单一策略，替代原先的 DecisionMaker 接口

仍然基于 look + 有标记的自由竞争策略

MainController

对于不同类型的 Request 进行分发，记录全局电梯信息以便进行 Maintain

后日谈

时间管理？

Fuck myself

第七次作业

迭代

  • 每层服务中电梯数量限制
  • 电梯可达性限制

每层服务中电梯数量限制

在某一时刻 $t$，某一楼层 $X$，对电梯行为给出如下定义

  1. 未服务：电梯不处于 $X$ 层，或者电梯处于 $X$ 层但未开门
  2. 服务中：电梯处于 $X$ 层且电梯处于开门状态。

每一次开关门会对应着一次电梯内外乘客的交换，针对某部电梯一次开关门时间窗口内的乘客交换，对该电梯的行为给出如下定义。

  1. 只接人：设该电梯开门前电梯内乘客集合为 $before$，关门后电梯内乘客集合为 $after$，则二者满足以下子集关系：$before\subseteq after$。

则一个程序被认为是电梯调度逻辑合理的，当且仅当

  1. 在任意时刻，任意楼层 $X$，处于服务中的电梯数量小于等于 $M_X$ 部
  2. 在任意时刻，任意楼层 $X$，处于服务中的只接人电梯数量小于等于 $N_X$ 部

为了完成以上限制，我们在每层楼引入两个信号量，分别对应服务中的电梯数量限制和服务中的只接人电梯数量限制

显然，如果需要等待资源的释放，可以引入新的策略，比如说直接路过原本需要停留的楼层。
但是为了策略的简洁性和有效性，可以认为信号量的限制 不影响电梯的运行策略，只是增加等待资源的释放的过程

为了完成资源的申请和释放，电梯到达楼层后，先按照当前的电梯内外的请求（包括 maintain）判断这次请求资源是只接人（$N_X,M_X$）还是存在下电梯的乘客（$M_X$），申请到对应的资源后进行开门。并在关门后释放资源

电梯可达性限制

本次作业需要支持电梯的可达性，即一部电梯不一定能在所有楼层停靠（但显然可以经过所有楼层）。可达性将以掩码形式给出

可达性限制的提出是本次作业的主要难点。引入可达性后，电梯载人时需要考虑可达性，而不能直接上客。同时乘客还需要考虑换乘的问题（不能直接到达）

对于任何一个 FROM A TO B 的请求，我们都可以将其拆分为 $k$ 段，
每一段均在 同一部电梯 的 同一个方向上。
每个请求暴露给电梯的只是当前所在的段

拆分方案很多，那如何确定最优的方案？

  1. 经历楼层最少
  2. 换乘次数最少
  3. …

标程在规划时会选择乘坐电梯数最少的方案。

由于不同策略的最终效果几乎是不可对比的，
本次设计采取较为稳妥的 换乘次数最少 方案

卡人方式：一部全能电梯 + 残疾电梯
增加换乘次数次少方案？

设计细节

注意到电梯不断在加入和维护的，我们也需要动态维护换乘方案

对于在电梯外的请求，每次新增电梯和删除电梯，动态维护当前最佳路径

对于在电梯内的请求，等到电梯到达某一楼层后，再更新当前最佳路径。
更新最佳路径时，优先选择 不下车 的路径

整体架构

整体架构
整体架构

Building

控制每个每个楼层的资源（锁）

DistanceCalculator

楼层距离计算与路径拆分

后日谈

开始怀疑自己的脑子是不是有问题：

  1. 信号量资源看错
  2. 忘记 新增电梯和删除电梯，动态维护当前最佳路径

不过电梯终于是结束了

Fuck the world

架构模式

Unit2 的架构较为固定，最终数据流动图如下

数据流动
数据流动
  • 稳定的内容：基础架构几乎不变，在迭代的过程中会加入一些辅助类，比如 DistanceCalculator 等
  • 不稳定的内容：根据不同的要求可能产生新的数据通路，此时需要新建不同类间存取数据的方法

bug 分析和 debug 方法

本单元中出现的问题有：

  • notify 没到位导致死锁
  • 有限制的资源理解错误
  • 没有实时 update 最短路状态

可以看到都是一些非常傻缺的问题，没有静下心来思考

应用的 debug 方法主要是最小化出错样例后疯狂的 print。
在每一个状态改变后都申请全局管控的 MainController 输出所有信息。
虽然繁杂，但是很容易精准定位出现的错误

心得体会

线程安全

本次作业的线程安全做得不错，
在共享对象的读写方法中加入了 Synchronized 进行保护。
还有一种思路是建立尽可能小的 Synchronized 保护块，
可能会产生安全问题（没考虑到），但是也有可能有更高的性能（减少冲突）。

线程协作

本次作业的线程协作出现了问题，
没有仔细考虑 wait-notify 的顺序，导致 wait 的线程无法唤醒

需要将会影响共享资源的所有信号都放到共享资源所在类中，
并及时 notify，这样才能保证状态改变能成功唤醒 wait 的线程

层次化设计

本次作业的层次化设计比较简单。
并没有很明显的层次化结构，于是笔者按照功能简要的进行了层次化设计，
主要的思路是将复杂结构解耦，防止出现超大的复杂类，难以进行迭代。

比如说电梯的运行类 Elevator 和电梯的策略类 ElevatorController。
借用强生老师的一句话：

有一个很好的比喻，就是把电梯从一个正常人的结构变成一个“瞎子背瘸子”的结构。瞎子一般对应残缺功能的电梯，它负责改变自身状态和输出信息。瘸子对应策略类，负责收集获取外界信息，结合电梯的自身状态信息，做出决策，将这些信息提供给电梯。

后日谈

你赢赢赢，最后却是输光光

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。