OO第二单元总结

第五次作业

题面

先解释若干概念：

• 目的选层电梯系统：

  1.进入电梯前，乘客输入目标楼层(?没进电梯选楼层)；

  2.电梯系统根据策略指定电梯服务，并告知结果；

  3.乘客进入电梯后，无需再按楼层，电梯自动送其至相应楼层。

• 优先级指数：表示不同类型乘客到达目的楼层急迫程度。

• 请求调度器：解析读入请求信息后，根据此时电梯运行状态将乘客请求合理分配给某部电梯的调度器，可以理解成指挥电梯运作的大脑。

此外，被分配请求的电梯将经过上下行、开关门、乘客进出电梯等动作，将乘客从起点运送至终点，注意每到一层都需要打印到达的相应楼层的信息。

单部电梯运行策略与电梯系统的调度策略可任意指定，即任意时刻，电梯的操作都可自定义，只要保证在电梯系统运行时间不超过要求时间上限且将所有乘客送至目的地。

一些约束

• 电梯楼层为B4-B1,F1-F7，11层，初始在F1层；6部电梯，id为1-6；0.4s/层(需要体现在时间戳上，也就是当前一层Arrive后到下一层Arrive之间需要手动间隔0.4s，也就是让电梯线程sleep(400))；限载6人；开关门间隔大于等于0.4s。
• 一些电梯常识：电梯移动时必关门；初始关门，开门下才能关门，关门下才能开门；乘客在电梯内才可出电梯，在电梯外才可进电梯；系统结束时不可以有乘客请求未完成或乘客困在电梯里的情况出现
• 运行过程中乘客可以中途下电梯，结束时到达目的地即可。

性能要求

只要记住下列三条即可：

• 运行时间尽可能短
• 尽量满足乘客请求的优先级
• 尽量减少系统的无效运行

代码架构分析

在这次作业中主要需要考虑这样几个问题：

1. 如何将上课讲过的**”生产者-消费者”**很好的应用出来？
2. 如何进行同步块的设置和锁的选择？
3. 如何进行电梯调度？

接下来将逐点进行分析：

“生产者-消费者”的应用

在此次作业中，我设计了三种线程：输入、调度和电梯线程。在发现总请求表和分请求表在我的架构中的作用类似后，我用一个RequsetTable类来囊括请求表的作用。因而这里就有由总请求表和分请求表构建的两种**”生产者-消费者”模型，共7对“生产者-消费者”。RequestTable类中有两个属性，一个是存储相应队列中的人的动态数组，还有一个结束标志isEnd，用于结束相关的线程。InputThread类中只有请求表类，DispatchThread类中有请求表类和一个存储6对以电梯序号作为键、请求表类作为值的HashMap，用于分派请求。ElevatorThread直接将分请求表作为一个属性，利用其中的人和内置的Elevator类的人作出状态转换决策**。

大致运作的流程是：InputThread向总请求表中放入请求，在判断当前输入的请求为NULL时给总请求表置结束标志，然后其结束运行。DispatchThread从总请求表中获取请求，根据请求的电梯序号分配到相应的电梯的分请求表，当总请求表为空且结束标志为true时，其向所有分请求表置结束标志，然后其结束运行。ElevatorThread利用分请求表中的人和电梯中的人进行状态转换的决策，当分请求表为空且其已被置结束标志且电梯内没人了结束进程(当然要在上一个操作完成前)。

同步块的设置和锁的选择

主要关注被共享的属性即可，也就是总请求表和分请求表，而由于这两者都是脱胎于同一个RequestTable类，因此，只需要对一个类进行加锁处理即可，其中我将涉及到对于RequestTable类中的读写方法都进行了加锁处理，为了能够有效唤醒等待队列，我只在写方法中设置了notifyAll()。此外我采用的是synchronized加锁的方法，这种方式的好处在于其简单易懂，不易出错。

电梯调度

在阅览了学长/学姐的博客后，发现最贴合现实的LOOK算法最深得人心，因此我也随大流采用了这种方法，此外我还采用了量子电梯(这种奇技淫巧)以及虚拟电梯的方式来提高性能分。

简单介绍一下LOOK算法，脱胎于SCAN算法：

• 在给电梯规定一个初始方向后，电梯开始运动。

• 到达某层后，先判断是否开门

  • 若电梯有人到了，就开门
  • 若外面有人在这一层，且目的楼层方向同电梯方向相同，也开门，然后根据将外面的可以电梯的人同电梯里的人揉成一堆，如果没有超电梯载重便相安无事。否则将根据优先级排名，取高的放入电梯，剩下的只能含泪离场了。(虽然耗电量可能会有点难看，但是平均时间应该好吧（)

• 若不能开门，就看看电梯里有没有人。有的话，便继续沿原方向移动一层。否则，检查分请求表中是否还有请求：

  • 分请求表不为空：

    • 有请求的出发地在电梯”前方”(例如，如果电梯向上，就是出发层在电梯当前所在楼层上方；反之亦然)，那么便继续沿原方向移动。
    • 没有的话，那么电梯就反向调头。

  • 分请求表为空：

    电梯停在当前层等待可能的请求输入。

此外，由于我们的作业是输出导向，也就是只能依据输出来判断是否完成相应动作，例如：移动的时候需要sleep，不是因为电梯这个时间真的要移动，而是要贴合输出时间戳，造成电梯移动了的假象。基于此，量子电梯便孕育而生，简单来说，就是当电梯进入等待状态或者一开始的时候，其将处于可同时处于上一层和下一层任意地方之间量子态，至于到底处于哪一层或哪几层之间就取决于上一次观测和此次观测的时间间隔，也就是因为本来如果是当分请求由空变不空的瞬间为电梯运动的开始，那么说明此前的等待时间将白白浪费，也就是电梯真的在等待，但量子电梯是根据等待时间决定，电梯运动的时间，也就是如果等待时间大于电梯运动一层的时间，那么为什么不能让电梯在请求进入前的0.4s就开始移动，因为根据输出是无法预测电梯的开始运动状态的；反之，如果等待时间不够移动一层的话，那就移动多睡剩下的时间即可。你或许想说，只有请求来的时候电梯才知道往哪走，是这样，但是我们的电梯在量子态下是可以同时完成转向移动操作的。

由于，LOOK算法并未规定一开始的运动方向，按理来说，随便指定一个向上的影响应该也不大，毕竟转向只要比毫秒还小的数量级时间，但是我还是采用了一种模拟的方式，也就是虚拟电梯VirtualElevatorThread，其中包含了电梯线程的重要信息，通过重写移动、开关门等方法，实现对初始方向两种选择的模拟，并记录所需时间，主要考虑时间性能，进而选择当前最优的方向选择。

代码UML图

类图

协作图

强测bug

由于我采用了一个名叫lasttime的变量来存储上一次关门或移动的时间，进而用来判断一台电梯在等待之后再次接人时是否能够”提前”利用那等待的时间向发出请求乘客的方向移动一层，但是在初始化该变量，也就是刚开始进来人的时候确犯了蠢，我将lasttime想当然的置为了0，而后续获取是否需要手动sleep用的却都是系统时间(从1970年1月1日开始计算到获取的时候的时间，问就是纪念Uinx)，因此这样一来一开始无论如何都是可以在请求发出的那一刻就移动一层，但是如果第一批请求来的时间不足0.4s，那么电梯就移速过快了，属于是”聪明”反被”聪明”误了，因此挂了一个点。

第六次作业

新增内容

1. 取消“乘客请求指定电梯”约束，自行设计电梯分配策略，取消自由竞争。也就是调度器得忙起来了。
2. 新增“临时调度”(模拟现实的电梯维修场景)，新增”RECEIVE“约束(通过输出来反馈电梯分配情况)。
   • 临时调度针对某一电梯，要求其官方包自动输出SCHE-ACCEPT开始，到其输出SCHE-BEGIN-电梯ID之间只能有两条ARRIVE输出，也就是在ACCEPT与BEGIN之间电梯可以正常运行，但一旦输出了BEGIN，电梯就需要按照要求的运行速度运行到相应楼层进行临时调度，即在到达的楼层开关门1s，并将其中的人全部清到电梯之外，然后输出END来表示临时调度的结束，在规定ACCEPT与END之间输出的时间差不能多于6s，BEGIN与END之间电梯处于静默状态，不能RECEIVE、上乘客、到达目标楼层前不能开关门等。
   • RECEIVE约束，为了更好的判断清楚电梯调度的策略，增加了RECEIVE输出，证明该乘客只能由相应RECEIVE电梯接送，电梯只有在RECEIVE到乘客、或者电梯内有人、或者进入临时调度状态下(指输出BEEGIN后)才能开始移动，否则不允许移动(无形中搬掉了半个量子态电梯)，且一名乘客只能被一部电梯接收。也就是一名乘客最多只能属于一部电梯，那么什么时候他们才能背过手呢？1.临时调度中输出BEGIN后与这部电梯相关的乘客的所属关系都需要解绑。2.当乘客从电梯出去后立马解绑，如果到目的地了最好。否则就回总请求表再分配一次。

代码架构分析

第六次作业一下子相对于第五次作业难度上了一个等级，除了要求限制很多外，更重要的是不允许使用自由竞争，说明要是想要比较好的性能，调度器线程是需要知晓电梯的状态的，如此一来电梯线程就会变成共享资源，其自身也会进行访问，难道在锁难免了吗？此外，原来是只要总请求表为空了且输入停止了，调度器就会停止，但是这其实是基于后续的乘客并不会再被踢回总请求表中，此次作业由于临时调度的强制踢人，虽然也可以一股脑的踢回分请求表中，临时调度结束后再重新RECEIVE回来，但是这样难免会损失很多性能分，一旦围师必阙可能就不是性能分低的问题了，大有正确性出错的情况发生，那么也就是当所有电梯线程都应该结束的时候，调度器线程才能结束，但是调度器线程不结束，电梯线程何谈结束，经典鸡生蛋蛋生鸡问题？

因此此次作业主要需要去考虑的问题有如下几个：

1. 如何将**”生产者-消费者模式”**应用在此次作业中？
2. 如何解决调度器线程与电梯线程谁先结束耦合问题？
3. 如何设计好合理的调度算法，也就是怎么分配乘客给合理的电梯？
4. 如何进行同步块的设置和锁的选择？
5. 如何处理好临时调度？
6. 如何处理好RECEIVE?

“生产者-消费者”的再应用

增加一个AllElevators类来管理所有电梯，它和RequestTable都采用了单例模式，这样一来并不需要将它们作为相关线程的内部属性，只需要通过获取单例即可。

此外，调度器的结束标志还是由RequestTable给出，不过ProcessingTable可以对相应的属性进行修改。InputThread在收到临时调度请求时，立马通过获取单例的形式传给AllElevators类，由后者根据请求内容给相应的电梯线程，进而使之进入接收临时调度的状态；而DispatchThread在从总表中获得乘客请求后，让AllElevators去决定分给哪部电梯，可以获得最好的性能。为了不锁电梯线程，(虽然也可以，但是我情感上并不情愿)我在ElevatorThread类中只保留了ProcessingTable一个对象属性，其余与电梯有关的属性与方法都放入ProcessingTable类中实现，也就是将ProcessingTable类作为一种状态机，而Elevator线程的run()方法就是每个循环都调用ProcessingTable的run()方法，获取一个当前电梯的状态，直到获取到OVER状态结束运作。这样一来，调度获取信息时只要锁住ProcessingTable即可，而ElevatorThread线程类同DispatchThread交替获取ProcessingTable的锁，进行相应的操作。

调度线程与电梯线程的解耦合

由于调度器线程的结束需要等到电梯线程都要结束了，也就是当所有电梯都没人可载(包括电梯内外)时进入等待状态时，且此时总请求表已被置结束且为空时，调度器结束运行，我的做法就是在总请求表类RequsetTable中设置一个记录每个电梯是否进入等待状态的数组，其中1代表进入，0代表未进入，再封装一个方法将该数组的所有值加起来返回其等于6的布尔值，也就是判断是否所有电梯都进入了等待状态，不过这里需要注意，每次修改状态都要去修改一下此处的等待数组，不然本来未结束但是提前结束的可能，而且由于为了避免轮询的情况发生，此处如果总请求表为空但并未置结束或者并未所有电梯都进入等待状态，需要让总请求表进入等待状态，同理分请求表在电梯进入等待状态后也需要让其进入等待状态，不过在这之前一定要先让其修改等待数组，不然如果这时候刚好没有输入了其他电梯都等待了，那么没有东西会让唤醒该电梯了，将永眠于此，造成超时。

调度电梯算法

DispatchThread在调度的时候通过获取单例的形式利用AllElevators调用Strategy类的方法虚拟化六部电梯(一定要同时获得)，这里为了避免围师必阙，并不会不考虑处于临时调度的电梯，所有电梯都会参与虚拟模拟，通过让虚拟电梯模拟得到最优解，再分配给相应的电梯，虚拟化的过程也就是虚拟的加上可能花费的时间来模拟，例如：开关门、移动和临时调度的开关门等，而在虚拟电梯中未达到目的地而下电梯的乘客就当做其中途下车，不计入最终的平均运送时间(因为压根都没送到嘛)。

synchronized (elevators.get(1)) {
    synchronized (elevators.get(2)) {
        synchronized (elevators.get(3)) {
            synchronized (elevators.get(4)) {
                synchronized (elevators.get(5)) {
                    synchronized (elevators.get(6)) {
                        long nowTime = System.currentTimeMillis();
                        for (int i = 1; i < 7; i++) {
                            ProcessingTable realElevator = elevators.get(i);
                            VirtualElevator virtualElevator = new VirtualElevator(
                                realElevator.getTotalPriority(), realElevator.isUp(),
                                realElevator.deepCopyPeople(),
                                realElevator.getElevator().deepCopy(),
                                realElevator.getSpeed(), realElevator.getLastTime(),
                                realElevator.getLastStatus(), realElevator.isSchedule(),
                                realElevator.getScheRequest(),
                                realElevator.getLastScheduleTime(),
                                realElevator.getScale(), nowTime);
                            virtualElevators.put(i, virtualElevator);
                        }
                    }
                }
            }
        }
    }
}

同步块的设置与锁的选择

锁我还是选择了synchronized。一开始的同步块的设置我并没有理解的很到位，导致出现了很多因为太过于”安全“导致的超时问题，简单来说，同步块的设置应该是使那些不同线程对于共享的临界资源的操作变为原子操作，不可打断，因此对于并不用以原子操作来看待的部分就可以不用加锁，此外，切忌带锁sleep，这是大忌，相当于当前锁住的对象，在sleep的过程中啥都不能干，其他进程只能等到它睡完才能接手操作，那一定程度上已经可以称为单线程了。

临时调度处理方式

为了保证6s限制，我只允许临时调度ACCEPT后的那一层开一次门，并且只有有人可以出去(包括到目的地了和去临时调度楼层与目的地反向或者更远了等)才会开门，之后根据临时调度的速度来判断再移动几层，如果临时调度的速度慢于原电梯速度，那么是否可以利用原有的速度进行移动，不过这里移动的前提是还有RECEIVE的乘客或者电梯内有人，不然也得立即BEGIN。此处还有一坑就是假若临时调度来的瞬间，电梯正在进行移动动作或者刚好完成移动动作，输出在ACCEPT之后，那么这说明之后最多只能再移动一层了，需要进行特判，我的方法是设置了lastScheduleTime、lastTime和lastStatus三个变量，分别代表上一次临时调度接收的时间、上一次操作的结束时间(包括移动和开关门)和电梯的上一个状态，如果lastTime>=lastScheduleTime & lastStatus == MOVE ，那么就可以判断出其之后只能再最多移动一层了。剩下的就是BEGIN开始后的固定操作了。

RECEIVE的处理

我为Person类添加了isRceived变量来标志这位乘客是否被接收。调度分配时，对于不处于临时调度的电梯，isReceived置true并且输出相应RECEIVE输出；否则，并不会输出相关信息，直到临时调度结束后电梯会判断电梯外的请求队列，未Received的人会统一进行RECEIVE。此处一定要注意判断电梯是否处于临时调度，跟进行相应输出一定是一个原子操作，因为，获取的判断是不允许在输出操作之前被修改的，如果允许，那么此前的判断就于事无补了。因此，此处一定需要加锁。

代码UML图

类图

协作图

强测bug

由于我并没有对于加锁条件的认识足够清晰，导致了因为一些胡乱的加锁导致的不可预料的错误，我的理解是加锁本质上是将一些本来不是原子操作的行为通过加锁的形式阻塞其他进程的访问，从而使其在其他线程的观测下达到类似于原子操作的目的。当然其中有些许行为并不需要视为原子操作，因此就可以不用进行加锁。首先是在调度器分配的时候，我是通过一个Allelevators类管理所有分请求表，此处我误认为并不用在分配的时候对Allelevators进行加锁，但是如果考虑到此时同时也来了临时调度，那么这两个很有可能会在Allelevators对象中同时进行，又由于我误认为拿电梯是否处于临时调度的状态时已经加锁了，之后判断的时候不用加锁，导致很有可能我刚拿完状态，那边临时调度就来了，如果分配输出在ACCEPT和BEGIN之间还能（侥幸逃过一劫），但是一旦比BEGIN还晚，就会BEGIN了还在进行RECEIVE操作；其次在move和openandclose操作中我都进行了带锁sleep，这让调度器需要等待某个电梯的锁被释放了才能采取决策，如此一来会导致之后的决策的时间延后，若碰巧在临时调度，就很有超时的可能；最后在schedule操作中，我将begin之后到移动到目标楼层的行为捆绑成原子操作了，但实际不然，同第二点，这也会让调度器等很久，导致决策延后。此外，我只将调度算法中的获取每个电梯状态放在锁中，至于之后那先释放锁再说。
这次的debug过程又让我再一次加深了对于多线程运作以及锁的机制的理解！！！

第七次作业

新增内容

1. 双轿厢改造：改造两个单轿厢电梯为双轿厢电梯，改造后，这两个电梯共享一个电梯井，一个在上一个在下，需要确保上下电梯在共享层不发生碰撞，改造后修改速度等，其余限制类似临时调度。
2. 新增RECEIVE的约束，一旦电梯开始进行双轿厢改造后，即输出UPDATE-BEGIN后，与这两个电梯相关的乘客的RECEIVE关系都取消。

代码架构分析

有了第六次作业的基础，这次加入的UPDATE操作大同小异，不过主要重要的是如何处理电梯升级后的双轿厢不相撞，对于共享层的抢夺等问题？

因此，此次作业要解决的问题有：

1. 如何实现电梯在升级过程中两个电梯之间的通信？
2. 如何在升级后让两个电梯相安无事的在同一个电梯井中运作？
3. 如何实现电梯调度策略从单轿厢向双轿厢的转变？
4. 采取何种调度策略？

换乘层的实现

与第六次作业相同的，情感上，我并不能接受将线程锁起来的做法，因此为了实现两个线程的通信，我设计了一个TransferArea类用来实现两个电梯线程对其的抢夺，抢到的才能进入共享层进行相应的后续操作。那么是如何抢的呢？我在TransferArea类中设计了一个side的属性用来标定当前是上下哪个电梯(“up”、”down”)占有，还是无电梯(“none”)占有。电梯线程通过互斥访问TransferArea的side变量，直到其为none才能将其设置该电梯的side，为了避免轮询，可以在判断到当前的side不是none后，交出锁，进入等待状态，代码如下：

while (!transferArea.getSide().equals("none")) {
            synchronized (transferArea) {
                try {
                    transferArea.wait();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        }
        transferArea.setSide(side);

抢到共享层使用权后，进入共享层，进行相应操作，直到得到RELEASE信号，由SubTable的run()方法返回。同时还用去唤醒另一个可能在等待的电梯。

对于升级的设计，我是采取收到升级信号后，立马把电梯中的人全清出去，进行UPDATE。

我采用了初始就将所有电梯设置双轿厢电梯的策略，也就是初始是六个电梯井，一上一下两个电梯，只不过一开始所有电梯都在上方(-4——7)，电梯井的下方电梯在-5层以下，再在分配的时候判断一下该电梯井上下电梯谁可以接收该请求来进行决策，如此一来在电梯升级的时候，只需要将下电梯或上电梯修改成对应实例(因为虽然一共有12个电梯，但实际上只有6个电梯对象，初始时上下电梯是一个实例)，并将换乘层进行修改即可完成升级。如此一来，我就不需要去考虑两套策略(单、双)，只要针对电梯井设计一种双轿厢策略即可，因为，未经历过升级的电梯井的下方电梯永远接收不到乘客，实际上就是单轿厢。

关于如何控制电梯间通信，我设置了一个外部管理所有电梯的类AllElevators(其实只是存有对应电梯井的hash表的一个容器类)，并在该类中完成对于对应电梯的调度等操作，因此升级时通过该类和电梯线程分别去访问换层区类TransferArea置开始信号，并获取开始信号，来标志着升级的开始，结束是类似的，但是不同于结束的是，开始是要在输出UPDATE-BEGIN之后的，也就是电梯线程一定要等到管理所有电梯类置了真正开始的信号并且自身和另一个电梯的开始信号都置1时，才可以正式开始，这样才能确保在某些极端情况下已经输出了UPDATE-BEGIN，但是还是RECEIVE的情况，我的解决方法就是多设置一个真正开始的量在输出UPDATE-BEGIN后才置上。当然对于换乘层的任何属性的访问都需要上锁。

调度策略

在第六次作业采用了影子电梯的策略，但是由于正确性堪忧，且舍友均分策略都取得了不俗的成绩的刺激下，我在第七次作业中采用了调参+均分的策略(其实也就是调参没完成的分配再通过均分去分配)，效果显著，因为有更多的时间去检查正确性。第六次就是倒在了正确性。

这里的调参，我大概考虑了电梯内外人数总和、与乘客所在楼层的距离、乘客的方向同电梯方向是否相同、是否为单轿厢等(因为双轿厢会更快点)等参数，极为朴素。

代码UML图

类图

协作图

强测bug

在进行电梯的升级操作时存在与电梯系统为了分配而获取的每一个电梯井上下电梯状态的竞争关系，稍有不慎就会触发死锁风险，因此**我在一些获取锁但并未在释放锁之前notify其他进程的地方设置了有效的notifyAll**。

三次作业稳定与易变的内容

稳定的内容

我认为**”生产者-消费者”的框架是三次作业中都一直出现的，以及线程之间的互动方式**都是稳定的。

易变的内容

我认为电梯行为和属性的极具扩展性，因此在三次作业中电梯的行为和属性逐渐迭代丰富，这是这三次作业中最易变的部分。

debug方法

1. 首先就是百试不爽的printf大法，在涉及到状态变化等可能出现问题的题目输出相应的状态和过程量。
2. 其次就是运动一会后再通读一遍代码，重新审视可能会有很不一样的感觉。
3. 最后就是多搓样例，尽可能在多种样例中复现问题，总结共性存在的问题。

心得体会

本单元了多线程程序设计，其中由于多线程导致的各种奇怪bug无不警示着我们线程安全至关重要。

说来惭愧，这三次作业中，我使用的都是synchronized，并没有去尝试课上讲的如读写锁之类的更高级的方式，但是这种原始的锁，也让我对于多线程之间的互斥与同步，进而达成协作有了更加深刻的认识——使那些不同线程对于共享的临界资源的操作变为原子操作，不可打断，对于非共享的资源便可并行处理进而提高运行效率，或许这就是多线程的魅力吧！！！

此外，在层次化设计的方面，我学会了至顶向下的设计思路，同样也会通过底层反推上部类的设计，使类之间具有层次感，可读性更加好。

我学到了许多很有用的设计模式，例如:单例模式、生产者-消费者模式、工厂模式、观察者模式等。

总之，电梯总算完结了，撒花撒花！！！