OO_Unit2_多线程电梯
一、第一次作业
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();
- 如图，
ClientWorker各有一个指向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 从表中得到，各个类之间耦合关系在正常范围内。
测试思路
- 本次使用了随机自动化测试，步骤如下：
- 生成随机数据
- 实现定时输入（评测机的输入）
- 验证输出的正确性和与输入的对应
- 将上述操作封装入批处理进行循环
- 利用 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.测试及修复
结构分析
- 复杂度分析（超标及整体）
| 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方法具有很强的面向过程特性：
整个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修复
- 第一个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
}
}
}