欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

OO_Unit2_多线程电梯

程序员文章站 2022-06-11 20:20:53
...

一、第一次作业

1.需求分析

单部多线程傻瓜调度(FAFS)电梯

2.实现方案

输入接口解析

  • 类似于Scanner,我们使用ElevatorInput进行阻塞式读取(第一次作业较简单,没有单独开一个线程,而是直接放在主控类Main中)
  • 读取到null时,表示已经读取完毕,可以退出
  • 本接口只会读取到正确的请求,错误的将跳过并在stderr输出错误信息(不影响程序本身运行,也不会引发RUNTIME_ERROR)
  • 记得在最后进行close()
while (true) {
    PersonRequest request = elevatorInput.nextPersonRequest();
    if (request == null) {
        break;
    } else {
        queue.add(request);
    }
}
elevatorInput.close();

建立类图 第一次作业较为简单,没有多考虑,建立了:

  • 一个Elevator线程(实现run方法)
  • 一个管理请求的队列Queue(线程安全,用于管理请求队列的ArrayList,这里可以①继承自ArrayList;②由ArrayList组成;方法②更好,避免了继承带来的麻烦问题,并可以将队列进行封装:少用继承,多用组合)
    OO_Unit2_多线程电梯
  • 其中:细实箭头代表包含关系,Elevator含有一个指向Queue的指针,用于访问Queue中的请求。
  • 主控类初始化时间戳,创建Queue及Elevator后调用Elevator.start(),最后才开始输入请求。

实现思路

主控类主动向Queue中输入请求put,Elevator向Queue中请求拿出请求get,两者需要互斥:syncronized

  • 在Elevator中,第一次直接使用了轮询:
while (!getEnd() || queue.hasNext()) {
    try {
        request = queue.getRequest();
        ...
    } catch (Exception e1) {
        stay(circleTime);// 每隔circleTime判断一次请求
    }
}
  • 请求结束时,Main调用List中requestEnd方法,Elevator读取List中End:getEnd
//List里方法,Main和Elevator分别访问,需要互斥;在调用requestEnd方法结束时需要notify
synchronized void requestEnd() {
    end = true;
    notifyAll();
}

synchronized boolean getEnd() {
    return end && list.isEmpty();
}

3.测试及修复

测试思路

此次作业相对简单,测试的思路也并不复杂,只需要按照指导书对每一种不同的省略输入进行测试即可

bug修复

本次作业由于使用了轮询机制,cpu占用时间较长,在第二次作业中修复此问题

二、第二次作业

1.需求分析

单部多线程可捎带调度(ALS)电梯

2.实现方案

输入接口解析

同第一次,只是请求的楼层变成了:电梯楼层:-3层到-1层,1层到16层,共19层

建立类图

Main建立了Client 线程和 List请求队列就结束了,再由List创建Worker,典型的线程池(Worker Thread)结构:

TimableOutput.initStartTimestamp();
List list = new List();
Client client = new Client(list);
client.start();

OO_Unit2_多线程电梯

  • 如图,Client Worker各有一个指向List的指针。而List创造并指向Worker;List类中含有private ArrayList<PersonRequest> list;
实现思路

Client主动向List中输入请求put,Worker向List中请求拿出请求get,两者需要互斥:syncronized,改掉了轮询机制。

  • 对于get方法,没有请求时需要在原地等待,再由put唤醒。
synchronized boolean get() {
    while (list.isEmpty()) {
       try {
            if (end) {
                return false;//等待之前判断是否结束了请求
            }
            wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    getOne();//直接分配一个请求;前提:list非空
    getAnother();//在已有的队列中寻求其他请求,并放入Worker
    return true;
}

3.测试及修复

结构分析

  • 复杂度分析(超标及整体)
Method ev(G) iv(G) v(G)
Worker.next() 9 6 10
Class OCavg WMC
Client 2 4
List 3 21
Main 1 1
Worker 2.67 48
Package v(G)avg v(G)tot
xxx 2.96 83
- 如表,Worker.next的ev(G)和v(G)高:
    - 基本复杂度:来衡量程序**非结构化程度**的;高意味着**非结构化程度高**,难以模块化和维护
    - 圈复杂度:用来衡量一个模块判定**结构的复杂程度**,数量上表现为独立路径的条数;
    圈复杂度大说明程序代码可能**质量低且难于测试和维护**
    - 模块设计复杂度:模块设计复杂度是用来衡量模块判定结构,即模块和其他模块的调用关系。
    意味模块**耦合度高**,这将导致模块**难于隔离、维护和复用**。
    ```
    private int next() {
        int i;
        if (up) {
            for (i = minFloor; i <= maxFloor; i++) {
                if (i != 0) {
                    if (getStop(i)) {
                        break;
                    }
                }
            }
        } else {
            for (i = maxFloor; i >= minFloor; i--) {
                if (i != 0) {
                    if (getStop(i)) {
                        break;
                    }
                }
            }
        }
        if (i > maxFloor || i < minFloor) {
            return -999;
        }
        return i;
    }
    ```
    - 这段用于寻找下一个停靠楼层的代码希望在上升时由低到高遍历,下降时由高到低遍历。
    - 写的很丑,结构层次化差,分支条件多。很容易出错,也很难发现错误的地方。
    - 异常时草率地返回了一个`-999`不太负责,应该直接抛出异常`throw new IllegalStateException("No Stop");`以后可以更好地发现错误。
- 其余的数据在正常范围之内
  • 依赖关系分析

    Class Cyclic Dcy Dcy* Dpt Dpt*
    Client 3 1 3 1 3
    List 3 2 3 3 3
    Main 3 2 3 2 3
    Worker 3 2 3 1 3

    从表中得到,各个类之间耦合关系在正常范围内。

测试思路

  • 本次使用了随机自动化测试,步骤如下:
    • 生成随机数据
    • 实现定时输入(评测机的输入)
    • 验证输出的正确性和与输入的对应
    • 将上述操作封装入批处理进行循环
  1. 利用 python 的 random 库生成若干条随机数据
# make.py
t = round(random.uniform(0,100),1) #生成[0,100)间的随机小数并保留一位小数
ID = random.randint(0,99999999) 
fromfloor= random.randint(-3,20) 
tofloor = random.randint(-3,20)
println("[%.1f]%d-FROM-%d-TO-%d" %(t,ID,fromfloor,tofloor))
  1. 利用黑箱投放数据
  • 需要将项目打包成.jar文件(有dl同学写出了builder脚本:直接通过.zip直接生成.jar文件,形成了如下文件树)
    ├──src
    │  ├─ Archer.jar
    │  ├─ Berserker.jar
    │  ├─ Caster.jar
    |  ├─ ....
    |  └─ Alterego.jar
    ├──lib
    │  ├─ elevator-input-hw3-1.4-jar-with-dependencies.jar
    │  └─ timable-output-1.1-raw-jar-with-dependencies.jar
    └──pat.py
    
  • 使用到hdl的黑箱投放已经生成好的数据
  1. 验证:
    对一些基本条件进行检验:
  • ①所有乘客都在fromfloor上电梯,并最终到达tofloor,中途可能有转梯
  • ②in,out需要在开关门之间
  • ③电梯连续地到达各楼层,相邻两层间时间不少于电梯运行时间
  1. shell 脚本运行批处理文件
python make.py > make.txt 
java -jar my.jar < make.txt > result.txt 
cat python judge.py < result.txt

bug修复

最初使用的方法是当且仅当电梯为空输入请求时List类将请求放入电梯中,但这样很可能出现异步的情况:

[0.0]1-FROM-1-TO-15
[0.4]2-FROM-2-TO-14

当电梯在1楼接到人以后,目的层按15层,可是由于第二个请求是异步的,没法正好在电梯到达2楼前收到消息并挺下来。电梯很有可能走过了第二层才接到第二个请求。使得2号乘客在14楼下却没有上电梯。

我尝试着让List优先级变高,Worker使用yield方法,但都没有解决线程不安全问题。最后只能让Worker没到达一层就访问一次List看看有没有可以携带的请求。

这样使得线程之间关系明了,不会出错了,但是明显因为每层都要访问,使得效率降低了,由于处理速度很快,基本上每隔3层才多出10ms,这样牺牲了小部分性能提升了线程安全性,简化了逻辑,是很值得的。

三、第三次作业

1.需求分析

在第二次作业的基础上,加入了多个电梯,并设置最大允许人数和允许停靠楼层。

  • 电梯数量:3部,分别编号为ABC
  • 电梯可运行楼层:-3-1,1-20
  • 电梯可停靠楼层:
    • A: -3, -2, -1, 1, 15-20
    • B: -2, -1, 1, 2, 4-15
    • C: 1, 3, 5, 7, 9, 11, 13, 15
  • 电梯上升或下降一层的时间:
    • A: 0.4s
    • B: 0.5s
    • C: 0.6s
  • 电梯最大载客量(轿厢容量)
    • A:6名乘客
    • B:8名乘客
    • C:7名乘客

2.实现方案

建立类图

本次多线程较为复杂,按照老师对于Worker Thread的提示,我详细看过了《图解java设计模式》的那一章,自己也画出了一个大致的类图:
OO_Unit2_多线程电梯
如图,细箭头表示包含,粗箭头表示继承。在第二次作业的基础上,运用了OCP原则,没有直接修改Worker类,而是使其继承了一个子类NewWorker,在新的类中重写父类方法,以保证第三次作业所做的能同时兼容第二次。

对于PersonRequest也继承了子类Request,并让它也成为了一个线程,并拥有了指向List和Client的指针。

图中所有的线程包括:Worker, NewWorker, Client, Request

实现思路

Client主动向List中输入请求put,Worker向List中请求拿出请求get,对于特殊请求Request(不能由一个电梯完成的)分两次向电梯发送请求,三者需要互斥。

其中,Request类比较特殊

  • 在Client中判断此请求是否被接受,不被接受则开启一个新的Request线程并设置一个原子信号量sem记录线程数量,否则Request就是一个简单的PersonRequest
PersonRequest a = elevatorInput.nextPersonRequest();
    if (a == null) {
        break;
    }
    Request request = new Request(a.getFromFloor(),
        a.getToFloor(), a.getPersonId(), list, this);
    if (list.accept(request)) {
        list.put(request);
    } else {
        sem.getAndIncrement();
        new Thread(request).run();
    }
  • 在Request类中则查找中间转梯层,并将其切分为两个Request,按次序投放:在投放完第一个后,需要调用waitFor(request1),直到List和电梯中都不存在request1再投放第二个。
Request request1 = new Request(getFromFloor(), i,
        getPersonId(), list, client);
Request request2 = new Request(i, getToFloor(),
        getPersonId(), list, client);
list.put(request1);
list.waitFor(request1);
list.put(request2);
client.decrease();
client.finishAndNotify();
  • 这样将Request单独开一个线程,大大简化了容器类List的设计,不需要使其成为一个线程。并且线程之间的交互关系简单明了,即使有新的需求:需要换成多次,也能轻松完成。缺点是:当这样换乘的请求过多,使得线程也很多,cpu调度的效率会下降。

3.测试及修复

结构分析

  • 复杂度分析(超标及整体)
Method ev(G) iv(G) v(G)
List.hasRequest(Request) 5 3 5
Request.run() 6 19 19
Worker.moveOne(int,boolean) 4 1 4
Worker.next() 9 6 10
Class OCavg WMC
Client 2 8
List 3.08 40
Main 1 1
NewWorker 2.55 28
Request 5 20
Worker 2.24 56
Package v(G)avg v(G)tot
xxx 3 174

可以看到,Request.run()方法三项均超标。这一个run方法具有很强的面向过程特性:
OO_Unit2_多线程电梯
整个run()方法写了60行,可以说对各种情况都进行了讨论并分支。违背了SOLID中的SRP单一职责原则,更好的方法是对每种特例写一个函数,并逐层调用,使得代码结构清晰,而且容易修正。这次的2个bug都是出现在Request.run()方法中的,由此可见,一个清晰的代码结构甚至能减少错误率。

  • 依赖关系分析
Class Cyclic Dcy Dcy* Dpt Dpt*
Client 5 2 6 2 5
List 5 4 6 5 5
Main 5 2 6 4 5
NewWorker 5 5 6 1 5
Request 5 4 6 4 5
Worker 5 3 6 3 5

从表中得到,各个类之间耦合关系依然在正常范围内,说明这次结构设计上问题不大。

bug修复

  1. 第一个bug出现在Request.run()中:本来希望min和max依次代表请求最低层上一层、最高层下一层:
int min = Math.min(getFromFloor(), getToFloor()) + 1;
int max = Math.max(getFromFloor(), getToFloor()) - 1;

却忽略了最低层正好是-1,最高层正好是1情形,按上面的算法都到了第0层,出现了数组转换越界。只好新增了Worker.moveOne(int floor,boolean up)方法,up为true是上移一层,否则下移一层。

int min = Math.min(getFromFloor(), getToFloor());
int max = Math.max(getFromFloor(), getToFloor());
//md,忽略了min和max可能因为from 与to正好是1,-1而出现0!!!!!
min = Worker.moveOne(min, true);
max = Worker.moveOne(max, false);
  1. 第二个bug也出现在Request.run()中,对于奇怪的请求:3->4,3->2,原本在两层之间找换乘失效了,而我正好没有考虑到这种情况:
//临界情况
if (min > max) {
    if (getFromFloor() == 3) {
        if (getToFloor() == 4) {
            dispatch(5); //3->4拆解成3->5->4
        } else if (getToFloor() == 2) {
            dispatch(1); //3->4拆解成3->1->2
        }
    }
}