OO_BLOG2_多线程电梯模拟

作业2-1 单部多线程傻瓜调度（fafs）电梯的模拟

i. 基于度量的程序结构分析

1）程序结构与基本度量统计图

2）分析

​ 这次作业基本奠定了本人三次电梯作业的基本架构，简述如下：

• elevator类：定义了”电梯“这一对象，即拥有开关门状态（state：close or open），电梯内乘客队列（passenger），当前楼层（floor：ground~top）等。
• passengerqueue类： 共享资源区。拥有push()，pop()，isempty()方法。
• elevatordispatcher类：电梯调度器。负责接受请求，安排电梯上下以及乘客上下（upordown()）。
• mainclass类：负责初始化并启动elevatordispatcher，以及接受请求并存入passengerqueue。

ii. 多线程的协同和同步控制

• 我采用的是典例“生产者消费者”的逻辑。mainclass代表“生产者” 线程，负责接受请求并将请求存入passengerqueue；elevatordispatcher相当于“消费者” 线程，负责从passengerqueue中取出请求，然后运行电梯到指定位置（处理请求）；passengerqueue是共享资源，利用wait和notify的组合，来确保对共享资源的存和取是互斥的。

• // 下为临界区的代码 
  private volatile queue<personrequest> requests = new linkedlist<>();
  
      public synchronized void push(personrequest request) {
          requests.offer(request);
          notifyall();
      }
  
      public synchronized personrequest pop() {
          while (requests.isempty()) {
              try {
                  wait();
              } catch (interruptedexception e) {
                  e.printstacktrace();
              }
          }
          personrequest r = requests.poll();
          return r;
      }

iii. 程序bug分析

• 本次程序结构较简单，大家都没有出现错误。

iv. 程序测试策略

1）白盒测试

• 大多数人（包括我）第一次接触多线程编码，但由于本次程序设计建构较简单。故虽然在编码的过程中有些阻碍，最终结果总归还是差强人意的。
• 观察发现大部分同学都是采用“生产者消费者”的典例逻辑进行编写的。

2）黑盒测试

• 定时投放指令，随机测试（由于电梯结构与逻辑都较简单，故未进行大量测试）。

v. 关于程序优化的思考

• elevator类中有若干多余的参数，可以舍弃；
• elevatordispatcher类的run()中集成了太多方法，为了进一步的拓展，应进行拆分。

作业1-2 单部多线程可捎带调度（als）电梯的模拟

i. 基于度量的程序结构分析

1）程序结构与基本度量统计图

2）分析

• 其实这一次的电梯只是上一部电梯的扩充，对调度算法进行了改进，整体结构没有发生变化。

• 我继承下来了elevator1的代码，并对其中的elevatordispatcher类进行了改写；

  public void run() {
          while (true) {
              // 读取当前电梯内的乘客队列到 passengers
              arraylist<personrequest> passengers = elevator.getpassengers();
  
              /* 初始化。判断电梯内乘客的情况：
               * 若电梯内无乘客且队列内读到null，电梯下班；
               * 若电梯内无乘客且队列内有乘客，peek()，然后控制电梯去接乘客；
               * 同时，判断电梯是否需要转向，若转向，则对标志位isup进行取反 */
              if (initialize(passengers)) {
                  return;
              }
  
              // 遍历电梯内乘客，将需要已到达的乘客从电梯内取出，加入removes 
              arraylist<personrequest> removes = getremoves(passengers);
              // 读取当前排队乘客队列
              arraylist<personrequest> requests = passengerqueue.getrequests();
              // 遍历电梯内乘客，将需要顺路的乘客从乘客队列内取出，加入adds 
              arraylist<personrequest> adds = findpassengers(requests);
  
              // 乘客上下电梯（先下后上）
              onoroff(removes, adds, requests);
  
              if (elevator.getpassengers().isempty() &&
                      (passengerqueue.isempty() || elevator.gettarget() == floor)) {
                  // 若电梯内无乘客（所有乘客都在这一层下，且无乘客顺路或上电梯），则电梯等待
                  elevator.settarget(0);
              } else { // 否则，电梯运行（向上一层 或 向下一层）
                  floor = upordown(floor, elevator.isup());
              }
          }
      }

• 同时，值得注意的是，在本次电梯中，由于电梯可以从-3层到15层上下运行，电梯没有0层，所以在1层到-1层之前有一个特殊的跨越。我的处理方法如下：

  if (isup) { // 电梯上行时
    floor++; // 楼层增一
      if (floor == 0) { 
        floor++; // 如果电梯运行到0层，楼层号继续增一，到达一层
      }
  } else { // 电梯下行时
    floor--; // 楼层减一
    if (floor == 0) { 
        floor--; // 如果电梯运行到0层，楼层号继续减一，到达负一层
    }
  }

ii. 多线程的协同和同步控制

• 由于本次作业，仅仅修改了电梯的调度策略，未对电梯结构进行修改，也未增添新的进程，故为引入新的线程安全风险，所以多线程的协同和同步控制的原理与上一次作业相同，不再赘述。

iii. 程序bug分析

1）自身错误

• 未出现线程安全问题与逻辑错误

2）他人错误

• 输出冗余： 两次输入间隔时间较长时，会重复输出arrive语句;

  stdin:
    [0.0]1-from--2-to-11
    [20.0]2-from-15-to-9
  stdout:
    [   0.8530]arrive--1
      [   1.2540]arrive--2
      [   1.2550]open--2
      [   1.6560]in-1--2
      [   1.6560]close--2
      [   2.0570]arrive--1
      ......
      [   6.4690]arrive-11
      [   6.4690]open-11
      [   6.4700]out-1-11
      [   6.8700]close-11
      /******* 这里第二条需求指令加入 *******/
      [  19.9120]arrive-11 /** 重复输出 **/
      ......
      [  21.5150]arrive-15
      [  21.5160]open-15
      [  21.9160]in-2-15
      [  21.9170]close-15
      [  22.3180]arrive-14
      ......
      [  24.3220]arrive-9
      [  24.3220]open-9
      [  24.3230]out-2-9
      [  24.7240]close-9

  • 错因：当请求处理结束时，电梯停止在当前楼层，但这种停止是动态停止，即每次上（下）0层。

iv. 程序测试策略

1）白盒测试

• 由于本次设计架构变得较为多样化，阅读代码更多时候是作为一种辅助工具，为了使测试更加有针对性，在随机测试的基础上，可通过阅读代码和思考架构以便根据实际状况添加一些限制。

2）黑盒测试

• 由于本次作业程序输出可能较为复杂，肉眼很难判断正误，自动化评测显得必不可少。
• 自动化测试带来方便，但是也有弊端，即评测得到的错误多为同质，但由于输入输出往往较长，肉眼依旧难辨。为解决这一问题，我采取了观察+人工修改重测的方法，效率较低但是最终结果可靠。

v. 关于程序优化的思考

• 本次程序的优化主要在于电梯调度的算法
• 根据度量来看，我的elevatordispatcher类的耦合度过高，需要对此进行优化
• 由于程序的继承性，所有关于优化的思考将在下一节进行陈述

作业1-3 多部多线程智能（ss）调度电梯的模拟

i. 基于度量的程序结构分析

1）程序结构与基本度量统计图

2）分析

本次作业是oo课程第二单元的重头戏。下面对本次程序进行分析。

• elevator 类：仅定义电梯的基本属性——上下行状态（isup），目标楼层（target），电梯内乘客队列（passengers）；

• elevatordispatcher 类：严格意义上不能称为调度器，更像是安装在电梯上的控件，每一个elevator与一个elevatordispatcher相结合形成一个可以自主地按照自己的一套规则接受乘客请求、上下行接送乘客。（这样的设计是为了较简单地继承上一次的电梯，但是使得进一步的优化变得困难。）

• mypersonrequest 类：这个类重新定义了一种乘客请求的类型 —— mypersonrequest ，它包含了对初始请求的储存，以及对乘客请求的分析分解的方法：

  public class mypersonrequest {
      private static final int a = 1;
      private static final int b = 2;
      private static final int c = 4;
      private personrequest request; // 本次请求
      private int worker; // 负责处理该请求的电梯编号
      private int transfer; // 电梯最终目的地（仅在换乘时有意义，请求无需换乘时置为0）
  
      mypersonrequest(personrequest request) {
          this.request = request;
          this.transfer = 0;
          this.worker = 0;
          demandanalysis();
      }
    /********************************************************
      * demandanalysis() 函数作用：根据请求与电梯实际进行分解，并分配任务给不同的电梯 *
      * 判断函数示例如下：                                         *
    *********************************************************/    
      private void demandanalysis() {
          int from = request.getfromfloor();
          int to = request.gettofloor();
  
          switch (from) {
              case -3: {
                  minusthree(to);
                  break;
              }
              case -2:
              case -1: {
                  minusone(to);
                  break;
              }
              case 1: {
                  one(to);
                  break;
              }
              case 2:case 4:case 6:case 8:case 10:case 12:case 14: {
                  evennumber(to);
                  break;
              }
              case 3: {
                  three(to);
                  break;
              }
              case 5:case 7:case 9:case 11:case 13: {
                  oddnumber(to);
                  break;
              }
              case 15: {
                  fifteen(to);
                  break;
              }
              case 16:case 17: case 18:case 19:case 20: {
                  minusthree(to);
                  break;
              }
              default: {
                  throw new runtimeexception(
                          "mypersonrequest has somethig wrang!");
              }
          }
      }
      private void minusthree(int to) {
          worker = a;
          if (to >= 2 && to <= 14) {
              updaterequest(1);
          }
      }
     /***********************
      * 此处省略其他方法的细节 *
    ***********************/    
  }

• mypersonrequest 类：这个类重新定义了一种乘客请求的类型 —— mypersonrequest ，它包含了对初始请求的储存，以及对乘客请求的分析分解的方法：

  public class passengerqueue {
      private volatile arraylist<mypersonrequest> requests = new arraylist<>();
      private volatile int trannum = 0; // 需要转乘而未被转乘的人数
  
      // 检测removes（即下电梯的乘客队列）中需要被换乘的乘客，
      // 并将其tofloor和fromfloor更改后，重新加入passengerqueue。
      synchronized void pickup(personrequest request) {...}
  
      synchronized void subtrannum() { trannum--;}
      synchronized int gettrannum() { return trannum;}
  
      /* 下列函数并未作更改 */
      synchronized void push(personrequest request) {...}
      synchronized mypersonrequest peek() {...}
      synchronized void remove(int index) {...}
      synchronized arraylist<mypersonrequest> getrequests() {...}
      synchronized boolean isempty() {...}
  
    /*******************************************
     * 下面这一函数为互测后打的补丁，并非一开始的设想 *
     *******************************************/
      synchronized void insertbefore() {
          int size = requests.size();
          mypersonrequest via = requests.get(size - 1);
          mypersonrequest o = requests.get(0);
          requests.set(0, via);
          requests.set(size - 1, o);
      }
  }

• 下面是elevatordispatcher类的run()方法，展示了程序的基本逻辑。

    public void run() {
            while (true) {
                arraylist<mypersonrequest> passengers = elevator.getpassengers();
                int r = initialize(passengers);
                if (r == -1) { 
                    return;
                } else if (r == 1) {
                    if (parks[floor + 3] == 1) {
                        arraylist<mypersonrequest> removes = getremoves(passengers);
                        pickuppassenger(removes);
                        arraylist<mypersonrequest>
                                requests = passengerqueue.getrequests();
                        arraylist<mypersonrequest> 
                                adds = findpassengers(requests);
                        onoroff(removes, adds, requests);
                    }
                    if (elevator.getpassengers().isempty() &&
                            (passengerqueue.isempty() ||
                                    elevator.gettarget() == floor)) {
                        elevator.settarget(0);
                    } else {
                        floor = upordown(floor, elevator.isup());
                    }
                } else {
                    try {
                        thread.sleep(400);
                    } catch (interruptedexception e) {
                        e.printstacktrace();
                    }
                }
            }
        }
    }

ii. 多线程的协同和同步控制

• 本次多线程的协同和同步控制仍是继承了之前的管程的思想，利用passengerqueue的来保证各电梯的取用之前是互斥的，同时请求的放入与取用也是互斥的。
• 各电梯之间不存在直接通信，只通过passengerqueue中定义的trannum变量来间接完成需求的通信。
• 具体的实现与第一次作业不尽相同，故不赘述。

iii. 程序bug分析

1）自身错误

​ 本次测试，强测点有8个未通过，互测点有4个未通过，数目令人触目惊心，节选如下：

stdin	stdout
[1.0]21-from-3-to-1 [1.0]22-from-3-to-2 [1.0]23-from-3-to--3 [1.0]24-from-3-to-4 [1.0]25-from-3-to-5 [1.0]26-from-3-to-6 [1.0]27-from-3-to-7 [1.0]28-from-3-to-8 [1.0]10-from-3-to--2 [1.0]11-from-3-to--1	passenger 22 has not arrived at his/her target floor yet
[0.0]1016036187-from-10-to-6 [0.1]1289556284-from-14-to-16 [0.1]587468376-from--1-to-3 [0.1]1477225549-from-20-to-2 [0.3]804572881-from-9-to-10 [0.4]2064667476-from-18-to-10 [0.5]1489802222-from-17-to-11 [0.6]615855192-from-17-to-13 [0.6]1994863070-from-5-to-7 [0.8]1793333371-from-7-to-2 [2.6]353255777-from-11-to--2 [2.7]403262883-from-15-to-14 [39.3]492338565-from--3-to-6	判定信息： real_time_limit_exceed 实际 cpu 时间：1.256 秒 最大允许的 cpu 时间：10 秒 实际运行时间：210.016 秒 最大允许的运行时间：210 秒 实际运行内存：79.58203125 mb 最大允许的运行内存：768 mb

• 分析：

  • 现象分析：这两个错误看似是两个不同的错误（996.icu与提前下班），但其实问题出在一个地方——null请求在队列中的位置不定，导致电梯不能正确停止。

  • 错因分析：

  • /****************************************************************************
     * 表面错因：在elevatordispatcher类的run()函数的第一步——initialize()方法中，
     *          读取到null时，乘客队列不为空。
     * 根本错因：由于线程安全问题，在pickup换乘请求时，调用了size()等不安全方法，
     *          导致请求的插入未插入到null的前面：
     *          理想情况 —— passenger1-passenger2-passenger3-null
     *          实际情况 —— passenger1-null-passenger2-passenger3
     * 修改措施：如下。
     ****************************************************************************/
    private synchronized int initialize(arraylist<mypersonrequest> passengers) {
            if (passengers.isempty() && elevator.gettarget() == 0) {
                mypersonrequest pr = passengerqueue.peek();
                if (pr == null) {
                    if (passengerqueue.gettrannum() == 0) {
                        if (passengerqueue.getrequests().size() > 1) {
                            /*************************************
                             * 当读取到null，但乘客队列中仍有非空请求 *
                             * 将位于null之后的请求置前。           *
                             ************************************/
                            passengerqueue.insertbefore();
                            return 0;
                        } else {
                            return -1;
                        }
                    } else {
                        return 0;
                    }
                } else if (((pr.getworker() & flag) == 0)) {
                    return 0;
                } else {
                    if (floor == pr.getfromfloor()) {
                        elevator.setup(pr.getfromfloor() < pr.gettofloor());
                    } else {
                        elevator.setup(floor < pr.getfromfloor());
                    }
                    if (floor == pr.gettofloor()) {
                        elevator.settarget(pr.getfromfloor());
                    } else {
                        elevator.settarget(pr.gettofloor());
                    }
                }
            } else {
                if ((floor == top) || (floor == bottom)) {
                    elevator.setup(!elevator.isup());
                }
                timableoutput.println("arrive-" + floor + "-" + name);
            }
            return 1;
        }

2）他人错误

• elevator c cannot open at floor -2 because this floor is not reachable
• passenger 22 has not arrived at his/her target floor yet
• exception in thread "thread-61" java.lang.arrayindexoutofboundsexception: -1

iv. 程序测试策略

• 本次程序测试的输出无法肉眼判断，基本只能用评测程序进行数据比照；
• 周围优秀的同学们应用各种工具编写了对拍器与评测机，在评测时应用这些可以大大节省掉重复的机械试错带来的时间消耗。

v. 关于程序优化的思考

1）结构优化

• 从度量图看出，程序耦合性较大，如果进行结构优化，可能只有重构了。

2）算法优化

• 由于没有独立的调度器，我的电梯只是“低级智商”——只能按照一定的规则进行读取、接送，而不能综合判断采用怎样的调度可以使时间最短。
• 如果进行优化的话，我选择进行“改良”的方法：
  • 首先，在电梯需求分解阶段，实现更优分析，能分配给a就不分配给b、c；
  • 其次，无请求时，电梯向中间层靠拢；
  • 最后，在电梯接请求时，设置优先级，时间短者优先（这就要求进程间通信）
• 以上只是我的一些想法，实现层次上还有一些问题。

vi. solid原则分析

• srp 单一责任原则	未满足，mypersonrequest类既存储，又分析
  ocp 开放封闭原则	未满足，请求的分析被写死了，扩展只能重写方法
  lsp 里氏替换原则	无父子继承类
  dip 依赖倒置原则	基本满足
  isp 接口分离原则	基本满足

作业1-4 面向对象课程第一单元学习感想

i. 对自己的程序要更狠一点， 对自己的程序要更狠一点， 对自己的程序要更狠一点；

ii. 在elevator3的漫长的debug过程中，我体会到了线程安全的重要性，也发现了自己在此方面的欠缺，定一个小目标，2周内读完《多线程编程实战教程》这本书，必能做一些相应的练习；

iii. 面向对象的思维方式不是一蹴而就的，课堂之外需要多读代码，多做练习，尤其是在课上测试的时候，发现对多线程编程的一些常用操作没有较好的掌握，需要更加认真地去学习；

iv. 要提高自己新旧知识的融会贯通能力，复习与预习双轨并行；

v. 要调整好自己的心态，不要过于畏惧，更不要懈怠！

最后，衷心感谢为这门课程辛苦付出的老师和助教。