第二单元面向对象作业——性感电梯在线吃人

part 1：单部可捎带电梯

多线程设计策略

本次电梯仅仅只有一部运行，因此，在多线程的设计中难度不大，并且，只需采用一对一的生产者-消费者模型即可解决问题。整体的设计大致为：输入线程作为生产者不断接受外部请求并投入托盘容器中；调度器线程起到了托盘容器的作用，并在电梯运行中辅助实现可捎带功能；电梯线程为消费者，接受乘客的请求，并不断计算目标地点和进行自身移动的处理。

在实现中，为了使电梯线程能够正确结束，在输入线程结束前夕，要对电梯线程发送状态信息，在电梯无任何需要处理的工作后，若检测到输入线程已结束运行，则结束自身生命，随之，调度器这个守护线程也一并结束。

三个线程的主要共享资源为请求等待队列的一个linkedlist容器，简单的对他上锁，即可保证基本的线程安全。而输入和电梯之间的一个信号传递，也是依靠共享资源进行的，这里需要注意的是：

while (persons.isempty() && queue.isempty()) {
    if (queue.getnomorereq()) { return; }
    synchronized (queue) {
        try {
            queue.wait();
        } catch (interruptedexception e) { e.printstacktrace(); }
    }
}

在电梯结束的判断和睡眠的执行中，可能会被打断，在这个时刻中，输入线程刚好完成了结束标志的设定，并再次唤醒“睡眠中的电梯”，结束自身运行，此时，控制权返回给电梯，电梯继续执行，进入睡眠，于是，线程进入永久的睡眠，无人再唤醒他了。为了避免这种情况的发生，最好对上述代码用一个同步块套起来。

算法：对于单部电梯来说，我认为如果容量没有限制，那么总是去接送或者去满足最近的请求，会有着非常好的效果。首先，这种方法可以避免电梯去接一个偏远的请求而浪费时间，倒不如解决完邻近密集请求，在空闲时再处理较远的请求。同时，这样也能避免新来的请求可能在你的反方向，而去向却和你的目的大致相同的情况导致走太长回头路的问题。

可扩展的架构设计

• srp（单一责任原则）

  main类只负责初始化和线程的启动，input负责对外部请求的获取、分析，并放入托盘，output专门为一些封装的输出函数，scheduler负责乘客的分配，elevator类只用决定去向和自己的移动。整体来说，较好的满足了srp原则。

• ocp（开放封闭原则）

  由于首次作业的架构简单，并且个人认为后面作业的架构设计中，personrequest并没有变化，并且不打算实现多级调度器，因此，个人认为ocp原则暂可无需满足，也就不预留任何借口或抽象类。

• lsp（里氏替换原则）

  同上，第一次中没有派生类相关结构。

• isp（接口隔离原则）

  同上，大部分类都设计为单例模式，电梯在设计中唯一被他人所调用的部分是对电梯门状态的判断，isp原则暂时无需满足。在需求不确定的情况下，设计接口是一件困难的事情。

• dip（依赖倒置原则）

  在我的实现中，三个主要的工作类属于并行的状态。

静态代码分析

• 代码规模

  type name	method name	loc	cc	pc
  main	main	10	1	1
  elevator	elevator	9	1	1
  elevator	run	23	5	0
  elevator	up	10	1	0
  elevator	down	10	1	0
  elevator	open	14	1	0
  elevator	close	10	1	0
  elevator	move	10	3	0
  elevator	retarget	25	6	0
  elevator	getfloor	3	1	0
  elevator	getdoor	3	1	0
  elevator	addperson	4	1	1
  elevator	removeperson	7	2	0
  scheduler	scheduler	4	1	2
  scheduler	run	18	3	0
  requestqueue	pull	11	2	0
  requestqueue	peek	11	2	0
  requestqueue	offer	4	1	1
  requestqueue	getnomorereq	3	1	0
  requestqueue	isempty	3	1	0
  requestqueue	setnomorereq	3	1	1
  requestqueue	getrequestat	13	3	1
  requestqueue	containrequestat	8	3	1
  requestqueue	getrequestto	13	3	1
  requestqueue	containrequestto	8	3	1
  requestqueue	findminfrom	16	4	1
  requestqueue	findminto	16	4	1
  input	input	4	1	1
  input	run	23	3	0

• 复杂度分析

  type name	nof	nom	loc	nc	dit	lcom	fanin	fanout	ocavg
  main	0	1	12	0	0	-1	0	4	1
  elevator	8	12	138	0	0	0	2	2	2
  scheduler	2	2	26	0	0	0	1	2	2
  requestqueue	2	12	113	0	0	0.16667	4	0	2.3333
  input	1	2	30	0	0	0	1	1	2
  output	0	6	20	0	0	-1	1	0	1

• uml类图

  

  本次设计了input、output、elevator、scheduler以及requestqueue这几个类，首先，保证了input、scheduler和elevator三个线程类具有较低的耦合性，这从类图和上述度量分析中都能看出。其次，设计了output类专门用来封装输出函数，可以很好地进行代码复用。同时，构造了requestqueue，对容器进行线程安全的数据管理，因此在设计中会稍微复杂一些。总体上看，整个设计的耦合性较低，分工明确，在未来可能具有的新的功能中，也不是难以扩展的。

• uml协作图

  

  main线程主要用来初始化和启动线程，这在设计部分已经阐述过。主要的线程协作部分在于输入、调度和电梯线程。具体内容如上。

bug分析

• 自己程序中的bug

  本次作业中在公测和强测中都没有bug出现，并且除了策略部分提到的一个关于线程安全的点，在代码编写中也十分顺利，但是在帮助同学查找bug时，发现了一种有问题的线程同步方式，我们在读取输入的请求时，如果现阶段没有输入，则会阻塞住等待下一个输入的到来，而有的同学将这条由外部包所实现的阻塞语句包含在了内部代码的临界区中，导致其他线程一直无法获得锁，直到读取到eof退出临界区，其他程序才得以复活，这是极为不可取的。

• 互测中的bug

  此次互测极为安静，只有1、2个hack点。多线程的hack不能像以前的程序一样做特殊样例了，可能在不断的随机数据中，才会引发程序的不安全的线程问题。我利用python生成随机数据，并解析时间点定时发送给待测程序，以达到模拟评测机的效果，然而，运气不好，没有hack到别人。

  在互测结束后，看到别的同学hack到的数据，结合他们的代码可以看出，主要问题不是线程安全带来的，而是调度算法出了bug，这是此次作业的主要bug。

part 2：多部可捎带电梯

多线程设计策略

本次作业仅仅改变了电梯的数量，在请求到来前会提供给程序需要启动的电梯数量。本次线程安全主要在于多个电梯对共享资源的竞争问题，然而，我的设计中，即使直接生成并启动多个电梯，也能够保证线程安全。

算法：单电梯调度依旧为前一次作业的处理最近请求，对多个电梯的乘客调度，我选择了争抢式的实现方式。在最初实现时，我计划利用person类构造一种被标记但是未进入电梯的状态，来调度乘客进入电梯，然而，由于电梯有着一定的容量限制，不能很好地将乘客标签化的分配，同时，由于我的单部电梯调度算法的原因，电梯的走向不如look算法那样稳定，因此这种设计带来了巨大的麻烦。于是我想到给每部电梯单独建立等待队列的方式，让每个队列只与特定的那个电梯可见，简化了标签化乘客带来的极其复杂的条件判断，但是，结果确实残酷的，这么搞根本没有让电梯自己去争抢乘客的方法快，我想原因大致是强测中的数据随机性很高，这样争抢让电梯可以较为平均的分布在每一层，使得局部请求能够快速处理，以此提高了性能。

可扩展的架构设计

• srp（单一责任原则）

  此次程序框架与第一次基本相同，仅仅是将原来的容器单独拆分出来，设计独立的等待队列和电梯舱体，较好的完成了srp原则。

• ocp（开放封闭原则）

  这次电梯仅仅要求是增加数量，与第一次类似，没有涉及扩展性（对下次作业的要求已经了解了，打算用多参数的constructor和工厂模式实现不同电梯的扩展）。

• lsp（里氏替换原则）

  同上，没有继承或实现的类。

• isp（接口隔离原则）

  同上。

• dip（依赖倒置原则）

  在我的实现中，三个主要的工作类属于并行的状态。

静态代码分析

• 代码规模

  type name	method name	loc	cc	pc
  main	main	15	2	1
  elevator	elevator	9	1	1
  elevator	run	23	5	0
  scheduler	scheduler	4	1	2
  scheduler	run	19	3	0
  scheduler	containrequest	11	4	0
  requestqueue	getrequestat	11	3	1
  requestqueue	containrequestat	8	3	1
  requestqueue	findminfrom	16	4	1
  person	person	6	1	4
  person	getpersonid	3	1	0
  person	getfromfloor	3	1	0
  person	gettofloor	3	1	0
  person	getstatus	3	1	0
  person	setstatus	3	1	1
  passengerlist	passengerlist	3	1	1
  passengerlist	getrequestto	11	3	1
  passengerlist	containrequestto	8	3	1
  passengerlist	findminto	16	4	1
  input	input	4	1	1
  input	run	31	5	0
  input	getelevatornumber	3	1	0

• 复杂度分析

  type name	nof	nom	loc	nc	dit	lcom	fanin	fanout
  main	0	1	17	0	0	-1	0	0
  elevator	10	13	148	0	0	0	0	0
  scheduler	2	3	38	0	0	0	0	0
  requestqueue	0	3	37	0	0	-1	0	0
  person	7	6	30	0	0	0	0	0
  passengerlist	0	4	40	0	0	-1	0	0
  input	3	3	43	0	0	0	0	0
  output	2	5	19	0	0	0	0	0

• uml类图

  

  其他类的职责和依赖关系基本与第一次相同，唯一的改动是将原来的托盘容器拆分出来，让他只去完成作为托盘的使命，而passengerlist则去完成管理电梯内乘客的使命，并且增加的person类，更好地管理和封装请求。没有一个接口确实不是很专业，但个人认为，没有一个庞大的任务需求作为前提，强硬的加入接口去实现，有种臃肿且杀鸡用牛刀的感觉。

• uml协作图

  

  本次线程间的协作与第一次类似。

bug分析

• 自己程序中的bug

  本次公测和强测中依旧没有bug出现，性能分也不差。在实现此次任务中，如策略一节所述，我有实现过其他两种方法，然而可以明显感觉到，给乘客制定标签，会让多个线程的共享资源异常的多，对于资源锁的处理不仅麻烦，而且漏洞百出，另外，那种实现破坏了整个架构，遂放弃。单独为每个电梯提供独立等待队列的方法，让线程间的共享资源保持在了第一次的水准上，大大简化了锁的设置，然而，在性能上的劣势让我放弃了他，但这种设计是第三次完成的基础。

• 互测中的bug

  此次互测房间内依旧很安静，仅仅只有4刀之少，大部分同学的问题都是调度中失去了方向导致不断地死循环。有一位同学是由于线程的过早结束，导致乘客没有结束运送，获得了wa。本次依旧使用暴力的自动化评测，没有刀到人，由于没有精力深入代码的原因，放过了这些有问题的同学。

part 3：多部多类别动态增设可转运电梯

多线程设计策略

本次电梯增加了允许停留的层数，改变了不同类型电梯的容量、速度等参数，我构造了一个工厂类完成了对不同类型电梯的构造。由于有些电梯无法接送乘客所在地或目的地的，因此利用第二次作业实现的电梯分离式请求队列，将每次到来的请求进行分析并送入合适的电梯等待队列中，而每个单独的队列依旧采用最短请求算法（同前两次）。在选择合适的电梯时，我采用优先选择能够直达的电梯，但由于for循环的固定性，这样可能导致多个同种电梯的等待队列过于拥挤，因此使用了collections.shuffle()对电梯容器进行打乱，这种随机打乱的方式利用随机性很好的保证了乘客请求进入电梯等待队列的平均分布。

本次电梯线程间的共享资源增加了电梯容器这一部分，由于电梯增加指令的引入，管理所有电梯的容器在不断增加（修改），而我们为了调度乘客请求，也需要不断遍历这个容器，然而，这个容器的使用不需要要保证读写前后的次序问题，只需要保证对他的读写是一个原子性操作即可，因此我使用了copyonwritearraylist来保证操作的原子性，同时，这个容器在使用for循环时可以删除容器内元素而不会产生异常，让某些操作变得更加简单。

可扩展的架构设计

• srp（单一责任原则）

  这次程序的各个类基本与第二次没有太大差异，主要是elevfactory的增加，来进行电梯的初始化，并且修改了scheduler，让其主要职责为将inputqueue中的请求分配给合适的电梯等待队列。较好的满足了srp原则。

• ocp（开放封闭原则）

  电梯种类的加入，让每个电梯都有自己不同的属性，这个词汇告诉我们，实际上电梯的具体功能没有任何改变，变化的只有移动时间、可达楼层、载客容量这些电梯具有的属性，我们的方法以及其内部的代码不需要做任何的改变，因此，这次扩展我直接利用构造器修改具体field，不进行类的继承。虽然确实没有满足ocp原则，但ocp原则的适用性也是需要考虑的。

• lsp（里氏替换原则）

  理由同上，但是，从第一次作业以来，我都保证了在调度不断替换的情况下，电梯不需要做任何改变，就可以进行适配，也许这是一种lsp更广泛的抽象（大嘘。

• isp（接口隔离原则）

  同上，没有接口啊。

• dip（依赖倒置原则）

  电梯章节各个类的依赖关系其实十分特殊，在我的实现中，没有一种通用的类去做接口让高层次的类依赖。例如，托盘这个类和电梯内部乘客的容器这个类，对他们的调用中，主要在意的分别是乘客的所在地、目的地，这是两种完全不同的需求，因此，我没有做一个接口。

静态代码分析

• 代码规模

  type name	method name	loc	cc	pc
  elevfactory	createelevator	19	4	3
  inputqueue	inputqueue	2	1	0
  inputqueue	run	27	5	0
  inputqueue	getinstance	3	1	0
  inputqueue	personinit	11	3	1
  inputqueue	putqueue	4	1	1
  inputqueue	takequeue	11	2	0
  main	main	9	1	1
  elevator	elevator	14	1	6
  elevator	run	23	5	0
  scheduler	scheduler	2	1	0
  scheduler	run	22	4	0
  scheduler	getinstance	3	1	0
  scheduler	isoff	3	1	0
  scheduler	setoff	3	1	1
  scheduler	tellallelevatorsoff	5	2	0
  scheduler	allelevatorsareempty	8	3	0
  scheduler	schedule	46	10	1
  requestqueue	getrequestat	13	3	1
  requestqueue	containrequestat	8	3	1
  requestqueue	findminfrom	16	4	1
  passengerlist	passengerlist	4	1	2
  passengerlist	offer	12	3	1
  passengerlist	getrequestto	13	4	1
  passengerlist	containrequestto	8	3	1
  passengerlist	findminto	16	4	1
  passengerlist	isabletoberth	3	1	1

• 复杂度分析

  type name	nof	nom	loc	nc	dit	lcom	fanin	fanout	ocavg
  elevfactory	3	1	24	0	0	0	2	2	5
  inputqueue	3	6	63	0	0	0.67	4	4	2.16667
  main	0	1	11	0	0	-1	0	3	1
  elevator	13	17	191	0	0	0	2	5	1.94118
  scheduler	4	8	98	0	0	0.375	3	5	2.875
  requestqueue	0	3	39	0	0	-1	3	1	3.33333
  person	9	10	46	0	0	0	5	0	1
  passengerlist	1	6	59	0	0	0.67	1	2	2.66667
  output	1	5	18	0	0	0	2	0	1

• uml类图

  

  对于类的构造，基本上其职责与依赖与第二次相同，主要增设了elevfactory工厂类来根据电梯类型初始化和启动电梯线程，整个结构的设置，依赖关系的处理，以及各个类的解耦，都做得不差，唯一的缺憾可能是没有一个接口在我的实现之中，对于接口，我还是保留个人观点，但是在后续可能出现的需求中，例如乘客的不同行为、调度器可能实现多级调度，以及电梯类型进一步的多样化（不能只改变参数了，实现起来意义不大），确实需要接口来保证设计的美观和合理。

• uml协作图

  

  协作方式基本不变，改变了传输停止信号的方式。

bug分析

• 自己程序中的bug

  本次强测中没有bug，但是在互测中被抓住了一个遗留了三次作业的bug，在调度中将对乘客所在地的获取，错写成了目的地的获取，在极为特殊的例子中，产生了死循环。线程安全部分没有问题出现，但其实，只要清晰地明白各个线程的共享资源情况，以及运行时的顺序依赖，就可以构造安全且无死锁的并发代码，有时候，画一画写一写，真的有助于自己的理解。

• 互测中的bug

  这次互测hack别的同学的策略，除了两次都没有意义的自动化测试工具，我决定在他们的代码中查找线程安全的问题，于是，好巧不巧，发现了一位认为电梯的名字只有“x1”、“x2”、“x3”的同学，于是我构造了一个会导致tle的数据，即47个从-3到20的乘客请求，并且加入了x10、x11、x12三个a类电梯，万万没想到，他直接runtimeerror了，但又抓出两位似乎不能很好处理一次性大量相同请求的调度的同学，他们各个都tle了。个人认为，大家的问题大多都在于调度算法的bug，线程安全做的确实不差。

part 4：收获与感想

这个寒假中，在随意学习java的过程中，小小的做了一个im即时通讯聊天软件，可以满足在互联网上的一对一的单人聊天，并且保存离线聊天记录，支持上线好友提醒，以及消息通知等，这个软件是我对多线程的第一次尝试，对多个线程的资源竞争和死锁等知识还不怎么了解，本来以为多线程啊也不过如此，在这三次电梯作业的迭代开发中，我才真正体悟到并发程序真正的困难所在，我们在这个单元的学习中，主要需要解决的困难，就是对共享资源的同步，以及线程空闲时的等待和安排任务后的唤醒，多线程的理解不难，个人认为，难度在于你有时不能考虑到共享资源附近可能出现的所有线程竞争的情况，少考虑一点，程序就有可能崩掉。

其次，接着上面的话，我觉得课程的安排似乎缺少了一点关于并发程序中过大的同步区域导致的性能问题，其实，一步步分析代码，尽可能减小临界区的大小，或者使用乐观锁、高级的并发容器等java自带的实现功能，来接近更快速、更高效的并发执行，这也是我们日后工作中可能遇到的问题，高并发、高可用、高性能，将会是未来程序开发的难点之一。

最后，回顾三次作业，收获了不低的强测分数，也更加了解了多线程的韵味儿，唯一略微遗憾的是，在这三次开发中，没有体会到明显的设计感，想要做一个要接口有接口，要派生类有派生类、层次分明、结构清晰的框架，但由于多线程的安全问题需要仔细考虑、又耗费着大量时间思考调度的安排，当然个人认为有一点点原因在于题目需求的电梯实际上不需要如此复杂的设计吧。《java编程思想》这本大黑书随着课程推进少了一章又一章，希望最后的我有一个崭新的改变吧。

如对本文有疑问， 点击进行留言回复！！