『BUAA-OO-Unit2-Summary』

『BUAA-OO-Unit2-Summary』

Homework5

0. 写在前面

由于没有看清DDL，导致本次作业卡点提交未能成功通过。（悲）

作为多线程编程的初学者，我认为本次作业的难点有三：

  1. wait()/notify()的使用；
  2. 共享对象类的构造；
  3. 调度策略的代码实现；

接下来，我将对本次作业的实现过程进行一个大致的复现，并对以上难点着重展开讲述。

1. 重点关注：同步块/共享对象/线程安全类

关于多线程程序设计，在拿到题面/了解客户需求后，设计架构时要提前想好以下几个问题：

  • 需要设计哪些线程类？
  • 共享对象是谁？
  • 线程与共享对象的关系是什么？

对于第五次作业来说，我们需要以下几个线程类：

  • InputThread：输入线程类，负责对标准输入的乘客请求进行解析，并将其传递给Dispatcher线程类。
  • Dispatcher：任务分配器，根据起点将各乘客分配到不同的请求队列中。
  • Elevator：电梯线程，将乘客运送到相应楼层并输出 运行轨迹 与 乘客信息。

如果分别构造InputThread与Dispatcher两个线程类的话，那么还需要实现一个供二者进行信息交互的共享对象类。但是二者均属于单例模式类，也就是说，自始至终只有两个线程会来访问这个共享对象，并且一个只会写，一个只会读。这样的设计显然十分不合理，因此我将InputThread与Dispatcher合并为一个线程类并命名为Dispatcher，其功能为从标准输入中获得乘客请求并将其分配到对应的队列中（即二者功能合并）。

至于共享对象，就十分明显了：Dispatcher需要将乘客信息写入一个队列，而Elevator类的五个实例（5 elevators）则需要从该队列中选择自己的任务来工作，并在任务完毕后将该任务从队列中删除。因此，共享对象就是各楼座的等候队列，创建共享对象类WaitQueue。WaitQueue的内部结构，我选择了同时维护一个ArrayList<>与一个ArrayList<ArrayList<>>，维护ArrayList<ArrayList<>>的目的是快速返回某楼层的请求信息，而ArrayList<>则起到了保留请求到达先后顺序的作用。采用这样看起来有些复杂的结构实际上有一个好处：明面上提示了设计者需要使用同步块。尤其是对于当时刚刚接触多线程的我来说，其实对共享对象读写的保护意识并没有那么强烈，但是在add与remove WaitQueue中请求时总是要同时对两个数据结构进行操作的这个事实总是在不断地提示着我读写方法的非原子性，共享对象的读写方法必须加synchronized同步块保护才能在线程中放心大胆地任意使用。

  • 关于共享对象类的构造：其实保证共享对象类内方法的安全性有两种方法：第一，开发者保证共享对象是线程安全类，即在构造时保证方法的原子性（不可分割的方法）；第二，在调用每一条方法前，用户对该指令操作的对象进行同步保护。只是，应该没有人会智障到采用第二种方式设计产品，或者说，应该没有用户会智障到选择采用第二种方式制作出来的产品吧。

各线程与共享对象的关系？Dispatcher线程对WaitQueue进行写入操作(W)，而Elevator既要从WaitQueue中读取数据，还要在任务完成后将数据清除(RW)。

这几个基本的问题思考清楚以后，我们便可以开始动手实现了！

2. 调度策略

关于调度策略，虽然学长与助教强烈推荐了LOOK算法，但我还是倔强地使用了ALS策略。

说实话，其实ALS策略并不是很好写。主要概念只有两个：主任务与捎带任务。实现分四步走，思路如下：

getMainMission(); move(); getNextMovingDir(); outAndIn();

  • getMainMission() / move() 存在两种情况：

  • A. 若电梯载客队列为空，则将WaitQueue中到达时间最早的请求作为主请求，朝着其起点方向移动；

  • B. 若电梯载客队列不为空，则将电梯载客队列的第一个请求作为主请求，朝着其终点方向移动。

  • P.S. ARRIVE-*信息在move()中打印

  • getNextMovingDir()：

    • 若到达主请求的起点楼层(A1)，nextMovingDir即为向主请求终点移动的方向
    • 若未到达主请求的起点楼层(A2)，nextMovingDir仍为向主请求起点移动的方向
    • 若未到达主请求终点楼层(B1)，nextMovingDir为向主请求终点移动的方向
    • 若到达主请求终点楼层(B2)，nextMovingDir为0，损失一次进人机会（该方法的一个小漏洞）

  • outAndIn()：

    • 为在不超载情况下最大限度多拉客，先getOut后getIn。
    • 为了将判定乘客进出逻辑与打印OPEN-*/OUT-*/IN-*/CLOSE-*两个过程分开实现（更加清晰），先获取出进成员名单，后打印出进结果。

至此，调度策略讲解完结。

3. 架构模式(类图/SD图)

4. Bug修复

本次作业中测未能成功通过，CTLE的原因即为没有完全搞懂wait()/notifyAll()的实现机制，导致共享队列为空时反复轮询。对此漏洞进行修复后，在第六次作业强测中又一次出现了CTLE的问题。这个问题一会儿再细说。

并且第一次堆砌的自以为实现了ALS策略的ShitMountain复杂度太高，应该也是导致超时的重要原因。

Homework6

0. 写在前面

本次迭代要求新增两大亮点：

  • 维护原有纵向层际直线运载电梯，新增横向座际环形观光电梯（北航特色）

    • Too much character, an access of character. --- Elizabeth Alexandra Mary Windsor

  • 同座/同层可支持多台电梯

1. 重点关注：线程安全/wait()/notifyAll() [详见Bug修复板块]

本次作业难度真的不是很大。但是由于没能成功参与第五次作业的互测，导致第六次作业强测中出现了本该在上一次作业中解决的历史遗留问题。

首先，先来谈一谈环形电梯的实现：

  • 我居然真的傻傻地按照指导书的要求，对环形电梯载客的最优策略进行了路线设计，好一阵取模运算比较选择最优运行方向后，在研讨课上和大家交流时才恍然意识到：环形电梯一共只有五个停靠点，即使电梯始终按同一方向运行也不会损失很多时间。仔细一想确实如此，并且在现实生活中的环形电梯也确实是始终朝着一个方向运行的；如果停靠点数目过多的话，我猜测设计者应该也会采用地铁环状线内外环两路的运营方式，而不会让电梯的运行方向始终飘忽不定的。

废话了这么多，第六次作业中我的环形电梯采用了运行方向可变的最优调度模式。由于实现方法与纵向电梯较为类似，只是计算最优路径时增加了一些取模运算，这里不再赘述。

而多台电梯的问题，我还真的思考了很久没有想到一个最佳的调度方案。后来无意之中提交后奇迹般通过后才意识到让共享同一队列的电梯间自由竞争居然也是一种解决方式。

2. 思考：HiddenDispatcher（隐式任务分配）

废话少说，直奔主题：

前一段时间我一直在思考这个问题，电梯线程间的信息是不能共享的，那么如何实现共享同一WaitQueue的线程间任务的最优分配呢？

e.g. 1-FROM-A-7-TO-A-8, 2-FROM-A-8-TO-A-10, 3-FROM-A-2-TO-A-1；其中，A座共有两台电梯，一台(1)停在6层，另一台(7)停在3层。

采用传统的自由竞争策略，必然会导致4号与7号电梯共同竞争上行的两个请求，7号电梯节节败退，白白跑到8层，一个请求都没有接到，而3号请求却始终无人问津的窘况。

为了破解这一难关，并且避免电梯线程间信息共享，就需要构建一个可以同时获取WaitQueue信息以及共享这一WaitQueue的全部电梯当前所在楼层及运行方向的Dispatcher。虽然听起来是一个好主意，让人叹为观止；但是听起来也有一点麻烦，让人望而却步。

但是转念一想，自由竞争方案中难道就不存在任务的分配器了吗？即使只考虑一个电梯线程，在进行主任务获取时，getMainMission方法在传入参数中仍然获得了当前电梯的所在楼层，getRequest()方法不仅获得了当前电梯的所在楼层，还获得了运行方向。而两个方法都是WaitQueue中的方法，也就是说我完全可以将这两个方法独立出来，形成一个MissionDispatcher线程帮助电梯确定主任务，以WaitQueue与mainMission(Elevator)为共享对象，将二者关联起来；换句话说，这样的一个MissionDispatcher线程类如果只针对单一电梯线程进行任务分配，那么完全可以将MissionDispatcher的全部功能简化为method方法，归并入WaitQueue的一部分。

就这，我愿意称之为隐式任务分配(Dispatcher hidden in methods)。

3. 架构模式(类图/SD图)

4. Bug修复

两个漏洞：

  1. 第五次作业的残留问题：没有保护输出线程（不安全），需要套上synchronized语句块。（看了讨论区一位同学的分享，讲的很清楚，这里不重复）
  2. 关于wait()/notify()/synchronized的实现机制：
    • 我对这个问题一直有一些误解，以为被synchronized获得的锁在跳出语句块释放后，其他因为需要获得同一对象的锁而无法正常执行的synchronized()语句块不会被自动唤醒，需要人工notify()一下。实际上完全没必要，这是我的误解，只用使用wait()被迫人工等待的线程需要被人工唤醒。（你系的铃你解，系统系的铃系统自己解!)

Homework7

0. 写在前面

迭代起来极具挑战性(Physically & Mentally)的一次作业：

  • Mentally:

    1. DIY电梯各项指标（速度/最大载客量/可达性）

    2. 乘客需求自由，不再有起终点同座/层的限制

​ 加上了这两条要求后（主要是第二条），工作量几乎可以说是对先前代码的全面重构。

  • Physically:

没错，我就是盯着这样一个支离破碎还漏液变色的电脑屏幕重构了10个小时。凭借着超人的意志以及强大的视力完成了这次作业的我真的很佩服我自己。

P.S. 知识方法类的感想与收获在前面两次作业的总结中已经介绍的差不多了。HW7将以介绍具体的设计思路与实现为主。

1. 迭代思路与难点

就是说因为乘客起点与终点并不一定在同座或同层，所以存在一个换乘的问题。如何进行换乘呢？

  • 我采用的是从一开始便计算出换乘路径的办法。

我们先不关心路径的算法，先思考这样一个问题：用什么样的数据结构来存储路径呢？

  • 在这里，我采用了一个类似索引查找的方法利用一维数组来存储请求的路径。
    • 先对各楼座楼层元素进行编号：A-1 : 0 -- A-2 : 1 -- ... -- E-10 : 49
      • \([\ spot = (block - 'A') * 10 + floor - 1\ ]\)
    • 对于形如i -> j -> k -> ... -> y -> z的路径，先初始化一个容量为50，元素值均为-1的一维数组；
    • 令\(path[i]=j,\ path[j] = k,\ ...,\ path[y]=z,\ path[z]=z\)
    • 这样，只需传入电梯当前所处位置，即可确定某任务下一移动位置。

这里我们可以注意到，由于path[]数组与PersonRequest类现在是不可分割的，我们随时都可能要同时获得二者的信息，或者依赖二者合作获得我们想要的数据。

  • 因此将它们封装为一个新类，重命名为PersonRequestPath（请原谅我蹩脚的命名）。

获得路径后，如何具体实现换乘操作呢？

  • 首先，构造一个getNextMove()方法，传入电梯当前位置，获取下一步的移动方位(UP/DOWN/OVER/ROUND)
  • 其次，构造一个单例线程类TransferDispatcher，负责与电梯线程进行数据交互（如SD图中所描述）。电梯线程中请求确定getOut后，判断其下一步移动方位，若判定其需要换乘，则将其加入TransferList（新的共享对象），与TransferDispatcher进行信息交互。两个小细节：
    • 为了让TransferDispatcher能成功定位请求的当前位置，在将请求加入中转队列前仍需一并传入当前位置信息。新建TransferInfo将PRP与curSpot封装在一起。
    • TransferList作为新的共享对象也应构造为线程安全类。
  • P.S. 原本电梯线程确定getOut名单的方式是比较当前位置与请求终点位置是否相同。而现在由于换乘请求的加入，我们在判断是否getOut的方式需要更加灵活一点，只观察下一步的移动方位，如果与当前电梯功能相符（Vertical -- UP/DOWN, Horizontal -- ROUND）则仍留在电梯中；否则(STAY/不相符)下车。

换乘问题解决了。回到开始的那个问题：如何计算换乘路径呢？

  • 设计之初考虑过使用Dijkstra算法，但是可行性不强。因为我们希望换乘次数尽量要少，而使用Dijkstra算法可能会出现七扭八歪的鬼才路径，这是我们不希望看到的。
  • 最终，我采用了有些智障的遍历算法。只在起点终点两层之间寻找是否存在横向可达的电梯，如果存在便选择这条始终向目标靠近的路径，否则，暴力一层中转。

这样，请求多样化的迭代就基本完成了。

  • 还有一点需要注意，就是在构造横向可达性的临接矩阵时，一定要将所有联通可达楼层之间的边全部置一。表述的不是很清晰，举个栗子：A-1/C-1/D-1/E-1 ---> \(4 *3 =12\) 个元素均为1。

最后的最后，由于换乘的存在，我们遭遇到了一个棘手的问题：

即使此时输入已经关闭，某电梯为空，也不代表该电梯线程一定结束。因为可能在其他电梯内的某乘客一会儿可能会乘坐该电梯中转。解决方案：构造一个Counter计数器，每输入一个新请求，调用incrementTotalRequests()，记录请求总数；每完成一个请求，调用incrementFinishedRequests()，记录完成请求数。在输入关闭后，判断两个static int变量是否相等，若相等，则各线程setEnd()；若不等，则wait()。这样在避免反复轮询的同时，可以起到判断程序是否终止的作用。

2. 架构模式(类图/SD图)

P.S. 由于本次结构较为复杂，略去末尾setEnd()的信息传递。

3. Bug修复

忽略了一个小问题：

由于同层横向电梯的规格可能有所不同，导致横向换乘乘客的需求并非每台电梯均可满足。在设计载客逻辑时忽略了这一问题，导致某些乘客不小心坐上了错误的电梯，而无法在到达目的地时成功下车。

主要在以下三处进行了修改：

  1. 主任务的判断：电梯在选择主任务时必须保证有能力完后才能该任务，为了使等候队列分配给电梯正确的主任务，需要在getMainMissionFromFloorWaitQueue()函数中传入电梯的access信息。

    P.S. 由于对主任务选择逻辑进行修正后，即使在等候队列不为空的前提下，主任务获取仍有可能失败，因此在函数返回值为null的情况下，需添加wait()语句进行异常处理。

  2. 获取getInList：在获得可进入乘客名单时，也需要在getRequestInCurBlock函数中传入电梯的access信息。

  3. 增加一个新函数：以上两处改动中，在判断乘客是否可以乘坐当前电梯时，均需要获取乘客在横向电梯的换乘终点。因此，新增getNextBlock()函数获取这一信息。

Summary

  • 本单元作业可以暴露出我对上一单元相关知识仍然没有熟练掌握的问题，比如多态：在第三次迭代后，我的WaitQueue类方法中出现了多个形如getMainMissionFromCurBlock, getMainMissionFromCurFloor, getgetRequestOnCurFloor, getRequestInCurBlock本可以用Overload(重载)方式实现的代码，而这些问题是我在完成作业后才意识到的。

  • 关于工厂模式，在第二次迭代要求中增加横向电梯时，我就在想使用Elevator接口运用工厂模式建模是不是会更规范一些。但是几经斟酌我还是没有这么干，仍然没有体会到工厂模式在实际应用中的实用性。