BUAA OO hw5 && hw6

本次作业的基本目标是模拟多线程实时电梯系统，熟悉线程的创建、运行等基本操作，熟悉多线程程序的设计方法，掌握线程安全知识并解决线程安全问题。

前言

由于第五次作业对电梯调度策略和电梯运行策略没有理解清楚，导致逻辑混乱，对电梯的状态更新复杂从而出现了bug，以及调度策略有问题导致时间性能较差。于是第六次作业进行了重构，采取了新的策略，目前评测机反馈正确性和性能都是可以的。

前置知识

继承、接口、多态形成了面向数据和行为抽象的层次结构 （关注数据抽象和行为抽象）

线程、共享、交互形成了面向并发和协同抽象的层次结构 （关注并发行为的安全和效率）

final 关键字

1. 修饰类：表明这个类不能被继承。
2. 修饰方法：把方法锁定，以防任何继承类修改它的含义。
3. 修饰变量：对于一个final变量，如果是基本数据类型的变量，则其数值一旦在初始化之后便不能更改；如果是引用类型的变量，则在对其初始化之后便不能再让其指向另一个对象。

线程的互斥处理（monitor）—— synchronized

一个实例中的 synchronized 方法每次只能由一个线程运行，对非 synchronized 方法没有影响。

每个实例拥有独立的锁。

只在共享对象中设置同步块，仅使用同步块中的共享对象来守护该同步块。

// synchronized 代码块
synchronized(expr) { // expr 为获取锁的实例
	...
}

// synchronized 实例方法和 synchronized 代码块
synchronized void method { // 使用this的锁来执行线程的互斥处理
    ...
}
void method {
	synchronized (this) {
		...
    }
}

线程的协作 —— wait, notify, notifyAll

wait, notify, notifyAll 都是 java.lang.Object 类的方法。

每个实例都拥有一个等待队列，放置在执行实例的 wait 方法后停止操作的线程。

若要执行 wait, notify, notifyAll 操作，线程必须持有锁。如果线程进入等待队列，便会释放其实例的锁。

obj.wait(); // 线程正在obj上等待
wait; // 线程正在this上等待
this.wait(); // 线程正在this上等待

obj.notifyAll(); // 在obj实例的等待队列中休眠的所有线程都会被唤醒 
notifyAll(); // 在this实例的等待队列中休眠的所有线程都会被唤醒 
this.notifyAll(); // 在this实例的等待队列中休眠的所有线程都会被唤醒 

Producer-Consumer 模式

• Data：由 Producer 生成，供 Consumer 使用。
• Producer： Producer 生成 Data，并将其传递给 Channel。
• Consumer：从 Channel 获取 Data 并使用。
• Channel：保管从 Producer 获取的 Data，并响应 Consumer 的请求，传递 Data。为了确保安全性，Channel 会对 Producer 和 Consumer 的访问执行互斥处理。

一个简单的例子：

import static java.lang.Thread.sleep;

public class MainClass {
    public static void main(String[] args) {
        Buffer buffer = new Buffer();
        new Producer(buffer).start();
        new Consumer(buffer).start();
    }
}
class Producer extends Thread {
    final Buffer buffer;
    public Producer(Buffer buffer) {
        this.buffer = buffer;
    }
    @Override
    public void run() {
       for (int i = 0; i < 10; i++) {
           buffer.push();
       }
    }
}

class Consumer extends Thread {
    final Buffer buffer;
    public Consumer(Buffer buffer) {
        this.buffer = buffer;
    }
    @Override
    public void run() {
        for (int i = 0; i < 10; i++) {
            buffer.pop();
        }
    }
}
class Buffer {
    int cnt = 0;
    boolean haveGoods = false;
    // 生产者放入商品
    public synchronized void push() {
        if (haveGoods) { // 已有货物，消费者取出商品
            // 生产者等待消费者消费
            try {
                this.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        if (!haveGoods){ // 被消费者通知生产
            cnt ++;
            System.out.println("Producer put:" + cnt);
            haveGoods = true;
            try {
                sleep((int)(Math.random()*100));
            } catch (InterruptedException e) {}
            // 通知消费者消费
            this.notifyAll();
        }
    }
    // 消费者取出商品
    public synchronized void pop() {
        if (!haveGoods) { // 没有货物，生产者生产商品
            // 消费者等待生产者生产
            try {
                this.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        if (haveGoods) { // 被生产者通知消费
            System.out.println("Consumer get:" + cnt);
            haveGoods = false;
            // 通知生产者生产
            this.notifyAll();
        }
    }
}

以上参考《图解 Java 多线程设计模式》。

题目描述

模拟多线程实时电梯系统。系统从标准输入中输入请求信息，程序进行接收和处理，模拟电梯运行，将必要的运行信息通过输出接口进行输出。 具体而言，本次作业电梯系统具有的功能为：上下行，开关门，以及模拟乘客的进出，以及模拟电梯系统扩建和日常维护时乘客的调度。

题目分析

看完题目，我们先理清一些概念：

电梯调度策略：把请求分配给电梯时采取的策略。

电梯运行策略：电梯处理自己的请求队列采取的策略。

通过题目可以发现程序要干的事情无非是：① 获取输入的请求信息；② 处理请求信息：若请求为乘客，则将乘客分配给电梯；若请求为电梯扩建和维护，就更新电梯。③ 电梯接送乘客到指定楼层。

根据多线程设计模式并参考了第三次实验下发的模板代码，我们确定线程数及线程所做的工作为：

1. 输入线程。接收输入请求，若为乘客请求，就将其放入总乘客队列；若为电梯扩建和维护请求，就更新 vector<elevator> 。
2. 调度线程。根据电梯调度策略，将总乘客请求分配给每部电梯的等待队列。
3. 电梯线程。有多少部电梯就有多少个电梯线程，它们之间相互独立的处理各自的等待队列。

整体架构

类：

• MainClass：初始化实例和开启线程。
• InputThread：获取输入的请求，若为乘客请求，就将其放入总乘客队列；若为电梯扩建和维护请求，就更新 vector<elevator> 。
• WaitQueue：总乘客队列。
• Schedule：根据电梯调度策略，将乘客请求分配给电梯的等待队列。
• Elevator：记录电梯的状态，模拟电梯运行过程。
• Strategy：得到电梯下一状态。
• RequestQueue：电梯的等待队列。
• Person：电梯的等待队列。
• Counter：计数器，判断乘客请求是否都处理完，用于线程终止判断。

还没有画类图和时序图啦~ 不如先看看idea自动生成的叭~

线程设计

在上文分析中，我们已经确定了线程的种类及其个数，在此回顾一下：

• 主线程进行初始化和启动其他线程。
• 输入线程获取输入的请求。若请求为 PersonRequest ，就用 addRequest 方法将其放入 WaitQueue 总队列；若请求为 ElevatorRequest，就用 expandElevator 方法将新增电梯放入 ElevatorQueue 电梯队列；瑞请求为 MaintainRequest，就用 maintainElevator 方法维护电梯。
• 调度线程将请求分配给电梯。调度线程从 WaitQueue 中用 getRequest 获取请求，遍历 ElevatorQueue 将请求发给加入该请求后模拟花费时间最少的电梯的 RequestQueue。
• 电梯线程处理 RequestQueue，模拟电梯上行、下行、开关门等行为。其利用 Strategy 获得电梯下一状态，从 RequestQueue 中获取 canPutOn 的请求。

线程安全

线程安全（thread-safe）是关于对象对象是否能被多个线程安全访问的特性。如果一个对象是线程安全的，则无论多个线程以什么样的交叠次序来访问都不会影响该对象的行为结果。

如何会导致线程不安全：

• 读写冲突
  • check-then-act
  • read-modify-write
• 写写冲突（覆盖）

线程安全的设计考虑：

• 使用不可变对象
• 使用可变对象
  • 操作的原子性
  • 共享对象要始终处于严密控制之下
  • 设置范围适当的临界区（临界区最小化）
  • 使用合适的监控器

在我的程序中主要通过 synchronized 语句块完成线程互斥。

此外，对象共享是产生线程安全问题的根本原因。在思考某一部分代码是否会产生线程安全问题时，可以思考其是否会被多个线程访问，线程访问的读写关系等。

线程协作

当某个线程卡在临界区或一直获取不到资源时，会发生轮询，会比较耗费CPU。当你提交时如果遇到 CTLE 可以考虑代码中是否有轮询。比如说当 Schedule 想要获取乘客请求时，waitQueue 为空，此时我们可以让该线程进入 waitQueue 的等待队列，也就是让它 wait 一下。当 waitQueue 非空（即输入线程把乘客请求给了 waitQueue）时，唤醒 waitQueue 的等待队列 （notifyAll）。该部分可以参考前文提到的 Producer-Consumer 模式或 Guard Suspension 模式。

线程终止

线程应该在什么时候终止是一个必须要解决的问题，否则线程一直无法终止会引发 RTLE 问题。这一部分内容有学长推荐看《图解Java多线程设计模式》中的 Two Phase Termination 这一章。我主要是通过实验代码理解。当输入结束，所有乘客请求都处理完成，那么程序就结束了。在介绍每个线程的结束条件之前，我们先来看看线程是如何结束的。run 方式是线程的入口，也是线程结束的位置。

public void run() {
	while (true) {
        if (线程结束条件) {
			break;
        }
        do someting;
    }
}

• 输入线程：由官方文档可知，当读入的 request == null 时说明输入结束，此时传递给 waitQueue end标志位，并结束输入线程。
• 调度线程：在hw5中当输入线程结束并且总队列为空时即可结束调度线程。但是在 hw6 中电梯维护时会把请求还给总队列，前面的条件会触发bug。所以在hw6中我将结束条件改为输入线程结束并且总队列为空并且所有请求已处理完毕（用counter静态类记录请求的出入），此时传递给 RequestQueue end标志位。
• 电梯线程：当 requestQueue end标志位为 true 时结束线程。

具体实现可以参考实验代码。

多线程调试

• 利用调试功能。可以根据输出大致判断出bug触发地，据此选定断点。比如说电梯门开了之后乘客却没有进来，此时就将断点设置在开门的方法。
• 利用 printf 输出。可以输出电梯状态改变、请求状态改变（进入等待队列等信息）、线程状态改变以及观察时间戳等判断。
• 有同学跟我分享了一种方法：设置一个 Debug 类，通过 stderr 抛出异常，这样也不会影响输出检测。

电梯调度策略

电梯调度有很多策略：(1) 模拟电梯保证局部最优解的策略，在输入线程获得一个请求时，深克隆电梯类进行模拟从而将请求分配各所花费时间最少的电梯。(2) 较为均衡的分配方式（第 i 位乘客分配给第 (i % 6) 座电梯），当输入请求数量较多的时候，性能上也还不错。(3) 随机分配方式 random，其实和前者策略差不多。(4) 自由竞争策略，所有电梯共用输入线程的请求队列，当输入一个请求时，所有电梯都努力去获取这个请求，这种策略在时间性能上占据优势，但是电量消耗会比较高。

我在 hw6 中实现了电梯模拟策略，也就是往届所说的 影子电梯。其主要思想为：对于每一个待分配的请求，“涉克隆”电梯此时的状态，将请求放入电梯的等待队列，进行模拟（将上下行开门的 sleep(400) 改为 time += 400），选择最早结束的电梯接收这个请求。和周围同学比较发现这种策略在运行时间和耗电量都比较优。

电梯运行策略

我采用了 look 算法：当电梯在往上走时，如果遇到向上的请求就捎带上，当电梯内没有乘客并且电梯前方没有等待的请求时就换方向。当到达某一楼层时，如果电梯未满并且请求与电梯运行方向一致时，就开门捎带上请求。

String nextState = strategy.getStrategy(floor, direction, fullNum, curInRequests, requestQueue); // strategy 获取电梯下一状态
boolean isEnd = false;
switch (nextState) {
    case "open":
        openAndClose();
        preTime = System.currentTimeMillis();
        break;
    case "keep":
        if (direction) { up(); } 
        else { down(); }
        preTime = System.currentTimeMillis();
        break;
    case "reverse":
        direction = !direction;
        break;
    case "wait":
        direction = true;
        requestQueue.waitRequest();
        break;
    case "end":
        isEnd = true;
        break;
    default:
}

性能优化

• 往届学长提出了“量子电梯”的概念：

  当电梯在等待时，电梯的请求队列获得了请求，电梯开始运动：

  [time1] ARRIVE floor1
  [time2] begin wait
  [time3] end wait
  [time4] ARRIVE floor2

  按照一般同学们的处理，有 $time4 = time3 + 0.4$ 。

  然而我们可以利用 wait 的时间，因为我们仅需保证 time4 - time1 > 0.4 。

  具体实现就是记录电梯最后一次关门、上下行的时间，然后：

  public synchronized void up() {
      long currentTime = System.currentTimeMillis();
      if (currentTime - preTime < speed) {
          try {
              sleep(speed - currentTime + preTime);
          } catch (InterruptedException e) {
              e.printStackTrace();
          }
      }
      floor++;
      TimableOutput.println(String.format("ARRIVE-%d-%d", floor, id));
  }

• 当电梯收到维护请求的时候，需要将电梯还未送达的乘客请求返回给 waitQueue，为了尽量缩短乘客的等待时间，将请求返回到 waitQueue 的队首使他们有限被分配。

结尾

​ 真的好喜欢自己重构后的代码，感觉对线程安全和电梯策略处理的都挺清晰的，在 Toby 的性能测试平台上每个店都能达到99.9以上。希望能安全度过 hw6 的强测和互测啦~

这是2023年4月10日的更新，主要内容为迭代 homework 7。

前言

接上文，hw6的强测和互测没有问题，主要是在强测中有一个点的性能不太好。这个点主要考虑为该情况下的优化：当有很多从同楼层出发前往各不同楼层的请求时（以该数据为例，为了简化我们假设仅有一部电梯），若不做特殊处理，仅按请求进入顺序调度，那么电梯需要从1-11-1接送前6名乘客，再从1-11-1接送第7名乘客。而如果我们按请求出发和到达楼层差的绝对值排序，显然电梯运行的层数会显著减少。所以或许写OO有时间的话，除了评测机，还可以集思广益一些特殊数据捏。

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