OO_Unit2_多线程

一、同步块 与 锁

在本次实验中，仅使用了如下两种形式进行同步：

 //format 1
 synchronized (lock) {
     // code block
 }
 //format 2
 try {
     lock.wait();
 } catch (InterruptedException e) {
     e.printStackTrace();
 }
 //in other code block
 lock.notifyAll();

不同线程在访问共享资源时可能发生写入冲突，因此使用同步块与锁来控制共享资源的访问——同一时刻只能由一个线程对该共享资源进行读写（使用读写分离模式可以提高效率，因为只有写操作可能产生冲突）。

关键字 synchronized（同步锁）：对所有同步控制区域加上同步锁（同一线程对同一对象锁是可重入的，且同一线程可以多次获取同一把锁——支持多次重入）。通常在 synchronized 控制区域中配套使用 wait - notify / notifyAll 方法避免轮询。

若某一线程访问共享资源时发现锁被其他线程持有，则使用 wait 进行等待以防止轮询消耗 CPU 资源，直到其他线程释放锁后进行 notify / notifyAll 来唤醒该等待中的线程。

二、架构 与 设计模式

考虑到请求按时间戳输入，需要独占一个线程，而并行运作的电梯也对应着多个并行的线程，且请求作为共享资源滞留在对应楼层、楼座，这就恰好适于使用生产者-消费者设计模式，将输入线程视为生产者，电梯视为消费者，再结合 Thread-Specific Storage 模式，为每个电梯、楼座分配单独的存储空间，避免所有线程共用相同等待队列（共享资源）带来的多余竞争开销。

这里给出基于线程交互的 UML 类图，省略部分类的部分细节内容，着重看各类之间的关系。

在 HW5 阶段，仅有 BuildingElevator、WaitList 与 RequestTable 三个关键类，使用标准的 Producer-Consumer 设计模式，BuildingElevator 对应 Consumer，RequestTable 对应 Producer，WaitList 对应 Channel，PersonRequest 对应 Data，形成类似下图的结构。

在 HW5 向 HW6 的迭代开发过程中，由于对跨楼座请求的限制（跨楼座请求不涉及楼层变化），问题可以被简单转换为增加十个横向楼座，引入 FloorElevator，整体与 BuildingElevator 类似，仅需对运行逻辑稍加修改——将上下移动修改为顺逆时针移动。

在面对 HW7 的跨楼座跨楼层请求时，化用生产者-消费者设计模式的变种—— Worker Thread，再结合流水线的设计思路，将请求分割后依次送入横向电梯与纵向电梯这两个流水级，具体来说，为 Elevator 添加与 WaitList 的交互方式—— Puts PersonRequest，用于模拟传递至下一流水级的行为。

在实际处理中，为了让电梯正常结束而基于请求数设置了计数器，基本流程为：主线程启动调度器，调度器开始按时间戳输入请求并分发至等待队列，等待队列根据请求启动新电梯或维护新的到达请求。电梯则从其对应的等待队列中不断获取新的到达请求并进行处理，处理结束后不需换乘则与计数器进行交互，否则将部分处理后的到达请求返回给调度器由其决定该请求的下一步去向。最后，当计数器清零且输入结束即意味着所有线程可以结束了。

三、调度器 与 线程交互

调度器使用 单例模式，某种程度上类似于 全局变量 的用法，使得所有类均可直接使用调度器（通过 getInstance 方法获取对象）进行调度。

 public class RequestTable {
     private static final RequestTable REQUEST_TABLE = new RequestTable();
     
     public static RequestTable getInstance() {
         return REQUEST_TABLE;
     }
 }

调度器主要负责将请求进行分类，并分发至对应的等待队列。在 HW5 与 HW6 中，调度器 RequestTable 仅负责将输入分发给对应等待队列 WaitList ，而在 HW7 构建流水线结构后，它还负责将各级流水线未完全完成的 PersonRequest 进行重新分配，将其视为另一种输入。具体来说，可以在 Elevator 中调用调度器及其方法，来实现同一请求的流水级转换。

四、测试 与 Bug 修复

相较第一单元化简表达式而言，第二单元更趋向于简单的模拟，因此很难在逻辑上出现漏洞，所以保证电梯调度系统的各部分功能基本实现即可证明系统整体的正确性。需要额外关注的重点，在于如何处理多线程之间的关系：一方面要防止轮询，另一方面又要防止死等。

在 HW5 、HW6 及 HW7 的测试与 hack 阶段，都发现了轮询的问题，追查原因后发现问题均是由 wait 与 notifyAll 的不配对使用造成的——常常发生等待线程被无谓的唤醒从而浪费 CPU 资源的现象。因此，确保仅在改变需要被等待线程使用的共享资源后才进行唤醒，便可以避免此类轮询问题。

此外，在 HW7 中还发现了死等的问题，主要是由于引入流水线结构后未设置完备的结束逻辑，使得流水级在部分情况下无法判断输入是否真的结束。对此，仿照控制器设置一个单例模式的计数器来标记请求数目，便可以解决上述问题。虽然这样外挂一个额外的计数器较为不优雅，但若后续需要其他迭代开发，也可以选择将其内嵌至控制器中，作为控制器的子功能来实现。

五、心得体会

本单元主要考察多线程，与 OS 在多进程方面的内容有异曲同工之妙，关注的核心内容都是不同进程/线程对共享资源的写读冲突问题。由于这两方面内容几乎同时讲授，我的关注点也主要落在多线程设计模式上，考虑各种线程交互的模式以及代码的整体架构，而几乎忽视了面向对象属性，使得类、方法的层次设计十分丑陋。如果能将面向对象这一代码管理方法应用得当，设计模式的实现可能会更加轻松吧。