「面向对象」Unit-2

第五次作业

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

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

电梯运行策略

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

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

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

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

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

• 请求分配策略：将用户请求分配给具有竞争关系的电梯的策略
  • 调度器
  • 自由竞争
  • ...
• 电梯处理请求策略：电梯处理自身请求的策略
  • 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。 借用强生老师的一句话：

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

后日谈

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