第一次作业

调度器设计

本次作业使用两个线程实现，即输入线程和电梯工作线程，在一个工作线程中处理单部电梯的调度运行。

电梯轿厢（Cabin）对象记录了电梯的所在楼层、剩余容量、是否开门、上次开门时间、到达当前楼层时间等信息，用于模拟一部可由外部控制调度且行为满足题目约束的电梯，提供进出乘客和移动等方法。

一个调度器（IScheduler）实例持有一个 Cabin 对象，并提供 assign 和 work 公有方法，支持外部向其分派乘客请求，以及根据当前 Cabin 的状态和内部剩余的请求控制电梯移动一步，运送乘客。针对 Morning 和 Random 到达模式，设计了两种实现 IScheduler 接口的调度器类 MorningScheduler 和 GeneralScheduler，其中 GeneralScheduler 实现了 LOOK 调度算法，MorningScheduler 则采用类似装饰器的实现，在人未满时等待，否则调用内部创建的 GeneralScheduler 进行调度。

工作线程（Worker）再次包装了 IScheduler 对象，通过内置的 BlockingQueue 实现线程通信。输入线程通过调用其 assign 和 interrupt 方法，可向其分派乘客请求或发送结束信号，其实现均为将请求对象加入队列，可使用特殊的空对象表示结束信号。run 方法中的主循环不断从队列中取出可用请求并分派给调度器，并控制调度器进行移动。若调度器空闲且尚未收到结束信号，则调用 BlockingQueue 的 take 方法，阻塞至下一请求到达。

这一设计下，调度器总在单线程环境中，实现中无需考虑线程安全性；Worker 遵从生产者-消费者模式，仅使用 BlockingQueue 进行线程通信，相比手动实现共享对象更为安全简便。

同步块设计

同一 Monitor 下的所有同步块具有互斥性，从而当对同一共享对象的操作都在同步块内时，都可视为原子操作。本次作业中，仅使用标准库提供的阻塞式队列进行线程通信，没有直接使用不安全的共享对象，故无需显式使用同步块。

第二次作业

调度器设计

本次作业中，为了实现多部电梯，在输入线程和工作线程（Worker）之间加入了分派器（Dispatcher）一层，作为一个单独的线程存在，从而各电梯的调度机制基本无需修改。分派器同样持有 BlockingQueue 用于请求传递，由输入线程向分派器发送请求。对于新增电梯请求，分派器将创建新的工作线程；对于乘客请求，分派器将请求分派给某一工作线程。由于题目中的数据范围较小，CPU 时间比较宽松，此处在分派时枚举各 Worker，获得其中调度器（IScheduler）的副本对象，模拟计算其获得新请求后的总周转时间，找到用时最少的电梯作为分派目标。

同步块设计

Worker 需要在电梯移动的每步后复制并保存调度器的状态，从而可随时获取调度器副本用于模拟。该对象在工作线程和分派器线程间直接共享，因此需要在更新和获取时使用同步块。

课程提供的输出接口本次需要在多个工作线程中使用，也需要使用同步块保证调用的线程安全性。

第三次作业

调度器设计

为了实现换乘，在请求类中存储了回调函数对象，调度器需要在请求完成后进行回调。分派器在需要换乘时，向 Worker 分派两个请求，在前一请求中附加回调函数，用于分派后一请求。同时，还需要向后一请求预期的承运 Worker 发送伪请求（Hint），使其在空闲时向换乘点移动。规划换乘时同样使用了模拟方法，枚举换乘点并计算总周转时间，从而确定是否换乘以及换乘位置。

同步块设计

本次作业的同步块设计与前一次作业相同，没有引入新的同步块。

类图

线程时序图

Listener 在主线程内执行，共使用了 (电梯数量 + 2) 个线程。

可扩展性分析

本单元作业中，始终使用了集中分派请求的调度方法，主要通过消息传递进行单向通信。相比自由竞争式调度，这种方式下的线程通信更简单安全，但为了防止性能退化，需要设计较稳定的调度策略。通过将电梯的状态转移、单部电梯的运行逻辑和高层的请求分派尽可能分离，该架构具有一定的可扩展性，在三次作业的迭代过程中，基本满足开闭原则，便于调整或测试不同的电梯运行逻辑和分派策略，但由于该架构以集中分派为前提，有其局限性，需要涉及自由竞争乘客的调度策略将很难通过较少的修改实现。

测试策略

主要使用 Python 脚本构造数据并通过管道通信进行自动测试。由于多线程环境下 Bug 的复现概率更低，需要构造大量的数据进行并行测试。为了提高运行时的并发性，程序支持从外部传入速度倍率，并将 Thread.sleep 等调用中的时间除以该倍率，从而可减少测试用时，同时更容易暴露出潜在的 Bug。

在开发过程中，由于尚未熟悉 BlockingQueue 的用法，我曾引入单独的 Monitor 对象来实现空闲时的 wait-notify 机制，但由于未与结束信号标志正确进行同步，可能导致输入结束后仍进行 wait，造成了潜在的死锁。通过添加同步块，可修复此问题，但最终直接使用了 BlockingQueue 提供的阻塞式方法进行等待，从而无需自行实现 wait-notify 机制。在三次作业的公测和互测中，没有发现 Bug。

互测环节中同样使用该方法进行测试，发现了其他同学程序中的 CTLE 以及电梯未正常结束导致的 RTLE 问题，但并非每次运行都能复现，需要多次提交数据。

心得体会

线程通信机制是本次作业架构中需要考虑的重点。在层次化的设计中，造成线程不安全的因素主要是共享对象的使用，其根本原因在于对共享内存的连续操作未能保证原子性。在实际实现时，我也体会到设计可在线程间安全共享的对象十分困难，需要缜密地考虑外部可能的调用方式并实现同步机制，而这将引入类间额外的耦合性，与面向对象的设计原则相悖，当在后续扩展功能的实现中复用该类时，不同的调用方式可能引起潜在的线程安全问题。

在现代主流的并发范式中，主要通过使用安全的队列进行消息传递，从而在高一级抽象之上进行共享内存，有效解除耦合，使生产者和消费者间不存在并发竞争。基于这一思想，我在本次架构中避免了直接共享复杂的容器对象，主要借助标准库提供的 BlockingQueue 进行线程通信，从而避免了难以调试的线程安全性问题，也使设计具有较强的可扩展性，与第一单元相比，花在调试和功能迭代上的时间明显减少。在多线程环境下，需要在架构层次的早期设计中兼顾线程安全性，在数据冗余和逻辑耦合间权衡，选择合理的线程通信机制。