OO第二单元总结

---

第五次作业

• 
  

  锁和同步块

  
  

　　此次作业中采用了线程安全容器——ArrayBlockingQueue作为请求的存储容器。

　　ArrayBlockingQueue有以下两个方法：

take()：取走 BlockingQueue 里排在首位的对象，若 BlockingQueue 为空，阻断进入等待状态直到 Blocking 有新的对象被加入唤醒线程为止 ；

put(E e)：把 e 加到 BlockingQueue 里，如果 BlockQueue 没有空间，则调用此方法的线程被阻断直到 BlockingQueue 里面有空间后被唤醒线程再继续。

　　利用这两个方法，可以实现在Distributer和Elevator线程中，避免轮询和超载的方式获取请求。

　　因为这次作业中是在Distributer中把MainRequest中的请求分发给五座楼中各自的RequestQueue中，同时，每座楼中只有一个电梯，不存在竞争问题，所以，此次作业中不存在对于存取问题中不同线程之间的类似“读写冲突”导致的bug，故不需要其他的额外加的锁。

　　对于输出还需要尤其注意线程安全！！由于每个线程可能同时调用输出，所以必须对输出方法加锁才能保证输出时间递增。可以通过用静态类，调用其方法来实现输出安全。

• 
  

  调度器设计

  
  

　　调度器Distributer是以MainQueue作为共享对象同Input进行关于“获取新请求”的信号的。即在Input中利用.put()方法添加新请求到MainQueue，在Distributer中利用.take()在MainQueue获取新请求从而实现交互。

　　以RequestQueue[5]分别于五座楼的电梯进行关于“乘客请求”的交互。在Distributer中，获取到的所有请求利用.put()被分发到对应楼座，在Elevator中利用.take()获取RequestQueue的请求。

　　特别的，对于结束的处理中，当Input获得null之后，会new一个Id为0的请求作为信号利用MainQueue传递给Distributer，同时结束自己的线程。在Distributer中接收到这个信号后，因为ArrayBlockingQueue是先入先出队列，在MainQueue中能够接收到结束信号意味着输入已经结束，故向每个RequestQueue发送一个Id为0的请求作为结束信号后可以结束自己的线程。在Elevator中，由于调度策略原因，接收到Id为0的请求时，只能说明RequestQueue不会再接收到新请求，故可以设置结束信号为true，但需要等所有其他请求执行完之后才能结束线程。

• 
  

  UML类图

  
  

• 
  

  UML协作图

  
  

• 
  

   未来拓展能力 

  
  

　　此次作业主要实现的是电梯运行的基础框架，电梯的调度、电梯应具有的属性和一系列操作函数是以后作业迭代的基础。可以适应修改成不同调度方式下的电梯。

　　同时，采用线程安全容器，新建容器时需要指定大小，方便更改电梯可容纳人数。

　　对于电梯可实现功能上的拓展，可以通过在Elevator类中增加相应实现功能的属性和方法实现。

第六次作业

• 
  

   锁和同步块

  
  

　　此次作业同第五次作业一样，使用的是线程安全容器，不同的是，此次作业存在一座楼的RequestQueue被多座电梯共享，从而出现类似“读写冲突”的现象，所以在此次作业中，除了.take(),.put()这两个线程安全方法外，还需要额外加锁以保证线程安全。

　　在此次作业中，我又额外在这个地方添加了锁：每座电梯在取外部乘客请求的过程中需要一定的调度原则选择一个合适的请求，这个操作需要遍历outQueue所有元素以实现，而且应该是一个原子操作，即在遍历整个队列时不应该有其他线程改变这个队列。因为取请求时需要通过一定算法确定下一个执行的请求，在遍历中，访问和取出不是同时进行的，访问不代表取出，如果不加锁可以多个线程同时访问某一请求。队列中如果找到合适的请求，会取出这一请求，如果不加锁可能会出现多个电梯都访问到目标请求，并取到了该请求，即请求被多次取出的现象，故需要加锁。

　　除了为实现同一座(层)电梯之间的自由竞争需要给outQueue加锁外，其他情况下的冲突均可利用线程安全容器自身特性解决。

　　在到达主请求的目的楼层后，需要判断是否还有其他请求可以在这一楼层实现，此时需要遍历outQueue来判断，由于遍历应该是一个原子操作，而outQueue是共享对象，故，对outQueue遍历时需要加锁以防止遍历过程中其他线程会同时操作。

　　遍历共享队列(安全容器)如果不加锁，可能会出现如下bug：遍历时，其他线程中添加了元素，但本线程中没有遍历到；遍历时，其他元素取出了某元素，但是，此时遍历过程中也访问到了该元素，导致本电梯中也仍旧能够得到这一请求，即请求被多次取出。

• 
  

  调度器设计

  
  

　　此次作业中，是为每座楼，每层楼都分别设了一个RequestQueue。Distributer同样还是利用MainQueue作为共享对象同Input进行交互，利用BuildingRequestQueue作为共享对象同对应楼座的BuildingElevator进行交互，利用FloorRequestQueue作为共享对象同对应楼座的FloorElevator进行交互。在Distributer中，把请求从MainQueue中取出后根据请求的FromBuilding 和 ToBuilding是否相同来判断应该将该请求分到那一个RequestQueue中。

　　结束方式同第五次作业。

　　我并没有给每个电梯也设计一个调度器，我的调度策略是Look，是通过取请求以及在电梯中设置dir这一变量来作为去请求的判断条件来实现该调度策略。

• 
  

  UML类图

  
  

• 
  

  UML协作图

  
  

•  迭代变化

　　此次作业较上一次作业多的是添加电梯、水平运送电梯和同一类电梯自由竞争这三项新增功能。

　　“添加电梯”是在上一次作业中的Input类中针对Request增添了动态新建线程这一情况来实现。

　　”水平运送电梯“是以上一次作业的Elevator为基本框架，重新建立BuildingElevator和FloorElevator这两种类型的电梯，其调度策略与第五次作业均类似，所需参数也均类似。

　　“同一类电梯自由竞争”是利用在“锁和同步块”那一部分讲的加锁的方法实现。

• 
  

  未来拓展能力

  
  

　　此次作业几乎同第五次作业。

第七次作业

• 
  

  锁和同步块

  
  

　　此次作业中，由于乘客的请求可能会出现不同楼层不同楼座，需要换乘，我才用的是“流水线”模式，在调度器中利用主队列获取乘客初始请求，分析乘客的请求并安排好该乘客换乘路径。然后，在调度器中把乘客对应的路径请求分发到电梯的队列中去。在电梯中乘客完成这一路程后即完成一项任务，再被放回到主队列中，等待调度器分发到下一路径所需的电梯，从而实现换乘。

　　作业六中提及的锁在此次作业中仍然是必要的，电梯向主队列添加元素的操作由于是安全容器故不需要加锁，但是，由于类型为floor的电梯有对可到达楼座的限制要求，即，此类电梯取请求时需要先判断电梯是否能够到达，不能够单纯采用.take()这一方法自由抢，所以，在此次作业中，floorElevator中在取元素时需要对outQueue加锁并在为空时对该对象.wait()，同时，在调度器中，向某层的floorQueue添加元素时需要对该共享对象加锁并用.notifyAll()唤醒电梯线程。

　　此外，为了判断什么时候调度器等线程的结束，我在此次作业中引入了一个静态变量count，在调度器中接收到新请求时，count++，在电梯中完成请求后count--,当count为0时说明所有任务已经完成，当Input接受到null时会给调度器一个信号，这两个信号同时满足条件时，调度器线程可以结束，并向各个电梯发出信号。对于count的加和减都应是线程安全的，我的实现方式是新建了一个类，以静态变量int型count作为属性，类中有加，减这两个加锁的方法以实现对count的加锁。这一方法或许可以是一种“单例模式”。

　　采用这一方法的原因：1.锁必须是对对象加锁，所以，如果只是为调度器或者任何一个类中添加一个静态变量来加锁是不被允许的。2.如果把count设为Integer这一对象，如果加锁，也会加锁失败，因为发现synchronized锁对Integer等基本类型的包装类没有效果。具体来讲：Integer类内部属性的定义是 private final int value；当value变化时就会产生一个新的 Integer。可以看出i前后所指向的对象地址不同，即加法操作前后引用的不是同一个对象。因此对 Integer 加锁是没有意义的，每一次加锁锁住的都是不同的对象。3.由于count变量需要被除了Input所有线程共享，同时，这是我为了更好的解决线程结束这一问题单独实现的，新增一个静态变量而不是为每个线程传入一个共享对象是最简洁且修改量最小的方法。

• 
  

  调度器设计

  
  

　　采用“流水线模式“。

　　在Input中添加了一个Paser类，分析每一个新请求为不同的步骤，即将换乘需求分解开。在Paser类中，根据add的floor类型电梯的数量、速度、楼层分布信息来为每一个需要换乘的乘客请求安排合适的换乘楼层，从而在Input中就确定了每个初始请求的路径，同时记录下乘客所需要的路径数。然后通过MainQueue这一共享对象给Distributer。

　　Distributer实现的功能类似作业五和作业六，不同的是此次作业中是按照乘客目前路径来分配乘客。此外由于电梯会向MainQueue重新添加乘客未完成的请求，即Input接收到null信号后，Distributer仍然有未分发完的任务，所以，引入count来作为信号记录乘客请求的完成情况。Distributer分发时count需要加上该乘客的请求数量，同时，在电梯中每完成一个乘客的一个请求，count--。当count == 0时，说明此时任务全部完成。以此可以作为结束的判断条件。

　　各电梯中，任务完成后重新把乘客放回MainQueue，等待Distributer的下一任务的分发。

• 
  

  UML类图

  
  

• 
  

   UML协作图

  
  

• 
  

  迭代变化

  
  

　　此次作业实现了乘客的“换乘”请求。

　　主要通过“调度器”部分所讲述的方法实现。

• 
  

  未来拓展能力

  
  

　　此次作业仅实现最多换乘两次的请求路径安排，可以改变Paser中的分配方式以选择更佳的最短路径。同时对于路径安排只考虑了每层的电梯速度、数量、容量、层数这几个静态因素，可以考虑到达时间、每层电梯既有的请求、以及电梯之间的送达与接受等动态因素，故在这一方面均可在Paser这一个单独的类中拓展，以提高电梯的运输效率。

　　每层楼或者每栋楼中的同类电梯仍然采用自由竞争的方式，但是各个电梯的运输速度和容纳人数均不同，自由竞争显然已经不是最佳处理方式，所以可以为每一座每一层再增加一个调度器，根据上述静态因素同时可以考虑到电梯已经容纳的人数和抵达目的楼层需要的等待时间等动态因素为某个请求安排特定的电梯，以提高电梯的运行效率。

自己程序的bug

1. 第五次作业中，线程输出不安全，是在各个电梯中直接输出。后改成新建一个输出的静态类，加锁以保证输出线程安全。


2.  在第六次作业中想重新整理一下代码内容时不小心删掉了一行，导致在某种情况下的讨论少了一项，但是这种情况的发生对数据具有偶然性，而不是必然的错误，所以，改完之后我又测试了几组数据就以外没什么问题了，但是却漏下了一种分析情况orz


3. 在第七次作业中需要对floor类型的电梯可到达的楼座用掩码判断一下，对位移动应该用“>>>"逻辑位移，而我使用的是">>"算数位移。

发现别人bug的策略

 　   用重复的随机的数据进行覆盖性测试。

　　同时注意由于调度策略不好可能会导致的RTL，所以可以选择一些在时间末尾添加大量请求的数据。

心得体会

通过此次作业，我主要对关于一下几点中收获颇丰：

1.  多线程的线程安全；


2. 单例模式、工厂模式；


3. 线程之间的交互；


4. 线程的等待与唤醒；


5. 对于”面向对象“设计的更深一步的体会。