在本课程Unit2中,我们需要迭代开发一个多线程电梯调度系统,实现运送乘客、临时调度和双轿厢改造的需求。

同步块&锁

同步块设置和锁的选择

同步块通过method-level synchronizedblock-level synchronized的方式实现,锁的粒度较细;同步块的范围通常是对共享资源的访问或修改操作,如SubList类中对于乘客的操作。未使用显式锁(如ReentrantLock等),完全依赖synchronized关键字实现线程同步。

处理语句的关系

一方面使用同步块保证包含添加和删除操作的处理语句的原子性;另一方面,在同步块中结合wait()notifyAll()方法实现线程之间的协调。考虑到可能导致死锁问题,没有使用notify()方法。

尽量控制锁的范围,使之仅包含对共享资源的处理,避免不必要的性能开销。

调度器

调度器设计与交互

尽管第一次作业不需要调度,但考虑到后续作业大概率需要实现调度,在第一次作业中就构建了调度器类。为了匹配调度器逻辑,设置了主请求表和副请求表,分别容纳全局请求和每个电梯各自的请求。调度器线程与输入线程和电梯线程构成两个“生产者-消费者”模型:

  1. 输入线程是生产者,向主请求表中添加请求信息;调度器是消费者,从中取出请求信息。
  2. 调度器是生产者,在指派电梯后将对应的请求信息添加进副请求表;各电梯线程是消费者,从各自的副请求表中取出请求信息。

调度策略

第一次作业直接调度输入指定的电梯,各电梯采用LOOK策略进行运营。

第二次作业和第三次作业中,根据调度时刻各电梯状态进行评估,将乘客分配给从时间角度最合适的电梯。因此,无法对耗电量指标进行控制。分配策略大致为取得电梯的关键状态信息(如所在楼层、方向、是否满员等),设置很简单的参数进行打分,分数越低越好。最终将乘客指派给分数最低的电梯。

由于加入RECEIVE限制,我在第二次作业中为各电梯设置了主请求的概念。电梯从停止状态转向移动状态时,先从副请求表中选择一个乘客作为主请求,将其RECEIVE。这之后电梯可以自由移动,在接送主请求的路上顺带捎带乘客。如果决定要捎带某乘客,临时RECEIVE之再进轿厢即可。

架构模式

逐步变化和未来扩展能力

三次作业架构变化不大,基本保持稳定。

前面提到,第一次作业各电梯采用LOOK策略进行运营,设置了Strategy类用于向电梯线程反馈当前应当执行的动作。但后两次作业采用主请求模式,不再需要Strategy类,而是变成了如图所示的状态机。

97d9c9b8c4f17a75faa61bc729e7ee7

最终UML类图如下图所示。按照需求变化,第二次作业和第三次作业相应地增设了Schedule类和Update类用于包装新增请求类型的信息。

为了给电梯打分,需要获得各电梯当前的状态。因此使用Building类容纳全部电梯线程,便于统一获取数据。而这个类只需要进行一次实例化,因此采用单例模式。

在三次作业中,整体采用的“生产者-消费者”模型十分稳定,是符合电梯调度情景的框架;然而,具体的调度方法和电梯内部的运行细节易变,需要根据需求不断调整优化。

image-20250418230240665

根据指导书提示,在迭代开发时将临时调度和双轿厢改造视为一个动作,连续、不间断地完成响应操作。因此,新增的需求只需要在Elevator新增一个状态,并添加其对应的handle()方法即可,未来可扩展性较高。但是,需要注意Elevator类内的代码臃肿问题,目前已逼近checkstyle对类行数的限制。

此外,电梯设计在多方面为未来更改作出了预留,例如电梯容量capacity可以更改,方便对电梯款式进行多样化处理。

UML协作图如下:

Sequence

双轿厢改造

同步开始改造

在第三次作业中,新增设了SharedFloor类,记录当前已准备好开始改造的电梯数量,其方法均使用synchronized关键字修饰。所有电梯接到Update请求时,在下一次ARRIVE后立刻开始做Update预备(清理所有乘客)。

预备后,并根据SharedFloor中的计数判断是否需要进入wait(),如不需要则说明另一部电梯更快完成了预备,唤醒对方。

指定电梯A负责输出信息,电梯B在此期间进入wait()。A输出完毕后唤醒B,两部电梯分别放置在共享楼层上下,开始改造后的运营。

碰撞防止

SharedFloor中设置信号isOccupied

每当被改造的电梯试图进入共享楼层时,首先判断该信号是否为真。若为真则说明另一台电梯目前在共享楼层,进入wait()以防止碰撞;若为假,则可以放心进入。

每当被改造的电梯离开共享楼层时,将isOccupied信号置为假,并notifyAll()以唤醒可能存在的等待线程。

电梯进入共享楼层后,会主动在下一次行动时沿反方向离开共享楼层,杜绝越界运营和一个电梯无限期占用共享楼层的情况。

bug相关

自己的bug

  1. 第二次作业在极端情况(电梯在顶层接到前往可调度范围内最底层或反之的临时调度请求,速度为0.5)下,$T_{complete}$会超过6s。这是因为我在开始响应临时调度前会开关门处理一次乘客,让轿厢内不顺路的乘客下车,轿厢外顺路的乘客上车。但在极端情况下,电梯赶路的时间就已耗去4s,留给其他操作的时间并不富裕,容易导致超时。我在最初通过停用调度前处理完成了bug修复,后改为先判断调度请求跨越楼层数量是否在可接受范围内,再进行调度前处理。
  2. 第三次作业概率触发死锁问题,因为电梯打分后遇到多个相同分数电梯时会随机分配,导致死锁问题较难复现。直接重交通过了bug修复,但是事后分析原因发现是电梯在处理输入末尾的Update请求时有可能陷入wait()状态,无法被唤醒。在研讨课上,同学分享可以设置一个定时唤醒各进程检查结束的时钟,避免无限期等待,这是一个可行的解决方式。

debug方法

主要使用print法进行调试。因为debug时各线程都遇到过问题,所以print的地方较多。参考助教在课程群内建议,保险起见增设了GlobalData类管理debug模式和最终上交模式,防止因输出调试信息浪费评测机会。

心得体会

线程安全

经过本单元三次作业的迭代,我对于多线程开发有了初步了解。保证线程安全主要有两方面工作:实现同步互斥和避免死锁问题。

实现同步互斥的方法很多,但我在本单元作业采用了比较保险的synchronized关键字,没有出现过线程不安全的问题。但是共享数据的形式不同,适用的锁的粒度也不同,可以在这一方面进行优化。

典型的死锁情景是两个线程分别拿到两把锁,并都试图再获取对方手上的那把锁,我在设计过程中有意避开了这种情况。此外,理论课上老师提出为避免死锁可以全部使用notifyAll(),我采用了这一方法,前两次作业没有出现死锁问题。但是最后一次处理Update请求时,逻辑上的漏洞导致可能出现电梯响应Update后没有新的输入请求,无限陷入等待的情况。

层次化设计

“生产者-消费者”模型具有清晰的层次结构,以第二组模型为例,从负责“生产”的分配器线程,到充当“托盘”的共享数据侯乘表,再到“消费者”电梯线程,它们的职责划分清晰,结构明了。这一点带来的好处是debug时能比较容易地确认问题所在位置。例如遇到乘客“消失”的情况,在分配器线程中添加输出,发现成功指派到某一电梯,就说明问题出在电梯线程。

总结本单元开发过程,我初步了解了多线程开发的技术,并进一步加深对于层次化设计的理解,在理论和实践两个层面均有所收获。