OO_Unit2_多线程电梯

CSDN博客链接

一、第一次作业

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组成；方法②更好，避免了继承带来的麻烦问题，并可以将队列进行封装：少用继承，多用组合）
  
• 其中：细实箭头代表包含关系，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();

• 如图，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();//在已有的队列中寻求其他请求，并放入Workerreturn true; }

3.测试及修复

结构分析

• 复杂度分析（超标及整体）

Methodev(G)iv(G)v(G)

Worker.next()	9	6	10

ClassOCavgWMC

Client	2	4
List	3	21
Main	1	1
Worker	2.67	48

Packagev(G)avgv(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");`以后可以更好地发现错误。 - 其余的数据在正常范围之内

• 依赖关系分析

  ClassCyclicDcyDcy*DptDpt*

  Client	3	1	3	1	3
  List	3	2	3	3	3
  Main	3	2	3	2	3
  Worker	3	2	3	1	3

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

测试思路

• 本次使用了随机自动化测试，步骤如下：
  • 生成随机数据
  • 实现定时输入（评测机的输入）
  • 验证输出的正确性和与输入的对应
  • 将上述操作封装入批处理进行循环

利用 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))

利用黑箱投放数据

• 需要将项目打包成.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的黑箱投放已经生成好的数据

验证：
对一些基本条件进行检验：

• ①所有乘客都在fromfloor上电梯，并最终到达tofloor，中途可能有转梯
• ②in,out需要在开关门之间
• ③电梯连续地到达各楼层，相邻两层间时间不少于电梯运行时间

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部，分别编号为A，B，C
• 电梯可运行楼层：-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设计模式》的那一章，自己也画出了一个大致的类图：

如图，细箭头表示包含，粗箭头表示继承。在第二次作业的基础上，运用了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.测试及修复

  结构分析

• 复杂度分析（超标及整体）

Methodev(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

ClassOCavgWMC

Client	2	8
List	3.08	40
Main	1	1
NewWorker	2.55	28
Request	5	20
Worker	2.24	56

Packagev(G)avgv(G)tot

xxx	3	174

可以看到，Request.run()方法三项均超标。这一个run方法具有很强的面向过程特性：

整个run()方法写了60行，可以说对各种情况都进行了讨论并分支。违背了SOLID中的SRP单一职责原则，更好的方法是对每种特例写一个函数，并逐层调用，使得代码结构清晰，而且容易修正。这次的2个bug都是出现在Request.run()方法中的，由此可见，一个清晰的代码结构甚至能减少错误率。

• 依赖关系分析

ClassCyclicDcyDcy*DptDpt*

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修复

第一个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);

第二个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}} }

转载于:https://www.cnblogs.com/RyanSun17373259/p/10762123.html

总结

以上是生活随笔为你收集整理的OO_Unit2_多线程电梯的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。