面向对象 第二单元总结

第二单元的任务是完成一个电梯调度系统，尽可能快的将所有人送到相应的目的地。主要考察了我们对于多线程程序的编写以及线程安全问题的理解。

第一次作业

总体架构

由于第一次作业的任务比较简单，所以我直接选择了生产者-消费者的架构。其中，我在输入线程与电梯线程中加入了调度器线程，因此属于两级生产者-消费者架构。在电梯的调度策略上，我选择了 LOOK 算法。

InputThred 作为一级生产者负责将输入请求放入一级托盘中；Schedule 作为调度器将一级托盘中的请求分配给二级托盘，也就是各电梯对应的托盘中；最后，再由各电梯从各自托盘中取出请求送至目标楼层。

两级托盘的架构思路比较清晰，将整个任务进行解耦，使得电梯只需要负责自己托盘内的请求即可。并且对于之后的作业，仅需要对调度器进行增量开发，不需要再对电梯的功能进行改动。

调度器设置

本次作业的调度器功能十分简单，仅需要与输入线程进行交互，从输入托盘中取出一个请求，判断请求是属于哪个楼座，并将其放入该楼座的托盘中即可。其实本次作业完全可以忽略掉调度器这一模块，直接由输入线程来进行分配请求的操作。但是考虑到后续作业的增量开发，所以还是设计了一个调度器的模块。这样也让电梯不需要关注到自身托盘以外的请求，只需要完成自己的任务。

同步块与锁的设计

由于是第一次接触多线程的内容，当时的我对于线程安全的理解还不是很深入，所以选择了上机训练的做法：即创建一个线程安全类 RequestQueue，它的锁是整个项目中唯一的锁，提供了增删查取的安全方法，以防止线程冲突的发生。事实证明，这样的设计相当简单，也为线程安全提供了有力的保障，因此我一直沿用到最后一次作业。

import java.util.ArrayList;

public class RequestQueue {
    private ArrayList<Person> requests;
    private boolean isEnd;

    public RequestQueue() {
        requests = new ArrayList<>();
        this.isEnd = false;
    }

    public synchronized void addRequest(Person request) {
    }

    public synchronized Person getTargetRequest(int target) {
    }

    public synchronized void setEnd(boolean isEnd) {
    }

    public synchronized boolean isEnd() {
    }

    public synchronized boolean isEmpty() {
    }

    public synchronized int size() {
    }

    public synchronized void remove(Person person) {
    }
}

其中， RequestQueue 的每一个方法都是线程安全的，而项目中唯一的共享对象只有 RequestQueue ，所以只要保证这个对象的所有方法都已上锁，整个项目就是线程安全的。

第二次作业

总体架构

这次作业的复杂程度陡增，增加了多部电梯、横向电梯，甚至还有动态增加电梯。因此，我在写代码前思索了一番，如果继续设置调度器来处理，各种规则判断都需要慎重考虑，甚至还可能变成了负优化。一不做二不休，既然写不出一个合理的调度器，那不如就扔掉它，让电梯自己去竞争请求。所以，我删掉了上次作业的调度器，采取了自由竞争的架构。

在删去调度器后，整个结构变得更加简单：我首先建立了两个 HashMap 来管理所有楼层的电梯和对应的共享队列，由输入线程判断输入的请求是电梯还是乘客并放入对应楼层的队列中。然后，剩下的工作就交给了这个楼层的所有的电梯，让他们去竞争这个楼层的所有请求。而对于横向的环形电梯，我单独为其设置了一个类来进行处理，采取的策略也类似于环形的 look 算法。

调度器设置

由于我采取了自由竞争的方法，所以没有设置调度器。但是从功能上来看，我的输入线程其实相当于一个伪调度器，它负责将输入直接分配到对应的楼层队列中。功能如此简单，也就不需要单独设置一个调度器了。所以输入线程仅需要与各电梯线程中的共享队列进行交互。

同步块与锁的设计

本次作业我沿用了上次设置的 RequestQueue 线程安全类。此外，由于在电梯接人时需要有遍历整个共享队列并取出元素的操作，所以我在 RequestQueue 中分别为纵向电梯和横向电梯加入了对应的线程安全方法。

import java.util.ArrayList;

public class RequestQueue {
      public synchronized Person getPersonH(char curBuilding) {
        Person res = null;
        for (Person p : requests) {
            if (p.getFromBuilding() == curBuilding) {
                res = p;
                requests.remove(p);
                break;
            }
        }
        notifyAll();
        return res;
    }

    public synchronized Person getPersonV(int curFloor) {
        Person res = null;
        for (Person p : requests) {
            if (p.getFromFloor() == curFloor) {
                res = p;
                requests.remove(p);
                break;
            }
        }
        notifyAll();
        return res;
    }
}

第三次作业

总体架构

最后一次作业在上一次自由竞争架构的基础上迭代其实相当容易，只需要将需要换乘的乘客在其完成一部分移动后放入下一个楼层队列中即可。但是有很多需要注意的细节以及优化的部分。

线程的协作时序图：

对于需要换乘的乘客，我先根据现有的横向电梯判断他应当前往哪一层，设置为他的中间目的地，并将其放入对应楼座的共享队列中。而我采用了动态更新的优化方法：在电梯每次运行时，会先更新电梯中所有乘客的目的地，这样就可以解决需要换乘的人在进入电梯后又新加入了距离更近的横向电梯的情况，从而避免了所用人都前往一层进行换乘而造成拥堵的情况。而在电梯将乘客送至目的地后，若乘客需要换乘，则将其放入下一个楼层的共享队列中，直到其到达最终目的地为止。

调度器设置

这次作业我同样没有设置调度器，而是将其职责分配给了输入线程和电梯线程。输入线程负责将请求放入共享队列中；电梯线程负责将请求从一个队列移至另一个队列中。

同步块与锁的设计

本次作业也沿用了上次作业的 RequestQueue 线程安全类。此外，这次作业中可能出现当某个请求队列为空且输入线程已关闭后时，由于还存在未到来的换乘请求，因此不能关闭对应的电梯线程。所以，我设置了一个线程安全类 Counter，用于记录进电梯与出电梯的总人数。当输入线程已关闭时，若进出电梯总人数相同，则说明所有乘客已到达目的地，此时才可以关闭电梯线程。同样，只需要保证该类是线程安全的即可。

public class Counter {
    private int numIn = 0;
    private int numOut = 0;

    public synchronized int getNumIn() {
        return numIn;
    }

    public synchronized void addNumIn() {
        this.numIn = this.numIn + 1;
    }

    public synchronized int getNumOut() {
        return numOut;
    }

    public synchronized void addNumOut() {
        this.numOut = this.numOut + 1;
    }

    public synchronized boolean isEmpty() {
        return this.numIn == this.numOut;
    }
}

Bug分析与测试

第一次作业由于对于官方输入包的盲目相信，所以没有使用线程安全的输出包，在互测中被人疯狂一顿 hack。这个 bug 修复起来也相当容易，只需要将官方包输出包装成一个线程安全类即可。而之后因为我使用了结构较为简单的自由竞争，加上唯一的线程安全类，几次强测互测都没有再发生线程安全的bug。只有在一次中测提交截止前我突然想起遍历共享队列的整个过程也应当保证是线程安全的，于是匆忙加上了这个方法。

这几次作业我都使用了自动评测机来生成数据并测试程序的正确性。事实证明，评测机可以发现一些自己代码里很愚蠢的bug，可以极大缩短肉眼 debug 的时间。

互测环节本着和平相处的原则，我并没有提交 hack。

心得体会

总算是完结了号称最折磨人的“电梯月”，回过头来想想，相比一个月前的自己，确实对于多线程、线程安全以及层次化设计等内容有了更深的理解。

何为线程安全？我认为线程安全的核心其实就是永远要保证同一时刻只有一个线程在访问某段同步块。而这个同步块的范围可大可小，取决于你的实现方式，也是效率与复杂程度的一个取舍。

而从层次化设计的角度出发，我先确定了整体的大结构为生产者-消费者模型，然后再按照电梯、队列、调度器逐个进行展开。每个模块只负责一部分的功能，践行单一职责的原则，同样也要保证模块的可扩展性，比如对于新增的换乘请求，只需要增加几行代码就实现了主要的功能。

因此，综合以上两点，我认为自由竞争应该是这个单元作业方案的一个最优解。因为没有一个调度器的分配策略可以是全局最优的，而使用调度器又不可避免的会加大架构的复杂性，并带来各种线程安全问题。所以，不如从根本上就抛弃掉调度器，转而拥抱更加简洁的自由竞争，一切交给电梯来决定。最重要的是，自由竞争的性能相当优秀：）

自由竞争，yyds！