Unit2电梯调度

​ 不知从什么时候开始，电梯就成为了四月的冠名词，好像潋滟春光与我们无关。

​ 请你相信，计算机学院的大多数压力来自于学长的过度宣传。

​ 笑着迎接这个有趣的单元吧，然后去享受人间的四月天。

第一次作业

你好，多线程

​ 多线程并不是面向对象语言的专利，我们之所以在OO课程中学习多线程，是因为Java作为高级语言，在多线程的封装上表现得很好。有关多线程的知识在OS课程中会重点讲述，但是显然我们在接触电梯的时候，它还没有正式露面。为了更好的了解多线程，我在这里补充一下相关知识。

​ 多线程的原型是多进程，而多进程是分时操作系统的核心机制之一，它的作用是保证各个进程（执行中的程序的代称）能够交替运行，也就是我们所说的并发性（在OO课程中我们不去分辨多线程与多进程的区别，在这篇文章里你可以把它们当作同一个东西），并发性的好处属实不少：一来是保证了程序的及时响应，其次是提升了CPU的工作效率。

​ 举个例子，如果我们的电脑只能顺序执行进程，那么你必须要等你的游戏打完才收到微信信息，而那条信息是室友通知你老师在点名，或者crush着急请你帮忙——那你基本上要找我买后悔药了（你完全可以这么做，因为我虽然没有后悔药卖，但是确实可以嘲笑你一阵）。不过好在我们的系统早就拥有了多进程的功能，在执行游戏程序的时候也能接受微信通知。

​ 上面那个例子是“及时响应”的体现，在我们的电梯程序里也有体现——在电梯运行的过程中调度器可以及时分配新的任务，保证了新任务的及时相应。至于提升效率其实也很好理解，如果一台电梯正在运动到另一层（通常耗时400ms），我们的程序就可以在这个期间去处理其它电梯的请求，或者去调度分配新乘客，极大地节省了时间。

​ 大部分操作系统实现多进程依靠的是信号量，这是个强大的工具，原始却高效，唯一的问题是它太过复杂，各种嵌套的PV操作让人头晕目眩，而且还很容易引发线程安全问题。所以人们开发了管程，它作为信号量的高度封装，简化了许多信号量操作，Java作为一种实现了管程的高级语言，自然是我们学习多线程的不二选择。

​ 多线程涉及很多专业术语，在课程中你很有可能产生不少疑问。我建议大家通过AI进行复习与回顾，关键词如下：Thread类和Runable接口，线程的启动（start），线程的暂停（sleep），线程的互斥（synchronized），线程的协作（wait与notifyAll），状态的转移。

​ 利用这些知识就可以顺利通关本单元了，骗你我周四吃KFC。

你好，分解者

​ 为什么我会提到分解者呢？因为我们的本单元要用到的模型是“生产者——消费者”模型，为了不让分解者受到排挤，我选择让它作为标题，然后，它就可以滚了。

​ 生产者——消费者模型是多线程的重要模型之一，顾名思义，它由生产者线程和消费者线程组成，除此之外还有数据和通道。

​ 在本单元中，他们的角色由以下类扮演：

  • Producer：生产者，如InputThread、Dispatcher
  • Consumer：消费者，如Dispatcher、Elevator
  • Channel：通道，如RequestQueue、WaitQueue
  • Data：数据，如PersonRequest等

​ 总的来说，由InputThread从输入里面提取各种信息，把它们封装成对应的请求放在RequestQueue这个总表里面，然后由Dispatcher提取请求分配给各个电梯，存放在WaitQueue里面，电梯则执行被分配的请求。如果你无法理解这个模型的运作方式，不用着急，等到实验课结束，一些都会迎刃而解。

​ 了解到这里，你完全可以实现第一次作业了。不用怀疑，就是这么简单。不过我得提醒一句，简单意味着大家的分都很高，性能分稍微差一点就会掉到B房，但这又有什么关系呢？别为了卷性能分走火入魔了。

第二次作业

​ 本次迭代引入了临时调度请求，并且让我们全权掌控调度器的工作，这一点也不难，反正比起第一单元的首次迭代，我感觉电梯单元非常仁慈。

​ 考虑到临时调度请求没什么困难，除了接客之后的开门次数，似乎也没有什么可以优化的点，这里留给大家自己探索。我们将重点放在电梯调度上。

暗影君王

​ 有关调度方法的选择众说纷纭，随机分配、启发式打分、影子电梯、自由竞争都可以完成本单元的任务，并不会有某个方法会引发TLE，如果有，那一定是考虑不到位，这一点我会在后面提及。

​ 在所有调度方法中，脱颖而出的是影子电梯。它会获取六部电梯的快照，然后用影子电梯来模拟新乘客进入电梯后的表现，最终计算出将新乘客带到目标楼层所需要的时间，将其当作打分依据选择分配目标。实现的方式非常简单，把电梯相关的类复制粘贴一遍就行了，你甚至可以删减一部分内容，因为在影子电梯里，不会再有其它新乘客了。当然，你必须把sleep(400)改为time += 400。

​ 遗憾的是，影子电梯之间亦有差距，其关键在于快照中的参数。除了电梯当前楼层、电梯运行方向、内部乘客列表和外部等候乘客列表之外，我们还要考虑一个关键点——电梯的运动状态。本人的电梯在move之后才会改变楼层号，这导致调度器误以为电梯正在等候，就把那一楼层的乘客分配了出去，但是实际上，电梯已经离开了当前楼层并且很长时间内难以掉头了。为了解决整个问题，我们可以为电梯快照添加isMoving关键字和remainTime值——用来记录电梯还要运行多久才能抵达下一层。如果还是觉得太麻烦了，你甚至可以在move的一开始就修改floor的值，我想这应该没什么问题。

​ 在进行影子电梯打分之前，我们其实要需要一层筛选，比如要剔除那些已经进入临时调度期的电梯，根据题意他们是无法receive新乘客的。除此之外，我还剔除了那些已经有大量乘客的电梯，避免一辆电梯receive过多的乘客。为什么这么做呢？因为有人会这么hack你，真不知道是谁这么阴毒，诅咒他大学找得到对象。

[49.0]MAINT-1-2001-F2
[49.0]MAINT-2-2002-F2
[49.0]MAINT-3-2003-F2
[49.0]MAINT-4-2004-F2
[49.0]MAINT-5-2005-F2
[50.0]1-WEI-100-FROM-F7-TO-B4
[50.0]2-WEI-100-FROM-F7-TO-B4
[50.0]3-WEI-100-FROM-F7-TO-B4
[50.0]4-WEI-100-FROM-F7-TO-B4
[50.0]5-WEI-100-FROM-F7-TO-B4
[50.0]6-WEI-100-FROM-F7-TO-B4
[50.0]7-WEI-100-FROM-F7-TO-B4
[50.0]8-WEI-100-FROM-F7-TO-B4
[50.0]9-WEI-100-FROM-F7-TO-B4
[50.0]10-WEI-100-FROM-F7-TO-B4
...
[50.0]59-WEI-100-FROM-F7-TO-B4

​ 但是这样的“剔除”就会引发一个新的问题——如果六部电梯都被临时调度了，那么我们的调度器将无事可做，一种方法是轮询——这似乎不会TLE，我看学长的“优秀”代码里面有这么一段。其次就是让调度器在总表里面等待(wait)，等到电梯临时调度结束notifyAll一声（实际上不仅仅是电梯会notifyAll，具体细节自己想），再重新工作。

​ 但是这样的“等待”就会引发一个新的问题——如果某部电梯在打分后和执行wait之间突然完成了临时调度，那么notifyAll就会被忽略，为此我们可以引入一个版本号，在每次notifyAll之后就改变版本号，并在wait之前判断当前版本号是否和打分之前的相同，如果不同，就重新打分调度。

public synchronized void waitDispatch(int oldVersion) {
        while (dispatchVersion == oldVersion) {
            if (!maintRequests.isEmpty()
                    || !updateRequests.isEmpty()
                    || !recycleRequests.isEmpty()) {
                return;
            }
            try {
                wait();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }

​ 以上是第二次迭代的全部内容，我感觉写的有点少，但是确实没什么好分享的了，大家加油！

第三次作业

​ 第三次作业引入了双轿升级，在我看来这是三次作业中最困难的一部分。但是只要我们正确的处理了双轿系统，一切困难将迎刃而解。

金屋藏轿

​ 为了实现双轿升级，当务之急是拥有双轿，实际上我们一共有三种电梯——主电梯、副电梯和普通电梯，与其生产三种不同的电梯线程类，不如更换电梯的大脑（也就是Strategy类，相信你在指导书的建议下写了这个类）。这种更换大脑的方法就是“策略模式”。在写新的策略类时，我们需要考虑换乘这种情况，也就是某些乘客的出发楼层在F2以上，但是目的地在F2以下；同时还要考虑防装机制，我在此选择让主副电梯无脑地逃离F2层，为另一部电梯让开空间。

​ 一旦你已经准备好了三个大脑，我们就可以进行下一步了——管理双轿电梯。回忆一下我们第二次作业中地调度类，它可以直接给电梯分配任务，直接获取电梯的快照而不需要什么额外的判断，为了达到“高内聚，低耦合”的目标，我们需要新增一个管理器来管理主副电梯，它向调度类暴露相同的接口，把一切逻辑判断交给自己。这就是我们新增的Shaft类。也就是说，我们的Shaft类会根据乘客的出发层与目的层划分责任，把请求分配给主副电梯。Shaft类的属性如下：

private final int shaftId;
//主电梯
private Elevator mainElevator;
private final WaitQueue mainQueue;
private final ElevatorTable mainTable;
//副电梯
private Elevator spareElevator;
private final ElevatorTable spareTable;
private final WaitQueue spareQueue;
//总表
private final RequestQueue globalRequestQueue;
//公共楼层
private final ReentrantLock transferLock = new ReentrantLock();
private final Condition transferCondition = transferLock.newCondition();
private boolean isOccupied = false;
//状态标志符
private boolean isNormal;
private boolean isMainting;
private boolean isUpdating;
private boolean isDouble;
private boolean isRecycling;

​ 那么问题来了，“公共楼层”和“状态标识符”是干什么吃的？这就涉及电梯仓的第二个作用——通信。在F2层的使用上，主副电梯需要通信，否则将会产生碰撞；在升级与回收的问题上，主副电梯同样需要通信，方便二者执行状态的转换。这其中最特殊的点，就是transferLock，我没有选择使用电梯仓本身作为锁，而是引入了显式锁ReentrantLock是为了将其它数据的写入读取与这个“耗时”的防撞机制放在一起，来提升效率。

危梯四伏

​ 虽然第二次作业的hack成功率很高，但大多数是因为没有考虑到上面提到过的“爆满”的情况。相比之下，第三次作业的错误倒是五花八门，我在此总结了几种常见错误：

​ 1、状态改变与输出存在窗口：请注意输出与状态改变的原子性，如果实在无法原子化，请仔细思考先后关系。比如请在输出了“Recycle end”之后再调整主电梯策略，否则很有可能你的主电梯会先一步闯入F1楼层；再比如请在输出“Arrive”之后再放开F2的锁，否则评测机会误认为你的主副电梯碰撞了。

​ 2、决策与动作存在窗口：请注意决策产生与动作执行之间的原子性，如果无法保证请加上防御措施。比如在电梯wait之前检查是否真的没有请求了。

public synchronized void waitForReq() {
        //等待更新
        while (isEmpty() && !isEnd) {
            try {
                wait(); // 释放当前的锁，进入等待池
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    public synchronized boolean isEmpty() {
        //是不是暂时没任务
        return waits.isEmpty() && maintRequest == null
                && updateRequest == null && recycleRequest == null;
    }

​ 3、电梯相应检修、升级、回收请求存在时间限制（如果你们还有的话），请不要盲目开门让乘客下电梯，频繁的开门与关门会导致电梯超时。为了解决这个问题，我们可以选择设置一个最大开门次数，3是一个比较靠谱的选择。如果你想知道自己的程序会不会出现这样的问题，下面这个数据点是个不错的测试样例。

[1.0]1-WEI-100-FROM-F1-TO-F7
[1.0]2-WEI-100-FROM-F1-TO-B4
[1.0]3-WEI-100-FROM-F1-TO-B4
[1.0]4-WEI-100-FROM-F1-TO-B4
[1.0]5-WEI-100-FROM-F1-TO-B4
[1.0]6-WEI-100-FROM-F1-TO-B4
[4.0]7-WEI-100-FROM-F7-TO-F6
[4.0]8-WEI-100-FROM-F7-TO-F5
[4.0]9-WEI-100-FROM-F7-TO-F4
[4.0]10-WEI-100-FROM-F7-TO-F3
[4.0]10-WEI-100-FROM-F7-TO-F2
[4.0]MAINT-1-100-F3

​ 无奖竞猜，设计出上面这种数据点的学长会面临什么惩罚？

​ 答案是开心一整天！哈哈哈哈。

日月无眠，人间又是一天