[BUAA-OO] 2025 第二单元总结博客

电梯调度吟

预判影行谋略深，乘客随唤策略新。
双轿协同开新境，调度有方启后人。
负载均衡效率高，智能运作见奇勋。
电梯虽小乾坤大，智慧无穷妙理存。

电梯月结束了，又有很多全新体验。尤其是多线程的相关知识，OS期中复习线程同步互斥时又看见了熟悉的知识点，联想到OO课上学到的相关理论，感觉收获颇丰，有种知识 融会贯通 涌入我的大脑的感觉。闲话少叙，下面进入正题———多线程电梯调度系统。

一、同步块和锁

下面笔者将结合本人三次作业中对于线程安全和线程同步的实际方案，谈谈同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系，具体架构实现请参考线程协作与架构设计和调度器设计与调度策略。

1.1 同步块的设置

同步块和锁设置的原因是为了在多线程并发执行时保证线程安全，防止多个线程同时访问共享资源，出现数据不一致的情况。在Unit2的模拟电梯调度系统中，由于我们所采用的生产者-消费者模型，因而存在多种由生产者和消费者访问的共享资源：

  • 输入线程生产乘客请求、临时调度请求和更新请求置于主队列或子队列中；
  • 调度线程从主队列中取出请求，通过调度算法将乘客请求放入对应电梯的子队列中；
  • 电梯线程从子队列中取出乘客请求、临时调度请求和更新请求并执行、清除；
  • 电梯线程将乘客请求返回到主队列中；
  • 双轿厢电梯互斥进入换乘楼层，互斥访问协作类。

以上场景中对于共享资源的访问，必须保证在同一时刻只有一个线程可以访问/操作。否则，可能会导致数据不一致或程序崩溃等问题。我们选择将共享资源封装成一个专门的类，便于进行同步互斥操作。具体的Java同步块实现如下：

1
2
3
synchronized (object) {
    // 需要同步的代码块
}

或者

1
2
3
public synchronized void method() {
    // 需要同步的方法
}

其中，object是用于标识同步对象的，可以是任意对象，也可以是this，即当前对象。在同步块中，只有获取到object的锁才能执行其中的代码，否则会被阻塞，直到锁被释放。对于方法，则是只有获取到当前对象的锁(对于静态方法是这个类的锁)才能执行该方法，否则会被阻塞，直到锁被释放。
读锁和写锁是另一种锁的选择，用于实现读写分离，提高并发性能。读锁允许多个线程同时读取共享资源，而写锁则独占访问共享资源。Java中可以使用ReentrantReadWriteLock类来实现读写锁。读锁和写锁的使用方法如下(不过我在Unit2中并未用到 因为没必要 )：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
lock.readLock().lock();
try {
    // 读操作
} finally {
    lock.readLock().unlock();
}

lock.writeLock().lock();
try {
    // 写操作
} finally {
    lock.writeLock().unlock();
}

1.2 锁的选择

在同步块中，锁的选择至关重要。如果锁的选择不当，可能会导致死锁、数据冲突等问题。在Java中，锁的选择通常基于以下原则：

  1. 锁的粒度：
    • 锁的粒度越小，线程的并发性能越高，但可能增加死锁的风险。
    • 锁的粒度越大，线程的并发性能越低，但实现简单。
  2. 锁的对象：
    • 使用this作为锁对象时，锁住的是当前实例。
    • 使用类对象（如对方法加锁时）作为锁对象时，锁住的是整个类的所有实例。
    • 如果需要更细粒度的控制，可以使用特定的对象作为锁。(但要保证不出现死锁或是一睡不醒的情况)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// in MainQueue.java
// 对方法加锁，锁住的是实例化后的对象
public synchronized void addPersonRequest(Person person) {
    persons.add(person);
    notifyAll(); // 唤醒所有等待的线程
}
// in Elevator.java
// 对this加锁，锁住的是当前实例
long remainingTime = waitingTime - System.currentTimeMillis() +  lastTime;
if (remainingTime > 0) {
    try { synchronized (this) { wait(remainingTime); } } // 电梯运行时等待
    catch (InterruptedException e) { e.printStackTrace(); }
}
// in Elevator.java
// 对类对象加锁
synchronized (subQueue) {
    // 防止一睡不醒！
    if (subQueue.isEnd()) { return; } // 如果子队列已结束，则不再等待
    if (!subQueue.isEmpty()) { return; } // 如果子队列不为空，则不再等待
    try { subQueue.wait(); } 
    catch (InterruptedException e) { Thread.currentThread().interrupt(); } // 调用等待方法，使当前线程挂起
}

上一小节列出了模拟电梯调度系统中的共享资源，我们需要在这些共享资源加锁，保证对其的访问是线程安全的。在退出临界区时，需要释放锁，并唤醒其他等待的线程。(在所有同步块中包含notifyAll()方法唤醒所有等待的线程并不明智，还是要具体分析看是否有需要唤醒的线程。)

锁与同步块中处理语句的关系

设置锁的目的是保证临界区代码的原子性，即要么全部执行，要么全部不执行。因此，锁保护了同步块中处理语句对于共享资源的访问和操作。有以下几点需要注意：

  1. 锁的作用范围： 锁的作用范围决定了哪些代码可以被多个线程并发执行，哪些代码需要串行执行以维护线程安全。在同步块中，只有获取到锁的线程才能执行代码，其他线程会被阻塞。这要求锁的作用范围应该尽量小，以提高并发性能。
  2. 死锁的风险： 对于共享资源的盲目加锁可能导致死锁。例如，如果两个线程分别持有一个锁，并试图获取对方持有的锁，那么它们将永远无法继续执行。例如下面这段代码就可能导致死锁(不过肯定没人这么写)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// in Elevator.java
// update结束后，电梯线程需要清除子队列中无法送达的请求
sycnhronized (subQueue) { <--获取子队列的锁
    Person unablePerson = subQueue.getUnableRequest(isA, isB, transferFloor);
    while (unablePerson != null) { // 清除等待队列中的无效请求
        // 将无效请求放回主队列
        mainQueue.addPersonRequest(unablePerson); <-- 需要获取主队列的锁
        unablePerson = subQueue.getUnableRequest(isA, isB, transferFloor);
    }
}

// in Scheduler.java
// 调度线程从主队列中取出请求，将乘客请求放入对应电梯的子队列中
sycnhronized (mainQueue) { <-- 获取主队列的锁
    Person person = mainQueue.getPersonRequest();
    if (person != null) {
        int elevatorId = bestElevator(person);
        subQueues.get(elevatorId).addPersonRequest(person); <-- 需要获取子队列的锁
    } else {
        continue;
    }
}
  1. 锁的粒度与性能： 如果同步块中包含的语句过多，会降低并发性能；如果同步块中包含的语句过少，可能无法完全保护共享资源。因此，锁的粒度需要根据具体情况进行调整。一般来说，锁的粒度应该尽量小，以提高并发性能，否则多线程有可能退化成单线程，但也要保证线程安全。

二、线程协作与架构设计

Unit 2的三次作业是循序渐进、逐层深入的，因此我们将在这里对三次作业的设计思路进行总结，尤其是对于多线程协作的架构设计思路。

作业 功能变化
hw5 根据输入的乘客请求和对应的电梯序号调度电梯，主要关注电梯运行策略的设计以及基本的生产者-消费者模型构建
hw6 在hw5的基础上，不再规定电梯序号，调度器根据乘客请求和电梯状态调度电梯，主要关注调度器的设计和调度策略的实现并增加临时调度请求的处理
hw7 在hw6的基础上，增加电梯的更新请求，改造两个单轿厢电梯为双轿厢电梯，主要关注双轿厢电梯的同步更新和运行防撞，调度器需要进行合理调度

下面将结合三次作业的具体实现，总结多线程协作的架构设计思路。

hw5

hw5线程协作

hw5协作图

由于乘客所乘坐的电梯已经在输入中给出，因此只需要将乘客请求放入对应电梯的子队列中即可。由于不知道输入何时到来，因此需要使用一个输入线程来读取输入，直至读到EOF。同时，由于电梯需要不断运行，保证将所有乘客送到目的地，因此需要使用一个电梯线程来处理子队列中的请求。在本次作业中，我们可以选择直接新建一个输入线程和六个电梯线程(白雪公主和六个小矮人bushi)，由输入线程直接将乘客请求放入对应电梯的子队列中，由电梯线程处理子队列中的请求。一个很简单的生产者-消费者模型：输入线程生产乘客请求，电梯线程消费乘客请求，电梯的子队列作为共享资源。但通过参考往年博客，我们发现后续作业将取消乘客所乘坐的电梯序号的输入，因此我们选择在hw5中设计一个调度器线程，负责处理输入线程放至主队列的乘客请求，并将乘客请求放入对应电梯的子队列中，交给电梯线程处理。这样，我们的电梯调度系统需要8个线程，分别是1个InputThread输入线程、1个Scheduler调度器线程和6个Elevator电梯线程，这些线程都由主类创建(后续协作图上省略主线程的创建过程)。
综上，我们构建了一个两级 生产者-消费者模型：输入线程生产乘客请求，调度器消费乘客请求，主队列作为共享资源；调度器生产对应电梯的乘客请求，电梯线程消费该乘客请求，电梯的子队列作为共享资源。 这样做的好处是：

  • 解耦：调度器线程和电梯线程之间的耦合度降低，调度器只负责调度，电梯只负责运行。这样可以更好地分离关注点，提高代码的可维护性和可扩展性。
  • 扩展：调度器线程可以扩展，在后续作业中，我们可以根据需要添加新的调度策略，而不需要修改电梯线程的实现。这样可以提高代码的可扩展性。
hw5架构设计

hw5类图

本单元的第一次迭代难度不是太高，主要的训练目标是让大家熟悉Java多线程的基本概念和使用方法，并且确定单个电梯的运行策略，为后续设计调度策略打下基础。我的架构设计如下：

  • InputThread：输入线程，负责读取输入，将乘客请求放入主队列中。
  • Scheduler：调度器线程，处理主队列中的乘客请求，根据bestElevator方法的返回值将乘客请求放入对应电梯的子队列中。本次作业中简单地读取乘客的电梯序号即可。
  • Person：乘客类，包含乘客的电梯序号、楼层、方向、优先级等信息。由官方包中Request类扩展而来，增加了int类型的楼层和方向属性。
  • RequesQueue：请求队列类，用于实例化主队列和子队列，管理乘客请求，是生产者-消费者模型中的共享资源。
  • ELevator：电梯线程，处理子队列中的乘客请求，根据电梯的运行策略将乘客送到目的地，可以捎带或优先处理高优先级乘客(踢人)。
  • Strategy：电梯运行策略接口，实现电梯策略和运行的解构，便于后续调整策略。本次作业采取LOOK策略。
运行策略和调度策略
  1. 运行策略：Strategy类是电梯线程的抽象策略类，用于获取电梯的运行建议。在本次作业中，我使用了最常见的LOOK策略，即电梯在当前方向上尽可能多地接送请求，直到当前方向上的请求都处理完毕，再转向继续处理请求。
    • 子队列不为空，电梯运行前方楼层有请求或电梯内有乘客，则电梯继续沿原方向运动；
    • 子队列不为空，所有乘客请求都在电梯运行后方的楼层(FromFloor和ToFloor)，则电梯掉头；
    • 子队列为空但并未结束，则电梯停在该楼层等待；
    • 子队列为空且已经结束，则电梯线程结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Strategy {
    private final RequestQueue subQueue;
    private final ArrayList<Person> persons;
    private int personsIn;
    private final int maxPersonNum = 6;

    public Strategy(RequestQueue subQueue, ArrayList<Person> persons, int personsIn) {
        this.subQueue = subQueue;
        this.persons = persons;
        this.personsIn = personsIn;
    }
    public Advice getAdvice(int currentFloor, int direction, int personsIn) {
        this.personsIn = personsIn;
        if (hasPersonOut(currentFloor) || hasPersonIn(currentFloor, direction)) {
            return Advice.OPEN; // 电梯内有乘客到达目的楼层，或者当前层有等待乘客且方向相同
        } else if (personsIn > 0) {
            return Advice.MOVE; // 电梯内有乘客，继续前进
        } else if (!subQueue.isEmpty()) {
            if (hasRequestAhead(currentFloor, direction)) {
                return Advice.MOVE; // 当前方向前方有请求，继续前进
            } else {
                return Advice.REVERSE; // 当前方向前方无请求，改变方向
            }
        } else if (subQueue.isEnd()) {
            return Advice.OVER; // 子队列为空，且输入结束，结束电梯线程
        } else {
            return Advice.WAIT; // 电梯内无乘客，外部无请求，等待新请求
        }
    }
···
}
  1. 调度策略： 本次作业中，我们只需简单地读取乘客的电梯序号，因此调度策略非常简单。我们只需要将乘客请求放入对应电梯的子队列中即可。
数据类

根据我们上面的分析，InputThread和Scheduler是生产者，MainQueue是共享资源，Scheduler和Elevator是消费者，SubQueue是共享资源，用来管理储存Person乘客请求。因此对于共享资源MainQueue和SubQueue的访问需要加锁，保证线程安全。我对RequesQueue类所有方法都加上了锁，并在需要时使用notifyAll()唤醒其他等待线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// RequesQueue.java
public class RequestQueue {
    private ArrayList<Person> persons = new ArrayList<>();
    private boolean end = false;

    public synchronized ArrayList<Person> getPersons() {
        notifyAll();
        return persons;
    }
    public synchronized void addPersonRequest(Person person) {
        persons.add(person);
        notifyAll();
    }
    public synchronized Person getPersonRequest() { 
        // 用于调度器从主队列中获取乘客请求
        ...
        return person;
    }
    public synchronized boolean isEmpty() {
        notifyAll();
        return persons.isEmpty();
    }
    public synchronized boolean isEnd() { return end; }
    public synchronized void setEnd() {
        end = true;
        notifyAll();
    }
    public synchronized Person getPersonIn(int floor, int direction) { 
        ...// 获取某层某方向优先级最高的乘客
    }
}

// Person.java
public class Person {
    public Person(PersonRequest request) {
        ...
        this.fromInt = floorToInt(fromFloor);
        this.toInt = floorToInt(toFloor);
        this.direction = Integer.compare(toInt, fromInt);
    }
    public Person(String fromFloor, String toFloor, int personId, int priority, int elevatorId) {
        ...
        this.fromInt = floorToInt(fromFloor);
        this.toInt = floorToInt(toFloor);
        this.direction = Integer.compare(toInt, fromInt);
    }
}
线程类

本次作业的InputThread和Scheduler类的设计比较简单，主要是读取输入和调度乘客请求：

  • InputThread类负责读取输入，将输入的乘客请求封装成Person对象，并放入主队列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class InputThread extends Thread {
    private final RequestQueue mainQueue;

    public InputThread(RequestQueue mainQueue) {
        this.mainQueue = mainQueue; // 由MainClass创建的主队列
    }

    @Override
    public void run() {
        ElevatorInput elevatorInput = new ElevatorInput(System.in);
        while (true) {
            PersonRequest request = (PersonRequest) elevatorInput.nextRequest();
            if (request == null) {
                // 设置主队列结束标志
                break;
            } else {
                // 将输入的乘客请求封装成Person对象
                // 将乘客请求放入主队列
            }
        }
    }
}
  • Scheduler类共享主队列，负责调度乘客请求，将乘客请求分配给电梯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Scheduler extends Thread {
    private final RequestQueue mainQueue;
    private final HashMap<Integer, RequestQueue> subQueues;
    private final HashMap<Integer, Elevator> elevators;

    public Scheduler(RequestQueue mainQueue, HashMap<Integer, RequestQueue> subQueues,
        HashMap<Integer, Elevator> elevators) {
        this.mainQueue = mainQueue;
        this.subQueues = subQueues;
        this.elevators = elevators;
    }
    public Integer bestElevator(Person person) {
        return person.getElevatorId(); // easy!
    }
    @Override
    public void run() {
        while (true) {
            synchronized (mainQueue) {
                if (mainQueue.isEmpty() && mainQueue.isEnd()) {
                    // 设置子队列结束标志
                    return;
                }
            }
            Person person = mainQueue.getPersonRequest();
            if (person != null) {
                subQueues.get(bestElevator(person)).addPersonRequest(person);
            } else {
                continue;
            }
        }
    }

}
  • Elevator电梯线程的设计相对复杂一些，主要是实现电梯的运行策略和捎带乘客的逻辑。我们在这里使用了一个Strategy类来实现电梯的运行策略，电梯只要调用getAdvice方法就可以获取到下一步的运行策略。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Elevator extends Thread {
    private final int id;
    private final RequestQueue subQueue;
    private int currentFloor;
    private int personsIn;
    private int direction;
    private final ArrayList<Person> persons;
    private final Strategy strategy;
    private final int maxPersonNum = 6;
    private long lastTime; // 维护时间戳，用于计算等待时间

    public Elevator(int id, RequestQueue subQueue) {
        this.id = id;
        this.subQueue = subQueue;
        this.currentFloor = 1;
        this.personsIn = 0;
        this.direction = -1; // 如何确定初始方向？
        this.persons = new ArrayList<>();
        this.strategy = new Strategy(subQueue, persons, personsIn);
        this.lastTime = System.currentTimeMillis();
    }

    @Override
    public void run() {
        while (true) {
            Advice advice = strategy.getAdvice(currentFloor, direction, personsIn);
            switch (advice) {
                case OPEN:
                    openAndClose();
                    break;
                case MOVE:
                    move();
                    break;
                case REVERSE:
                    reverse();
                    break;
                case OVER: // 结束
                    return;
                case WAIT:
                    waitRequest();
                    break;
                default:
                    System.out.println("Error in Elevator.run");
                    break;
            }
        }
    }
... // 具体实现
}

关于初始方向： 由于电梯初始在F1层，而电梯大楼从B4层到F7层，LOOK策略会优先接送完当前方向的请求再反向，因此如何设置初始方向成了我在第一次迭代时考虑的问题。我认为，B4层到F1层的距离小于F1层到F7层的距离，因而设置初始方向向下，使得响应两方向的请求时间都不太长。但在第二次迭代时，我选择修改LOOK策略为LOOK+ALS策略，由电梯主动选择方向。

关于量子电梯：第一次迭代并未有RECEIVE限制，即要求电梯在接到请求(输出RECEIVE)后才能运动，因此电梯在等待或运行时存在量子状态：

  1. 等待状态：电梯在等待乘客请求时，由于输出ARRIVE是电梯移动一层的结束，因此等待在某一层的电梯可以处于等待、向上走、向下走的量子状态，也就是在三层楼之间处于不被观测的状态。
  2. 运行状态：电梯在运行时，移动的时间是电梯运行的量子时间，电梯在运行时可以处于移动、等待的量子状态。在移动时间结束时，电梯既可以出现在当前楼层，也可以出现在下一楼层。

电梯既在等待，又在运行。

量子电梯时一种仅仅为了适应评测机而诞生的毫无作用的小trick。想要ban掉量子电梯的设计，最简单的方法就是让电梯开始移动也输出一个标志位。

hw6

hw6线程协作

hw6协作图

在第六次作业中，我们继续沿用两级生产者-消费者模型，在上次作业的基础上迭代。输入线程负责读取乘客请求并将其放入主队列；调度器从主队列中取出乘客请求，并根据调度策略调用bestElevator方法，将其分配给合适的电梯子队列；电梯线程从自己的子队列中取出请求并处理。本次作业的重点在于 1. 实现模拟电梯系统的调度策略 以及 2. 实现新增临时调度请求。

  • 新增Elevator类向MainQueue中返回乘客请求的协作，用于临时调度前后的乘客请求取消RECEIVE，并配合LOOK+ALS策略实现乘客可重复选择电梯。
  • 新增调度辅助类ElevatorStorage和ShadowElevator类，通过电梯线程主动留下影子和调度器线程获取电梯状态的协作方式，实现调度策略。
  • 新增InputThread类向SubQueue中添加临时调度请求的协作，保证电梯线程在运行时会优先处理临时调度请求。
hw6架构设计

hw6类图

本次作业的架构设计在第五次作业的基础上进行了扩展和优化：

  • InputThread：读取输入并放入主队列(乘客请求)或者电梯线程的子队列(临时调度请求)，在输入结束时传递InputEnd信号。
  • MainQueue：主队列存储所有待分配的乘客请求(输入线程生产的乘客请求以及电梯线程返回的乘客请求)，供调度器消费，设置计数器给出isAllEnd信号。
  • Scheduler：调度器线程负责从主队列中取出乘客请求，并根据调度策略将其分配到合适的电梯子队列。
  • SubQueue：每个电梯都有自己的子队列，存储分配给该电梯的乘客请求。
  • Elevator：电梯线程从自己的子队列中取出请求并处理，根据 LOOK+ALS 策略运行。
  • ElevatorStorage：电梯存储类，存储所有影子电梯的状态信息。
  • ShadowElevator：影子电梯类，用于模拟电梯的当前状态，供调度器进行调度决策。
  • NewStrategy：策略类，实现 LOOK+ALS 策略，指导电梯的运行。
LOOK+ALS 策略的实现

自由竞争策略曾经是往届博客中强推的一种电梯调度方法，但所有电梯一拥而上比拼速度，会导致耗电量巨大，且电梯运行效率低下，也不符合现实情况。而RECEIVE的限制使得电梯不能随意移动，而必须在接受乘客请求后才能开始运动(这也ban掉了量子电梯)，因此我们需要设计一个合理的调度策略来解决这个问题。那么问题来了，RECEIVE应该在何时输出，由谁来输出？
由Scheduler或者SubQueue在将乘客请求放入电梯子队列时输出RECEIVE是一种简单的设计，但这样会导致电梯接受乘客请求的时间未知，不利于维护时间戳以及保证输出顺序。因此，我们选择在Elevator中输出RECEIVE，但电梯线程如何知道何时输出RECEIVE并及时输出呢？
电梯在运行过程中，可能会出现电梯正在移动或者等待的情况，此时电梯无法执行接受新的乘客请求的方法。这会导致输出时间延后，还是不利于维护时间戳。所以，有什么方法可以让电梯在运行过程中及时输出RECEIVE呢？
事实上，我们不需要在将乘客请求加入子队列时就输出RECEIVE，我们并没有要求乘客RECEIVE和IN之间有时间间隔，完全可以在乘客进入电梯时输出RECEIVE。可电梯无法在RECEIVE任何乘客之前移动，除非我们保证电梯在移动之前有RECEIVE的乘客，这和ALS的主请求很相似，不是吗？因此我们利用ALS运行策略让电梯有主请求。
在实际生活中，人们在电梯厅等待电梯时，通常会选择距离最近的电梯。如果电梯满员或无法满足需求，人们会切换到其他电梯。这种行为模式为我们设计乘客分配策略提供了直观的灵感。参考钟昊翔学长的博客
综上，我们采用LOOK+ALS和乘客可重复选择电梯的电梯运行策略；

  • 乘客初始时被分配给一个电梯，但如果该电梯满员或无法满足需求，乘客会被放回主队列，重新分配给其他电梯。
  • LOOK+ALS策略结合了 ALS和 LOOK 策略的优点：1. ALS 策略：电梯空闲时选择一个主请求，并沿主请求的方向开始运动，捎带沿途的其他请求。实现了电梯只需要RECEIVE最少的请求即可开始运动。2. LOOK 策略：电梯在当前方向上移动，处理沿途的请求，若前方无请求且电梯内无人，则反转方向。实现了电梯在当前方向上尽可能多地接送请求。具体实现如下：
    • 选择主请求：电梯空闲时，从子队列中选择并RECEIVE一个主请求，沿主请求的方向开始运动。
    • 捎带请求：在运动过程中，电梯会捎带同方向的其他请求。
    • 接送乘客：电梯在到达目标楼层时，开门接送乘客，乘客进入前RECEIVE(除了主请求)，无法进入的乘客将返回主队列。
    • 方向反转：当电梯当前方向前方无请求且电梯内无人时，电梯反转方向。
    • 临时调度请求处理：若电梯收到临时调度请求，会优先处理该请求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class NewStrategy { // LOOK+ALS
    private final SubQueue subQueue; // 等待队列
    private final ArrayList<Person> persons; // 电梯内乘客列表
    private int personsIn;
    private final int maxPersonNum = 6;
    private AtomicReference<Person> mainRequestRef; // 主请求

    public NewStrategy(SubQueue subQueue, ArrayList<Person> persons, 
        int personsIn, AtomicReference<Person> mainRequestRef) {
        this.mainRequestRef = mainRequestRef; // 主请求
        this.subQueue = subQueue; // 初始化子队列
        this.persons = persons; // 初始化电梯内乘客列表
        this.personsIn = personsIn;
    }
    public Advice getAdvice(int currentFloor, int direction, int personsIn) {
        this.personsIn = personsIn;
        if (subQueue.hasScheRequest()) { // 处理临时调度请求
            return Advice.SCHE;
        }
        if (direction == 0) { // 电梯空闲状态选择主请求
            Person p = subQueue.getPrimaryRequest();
            if (p != null) { // 主请求的设置由电梯完成
                return Advice.MOVE;
            } else {
                return subQueue.isEnd() ? Advice.OVER : Advice.WAIT;
            }
        } else if (hasPersonOut(currentFloor) || hasPersonIn(currentFloor, direction)) {
            return Advice.OPEN; // 如果电梯内有乘客到达目的楼层，或者当前层有等待乘客且方向相同
        } else if (personsIn > 0) {
            return Advice.MOVE; // 如果电梯内有乘客，继续前进
        } else if (!subQueue.isEmpty()) {
            if (hasRequestAhead(currentFloor, direction)) {
                return Advice.MOVE; // 如果当前方向前方有请求，继续前进
            } else {
                return Advice.REVERSE; // 如果当前方向前方无请求，改变方向
            }
        } else if (subQueue.isEnd()) {
            return Advice.OVER; // 如果请求队列为空，且输入结束，结束电梯线程
        } else {
            return Advice.WAIT; // 如果电梯内无乘客，外部无请求，等待新请求
        }
    }
    ···
}
电梯调度的改进

似是而非的影子电梯：在第六次作业中，我们引入了影子电梯（ShadowElevator）的概念，用于调度器对电梯运行的粗略模拟，实现调度。调度器不再直接根据乘客的电梯序号分配请求，而是根据所有电梯的当前状态（通过影子电梯获取）为每个乘客选择最佳的电梯。具体实现如下：

  • 影子电梯（ShadowElevator）：每个电梯对应一个影子电梯，记录电梯的当前楼层、方向、乘客数量、是否处于临时调度状态等信息。这些信息用于调度器估算电梯完成当前请求所需的时间。
  • 调度器（Scheduler）：调度器从主队列中取出乘客请求后，调用 bestElevator 方法遍历所有影子电梯，根据每个影子电梯的当前状态估算完成该乘客请求所需的时间，并为乘客选择时间最短的电梯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// in Scheduler.java
public Integer bestElevator(Person person) {
    Collection<ShadowElevator> shadows = ElevatorStorage.getInstance().getAllShadows();
    int bestPerformance = Integer.MAX_VALUE;
    int bestAssignedCount = Integer.MAX_VALUE;
    int bestElevatorId = -1;
    ShadowElevator bestShadow = null; 
    for (ShadowElevator shadow : shadows) {
        int perf = shadow.getEstimatePerformance(person);
        if (perf < bestPerformance) {
            ... // 更新最优电梯
        } else if (perf == bestPerformance) {
            int currentAssigned = shadow.getAssignedCount();
            if (currentAssigned < bestAssignedCount) {
                ... // 如果已分配数量较少，则选择该电梯
            } else if (currentAssigned == bestAssignedCount) {
                ... // 如果已分配数量也相同，则选择电梯编号较小的
            }
        }
    }
    if (bestShadow != null) { // 选定后增加该电梯的请求分配计数
        bestShadow.addAssignedCount();
    }
    return bestElevatorId;
}
数据类
  • MainQueue 类是输入线程和输出线程之间的通信桥梁，用于传递请求供调度器消费。主队列的设计与上次作业类似，但增加了计数器用于线程是否结束。
1
2
3
4
5
6
7
8
9
10
11
public class MainQueue extends RequestQueue {
    private int passengerCount = 0; // 乘客请求计数器
    private int scheRequestCount = 0; // 调度请求计数器
    private boolean inputEnd = false; // 输入结束标志

    public synchronized void addPassengerCount() { passengerCount++; }
    public synchronized void addScheRequestCount() { scheRequestCount++; }
    ...
    public synchronized boolean isAllEnd() { return inputEnd && passengerCount == 0 && scheRequestCount == 0; }
    public synchronized void setInputEnd() { inputEnd = true; }
}
  • ElevatorStorage 类保存所有电梯的影子状态，并提供更新和获取影子状态的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class ElevatorStorage {
    private static ElevatorStorage instance = new ElevatorStorage(); // 单例实例
    private HashMap<Integer, ShadowElevator> shadowElevators; // 保存影子电梯状态

    private ElevatorStorage() { 
        shadowElevators = new HashMap<>();
    }

    public static ElevatorStorage getInstance() { 
        return instance;
    }
    
    public synchronized void updateShadow(int elevatorId, int currentFloor,
        int direction, int personsIn, ScheRequest scheRequest) {
        ShadowElevator shadow = shadowElevators.get(elevatorId);
        if (shadow == null) {
            shadow = new ShadowElevator(elevatorId, currentFloor, 
                direction, personsIn, scheRequest);
            shadowElevators.put(elevatorId, shadow);
        } else {
            shadow.update(currentFloor, direction, personsIn, scheRequest);
        }
    }
    
    public synchronized ShadowElevator getShadow(int elevatorId) {
        return shadowElevators.get(elevatorId);
    }
    
    public synchronized Collection<ShadowElevator> getAllShadows() {
        return new ArrayList<>(shadowElevators.values());
    }
}
  • ShadowElevator 类模拟电梯的当前状态，包括楼层、方向、乘客数量、临时调度请求等。调度器根据这些信息估算电梯完成乘客请求所需的时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ShadowElevator {
    private int elevatorId;
    private int currentFloor;
    private int direction;
    private int personsIn;
    private ScheRequest scheduleReq;
    private int assignedCount = 0;

    public ShadowElevator(int elevatorId, int currentFloor, int direction, int personsIn, ScheRequest scheduleReq) {
        this.elevatorId = elevatorId;
        this.currentFloor = currentFloor;
        this.direction = direction;
        this.personsIn = personsIn;
        this.scheduleReq = scheduleReq;
    }

    public synchronized int getEstimatePerformance(Person person) {
        ... // 计算电梯完成乘客请求所需的时间
        double totalTime = travelTime + reversalDelay + loadPenalty;
        return (int)(totalTime * 1000);
    }
}
线程类
  • InputThread 类负责读取输入并将乘客请求放入主队列。本次作业中输入结束将设置主队列InputEnd标志位，作为线程结束的条件之一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class InputThread extends Thread {
    private final MainQueue mainQueue;
    private final HashMap<Integer, SubQueue> subQueues;

    public InputThread(MainQueue mainQueue, HashMap<Integer, SubQueue> subQueues) {
        this.mainQueue = mainQueue;
        this.subQueues = subQueues;
    }
    @Override
    public void run() {
        ElevatorInput elevatorInput = new ElevatorInput(System.in);
        while (true) {
            Request request = elevatorInput.nextRequest();
            if (request == null) { 
                mainQueue.setInputEnd();
                break;
            } else if (request instanceof PersonRequest) {
                ... // 将乘客请求放入主队列
                mainQueue.addPassengerCount();
            } else if (request instanceof ScheRequest) {
                ... // 将调度请求放入对应子队列
                mainQueue.addScheRequestCount();
            }
        }
    }
}
  • Scheduler 类负责从主队列中取出乘客请求，并根据调度策略将其分配到合适的电梯子队列。除bestElevator方法外无变化。

如何实现电梯调度和乘客分配是本次作业的核心问题，我的所谓影子电梯调度策略仅能算是某种调参，但借助乘客可重新分配的特性，仍能取得较好的效果。各类调度器比较可参考调度器设计与调度策略。

  • Elevator 类负责处理子队列中的乘客请求，根据 LOOK+ALS 策略运行。对于本次作业新增临时调度请求，电梯线程会在调用getAdvice方法时优先检查是否有临时调度请求，如果有则优先处理临时调度请求；并且在运行时(move()方法中)会检查是否有临时调度请求，保证在规定时限(6s)内完成临时调度请求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class Elevator extends Thread {
    ...
    private long lastTime; // 上次运行时间
    private double speed = 0.4; // 电梯速度
    private AtomicReference<Person> mainRequest; 

    @Override
    public void run() {
        while (true) {
            Advice advice = newStrategy.getAdvice(currentFloor, 
                direction, personsIn);
            if (direction == 0) {
                initialize(); // 初始化主请求和方向
            }
            switch (advice) {
                case SCHE: // 临时调度请求
                    handleScheRequset();
                    break;
                case OPEN:
                    openAndClose(); 
                    // 主请求到达则设置主请求为空，将未进入的乘客返回主队列
                    break;
                case MOVE:
                    move();
                    // 移动开始时检测主请求是否为空，为空则初始化主请求和方向
                    break;
                case REVERSE:
                    reverse();
                    break;
                case OVER: // 结束
                    return;
                case WAIT:
                    waitRequest();
                    break;
                default:
                    System.out.println("Error in Elevator.run");
                    break;
            }
            ElevatorStorage.getInstance().updateShadow(id, 
                currentFloor, direction, personsIn, null); // 更新电梯状态
        }
    }

    private void handleScheRequset() {
        ScheRequest req = subQueue.getScheRequest();
        if (req == null) { return; } // 如果没有临时调度请求，则返回
        ...
        scheduleOpenAndClose(tempDirection, targetFloor); // 如果电梯内已有乘客，开门
        TimableOutput.println(String.format("SCHE-BEGIN-%d", id)); // 保证门已关闭后，开始临时调度
        lastTime = System.currentTimeMillis(); // 更新时间
        Person person = subQueue.getAndCleanRequest(); // 清除子队列
        while (person != null) {
            mainQueue.addPersonRequest(person); // 放回主队列
            person = subQueue.getAndCleanRequest();
        }
        ...
        scheduleMove(tempDirection, targetFloor, tempFloor); // 移动
        speed = originalSpeed; // 到达目标楼层后，恢复默认速度
        cleanOpenAndClose(1000); // 到达目标楼层，开门并保持 T_stop
        TimableOutput.println(String.format("SCHE-END-%d", id));
        lastTime = System.currentTimeMillis(); // 更新时间
        direction = 0; // 设置电梯方向为0，表示等待
        mainRequest.set(null); // 清空主请求
        subQueue.setScheRequest(null); // 处理完请求后，清空请求
        mainQueue.subScheRequestCount();
    }
}

为了保证电梯能在两次移动楼层操作内开始临时调度且 TcompleteT_{complete}不超过6s，我们不能让临时调度请求和乘客请求一样经过主队列和调度器分配，否则可能会导致ARRIVE过多或是超过6s，而是选择在InputThread类中直接分派临时调度请求，电梯线程在运行时会优先处理临时调度请求。

hw7

hw7线程协作

hw7协作图

在第七次作业中，我们在之前的基础上增加了对双轿厢电梯的支持，引入流水线设计使换乘乘客由A-B电梯接力处理。输入线程读取输入，将乘客请求放入主队列或直接发送临时调度/更新请求给电梯线程；调度器从主队列中取出乘客请求，并根据调度策略将其分配给合适的电梯子队列；电梯线程处理自己的子队列中的请求，并在遇到双轿厢更新请求或是到达换乘层时，与协作器协调完成双轿厢电梯功能。

  • InputThread：读取输入，将乘客请求放入主队列，或将临时调度请求和双轿厢更新请求直接发送给对应的电梯子队列。完成输入后，设置主队列的结束标志。
  • MainQueue：主队列存储所有待分配的乘客请求，供调度器消费。同时，电梯线程会将无法处理/换乘的乘客请求返回主队列，主队列负责维护系统的结束状态。
  • Scheduler：调度器线程与之前相同
  • SubQueue：电梯的子队列，增加支持双轿厢电梯的特殊操作，如处理更新请求和管理换乘楼层相关的乘客请求。
  • Elevator：电梯线程处理自己的子队列中的请求，根据 LOOK+ALS 策略运行。在处理双轿厢更新请求时，与协作器协调，完成双轿厢的设置和更新操作。
  • Coordinator：协作器负责管理双轿厢电梯的换乘楼层协调和更新操作。确保两个轿厢不会同时位于换乘楼层，并协调双轿厢的更新过程。
hw7架构设计

hw7类图

本次作业是电梯单元的最后一次迭代，我的架构设计在前两次作业的基础上进行了扩展，以支持双轿厢电梯的功能。以下我们主要关心双轿厢电梯的实现和调度策略的改进。

双轿厢电梯的实现

双轿厢电梯的运行规则： 双轿厢电梯由原本独立的两台电梯（A 和 B）改造在同一电梯井道内组成(A从原先电梯井瞬移而来，不过并不重要，两台电梯也不会共用子队列)。为了确保安全，两个轿厢不能同时位于换乘楼层。具体规则如下：

  • 轿厢 A 只能在 换乘楼层~F7 运行，轿厢 B 只能在 B4~换乘楼层 运行。
  • 同一井道内的两轿厢不能同时位于换乘楼层。

我们选择使用协作器（Coordinator）来管理双轿厢电梯的换乘楼层访问和更新操作。协作器负责协调两个轿厢的运行，轿厢进入换乘楼层前申请锁，离开时释放锁，确保它们不会在同一时间进入换乘楼层。

协作器（Coordinator）的实现

协作器负责管理双轿厢电梯的换乘楼层访问和更新操作：

  • 换乘楼层协调：在 move 方法中，电梯在即将进入换乘楼层时调用 coordinator.robTransferFloor() 获取换乘层的锁，确保同一时间只有一个轿厢在换乘楼层。当电梯离开换乘楼层时，调用 coordinator.releaseTransferFloor() 释放锁，允许另一个轿厢进入换乘楼层。且如果电梯要在换乘层等待，则手动将其挪个位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Coordinator.java
private boolean isOccupied; // 用于楼层换乘协调
// ---------------- 楼层换乘协调功能 ----------------
public synchronized void robTransferFloor() {
    while (isOccupied) {
        try {
            wait(); // 等待直至换乘层空闲
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    isOccupied = true;
}
public synchronized void releaseTransferFloor() {
    isOccupied = false;
    notifyAll();
}
// Elevator.java
private void move() {
    // 换乘楼层访问控制
    if (currentFloor == transferFloor) {
        coordinator.robTransferFloor(); // 获取换乘层锁
    }
    TimableOutput.println(String.format("ARRIVE-%s-%d", curFloorStr, id));
    // 离开换乘楼层时释放锁
    if (currentFloor == transferFloor + direction) {
        coordinator.releaseTransferFloor();
    } 
}
private void waitRequest() {
    if (hasUpdated && currentFloor == transferFloor) {
        ...
        if (remainingTime > 0) {
            try { synchronized (this) { wait(remainingTime); } } 
            catch (InterruptedException e) { Thread.currentThread().interrupt(); } // 中断
        }
        if (isA) {
            currentFloor = transferFloor + 1; // 更新当前楼层
            ...
        } else if (isB) {
            currentFloor = transferFloor - 1; // 更新当前楼层
            ...
        }
        TimableOutput.println(String.format("ARRIVE-%s-%d", curFloorStr, id)); // 输出到达信息
        coordinator.releaseTransferFloor(); // 离开换乘层，释放换乘层
        lastTime = System.currentTimeMillis(); // 更新时间
        return;
    }
    ...
}
  • 更新协作：在双轿厢更新过程中，协调两个轿厢的同步操作。确保两个轿厢都准备好后再开始更新，更新过程中保持至少 1 秒的等待时间，并输出更新开始和结束的信息。我没有选择由某个电梯线程输出或是创建协作器线程并由其新建电梯线程，而是选择沿用已有的电梯线程，并在协作器中添加了多个标志位来控制更新各阶段的开始和结束，使用 wait() 和 notifyAll() 方法实现线程间的同步。虽然这样可能使得协作器显得复杂，但避免了创建新的线程，也避免输出顺序混乱的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Coordinator {
    private final int elevatorAId;
    private final int elevatorBId;
    private boolean readyA;
    private boolean readyB;
    private boolean readyWaitEnd; // 用于是否已收到 update 通知
    private boolean printBegin; // 用于是否输出 UPDATE-BEGIN 消息
    private boolean updateWaitEnd; // 用于A和B电梯是否结束1s等待
    private boolean printEnd; // 用于是否输出 UPDATE-END 消息
    private long startTime; // 用于记录更新开始时间
    // ---------------- 更新协作功能 ----------------
    public synchronized void updateMonitor(int elevatorId) {
        // 标记己方进入更新状态
        if (elevatorId == elevatorAId) { readyA = true; } 
        else if (elevatorId == elevatorBId) { readyB = true; }
        // 若对方未到位，则等待
        while (!(readyA && readyB)) {
            try { wait(); } 
            catch (InterruptedException e) { ... }
        }
        if (!readyWaitEnd) {
            readyWaitEnd = true;
            notifyAll();
        }
        // 至此，双方均已进入更新状态
        if (!printBegin) {
            printBegin = true;
            TimableOutput.println(String.format("UPDATE-BEGIN-%d-%d", elevatorAId, elevatorBId));
        }
        // 强制等待至少1s，确保双方均在等待中
        if (startTime < 0) {
            startTime = System.currentTimeMillis();
        }
        while (System.currentTimeMillis() - startTime < 1000) {
            try { wait( ... ); } 
            catch (InterruptedException e) { ... }
        }
        if (!updateWaitEnd) {
            updateWaitEnd = true;
            notifyAll();
        }
        if (!printEnd) {
            printEnd = true;
            TimableOutput.println(String.format("UPDATE-END-%d-%d", elevatorAId, elevatorBId));
        }
    }
}
电梯线程的更新处理

电梯线程在处理双轿厢更新请求时，执行以下操作：

  • 收到更新请求后，清空电梯内的所有乘客，并将无法处理的乘客请求返回主队列。
  • 与协作器协作，完成双轿厢的更新设置，包括设置换乘楼层、轿厢类型（A 或 B）、速度等。
  • 更新完成后，电梯移动到换乘楼层上/下的位置，设置为等待准备重新投入运行。
调度策略的改进

扩展影子电梯：增加了对双轿厢的支持，包含以下属性：

  • isA 和 isB：表示电梯是否为轿厢 A 或轿厢 B。
  • transferFloor：换乘楼层。

在估算电梯完成乘客请求所需时间时，根据电梯是否为轿厢 A 或 B 以及乘客的起点和终点楼层，判断乘客是否在轿厢 A 或 B 的服务范围内。如果乘客不在某轿厢的服务范围内，则该轿厢不会被选中。

数据类
  • MainQueue 类扩展了计数器，增加了对更新请求的计数，并提供相应的增加、减少和获取方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class MainQueue {
    private int passengerCount = 0;
    private int scheRequestCount = 0;
    private int updateCount = 0;
    private boolean inputEnd = false;
    ...
    public synchronized void addUpdateCount() {
        updateCount++;
    }
    public synchronized void subUpdateCount() {
        updateCount--;
        notifyAll();
    }
    public synchronized boolean isAllEnd() {
        return inputEnd && passengerCount == 0 && scheRequestCount == 0 && updateCount == 0;
    }
}
  • SubQueue 类 增加了对双轿厢更新请求的处理方法，如设置更新请求、获取更新请求、检查是否有更新请求等。同时，提供了获取不符合轿厢服务范围的乘客请求的方法，用于将无法处理的乘客请求返回主队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SubQueue {
    private UpdateRequest updateRequest = null;

    public synchronized void setUpdateRequest(UpdateRequest updateRequest) {
        this.updateRequest = updateRequest;
        notifyAll();
    }
    public synchronized UpdateRequest getUpdateRequest() {
        return updateRequest;
    }
    public synchronized Person getUnableRequest(boolean isA, boolean isB, int transferFloor) {
        if (persons.isEmpty()) { return null; }
        Person selected = null;
        Iterator<Person> iterator = persons.iterator();
        while (iterator.hasNext()) {
            Person p = iterator.next();
            boolean condition1 = isA && p.getFromInt() < transferFloor;
            boolean condition2 = isB && p.getFromInt() > transferFloor;
            boolean condition3 = isA && p.getFromInt() == transferFloor && p.getToInt() < transferFloor;
            boolean condition4 = isB && p.getFromInt() == transferFloor && p.getToInt() > transferFloor;
            if (condition1 || condition2 || condition3 || condition4) {
                selected = p;
                iterator.remove();
                break;
            }
        }
        return selected;
    }
}
  • ShadowElevator 类增加了对双轿厢的支持，包含 isA、isB 和 transferFloor 属性。在估算时间时根据轿厢的运行范围对乘客请求进行过滤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class ShadowElevator {
    private boolean isA = false;
    private boolean isB = false;
    private int transferFloor = 100;

    public synchronized void update(int currentFloor, int direction, int personsIn, 
        ScheRequest scheduleReq, boolean isA, boolean isB, int transferFloor) {
        this.currentFloor = currentFloor;
        this.direction = direction;
        this.personsIn = personsIn;
        this.scheduleReq = scheduleReq;
        this.isA = isA;
        this.isB = isB;
        this.transferFloor = transferFloor;
    }

    public synchronized int getEstimatePerformance(Person person) {
        int pf = person.getFromInt();
        int pd = person.getToInt();
        double speed = 0.4;
        ...
        if (isA || isB) {
            speed = 0.2;
            if (isA) {
                if (pf > transferFloor || (pf == transferFloor && pd > transferFloor)) {
                    return Integer.MAX_VALUE;
                }
                ...
            } else if (isB) {
                if (pf < transferFloor || (pf == transferFloor && pd < transferFloor)) {
                    return Integer.MAX_VALUE;
                }
                ...
            }
        }
        ...
    }
}
线程类
  • InputThread 类新增双轿厢更新请求。将更新请求直接发送给电梯线程，并设置相关电梯的协作器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class InputThread extends Thread {
    private final MainQueue mainQueue;
    private final HashMap<Integer, SubQueue> subQueues;
    private final HashMap<Integer, Elevator> elevators;

    public InputThread(MainQueue mainQueue, HashMap<Integer, SubQueue> subQueues, 
        HashMap<Integer, Elevator> elevators) {
        this.mainQueue = mainQueue;
        this.subQueues = subQueues;
        this.elevators = elevators;
    }
    @Override
    public void run() {
        ElevatorInput elevatorInput = new ElevatorInput(System.in);
        while (true) {
            Request request = elevatorInput.nextRequest();
            if (request == null) { 
                mainQueue.setInputEnd();
                break;
            } else if (request instanceof PersonRequest) {
                ...
            } else if (request instanceof ScheRequest) {
                ...
            } else if (request instanceof UpdateRequest) {
                UpdateRequest updateRequest = (UpdateRequest) request;
                ...
                Coordinator coordinator = new Coordinator(elevatorAId, elevatorBId);
                elevatorA.setCoordinator(coordinator);
                elevatorB.setCoordinator(coordinator);
                subQueueA.setUpdateRequest(updateRequest);
                subQueueB.setUpdateRequest(updateRequest);
                mainQueue.addUpdateCount();
            }
        }
    }
}

  • Scheduler 类无变化。

  • Elevator 类新增在遇到双轿厢更新请求时，与协作器协作完成更新操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Elevator extends Thread {
    ...
    private double speed = 0.4;
    private Coordinator coordinator = null;
    private boolean isA = false;
    private boolean isB = false;
    private boolean hasUpdated = false;
    private int transferFloor = 100;

    public Elevator(int id, MainQueue mainQueue, SubQueue subQueue) {
    ...
    }

    @Override
    public void run() {
        while (true) {
            Advice advice = newStrategy.getAdvice(currentFloor, direction, 
                personsIn, hasUpdated, transferFloor, isA, isB);
            if (direction == 0) {
                initialize();
            }
            switch (advice) {
                case UPDATE:
                    update();
                    break;
                ...
            }
        }
    }

    private void update() {
        if (hasUpdated) { return; }
        if (personsIn != 0) { cleanOpenAndClose(400); }
        UpdateRequest updateRequest = subQueue.getUpdateRequest();
        ...
        coordinator.updateMonitor(id); // 更新等待，由协作器完成
        // 设置更新后状态
        // 清除子队列无法处理的乘客请求
        Person unablePerson = subQueue.getUnableRequest(isA, isB, transferFloor);
        while (unablePerson != null) {
            mainQueue.addPersonRequest(unablePerson);
            unablePerson = subQueue.getUnableRequest(isA, isB, transferFloor);
        }
        subQueue.setUpdateRequest(null);
        if (isA) { mainQueue.subUpdateCount(); }
    }
}

三、调度器设计与调度策略

调度器设计与线程交互

hw5
  • 调度器设计：在 hw5 中，调度器的主要功能是将乘客请求从主队列分配到对应的电梯子队列。调度策略非常简单，直接根据乘客请求中指定的电梯序号进行分配。
  • 线程交互：通过主队列与输入线程交互，通过子队列与对应电梯线程交互。调度器从主队列中取出乘客请求，并根据乘客的电梯序号将其放入对应的电梯子队列。
hw6
  • 调度器设计：在 hw6 中，调度器的功能得到了扩展。调度器不再依赖乘客请求中指定的电梯序号，而是根据所有电梯的当前状态（通过影子电梯获取）计算所有电梯线程运送这名乘客花费的时间，从而找到理论时间最短的电梯。临时调度请求则越过调度器，直接发送给电梯线程，以减少调度延迟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ShadowElevator.java
public synchronized int getEstimatePerformance(Person person) {
    int pf = person.getFromInt(); // 乘客起始楼层
    int pd = person.getToInt();   // 乘客目的楼层
    
    double reversalDelay = 0.0;
    // 判断是否需要反转：电梯正行驶且乘客楼层方向与当前方向相反
    if (direction != 0 && (pf - currentFloor) * direction < 0) {
        // 计算反转延迟
    }
    double loadPenalty = 0.0; 
    // 计算载客数延迟
    double travelTime;
    if (scheduleReq != null) {
        // 计算临时调度时间延迟+正常时间延迟
    } else {
        // 计算正常时间延迟
    }
    double totalTime = travelTime + reversalDelay + loadPenalty;
    return (int)(totalTime * 1000);
}
  • 线程交互：基本无更多变化。输入线程直接发送临时调度请求给电梯线程，电梯线程会在运行过程中会更新影子电梯的状态，供调度器参考。
hw7
  • 调度器设计：在 hw7 中，调度器的设计进一步扩展以支持双轿厢电梯。调度器需要考虑双轿厢电梯的换乘楼层限制，并合理分配乘客请求。调度器继续使用影子电梯类来模拟电梯的当前状态，并在调度决策中考虑双轿厢的运行规则。调度器与协作器协作，确保双轿厢电梯的安全运行。
  • 线程交互：只考虑新增部分。输入线程直接发送临时调度请求和双轿厢更新请求给电梯线程。双轿厢电梯线程在遇到更新请求或是进出换乘楼层时通过协作器协作。

调度策略分析

hw5 调度策略

在 hw5 中，由于乘客请求指定电梯序号，调度器只需将乘客请求转发至对应的电梯子队列，性能的提升的关键点在于电梯运行策略与乘客优先级的结合。我使用LOOK运行策略，在开关门时允许电梯优先处理优先级高的乘客请求，并进行优先级替换，再加上一点点量子电梯，在强测中拿到了96.66分。

电梯在轿厢较空时，也可以携带反方向的乘客，省下一次开关门的时间。

hw6 调度策略

hw6 采用估算电梯最短送达时间，为每个乘客请求选择理论上完成时间最短的电梯，乘客若在电梯到达时无法进入电梯，则重新分配，再加上LOOK + ALS策略结合了乘客的请求优先级，能够有效减少乘客平均等待时间TWT_W，而代价是电梯的耗电量增加。在互测时查看评测机随机生成的测试数据，我的调度策略在高并发请求下，性能会优于传统的影子电梯以及随机分配等策略，强测96.79分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// SubQueue.java
public synchronized Person getPrimaryRequest() {
    if (persons.isEmpty()) {
        return null;
    }
    Person selected = null;
    double maxScore = Double.NEGATIVE_INFINITY;
    long currentTime = System.currentTimeMillis();
    for (Person p : persons) {
        double waitingSeconds = (currentTime - p.getTimeStamp()) / 1000.0;
        double compositeScore = p.getPriority() * waitingSeconds;
        if (compositeScore > maxScore) {
            maxScore = compositeScore;
            selected = p;
        }
    }
    return selected;
}
hw7 调度策略

hw7 的调度策略在 hw6 的基础上增加了对双轿厢电梯的支持。调度器不仅要考虑单个电梯的运行效率，还需确保双轿厢电梯的协作安全与高效运行。通过影子电梯的状态，调度器可以识别双轿厢电梯的特殊运行规则，并合理分配乘客请求。对于双轿厢电梯跨区域乘客，增加等待时间延迟。但对于我的架构，乘客到达换乘楼层后，是有可能选择其他电梯乘坐的，因此时间计算是不够精准的。这带来了更多优化空间，但受限于时间和精力，我没有进一步优化。不过最后强测分数甚至还比上次高不少(都快赶上影子电梯了？)

1
2
3
4
5
6
7
8
9
10
public synchronized int getEstimatePerformance(Person person) {
    ...
    double transferDelay = 0.0;
    if (isA) {
        ...
    } else if (isB) {
        ...
    }
    double totalTime = travelTime + reversalDelay + loadPenalty + transferDelay;
}

四、Bug分析与debug

本单元强测和互测均未出现 Bug (我们宿舍开发的评测机功不可没！)，但在写代码和本地跑评测机的过程中还是发现了一些问题。

  • ConcurrentModificationException in visit subQueue：hw5的这个bug与我的封装和层次化设计问题有关，SubQueue类中使用了ArrayList来存储乘客请求，Elevator类直接get出来遍历时，如果有其他线程对其进行修改，就会抛出迭代器遍历异常。解决方法是对于电梯线程中遍历的代码块加锁，但更应该是由SubQueue类用sychronized修饰的方法遍历子队列中的ArrayList，返回操作结果。所以我在随后的作业中都规避了这种做法。
1
2
3
4
5
6
7
synchronized (subQueue) { // 加锁
    for (Person person : subQueue.getPersons()) {
        if (person.getFromInt() == currentFloor && person.getDirection() == direction) {
        ...
        }
    }
}
  • do not OVER after SCHE/UPDATE and sleep in wait：我在hw6和hw7中都出现了这个问题(屡教不改)，都是因为电梯运行时策略类返回 WAIT 建议和电梯线程执行 WAIT 操作不是一个原子操作，导致子队列会在电梯线程拿到WAIT建议 到进入 WAIT状态 的时间段之间改变状态并notifyAll()，电梯线程进入WAIT状态后一睡不醒了。解决办法只需要在synchronized块中加上对于subQueue状态的判断。
1
2
3
4
5
6
7
8
9
10
// Elevator.java
private void waitRequest() {
    ...
    synchronized (subQueue) {
        if (subQueue.isEnd()) { return; } // 如果请求队列已结束，则不再等待
        if (!subQueue.isEmpty()) { return; } // 如果请求队列不为空，则不再等待
        try { subQueue.wait(); } 
        catch (InterruptedException e) { Thread.currentThread().interrupt(); } // 调用等待方法，使当前线程挂起
    }
}
  • 互测中发现的bug：第五次作业互测中用一条高并发和长时间运行的测试用例hack到一个TLE；第六次作业互测未发现bug；第七次作业互测中发现一位同学的SCHE/UPDATE请求完成超时，另一位同学电梯对于UPDATE请求与多个乘客请求同时到达时无法将乘客送达的问题，还有一位同学发生了电梯相撞的问题。

    有个经典的围师必阙bug是让5部电梯临时调度，同时涌入很多乘客请求，导致唯一未被调度的电梯接受大量请求，导致TLE。在第六次作业中测设置了这样的样例，使得大家都用缓冲区或是正常分配的方式规避了这一问题。而我的架构中乘客是可以重新选择电梯的，因而不会TLE。

对于多线程debug，无法用IDE的调试模式，只能用print大法打印状态，抽丝剥缕找出问题。此外，多线程的随机性和不可预知性使得一些问题难以复现，调试起来非常麻烦。感谢室友评测机的本地重复测试功能（把自己的jar包复制10份放在评测机上并发运行，能快速复现bug、降低随机性）。

五、心得体会

线程安全与同步机制

在多线程电梯系统的设计中，线程安全的核心在于 合理使用同步块与锁机制。我通过封装共享资源（如主队列、子队列），并对其访问方法添加synchronized关键字，确保 同一时刻仅有一个线程 操作共享数据，避免了数据竞争。代码逻辑操作保持原子性也十分重要。例如，在电梯线程等待子队列请求时，需在synchronized块内检查子队列状态，避免因状态判断与等待操作分离导致的“一睡不醒”问题。此外，结合wait()/notifyAll()实现线程间协作，确保了状态更新的正确性与及时性。总之，无脑加synchronized和notifyAll不可取，请在理解自己写的代码基础上使用同步互斥机制。

层次化设计与模块化思维

在架构设计上，系统高内聚低耦合是我们层次化与模块化设计的目标。生产者-消费者模型 的引入将输入线程、调度器、电梯线程解耦：输入线程仅负责生产请求，调度器专注于分配策略，电梯线程独立运行策略，三者通过主队列和子队列通信，职责清晰。影子电梯（ShadowElevator）模块 封装了电梯状态的模拟逻辑，供调度器独立计算最优分配，而协作器（Coordinator）模块 专注于双轿厢的同步与冲突避免。这种分层设计使得新增功能（如临时调度、双轿厢）只需扩展特定模块，无需全局重构。同时，策略模式（NewStrategy） 将电梯运行逻辑与调度逻辑分离，提升了代码复用性。良好的层次划分不仅能降低开发复杂度，还能显著增强系统的可维护性与扩展性。使得迭代过程中修改的代码量大幅减少，且更不容易出现bug。

OO第二单元完结撒花！这次的总结博客似乎写的有点太长了（笑），上次参加吴际老师的office hour，说到引入多线程训练作为面向对象设计的一个单元，虽然多线程不属于面向对象的三大特征（继承、封装、多态），但多线程的引入使得面向对象设计从还是稍微 “面向过程” 的单线程转变为 “面向并发、面向系统” 的多线程（这句话是我自己编的），程序更加复杂，但同时也更加灵活，更加符合现代计算机系统的需求。