OO第二单元作业总结

OO第二单元作业总结

综述

本单元共三次作业，需要完成的任务依次为单部多线程傻瓜调度（FAFS）电梯的模拟，单部多线程可捎带调度（ALS）电梯的模拟，多部多线程智能（SS）调度电梯的模拟。

三次作业中新学到的知识点：多线程编程、线程互斥与同步

三次作业的架构：消费者生产者模式。使用一个Vector保存输入的请求，获取请求线程就是生产者，各个电梯就是消费者，这Vector相当于托盘，由各个线程共同维护。各个作业使用的调度方法以及具体细节设计在各个作业的分析中具体介绍。

学到的编程知识

首先，为什么要使用多线程呢？因为在许多工程项目中，使用单一线程很难完成一些比较复杂的需求。最明显的一个例子，就是如何让程序在运行的时候能夠随时响应用户提出一个请求，在本次作业中的体现是需要在电梯运行的同时保存新的request并在之后分配给电梯，当然，如果采用一些特殊方式，如每隔特定时间查询输入等也可以实现“响应”用户请求，但是这种方式无疑是降低了程序的运行效率，且会浪费CPU的资源，因此，多线程编程对我们来说是很重要的知识。

在java中想要实现多线程运行很方便，只需要定义java类时继承Thread类或者Runnable接口，便可以实例化出支持新线程运行的对象。

线程安全是多线程编程中最需要我们重视的问题，大多数bug也都是因为多个线程同时对同一资源（OS课程中称其为临界资源）进行访问和操作导致的。在java中我们可以使用java提供的关键字synchronized和lock实现对对象的同步操作。在本单元作业中我一直使用的synchronized对对象加锁。为了防止产生线程安全bug，在我这几次作业编程中，每次对临界资源访问时，如 isEmpty()，size()，get等，都要把依赖于本次访问的代码段全部使用synchronized将相应资源锁住，防止在对该资源操作时，它的前提条件被其他线程改变，从而导致对临界资源操作出错。

synchronized关键字被称为对象锁，对这个对象锁的理解和使用在一开始确实让我有点晕头转向，而且一直到了第三次作业我还在互测所在屋中发现有人对所有方法盲目的使用了synchronized，而且实际上并没有实现线程安全，仍然存在线程安全bug（但是本地90%+的错误率，交了好多次，神秘的评测机就是测不出来，很玄妙），因此我想在自己的博客中根据自己的理解做个小结。synchronized加锁方式有很多，在本单元作业中我了解到的加锁方式和对相应加锁方式的理解如下：

• 对整个类加锁

class ClassName {
   public void method() {
      synchronized(ClassName.class) {
         code1;// todo
      }
   }
}

此时的synchronized不再简简单单的是“对象”锁，而是实现对整个类的对象的同步。这个加锁方式产生的效应就是所有从该类实例化的对象在调用该方法时，均使用同一把锁。例如：当我们在两个不同线程t1,t2中，创建出该类的两个不同的对象o1,o2，当线程t1中的o1调用加了“类锁”的方法且还没有运行结束释放这把锁时，线程t2中的o2若想调用加了“类”锁的方法就会被阻塞，直到锁被释放。

• 对某个对象加锁

class ClassName {
   public void method() {
      synchronized(object) {
         code1;// todo
      }
   }
}

这个方式最好理解，也最符合synchronized的外号“对象锁”，当某个线程拿到了这个对象的锁的钥匙并且对没有释放时，其他线程中想要访问同一对象时就会被阻塞。

• 对某个非静态方法或代码块加锁

class ClassName {
   public synchronized void method() {
   		code1;// todo
   }
}

class ClassName {
   public void method() {
      synchronized(this) {
         code1;// todo
      }
   }
}

这两种方式是最容易被误解的，它们是对实例化出的对象自身加锁，而不是对方法加锁。虽然写法上有区别，但实际上并没有任何区别，因为synchronized是实现对象锁，当我们采用这两种方式对类中方法或代码块加锁时，并不是任意线程只有一个线程能调用被加锁的方法或代码块，而是这个类的实例化对象在不同线程中不能同时调用被加锁的方法和代码块，例如：线程t1中调用o1加锁的方法还未释放时，线程t2若想调用同一对象o1的加锁的方法就会被阻塞，但是如果线程t1中调用o1加锁的方法还未释放时，线程t2若想调用另一对象o2的加锁的同一方法时并不会被阻塞，这两种方式看起来是对方法加锁，实际上只是对该类实例化出的对象自己本身加锁的简写，将方式四中的this理解为自身这个对象而不是代码块可能更好理解。

• 对静态方法加锁

class ClassName {
   public static synchronized void method() {
   		code1;// todo
   }
}

这种方式才是真正对方法加锁，当一个线程调用该静态方法且未释放锁时，其他线程若还想调用就会被阻塞。

学到的有关设计的知识

• 耦合与解耦

  类之间的耦合度就是设计的这几个类之间的依赖性，耦合越高说明依赖性越高，说明代码维护需要考虑的东西越多，维护越难，因此好的设计应该让耦合尽量的降低，也就是解耦。

  在本次作业中我采用解耦的策略就是尽量让某个类只干自己该干的事，某个对象该干什么，某个方法应该是什么对象干的，这应该是在设计之初就考虑的事，然而直到最后我才意识到应该要解耦，修改代码，因此这几次作业可以说是比较混乱了

  本单元作业中我主要将人这一类的功能与电梯尽量分开，如判断人是否进入电梯，他在上了某状态的电梯后应改在哪层下电梯，他是否应该上某状态的电梯，以及出电梯、进电梯的行动等，这些都不应该是调度器或电梯干的活，而应该是调度器告诉人现在有一个状态为a的电梯b，通过消息交互，让人自己就能决定出来的东西，因此放在人这一类中更好。

• SOLID设计原则

  本单元作业中，在设计之初并未了解过这几项原则，之后在用这五项原则重新检查审视自己的代码时，发现除了曾经尽力实现SRP原则之外，其他原则完全没有做到，垃圾设计没跑了。

• 消费者生产者模式

  个人理解就是多个消费者线程和多个生产者线程对临界资源Tray（托盘）进行访问和操作的模式。在本单元三次作业中，我均使用消费者生产者模式，获取请求线程就是生产者，各个电梯就是消费者，而共同维护的保存请求的队列就是Tray，这种需要由电梯自己决定运行策略，调度器显得很鸡肋，因此感觉这种架构并不夠好，只能勉强应付这单元的三次作业。

• 工厂模式

  在本单元作业中为了追求好写而忽略了架构的拓展性，而且没有仔细考虑OCP设计原则，因此也没有使用工厂模式，需要反思。

• Worker Thread模式

  由于自己被消费者生产者模式限制了思维，直到最后第三次作业仍然使用消费生产者模式，没有使用该模式。

三次作业分析

第一次作业

• 调度方法

  无捎带傻瓜调度

• 实现细节

  • 线程安全保障：第一次作业由于无需考虑捎带，请求队列的功能较为简单，即将请求放入队尾，获取队首请求，因此直接使用java自带线程安全和阻塞功能的容器BlockingQueue，很方便，在此附上使用时的参考链接BlockingQueue学习参考
  • 生产者线程：每当生产者线程获得新的请求时，将改请求保存入请求队列。当输入请求结束时，向请求队列中保存 FROM-0-TO-0 这样的请求，作为结束标志并且结束线程。
  • 电梯线程：使用BlockingQueue自带方法take获取第一个请求，如果为结束标志则结束线程，否则满足该请求的需求。

• 代码结构

project
|--- readme.md
|--- .gitignore
|--- src
    |--- Elevator.java
    |--- Main.java
    |--- Person.java
    |--- Request.java

• 代码文件说明
  • Main.java：包含main函数，项目入口
  • Elevator.java： 电梯类，继承Runnable接口，控制单部电梯运行
  • Request.java： 请求类，继承Runnable接口，处理外部请求
  • Person.java： 人类，包含人的属性和行为
• 图示分析

​ 通过耦合图可以看出，本次作业的架构还是挺好的，因为需求简单，设计起来也很简单，写起来需要考虑的架构问题也很少。

• 架构分析

  生产者消费者模型可以完美解决傻瓜调度下的本次作业，因此使用生产者消费者模型。在第一次作业的傻瓜调度中使用BlockingQueue这一java本身自带的线程安全容器，并且只有一部电梯，可以较好的实现对临界资源的保护，保证项目的正确性，但由于BlockingQueue本身的功能限制（只能依次拿出元素，也可能是我没了解全），因此在之后几次需要实现有捎带功能的电梯时，需要舍弃BlockingQueue，自己实现对容器进行线程安全的操作。

• bug分析

  本次作业较为简单，没有出现逻辑上或者线程安全上的bug，同屋人也都没有出现问题。

第二次作业

• 调度方法

  基于ALS的并向LOOK方向略微优化的调度方法。

  在课程组要求的ALS的基础上

  • 添加了电梯空转时可以更换主请求的优化（电梯空转：电梯正在向某一方向运行准备接人，并且电梯中没有人）如：电梯得到第一个主请求为1- FROM - 10 - TO - 9，当电梯运行到 5 楼时，又发现有请求 2 - FROM- 5 - TO - 14，此时令 2 号进入电梯，并且将主请求替换为 2 号。该优化存在特殊数据超时风险。-
  • 添加了电梯掉头时减少开关门次数的优化。如：1-FROM-1-TO-5;2-FROM-5-TO-1电梯在5楼只进行一次开关门操作。该优化存在特殊数据超时风险。

• 实现细节

  • 线程安全保障：使用Vector保证每个操作是线程安全的，每次对临界资源访问时，如 isEmpty()，size()，get等，都要把依赖于本次访问的代码段全部使用synchronized将相应资源锁住，防止在对该资源操作时，它的前提条件被其他线程改变，从而导致对临界资源操作出错。
  • 生产者线程：每当生产者线程获得新的请求时，将该请求保存入请求队列，并唤醒电梯线程。当输入请求结束时，向请求队列中保存 FROM-0-TO-0 这样的请求，作为结束标志并且结束本线程。
  • 消费者线程：每当电梯线程被唤醒时，首先判断请求队列是否为空，若为空，则进入wait状态，否则进入运行状态。当电梯处于运行状态时，如果电梯中没有人且请求队列为空，则进入wait状态，否则继续运行。每当电梯开始运行或运行到某一楼层时，检测是否有人需要进门或出门，若是，则打开门让人进出，否则继续运行。

• 代码结构

project
|--- readme.md
|--- .gitignore
|--- src
    |--- Elevator.java
    |--- Main.java
    |--- Person.java
    |--- Request.java

• 代码说明
  • Main.java：包含main函数，项目入口
  • Elevator.java： 电梯类，继承Runnable接口，控制单部电梯运行
  • Request.java： 请求类，继承Runnable接口，处理外部请求
  • Person.java： 人类，包含人的属性和行为
• 图示分析

​ 通过图可以看出这次架构与上次相比较差，因为加入的许多优化有点面向过程的感觉，而且是在写完ALS之后才陆陆续续打得补丁，作业完成质量一般。

• 架构分析

  第二次作业我仍然使用消费者生产者模型，并且在该模型下是由消费者自主对产品抢的过程，因此感觉调股器很鸡肋，而且当时的我已经做好了第三次作业重构的打算（这样的态度不对，需要反省），因此在再三考虑之后去掉了调度器类（不过可能是由于自己对自己要求变低了，而且感觉能力有限实现电梯之间的协作太复杂，第三次作业最终还是没有重构，仍然是由多电梯共同抢请求）。该架构写起来比较简单，而且在不考虑电梯间协作的优化下可以进行一定程度的拓展，可见消费者生产者模式还是蛮经典的架构。

• bug分析

  作业还是没有出现和被找到bug，不过没啥性能分，强测中没有出现能卡掉我调度方法的数据还真的是幸运啊。

第三次作业

• 调度方法

  基于 SCAN 的向 LOOK 方向优化的调度方法。

  • 请求处理策略：对于电梯i来说，若某请求无需换乘便可解决并且电梯i可以解决该请求，则电梯i拥有“抢”该请求的资格，若某请求必须要换乘才可解决并且该请求的起始楼层在电梯i的可停靠范围内，则电梯i拥有“抢”该请求的资格。对于输入的请求i，等待被三个电梯中具有“抢”该请求资格的电梯抢。
  • 三个电梯最初基础调度方法：SCAN扫描算法，从顶到底循环扫描，将当前状态下，目的地与电梯同方向的可以“抢”的请求，按相遇的先后顺序在不超载的情况下全部捎带。
  • 添加对扫描范围的优化。每个电梯在根据自己电梯里的人和待处理的请求队列中的请求按照某种策略实时更改自己扫描运行的范围，减少无用的空转时间。
  • 添加减少开关门次数的优化。如：1-FROM-1-TO-5;2-FROM-5-TO-1电梯在5楼只进行一次开关门操作。

• 实现细节

  • 线程安全保障：虽然这次有三个电梯，但我的请求队列也就是Tray仍然只有一个，因此每次对着一个托盘操作时将托盘锁住，仍然类似第二次作业即可。
  • 生产者线程：每当生产者线程获得新的请求时，将该请求保存入请求队列，并唤醒电梯线程。当输入请求结束时，向请求队列中保存 -1 - FROM-0-TO-0 这样的请求，作为结束标志并且结束本线程。
  • 消费者线程：每当电梯线程被唤醒时，首先判断请求队列是否为空，若为空，则进入wait状态，否则进入运行状态。当电梯处于运行状态时，如果电梯中没有人且请求队列为空，则进入wait状态，否则继续运行。每当电梯开始运行或运行到某一楼层时，首先通过对自身队列和请求队列的检测，决定自己的运行范围，再根据自己当前的运行范围，决定自己的运行方向，之后判断是否有人需要进门或出门，若是，则打开门让人进出，否则继续运行。

• 代码结构

project
|--- readme.md
|--- .gitignore
|--- src
    |--- ElevatorA.java
    |--- ElevatorB.java
    |--- ElevatorC.java
    |--- Main.java
    |--- Person.java
    |--- Request.java
    |--- OutputHandler.java
    |--- Dispatch.java

• 代码说明
  • Main.java：包含main函数，项目入口
  • ElevatorA.java： 电梯类，继承Runnable接口，控制A电梯运行
  • ElevatorB.java： 电梯类，继承Runnable接口，控制B电梯运行
  • ElevatorC.java： 电梯类，继承Runnable接口，控制C电梯运行
  • Request.java： 请求类，继承Runnable接口，处理外部请求
  • Person.java： 人类，包含人的属性和行为
  • OutputHandler：输出类，用于将课程组提供的线程不安全的输出接口封装为线程安全的输出
  • Dispatch：调度器类，包含一些对请求队列的静态的检索方法
• 图示分析

​ 果然，这次的架构非常垃圾orz。而且有三个只是属性不同的类，写出这种代码的我看着都很难受，而且这次作业由于还是生产者消费者模型，调度器仍然比较鸡肋，正如一开始提到的解耦考虑的也不全面。

• 架构分析

  第三次作业仍然是消费者生产者模型。本次作业架构十分垃圾，没能正确预估个人能力，最初的想法是给予A、B、C不同的调度方法，因此电梯写了三个类，也没有使用继承，然而最终由于各种各样的想法和抉择，还是选择了三个电梯都用同一种调度方法，这就导致了自己最终每次对电梯调度进行优化时，都要同时改三份源代码，真的是惨痛教训。

• bug分析

  第三次作业也还是没有被自己或互测中的同学发现bug，而且出乎意料的性能分也不错。

自己强测或互测出现的bug分析

第一次作业较为简单，没有出现逻辑上或者线程安全上的bug，同屋人也都没有出现问题。

第二次作业还是没有出现和被找到bug，不过没啥性能分，强测中没有出现能卡掉我调度方法的数据还真的是幸运啊。

第三次作业也还是没有被自己或互测中的同学发现bug，而且出乎意料的性能分也不错。

互测发现别人bug的策略

第一次由于作业较为简单，大概看了下大家的代码感觉没什么问题，为了满足活跃度交了几个空刀。

第二次互测中，开始和舍友一起合作搭建包括生成数据、输出数据、结果判断的自动评测脚本，并且和同学交流尝试他们屋出现的bug在自己屋是否适用，但最终并没有测出bug。

第三次互测中，针对改变的需求改善自己的脚本，同时保持和别的同学的交流。很幸运的通过测评脚本发现了一个同学在某个数据的测试中出现了bug，在发现有bug之后，我通过输入数据以及输出数据的对比，来判断他是在对哪个请求处理时出现了bug，并观察该请求的特征和他输出的特征，定位他应该是哪部分逻辑或线程出了问题，再通过阅读代码来寻找代码中的bug，最后通过构造这一类数据验证他的bug。然后把在本地测试时，他错误率超过90%的数据提交上去，然后评测机表示他没bug，然后多交好几次之后评测机仍然对他非常宽容