BUAA_OO_第二单元总结

​第二单元是多线程电梯模拟，这是我第一次接触多线程的概念，还是比较难理解的。与第一单元相比，代码量有所减小，但是需要花费更多心思在调度策略的设计和线程安全上。经过这一单元的练习，我还是收获了许多的。下面来分享一下我的思考。

1.同步块的设置和锁的选择

​在第一次作业中，我使用了生产者-消费者模式，输入作为生产者不断产生Requset，电梯作为消费者取出Request，等待队列WaitingList作为共享对象需要保证线程安全。

​由于这个共享对象最多只有两个线程同时访问，没有激烈的竞争，不需要更多的性能优化，所以选择synchronized关键字来为共享对象加锁。

​输入线程和电梯线程之间存在读写互斥和写写互斥，所以我为WaitingList类中的每个能被外界调用的实例方法都加上synchronized锁，保证线程安全。此外，还需要用到synchronized代码块。为了避免轮询，消费者在等待生产者在WaitingList中放入Request需要用到wait-notify策略，这时需要用到以WaitingList实例的锁的代码块。

    synchronized (waitingList) {
        while (waitingList.getSize() == 0) {
        	try {
                waitingList.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
           	}
        }
        DoSomething;
    }

​此外，对于需要多次访问共享对象且联系比较紧密的代码块，例如遍历共享对象，需要用synchronized加锁代码块，使得这块代码一次执行完，防止与其他线程穿插执行，改变共享数据的状态。

    synchronized (waitingList) {
    	for (int i = waitingList.getSize() - 1; i >= 0; i--) {
            PersonRequest request = waitingList.get(i);
            DoSomething;
        }
    }

​在第二次和第三次作业中，我引入了调度器，共享对象有输入和调度器之间的InputList和调度器和电梯之间的WaitingList。一个共享对象仍然最多只有两个线程访问，不存在激烈的竞争关系，所以我基本延用了第一次作业锁的策略。

​总的来说，由于本单元作业场景下线程对于共享资源的竞争并不激烈，所以我统一选择了比较简单也比较保险的synchronized锁及同步块，这样可以放心的将更多时间投入在电梯的调度策略和性能优化上。

2.调度器设计

​由于第一次作业是单点梯，所有输入的Request都由唯一的电梯进行实现，所以我并没有实现调度器。但是为了满足Morning、Random、Night三种不同的数据特征，我的电梯实现了LOOK算法，使得在Random和Night模式下都能达到较优。对于Morning模式，我使其在第一层时等满6人再出发（除非输入已经关闭）。之后在研讨课上我通过同学的分享，将Morning状态下的电梯加上没有乘客就自动回到一楼的特征，优化了性能。

​我的Elevator类与其它线程的交互只通过一个WaitingList类的实例，且功能比较稳定，在之后的两次作业中都没有较大的改动。之后的的工作都集中在如何给每个电梯的WaitingList分配Request，也就是调度器的设计。

第二次作业

​第二次作业是无差别的多电梯。调度器主要的功能有与输入进行交互，与电梯进行交互，管理电梯。

与输入进行交互

​电梯线程与输入线程通过共享资源InputList的实例进行交互。调度器将InputList中的Request合理的分配给每个电梯的WaitingList。当InputList中有元素时进行分配，没有时通过wait-notify等待新的请求到来，如果输入关闭了，则分配完后就关闭

与电梯进行交互

​每一个电梯线程都对应有一个WaitingList实例，调度器将合理地分配请求，将请求放入每个电梯对应的WaitingList中，每个电梯独立工作。当调度器将InputList清空且自身关闭后，改变WaitingList中一个属性，使得电梯在处理完自己的等待队列后关闭，线程都结束后程序关闭。

管理电梯

​首先是管理添加电梯。在调度器的构造方法和发现增加电梯请求是调用增加电梯的函数，将电梯用ArrayList容器管理起来，同时为每个电梯创建一个等待队列，new一个电梯，将等待队列作为电梯的成员。这样这个等待队列就成了特定电梯和调度器的共享对象。此外，为了更好的分配资源，WaitingList中还有对应电梯的层数和在电梯中的乘客人数，这样调度器通过访问这些数据，可以更好的安排请求的分配

​关于请求的分配，我将三种情况用switch分成三种情况，相互相对独立，相同的部分抽象成private方法，避免代码的重复，提升可维护性。

    public void run() {
        for (int i = 0; i < elevators.size(); i++) {
            elevators.get(i).start();
        }
        switch (type) {
            case "Morning":
                morningDispatch();
                break;
            case "Night":
                nightDispatch();
                break;
            default:
                randomDispatch();
        }
    }

• Random下，我采取检测到请求到来就即时分配的方法，优先将请求分配到目前等待队列最少的电梯中，如果相同，则分配到电梯内人数最少的电梯中。

• Night下，由于乘客请求会一次性全部到来，且加电梯的请求会在任何时候到来，如果一次性就分配好的话，那么新加的电梯就不会起到作用。所以我实现了延迟分配的方法。

  • 当检测到请求来的时候，先对InputList排序，这样可以将同一楼层的请求尽量分配到同一个电梯，减少开关门的时间
  • 每当一个电梯到达1楼时，给它分配6个乘客。为了照顾乘客较少的情况，当InputList中元素小于18个时，就开始进入Random的分配方法，防止有的电梯分配到了六个乘客，有的电梯提早进入空闲状态。
  • 当InputList中放入增加电梯请求时，把请求放到队头，尽快的添加电梯

• Morning下，我采取当等到InputList中有六个请求时分配一次，分配给当前在一楼或者即将最早到达一楼的的电梯，输入关闭后剩余的一些请求采用Random分配

第三次作业

​这次作业本来是想要实现换乘功能的，但是在实现中发现需要考虑的情况太多，难度较大，极容易发生错误，所以我最后还是放弃了。在第二次作业的基础上进行了改进，主要改了以下几点

• 改了一下分配策略，将满足C电梯的请求全部分配个C电梯，其余的请求满足B就分配个B电梯，其余分配给A种电梯。
• 对电梯做了改进使其能成为三种不同的电梯，将每种电梯的特殊属性用构造方法在初始化时根据不同的状态进行初始化，为了保险，还对电梯的停靠楼层、准入请求做了限制（其实调度器做的好的话电梯不会在不该停的楼层停，进不该进的人
• 对调度器的分配方法做了一定改进，由于乘客种类不同，Morning情况下不再等满人再出发，等2秒后就直接出发。还有其他一些为了满足功能但不属于核心思路的改动，不再赘述.

3.架构分析

UML类图

UML协作图

​从UML图和UML协作图中可以看出MainClass中创建见了调度器Disaptcher和请求输入队列InputList，并随后忘输入队列中加入请求，调度器创建电梯Elevator和等待队列WaitingList

扩展性分析

​首先是两个共享对象类WaitingList和InputList，这两个类其实是ArrayList包装后实现的线程安全类，其中根据需要加入了一些特殊的方法，比如InputList.waitForNext()当容器为空时等待下一个输入，若空且关闭则返回false，还有可以排序且优先增加电梯请求的InputList.put()。这两个类可以扩展更多的方法来满足更高的要求，具有扩展性。

​电梯类Elevator具有很好的扩展性，其功能已经比较完备，是一个相对独立的类，只与等待队列进行交互。其运行的参数，可到达的楼层，最大人数等特性都是用成员变量来保存，实现不同的功能修改这些成员变量即可。

​调度器由于是根据题意来尽量做优化的，比较具有特殊性，但也具有一定的扩展性。用ArrayList管理电梯及其请求队列，可以创建数目不限的电梯。调度算法相对独立，但其中一些常用的代码以及抽象为private方法，在修改算法时也可以调用。

4.Bug分析

我出现的Bug

​在前两次作业中，强测在正确性上没有问题。第三次作业中出现了一个写Comparator的错误，这个错误使得在某些情况下会抛出异常，不过好在只有一个测试样例抛出了异常，如果运气不好损失就惨重了。

​我在InputList中实现了sort方法，使得能让增加电梯的请求排在最前面，然后按照请求的起始楼层从高到低将请求排序，以提高效率，但是在写Comparator时没有return 0；只返回了1和-1两种，这样可能会导致在不同情况下两个元素的顺序发生冲突，抛出异常。

​所以以后在写sort函数的Comparator时，一定要写三种返回值，当两个元素在某种比较方法下相等时，就要返回0；

关于测试

这一单元感觉互测难度比较大，也确实比较忙（懒），在互测中并没有测试出别人的bug。

但对于我自己程序的正确性我还是做出了一些测试。基本思路就是先用上一次强测的数据测试一下我程序的正确性，再出一些边界数据，比如只满足一种电梯的数据，看看其余电梯是否会参与进来。不同模式下对于大量聚集在某些楼层的数据，看看能不能按我设想的那样调度。不过总体来看，测试还是比较弱的。

5.心得体会

​第二单元相较第一单元，我解除了全新的概念，从对多线程一无所知到好歹也能写出个强测分还可以的电梯程序，还是收获了很多的。在思考和debug的痛苦过后，也得到了收获的成就感。

​多线程的学习真是打开了新世界的大门，让我能用一个全新的视角去理解计算机程序的运行过程，加上OS最近也在学进程的并发，让我更立体的学习了线程切换，线程安全等概念。尤其是线程安全，我也了解了不同的加锁方法及它们的优缺点，希望在之后的学习中能将它们灵活的应用在程序之中。还有关键的一点就是如何避免轮询，对于wait-notify机制的灵活运用，也让我初步学会了多线程提高效率的基本方法。

​这一单元的结束也是学习多线程编程的开始，在实际应用中，大部分的程序都需要用到多线程，而我对多线程的认识还非常的浅薄，还需要在以后学习更多。