OO第二单元总结——电梯调度问题
一、设计策略。
在三次作业中,多线程程序的实现分以下几个步骤:
1. 主线程Main类的创建多个线程。
2. 共享对象的synchronized锁保证线程之间的互斥访问。
3. 采用notifyAll和wait的方式实现同步控制,第三次作业中少部分采用sleep(10)的轮询机制(本希望能去掉,但时间不足)。
4. 结束指令NULL的异步传递(传递到共享对象中,由各个线程读取)结束线程。
第一次作业的结构比较好,耦合度低,使得第二次作业轻松摸鱼,修改很少,但没有为下一次作业修改架构。后果是第三次作业的时间不足,第二次作业的架构又不适应第三次作业的要求,导致强测炸点。
二、基于度量和SOLID原则分析程序结构
SOLID简介
S.O.L.I.D是面向对象设计和编程(OOD&OOP)中几个重要编码原则(Programming Priciple)的首字母缩写。
SRP | The Single Responsibility Principle | 单一责任原则 |
OCP | The Open Closed Principle | 开放封闭原则 |
LSP | The Liskov Substitution Principle | 里氏替换原则 |
DIP | The Dependency Inversion Principle | 依赖倒置原则 |
ISP | The Interface Segregation Principle | 接口分离原则 |
作业一、单人电梯
1. 统计信息图
2. 复杂度分析
基本复杂度(Essential Complexity (ev(G))、模块设计复杂度(Module Design Complexity (iv(G)))、Cyclomatic Complexity (v(G))圈复杂度
OCavg为平均循环复杂度;WMC为总循环复杂度
3. 结构信息图
可见,由于逻辑简单,本次作业的复杂度和耦合度都不高。
由UML类图可以看出,主线程是Main类(启动子线程后立即结束),创建了两个子线程Inputhandler和Elevator,两者的共享对象是Schedule类。
4. SOLID分析
单一责任原则:基本实现
开放封闭原则:基本实现
里氏替换原则:基本实现
依赖倒置原则:基本实现
接口分离原则:基本实现
作业二、单部捎带电梯
1. 统计信息图
2. 复杂度分析
基本复杂度(Essential Complexity (ev(G))、模块设计复杂度(Module Design Complexity (iv(G)))、Cyclomatic Complexity (v(G))圈复杂度。
OCavg为平均循环复杂度;WMC为总循环复杂度
3. 结构信息图
可见,由于逻辑简单,本次作业的复杂度和耦合度都不高。
由UML类图可以看出,主线程是Main类(启动子线程后立即结束),创建了两个子线程Inputhandler和Elevator,两者的共享对象是Schedule类。
本次作业结构继承了上一次作业,仅仅在Elevator和Scheduler类中加入了3个方法,说明上一次作业的结构设计合理,可以适应本次作业的修改。但同时这次作业没有为下一次作业而修改结构,轻松摸鱼,为第三次作业的悲剧埋下了伏笔。
4. SOLID分析
单一责任原则:Elevator中不应该出现sort方法,这是属于Schedule的工作,应该放到Schedule中。
Schedule中的search方法过于臃肿,应该拆分。
开放封闭原则:可扩展性低,当多个Elevator共享一个Schedule时,会出现很多问题。
里氏替换原则:基本实现
依赖倒置原则:抽象的不是很好,在sort中考虑了过于细节的问题(比如乘客是否在电梯内,方向是否一致)。
接口分离原则:基本实现
作业三、多部捎带电梯
1. 统计信息图
2. 复杂度分析
基本复杂度(Essential Complexity (ev(G))、模块设计复杂度(Module Design Complexity (iv(G)))、Cyclomatic Complexity (v(G))圈复杂度
OCavg为平均循环复杂度;WMC为总循环复杂度
3. 结构信息图
可以发现,本次作业不论是复杂度还是耦合度都很高,这给测试和改BUG带来了很大的困难。
由UML类图可以看出,主线程是Main类(启动子线程后立即结束),创建了四个子线程InputHandler和三个Elevator,Inputhandler和Elevator之间的共享对象是Schedule类;Elevator和Schedule之间的共享对象是ElevSchedule,Elevator间共享对象是Output和Empty。
4. SOLID分析
单一责任原则:Elevator中不应该出现sort方法,这是属于Schedule的工作,应该放到Schedule中。
Schedule中的search方法过于臃肿,应该拆分。
为了判断NULL信号,用了Empty类以及其中的方法、ElevSchedule中的isEmpty方法和Num方法。
比如下图的代码(截取自第三次作业)就是一个很好的反面材料(if语句嵌套过多,与多个类有联系(耦合度高),存在轮询):
1 if (order.get(0).get(1) == 0) {
2 if (order.size() == 1) {
3 // System.out.println(name + order);
4 order.remove(0);
5 boolean end = false;
6 empty.setEmpty(name);
7 while (true) {
8 if (empty.isEmpty() & (elevScheduler.Num() == 0)) {
9 // System.out.println(name + ": end==========");
10 if (!closeDoor) {
11 close();
12 }
13 end = true;
14 break;
15 }
16 if (elevScheduler.Num() != 0) {
17 ArrayList<ArrayList<Integer>> integer
18 = elevScheduler.pop();
19 if (integer.get(0).get(1) == 0) {
20 sleep(100);
21 continue;
22 }
23 order.addAll(integer);
24 empty.setFull(name);
25 // System.out.println("addBack" + order);
26 break;
27 }
28 // System.out.println(name + " wait...");
29 sleep(100);
30 }
31 if (end) {
32 break;
33 }
34 } else {
35 order.remove(0);
36 }
37 }
开放封闭原则:可扩展性低,如果再加一个电梯,几乎不能运行,硬编码过多。
如下图:
synchronized void add(ArrayList<Integer> list) {
// System.out.print("list");
// System.out.println(list);
if ((list.get(1) == 0)) {
list.add(0);
elevSchedulerA.add(list);
elevSchedulerB.add(list);
elevSchedulerC.add(list);
inputEnd = true;
} else if (floC.contains(list.get(1)) && floC.contains(list.get(2))) {
elevSchedulerC.add(list);
} else if (floA.contains(list.get(1)) && floA.contains(list.get(2))) {
elevSchedulerA.add(list);
} else if (floB.contains(list.get(1)) && floB.contains(list.get(2))) {
if (floC.contains(list.get(1)) && floC.contains(list.get(2)) &&
(!elevSchedulerC.isFull() || elevSchedulerC.Num() < 5)
&& (elevSchedulerB.isFull() || elevSchedulerB.Num() > 5)) {
elevSchedulerC.add(list);
} else {
elevSchedulerB.add(list);
}
} else {
list.add(1);
if (floA.contains(list.get(1))) {
if (floB.contains(list.get(2))) {
elevSchedulerA.add(list);
} else if (floC.contains(list.get(2))) {
elevSchedulerA.add(list);
}
} else if (floB.contains(list.get(1))) {
if (floA.contains(list.get(2))) {
elevSchedulerB.add(list);
} else if (floC.contains(list.get(2))) {
elevSchedulerB.add(list);
}
} else if (floC.contains(list.get(1))) {
if (floA.contains(list.get(2))) {
elevSchedulerC.add(list);
} else if (floB.contains(list.get(2))) {
elevSchedulerC.add(list);
}
}
}
}
里氏替换原则:基本实现
依赖倒置原则:抽象的不好,高层模块Schedule为了满足底层模块Elevator的需求,将高层模块的逻辑修改,加入了addBack方法,将指令长度从4扩展到5。
接口分离原则:基本实现
三、自己程序BUG分析
前两次作业未发现BUG,第三次作业中出现了一个BUG(中了三个强侧点),具体分析如下:
当三个elevScheduler中的队列都为空,且A、B、C电梯为空时,且最后一个请求是拆分请求(一部电梯不能到达),会向最后一部运行电梯的elevScheduler发送全零信号,导致给电梯线程在没有输入NULL时提前结束。出现TLE或者WA(因某电梯线程结束乘客没有送到指定位置)
从程序上来说,是由于读入NULL的设计失误导致:
我为了保证遇到NULL且需要换乘的乘客在第一个电梯里时,换乘的第二个电梯不会停止,任意电梯停止前,会查看其他电梯的情况,若有正在运行的电梯,则wait并删掉NULL信号(全零信号)。当该乘客换乘时,再向Scheduler中模拟写入一个NULL信号(全零信号)。那么,当真正的NULL信号没有出现时,模拟写入一个NULL信号会导致电梯线程中止(没有判断InputHandler线程的运行情况)。
BUG出现的原因:
测评机出世后,爱不释手,终于在跑了400+组后出现一个BUG,于是开开心心的改完就提交了,却忘了检验新的逻辑正确性,恰巧我们的评测机测不出新的BUG,于是BUG就顺理成章地出现在了强测中。。。
获奖感言:
不可太信任评测机,有时手动生成的数据更靠谱(比如“分布式集中投放”,而不是单独一个点的集中投放指令),有了评测机就懒了。
改BUG(尤其是逻辑BUG)时,一定要时间充沛、精力旺盛时,仔细想清楚改完BUG后的逻辑,有没有新增的漏洞。改完BUG不能高兴,切实提高正确率才能偷偷乐一下。
反思:
其实加入判断InputHandler线程的运行情况只是一个临时方案,最好的解决方法是,将判断结束信号单独写一个共享对象,保证所有线程正确关闭,也可以去掉复杂的判断方法(isEmpty等)和多余的类(Empty类),减少程序复杂度和耦合度。
四、他人程序BUG分析
前两次作业的易错点不多,均没有发现BUG(其实是不知道怎么测,所以都没有提交测试用例)。第三次作业决定搞一番事情,于是和几个同学一起搭了评测机。一亮相,就WA声一片,于是回头改BUG。。。
评测机的故事:
在第二次互测中无事可做地划水后,感觉需要什么来提高效率,增加互测中的hack数。正巧,jly巨佬招人做对拍器,于是欣然起行,举手报名,开启了罪恶的一生。 However,入党发展对象答辩悄然降临在周日晚上,我只好先去准备答辩,偷空写OO & OS。显然偷空是不够的,直到周日晚上任未写出能跑的程序。周一上午终于提交了第一版,AC:WA = 1:9,心灰意冷的我顺利地在下午的OS考试中挂掉,又理直气壮的“休息“了一个晚上。到了11点,不知哪来的自信,可能是秉着磨刀不误砍柴工的真理,开始写评测机??终于,2点的时候,带着残缺的评测机入睡了。(就是太懒了,不想写) 周二中午,老天开眼,解决了大部分的BUG,通过中测,评测机(检验输出部分)也顺利运行,和几位大佬的程序合并后,测评机成功跑了起来! 有了测评机后,可以同时开着8个测试程序,一个小时干掉了我手动一天的DEBUG量,评测姬nb!
看到这里读者应该可以料想到,一个人强测炸了三个点进入C组,恰巧手里拿着评测机,会做出什么样的事情呢。
于是乎,一启动评测机,就是WA声一片,就放弃了阅读代码发现BUG的方法(其实不应该放弃,最起码看一看别人的思路),随机选取一些WA掉的测试点就提交了。最后的结果是26 / 70。大部分错误是以下几个方面:
1. 线程未停止
2. 有乘客未被接上就结束线程
3. 数组 / list越界
4. 线程停止时没有关门
本次结果可以看出,线程安全是个大问题,互斥和同步,什么时候停止都可能出现BUG。
五、心得体会
1. 框架设计很重要,第一次作业做的好使得第二次作业很轻松,但是第二次作业没有做,导致第三次作业的滑铁卢。
2. 评测机很重要,大大提高Debug效率,但是一定要结合自己的逻辑验证,防止评测机的片面性导致的BUG盲区。
3. 多线程停止时,最好建一个类或者单一变量,让它做众多停止信号和实际停止的桥梁,不要直接用一大堆信号做实际停止的标志。
4. 减少硬编码,灵活使用工厂模式、抽象工厂模式等方法。
5. 单一任务原则,不要试图在一个类或一个方法中干过多的事情。
6. 不要轻易改BUG,先想清楚逻辑上的思路,精准定位哪里出错了,怎么改最好。
希望多思考,多实践,多看大佬分享的思路,OO加油啊~
最新文章
- jquery 集合操作
- 【学习笔记】Wireshark的用法
- (转)现代C++函数式编程
- 连接池和 ";Timeout expired";异常
- MongoDB查询命令具体解释
- Webx框架:Valve详细解释
- CRC的校验原理
- Jmeter(十三)用Jmeter自带录制工具代理录制手机端应用脚本APP脚本
- VIM的字符编码设置
- Java IO(四)
- 设计模式之外观模式——Java语言描述
- 【做题】CSA49F - Card Collecting Game——思维&;dp
- 每天一点Linux系列之—vim
- python笔记15-集合
- PHP 用正则获取URL的根域名
- kepware http接口 nodejs开发
- 20145225《网络对抗》Exp7 网络欺诈技术防范
- Python入门系列教程(五)函数
- android boot.img unpack pack
- python 描述符 上下文管理协议 类装饰器 property metaclass
热门文章
- Mongodb学习总结(1)——常用NoSql数据库比较
- 转-----------------------js window.open() 操作
- MySQL 与 MongoDB的操作对比
- BA--关于江森的学习笔记
- CF914A Perfect Squares
- 带有public static void main方法的类,其中的成员变量必须是static的,否则main方法没法调用。除非是main里的局部变量。因为main方法就是static的啊。
- 腾讯云 ubuntuservermysql安装和外网訪问
- 初探swift语言的学习笔记十(block)
- TT流程随笔
- 通过meta标签改变浏览器内核做兼容