OO 第二单元总结

第二单元的任务是设计一个电梯调度的程序，需要我们设计调度方法以便在相对较短的时间内将乘客送到目的地。主要应用多线程的知识，包括多线程中的同步和互斥，以及避免出现死锁。理解线程间如何进行通信以及如何保持通信的安全，就已经完成了本单元任务的大部分。

第一次作业

作业思路

第一次作业我认为是这三次作业之中最难的，第一次应用多线程进行编程，需要选取一个合适的模式。借鉴课程上机内容，选取的是生产者消费者模式，据老师理论课介绍，这个模式能够解决大部分工业界的问题，可见有其优势。

在第一次作业中，就加入了调度类Shedule，这一部分在第一次作业中作用不是很明显，只是根据楼座对乘客进行了分配。关键类在于CustomerQueue和Elevator。CustomerQueue这个类是生产者消费者的集中体现，这之中应用notifyAll和wait来进行通信。Elevator是运送乘客的核心类，判断何时加入乘客，放出乘客。将这三个类分开，程序的策略拓展性更高，无论应用什么策略，电梯部分的输出都是符合股则的。策略主要是包括ALS，LOOK等算法，每一种算法都有其优越型，可以进一步优化以便性能更高。

类说明

|- Mainclass：主类
|- Shedule：调度器，将读入的乘客请求进行分类，加入到相应的等待队列
|- InputThread：读入线程，负责从控制台中读入请求，加入乘客到等待队列
|- Elevator：电梯线程，是消费者角色，从等待队列中拿取请求进行处理
|- PeopleOn：电梯乘客集合，管理电梯上的人
|- Customer：乘客类
|- CustomerQueue：等待队列线程，负责管理没有上电梯的人，是关键的类

多线程设计

本次作业共有三个线程，InputThread，Shedule和Elevator，这三个线程共享一个线程安全对象CustomerQueue。CustomerQueue是本次作业中唯一上锁的类，也是生产者消费者模式中的关键部分。这一个类主要作用在于从输入中读入乘客请求，将其加入到等待队列。同时提供Elevator拿取乘客，是一个线程安全的类。

当没有请求时，各线程进入到wait状态，当有请求加入是，notifyAll唤醒这些线程。在电梯内部，执行Thread.sleep来模拟电梯开关门和升降楼层。在这期间进行乘客的加入等行为，这种方式比较好控制也比较好理解，不会出现未关门就上下乘客的问题。同时也很易拓展后续的电梯停靠时间进行改变的问题。

调度器设计

第一次作业通过Shedule类进行进行调度，这一次主要是根据不同乘客的起始楼层将乘客请求进行分配，分配到每一楼座电梯对应的请求队列当中。实现的比较简单，但是为了后续作业的拓展，加入了这一部分。

调度策略

本次作业选择了LOOK算法进行调度，首先是将电梯内乘客运送到目的地，运行期间如果有同方向的请求，就将此乘客进行捎带。电梯空后，继续检索同方向是否有乘客请求，如果有继续沿此方向运行，没有则改变方向。LOOK算法没有先来先上这一规则，只是凭借电梯状态和乘客请求进行调度，更符合正常的思考模式。

类图与时序图

第二次作业

作业思路

在大体框架上第二次作业相对于第一次作业没有很大的变化，仍然采用的是生产者消费者模式，在调度器部分，仍然是判断乘客做横向电梯还是竖向电梯，将其分配到相对应的电梯等待队列之中。但第二次又存在每一层有多个电梯的情况，这里的分配策略就是那个等待队列人少就将乘客加入其中。

采用的调度策略仍然是LOOK算法，改变在于增加了横向电梯的类，横向电梯的类与竖向电梯类似，只是在应用LOOK算法时要考虑循环的情况，”最高层“是根据当前楼层改变的，实现的时候要小心考虑，否则会出现死循环的问题，这一部分在Bug分析部分进一步详述。

调度器设计

这一部分与第一次作业相类似，唯一改变的是调度策略。

调度策略

这次作业实现的是每一个电梯都对应一个等待队列。在分配时，同一层或者同一栋中哪一个队列中的人少就将新的乘客加入其中。这样实现相对来说能够让每一个电梯都处于运作状态，更加充分的运用了资源。

在设计的时候，也考虑过应用自由竞争的策略，但是遇到了CPU的tle问题。当时没能够发现问题的原因，就为采用这一中方式。后来明白是不适当的加入了notifyAll导致出现轮询问题。但从评测来看，这两种方法的性能没有相差很多。

类图与时序图

第三次作业

作业思路

本次作业结构仍没有很大的改动，只是在Shedule类中加入了一个容器存储所有的横向电梯，以便在调度的时候确定要中转选择的横向电梯。在增加横向电梯时要对这里进行处理。

同时在每个乘客类内部加入三组记录起始地址的变量，前两次都只是记录起始的和终止的，这一次加入中间状态。在Shedule进行乘客请求分配的时候，根据乘客的需求即是否需要换成将中间状态的两个变量进行赋值，LOOK算法进行分析时变为分析起始状态和中间状态。当一个乘客从电梯下来时，将其起始状态更改为当前位置对应的数值，判断这时起始和终止的状态是否相同，如果不相同将这个乘客继续加入到CustomerQueue等待队列进行继续的处理，直至这个乘客处理完成。

调度策略

总体的调度策略仍然是将乘客进行分配，对于需要换成的乘客，分析每一层的横向电梯，如果存在可以到达的电梯，就将乘客在这一层进行换乘。但这里我犯了一个大错误，就是对于换成，在分析哪一座楼层可以到达横向的目的时，考虑了每一个电梯能够到达的楼座。但是在将乘客加入横向电梯的时候，却没考虑这一点。如果一层横向电梯有两个，一个可到达，另一个不可，此时就会出现问题。

类图与时序图

BUG分析

第二次作业

强测时没有发现问题，但是在互测是被hack，问题在应用LOOK算法的时候，没有考虑到底层是在时刻改变的，比如在此时电梯在E，但是在D，B，A，都有请求的时候，就出现了循环问题，因为电梯在D坐又要到B坐，然后又到A，如循环，导致超时。解决很简单，在LOOK判断加入一点判断即可。

第三次作业

如上所说，虽然在换成判断横向电梯的时候考虑了横向电梯呢能否到达的问题，但是在将乘客加入到横向电梯的时候，却没考虑这个横向电梯能否到达，出现问题，只需要在横向电梯加入乘客时候进行判断即可。

互测BUG分析

如下是一些自己构造的查找BUG的数据，每一次都能够有所收获。

判断电梯调度是否正确：

ADD-floor-10-3-4-0.6-18
ADD-floor-11-3-4-0.6-31
ADD-floor-13-3-4-0.6-24
1-FROM-B-5-TO-E-7
2-FROM-B-5-TO-E-7
3-FROM-B-5-TO-E-7
4-FROM-B-5-TO-E-7
5-FROM-B-5-TO-E-7
6-FROM-B-5-TO-E-7

判断电梯是否超载：

ADD-floor-10-3-4-0.6-18
1-FROM-B-5-TO-E-7
2-FROM-B-5-TO-E-7
3-FROM-B-5-TO-E-7
4-FROM-B-5-TO-E-7
5-FROM-B-5-TO-E-7
6-FROM-B-5-TO-E-7
7-FROM-B-5-TO-E-7
8-FROM-B-5-TO-E-7
9-FROM-B-5-TO-E-7

对于线程锁的一些理解

多线程很关键的一步就在于进行同步，这一单元的作业里主要是应用synchronized这一关键字，以下是一些我对锁的总结。

方法锁

这一部分里synchronized修饰类里面的方法，相当于锁这个类即this

public synchronized void method() {
}

代码块形式

如下的obj可以是类里面的某一变量或者是容器，锁住这个变量，以便不同线程间都能得到这个变量的最新值。

synchronized (obj) { 
}

类锁

public static synchronized void method() {
}

这种方式只要是这个类实例化出的对象都共有一个锁，无关乎是否有相同的对象名。

public synchronized void method() {
}

这种就只是锁住同一个对象。锁发挥的作用相对于上面要小很多。

心得体会

多线程应该是真正生活中应用很多的一种代码模式，感觉编写多线程，主要是考虑哪些对象要进行上锁即要时时同步，大抵可包括这两种，check then act ，read modify write。将正确的对象上锁，多线程就不会出现那些死锁等很难找到bug所在的问题。

虽然刚接触多线程感觉很难，但是在调试的时候越来越理解多线程的同步等问题。感觉还是很满足的。

这单元的作业相对于第一单元完成的很好，有很大的进步，希望在接下来的单元里能够继续的认真学习。