写在前面

本篇博客重点在于复盘, 反思与自我批判, 提出一些优化的可能, 同时满足作业要求.

笔者的 另一篇博客 则重点介绍架构与算法, 并不满足作业要求, 因此不在本站发布.

架构分析

QAQ 手动 Visio 画图累死我了.

第一次架构

UML类图

UML协作图

第二/三次架构(重构)

由于第三次作业的架构与第二次的架构区别不大, UML类图基本一致, 协作图也相差无几, 所以这部分进行合并.

第二次架构

第三次架构

UML类图

UML协作图

线程安全控制

第一次作业 - 混乱的线程安全控制

由于是第一次接触多线程编程, 第一次作业的整体相当臃肿, 到处都有 synchronized 块, 到处都有面向过程的痕迹(所以一周后火速重构).

第一次的架构中, 除了明面上标注的 RequestQueue 和 ElevatorTask 是共享对象外, Scheduler 和 Elevator 中也有许多未被明显注出的共享对象(Scheduler 与 Elevator 互为生产者消费者, 共享对象为内部字段), 这就是我第一次作业中不成熟的线程安全类控制.

对于这次作业, 我的线程安全控制属实差劲. 归结起来, 最主要的问题就是多线程开发零经验, 引发了哪里不安全, 就往哪里加锁的编程过程.

第二/三次作业 - 线程安全类与原子操作

第二第三次作业中, 我逐渐摸索出了线程安全控制的技巧. 经验总结如下:

线程安全类 - 需求引导实现

生产者与消费者共享的托盘即为线程安全类, 此时线程安全类需要实现什么方法呢? 是否需要带有阻塞机制(托盘为空时, 等待)?

这些问题是不能够直接根据托盘解决的, 必须根据生产者和消费者的需求进行设计!

原子类 - 锁的极小化

在第三次作业中, 基于最短路的换乘分配算法需要从电梯线程中动态获取当前到达的楼层与当前的目标楼层, 此时若直接对 Elevator 类进行加锁, 则会严重影响并发, 拖慢线程. 正确的做法是将当前楼层与目标楼层装入原子类 AtomicInteger 完成线程安全控制.

调度策略设计

第一次作业

不涉及多梯调度, 所以只考虑不同到达模式引发的不同策略. 由于第一次作业时线程安全问题困扰了我很久, 所以并没有考虑很多性能优化:

• Random与Morning模式: ALS调度
• Night模式: 高楼层优先

本次作业中, 调度器作为单独的线程存在, 由于其"知道"的太多, 所以成了一个"上帝"类, 这是不利于后续迭代的. 至于其与其他线程的交互, 已在架构分析中有图示, 此处不赘述.

第二/三次作业

关于针对不同模式的优化, 也没有做很多优化:

• Random模式: ALS调度
• Morning模式: 等待6s后激活ALS调度
• Night模式: 高楼层优先

关于多梯调度的优化:

• 第二次作业: 按负载分配
• 第三次作业: Dijkstra最短路算法进行路线规划(换乘与分配)

第一次作业后, 我就开始思考调度器作为单独线程存在的必要性. 在第二次作业中重构代码, 将调度器改为一个非线程类来处理, 这一做法的好处十分显然, 那就是减轻了线程安全控制的负担. 关于其与其他模块的交互, 也在架构分析中有图示, 此处不赘述.

关于BUG

三次强测与互测中均无bug. 其实我并没有搭建本地的自动评测机:

1. 第一次作业时间比较紧, 但比较幸运, 没有出问题;
2. 第二次与第三次作业中, 由于采用了十分容易理解的线程安全控制方法, 使得逻辑与线程安全控制基本分离, 所以我也有自信不被测出bug.

关于HACK

主要是线程安全问题!

样例的手动构造思路: 极端数据 - 集中到达? 长时间停滞?

正确性判定: 正则表达式提取与肉眼判定(由于构造的数据都比较精炼, 所以肉眼看一下也问题不大)

第二单元过程中其他事情太多了, 确实没什么时间弄自动测试机.

一些互测环节的问题

有些线程安全的问题难以复现: 尽管互测CD减少了, 但是没有办法提高评测环境的并发数, 所以还是难以hack一些本来就不容易出现的bug.

比如有同学在多个线程中共享电梯列表, 当外部有加电梯命令, 线程正遍历列表时, 就会引发 ConcurrentModificationException , 但是由于加电梯命令仅限两个, 所以事实上这个bug是几乎不会有复现机会的.

以及尽管艰难地在互测中hack成功, 该同学也有可能重新交一次一样的代码就能通过评测, 这实在不得不说是多线程编程题互测的一个bug.

想对同学们说的(?

关于第三次作业的特种电梯, 其实更具有扩展性的做法是最短路, 某些专项优化其实并没有什么扩展性. 只需稍稍更改题目, 将特种电梯所能到达的楼层以指令形式动态传入, 大部分同学估计都要大范围重构. 而最短路并不依赖于静态的编码, 而是动态进行路线规划的, 事实上具备更优秀的可迁移能力.

在第三次互测中, 同屋者有用长长的 if-else 语句进行路线规划的, 实在是令人瞠目结舌, 这样的做法不得不说是毫无扩展性可言了.

心得体会

线程安全是个难题, 但绝对不应成为软件设计上的主要考虑, 所以下次再遇到多线程编程时, 正应当把目光聚焦于层次化设计与结构上, 线程安全只需由线程安全类集中管理即可.

本单元中我的层次化设计主要体现在策略模式中, 第二/三次作业中的策略设计实质上是可插拔的, 甚至可实现热切换 - 可以应对中途模式切换的迭代开发要求.

在4月份之前, 我并未接触过任何多线程相关的知识, 能够在三周之内"速成"多线程编程, 令人回味. 当然未能在性能分上得到很好的成绩也是值得思索(也许是最短路设计中一些系数过于主观, 也许是没有对请求进行排列优化).

一直以来, 我都要求自己独立完成作业, 这一要求是独立思考, 独立测试, 独立调试. 所以在没有自造评测机的条件下, 尽管有些同学造了很厉害的评测机, 我也没有请求他们帮助我进行测试.

这一点, 我认为是工程化编码与面向对象编码带给我的自信.