Java模拟电梯系统，可接收用户请求、动态调度，接受临时调度和双轿厢改造请求并及时响应
第一次作业
1. 迭代思路
- 整体架构：输入线程接收输入，存入RequestQueue中，RequestQueue用TreeSet实现，由于TreeSet本身并不保证线程安全，需要在该类的所有方法中都加入同步关键字，调度线程将队列中的请求逐个分配到对应的电梯中，电梯接收到请求后开始服务。
-
停止方法：输入线程结束告知调度线程，此后不会有输出；调度线程检测到RequestQueue中没有请求，且输入线程结束后结束，并告知所有电梯线程；电梯线程在内部没有未完成的请求，且调度线程结束后结束，程序运行结束。
- 运行策略：考虑到优先级问题，我使用了ALS算法，确定一个主请求后，允许同向移动的乘客进入电梯。主请求满足后，检查该方向上是否还有请求，如果还有请求，将请求处理完毕，然后接收下一个主请求，否则直接接收下一个请求。
2. 评测思路
- 对于数据生成，只需要随机生成时间戳、用户编号、优先级、起始楼层、终点楼层、指定电梯，即可生成大量随机数据。
- 较为密集的数据能够测试电梯系统的抗压能力，可以通过缩小时间戳的范围，缩小指定电梯的集合等方法实现对系统的压力测试。
- 较为稀疏的数据能够检测在没有请求到达的时候，代码是否出现轮询，可以通过将起始时间戳后调的方式，测试无请求时系统的CPU占用情况。
- 对于正确性判定，本次作业相对简单，我并没有模拟电梯的运行，仅仅通过字符串查找的方式就能完成正确性的判断。
- 第一，检查每部电梯开门和关门的时间间隔、相邻楼层间移动的时间是否合法，第二，由于电梯已经给定，每个乘客从起始楼层到目标楼层经过的所有操作一定是确定的，只需要根据输入，在输出中逐条进行字符串匹配即可。
3. bug分析
- 本次作业强测和互测均未出现bug，强测92.7分，ALS算法导致性能分偏低，意料之中。
第二次作业
1. 迭代思路
- 调度算法：当接收到一个新请求，假设该乘客送入某电梯进行模拟，计算该乘客从发出请求到抵达目标楼层总共需要的时间。这种方法只片面考虑了时间，而没有考虑耗电量和优先级等其他与性能分有关的参数，并不是全局的最优解，而且对CPU的计算开销较大，在极端情况下可能导致CTLE。
- 临时调度：在接受到临时调度的请求时，调度器强制停止当前用户请求的等待，将请求放回队列，并将临时调度请求传递给对应的电梯；电梯线程接收到请求后，关门前往目标楼层，中途禁止所有开关门行为，到达后将所有人赶出电梯，等待一秒，没有到达最终楼层的乘客请求重新送入RequestQueue中。
- 停止方法：输入线程结束告知调度线程，此后不会有输出；调度线程检测到RequestQueue中没有请求，且所有电梯都不处于临时调度状态，且输入线程结束后结束，并告知所有电梯线程；电梯线程在内部没有未完成的请求，且调度线程结束后结束，程序运行结束。
2. 评测思路
- 数据生成
- 用户请求：随机生成时间戳、用户编号、优先级、起始楼层、终点楼层，即可生成大量随机数据。
- 临时调度：在输入中，满足一定时间间隔的情况下，随机插入一些随机调度指令。
- 评测思路
- 输出正确性：由于本次作业并没有指定电梯，需要我们自己进行调度，之前的字符串替换方式行不通，所以对于输出的正确性，我通过模拟6部电梯的行为来实现，将输出的行为施加于各个电梯，检查在当前状态下，该输出的行为是否合法。
- 输入满足：对于每一条输入请求，都要检测该请求是否得到及时的满足，对于用户请求，通过模拟用户来实现，检测每个用户的乘梯行为是否合法，以及最终是否到达目的地；对于临时调度请求，需要根据指导书中复杂的临时调度约束，判断临时调度是否成功且合法的执行。
3. bug分析
-
中测最后一个数据点一直无法通过，其根本原因在于，当6部电梯中的5部电梯处于临时调度状态时，如果收到大量的用户请求，会导致所有的请求都被堆积到剩下的一部电梯中，进而导致超时，为了解决这个问题，我规定只有4部电梯处于空闲状态时，才能开始请求的调度，否则进行等待，减少某个电梯负载过高的情况出现的可能性。
- 本周强测出现一个bug，得分91.3分，互测也出现一个bug，两个错误是同质的。
- 这个错误出现的原因在于：上面规定只有4部电梯处于空闲状态时，才能开始请求的调度，否则进行等待，但如果在等待过程中接收到临时调度请求，那么这个临时调度请求显然就不能及时得到满足，为了解决这个问题，接收到的临时调度请求应该唤醒正在等待的用户请求，并将用户请求放回队列，优先处理临时调度请求。
private boolean urgent = false;
private Elevator choice(PersonRequest request) {
ArrayList<Elevator> free = getFree(); // 获取空闲电梯列表
while (free.size() < 3) {
if (urgent) {
return null;
}
try {
synchronized (this) {
wait();
}
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
if (urgent) {
return null; // 如果有更紧急的临时调度请求，停止当前等待
}
free = getFree();
}
int min = Integer.MAX_VALUE;
Elevator res = null;
for (Elevator elevator : free) {
int pre = elevator.size(request);
if (pre < min) {
min = pre;
res = elevator;
}
}
return res;
}
第三次作业
1. 迭代思路
- 停止方法：输入线程结束告知调度线程，此后不会有输出；调度线程检测到RequestQueue中没有请求，且所有需求都被满足，且输入线程结束后结束，并告知所有电梯线程；电梯线程在内部没有未完成的请求，且调度线程结束后结束，程序运行结束。
-
双轿厢改造：在接受到双轿厢改造的请求时，调度器强制停止当前用户请求的等待，将请求放回队列，并将改造请求传递给对应的两部电梯，同时给两部电梯传入共享锁用于同步互斥管理；电梯线程接收到请求后，停止当前所有的服务，就近停靠，将所有人赶出电梯，没有到达最终楼层的乘客请求重新送入RequestQueue中。
- 双轿厢管理
- 对于双轿厢电梯，有的同学可能新创建了一个类，用于专门管理双轿厢电梯，但我认为没有这个必要，可以完全把双轿厢电梯看作一个限制最低楼层和最高楼层的电梯，这样做可以使代码的复用型更强一些，减少迭代的代码量。
- 增加了双轿厢电梯后，对应的调度策略也需要考虑更多的因素，一方面，双轿厢电梯的移动速度更快，能让用户更快到达，另一方面，双轿厢电梯又增加了换乘和开关门的次数，这会降低用户到达的速度，而且也会增大耗电量。
- 基于以上两点考虑的平衡，我的调度策略与第二次作业完全一致，采用影子电梯，没有做任何的更改。
- 防撞策略
- 我采用了一种回避相撞的策略，在上下两部电梯中，只允许其中一部电梯进入换乘楼层。
- 但无脑这样做是有问题的，对于6部电梯全部在同一楼层被改造的情况，有可能出现用户需求永远得不到满足的情况，我们需要动态的选择双轿厢电梯中哪一部电梯能够到达换乘楼层。
- 根本原因在于，全部双轿厢改造导致在换乘楼层的人只能单向移动，为解决这一问题，我通过设计单例模式，定义一个列表，存储每个楼层能向上移动和能向下移动的电梯数，通过这个数量来进行动态选择。
public static final ArrayList<HashMap<State, Integer>> upDown = new ArrayList<>();
public void init() {
for (int i = 0; i < 11; i++) {
HashMap<State, Integer> temp = new HashMap<>();
if (i == 0) temp.put(State.UP, 6); temp.put(State.DOWN, 0);
else if (i == 10) temp.put(State.UP, 0); temp.put(State.DOWN, 6);
else temp.put(State.UP, 6); temp.put(State.DOWN, 6);
upDown.add(temp);
}
}
public ArrayList<Integer> getLimit(UpdateRequest ur) {
ArrayList<Integer> result = new ArrayList<>();
int floor = getFloorIndex(ur.getTransferFloor());
if (upDown.get(floor).get(State.UP) < upDown.get(floor).get(State.DOWN)) {
result.add(0); result.add(floor - 1);
result.add(floor); result.add(10);
upDown.get(floor - 1).compute(State.UP, (k, v) -> v - 1);
upDown.get(floor) .compute(State.DOWN, (k, v) -> v - 1);
return result;
}
result.add(0); result.add(floor);
result.add(floor + 1); result.add(10);
upDown.get(floor) .compute(State.UP, (k, v) -> v - 1);
upDown.get(floor + 1).compute(State.DOWN, (k, v) -> v - 1);
return result;
}
- 输出策略
- 同步关系：两部电梯都停下，并且所有人离开后，两部电梯分别输出开始改造的信息。
- 实现方法：上下两部电梯共享一个锁变量groupLock，先达到改造条件的电梯等待另一个电梯达到条件，而后分别输出。
- 互斥关系：两部电梯都改造完成之后，只输出一次改造完成的信息。
- 实现方法：上下两部电梯共享一个锁变量printLock，强制只有上面的电梯才能输出改造完成的信号，下面的电梯需要等待上面的电梯输出完成信号，才能退出等待，两者共同接收新的用户请求。
public static final HashMap<Elevator, Boolean> groupFinished = new HashMap<>();
public static final HashMap<Elevator, Boolean> printFinished = new HashMap<>();
private Object groupLock;
private Object printLock;
public void update(UpdateRequest ur) {
Elevator partner = getPartner(ur); // 获取与这个电梯在同一个轿厢的电梯
State pos = getPosition(ur); // 判断这个电梯是在上方的还是下方的
try {
synchronized (groupLock) {
groupFinished.put(this, true);
while (!groupFinished.get(partner)) {
groupLock.wait();
}
groupLock.notifyAll();
}
synchronized (printLock) {
if (pos == State.UP) {
print(ur);
printFinished.put(this, true);
printLock.notifyAll();
} else {
while (!printFinished.get(partner)) {
printLock.wait();
}
}
}
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
2. 评测思路
- 本周周末在外比赛，过于忙碌，无暇继续迭代之前的评测机，为之后出现bug埋下了伏笔。
3. bug分析
- 本次作业中，我的中测有两个测试点总是不通过，通过与一名出现过同样bug的同学交流，我发现错误的原因在于：在update begin之前把receive取消，被其他电梯提前receive。这更加提醒我仔细阅读指导书的重要性。
- 在强测中，我有两个测试点出现错误，获得86.7分，互测中被hack四次，这6个错误是同质的。
- 错误的原因在于：关闭调度器的条件是所有输入的需求全部被满足，但我在统计完成的请求数时，没有对自增运算上锁，导致两次自增运算并发执行时，有可能出现不同的结果，只需对自增运算上锁即可解决该bug。
private final Object lock = new Object();
public void satisfy() {
synchronized (lock) {
satisfy++;
}
}
整体复盘
1. 架构分析
第一次作业类图
第二次作业类图
第三次作业类图
2. 复杂度分析
方法复杂度
类复杂度
3. 稳定和易变
-
稳定内容
- 生产者 - 消费者模式：三次作业都采用了生产者 - 消费者模式，这种模式是整个系统的核心架构，保证了系统的稳定性和可扩展性。
- 请求队列：请求队列作为生产者和消费者之间的缓冲层，是系统的重要组成部分。无论调度策略和电梯类型如何变化，请求队列的基本功能都不会改变。
-
易变内容
- 运行和调度策略：随着作业的迭代，调度策略可以发生变化。运行策略从简单的 ALS 可以改进为Look，调度策略从均匀分配，再到影子电梯，运行和调度策略的变化反映了对性能要求的提高。
- 电梯类型：从单部电梯到双轿厢电梯，电梯类型的变化导致了架构的调整和代码的修改。未来可能还会增加更多类型的电梯，如横向电梯和多座大楼的情况，需要对架构进行相应的扩展。
4. debug方法
- 打印输出：在关键代码处添加输出的，输出线程的状态和共享资源的变化，帮助定位问题。
- 断点调试：使用 IDE 的断点调试功能，在关键代码处设置断点，逐步执行代码，观察变量的变化和程序的执行流程，但注意断点调试在多线程程序中，可能会产生一些不可预料的后果，如果是针对某一线程自身运行的问题，可以使用，如果是线程之间的交互问题，那么不建议使用。
- 堆栈信息：在面对死锁问题时，难以定位死锁发生的位置和原因，通过与大模型交流，了解到可以通过修改主类，输出程序正常或非正常停止时的堆栈信息，借助这个信息，可以快速定位死锁发生的位置。
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
public class MainClass {
public static void main(String[] args) {
Runtime.getRuntime().addShutdownHook(new Thread(() -> printStackTrace()));
try {
// Your code here
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
}
private static void printStackTrace() {
ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
ThreadInfo[] threadInfos = threadMXBean.dumpAllThreads(true, true);
for (ThreadInfo threadInfo : threadInfos) {
System.out.println(threadInfo);
}
}
}
心得体会
1. 线程安全
在多线程编程中，线程安全是一个非常重要的问题。通过使用同步块和锁，可以保证共享资源的安全访问，避免数据竞争和不一致性。在本单元的作业中，我深刻体会到了线程安全的重要性，也学会了如何使用锁和同步块来实现线程之间的同步和通信。
2. 层次化设计
层次化设计可以提高代码的可维护性和扩展性。通过将不同的功能模块分离，每个模块只负责自己的任务，降低了模块之间的耦合度。在本单元的作业中，我采用了生产者 - 消费者模式、策略模式和单例模式等设计模式，将请求输入、调度和电梯运行等功能模块分离，使得代码结构更加清晰，易于维护和扩展。
未来方向
本单元的课程经受多年的考验，我认为设置已经相对完善，感谢在此过程中为同学们辛勤付出的老师和助教。