面向对象设计与构造第二单元总结

一、程序结构与思路

三次作业中，笔者程序的基本框架保持不变。三次作业都采取了生产者-消费者的模式，对请求进行读取-分配-执行。

1. 第五次作业程序结构

输入线程从官方接口中获取请求，放入大盘子mainQueue中，Scheduler调度器从mainQueue中取出请求，分配给小盘子Strategy，Strategy为电梯Elevator从选取相应的请求，电梯进行执行。受到第三次课上实验的影响，尽管只有一部电梯，但依旧保留了调度器Scheduler的设定，来方便后来作业的扩展。

在本次作业中，乘客有三种到达模式，需要根据到达模式采取不同的策略Strategy，来获得更好的性能。也因此，我把Strategy变为抽象类，被三种不同的模式继承。

2. 第六次作业新增程序结构

相对于第五次作业，本次作业调度器开始发挥作用。针对三种不同的达到模式，除了电梯的子队列Strategy需要有不同的策略外，电梯的调度器Scheduler也需要有不同的策略。所以本次作业，Scheduler上升为了一个抽象类，其他程序结构基本没变。

3. 第七次程序结构微调

相对于第六次作业，本次作业电梯具有了3种类型，分别具有不同的移动速度、容量、到达楼层（A全层通，B奇数层，C可达1-3与18-20）等，考虑到其为静态特点，笔者采用enum ElevatorType进行存储，可以在其中自定义相应的方法，来满足电梯各处的需求。同时对人进行分类，采用enum PersonType进行存储。

public enum ElevatorType() {
	A, B, C;
	
	moveSpeed();
	capacity();
    cost();
}

public enum PersonType() {
    A, B, C, AB, BA;	//偶-偶，奇-奇，高底层，偶-奇，奇-偶
    //其余略
}

4. 最终结构图

调度器和候乘策略分别具有Morning、Random、Night各自的子类，来达成不同的目的。

二、调度策略与调度器设计

笔者的调度策略主要来自于Scheduler类和Strategy类。前者根据请求和电梯的当前情况将其分配给电梯的Strategy类，后者根据自己所持有的候乘请求和电梯的当前情况为电梯决定下一步的运行方向，尽量能够更快地清空自己所持有的候乘列表。

1. 电梯子队列调度策略（Strategy类）

对于电梯的调度，基本上采取了SSTF最短寻道时间优先算法。

1. 在主请求结束后且电梯内没有其他请求来成为新的主请求时，从等待队列中选取离电梯最近的请求作为主请求，完成下一次的运行。

2. （以例子描述）电梯当前处在10层，向上运行。此时设电梯内最近出电梯的楼层为a（a>10），设同方向且在10层以下的最近请求楼层为b，如果a-10>10-b则选择反向去接该请求，否则不去。这样可以捎带部分错过的请求，相对于原来来说有更好的性能，也能够较好地应对如下情况：

   Random
   1-FROM-5-TO-1
   2-FROM-6-TO-1
   3-FROM-7-TO-1
   4-FROM-8-TO-1
   5-FROM-9-TO-1
   

3. Night到达模式下，可以先对到达的请求按楼层由大到小排序，优先服务楼层最高的请求，下来的过程中进行捎带，能够获得不错的性能。

在作业中，我留有了主请求的概念，让主请求在大体上决定电梯的运行方向，原因是我不想让电梯每次都计算一次下一层该去向哪里，防止理不清关系出现反复横跳的问题。主请求的出现也让线程结束的判断变得简单，当从等待队列中getMainRequest()==null时，就意味着不会再有请求了。

至于当电梯为空，且需求移动去接主请求时，我采取了新建一个假请求的策略，将其作为一个临时的主请求把电梯带向真正选中的主请求所在的楼层。

2. 基本调度设计（Scheduler类）

• 电梯需要拥有较好的性能，在部分时候就需要有所牺牲，来换取一般情况的性能。

• 笔者选择根据电梯和请求所在的楼层和方向来完成请求的分配，尽量保证分配进电梯的请求能够成为主请求或100%被捎带。在电梯满人时不分配进等待队列，保证各电梯的等待队列+电梯内人数始终小于电梯容量。（这很明显不是最优解，但应该也具有不错的性能）

• RandomScheduler：

  • 本模式乘客到来完全随机，只能来一个分配一个。在电梯里没人时，直接分配给该电梯；在电梯内有人时，选择离该请求最近且可以捎带的电梯进行分配。不满足以上条件的等待下一轮分配。

• MorningScheduler：

  • 乘客在2s间隔内依次到达。考虑平均分配和优先装满一部电梯：假设乘客按2s, 4s, 6s, 8s...到达，平均分配需要逐个将请求分配给当前在1层的电梯，可能会让电梯在被分配一个请求后超过2s等待时间而直接离开，在人多时不具有很好的性能（尽管可以再把电梯叫下来，但可能会反复横跳）。
  • 笔者选择优先装满一部电梯，这在人少时性能较差（因为电梯空闲），但在人较多时，能够很好地进行服务。

• NightScheduler：

  • 乘客一次性达到。依旧按照楼层将请求排序，逐步分配满每一部电梯。优先高层、其次低层比优先底层、其次高层的性能要好。
  • 笔者没有选择在Night模式下从中途增加请求进没有满人的电梯队列，因为这样需要考虑的因素依旧很多，没有满人出现的情况也较少。

3. 电梯有类别时的新增调度设计（Scheduler类)

考虑电梯的可到达楼层、移动速度，可以将乘客大致分为5类，用enum PersonType存储：

将以上人员类型分别叫做C、B、BA、A、AB，分别考虑3种到达模式。在早上和晚上可以根据到达人员类型建立相应的子队列进行分配。

• Morning

  早上只具有C、B、BA三种类型的人，分别从子队列中拿出，分给C、B、A电梯的候乘队列即可。在B、BA两类中有一类人过多时，可考虑B、A两类同时进行捎带，加快响应速度。

• Night

  晚上只具有C、B、AB三种类型的人，分别从子队列中拿出，分给C、B、A电梯的候乘队列。在B类人过多时，A类电梯可帮助B类电梯捎带。（AB类人过多依旧只有A类电梯捎带，因为笔者觉得太难实现）

• Random

  本模式下所有人员类型都有，笔者在本模式下并没有采用5种子队列，而是直接根据电梯是否可以达到，计算不同电梯前来接人的时间花费（时间花费=电梯类型权重*楼层数，并没有考虑的特别复杂的接人关系），C电梯只捎带C类人，B电梯捎带B、BA两类人，A电梯可捎带A、AB、BA、B、C五类人。

4. 调度器设计代码描述及线程交互（指Scheduler）

• 笔者采取的是分布式调度，从主等待队列CachedQueue中拿出请求，根据各电梯的当前情况，分入各电梯子等待队列。具体内容已在2、3描述清楚了， 此处不再赘述。

• 作业中除了调度器以外，程序中还有电梯和输入两类线程，三者的交互形式通过主队列CachedQueue、子队列Strategy来完成，交互形式较为单一，不容易出问题。

• 根据调度器所承担的任务，调度器的设计细节直接以代码描述：

  void run() {
      while(true) {
          people = cachedQueue.getAllPerson();
          if (没有得到新请求 && 外部再无请求 && 没有乘客需要换乘) {
              break;
          }
          dispatchAll(people);	
      }
      notifyIsEnd();	//通知所有电梯再无请求
  }
  
  void dispatchAll() {
      for (Person person: people) {
          /* Random: 获取电梯捎带的权重，选择权重最小的进行分配	*/
          /* Morning or Night: 直接根据乘客类型分入相应的电梯类型 */
          
          /*
          加入对应的电梯时，需要判断是否需要换乘
          维护一个换乘总人数的变量，需要换乘就++
          调取器再次见到它时再--（这关系到结束条件的判断）
          */
      }
      if (分配失败：没有电梯需要请求) {
          wait();	//不要轮询！不要轮询！不要轮询！
      }
  }
  

三、同步块的设置与锁的选择及处理语句的直接关系

笔者在三次作业中均为采用锁的设计，全部是使用synchronized来完成。从结构中可以看出，需要在线程间进行共享的变量主要是主等待队列CachedQueue、子等待队列Strategy以及可能产生数量变化的电梯数量。根据程序结构，被锁住的内容其实只有2个暂存乘客容器、1个电梯容器，需要进行加锁的方法为add()、get()以及notify()方法。此外，Scheduler获取Elevator的当前信息不需要加锁，因其影响不大，不会影响电梯的正常运行。

四、功能与性能的权衡、可扩展性

1. UML类图

2. UML协作图

3. 可扩展性

笔者在设计的过程中，期望能够在功能和性能上平衡，优先考虑功能性和正确性，其次才是性能。笔者的架构基本上能够很好地满足功能上需求，能够很好地解决不同的到达模式、多电梯、不同的电梯参数等需求，但在换乘方面不能很好地解决。在性能方面，笔者是先完成程序的基本功能才进行性能上的优化，在功能性的前提下，对基本架构的前提下，对性能的追求受到限制，笔者最终选择抛弃了部分性能，只进行了奇数层到偶数层的换乘处理，来保证功能的正确性。

对于当前的架构，扩展性如下：

• 可扩展的方面
  • 电梯参数改变（enum方便添加改变）
  • 电梯到达模式的改变（直接加新策略即可）
• 难以扩展的方面
  • 强制换乘（没有楼层相关的管理，在楼层情况更加复杂时需要进行的改动很大）

五、BUG与测试

1. 己方BUG

• 3次作业没有被发现BUG，但不代表没有BUG

• 笔者自己知道的bug来自于第六次作业，但互测强测都没有被发现

  • 容器越界：笔者Elevator类的Arraylist<Person> people容器，在读取的同时可能有其他线程进行删除操作，导致数组越界/数组并发异常。

  • 所有线程wait：笔者在处理线程安全时，可能有极小的概率导致所有线程同时进入wait状态，代码如下：

    //调取器内：在所有电梯都不想要请求的时候，选择wait来避免轮询
    synchronized(mainList) {
        if (noElevatorNeed && !mainList.isEmpty()) {
         	mainList.wait();   
        }
    }
    //电梯内：在电梯想要新的请求时，先唤醒调度器，让调度器来进行分配
    synchronized(subList) {
        synchronized(mainList) {
        	mainList.notifyAll();	//加锁单纯为了唤醒调度器
    	}
        subList.wait();	//等待调度器分配请求
    }
    

    由于多线程的缘故，noElevatorNeed得不到及时的更新，且notifyAll()可能不起作用，导致在电梯进入wait状态后调度器可能也会接着进入wait状态，造成RTLE。后续采取wait(6000)来保证不会全部wait，但这并不优雅，没有解决实际问题。笔者后来对条件进行了加强，在if里进一步判断是否真的noElevatorNeed，解决了这个bug。

2. hack策略

• 总述
  • 电梯作业总体来说不太好测试，需要运行的时间较长，才能进行判断，在自测时还能接受，但hack时效率并不高。笔者对测试主要采取构造随机样例+特定样例来进行测试。从有效性来看，二者似乎区别不算太大。
• 随机测试
  • 数据通过python进行构造，随机/固定到达模式，随机/固定人数范围，随机电梯新增数量及时间。（可选）设置楼层特点（大部分奇数层，大部分偶数层等）
  • 输入通过讨论区的DebugInput()类进行，输出进行重定向
  • 数据正确性验证：从输入中读取起始楼层，从输出中读取人员的楼层变动信息（同时验证电梯是否可到达该楼层），进行人员情况的更新，最终比较人员的楼层是否与期望一致。
• 针对性样例
  • 通过极端样例的输出观察程序的特点，对程序所采取的调度方式进行初步判断
  • 观察用时，比自己快很多的应该问题不大
  • 观察线程安全，看看会不会出现RE问题或并发错误
  • 程序在正确性上问题应该都不会很大，笔者把重心放在了RTLE和CTLE上。对于RTLE采取极端样例；对于CTLE，直接在while循环中加println()，如果输出过多多半CTLE
• 关于线程安全
  • 线程安全的问题主要依赖于测试，其次是对代码的阅读。测试能够直接发现是否存在线程安全的问题，笔者发现但没有hack成功的bug就来自于自动生成的样例。对代码的阅读主要关注共享变量，观察是否存在线程同步的问题，三次作业房间内线程安全问题不明显，笔者似乎仅发现了一个线程安全的问题，还很难复现。

3. hack结果

笔者3次作业均为hack到别人，仅在第五次作业发现了别人的2个BUG，但hack未遂。

• 人进去了又进去了：2个同层乘客以某个间隔时间到达时，会出现如下情况：

  OPEN-1
  IN-1-1
  CLOSE-1
  OPEN-1
  IN-1-1
  IN-2-1
  CLOSE-1
  

  这种奇怪的并发错误可能来自于没有即使将乘客1从等待队列里移除的缘故

• RTLE：针对其载人策略，笔者构造了一个样例，最大允许时间31s，但其运行时间达到了40s，但hack失败。该同学时间花费较长的原因是其采用了反向接人的策略，但并未加最大楼层差限制，如电梯当前10层，运一位乘客从1楼上20楼，此时1楼来了6名从1楼到20楼的乘客，电梯会返回接人，造成时间的大量浪费，还不能将人员全部载走。

4. 单元测试策略的差异

对于第一单元的测试，基本上采取的是纯粹的样例自动生成。而在本单元作业，主要是样例的随机生成与手动构造极端样例的结合。笔者初步认为，本单元作业测试的关注重点是RTLE、CTLE，线程安全问题固然重要，但测试中基本很难遇到，相对只能寄希望于调度策略的失误以及CPU超时，事实上，三次作业房间内的所有bug也均为RTLE或CTLE。而在第一单元作业中，测试的重点是在程序的正确性以及格式错误上。这些区别导致了两个单元测试策略的差异性。

六、心得体会

1. 线程安全

• 线程安全问题来自于共享变量，读写或写写同时进行容易产生错误。
• synchronized语句或lock均可用来保证线程安全，根据程序的实际需求选择，用的顺手就行。如果出现连续加2个不同锁的情况，或许可以思考下是否有必要、或者可以通过其他方式来达到目的，避免各种奇怪的死锁问题。
• 在保证程序正常运行的前提下，加锁的范围应该尽量地小，来避免不必要的等待。
• wait和notifyAll配合使用，考虑各个类里面的执行顺序，尽量避免同时wait的情况
• 线程安全类
  • 需要同步或加锁的地方均放在线程安全类的内部实现，让外部调用时看起来像个普通的类一样
  • 线程安全类带来的是外部调用代码的简洁，相当于是一种封装，不必要在外面考虑程序的并发问题。这让我在3次作业中不必考虑太多的问题，而能够精力放在电梯的调度上。

2. 层次化设计

• 层次化设计在分布式调度中的体现还行，如图所示。

  graph LR A[InputThread] -->B(cachedQueue) B --> C[abstract Scheduler] B --> D[Morning Scheduler] B --> E[Night Scheduler] B --> F[Random Scheduler] C --> G(abstract Strategy) D --> H(Morning Strategy) E --> I(Night Strategy) F --> J(Random Strategy) G --> K[Elevator] H --> K[Elevator] I --> K[Elevator] J --> K[Elevator]

  架构的层次带来的可能是一种轻松吧，各自承担各自的功能，通过共享区域进行交互，避免线程间太多的相互调用造成耦合度上升。请求转移的整个过程看协作图即可。

3. 其他

• 正确性高于性能
• 明确程序的需求，考虑程序的可扩展性。不要一来就把程序写死，不然难以扩展。
• 尽量遵循SOLID原则
• 尽管有许多知识在程序中不是必须的，但或许也可以来次尝试，加深自己的理解，而不是仅用自己已经熟练的知识。
• 少用魔法值