BUAA - OO - 第二单元作业总结

1. 程序架构

1.1 第五次作业

​ 第五次作业要求模拟一个多线程实时电梯系统，其中乘客请求仅包括在本座内的上下移动

1.1.1 概述

主要思路是：读入线程读入请求至等待队列 => 主控线程分配请求至各个调度队列 => 各个电梯线程处理调度队列中的请求

• 创建请求类（其实可以用官方包），用以记录乘客状态并作为队列的储存单元

  
  



• 基于生产者-消费者模式

  
  
  
  
  • 创建生产者：输入线程。读入输入信息并转化为调度请求，将其填入等待队列
  
  
  • 创建托盘类：作为生产者和消费者存取请求的媒介
  
  
  • 创建消费者：电梯线程。处理调度队列中的调度请求，即完成开关门、寻地与运送乘客的任务
  
  
  
  



• 创建主控线程，将等待队列中的请求分配给电梯对应的调度队列

  
  

以此基本完成 读入 => 分配 => 处理 的模式。_{（实际上还需要单独封装一个线程安全的输出类，在本次作业中不慎忽略，后续会加以补充）}

接下来我们结合UML类图对分配逻辑和处理方法进行一些介绍。

1.1.2 UML类图

调度设计

读入 => 分配

• 首先用读入线程将请求放入waitQueue


• 同时要为不同的电梯准备不同的processingQueue


• 接下来主控线程从waitQueue中get()出请求，再put()进楼座对应的processingQueue中

分配 => 处理

• 为了防止多线程并行在对同一个队列进行存取，首先为Tray中所有方法添加synchronized关键字以保障原子性

  
  



• 接下来要为电梯和乘客设定不同的状态：等待，上行，下行。

  
  



• 然后是调度策略的设计，我们模仿现实中的电梯进行策略设计：

  
  
  
  
  • <启动>：
    
    
    
    • 此时为起点
      
      
      
      • 未上电梯的请求状态为等待，且有各自方向
      
      
      • 电梯状态为等待
      
      
      
      
    
    
    • 从processingQueue中get()最远的等待请求，并将其加入目标队列
    
    
    • <更新>并<移动>至请求起点，<交互>
    
    
    
    
  
  
  • <移动>：
    
    
    
    • 向status方向移动，每一层都要输出ARRIVE信息
      
      
      
      • 若本层有同向等待乘客或到达乘客，<交互>
      
      
      • 继续<移动>
      
      
      
      
    
    
    • 当彻底清空电梯，且processingQueue中无新请求时，电梯重回等待状态
    
    
    
    
  
  
  • <交互>：
    
    
    
    • 开门，<清除>，<添加>，关门
    
    
    
    
  
  
  • <添加>：
    
    
    
    • 将所有本层同向等待乘客加入运行队列
    
    
    • 直到装满或加完后，<更新>
    
    
    • 更改所有乘客状态为运行方向
    
    
    
    
  
  
  • <清除>：
    
    
    
    • 让所有到达目的地的乘客离开电梯，从运行队列中删除
    
    
    
    
  
  
  • <更新>：
    
    
    
    • 更新目的地为指定值 或 距此最远请求的位置
    
    
    • 更新状态为到目的地的运行方向
    
    
    
    
  
  
  
  

线程结束

• 当输入结束时，输入线程设置waitQueue的isEnd，notifyAll()并结束


• 主控线程在操作waitQueue时探测到isEnd()，则为每个processingQueue设置isEnd()，notifyAll()并结束


• 每个电梯线程在操作processingQueue时探测到isEnd()，结束

1.1.3 基于度量的结构分析

对于代码规模，有如下statistics analysis

对于类，有如下metrics analysis

对于方法，有如下主要部分metrics analysis

经过讨论和学习研究，终于勉强完成了第一次多线程程序写作。利用一次性接满同一方向乘客的策略完成了最基本的电梯调度。代码量尚为适中，主要类中仅消费者线程较为臃肿，总体来说尚可接受。

1.2 第六次作业

​ 第六次作业允许水平环形电梯的存在，并增设了添加电梯的请求，而所有乘客请求仍不涉及换乘

1.2.1 概述

主要思路仍是遵循 读入 => 分配 => 处理 模式设计，只是要区分两种请求和两种电梯

• 自官方包派生乘客请求类，用以记录乘客状态并作为队列的储存单元


• 自官方包封装输出类，完成输出的线程安全设计


• 基于生产者-消费者模式
  
  
  
  • 更新生产者：输入线程。将乘客请求填入等待队列，为新建电梯配置调度队列
  
  
  • 更新托盘类：作为生产者和消费者存取请求的媒介，增设分配策略
  
  
  • 更新消费者：电梯线程。处理调度队列中的调度请求，即完成开关门、寻地与运送乘客的任务
    
    
    
    • 派生横向电梯线程
    
    
    • 派生纵向电梯线程
    
    
    
    
  
  
  
  


• 更新主控线程，将等待队列中的请求分配给电梯对应的调度队列，增设分配策略

接下来我们结合UML类图对分配逻辑和处理方法进行一些介绍。

1.2.2 UML类图

调度设计*

读入 => 分配

• 首先用读入线程将请求放入waitQueue

  
  



• 同时要为不同的线路准备不同的ArrayList processingQueue，其中

  
  
  
  
  • 【1-10】代表十条水平线路
  
  
  • 【11-15】代表五条竖直线路
  
  
  • 而每条线路之下都为每个新电梯配置新的processingQueue
  
  
  
  



• 接下来主控线程从waitQueue中get()出请求，再put()进楼座对应的processingQueue中，

  其中请求分配的策略值得一提，这里我暂时没有想到合适的方法，只是讨论出了一个补救方法

  
  
  
  
  • 其实完全可以自由竞争（
  
  
  • get()时可选择路程最远（且离边缘最近）的请求
  
  
  • put()时可选择当前路径上调度队列中请求最少的电梯接手
  
  
  
  

分配 => 处理

• 为了防止多线程并行在对同一个队列进行存取，首先为Tray中所有方法添加synchronized关键字以保障原子性

  
  



• 接下来要为电梯和乘客设定不同的状态：等待，前进，后退。

  
  



• 然后是调度策略的设计，我们模仿现实中的电梯进行策略设计：

  
  
  
  

  • <启动>：

    
    
    
    
    • 此时为起点
      
      
      
      • 未上电梯的请求状态为等待，且有各自方向
      
      
      • 电梯状态为等待
      
      
      
      
    
    
    • 从processingQueue中get()最远的等待请求，并将其加入目标队列
    
    
    • <更新>并<移动>至请求起点，<交互>
    
    
    
    
  
  

  • <移动>：

    
    
    
    
    • 向status方向移动，每一处都要输出ARRIVE信息
      
      
      
      • 若本层有同向等待乘客或到达乘客，<交互>
      
      
      • 继续<移动>
      
      
      
      
    
    
    • 当彻底清空电梯，且processingQueue中无新请求时，电梯重回等待状态
    
    
    
    
  
  

  • <交互>：

    
    
    
    
    • 开门，<清除>，<添加>，关门
    
    
    
    
  
  

  • <添加>：

    
    
    
    
    • 将所有本层同向等待乘客加入运行队列
    
    
    • 直到装满或加完后，<更新>
    
    
    • 更改所有乘客状态为运行方向
    
    
    
    
  
  

  • <清除>：

    
    
    
    
    • 让所有到达目的地的乘客离开电梯，从运行队列中删除
    
    
    
    
  
  

  • <更新>：

    
    
    
    

    • 更新目的地为指定值 或 距此最远请求的位置

      
      
    
    

    • 更新状态为到目的地的运行方向

      
      
      
      
      • 横向电梯可在启动时选择如下策略确定最近方向（经课下讨论得出结论）
      
      

      (dst - src + 5) % 5 > (src - dst + 5) % 5 ? "INC" : "DEC";

      

      
      
      • 此后可直接固定运行方向（经研讨课上的同学提点，此方法效率甚至可能更高）
      
      
      
      
    
    
    
    
  
  
  
  

线程结束

• 当输入结束时，输入线程设置waitQueue的isEnd，notifyAll()并结束


• 主控线程在操作waitQueue时探测到isEnd()，则为每个processingQueue设置isEnd()，notifyAll()并结束


• 每个电梯线程在操作processingQueue时探测到isEnd()，结束

1.2.3 基于度量的结构分析

对于代码规模，有如下statistics analysis

对于类，有如下metrics analysis

对于方法，有如下主要部分metrics analysis

由于较差的休息状况和OS的失利，我被迫在第六次作业上依赖了很多外部帮助，尽管效果并不很令人满意，不过最终还是完成了。在本次作业中，主控线程和托盘类过于臃肿，其中许多方法即便经过数次refactor也依然有相当高的复杂度，大抵是没有经过深入优化和提取共性方法所致。日后定当在各种方面引以为戒。

1.3 第七次作业

​ 第七次作业要求满足个性化电梯的定制需要（速度、容量、横向电梯的停留条件）和乘客的换乘需要

1.3.1 概述

主要思路仍是遵循 读入 => 分配 => 处理 模式设计，只是需要拆解换乘请求、明确换乘方法和厘清类间关系

• 自官方包封装输出类，完成输出的线程安全设计

  
  



• 为了换乘

  
  
  
  

  • 自官方包派生乘客请求类，用以记录乘客状态并作为队列的储存单元

    
    
  
  

  • 新建请求链类，根据通达情况将请求拆分为不需换乘的子请求链

    
    
    
    
    • 若是在分配完后添加了新的电梯，这样静态的拆分方法不一定足够优越，只是真的没时间做动态更新了
    
    
    
    
  
  

  • 新建信号量类，使每个请求链作为一个单独的资源存在，以此

    
    
    
    
    • 避免多个线程插手同一任务的不同阶段
    
    
    • 避免线程由于针对请求队列的操作而提前结束或不能结束
    
    
    
    
  
  
  
  



• 基于生产者-消费者模式

  
  
  
  
  • 更新生产者：输入线程。将乘客请求填入等待队列，为新建电梯配置调度队列
  
  
  • 更新托盘类：作为生产者和消费者存取请求的媒介，更新分配策略
  
  
  • 更新消费者：电梯线程。处理调度队列中的调度请求，即完成个性化设定、开关门、寻地与运送乘客的任务
    
    
    
    • 派生横向电梯线程，添加换乘位表
    
    
    • 派生纵向电梯线程
    
    
    
    
  
  
  
  



• 更新主控线程，将等待队列中的请求分配给电梯对应的调度队列，更新分配策略

  
  



• 增设电梯工厂类，考虑到电梯的设计愈发独立和完善，选择将建立和存储电梯的任务从输入和主控线程中解放出来

  
  



• 增设等待队列类，考虑到所有线程都要和等待队列直接交互，选择让所有线程面对独立的单例模式等待队列类

  
  

接下来我们结合UML类图对分配逻辑和处理方法进行一些介绍。

1.3.2 UML类图

调度设计+

读入 => 分配

• 首先用读入线程将请求转化为原子请求链，放入waitQueue

  
  



• 同时要为不同的线路准备不同的ArrayList processingQueue，其中

  
  
  
  
  • 【1-10】代表十条水平线路
  
  
  • 【11-15】代表五条竖直线路
  
  
  • 而每条线路之下都为每个新电梯配置新的processingQueue
  
  
  
  



• 接下来主控线程从waitQueue中get()出请求，再put()进楼座对应的processingQueue中，

  其中请求分配的策略有所更新：

  
  
  
  

  • get()时可选择具有最远路程（且离边缘最近）的请求的所在请求链

    
    
  
  

  • put()时可选择当前路径上调度队列中请求最少的电梯接手，但此电梯一定满足一次换乘条件

    ((switchInfo >> (src -'A')) & 1) + ((switchInfo >> (dst -'A')) & 1) == 2

    

  
  
  
  

分配 => 处理

• 此处对请求链操作时，只操作其目前需要做的一项子请求

  
  



• 为了防止多线程并行在对同一个队列进行存取，首先为Tray中所有方法添加synchronized关键字以保障原子性

  
  



• 信号量本身的PV操作都要保障原子性，所以毫无疑问地需要添加synchronized关键字

  
  



• 接下来要为电梯和乘客设定不同的状态：等待，前进，后退。

  
  



• 然后是调度策略的设计，我们模仿现实中的电梯进行策略设计：

  
  
  
  

  • <启动>：

    
    
    
    
    • 此时为起点
      
      
      
      • 未上电梯的请求状态为等待，且有各自方向
      
      
      • 电梯状态为等待
      
      
      
      
    
    
    • 从processingQueue中get()最远的等待请求，并将其加入目标队列
    
    
    • <更新>并<移动>至请求起点，<交互>
    
    
    
    
  
  

  • <移动>：

    
    
    
    
    • 向status方向移动，每一处都要输出ARRIVE信息
      
      
      
      • 若本层有同向等待乘客或到达乘客，<交互>
      
      
      • 继续<移动>
      
      
      
      
    
    
    • 当彻底清空电梯，且processingQueue中无新请求时，电梯重回等待状态
    
    
    
    
  
  

  • <交互>：

    
    
    
    
    • 开门，<清除>，<添加>，关门
    
    
    
    
  
  

  • <添加>：

    
    
    
    
    • 将所有本层同向等待乘客加入运行队列
    
    
    • 直到装满或加完后，<更新>
    
    
    • 更改所有乘客状态为运行方向
    
    
    
    
  
  

  • <清除>：

    
    
    
    
    • 让所有到达目的地的乘客离开电梯，从运行队列中将其删除
    
    
    • 对每个离场的乘客，在其请求链中清除本次的请求，更新请求链
      
      
      
      • 若尚未完成，则把更新后的请求重新交给waitQueue，即准备换乘调度
      
      
      • 否则，使信号量释放资源，表示该请求已经完成
      
      
      
      
    
    
    
    
  
  

  • <更新>：

    
    
    
    

    • 更新目的地为指定值 或 距此最远请求的位置

      
      
    
    

    • 更新状态为到目的地的运行方向

      
      
      
      
      • 横向电梯可在启动时选择如下策略确定最近方向（经课下讨论得出结论）
      
      

      (dst - src + 5) % 5 > (src - dst + 5) % 5 ? "INC" : "DEC";

      

      
      
      • 此后可直接固定运行方向（经研讨课上的同学提点，此方法效率甚至可能更高）
      
      
      
      
    
    
    
    
  
  
  
  

线程结束

• 当输入结束时，输入线程用信号量依次检验所有请求链的完成，未完成则不结束


• 输入线程结束时，设置waitQueue的isEnd，notifyAll()并结束


• 主控线程在操作waitQueue时探测到isEnd()，则为每个processingQueue设置isEnd()，notifyAll()并结束


• 每个电梯线程在操作processingQueue时探测到isEnd()，结束

1.3.3 基于度量的结构分析

对于代码规模，有如下statistics analysis

对于类，有如下metrics analysis

对于方法，有如下主要部分metrics analysis

直到现在还有RTLE存在，只能说是一开始就没有设计好自己的架构导致的

1.3.4 时序图

拼接起来太过复杂，且毫无启发意义，故针对几个主要类分别建立时序图

• InputHandler

  
  




• MainClass

  
  

• ElevatorFactory

  
  




• Horizontal为例

  
  

2. Bug修复

自己的代码都来不及写，拿大家的互测代码学习一下也就罢了，真没精力找bug

2.1 第五次作业

• 自己的bug

  
  
  
  

  • Bug1：输出时间戳未递增

    
    
    
    
    • 原因：没有封装线程安全输出类
    
    
    • 评价：未能理解什么是线程安全，忽视了多线程的特点
    
    
    
    
  
  

  • Bug2：输出错误

    
    
    
    
    • 原因：没有在每一层都输出ARRIVE
    
    
    • 评价：没有仔细看指导书，该打
    
    
    
    
  
  

  • Bug3：RTLE

    
    
    
    
    • 原因：调度策略编写有误
    
    
    • 评价：需更多地进行评测和分析讨论
    
    
    
    
  
  
  
  

2.2 第七次作业

• 自己的bug

  
  
  
  

  • Bug1：RTLE

    
    
    
    
    • 原因：...线程结束标记和信号量检验写反了
    
    
    • 评价：...治治眼睛
    
    
    
    
  
  

  • Bug2：真·RTLE

    
    
    
    
    • 原因：调度策略编写并未得到足够优化
    
    
    • 评价：动态规划路径可能会更好一些，但也许难度更大
    
    
    
    
  
  
  
  

3. 心得体会

最难单元

• 一定要读清楚指导书，一定要读清楚指导书，一定要读清楚指导书


• 提前了解未来可能存在的需求并在架构设计中加以考虑，会大大降低重构的成本


• 认真了解各种设计模式，如单例模式、工厂模式，又如生产者消费者模式、观察者模式等等


• 死锁：对共享变量合理上锁，嵌套锁保证顺序无误


• 轮询：对wait()条件要合理判断【该改变线程结束条件的时候，不要wait()，不然RTLE】