BUAA_OO_Unit2_单元总结

OO-Unit2 电梯调度

hw5

写在动手之前

在开始本次作业之前，需要明确几个问题：

1.需要哪些线程

首先自然是6个电梯6个线程，然后便是输入线程

2.有哪些共享对象

因为乘客都已经分配给某个电梯了，乘客自然就不能算共享对象，因为乘客只独属于某个电梯（线程）。那么还有什么算共享对象呢，笔者觉得应该是任务列表类。输入线程把读到的请求写到任务列表里面，6个电梯线程对任务列表进行读操作，获取属于各自的请求，完成请求后写回任务列表。

综上所述，整体框架就已经很明确了，在MainClass类里面，需要把6个电梯线程Elevator依次启动，再把输入线程InputThread启动，每个电梯线程有一个自己的任务列表QuestList，然后InputThread就根据请求的要求（电梯id）来把请求放到人物列表中，由电梯去完成

整体架构

第一次作业类图如图所示，整体按照生产者-消费者模型去搭建的，美中不足的一点是笔者没有写分配器类，这样这个作业的可迭代性就不好

同步块设计与锁

第一次作业笔者只是用了synchronized关键字，并没有使用其他的锁。

如图所示，笔者只在QuestTable里面用了synchronized方法，使得InputThread和Elevator线程对其操作是线程安全的。java目前的实现中synchronized的效率也是很高的，所以这种方法很清晰。不过荣老师上课讲过，最好应该是使用synchronzied代码块来上锁，这样更清晰，可拓展性也好，不要在方法上上锁。

电梯调度

本次作业笔者主要采用了LOOK策略，逻辑如下

if (/*电梯内有人要出电梯或者电梯外有人要进电梯*/) {
            return Operation.OPEN; // 电梯开门
        } else {
            if (/*电梯内有人*/) {
                return Operation.CONTINUE; // 电梯按当前方向继续运行
            } else { // 电梯内没人
                if (/*所有电梯的任务表都为空*/) {
                    if (/*所有请求都已完成*/) {
                        return Operation.END; // 电梯终止运行
                    } else {
                        return Operation.WAIT; // 电梯等待
                    }
                } else {
                    if (/*当前方向上还存在请求*/) {
                        return Operation.CONTINUE; // 电梯按当前方向继续运行
                    } else {
                        return Operation.REVERSE; // 电梯掉头
                    }
                }
            }
        }

Opreation是一个枚举类，用来规定电梯的各种动作。

顺带一提，生活中绝大多数的电梯执行的都是LOOK策略。

此外，笔者还实现了电梯踹人的策略，也就是在同方向上，若是电梯已满，且门外有优先级比电梯内高的请求，两者交换一下。第一次作业没有RECEIVE的要求，该方案实现起来非常简单。

代码量和类复杂度分析

第一次作业的代码量整体比较少，集中在Elevator类和QuestTable类中。

Elevator类，QuestTable类和Scheduler类的复杂度都比较高。其中Elevator.run()中有while循环和大量if条件判断，而Shceduler类中的existQuest方法和nextOperation方法也是如此，所以复杂度比较高。

值得注意的bug

笔者在实现电梯的过程中没有什么印象深刻的bug，不过在互测中找到了别人的bug。我们知道，当我们对一个容器进行边遍历边移除的时候，会发生ConcurrentModificationException，因此我们需要使用迭代器来遍历。然而当两个线程同时对某个容器进行操作的时候，即使使用了迭代器，依然会有CME错误。因此，对共享类进行严格的线程安全保证是很重要的。

hw6

整体架构

类图如上图所示

这一次的作业整体要复杂一点，首先不再为每个乘客规定电梯了，其次对电梯也增加了临时调度请求，整体的复杂度很高，笔者也几乎写了整个清明节假期

这一次加入了新的线程Manager，用来将每个请求分配给电梯。

调度算法

在浏览往届学长学姐的帖子的时候，偶然发现了这个学长的博客，学到了一个经过合理建模后的打分算法，整体体验下来效果很好，不逊于影子电梯。主要逻辑如下

//返回的分数为电梯从当前楼层出发到接到乘客共运行的楼层数
//在QuestScheduler里取分数最低的电梯分配该乘客
public int getScore(Quest quest) { 
    if (/*乘客需求方向与电梯运行方向相同*/) {
        if (/*电梯内人数+与电梯运行方向相同的剩余任务数<电梯容量*/) {
            if (/*电梯无需掉头即可接到乘客*/) {
                return /*电梯当前楼层与乘客出发楼层之差的绝对值*/;
            } else { //需要掉头
                return /*电梯运行一圈的楼层数-电梯当前楼层与乘客出发楼层之差的绝对值*/;
            }
        } else { //电梯这趟接不到乘客
        	return /*电梯接到乘客需要遍历的圈数x电梯运行一圈的楼层数-电梯当前楼层与乘客出发楼层之差的绝对值*/;
            }
        }
    } else { //乘客需求方向与电梯运行方向相反
    	//...
    }
}

经过笔者的优化，笔者将电梯运行一圈的楼层数做了一个期望计算，最后的结果约为9-10之间，最后选择了9。第六次作业的强侧得分为95.25分，整体结果还算满意。

除此以外，整体的调度算法没有改变，一个值得注意的点，就是本次作业的RECEIVE要求使得踢人的实现变得略有复杂，再经过长时间的优化而一直出bug之后，笔者有点自暴自弃，干脆放弃了此策略

另外有一个让人笑话的点，就是笔者没有想到可以在接收到SCHE时就把电梯内部的乘客放出，反而是让乘客全程跟着电梯跑去临时调度的目标楼层，浪费了一些性能分。

代码量和复杂度分析

可以看到本次作业的代码量一下子就上去了，最多的是在Elevator类里面，对于实现RECEIVE和SCHE花费了大量的精力和代码。

通过复杂度也可以看出，Elevator类确实变得过于复杂，其中主要是打分算法有较多的条件判断等。而执行分配调度的Manager类也是如此。

值得注意的bug

本次主要的bug有一个，在中测结束前通过笔者的评测机发现了。有时候，电梯可能会同时输出一个RECEIVE和一个SCHE-BEGIN。最后检查发现是在执行临时调度的开始阶段，笔者把锁挂在了电梯身上，而不是未完成请求列表，这导致分配线程在此期间还可以房屋内未完成请求列表，并把一个请求分配给该电梯。而对于笔者的实现，输出RECEIVE是交给分配器的，因此会导致同时输出。

在互测中，笔者发现同房间同学的一个有趣的bug。该同学似乎为了追求性能，尽量在输出SHCE-BEGIN前多跑几层楼。因此，笔者构造了一个跨度较长的SCHE请求，把电梯卡在极限距离，让该电梯的相应SCHE时间超过规定时间了。

hw7

如何处理轿厢不碰撞

经历过前两次作业的折磨之后，这个问题其实很容易想到解决办法。笔者在电梯内部新建一个TargetFloor对象，对于同一个井道的两个电梯，它们共享这一个楼层。笔者令到达换乘层的电梯获取换乘层对象的锁，在离开该层时释放换乘层对象的锁。需要注意的是，到达与离开均以输出为标准

如何实现双轿厢电梯

笔者的实现十分的不优雅。

调度器分别把这个update请求交给A、B两部电梯，两部电梯同时开始改造，分别放出其内部的乘客、修改参数信息（最高到达楼层等），而这个过程中的UPDATE-BEGIN等，均由A电梯来进行输出，不过很快笔者就发现这样的实现是有问题的。

尽管两部电梯同时接受到了来自调度器的请求，但这不能保证两部电梯可以同时进行UPDATE，或者说UPDATE的进度能保持一样，这就导致了有可能当A电梯已经输出了UPDATE-BEGIN的时候，B电梯还在放出客人；或者当A电梯尚未输出UPDATE-END的时候，B电梯已经完成了改造，开始RECEIVE乘客了。

笔者最后采用了这样的方法：对于一个update的请求，其内部设置三个方法，分别是UPDATE的准备、开始和结束。每个方法要求两部电梯都执行一次，才会使得电梯同步进入下一阶段。其实更优雅的方法就是把输出也放置到这些方法中，但笔者没有更改。

整体架构

类图如上所示，架构较上一次作业没有太大变化。

代码量和复杂度分析

第七次作业代码量突破了1000行，其实整体上还是有东西可以合并的，在代码块中有几处重复或者高度相似的代码段。主要集中在Elevator类里面。

作业整体的复杂度也很高，集中在电梯、调度器等。为了迎合双轿厢电梯的改造，Scheduler，即电梯行为的指示器，复杂度也变高了。

值得注意的bug

本次作业出现的有趣的bug都在开头部分交代了。在强测和互测中均没有跑出bug。

同步块和锁

本次作业中，笔者主要使用的都是synchronized关键字。在第六次作业的实现过程中，笔者初步尝试了使用读写锁，但是在自己评测的过程中出现了很多难以修复的奇妙bug，遂作罢，改回synchronized。另外，对于很多私有变量，我使用了AtomicBoolean以及AtomicInteger，降低了锁的使用频率。java保证了对这些变量的读写都是原子性的。

bug以及debug方法

本次电梯单元，笔者是无伤通关，强测互测均没有出现bug。对于debug，笔者有一些自己比较好用的方法：

1. 调试输出
   多线程的bug并不能稳定复现，而且也不能通过打断点的方法去debug，因此我们可以进行调试输出，也就是在一些关键地方输出一些能反映线程参数的信息。比如在线程结束时，让线程输出end等，这样可以观察有哪些线程可能没有正常结束，进而发现程序中的缺陷
2. 代码走查
   代码走查指的是在代码写完之后通读代码全体，检查代码潜在的bug。笔者主要通过这种方法来寻找可能出现的线程不安全问题，也确实用这样的方法成功的查漏补缺了。
3. 构造评测机
   自动化评测对于多线程问题来说，笔者认为是必要的。大量的测试点才有可能测出多线程项目中潜在的问题，人工构造的测试点并不总能很好的”压迫边界“。构造评测机方法，详情可以看笔者的讨论区帖子，抑或是已经同步更新的博客。

心得体会

经历了面向对象和操作系统的双重折磨，笔者算是对多线程有了一点理解。对于多线程编程，同步与互斥，也就是线程安全，是多线程编程最核心的内容之一。

笔者在测试中没有发现自己的任何有关线程安全的bug，这主要归功于在开始学习多线程编程之前，笔者对线程问题进行了细致系统的学习。尽管如此，笔者也并不认为自己对线程安全已经完全掌握。本次作业并发程度并不高，共享资源并不复杂，尚且没有达到生活中常见的多线程问题（12306），只能说对多线程初窥门径。

层次化设计

本次作业的核心架构没有离开多线程架构中经典的生产者-消费者模型，而经历了操作系统的学习之后，这样的模型其实还有更多、更复杂、同样很精巧的模型。

层次化设计要求编程者自顶向下对整个设计任务进行分层分块，并对每层每块分别建类实现。高层的类只关注抽象后的功能调用，而底层的类则负责每种功能的具体实现。这样的做法在降低每层代码的复杂度发同时也会增加程序的代码总量，所以应该合理平衡代码复杂度与代码量。

本次作业中，我的层次化设计整体还算比较好，每个类负责的功能比较单一，类间逻辑比较清晰。但其实还可以做的更好，有很多可以继续抽象的地方尚可优化。