第一次作业
1、线程安全
由于写第一次作业时刚刚学完多线程,理解不透彻,生怕出错,于是就直接暴力synchronized
,凡是访问共享数据地方全都用同步代码块,且同步块的范围很大。
如上图,这是电梯线程类的run方法,其中synchronized
块套住了while(true)
内电梯的整个决策部分,只剩下电梯状态的执行过程(开关门、移动)没在同步块中。锁对象是电梯自身的等待队列。
输入线程和调度器线程中同步代码块的设置类似。
这样的好处是电梯线程对其等待队列的访问绝对线程安全,因为可能访问table
(等待队列)的代码全都在同步块中(决策过程)。
坏处显而易见,整个程序到处都是synchronized
块,可阅读性、可维护性非常差。且由于synchronized
块过大,以上面的电梯线程为例,整个决策过程中,电梯线程一直占用锁,此时调度器线程无法向table
(等待队列)中写入乘客,并发性、性能较低,而实际上电梯的决策过程中只有一部分访问了table。
2、调度器设计
电梯运行策略采用的是标准的ALS算法
由于第一次作业只有一部电梯,调度器只需将总队列的乘客,全部原封不动的传输给电梯的等待队列即可,并在输入结束且总队列为空后,将end
信号传递给等待队列。本次作业中电梯的等待队列是定义在main函数中的,并未封装成线程安全类,仍需用synchronized
块确保对等待队列的读写是线程安全的。
3、bug分析
本次作业未出现多线程相关bug。
被强测和互测测出了一个逻辑bug,在Random
策略中,电梯在开门后判断乘客能否上电梯时,因逻辑错误,导致主目标可能会在错误楼层进入电梯。(本次作业为ALS捎带策略)。
这一bug与我if else
逻辑混乱直接相关,因为我写算法非常不熟练,if else
是想到一点写一点,没有完整的逻辑链,很大概率会被特殊情况hack,在被hack后,我不仅重写了此处的判断逻辑,还修改了其他策略的判断逻辑,让if else
能形成逻辑判断链,确保后面的if
是基于之前的if
逻辑、覆盖所有可能性,既提高可读性又提高鲁棒性。
第二次作业
1、线程安全
基于上次作业中同步块的设置缺点,我在本次作业中将table
(等待队列)封装成类,并配置访问方法,所有有线程安全问题的方法都加上了synchronized
,并在table
中设置了保证线程安全的遍历方法(直接拷贝ArrayList
并返回给调用者),还将原本位于电梯线程中判断是否终止电梯线程、电梯线程wait的逻辑放入table
类中(这个增加了电梯与等待队列的耦合)。
最终清除了电梯类和策略类中所有的synchronized
块,同步块中的内容大幅减少,可读性、可维护性、并发性大幅提升。当然加锁、释放锁也更加频繁了,由此也会带来性能开销,此问题将在下一次作业得到一定程度的解决。
由于本次作业出现多台电梯,每台电梯都对应一个电梯线程对象和等待队列,为方便管理,我设置了ElesAndTables
类,其中存放着所有的电梯对象和电梯等待队列(各个Elevator和Table对象),并将该类也设置为线程安全类。
2、调度器设计
现在看来这次,作业的调度设计,从性能上讲,很糟糕,梯与乘客的距离、电梯内与其等待队列的人数等因素,通过一个方法,为每一个乘客对每一个电梯都计算出一个权重,找到对应权重最大的电梯,然后将该乘客加入此电梯的等待队列,再计算下一个乘客... 从性能角度考虑,我的调度器有如下缺点。
-
不能确定电梯能否捎带乘客
这次作业中,对于电梯运行策略,我仍然采用的是ALS捎带策略,这使得在调度器中,不能通过电梯运行方向、人数和乘客信息判断能否捎带,还需要从电梯的策略类中获取到目标乘客,而策略类会不时修改这一目标乘客,这就有线程安全问题,就要加锁了,复杂度、耦合度可想而知。而且目标乘客还有可能是
null
,导致算法失效。理论上,效率较高的调度策略,应优先考虑能否捎带,再考虑其他因素,所以有在调度器不能判断捎带的缺点。 -
其次是各个因素间的权重难以决策
电梯内人数、电梯等待队列人数、电梯距离乘客的距离、能否捎带等等因素之间的权重该如何分配?哪个因素应起到更大的作用?难以把握。 -
我的调度器只平衡人数、距离,只有宏观调控,而没考虑捎带
一个乘客能否被捎带、捎带的较优运输方案,往往在其被输入时,仅靠一次调度决策,难以判断出来,而我的调度器会在乘客输入后,立刻将乘客分配到某一电梯的等待队列,其他电梯都无法感知到这名乘客,显然这一决策过程是静态的的、过于宏观的,只能用于平衡人数。所以不少情况下,等待队列中的乘客实际上并未被合理分配。
对于第一个缺点,我在下一次作业中进行了处理,将电梯策略类中目标选取策略、捎带策略全部改为类似look算法的模式(但“主目标”这一设定不能改,毕竟引导电梯运行还是要靠目标乘客),并加入isUp
布尔变量以供查询电梯运行方向,就可以不管目标乘客,而只根据电梯运行方向、所在楼层、乘客信息来判断能否捎带。
针对第二、三点缺陷的可能解决方案(前提是缺点一已经解决)
-
只将判断为可捎带的乘客放入决策出的电梯的等待队列,其余无法判断的乘客就先留在总队列里,乘客绝不会进入没有空位的电梯的等待队列(“没有空位”指电梯内人数和等待队列人数之和等于电梯容量)。
这其实就是在模拟“电梯选乘客”的思路,相当于将调度器和*竞争策略相结合(或者说在*竞争策略上,加个调度器和等待队列,避免电梯赛跑,同时使竞争拥有更加全局的调度视角),毕竟谁也没说过调度器就只能“乘客选电梯”。 还可以理解为,捎带决策的前移,即原本电梯线程中,策略类的捎带操作,被前移到了调度器中,让乘客经历的第一次调度就考虑了捎带因素,电梯就只负责消耗乘客了。
但假如不同电梯有不同的捎带策略,那这一方案扩展性较差的缺点就暴露了,因为调度器只有一个,将调度器与捎带绑在一起,则意味着捎带策略也只能有一个了,但是这可通过细化调度器职责,将调度器判断捎带、状态管理、分配乘客等任务分成几个类来解决。
-
每过一段时间或因某条件触发,将每个电梯的等待队列里的乘客取出到总队列中,再次让调度器执行调度算法进行调度,以破除调度器一次性分配的静态特性,实现动态调度。实现难度较大
由于我精力有限,下次作业中只是将原先的ALS算法修改的很像LOOK算法(LOOK比ALS快一些),未能对此调度器进行修改,调度器仍未尝试判断能否捎带,因为在上述提到的三个缺陷中,缺陷2和3无法解决,就算将捎带因素加入调度策略,对调度效率的提升效果也不大。
3、bug分析
本次作业在强测、互测、同学的评测机上均未被测出bug
第三次作业
1、线程安全
本次作业中ElesAndTables
类被大幅增加内容,其作为最复杂、被访问最频繁的共享对象(从后面的协作图即可看出),若仅仅采用synchronized
块来确保线程安全,显然并发度较低、效率较低,因为synchronized
块是互斥锁,读-读
之间也互斥,但读与读之间并没有安全问题。
鉴于此问题,我在此次作业中,将ElesAndTables
类中的同步代码块全部换为了读写锁。
2、调度器设计
我的调度器采用的是最简单的静态换乘,思路是先分类再找电梯。
-
首先按照乘客的起点和终点为乘客安排电梯的类型。比如,3-16层的乘客,我会先将其分配到C类电梯运到18层,然后由A类电梯往回运两层。又比如5-14层的乘客,会先用B类电梯运到13层,再由A类电梯运到14层。一般情况下,若乘客能用B类或C类电梯直达,就不会换乘了。
-
当然调度器也包括应对特殊数据的缓冲措施,其实就是一堆特判。比如一次性给了30个3到18层的乘客,肯定不能只让C类电梯运,其他电梯围观看戏。当C类电梯的人数是B类电梯的2倍时,就会把C类后续乘客交给B处理。C对A类、B对A类、A对B类均有类似处理,就是为了避免电梯看戏的情况。
-
确定乘客的电梯类型后,利用上次作业的调度器方法(这应该就是开闭原则吧),在该类型的所有电梯中选择出一个合适的电梯 ,将乘客放入其等待队列。
但换乘是有代价的、大量特判是很危险的,比如输入只有从1-16的一名乘客,B类电梯会把乘客运送到15层,然后A类电梯再从1层跑去15层去接乘客,最后A类和B类都跑了一趟,而且是A类等到B类到达才出发,这比直接用A类运送还慢得多。
解决办法即是减小换乘的力度,一般情况下,奇数到奇数的给B类,奇数到偶数、偶数到奇数都交给A类。如果发现A类人数与B类人数的比值小于某一数值,则也把奇数到奇数的交给A类。若B类比A类闲的多,则把奇-偶、偶-奇的乘客交给B类处理。毕竟,论运力,A类电梯没比B类慢多少,虽然速度慢,但运载量大。
缺点也显而易见,除了我在上面第二次作业指出的调度器缺陷,“静态换乘”也会导致不少无效甚至负优化的换乘,理由同样是因为乘客刚输入,难以一次就能判断出合理的换乘路线。
3、可拓展性分析
-
Random
策略在优化后也支持Night
模式最优解,同时考虑到个人能力不足,Morning
策略优化起来效果不佳,为确保正确性,本次作业只用Random
一个策略,损失性能 - 没有采用动态换乘,因为本人能力有限,太容易出错,牺牲性能换正确性
- 为了能实现换乘,策略类的父类调用了调度器也会调用的方法,该方法位于调度器线程和电梯线程的共享对象中,相当于在换乘时,策略类中又调度了一次,这无疑增加了耦合度,影响可拓展性
- 由于调度器中用了大量的if else来尽可能特判,若电梯规则有所变化,这些特判很可能需要重写,可扩展性极差。
- 捎带决策过程仍交给电梯线程的策略类处理,调度器只负责宏观的电梯人数、距离平衡,用性能换简单、正确性。
- 电梯的构造方法包括很多参数,虽然看上去很复杂,但当输入的电梯参数是动态的、不确定的时候,我只需将构造方法的一部分参数放到输入端口就行。
- 如果修改电梯楼层上下限,比如改到20层以上,或者负数层,我完全无需修改任何代码,因为电梯怎么移动是根据乘客,只要输入合法,电梯移动就合法。
- 由于不存在
synchronized
块到处飞的情况,将容器都封装成了线程安全类,就算架构有所变动,出线程安全问题的几率也较小 - 从协作图即可看出,输入线程、调度器线程、电梯线程间均有共享对象隔开,耦合度较低,不至于略微修改代码就"动全身"
- 由于采用了状态模式,对电梯状态的管理非常简洁容易,就算电梯新增一些奇怪行为,比如突然停电宕机、坠梯等,也就是新增状态类而已,仍然能保持清晰的状态转移逻辑
- 由于策略类独立性较高,电梯线程可以支持动态切换策略
- 未使用工厂类,在创建对象时,创建过程与所在类的耦合性较大
4、bug分析
本次作业未被强测hack,但在互测中被hack,原因是java 1.7 后Collections.sort()
方法所需要的比较器,必须要在两元素相等时return 0
,否则会可能抛出异常。
心得体会
通过本系列作业的学习,我理解了多线程的基本概念,深入学习了生产者-消费者模式,掌握了基本的线程安全控制、通信技巧(内置锁、逻辑锁、读写锁),学会使用“状态模式”简化对多状态的管理。对“层次化设计”有了更为深入的理解。锻炼了业务分析能力。