OO_U2 - HW7简要总结

前言

讨论区已有一众仙人分享了自己的实现，但我认为我有在降低修改复杂度上更进一步的办法。

考虑到本次作业为本单元的最后一次作业，我的修改方法更注重于降低修改的复杂度，可能存在部分性能的牺牲。 在各位进行参考时，请注意这一点。

本人实现的亮点在于：UPDATE请求的处理，与双轿厢目标楼层的规避，全部利用线程交互实现。

支持UPDATE请求

特殊请求由谁分给电梯？

针对上一单元的SCHE请求与本单元的UPDATE请求，我都选择交由Dispatcher实例进行处理。

原因无他，为了减少进程交互的复杂性。 我的电梯运行线程Scheduler与电梯信息类Elevator是分离的，我希望Elevator只有Dispatcher与Scheduler两者在竞争。

这两类特殊请求都将直接加入请求池。那我们怎么保证Dispatcher优先处理这两种特殊请求呢？

答案是，将请求池改为用优先队列实现。这是因为，优先队列的比较条件（提供了Comparator接口）可以自行实现，这为我们当前情况的需求提供了极大的便利。

我们需要保证：

• SCHE/UPDATE请求在优先队列的首位
• 剩下的普通请求在后面。

示例如下：

import java.util.Comparator;  
  
public class RequestComparator implements Comparator<SubRequest> {  
    @Override  
    public int compare(SubRequest o1, SubRequest o2) {  
        int o1Index = calcIndex(o1);  
        int o2Index = calcIndex(o2);  
        return o1Index - o2Index;  
    }  
  
    private int calcIndex(SubRequest subRequest) {  
        if (subRequest.isSche()) { return 0; }  
        else if (subRequest.isUpdate()) { return 0; }  
        else {  
            // 按你自己的方法，处理普通请求！
        }  
    }  
}

在Dispatcher从头遍历优先队列时，我们此时即可保证特殊请求被优先处理。

UPDATE请求的处理

现在，我们的UPDATE请求放在了Dispatcher处理；此时，聪明的你不难发现一些问题：

• 在UPDATE请求处理完成前，Dispatcher是不是会被阻塞，不能分配其他请求？
• UPDATE显然需要一个类似总控的东西，来控制有关的交互；这个总控难道就是Dispatcher线程本身？

这样肯定不对。因此，我们在Dispatcher内引入一个子进程，作为UPDATE请求处理的“总控”。

这个子线程怎么创建呢？使用Lambda表达式，可以快速创建新线程：

Thread th = new Thread(() -> {  
    // Do something!
});  
th.start();

这样，Dispatcher线程就可在处理升级请求的过程中，继续分配其他可分配的请求，而不会发生阻塞。

如果你不放心，还可以用th.join()，在Dispatcher线程的某处，强制处理UPDATE请求的子线程完成后，再继续执行。

总控与两台待升级的电梯的整体交互逻辑如下：

• 告知两台电梯需要升级，等待两电梯就绪
• Scheduler读取Elevator中信息，得知电梯需要升级，进行疏散乘客等“预处理”操作
• 处理完成后，通知总控该电梯已就绪，等待总控对其进行升级
• 总控在两台电梯均就绪后，输出UPDATE-BEGIN，随后修改电梯的运行属性，完成升级

具体实现上，我的电梯信息类Elevator采用了ReentrantLock实现锁管理，上文中的两个等待，我们通过创建两个Elevator锁的Condition实现。

电梯如何指示自己已就绪？我采取给电梯增加一个UPDATE运行状态；在电梯完成了“预处理”后，电梯就将进入这一运行状态，并使用Condition.signal()唤醒总控。

下述伪代码仅作示意之用。更进一步的细节，需要各位根据自己的架构实现。

// Elevator
ReentrantLock lock;
Condition schedulerUpdateCond = lock.newCondition()
Condition dispatcherUpdateCond = lock.newCondition()

setUpdateStatus() {
		this.status = new Status("UPDATE");
		this.dispatcherUpdateCond.signal();
	}

updateA() { // updateB()同理
	// 修改属性，并将电梯运行状态设为IDLE
	this.schedulerUpdateCond.signal()
}

// Scheduler
elevator.lock.lock();
...
if (elevator.shouldUpdate()) {
	evacuatePassengers();
	elevator.setUpdateStatus;
	elevator.schedulerUpdateCond.await();
	elevator.respondUpdate; // 解除指示电梯需要升级的flag
	// await()结束后，电梯已被更新为新的状态，按照原有的运行逻辑运行即可！
}

// Dispatcher
Thread th = new Thread(() -> {  
    Elevator elevA, elevB;

	// 由两层await()，实现两电梯均就绪后再继续
    elevA.lock.lock();
    if(elevA.getStatus() != "UPDATE") {
	    elevA.dispatcherUpdateCond.await();
    }
	
	elevB.lock.lock();
    if(elevB.getStatus() != "UPDATE") {
	    elevB.dispatcherUpdateCond.await();
    }

	// UPDATE-BEGIN
		//重新分配被取消RECEIVE的请求
		elevA.updateA();
		elevB.updateB();
	// UPDATE-END

	// 放elevA/B的锁
});  
th.start();

“三角死锁关系？”

看到上面的实现后，聪明的你不难发现，这一实现中，如果调度策略是影子电梯，总控、Scheduler、Dispatcher三者都可能争夺Elevator的锁，很容易出现死锁，不是吗？

事实上，只要锁管理得够好，这个问题仍然是可以避免的。下面，我将从这三个竞争者在处理UPDATE请求的情况下，分析如何避免“三角死锁”。

• Dispatcher:（事实上，关键的只有这一处）
  在进行普通请求分配时，先判断当前电梯的是否仍在响应UPDATE请求（这一判断不获取电梯的锁），再获取锁
• Scheduler/总控：await()在开始等待前会自动放锁，等待结束后会自动重新获得锁；仔细观看上面的实现，你会发现，冲突此时并不存在！

楼层冲突规避

基本分析

很遗憾，我们不能通过不到“目标楼层”的方法，规避楼层冲突的问题，否则全部都被改造成双轿厢，且目标楼层均在同一层时，会导致跨越目标楼层的请求全部无法完成。

产生冲突的情况，我们大致可以分为三类：

• 相向而行：两电梯同时将要到达目标楼层
• 同向而行：一个电梯尚未完全离开目标楼层，而另一电梯即将到达
• 一动一静：一个电梯闲置于目标楼层，或正在目标楼层下客，而另一电梯即将到达

在我的实现中，与电梯移动有关的逻辑是这样，相信各位的实现与其大同小异：

// Scheduler 
while (true) {
	elevator.lock.lock;
	try {
		if (/*一般情况*/) {
			normSchedule();
		}
	} finally {
		// 以防中途开锁
		if(elevator.lock.isHeldByCurrentThread()) { elevator.lock.unlock(); }
	}
}

normSchedule() {
	if (elevator.status == RUNNING)
		runningSchedule;
}

runningSchedule() {
	elevator.lock.unlock();
	// 唤醒Dispatcher；开锁是为了允许Dispatcher此时为其分配可加入的请求
	sleep(speed);
	elevator.lock.lock();
	// 更改楼层
	// 输出ARRIVE
	// 判断下一步状态：是下客的WAITING，还是继续RUNNING？
}

为了防止不必要的判断，这一判断只应在当前电梯即将进入目标楼层时进行。

在判断之前，我们自然要获取对方电梯的锁，以免对方电梯的状态在判断时改变。

观察我们上面实现的锁管理情况，我们不难发现：

• 为了避免死锁，我们尽量确保一个线程一次只拿一把锁；
• runningSchedule()中恰好有一个开锁的窗口，为一次只拿一把锁提供了可能
• 对方电梯正前往目标楼层时，由于我们上面的锁机制，读取到的对方当前楼层，一定是目标楼层的前一层
• 在对方电梯的当前楼层为目标楼层时，读出的状态不可能为RUNNING，只可能为闲置的IDLE，或正在下客的WAITING

因此，上述三种冲突情况，我们只需要对“相向而行”这一情况特殊考虑；其余情况，都可以通过判断对方当前位置是否为目标楼层判断。

“相向而行”特殊在哪呢？特殊在无法直接确定需要等待的电梯。其他两种情况中，我们可以确定等待的是当前不在目标楼层的电梯，这一情况不行。

对此，我规定：下方的电梯，规避上方的电梯。

为了减少复杂度，我并没有考虑轿厢中乘客的问题，性能可能因此下降；如各位希望争取这一部分性能，可以以这一条件为最低级条件，将轿厢内请求加入判断条件中。

具体实现

自然，为了避免死锁，我们的判断放在在runningSchedule()那一开锁的窗口内。

下文中以cooper称呼对方电梯。（coop-er，能想出的最简洁称号就这个了，笑）

为双轿厢电梯单独写一套运行逻辑自然不大明治。我们将这一判断逻辑融入原有的运行逻辑中，判断只在电梯已被改造为双轿厢（对方电梯cooper !=null）时进行。

runningSchedule() {
	elevator.lock.unlock();
	// 唤醒Dispatcher；开锁是为了允许Dispatcher此时为其分配可加入的请求
	
	if (elevator.willEnterTargetFloor && cooper != null) {
		cooper.lock.lock();// 获取对方的锁
		judge(); // 判断
		// 放锁；这样放锁当然有目的，详见下文
		if(cooper.lock.isHeldByCurrentThread()) {cooper.lock.unlock(); } 
	}
	sleep(speed);
	elevator.lock.lock();

电梯避让的等待/唤醒，使用挂在电梯信息类Elevator的锁上的Condition实现，命名为conflictCond。

整体交互如下：

• 在判断出我方需要等待后，我方执行conflictCond.await()，同时通知对方需要规避
• 通知对方规避时，唤醒对方的Scheduler，以处理对方正处在IDLE，Scheduler正休眠的问题
• 每当对方远离目标楼层时，就让对方执行我方方法conflictCond.signalAll()，唤醒等待冲突解除的我方。

随后，我们就可得出如下判断逻辑：

judge() {
	if (elevator.isElevB()) { // 是在下方的B电梯  
	    switch (cooper.getStatus().getStatusType()) {  
	        case RUNNING:  
		        // 相向而行
	            if (cooper.getFloorBeforeTargetFloor() == cooper.getCurrentFloor() 
	                && cooper.towardsTargetFloor()) {  
	                cooper.setAvoid();  // 通知对方规避
	                cooper.lock.unlock();  // 避免同时获取两把锁
	                elevator.lock.lock(); // 没锁就await()，会发生什么？ 
	                elevator.conflictCond.await();  
	                elevator.lock.unlock();  
	            }  
	            break;  
	        default: break;  
	    }  
	}  
	// 其他情况
	if (cooper.getCurrentFloor() == cooper.getTargetFloor()) {  
	    cooper.setAvoid();  
	    cooper.setUnlock();  
	    elevator.lock.lock(); 
	    elevator.conflictHangUp();  
	    elevator.lock.unlock();  
	}
}

判断写好之后，该通知对方规避了，响应机制当然也得有：

// Elevator
public void setAvoid() {  
    this.awaitingAvoid = true;  
    this.idleCall();  
}

public void respondAvoid() {  
    this.awaitingAvoid = false;
}

改完这些还不够，我们需要对WAITING/IDLE两个状态的转移规则稍加修改，使得在一动一静的情况下，两种状态转移后，可以响应规避请求：

waitingSchedule():

... // 原有实现
// 接在原有实现之后

if (entersIdle) {
	if(shouldAvoid) {
		/*让电梯移动到下一层，类似SCHE，但到了之后不开门*/
		respondAvoid()
	} else {
		setIdle()
	}
}

idleSchedule(): 
if (keepsIdle) {
	if (shouldAvoid) {
		/*让电梯移动到下一层，类似SCHE，但到了之后不开门*/
		respondAvoid()
	} else {
		// 原逻辑
	}
} else {
	...
}

对于同向而行的情况，我们还需要继续修改RUNNING下的运行逻辑，使得避让请求被正确响应：

runningSchedule() {
	... // sleep()完成
	/*更改楼层*/
	/*在楼层更改时，若远离了目标楼层，暂存一个flag*/
	.... // 状态转移
	// normSche原有逻辑结束
	if (flag) {
		elevator.setUnlock(); // 同样，此处开锁是为了保证一个线程只拿一把锁
		respondAvoid()
		cooper.lock.lock();
		cooper.conflictCond.signal();
		cooper.lock.unlock();
	}
	// 需要Scheduler线程的`while(true)`处能够正确处理中途开锁的锁释放问题，可以看看本文前面的实现
}

做到这里，我们就成功的使用纯线程交互的方法，完成了楼层冲突的处理，不需要引入任何新的类来进行管理。

调度

再次，我们本单元求稳为先，选择的方法不一定最优。

我的原调度逻辑（见HW5，6总结）类似影子电梯，在出现双轿厢的时候也犯了难。比起编写新逻辑，我选择最大程度复用原有的调度逻辑。

在原有的调度基础上，我们需要添加是否在运营范围内的判断。

调度第一步，沿用原有逻辑，对所有电梯评估请求是否可分配，选评价指数最低者。

同时，在这一步中，记录下所有的双轿厢电梯。

此处记录的并不是双轿厢电梯对，而是其中的每一个电梯。 例如：2、3是一对双轿厢电梯，我们这里记录的是：电梯2、电梯3，而不是[电梯2，电梯3]。

若第一步未能分配，则进行第二步，“拆请求”。在第二步中，我们只对双轿厢电梯进行评估。

• 将原有请求，以当前评估电梯的目标楼层为节点，按先后顺序分成两段；
• 在第一段请求完成后，再由Dispatcher分配第二段请求。

“拆请求”如何实现？我们需要修改我们已有的乘客请求类passengerRequest，在其属性中加一个passengerRequest followingRequest，存储当前请求的后半段。

在下电梯的时候，需要判断是否包含后续请求，有则OUT-F，并将后续请求放回请求池，没有则OUT-S。

判断是否可加入，与计算代价指数的逻辑不变。 不过，我们选取电梯的逻辑发生了变化，选取优先级如下：

• 可行楼层跨度最大
• 原设计中，评估指数最小者

选取楼层跨度最大者，是因为，我们无法保证后续换乘的次数；换乘可能会造成额外的等待时间，且额外等待时间难以预知。楼层跨度尽可能大，可以尽可能减少换乘次数，一定程度缓解这一问题。

线程交互

不难注意到，对于双轿厢电梯对的其中一个电梯，在IDLE，无请求，且closed的条件下就结束，在这里肯定不对劲。不这样的话，目标楼层的冲突没法规避。

我采取了一个相对粗糙的办法：

• 电梯的close()由Dispatcher调用，这是我的原有设计
• 在close时，Dispatcher用一不加锁的方法，获取当前所有电梯的状态；只在所有电梯都处在IDLE状态时，才将所有电梯close()，否则wait()
• 保证电梯在进入IDLE时，会唤醒Dispatcher

至此，我们完成了HW7所需的所有改造。