OO第二单元总结

作业总结

第五次作业

作业简介

这次作业是编写一个简单的多线程实时电梯系统，实现模拟五部电梯接送乘客的功能。

类图与协作图

类图如下：

协作图如下：

各个类含义如下：

Main：主类
Person：乘客类/请求类
AllTable：全局Table（后来发现其实和控制器类似）
Table：请求队列
Request：输入请求线程
Elevator：电梯线程

代码分析

策略分析

这一次我主要采用look算法来调度我们的电梯。

• 当我们电梯发现前进方向有请求时，电梯按原方向前进，否则，电梯掉头。

• 当此层有乘客并且乘客的行动方向与我们一致时，并且电梯未满员，则捎带此乘客。

其实我并不是了解到look算法以后才编写的代码，而是先完成了本次作业才知道我用的是look算法。其实细心的同学会发现，这个算法不就是宿舍公寓的电梯算法吗？没错，我是先仿照了宿舍电梯的运行逻辑之后，想出了这样的调度算法。

同步块的设置和锁的选择

本次作业，由于一部电梯对应一个请求队列，是多线程中最简单的情况，每一个请求队列会被它对应的电梯和AllTable类调用，因此，只需要将请求队列中每一个方法加上synchronized即可。例如：

    public synchronized boolean havePerson(int status, int floor) {
        int key = 2 * floor - 2;
        if (status == -1) {
            key++;
        }
        if (floorMap.get(key).size() == 0) {
            notifyAll();
            return false;
        }
        notifyAll();
        return true;
    }

bug分析

自测和课下：

在课下自己的测试中我一共出现了三次bug，但是很巧的是，三次bug根本原因都是一个。由于我不太习惯使用枚举型变量来存储一些状态、数据，而是使用int人为规定1,2,3,4等状态码来表示电梯的状态，楼层等。由于数组变量是从0开始的，而现实中的电梯是从1楼开始的，因此我在对应的时候想当然的用楼层数去取数组变量；在电梯状态方面，我在一处代码中用错状态码导致出现致命bug。

互测和公测：

第五次作业的互测和强侧并没有测出我的bug，但是诚实的说，我并没有安全输出类，因此我的输出线程并不安全。

测试思路

由于是第一个多线程作业，我的测试并没有什么明确的思路，我的测试分两种，一种是同一时刻输入很多指令，另一种是隔很久输入一两条指令，来找出多线程调度的漏洞。前者是测试有无线程不安全和死锁问题，后者是测试有无死等问题。

第六次作业

作业简介

这一次作业加入了横向电梯和多部电梯的设定，增加了线程之间的耦合度，提高了编码的难度。

类图与协作图

类图如下：

协作图如下：

各个类含义如下：

Main：主类
Person：乘客类/请求类
AllTable：全局Table（后来发现其实和控制器类似）
Table：纵向请求队列
TableFloor：横向请求队列
Request：输入请求线程
Elevator：纵向电梯线程
ElevatorFloor：横向电梯线程
OutPut：输出安全类

代码分析

策略分析

这一次，我并没有更改我上一次作业中关于纵向电梯的调度策略，对于多部电梯让它们自由竞争就好了。

其实选择自由竞争并不是由于我想偷懒的缘故，而是我经过深思熟虑之后的选择。对于较大的数据来说，将来的请求分给各个电梯是十分不划算的。可能出现你分给电梯2的请求恰巧就能被电梯1捎带等这样的情况，或者出现电梯1忙的不可开交，其他几个电梯却在看戏的情况。因此我选择了自由竞争。但自由竞争会产生一个问题：在多个线程共享一个请求队列的情况下，这个程序会不会容易出现死锁bug？

答案是不会，因为这些线程只能访问一个请求队列，并不会出现线程1抱着资源a的锁想要资源b的锁同时线程2抱着资源b的锁想要资源a的锁的情况。只要这个队列的数据给保护起来，线程不安全的问题也解决了。

对于横向电梯，我一开始也想使用look算法，但是一直没有头绪。对于讨论区中有人说的“把此时的楼层作为楼层的中间层，采用look调度”我认为是会出大问题的。这个调度方法是强行披上look的外衣，实际上并没有把握look算法的精髓。在look的调度算法中，我认为最重要的是请求的方向。我们在乘坐电梯的时候，电梯门口会有两个按钮——一个是上行，一个是下行。在环形电梯中方向变得模糊了，什么是前进？什么是后退？这些都不清楚。因此，当出现ABCDE座同时有人想逆时针乘坐电梯而电梯却是顺时针时，电梯会不停的旋转。

最后，我的横向电梯采用了定向旋转的调度算法，此算法虽然在大多数情况下比主请求算法要慢上一些，但是算法设计比较简单。

同步块的设置和锁的选择

在这次作业中，同步块的设置和锁的选择和上次相同，只需要保护Table、TableFloor和OutPut三个类即可。具体实现方式如下：

TableFloor中：

    public synchronized boolean havePerson(int keyIn) {
        int key = keyIn;
        if (floorMap.get(key).size() == 0) {
            notifyAll();
            return false;
        }
        notifyAll();
        return true;
    }

Table中：

    public synchronized void addPerson(Person person) {
        int key = person.getOriginFloor() * 2;
        if (person.getStatus() == 1) {
            key++;
        }
        ArrayList<Person> floor = floorMap.get(key);
        floor.add(person);
        number++;
        notifyAll();
    }

OutPut中：

public class OutPut {
    public synchronized void printf(String str) {
        TimableOutput.println(str);
    }
}

bug分析

自测和课下：

在这次课下的代码编写和自我测试中，我只出现了一次bug。具体原因是由于Elevator和ElevatorFloor类、Table和TableFloor类过于相同，在编写代码的时候复制粘贴出现了问题。现在回想起来，我觉得应该使用父类继承的方式来完成这部分的代码，这也是我这次代码中不太好的一点吧。

互测和公测：

在这一次的互测和公测中我出现了一个bug，然后被同房大佬疯狂hack。还记得我上一个作业输出线程不安全没被查出来吗？这次我确实整了一个输出线程安全的OutPut类，但是我在更改代码的时候有两个输出依然使用的官方的输出包！！！！！

测试思路

这一次的测试我就更有了针对性。

首先，针对易错的点和边界数据构造测试数据。比如线程安全问题就集中大量的push请求，调度死等死锁问题就构造相应调度算法的最坏情况……

同时与同学交流测试时容易出现的bug，看看有没有自己想不到的错误点。

最后还可以将这些测试数据混合在一起，来一个随机测试。

第七次作业

作业简介

这一次作业引入了电梯换乘的问题，作业中用到了流水线工作模式。线程之间的耦合极大的增强，难度急剧增加。

类图与协作图

类图如下：

协作图如下：

各个类含义如下：

Main：主类
Person：乘客类/请求类
AllTable：全局Table（控制器）
Table：纵向请求队列
TableFloor：横向请求队列
Request：输入请求线程
Elevator：纵向电梯线程
ElevatorFloor：横向电梯线程
OutPut：输出安全类
MyMap：换乘策略地图
MapElevator：地图电梯标记

代码分析

策略分析

首先，对于任意一个乘客，他一定可以通过纵向电梯、横向电梯、纵向电梯的方式到达目的地（当然可能会有其中一些过程是没有的）。因此，把握住这个任意性，乘客换乘的策略就很清晰了。三级流水线的请求处理方式是大势所趋。

路线规划方面，我采用请求事先规划路线的方式解决路线处理问题。可以看到，这一次作业我多了MyMap这个类。这个类存储了各个横向电梯的参数。在请求进入之前，MyMap类就会根据请求的起始地和目的地规划处请求的换乘路线。

这一次的Person类中我做了一小点改动，Person类会有一个目的地参数和当前目的地参数。因为对于任何一级处理请求的流水线，它只需要知道乘客在此阶段的目的地在哪里就可以了，对于这个乘客他具体要去哪实际上与电梯无关。

public class Person {
    private String id;
    private int origin;
    private int originFloor;
    private int destination;
    private int destinationFloor;
    private int status;
    private int destinationFinal;
    private int destinationFloorFinal;
    private int changeFloor;
}

通过AllTable这个全局类，将每一级流水线结束的请求交给下一级流水线，实现流水线处理。具体如下：

    public synchronized void addRequest(Person person) {
        //System.out.println(person.getId() + " " + person.getStatus());
        if (person.getStatus() == 4) {
            count--;
            notifyAll();
            return;
        }
        if (person.getStatus() == 3) {
            TableFloor tableFloor = floorMap.get(person.getOriginFloor());
            tableFloor.addPerson(person);
            notifyAll();
            return;
        }
        Table table = tableMap.get(person.getOrigin());
        table.addPerson(person);
        notifyAll();
        return;
    }

同步块的设置和锁的选择

我认为本次作业才是多线程的精髓，线程之间的高度耦合使程序的复杂度大大提升，一不注意还会出现死锁、死等、等令人头秃的bug。对于同步块的设置和锁的选择，我依然是使用了最简单的synchronized。

对于OutPut类：

public class OutPut {
    public synchronized void printf(String str) {
        TimableOutput.println(str);
    }
}

对于Table类：

    public synchronized void addPerson(Person person) {
        int key = person.getOriginFloor() * 2;
        if (person.getStatus() == 1) {
            key++;
        }
        ArrayList<Person> floor = floorMap.get(key);
        floor.add(person);
        number++;
        notifyAll();
    }

对于TableFloor类：

    public synchronized void addPerson(Person person) {
        //System.out.println("addPerson");
        if (person.getStatus() == 3) {
            int key = person.getOrigin();
            ArrayList<Person> floor = floorMap.get(key);
            floor.add(person);
            number++;
            notifyAll();
            return;
        } else {
            System.out.println("What are you doing?");
            notifyAll();
        }
    }

对于全局类：

    public synchronized void addCount() {
        count++;
        notifyAll();
    }

bug分析

自测和课下：

测试不充分，未发现bug。

互测和公测：

出现了一个bug,被大佬和强测疯狂hack……

问题就出在我课下不充分的测试上，我考虑不周导致出现了bug。

测试思路

这一次的测试我和上次采用相同策略。

首先，针对易错的点和边界数据构造测试数据。比如线程安全问题就集中大量的push请求，调度死等死锁问题就构造相应调度算法的最坏情况……

同时与同学交流测试时容易出现的bug，看看有没有自己想不到的错误点。

最后还可以将这些测试数据混合在一起，来一个随机测试。

心得体会

其实，这三次作业做下来，我感觉收获还是很多的。纵观三次作业，设计的十分合理，从简单的线程资源一对一，到线程资源多对一，再到流水线处理模式……作业的难度，深度都是循序渐进的。诚然，横向电梯的想法确实有些脑洞大开，也是有很多同学吐槽，但是我认为，助教和老师们能想到这么脑洞大开的题目，也侧面说明了他们的良苦用心。

在这次作业中，很多同学对调度算法似乎很有兴趣，每天饭前饭后和同学们讨论，常听到这样的话：“某某大佬好像采用了某某调度算法，我回去看看。”，“我听说这次作业的调度可以用图论。”……实际上这三次作业的重点真的是调度算法吗？

应该不是吧，我觉得在这门课程的学习上，我们可千万不能忘记了课程的名称：“面向对象设计与构造”，似乎并不是：“算法与程序设计”。当然，这里并没有贬低大佬的意思。我觉得在这三次的作业中，细细体悟什么是面向对象比优化个算法来的更加重要。

在第三次作业的课下编码中，我对死锁问题有了一定的感悟和体会。死锁是什么呢？死锁就是线程1抱着资源a的锁等资源b的锁，而线程2抱着资源b的锁等资源a的锁。两个线程互不相让，导致了这种情况。如何解决这个问题成了一个难题。在第三次作业中，如果我想让请求流水线间换乘的话就势必会出现线程想将请求1从流水线a送到流水线b，同时另一个线程想将请求2从流水线b送到流水线a。这不就死锁了吗？经过几个晚上的思考，我认为可以通过资源分级的方式避免一切死锁。资源分级是指将资源分等级，可以通过等级高的资源调取等级低的资源，而等级低的资源不能回调等级高的资源和同等级资源。这样，我们对上述情况的资源a和资源b分级，如果资源b能调用资源a,那么，资源b的等级就一定比资源a高，资源a就不能调用资源b。这种方式虽然能避免死锁，但是会失去一部分代码灵活性。

对于代码设计和架构方面，我认为一份有良好拓展性的代码才能算是好代码（当然，我的应该不算）。对于一个类，如何能将这个类封装好是一个值得探讨的问题。我在写代码的时候，常常想实现某一个功能，于是加入了一些十分丑陋的方法。这些方法往往有着超过五个需要输入的变量，往往有着长达几十行的if-else往往有着脑洞大开的返回值……如何封装一个类，如何去管理这些数据，依然是值得我继续思考的问题。