架构设计

黄色部分为第一次作业的类，红色部分为第二次作业新增类，紫色部分为第三次作业新增类。

架构迭代

第一次作业

整体采用了生产者-消费者的设计模式。考虑到第一次作业指定了乘客请求的电梯，我并没有设置调度器线程，而是输入线程 inputThread 读取到乘客请求后直接放入每个电梯各自的乘客请求处理队列 processingQueue。电梯运行采用 LOOK 策略，电梯线程 elevatorThread 每执行完一个动作后从自己的 processingQueue 中取出一个乘客请求，并结合自身的信息发送给策略类 Strategy，获取下一动作 advice 并执行。

第二次作业

第二次作业新增了临时调度请求，并取消了乘客请求指定电梯，即需要调度给某部电梯来运送乘客。因此在第二次作业中，我新增了全局的请求队列 requestQueue，并由调度器线程 dispatchThread 来将请求分配给某部电梯，放入其请求处理队列 processingQueue，随后电梯线程 elevatorThread 不断获取和处理其中的请求。

第三次作业

第三次作业新增了双轿厢改造请求，改造后的两部电梯需要协同完成乘客请求。因此在第三次作业中新增了伙伴锁 buddyLock，被双轿厢中的两部电梯各自拥有，用于实现两部电梯的通信。

线程协同

主线程 main 依次创建电梯线程 elevatorThread、调度器线程 dispatchThread 和输入线程 inputThread。inputThread 每次读取到请求就放入全局请求队列 requestsQueue，dispatchThread 依次从 requestsQueue 中取出一个请求，并按随机调度策略或特殊请求的指定电梯放入相应电梯的请求处理队列 processingQueue。elevatorThread 每执行完一个动作就按优先级从自己的 processingQueue 中获取不同的请求（临时调度请求 = 双轿厢改造请求 > 乘客请求）；若遇到特殊请求，则根据情况将电梯中的乘客放回到 requestsQueue 中重新调度。

inputThread 结束的标志为读取到的请求为 null，结束时通知 requestsQueue。requestsQueue 关闭的标志为 inputThread 结束且 6 部电梯在同一时间段内全部处于等待状态，关闭时通知 dispatchThread。dispatchThread 结束的标志为 requestsQueue 关闭且为空，结束时通知六部电梯的 processingQueue。processingQueue 被 dispatchThread 通知后立即关闭，即每部电梯不再接收新的请求，并通知相应的 elevatorThread。elevatorThread 的结束标志为相应的 processingQueue 关闭且为空，作为整个程序最后结束的线程。

调度器 & 电梯运行

调度器设计

我是保守派，为了保证正确性，只采用了随机调度策略（考虑到双轿厢改造，需保证电梯能够到达乘客的出发楼层）。同时，一个乘客请求仅由一部电梯或由一对双轿厢电梯协作完成接送：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// DispatchThread.java
public class DispatchThread extends Thread {
    public void run() {
        //...
		Person person = requestsQueue.pollPersonRequest();
    	if (person != null) {
        	int elevatorId = person.getElevatorId() == 0 ? getBestElevator(person.getFromFloor()) : person.getElevatorId();
       	 	processingQueueMap.get(elevatorId).offerPersonRequest(person);
  	  	}
        //...
    }

    private int getBestElevator(int fromFloor) {
        Random random = new Random();
        int elevatorId;
        do {
            elevatorId = random.nextInt(6) + 1;
        } while (!(processingQueueMap.get(elevatorId).canArrive(fromFloor)));
        return elevatorId;
    }
}

当某部电梯被分配到乘客请求时，若该电梯正在处理特殊请求（临时调度 or 双轿厢改造），则将该乘客请求放入一个缓冲区 ArrayList<Person> buffer（位于 ProcessingQueue）中，待电梯处理完特殊请求后将所有缓冲区中的乘客请求全部 RECEIVE，并进行处理；否则，该电梯直接 RECEIVE 并接送该乘客。

电梯运行策略

电梯运行采用 LOOK 策略，并考虑乘客的优先级。

  • 先判断是否要开门（先出后进）：
    • 若当前电梯中有乘客的目的楼层为当前楼层，则这些乘客出电梯（type = OPEN）；
    • 若 queue 中有乘客从当前楼层出发，且目的楼层在电梯移动的前方、电梯人数未达上限，则这些乘客按优先级进电梯（type = OPEN）；
  • 若上述条件均不满足，但电梯中仍然有乘客，则电梯沿当前方向移动一层（type = MOVE）；
  • 若上述条件均不满足（既不开门也没有乘客在电梯），则判断电梯是否要移动：
    • 若乘客请求队列非空，且存在请求的出发楼层在电梯移动的前方，则电梯沿当前方向移动一层（type = MOVE）；
    • 若乘客请求队列非空，且所有请求中，要么出发楼层在电梯移动的后方，要么出发楼层为当前楼层但目的楼层在电梯移动的后方，则电梯转向（type = REVERSE）；
    • 若乘客请求队列非空，且优先级最高的乘客请求在前方
    • 若乘客请求队列为空，但队列仍未关闭，则电梯等待（type = WAIT）；
    • 否则，乘客请求队列为空且队列关闭，且电梯中没有乘客，则电梯结束（type = OVER）

同步块

本单元中，拥有临界资源的类我一律使用 synchronized 将其方法设置为同步块：

  • 生产者方法（如 addPersonRequest）：添加请求时获取锁，操作后调用 notifyAll() 唤醒等待线程。
  • 消费者方法（如 pollPersonRequest）：获取锁后若队列为空，则通过 wait() 释放锁并等待。
  • 特殊请求处理（如 pollScheRequest）：非阻塞获取临时请求，避免线程阻塞。

同步块处理语句的关系：

  • 原子操作：对共享数据的修改（如 personRequests.remove(0)）均在同步块内完成，确保操作的原子性。

  • 等待条件：在 pollPersonRequest 中，若队列为空且未终止，线程通过 wait() 释放锁并等待。

  • 唤醒机制：任何新增请求或终止信号（如 addPersonRequest、setInputEnd）均调用 notifyAll()，确保等待线程及时响应。

双轿厢改造

在第三次作业中，新增 BuddyLock 类用于实现双轿厢电梯的通信。双轿厢的两部电梯拥有一个公共的 buddyLock。

输出唯一

两部电梯在双轿厢改造时，调用 buddyLock.printBegin() 与 buddyLock.printEnd() 来进行题目要求的输出。通过 synchronized 对同步块进行加锁，以及 waitForBuddy 和 hasPrinted 信号的设置，实现两部电梯仅有一次终端输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// BuddyLock.java
public synchronized void printBegin() { print(String.format("UPDATE-BEGIN-%d-%d", elevatorAId, elevatorBId)); }
public synchronized void printEnd() { print(String.format("UPDATE-END-%d-%d", elevatorAId, elevatorBId)); }

private synchronized void print(String s) {
    if (waitForBuddy) { // 先到者进入
        waitForBuddy = false;
        try {
            wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    if (!hasPrinted) {  // 后到者进入
        TimableOutput.println(s);
        hasPrinted = true;
        notifyAll();
    } else {
        waitForBuddy = true;
        hasPrinted = false;
    }
}

避免碰撞

当某一部电梯尚未离开共享楼层时，该电梯将一直持有该楼层的锁（locked = true），此时另一部电梯无法到达该楼层（wait()）；直到 ARRIVE 其他楼层时调用 buddyLock.unlock() 释放锁（locked = false）。若该电梯持有共享楼层的锁时，另一部电梯想要到达楼共享层，则会调用 buddyLock.notifyBuddy() 来通知另一部电梯离开。这样就可以有效地避免碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//BuddyLock.java
public synchronized void lock(int elevatorId) {
    while (locked) {
        try {
            notifyBuddy(elevatorId);
            wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    locked = true;
}

public synchronized void unlock() {
    locked = false;
    notifyAll();
}

BUG & DEBUG

该单元依旧采用搭建评测机的方式来对自己的程序进行测试。一些简单的 WRONG_AWNSER Bug 不提，下面主要针对一些 CPU_TIME_LIMIT_EXCEEDED 以及 REAL_TIME_LIMIT_EXCEEDED 的 Bug。

CPU_TIME_LIMIT_EXCEEDED 基本上是出现轮询的原因，第一次作业和第二次作业在课下测试的时候都遇到过。Debug 主要借助 Interllij Profiler 工具来查找 CPU 执行时间过长的代码段，从而定位轮询的地方。如下图，很明显 ProcessingQueue.canArrive() 被轮询调用。

REAL_TIME_LIMIT_EXCEEDED 的原因就比较复杂了，我出现的原因是死锁以及线程没有被正确终止，并且这两个问题都难以复现，基本上同一个数据点跑几百次会爆一次。Debug 的方式参考讨论区的方法：对关键地方进行日志打印 [LOG]...，从而在爆 REAL_TIME_LIMIT_EXCEEDED 时根据输出来定位 bug。

心得体会

  • 线程安全：
    • 避免死锁：避免两个线程（Thread_0, Thread_1）同时拥有相同的两个临界资源（lock_A, lock_B）！可能会出现两个线程持有各自临界资源的锁时（Thread_0:lock_A，Thread_1:lock_B），想获取对方临界资源的锁，此时就会发生死锁！
    • 避免错过唤醒：一个线程在尚未获取到锁、但下一步是在该锁上 wait() 时，如果另一个线程此时在该锁上 notify() 了，那么第一个线程可能永远醒不过来了。解决方法：在获取到锁后、wait() 之前再一次进行条件判断，是否真的要睡，即从判断睡眠到执行睡眠的过程中不放锁。
    • 保证临界资源的安全：通过 synchronized 关键字对共享资源的访问进行同步，确保多线程操作的原子性。
  • 层次化设计：
    • 模块化职责划分：将不同的职责模块化为不同种的类：线程类 InputThread、DispatchThread 和 ElevatorThread，共享资源实体类 RequestsQueue 和 ProcessingQueue，策略类 Strategy。
    • 策略解耦：将电梯运行策略 Strategy 与电梯运行 ElevatorThread 逻辑分离，未来可通过替换策略实现不同算法。