BUAA-OO-2024-Unit2

同步块与锁

在本单元的设计中，考虑到对性能的影响不大（请求数量级为 $10^2$ ），以及为了更简单地保证共享资源时的线程安全，绝大部分情况下我是用synchronized给方法加锁（即锁住对应实例）。

其余部分为了实现其他的互斥操作或者线程同步操作，如将进行重置操作后的乘客“遣返”回主请求队列、进行影子电梯模拟、双轿厢离开交换楼层时通知另一个轿厢，则会使用synchronized (...) {}进行上锁。

需要注意的是，后者加锁方式必须仔细考虑获取锁的时候是否会造成死锁问题，也可以使用ReentrantLock的tryLock()方法避免这一问题，此处先按下不表。

总之，在进行多线程同步设计时，需要对线程间的协作和资源的共享情况有一个清醒的认知。

架构设计迭代

hw5

基本思路

主要采用了生产者-消费者设计模式，一方面输入线程InputThread不断“生产”请求，另一方面将这些请求经由调度器Dispatcher分发给一个合适的电梯线程Elevator去处理。

由于这次作业指定了每个乘客乘坐的电梯，故最开始~~没有单独设计~~Dispatcher，直接分给对应的电梯就好了。

while (true) {
    if (mainRequestQueue.isEmpty() && mainRequestQueue.isEnd()) {
        for (int i = 1; i <= 6; ++i) {
            requestQueues.get(i - 1).setEndFlag(true);
        }
        return;
    }
    Person person = mainRequestQueue.getOneRequestAndRemove();
    if (person == null) {
        continue;//跳过
    }
    requestQueues.get(person.getElevatorId() - 1).addRequest(person);
}

至于电梯的运行策略，采用了主流且效率高的 $\mathcal{LOOK}$ 策略，具体流程和实现如下：

首先规定电梯初始运行方向（由于所有电梯初始停在一楼，故方向设为向上direction = true），然后沿此方向移动
到达某楼层后，根据电梯内外乘客情况，判断是否需要进行开关门操作
- 如果有人达到目的地（这里为了方便设置了一个以楼层为Key的HashMap来记录），则开门
- 如果该楼层有人，方向与电梯相同且不超载，则开门
接着判断电梯中是否还有人，有则继续移动，没有则检查请求队列
- 队列为空，若endFlag为真则电梯停止工作，否则等待请求输入和分配
- 不为空，且存在请求的出发地为此时电梯运行的前方，则继续移动；若所有请求都在相反的方向，则调头

public Advice getAdvice() {
    if (canOpenForOut() || canOpenForIn()) {
        return Advice.OPEN;
    }
    if (curNumber != 0) {
        return Advice.MOVE;
    } else {
        if (this.requestQueue.isEmpty()) {
            if (this.requestQueue.isEnd()) {
                return Advice.END;
            } else {
                return Advice.WAIT;
            }
        }
        if (haveSameDirection()) {
            return Advice.MOVE;
        } else {
            return Advice.REVERSE;
        }
    }
}

hw6

基本思路

采用两级调度器进行调度，一级调度器即dispatcher，使用影子电梯模拟局部最优解，将请求分给最合适的电梯；二级调度器即电梯运行策略strategy，与之前基本保持不变。（新增RESET动作）

设置乘客请求达到的顺序order，按照先来后到的顺序进行分配和接送：

public int compareTo(Person person) {
    return Integer.compare(this.order, person.order);
}

public class RequestQueue {//主请求队列
    private final PriorityQueue<Person> requests;
    ...
}

private final PriorityQueue<Person> requestQueue;

为每个电梯增加一个等待队列waitingQueue，用于暂存重置期间被分配的乘客，重置完成后再将其加入requestQueue

for (Person person : waitingQueue) {
    TimableOutput.println(String.format("RECEIVE-%d-%d", person.getPersonId(), id));
    requestQueue.add(person);
}
waitingQueue.clear();

主请求队列end条件变为

public synchronized boolean isEnd() {
    return this.endFlag && resetCount == 0;
    //新增resetCount确保所有reset都已完成
}

架构调整

另外，在进行hw6的bug修复时，借鉴讨论区大佬的思路，对架构进行了一些调整——将电梯的运行状态与线程分离开来，单独设计一个处理器类ProcessingUnit。

为了读取电梯的状态实现影子电梯的模拟，电梯的运行状态成了电梯和调度器的共享资源。所以为了整体架构和各部分职责看起来更清晰明了，选择将电梯的运行状态与线程分离开来。

public class Elevator extends Thread {
    private final ProcessingUnit processingUnit;
    
    public Elevator(ProcessingUnit processingUnit) {
        this.processingUnit = processingUnit;
    }
    
    public void run() {
        while (true) {
            if (processingUnit.execute() == 1) {
                break;
            }
        }
    }
}

hw7

基本思路

主要是对于双轿厢进行的调整，不过规定了重置为双轿厢之后就不得再重置，倒是省去了不少麻烦。

然后是主请求队列end条件变为

1
2
3

public synchronized boolean isEnd() {
    return this.endFlag && resetCount == 0 && peopleCount == 0;
}

双轿厢设计

开始时就创建12个电梯线程，1-6为A轿厢，7-12为B轿厢（未重置时处于Advice.WAIT状态）
A轿厢完成双轿厢重置后，再去唤醒B轿厢，使得重置完成同步

if (isDoubleCar.equals("-B") && resetFlag) {
    startTime = System.currentTimeMillis();
    checkResetFlag();//等待唤醒
}
//---------------
if (transferFloor != 0) {
    isDoubleCar = "-A";
    curFloor = transferFloor - 1;
    synchronized (anotherCar) {
        anotherCar.notify();
    }
}

值得注意是，我设置了isDoubleCar这一属性来区分双轿厢和解决输出问题（初始为NULL），而A轿厢释放乘客时还未完成重置，此时还不能将这一属性改为-A。

同时，如果某次模拟的时候正在进行双轿厢重置，别忘了设置影子电梯的当前楼层为transferFloor + 1。

在双轿厢中设置共享对象Flag，处理相撞问题

if (!isDoubleCar.isEmpty() && curFloor == transferFloor) {
    if (flag.getState()) {
        try {
            wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    flag.setOccupied(true);
}
//进入前等待另一轿厢离开

if (!isDoubleCar.isEmpty() && tempFloor == transferFloor) {
    flag.setOccupied(false);
    if (isDoubleCar.equals("-B")) {
        try {
            wait(5);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
    synchronized (anotherCar) {
        anotherCar.notify();
    }
}
//离开后通知另一轿厢

最终架构

类图

New_diagram

时序图

seq

复杂度

method	CogC	ev(G)	iv(G)	v(G)
Dispatcher.dispatch	0.0	1.0	1.0	1.0
Dispatcher.Dispatcher	0.0	1.0	1.0	1.0
Dispatcher.doubleCarReset	0.0	1.0	1.0	1.0
Dispatcher.getBestElevator(Person)	16.0	6.0	8.0	11.0
Dispatcher.normalReset(int, int, int)	0.0	1.0	1.0	1.0
Dispatcher.run()	9.0	4.0	5.0	6.0
Dispatcher.simulate(ProcessingUnit, Person)	0.0	1.0	1.0	1.0
Elevator.Elevator(ProcessingUnit)	0.0	1.0	1.0	1.0s
Elevator.run()	3.0	3.0	2.0	3.0
Flag.Flag()	0.0	1.0	1.0	1.0
Flag.getState()	0.0	1.0	1.0	1.0
Flag.setOccupied(boolean)	0.0	1.0	1.0	1.0
InputThread.InputThread(RequestQueue, Dispatcher)	0.0	1.0	1.0	1.0
InputThread.run()	9.0	3.0	5.0	6.0
MainClass.init(RequestQueue)	4.0	1.0	3.0	4.0
MainClass.main(String[])	0.0	1.0	1.0	1.0
Person.compareTo(Person)	0.0	1.0	1.0	1.0
Person.deepClone()	0.0	1.0	1.0	1.0
Person.getDirection()	0.0	1.0	1.0	1.0
Person.getFromFloor()	0.0	1.0	1.0	1.0
Person.getPersonId()	0.0	1.0	1.0	1.0
Person.getToFloor()	0.0	1.0	1.0	1.0
Person.Person(int, int, int, int)	0.0	1.0	1.0	1.0
Person.setFromFloor(int)	0.0	1.0	1.0	1.0
ProcessingUnit.addRequest(Person)	4.0	1.0	3.0	3.0
ProcessingUnit.canTake(int)	1.0	1.0	1.0	2.0
ProcessingUnit.checkResetFlag()	2.0	1.0	2.0	3.0
ProcessingUnit.clearTheElevator()	6.0	1.0	5.0	5.0
ProcessingUnit.execute()	2.0	2.0	1.0	7.0
ProcessingUnit.getAdvice()	0.0	1.0	1.0	1.0
ProcessingUnit.getRestTime()	0.0	1.0	1.0	1.0
ProcessingUnit.getTransferFloor()	0.0	1.0	1.0	1.0
ProcessingUnit.makeShadowElevator(ShadowElevator)	7.0	1.0	6.0	7.0
ProcessingUnit.move()	30.0	7.0	9.0	15.0
ProcessingUnit.openAndClose()	30.0	6.0	12.0	16.0
ProcessingUnit.ProcessingUnit(int, RequestQueue, PriorityQueue, ArrayList)	0.0	1.0	1.0	1.0
ProcessingUnit.reset()	12.0	4.0	7.0	9.0
ProcessingUnit.setDoubleCar(String, int, int, int, ProcessingUnit)	0.0	1.0	1.0	1.0
ProcessingUnit.setEndFlag(boolean)	1.0	1.0	2.0	2.0
ProcessingUnit.setFlag(Flag)	0.0	1.0	1.0	1.0
ProcessingUnit.setResetFlag(boolean, int, int)	1.0	1.0	2.0	2.0
ProcessingUnit.waitRequest()	6.0	2.0	5.0	6.0
RequestQueue.addRequest(Person)	0.0	1.0	1.0	1.0
RequestQueue.addReset()	0.0	1.0	1.0	1.0
RequestQueue.finishOneRequest()	0.0	1.0	1.0	1.0
RequestQueue.finishOneReset()	0.0	1.0	1.0	1.0
RequestQueue.getOneRequestAndRemove()	6.0	3.0	3.0	7.0
RequestQueue.isEmpty()	0.0	1.0	1.0	1.0
RequestQueue.isEnd()	1.0	1.0	1.0	3.0
RequestQueue.RequestQueue()	0.0	1.0	1.0	1.0
RequestQueue.setEndFlag(boolean)	0.0	1.0	1.0	1.0
ShadowElevator.addPerson(Person)	0.0	1.0	1.0	1.0
ShadowElevator.canTake(int)	1.0	1.0	1.0	2.0
ShadowElevator.move()	4.0	1.0	1.0	4.0
ShadowElevator.openAndClose()	12.0	4.0	5.0	8.0
ShadowElevator.reset()	1.0	1.0	2.0	2.0
ShadowElevator.run(Person)	3.0	1.0	2.0	7.0
ShadowElevator.setAttributes(int, int, int, int, int)	0.0	1.0	1.0	1.0
ShadowElevator.setAttributes(String, int, int, int, int, boolean)	0.0	1.0	1.0	1.0
ShadowElevator.setQueue(int, PriorityQueue, ArrayList, HashMap>, boolean)	0.0	1.0	1.0	1.0
Strategy.canOpenForIn(int, int, boolean, int)	5.0	4.0	3.0	5.0
Strategy.canOpenForOut(int, HashMap>)	0.0	1.0	1.0	1.0
Strategy.getAdvice(int, int, boolean, int, HashMap>, boolean, boolean, …)	15.0	7.0	3.0	9.0
Strategy.haveSameDirection(int, boolean)	3.0	3.0	2.0	3.0
Strategy.Strategy(PriorityQueue)	0.0	1.0	1.0	1.0

可以看到，为了保证性能、处理轿厢相撞问题，复杂度主要在电梯的openAndClose、move出现了超标，这也算是符合预期吧。不过总的来说，感觉最后的架构还是十分清晰的，各部分内容较好地做到了高内聚低耦合、职责分明。

关于影子电梯

基本步骤

深克隆电梯状态
模拟电梯运行过程得到最优电梯
将请求分给对应电梯

需要注意的问题

为了模拟结果的准确，我们必须获取到在进行分配的那一刻的所有电梯的状态，并且模拟过程中所有电梯都不能运行。

但是电梯是一刻不停地持锁在运作的，如果要等待每个电梯完成当前动作，那分配过程将会迟迟无法结束，这是完全不能接受的。所以选择将sleep改为wait，让电梯在模拟时间消耗时将锁释放出。这样调度器线程和电梯线程交替获取和释放锁，便可以在性能损失最小的情况下解决这一问题。

long curTime = System.currentTimeMillis();
while (System.currentTimeMillis() < curTime + 400) {
    try {
        wait(curTime + 400 - System.currentTimeMillis());
    } catch (InterruptedException e) {
        throw new RuntimeException(e);
    }
}

不过这个时候又有新的问题产生，那就是电梯当前动作没有执行完，状态没有稳定下来，就可能导致模拟结果的不准确。为了解决这个问题，我在影子电梯中保留了当前的状态（如resetFlag等），让影子电梯将当前作业也完整地模拟一遍，同时记录电梯进行当前动作已经花费的时间（若需要花费），最后从总时间中减去，便可得到较为精确模拟的结果。

public synchronized long getRestTime() {
    return System.currentTimeMillis() - this.startTime;
}
//dispatcher
if (advice.equals(Advice.RESET) || advice.equals(Advice.MOVE) ||
        advice.equals(Advice.OPEN)) {
    spendTime -= processingUnits.get(i - 1).getRestTime();
}

bug分析

第一次作业强测和互测均未出现问题。

第二次作业深克隆的时候没有去获取所有电梯的锁，线程安全出了大问题，本地没有做好足够的测试掉以轻心了。结果强测错两个点，互测更是被刀烂了。后来bug修复了时候进行了一些小重构，也使得架构更加清晰。

第三次作业出现了死锁问题。具体来说，为了避免双轿厢电梯相撞，设置了共享对象Flag，当轿厢将进入交换层时，若Flag被占则wait；当轿厢离开时，取消占领并notify另一轿厢。

但是在影子电梯的实现过程中需要依次获取总计12个电梯的锁（1-6为下层轿厢，7-12位上层），若已经获取了i-A电梯的锁，而i-B尝试进行上文所述唤醒操作时，则不可避免地会产生死锁。

为解决这个问题而不进行大的调整（改用ReentrantLock），将影子电梯中获取锁的顺序改为同一电梯井的顺序而非电梯编号顺序；同时若i-B尝试唤醒，先令其wait(5)，将可能被需要的锁短暂地交出。

心得体会

本单元无疑是巨大的失败，后两次强测均有bug，归根结底还是因为没有做充分的测试和对多线程协作理解不够深。不过在修复bug的过程中，我也开始对如何设置同步块和锁的获取顺序以防止死锁等问题，有了更多的思考与体会。

另外，影子电梯虽然给我带来了不少bug，但最后实现了以后还是挺赏心悦目的，然后~~debug能力也更进一步了~~