OO第二单元总结

​ 第二单元的主要任务是电梯调度。在第一次作业中，虽然是有多个楼多部电梯，但实际上电梯之间没有关系，因此我认为第一次只是一个生产消费模式的实例，主要难点是刚接触线程，需要考虑线程的安全问题。而第二次作业是真正有了多电梯之间的调度问题，在这次作业中我采用了“标记法”。此外，虽然这次作业添加了横向电梯，但是并不涉及转运问题。而第三次作业需要处理转运问题，且电梯有容量速度的差别，因此我又回归到了自由竞争的look调度方法。

1.第一次作业

1.1整体架构与调度器设计

​ 在本次作业中我的线程有三种：main线程，Input线程和电梯线程。main线程负责创建共享区和启动其他两种线程。Input线程会调用大共享区（shareData）中的分配方法将人分配到对应的楼中。电梯可以自行查询楼中的数据并根据可捎带ALS策略接送人。

​ 可以看到，其实Input线程相当于起到了调度器的作用，电梯是不受约束的，完全是读取数据并自己决定怎么运行。

.

1.2 同步块与锁的设置

​ 我在三次作业中都只使用了synchronized来进行同步。通过上面的结构分析可以知道，第一次的同步情况较为简单：虽然有多栋楼多栋电梯，但每个共享区（楼）里只有一部电梯，线程安全是比较容易做到的，最次的情况也是把小共享区building里所有的方法都修饰synchronized。因此我在第一次作业中的重点不是如何更安全，而是如何减少synchronized的使用来提高效率。

​ 共享区的方法是要加锁的：避免电梯在查询building或从building里取人时Input线程通过shareData向building加人的情况，但是电梯对于自己状态改动时就不用加锁了。比如电梯要查看自己是否有乘客（isEmpty方法)，是否满载(persons.size()<capacity)或是否应该放人出去(outPerson方法)时是不用加锁的，因为在我的设计中电梯自己内部的数据并不会被外界查询，不是共享数据。

​ 当然，虽说我认为这次作业的重点不在于线程安全，但是有一个小细节需要注意，比如下面这段代码严格来说是有问题的

			if (!isEmpty()) {
                move();
            } else {
                if (building.isEmpty()) {
                    if (building.isEnd()) {
                        break;
                    }
                    synchronized(building){
                    	building.wait();
                    }
                   //代码为伪代码
                    continue;
                }
                //...............
                //楼没有空，找到第一个人，设定方向并且移动
                //...............
            }

​ 大家可以当这一段代码是电梯run函数里的一个节选：先判断电梯自己是不是空的，如果不是，那就按定好的方向move即可，否则先判断楼有没有空，如果楼空了而且building被标记为end，这说明一切已经结束了，跳出最外层while循环，否则wait一下等待来人被唤醒。。。

​ 这段代码的问题是：可能刚刚判断完building.isEmpty（），InputThread就向该楼加入了一个人（addPerson)，addPerson在执行的时候也确实notifyAll了，但是这是在building.wait()之前的，于是这部电梯就进入wait状态而不去接人。解决方法也比较粗暴：增大synchronized范围即可。

​ 此外还有一点值得注意：如何结束线程。其实上文已经给出了我的大体思路：那就是在楼中增加一个end变量。当Input线程结束时，会调用大共享区（shareData）的setEnd方法。该方法调用每一个building的setEnd方法：设置end为true并notifyAll。在本次作业和第二次作业中building.setEnd()方法是被synchronized修饰的，我在第三次作业中做了改进，将在下文提到。

1.3 bug与hack

本次作业共有两个bug

​ 第一个是输出线程安全问题，没有给输出线程加锁导致的。要解决这个bug，我新建了一个输出类MyPrint，在类中将原先的输出方法包装起来并同步即可。

​ 而第二个是在电梯进人时忘记了规定容量。虽然在决定是否开门时要判断是否有人要进来而且在该函数中我判断了容量的问题，但由于要同时判断了是否要出人，因此会出现为了出人而开门然后超载的情况。

​ 在hack时，我并没有时间读取他人的大量代码，我的策略是在规定时间的最后一刻放入大量的人，来检测别人的代码是否可以执行完成。

2 第二次作业

2.1整体架构与调度设计

​ 本次作业中虽然有了横向电梯，但是并不涉及电梯之间的转运，因此完全可以把每层和一栋楼等价，把横线电梯与纵向电梯等价，唯一不同的是横向电梯是可以循环的。为了更快的运送，应该沿着更近的方向接送，这也是比较好实现的。总之，INputThread依然可以分担分派人的任务，起到调度器的作用。

​ 我认为本次做作业的重点在于一栋楼里可以有多部电梯，因此会产生线程安全问题。此外，如何调度这些电梯也是一个问题。比如要用一个monitor来监控电梯的状态并以此对调度做规划吗？或者会否要让电梯之间交流呢？我认为上述做法是不可行的，这样共享数据就不只是building中的了，elevator中的数据也变成了共享数据。如果发生了互相读取的过程，那更可能发生死锁。

​ 因此我依然采取电梯读取共享区信息并自主接人的策略，并采用了标记法来减少“自由竞争”时的陪跑现象。事实证明标记法并没有明显的比自由竞争快，而且在第三次作业中也将被淘汰，但是我当时还是选择了这种做法。

​ 标记法与自由竞争的不同是，每部电梯在空的时候每到一层可以最多给一个人做标记，这个标记包括电梯ID和自己当前的位置。电梯将朝着自己标记的人的方向前进。当其他电梯发现自己离这个人更近的时候，可以替换这个标记为自己的。若一步电梯无法标记任何人，则他会wait。

​ 这种做法是我和另一位同学共同设计的。其原本目的如上文所说，是减少自由竞争的陪跑现象。此外，我们规定一步电梯最多标记一个人，是为了防止人太多又集中时时，只有一部电梯运作的情况。

2.2 同步块与锁

​ 虽然相比第一次作业增添了标记，但其实共享资源并没有增加，因为标记过程也是在遍历队列的过程。

​ 此外，这次作业中虽然有假如电梯的指令，但由于building可以查询building中的内容，但building或shareData无法查询电梯的内容，因此加入电梯时也并不用上锁。

2.3 bug与hack

​ 本次作业中我没有被发现bug。

​ 我也没有hack别人。

3 第三次作业

3.1 整体架构与调度设计

​ 在本次实验中电梯可以被规定容量和速度。对横向电梯还可以规定停靠的楼座，我认为这种条件下自由竞争可以发挥最大作用。此外我放弃了ALS而采用用了Look算法。整体结构和时序图如下。

​ 整体构建相比第二次改动不大。shareData内部包含着各个building（楼）和各个circle（层）并作为大共享区负责接收InputThread的指令。当要加电梯时创建电梯并建立电梯和对应楼座或楼层的关系（也就是让该电梯能看到小共享区）。当加人时将这个人分派给对应的小共享区即可。

​ 主要在于怎么处理换乘。我的思路是：新建一个Person类，如上图。该类中保存有原personRequest中的信息以及该人当前位置和临时目的地位置。在InputThread请求分配一个人时，shareData会根据当前横向电梯的分布情况为这个人规划一条路线并根据该路线的第一段将这个人分派给合适的楼或层，并记录这一段的临时终点。电梯在查询小共享区时只关注临时终点的位置。当电梯完成某个人的任务时，会检测该人的临时终点是否和其终点相同，如果不相同，则设定其当前位置，并交给shareData重新分配出去。

3.2 同步块与锁的设置

​ 相比于上次，产生了一下几个问题，我们一一解决

怎么实现人员分配

其实上面已经提到了分配方法，但可以看到，无论是输入线程的人员分配请求，还是电梯在出人时产生的分配请求，都是由也只能由shareData完成的，因为只有shareData是各个小共享区沟通的桥梁。因此我们实际上是在shareData里加入了一个横向电梯队列（floorElevators），保存着所有的横向电梯的情况。当有请求到来时，查询该横向电梯队列来进行分配

如何使电梯停下来

​ 在前两次中，只要输入线程结束，我们就可以把个共享区的end标记为true了，但这次次由于存在换乘，电梯不能因为自己是空的，而且输入线程结束就结束了。随时可能有人因为换乘来到这个小共享区。

​ 对此我的策略是加入一个计数器，当输入线程有一个加人请求时，该计数器加1，在该请求完全完成时，计数器减1对应上面的shareData中的add和sub方法。电梯只有在自己为空，输入线程结束，且计数器为0的情况下才会停止运行。

上面两个问题引发的死锁问题

​ 我们先考虑shareData中两个函数的使用情况：它们分别是disPatchPerson和addElevator。addElevator会在floorElevators中加入一个新的电梯元素，而disPatchPerson会查询floorElevators并将人派发到相应的共享区。显然，如果不加同步块，这两个函数完全可能共同执行，即一步电梯正在出人并试图把该人重新dispatch到合理的共享区，而此时输入线程正好在请求增加一部电梯。

​ 因此为了保证安全，我们应该将这两个函数上锁。上锁后disPatch的情况大致如下。也就是外层锁shareData内层锁building或circle

//对于disPatchPerson函数，
public void dispatchPerson(Person person) {
	synchronized(shareData){ //先锁住大共享区shareData，因为要查询floorElevators中的信息
        //.............
        //找到合适的电梯,确定该人员要分配的小共享区
        //...........
        synchronized(building or circle){  //锁住该小共享区
            //....
            //向小共享区加人
            //...
        }   
    }
}

我们还可以看看上面提到过的那段曾经有问题的代码，下面已经把问题改好了。

			if (!isEmpty()) {
                move();
                continue;
            } else {
                int dir;
                synchronized (building) {
                    if (building.isEmpty()) {
                        if (building.isEnd() && shareData.getCount()) {
                            break;
                        }
                        myWait();

                        continue;
                    }
                    dir = shortest();

                }
              
				//......其他操作
            }
			

​ 可以看到，这次synchoronized块包含了整个部分，因此原来的问题得到了解决。

​ 但是我们可以清晰地看到这个块里有shareData.getCount()方法，这个方法是用来判断计数器是否为0的，而且显然计数器相关的函数应该上锁。这将导致外层锁building，内层锁shareData的情况。

​ 这两者之间当然可能产生死锁。

​ 这时我发现，shareData是不应该只有一把锁的。比如上文中涉及到count的操作应该有一个count的锁，而对应floorElevator的操作，应该也有他自己的锁。这样就可以解决问题了。而这种思想其实应该在第一次作业就运用的。

3.3bug与hack

​ 在本次作业中我又犯了同样的错误在修改容量是没有修改完全，横向电梯的capacity依然维持在6，最后导致强侧有3个点没有通过。

​ 在hack其他人时，我采取了与第一次相同的策略。在规定时间得最后放入大量的人，成功hack了两个人。

心得体会

线程安全

​ 在第一次作业中，我就犯了一个线程安全错误：也就是输出的线程安全问题。其实这是因为我未必饿了老师曾经说过的一个原则：永远不要相信别的程序员写的代码是线程安全的。当然，关于输出线程不安全的问题指导书里已经提过了，最终还是因为我自己太懒没有解决。

​ 除此之外我很庆幸自己在测试中没有碰到线程安全的bug。但在这三次作业中保证线程安全却真的耗费了我大量的时间。比如在第一次作业中我就曾经犯过上面提到的那个错误，幸好在同学的提醒下改正了。同时，再第一次作业中我还精简了锁的运用，尽量提高效率。而在第三次作业中，因为同步关系越来越复杂，我开始关注锁之间的互相嵌套是否会发生死锁，通过设置多个锁，我解决了原来存在的线程安全问题。

层次化设计

​ 在层次化设计方面，设计大共享区和小共享区的思路是我的最大收获。在第三次作业中，各个小共享区之间是要互相交换数据的。而这时大共享区就变成了他们之间的桥梁。

​ 此外，我还有一个收获就是每一部分应该干好自己的事，尽量不要获取其他对象的数据。因为共享数据越多，同步关系越复杂，越有可能发生死锁。

​