在本课程Unit2中,我们需要迭代开发一个多线程电梯调度系统,实现运送乘客、临时调度和双轿厢改造的需求。
同步块&锁
同步块设置和锁的选择
同步块通过method-level synchronized
或block-level synchronized
的方式实现,锁的粒度较细;同步块的范围通常是对共享资源的访问或修改操作,如SubList
类中对于乘客的操作。未使用显式锁(如ReentrantLock
等),完全依赖synchronized
关键字实现线程同步。
处理语句的关系
一方面使用同步块保证包含添加和删除操作的处理语句的原子性;另一方面,在同步块中结合wait()
和notifyAll()
方法实现线程之间的协调。考虑到可能导致死锁问题,没有使用notify()
方法。
尽量控制锁的范围,使之仅包含对共享资源的处理,避免不必要的性能开销。
调度器
调度器设计与交互
尽管第一次作业不需要调度,但考虑到后续作业大概率需要实现调度,在第一次作业中就构建了调度器类。为了匹配调度器逻辑,设置了主请求表和副请求表,分别容纳全局请求和每个电梯各自的请求。调度器线程与输入线程和电梯线程构成两个“生产者-消费者”模型:
- 输入线程是生产者,向主请求表中添加请求信息;调度器是消费者,从中取出请求信息。
- 调度器是生产者,在指派电梯后将对应的请求信息添加进副请求表;各电梯线程是消费者,从各自的副请求表中取出请求信息。
调度策略
第一次作业直接调度输入指定的电梯,各电梯采用LOOK策略进行运营。
第二次作业和第三次作业中,根据调度时刻各电梯状态进行评估,将乘客分配给从时间角度最合适的电梯。因此,无法对耗电量指标进行控制。分配策略大致为取得电梯的关键状态信息(如所在楼层、方向、是否满员等),设置很简单的参数进行打分,分数越低越好。最终将乘客指派给分数最低的电梯。
由于加入RECEIVE限制,我在第二次作业中为各电梯设置了主请求的概念。电梯从停止状态转向移动状态时,先从副请求表中选择一个乘客作为主请求,将其RECEIVE。这之后电梯可以自由移动,在接送主请求的路上顺带捎带乘客。如果决定要捎带某乘客,临时RECEIVE之再进轿厢即可。
架构模式
逐步变化和未来扩展能力
三次作业架构变化不大,基本保持稳定。
前面提到,第一次作业各电梯采用LOOK策略进行运营,设置了Strategy
类用于向电梯线程反馈当前应当执行的动作。但后两次作业采用主请求模式,不再需要Strategy
类,而是变成了如图所示的状态机。
最终UML类图如下图所示。按照需求变化,第二次作业和第三次作业相应地增设了Schedule
类和Update
类用于包装新增请求类型的信息。
为了给电梯打分,需要获得各电梯当前的状态。因此使用Building
类容纳全部电梯线程,便于统一获取数据。而这个类只需要进行一次实例化,因此采用单例模式。
在三次作业中,整体采用的“生产者-消费者”模型十分稳定,是符合电梯调度情景的框架;然而,具体的调度方法和电梯内部的运行细节易变,需要根据需求不断调整优化。
根据指导书提示,在迭代开发时将临时调度和双轿厢改造视为一个动作,连续、不间断地完成响应操作。因此,新增的需求只需要在Elevator
新增一个状态,并添加其对应的handle()
方法即可,未来可扩展性较高。但是,需要注意Elevator
类内的代码臃肿问题,目前已逼近checkstyle对类行数的限制。
此外,电梯设计在多方面为未来更改作出了预留,例如电梯容量capacity
可以更改,方便对电梯款式进行多样化处理。
UML协作图如下:
双轿厢改造
同步开始改造
在第三次作业中,新增设了SharedFloor
类,记录当前已准备好开始改造的电梯数量,其方法均使用synchronized
关键字修饰。所有电梯接到Update请求时,在下一次ARRIVE后立刻开始做Update预备(清理所有乘客)。
预备后,并根据SharedFloor
中的计数判断是否需要进入wait()
,如不需要则说明另一部电梯更快完成了预备,唤醒对方。
指定电梯A负责输出信息,电梯B在此期间进入wait()
。A输出完毕后唤醒B,两部电梯分别放置在共享楼层上下,开始改造后的运营。
碰撞防止
在SharedFloor
中设置信号isOccupied
。
每当被改造的电梯试图进入共享楼层时,首先判断该信号是否为真。若为真则说明另一台电梯目前在共享楼层,进入wait()
以防止碰撞;若为假,则可以放心进入。
每当被改造的电梯离开共享楼层时,将isOccupied
信号置为假,并notifyAll()
以唤醒可能存在的等待线程。
电梯进入共享楼层后,会主动在下一次行动时沿反方向离开共享楼层,杜绝越界运营和一个电梯无限期占用共享楼层的情况。
bug相关
自己的bug
- 第二次作业在极端情况(电梯在顶层接到前往可调度范围内最底层或反之的临时调度请求,速度为0.5)下,$T_{complete}$会超过6s。这是因为我在开始响应临时调度前会开关门处理一次乘客,让轿厢内不顺路的乘客下车,轿厢外顺路的乘客上车。但在极端情况下,电梯赶路的时间就已耗去4s,留给其他操作的时间并不富裕,容易导致超时。我在最初通过停用调度前处理完成了bug修复,后改为先判断调度请求跨越楼层数量是否在可接受范围内,再进行调度前处理。
- 第三次作业概率触发死锁问题,因为电梯打分后遇到多个相同分数电梯时会随机分配,导致死锁问题较难复现。直接重交通过了bug修复,但是事后分析原因发现是电梯在处理输入末尾的Update请求时有可能陷入
wait()
状态,无法被唤醒。在研讨课上,同学分享可以设置一个定时唤醒各进程检查结束的时钟,避免无限期等待,这是一个可行的解决方式。
debug方法
主要使用print法进行调试。因为debug时各线程都遇到过问题,所以print的地方较多。参考助教在课程群内建议,保险起见增设了GlobalData
类管理debug模式和最终上交模式,防止因输出调试信息浪费评测机会。
心得体会
线程安全
经过本单元三次作业的迭代,我对于多线程开发有了初步了解。保证线程安全主要有两方面工作:实现同步互斥和避免死锁问题。
实现同步互斥的方法很多,但我在本单元作业采用了比较保险的synchronized
关键字,没有出现过线程不安全的问题。但是共享数据的形式不同,适用的锁的粒度也不同,可以在这一方面进行优化。
典型的死锁情景是两个线程分别拿到两把锁,并都试图再获取对方手上的那把锁,我在设计过程中有意避开了这种情况。此外,理论课上老师提出为避免死锁可以全部使用notifyAll()
,我采用了这一方法,前两次作业没有出现死锁问题。但是最后一次处理Update请求时,逻辑上的漏洞导致可能出现电梯响应Update后没有新的输入请求,无限陷入等待的情况。
层次化设计
“生产者-消费者”模型具有清晰的层次结构,以第二组模型为例,从负责“生产”的分配器线程,到充当“托盘”的共享数据侯乘表,再到“消费者”电梯线程,它们的职责划分清晰,结构明了。这一点带来的好处是debug时能比较容易地确认问题所在位置。例如遇到乘客“消失”的情况,在分配器线程中添加输出,发现成功指派到某一电梯,就说明问题出在电梯线程。
总结本单元开发过程,我初步了解了多线程开发的技术,并进一步加深对于层次化设计的理解,在理论和实践两个层面均有所收获。