作业2-1 单部多线程傻瓜调度（FAFS）电梯的模拟
I. 基于度量的程序结构分析
1）程序结构与基本度量统计图
2）分析
这次作业基本奠定了本人三次电梯作业的基本架构，简述如下：
- Elevator类：定义了”电梯“这一对象，即拥有开关门状态（state：CLOSE or OPEN），电梯内乘客队列（passenger），当前楼层（floor：GROUND~TOP）等。
-
PassengerQueue类： 共享资源区。拥有
push()，pop()，isEmpty()方法。 -
ElevatorDispatcher类：电梯调度器。负责接受请求，安排电梯上下以及乘客上下（
upOrDown()）。 - MainClass类：负责初始化并启动ElevatorDispatcher，以及接受请求并存入PassengerQueue。
II. 多线程的协同和同步控制
我采用的是典例“生产者消费者”的逻辑。MainClass代表“生产者” 线程，负责接受请求并将请求存入PassengerQueue；ElevatorDispatcher相当于“消费者” 线程，负责从PassengerQueue中取出请求，然后运行电梯到指定位置（处理请求）；PassengerQueue是共享资源，利用wait和notify的组合，来确保对共享资源的存和取是互斥的。
// 下为临界区的代码
private volatile Queue<PersonRequest> requests = new LinkedList<>(); public synchronized void push(PersonRequest request) {
requests.offer(request);
notifyAll();
} public synchronized PersonRequest pop() {
while (requests.isEmpty()) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
PersonRequest r = requests.poll();
return r;
}
III. 程序BUG分析
- 本次程序结构较简单，大家都没有出现错误。
IV. 程序测试策略
1）白盒测试
- 大多数人（包括我）第一次接触多线程编码，但由于本次程序设计建构较简单。故虽然在编码的过程中有些阻碍，最终结果总归还是差强人意的。
- 观察发现大部分同学都是采用“生产者消费者”的典例逻辑进行编写的。
2）黑盒测试
- 定时投放指令，随机测试（由于电梯结构与逻辑都较简单，故未进行大量测试）。
V. 关于程序优化的思考
- Elevator类中有若干多余的参数，可以舍弃；
-
ElevatorDispatcher类的
run()中集成了太多方法，为了进一步的拓展，应进行拆分。
作业1-2 单部多线程可捎带调度（ALS）电梯的模拟
I. 基于度量的程序结构分析
1）程序结构与基本度量统计图
2）分析
其实这一次的电梯只是上一部电梯的扩充，对调度算法进行了改进，整体结构没有发生变化。
-
我继承下来了elevator1的代码，并对其中的ElevatorDispatcher类进行了改写；
public void run() {
while (true) {
// 读取当前电梯内的乘客队列到 passengers
ArrayList<PersonRequest> passengers = elevator.getPassengers(); /* 初始化。判断电梯内乘客的情况：
* 若电梯内无乘客且队列内读到null，电梯下班；
* 若电梯内无乘客且队列内有乘客，peek()，然后控制电梯去接乘客；
* 同时，判断电梯是否需要转向，若转向，则对标志位isUp进行取反 */
if (initialize(passengers)) {
return;
} // 遍历电梯内乘客，将需要已到达的乘客从电梯内取出，加入removes
ArrayList<PersonRequest> removes = getRemoves(passengers);
// 读取当前排队乘客队列
ArrayList<PersonRequest> requests = passengerQueue.getRequests();
// 遍历电梯内乘客，将需要顺路的乘客从乘客队列内取出，加入adds
ArrayList<PersonRequest> adds = findPassengers(requests); // 乘客上下电梯（先下后上）
onOrOff(removes, adds, requests); if (elevator.getPassengers().isEmpty() &&
(passengerQueue.isEmpty() || elevator.getTarget() == floor)) {
// 若电梯内无乘客（所有乘客都在这一层下，且无乘客顺路或上电梯），则电梯等待
elevator.setTarget(0);
} else { // 否则，电梯运行（向上一层 或 向下一层）
floor = upOrdown(floor, elevator.isUp());
}
}
} -
同时，值得注意的是，在本次电梯中，由于电梯可以从-3层到15层上下运行，电梯没有0层，所以在1层到-1层之前有一个特殊的跨越。我的处理方法如下：
if (isUp) { // 电梯上行时
floor++; // 楼层增一
if (floor == 0) {
floor++; // 如果电梯运行到0层，楼层号继续增一，到达一层
}
} else { // 电梯下行时
floor--; // 楼层减一
if (floor == 0) {
floor--; // 如果电梯运行到0层，楼层号继续减一，到达负一层
}
}
II. 多线程的协同和同步控制
- 由于本次作业，仅仅修改了电梯的调度策略，未对电梯结构进行修改，也未增添新的进程，故为引入新的线程安全风险，所以多线程的协同和同步控制的原理与上一次作业相同，不再赘述。
III. 程序BUG分析
1）自身错误
- 未出现线程安全问题与逻辑错误
2）他人错误
-
输出冗余： 两次输入间隔时间较长时，会重复输出
Arrive语句;STDIN:
[0.0]1-FROM--2-TO-11
[20.0]2-FROM-15-TO-9
STDOUT:
[ 0.8530]ARRIVE--1
[ 1.2540]ARRIVE--2
[ 1.2550]OPEN--2
[ 1.6560]IN-1--2
[ 1.6560]CLOSE--2
[ 2.0570]ARRIVE--1
......
[ 6.4690]ARRIVE-11
[ 6.4690]OPEN-11
[ 6.4700]OUT-1-11
[ 6.8700]CLOSE-11
/******* 这里第二条需求指令加入 *******/
[ 19.9120]ARRIVE-11 /** 重复输出 **/
......
[ 21.5150]ARRIVE-15
[ 21.5160]OPEN-15
[ 21.9160]IN-2-15
[ 21.9170]CLOSE-15
[ 22.3180]ARRIVE-14
......
[ 24.3220]ARRIVE-9
[ 24.3220]OPEN-9
[ 24.3230]OUT-2-9
[ 24.7240]CLOSE-9- 错因：当请求处理结束时，电梯停止在当前楼层，但这种停止是动态停止，即每次上（下）0层。
IV. 程序测试策略
1）白盒测试
- 由于本次设计架构变得较为多样化，阅读代码更多时候是作为一种辅助工具，为了使测试更加有针对性，在随机测试的基础上，可通过阅读代码和思考架构以便根据实际状况添加一些限制。
2）黑盒测试
- 由于本次作业程序输出可能较为复杂，肉眼很难判断正误，自动化评测显得必不可少。
- 自动化测试带来方便，但是也有弊端，即评测得到的错误多为同质，但由于输入输出往往较长，肉眼依旧难辨。为解决这一问题，我采取了观察+人工修改重测的方法，效率较低但是最终结果可靠。
V. 关于程序优化的思考
- 本次程序的优化主要在于电梯调度的算法
- 根据度量来看，我的
ElevatorDispatcher类的耦合度过高，需要对此进行优化 - 由于程序的继承性，所有关于优化的思考将在下一节进行陈述
作业1-3 多部多线程智能（SS）调度电梯的模拟
I. 基于度量的程序结构分析
1）程序结构与基本度量统计图
2）分析
本次作业是OO课程第二单元的重头戏。下面对本次程序进行分析。
Elevator 类：仅定义电梯的基本属性——上下行状态（
isUp），目标楼层（target），电梯内乘客队列（passengers）；ElevatorDispatcher 类：严格意义上不能称为调度器，更像是安装在电梯上的控件，每一个
Elevator与一个ElevatorDispatcher相结合形成一个可以自主地按照自己的一套规则接受乘客请求、上下行接送乘客。（这样的设计是为了较简单地继承上一次的电梯，但是使得进一步的优化变得困难。）-
MyPersonRequest 类：这个类重新定义了一种乘客请求的类型 ——
MyPersonRequest，它包含了对初始请求的储存，以及对乘客请求的分析分解的方法：public class MyPersonRequest {
private static final int A = 1;
private static final int B = 2;
private static final int C = 4;
private PersonRequest request; // 本次请求
private int worker; // 负责处理该请求的电梯编号
private int transfer; // 电梯最终目的地（仅在换乘时有意义，请求无需换乘时置为0） MyPersonRequest(PersonRequest request) {
this.request = request;
this.transfer = 0;
this.worker = 0;
DemandAnalysis();
}
/********************************************************
* DemandAnalysis() 函数作用：根据请求与电梯实际进行分解，并分配任务给不同的电梯 *
* 判断函数示例如下： *
*********************************************************/
private void DemandAnalysis() {
int from = request.getFromFloor();
int to = request.getToFloor(); switch (from) {
case -3: {
minusThree(to);
break;
}
case -2:
case -1: {
minusOne(to);
break;
}
case 1: {
one(to);
break;
}
case 2:case 4:case 6:case 8:case 10:case 12:case 14: {
evenNumber(to);
break;
}
case 3: {
three(to);
break;
}
case 5:case 7:case 9:case 11:case 13: {
oddNumber(to);
break;
}
case 15: {
fifteen(to);
break;
}
case 16:case 17: case 18:case 19:case 20: {
minusThree(to);
break;
}
default: {
throw new RuntimeException(
"MyPersonRequest has somethig wrang!");
}
}
}
private void minusThree(int to) {
worker = A;
if (to >= 2 && to <= 14) {
updateRequest(1);
}
}
/***********************
* 此处省略其他方法的细节 *
***********************/
} -
MyPersonRequest 类：这个类重新定义了一种乘客请求的类型 ——
MyPersonRequest，它包含了对初始请求的储存，以及对乘客请求的分析分解的方法：public class PassengerQueue {
private volatile ArrayList<MyPersonRequest> requests = new ArrayList<>();
private volatile int tranNum = 0; // 需要转乘而未被转乘的人数 // 检测removes（即下电梯的乘客队列）中需要被换乘的乘客，
// 并将其toFloor和fromFloor更改后，重新加入passengerQueue。
synchronized void pickUp(PersonRequest request) {...} synchronized void subTranNum() { tranNum--;}
synchronized int getTranNum() { return tranNum;} /* 下列函数并未作更改 */
synchronized void push(PersonRequest request) {...}
synchronized MyPersonRequest peek() {...}
synchronized void remove(int index) {...}
synchronized ArrayList<MyPersonRequest> getRequests() {...}
synchronized boolean isEmpty() {...} /*******************************************
* 下面这一函数为互测后打的补丁，并非一开始的设想 *
*******************************************/
synchronized void insertBefore() {
int size = requests.size();
MyPersonRequest via = requests.get(size - 1);
MyPersonRequest o = requests.get(0);
requests.set(0, via);
requests.set(size - 1, o);
}
} -
下面是ElevatorDispatcher类的run()方法，展示了程序的基本逻辑。
public void run() {
while (true) {
ArrayList<MyPersonRequest> passengers = elevator.getPassengers();
int r = initialize(passengers);
if (r == -1) {
return;
} else if (r == 1) {
if (parks[floor + 3] == 1) {
ArrayList<MyPersonRequest> removes = getRemoves(passengers);
pickUpPassenger(removes);
ArrayList<MyPersonRequest>
requests = passengerQueue.getRequests();
ArrayList<MyPersonRequest>
adds = findPassengers(requests);
onOrOff(removes, adds, requests);
}
if (elevator.getPassengers().isEmpty() &&
(passengerQueue.isEmpty() ||
elevator.getTarget() == floor)) {
elevator.setTarget(0);
} else {
floor = upOrdown(floor, elevator.isUp());
}
} else {
try {
Thread.sleep(400);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
II. 多线程的协同和同步控制
- 本次多线程的协同和同步控制仍是继承了之前的管程的思想，利用PassengerQueue的来保证各电梯的取用之前是互斥的，同时请求的放入与取用也是互斥的。
- 各电梯之间不存在直接通信，只通过PassengerQueue中定义的tranNum变量来间接完成需求的通信。
- 具体的实现与第一次作业不尽相同，故不赘述。
III. 程序BUG分析
1）自身错误
本次测试，强测点有8个未通过，互测点有4个未通过，数目令人触目惊心，节选如下：
| STDIN | STDOUT |
|---|---|
| [1.0]21-FROM-3-TO-1 [1.0]22-FROM-3-TO-2 [1.0]23-FROM-3-TO--3 [1.0]24-FROM-3-TO-4 [1.0]25-FROM-3-TO-5 [1.0]26-FROM-3-TO-6 [1.0]27-FROM-3-TO-7 [1.0]28-FROM-3-TO-8 [1.0]10-FROM-3-TO--2 [1.0]11-FROM-3-TO--1 |
Passenger 22 has not arrived at his/her target floor yet |
| [0.0]1016036187-FROM-10-TO-6 [0.1]1289556284-FROM-14-TO-16 [0.1]587468376-FROM--1-TO-3 [0.1]1477225549-FROM-20-TO-2 [0.3]804572881-FROM-9-TO-10 [0.4]2064667476-FROM-18-TO-10 [0.5]1489802222-FROM-17-TO-11 [0.6]615855192-FROM-17-TO-13 [0.6]1994863070-FROM-5-TO-7 [0.8]1793333371-FROM-7-TO-2 [2.6]353255777-FROM-11-TO--2 [2.7]403262883-FROM-15-TO-14 [39.3]492338565-FROM--3-TO-6 |
判定信息：REAL_TIME_LIMIT_EXCEED实际 CPU 时间：1.256 秒 最大允许的 CPU 时间：10 秒 实际运行时间：210.016 秒 最大允许的运行时间：210 秒 实际运行内存：79.58203125 MB 最大允许的运行内存：768 MB |
-
分析：
现象分析：这两个错误看似是两个不同的错误（
996.ICU与提前下班），但其实问题出在一个地方——null请求在队列中的位置不定，导致电梯不能正确停止。错因分析：
/****************************************************************************
* 表面错因：在ElevatorDispatcher类的run()函数的第一步——initialize()方法中，
* 读取到null时，乘客队列不为空。
* 根本错因：由于线程安全问题，在pickUp换乘请求时，调用了size()等不安全方法，
* 导致请求的插入未插入到null的前面：
* 理想情况 —— passenger1-passenger2-passenger3-null
* 实际情况 —— passenger1-null-passenger2-passenger3
* 修改措施：如下。
****************************************************************************/
private synchronized int initialize(ArrayList<MyPersonRequest> passengers) {
if (passengers.isEmpty() && elevator.getTarget() == 0) {
MyPersonRequest pr = passengerQueue.peek();
if (pr == null) {
if (passengerQueue.getTranNum() == 0) {
if (passengerQueue.getRequests().size() > 1) {
/*************************************
* 当读取到null，但乘客队列中仍有非空请求 *
* 将位于null之后的请求置前。 *
************************************/
passengerQueue.insertBefore();
return 0;
} else {
return -1;
}
} else {
return 0;
}
} else if (((pr.getWorker() & flag) == 0)) {
return 0;
} else {
if (floor == pr.getFromFloor()) {
elevator.setUp(pr.getFromFloor() < pr.getToFloor());
} else {
elevator.setUp(floor < pr.getFromFloor());
}
if (floor == pr.getToFloor()) {
elevator.setTarget(pr.getFromFloor());
} else {
elevator.setTarget(pr.getToFloor());
}
}
} else {
if ((floor == top) || (floor == bottom)) {
elevator.setUp(!elevator.isUp());
}
TimableOutput.println("ARRIVE-" + floor + "-" + name);
}
return 1;
}
2）他人错误
Elevator C cannot open at floor -2 because this floor is not reachablePassenger 22 has not arrived at his/her target floor yetException in thread "Thread-61" java.lang.ArrayIndexOutOfBoundsException: -1
IV. 程序测试策略
- 本次程序测试的输出无法肉眼判断，基本只能用评测程序进行数据比照；
- 周围优秀的同学们应用各种工具编写了对拍器与评测机，在评测时应用这些可以大大节省掉重复的机械试错带来的时间消耗。
V. 关于程序优化的思考
1）结构优化
- 从度量图看出，程序耦合性较大，如果进行结构优化，可能只有重构了。
2）算法优化
- 由于没有独立的调度器，我的电梯只是“低级智商”——只能按照一定的规则进行读取、接送，而不能综合判断采用怎样的调度可以使时间最短。
- 如果进行优化的话，我选择进行“改良”的方法：
- 首先，在电梯需求分解阶段，实现更优分析，能分配给A就不分配给B、C；
- 其次，无请求时，电梯向中间层靠拢；
- 最后，在电梯接请求时，设置优先级，时间短者优先（这就要求进程间通信）
- 以上只是我的一些想法，实现层次上还有一些问题。
VI. SOLID原则分析
SRP 单一责任原则 未满足，MyPersonRequest类既存储，又分析 OCP 开放封闭原则 未满足，请求的分析被写死了，扩展只能重写方法 LSP 里氏替换原则 无父子继承类 DIP 依赖倒置原则 基本满足 ISP 接口分离原则 基本满足