关于面向对象多线程电梯那些事

写在前面：经历面向对象第二单元作业的这三周后，我对于多线程电梯的评价是很好的。这次作业给了我们机会去尝试多线程编程，能实际面临并解决多线程的资源竞争和线程安全问题。对我个人来说，我体会了多线程的复杂与神奇所在，在写每一个独立线程时需要时刻保持警惕，要把其它线程想象为一个陌生的程序员，保护自己的工作逻辑不受其它线程的破坏。

Unit2三次作业感受

个人感觉其实第一次作业是最难的，是因为第一次面临多线程设计是最不熟悉的，好在practice3给了我很大的启发和帮助。而第二次和第三次作业则相对简单了很多（不写影子电梯的话）。

多线程协作与锁的选择

第一次作业

第一次作业需要设计三种线程，分别是InputHandler（输入处理），Dispatcher（请求分派）和elevator（电梯）；两类共享资源RequestTable（请求总表）和WaitTable（电梯等待队列）。这三种线程两种共享资源构成了两对生产者消费者模型。

InputHandler线程的逻辑非常简单，就是利用官方包从stdin读入数据并解析请求类型，第一次作业只有PersonRequest，所以InputHandler就只需考虑将请求信息封装为一个对象Person（方便后续电梯中途下人并重新分配电梯），然后作为生产者将Person投喂给RequestTable即可。

RequestTable作为共享资源，所要面临的是InputHandler的写入和Dispatcher的读出。对于InputHandler提供offer()方法，对Dispatcher提供poll()方法，同时设置一系列RequestTable的状态查询方法（如是否结束或者是否为空，以便所有请求都处理后线程都能正常结束）。荣老师在课上说对对象的方法上synchronized修饰上锁是不合适的，究其原因在于要最小化一个原子操作（待会解释什么是一个原子操作）。但是考虑到RequestTable方法本身非常简单，给方法修饰synchronized反而可能更安全。
对于共享资源的保护，我们提及了synchronized修饰符和原子操作这个概念，所谓原子操作，通俗一点的解释就是某一个线程的操作是不可被其它线程插入并修改共享资源从而改变运行逻辑的操作就是一个原子操作，就像原子是物质的基本组成粒子，不可再分（化学层面 :））。理解了原子性这个概念后，我们对于线程安全问题就能更上一层楼了。

Dispatcher设计或许在这一次作业里没那么重要，但是其存在为后续的非指派的分派算法设计提供了空间。当RequestTable非空时，Dispatcher从总表poll()一个请求，并按照设定的算法分派给对应电梯的WaitTable即可。为避免轮询白白占用cpu资源，我们需要让Dispatcher在RequestTable在为空但是未结束时“睡一会”，这里的“睡一会”并非真的睡觉（sleep），而是调用RequestTable.wait()进入RequestTable的等待队列。
这里又会涉及到一个新的概念：wait-notify。Dispatcher会先判断RequestTable的状态并决定是否进入RequestTable的等待队列，这里有两个点需要注意：

1. Dispatcher需要分别查询RequestTable是否为空和是否结束，虽说是两次查询，但我们需要将这次行为作为一次原子操作，不然在第一次和第二次查询之间很有可能有其它线程抢走RequestTable的锁并改变了RequestTable的状态导致Dispatcher的逻辑错误。
2. 为了避免死锁，我们需要在每一次改变共享对象的状态后调用notifyAll()将所有的处于共享对象的等待队列的线程唤醒，但是这个唤醒是无条件的，所以可能存在“假醒”的存在。所以我们需要将wait块包装在while(true)块内，唤醒后再一次查询资源状态，只有满足条件才会真的被唤醒。

WaitTable同样作为共享资源，其所设计的逻辑和RequestTable是大差不差的，要为Dispatcher提供offer()方法，要为电梯提供poll()方法，内部维护的是分派给对应电梯的Person。

Elevator作为另一个消费者，其逻辑是根据WaitTable的状态和自身的决策算法，不断选择一定的运动，如移动，载人，放人，等待和结束。

第一次作业到此就结束了，虽然理清逻辑后觉得很简单，但是多线程编程设计时每写一句可能就需要考虑会不会造成线程冲突和不安全问题，会不会造成死锁问题。

第二次作业与第三次作业

第二次作业主要的改动有：

1. 不再提前指定请求分派的电梯，需要Dispatcher通过设计dispatch算法为请求分派请求。
2. 新增SCHE特殊调度，并且这个调度的优先级很高，需要让电梯尽快的响应。

这一次作业我觉得有几点设计是值得说一说的：

1. 将电梯属性和动作全部转至WaitTable维护，电梯本身抽象为一个纯粹的线程，只是不断的调用WaitTable的状态转移函数；电梯属性和电梯动作抽象为WaitTable的数据和属性改变和查询的方法。这么做虽然会大大增加WaitTable的复杂度，但是为外部设计带来了很多便利：
   • Dispatcher设计dispatch算法时避免不了需要同时掌握等待队列和电梯的信息，然后决定分派给谁，当把电梯的属性转至WaitTable统一维护时，Dispatcher就只需要和WaitTable进行交互，同时也能提高电梯数性的安全性，避免了对于电梯属性的数据冲突。
2. “围师必阙”：这一点设计我其实参考的是讨论区里助教的设计，注意到当电梯进入特殊调度状态时，就不能receive请求了，那如果某段时间只有一个电梯可用，同时这段时间来了大量的请求，如果分派算法设计的不好的话很有可能会把所有的请求都分派给“劳模电梯”，导致运行时间大大增加。那我们怎么解决这个问题呢，我们可以采用缓冲机制（Buffer），讨论区的助教可能是为了设计影子电梯分派算法而设计的这个机制，但是我发现其适用性非常广，于是便吸收进来化为己用。所谓缓冲机制，就是在WaitTable里设置另外一个容器，当Dispatcher决定将某一个请求分派给某一个电梯时，而此时电梯处于特殊调度状态，我们不直接把这个请求“分”给这个电梯，而是把这个请求放进这个特殊的容器，当电梯结束特殊调度状态时自动的把这个容器全部正式接收。
3. 引入单例模式和多例模式。注意到在设计的过程中，经常需要访问其它对象，在这次作业里频次格外的高，但是把对象作为一个方法的参数传入的话实在不美观，于是我引入了单例模式和工厂模式。注意到RequestTable有且只有一个，电梯和与其对应的WaitTable存在6个。所以我把RequestTable设计为单例模式，把电梯和WaitTable设计为多例模式。其在程序创立之初就已经被静态的创建和存储在对应的Factory里，所以在需要访问某一个对象时就只需要向对应的静态Factory里请求即可。

这里作业还有一个关于原子操作方面的点值得注意，与第一次作业不同的是，RequestTable还有可能会接受来自电梯的在分派请求，所以RequestTable是否结束的标准改为是否所有的请求都已经完成了，所以电梯在获得等待建议和执行wait进入WaitTable的等待队列的过程中需要保持为一个原子操作，否则，当最后一个电梯完成最后一个请求时，倘若Dispatcher线程插入，为WaitTable设为结束，但是当电梯重新拿回WaitTable的锁时，仍然会调用wait而不是结束线程，这时这个线程就会自此长睡不起了。

第三次作业主要的改动有：

1. 新增双轿厢电梯，对应UPDATE请求。

这次作业有两类设计是值得一说的：

1. 首先是线程同步机制，需要在UPDATE-begin和UPDATE-end进行两次同步，我采用了多例模式和CyclicBarrier结合的形式。我为每一对电梯都创建了实例化了一个CyclicBarrier，并存储在BarrierFactory里，在update的过程中，两个电梯通过同一个CyclicBarrier来进行同步。
2. 关于双轿厢的设计，我自认为我的设计是比较简洁的。首先是结束UPDATE-end后，我不改变线程数量，仍然认为电梯处于自己的电梯井中，只是限制了其最高楼层和最低楼层，然后对于共享楼层的访问，设立了一个新的类SharedFloor，当电梯需要进入该楼层时，会向SharedFloor申请；当离开楼层时会“释放”该共享楼层的所有。同时要静止电梯在共享楼层等待从而长久的占用共享楼层。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   public class SharedFloor { private boolean isOccupied = false; // 标记是否被占用 public synchronized void acquire() throws InterruptedException { while (isOccupied) { // 如果已被占用，线程进入等待状态 wait(); } isOccupied = true; } public synchronized void release() { isOccupied = false; notifyAll(); // 唤醒所有等待的线程 } }

调度器设计

电梯调度

关于电梯的运作算法主要可能有ALS、SCAN、LOOK等，其实我个人在SCAN与LOOK中纠结了一下，但是鉴于往年学长统一的选择LOOK算法，我想这肯定是有道理的，便下定决心选择实现LOOK算法。

下面简单介绍一下LOOK算法：

• 假定电梯处于某一层，且有一个特定的方向。
• 首先判断是否需要开门
  • 有人需要在该楼层下电梯
  • 有人需要在该楼层进电梯
• 然后判断电梯内部是否为空
  • 若不为空则往当前方向前进一步
  • 再判断电梯是否有请求
    • 若电梯前方有请求则往当前运作方向前进一步
    • 若电梯前方无请求则转向
    • 若无请求则电梯进入睡眠状态

所以getAdvice需要访问WaitTable维护的属性来确定电梯的下一步运作，所以在最外层套上对waitTable的synchronized块，实现代码大致如下：

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

private Advice getAdvice() throws InterruptedException {
        synchronized (this) {
            if (sche != null) {
                return Advice.SCHE;
            }
            if (update != null) {
                return Advice.UPDATE;
            }

            if ((beRequested(floor, direction) && inside.size() < space) || canOut()) {
                return Advice.OPEN;
            } else if (!inside.isEmpty()) {
                return Advice.MOVE;
            } else {
                if (isEmpty()) {
                    if (isEnd()) {
                        return Advice.END; //如果输入结束，电梯线程结束
                    } else {
                        if (sharing && floor == transfer) {
                            if (floor == top) {
                                if (direction > 0) {
                                    return Advice.REVERSE;
                                } else {
                                    return Advice.MOVE;
                                }
                            } else if (floor == base) {
                                if (direction < 0) {
                                    return Advice.REVERSE;
                                } else {
                                    return Advice.MOVE;
                                }
                            }
                        }
                        this.wait();
                        return Advice.WAIT; //如果输入未结束，电梯线程等待
                    }
                } else {
                    if (requestFront(floor, direction)) {
                        return Advice.MOVE; //如果有请求发出地在电梯“前方”，则当前方向移动一层
                    } else {
                        return Advice.REVERSE; //电梯转向,不移动
                    }
                }
            }
        }
    }

Dispatcher分派策略

早已在刚进入计算机学院之处就听闻了影子电梯的大名，但是影子电梯需要同时获得六把锁，实现起来具有很大的风险，遂放弃，转而实现了随机分派策略。

随机分牌策略就是每一次分派时等可能的获得所想分派的电梯的id，然后仅需获得该电梯对应的WaitTable即可。但是在第二次和第三次作业中，电梯有可能处于特殊状态导致不能被分派，此时我们如果把所有请求分给空闲的电梯很有可能导致运行时间过长，为了解决这个问题让随机分派策略依然能进行下去，我设计了一种缓冲机制。

所谓缓冲机制，就是在电梯处于特殊状态时，不立即让这个电梯receive，而是存储在WaitTable的Buffer内，当电梯结束特殊状态后将Buffer清空并全部正式存储。

1
2
3
4
5
6
7
8
9
10
11
12

public synchronized void addBuffer(Person person) {
     buffer.add(person);
 }
 
synchronized (this) {
        upDating = false;
        update = null;
        for (Person person : buffer) {
            offer(person);
        }
        buffer = new ArrayList<>();
}

DeBug方法

评测机的搭建

出于前几次作业没有做好评测而导致强测爆炸的惨痛经历，我在这单元充分的请教了D老师和G老师，将题目的指导书作为prompt，同时加入自己对于评测机的设计的思路，最终设计出了一个自动随机测试程序，遂用在了互测上，自动化评测房间里的同学，当出问题时就将对应的stdin和stdout信息保存下来，方便后续hack。

输出日志

光有评测机是远远不够的，处于多线程的随机性和无法调试性，我们很难直接从一般的输入输出信息发现自己程序的bug。受评论区大佬的启发，我单独开了一个DeBug类，如下：

1
2
3
4
5

public class DeBug {
    public static boolean d() {
        return true;
    }
}

然后在程序中每个关键节点输出日志信息：

1
2
3

if (DeBug.d()) {
     System.out.println("[Log] + 相关信息"))
}

通过观察日志信息，就让我发现了我在上文提到的最后一个电梯无法结束的bug，我发现日志没有所有电梯的end信息，便迅速察觉到了这个bug并立即做了修复。

日后谈

在三次作业中，我逐渐加深了对线程安全的理解和实践：

• 理解原子操作与synchronized的使用场景：起初通过简单地给方法加 synchronized 来实现互斥，后来意识到应该精细控制锁的粒度，只在必要的代码块加锁，避免造成性能浪费。
• 掌握了wait-notify机制：在生产者消费者模型中，用 wait() 和 notifyAll() 控制线程的唤醒与阻塞，尤其注意了在循环中使用 wait 防止“假唤醒”问题。
• 避免死锁与线程长时间阻塞：在设计过程中不断检查线程可能卡死的点，像是线程 wait 后永远不被唤醒、或者电梯“长睡不起”等，尽量做到每一个线程都能有序启动与结束。
• 共享资源访问保护：每次访问共享数据结构如请求队列、缓冲区等都考虑到了线程竞争，并通过锁机制保证数据一致性。

随着作业难度的提升，我也逐步建立起了模块化和分层的编程习惯：

• 将电梯与调度逻辑解耦：电梯线程只负责执行动作，调度决策交给外部管理，使逻辑更清晰，便于扩展。
• 引入工厂模式和单例模式：将一些全局对象（如请求表）做成单例，把多个电梯或资源用工厂统一管理，避免重复创建，提高代码可维护性。
• 采用缓冲机制与共享区抽象：例如在 UPDATE 和 SCHE 等特殊状态下加入缓冲队列，保证调度器分派灵活不冲突；设计 SharedFloor 类集中管理共享楼层的进入与退出，简化了双轿厢访问控制。
• 输出日志与自测工具：为每一个模块加上日志输出、设计评测机进行压力测试，帮助在复杂的多线程环境中快速定位问题。