OO_Unit2

OO
发布日期:   2024-03-20
更新日期:   2024-04-19
文章字数:   4.9k
阅读时长:   17 分
阅读次数:  

OO_Unit2: 电梯调度

前言

OO第二单元主要是对多部电梯的运行进行模拟，要求我们使用多线程编程，难点在于理解线程交互过程，需要通过对合适的共享对象加锁来解决线程安全问题。多个线程的同步进行使得需要分析的情况变得复杂多变，而且错误是概率出现的，增加了作业完成和debug难度。随着作业结构越发复杂，更需要理清电梯调度的时序等多种细节，总之要清楚某些时刻电梯在干什么事儿才能尽量避免bug的出现。

hw5

电梯第一次作业需要管理6部电梯，题目已经给出每个Request需要乘坐的电梯ID。本次作业我对多线程设计有了基本的概念，对synchronize同步块和锁的设置有了初步体会。此外我也意识到解耦的重要性，运用好面向对象思想，使用好的架构和明确的分工会让整个作业的构建和调试难度大大降低，同时也会让自己的思路更加清晰明确。

设计思路

生产者-消费者模型

本次作业首先要解决的是如何将乘客请求正确分配给电梯。

我用RequestTable类来存储请求。该类实例化为以下两种请求队列：

  • allRequest：用于存放来自输入所有的请求。
  • ElevatorReqTable：每个电梯都会实例化一个该电梯专有的请求，用于存放该电梯要处理的请求队列。
public class RequestTable {
    //<楼层序号，出发地在该楼层的请求>
    private HashMap<Integer, ArrayList<Person>> requestMap;
    private boolean isEnd;
}

我使用生产者-消费者模型，其中生产者是输入线程类Input，该类拥有实例allRequest，每当有请求输入进来就新建一个Person加入到allRequest中；消费者是Elevator类，每个实例化的电梯都有自己的eleReqTable作为待处理请求。此外输入线程类还负责在输入结束后将总请求队列的isEnd置1代表不再会有新请求，输入结束。

Manager类在这里发挥分配请求的作用，同时拥有以上两种RequestTable。主要负责：

  • 如果allRequest中还有请求，则将其pop出来，按照所需乘坐的电梯id交给相应的电梯自己的eleReqTable。

  • 如果allRequest中没有请求了而且isEnd为1，则将电梯的子table也设为结束结束本进程。

至此电梯类通过成员变量eleReqTable获得了自己需要处理的请求。这时电梯需要根据自身状态以及请求决定其行为。

电梯调度

我的电梯类有如下成员变量：

public Elevator(int id, RequestTable reqTable) {
    this.id = id;
    this.reqTable = reqTable;
    this.curFloor = 1;
    this.curNum = 0; //电梯内总人数
    this.direction = 1;
    this.destMap = new HashMap<>(); 
    // HashMap<Integer, ArrayList<Person>>，当前在电梯内部的Person，按照目的地层数划分
    this.strategy = new Strategy(reqTable);
}

电梯会有如下的行为：

public void move(); //电梯沿着原方向移动一层，改变curFloor即可

public void OpenAndClose();//电梯开门，人员先下后上getOut(),getIn()，关门

public void reverse();//电梯转向，direction取反

public void getOut();//目的地为这一层的人全部出去，直接将destMap整个键删去

public void getIn() {
        //从电梯请求队列移除，delRequest返回需要进入电梯的Person列表
        ArrayList<Person> inPersonList = reqTable.delRequest(curFloor, 6 - curNum, direction);
        for (Person per : inPersonList) {
            //加入电梯的destMap
        }
    }

电梯该如何决定进行何种行为，需要引入Strategy策略类，该类中的一个getAdvice函数会将具体策略(OPEN, MOVE, REVERSE, WAIT, END)交给电梯。所以策略类需要获取当前电梯的请求队列，在之前电梯构造创建自己的Strategy时已经作为Strategy自己的成员变量传入了；至于当前电梯的状态则会在调用getAdvice函数时作为参数传入，具体来说就是：

public Advice getAdvice(int curFloor, int curNum, int dir,
                       HashMap<Integer, ArrayList<Person>> destMap)

接下来执行具体的电梯调度策略就行了，这里我选择了简单易行的LOOK算法。

锁的设置

由于RequestTable类在多个线程中使用，因此对这个类的任何读写操作我都加了锁。此外，由于对RequestTable的任何读写操作我都在该类内完成，我的所有synchronized块全部而且仅出现在请求类中。具体来说，读写RequestTable类主要分为以下几种情况：

  • addPerson: 两类请求都要用，用于向请求队列中加入新的请求(Person)。
  • 由主请求队列allRequest调用的：
    • popPerson: 从主请求中pop出一个Person用于分配给电梯子请求。
  • 由电梯的分请求队列eleReqTable调用的：
    • delRequest: 用于从电梯子请求队列中移除一些符合要求的请求，即代表这些Person进入电梯。
  • 上面的方法全都要加锁，此外还有一些判断Map是否为空，读和写isEnd和其他一些队列情况的方法，也需要上锁。这样我的读写全部封装在类内进行，外面只需要调用这些函数即可。

至于notifyAll，当一个线程调用了某个对象的 notifyAll() 方法时，该对象上所有调用了 wait() 方法而被挂起的线程都将被唤醒，然后它们会竞争对象上的锁。考虑我整个程序中的两个需要wait的地方：

  • 主请求队列在popPerson时主请求队列空了，但输入还没有结束，也就是需要等待外部输入新的请求。在这种情况下：①若外部输入了新的请求，则会通过addPerson函数进行，所以addPerson我增加了notifyAll() 来唤醒。②如果不会再有新的输入，就会执行setEnd，所以在setEnd也增加notifyAll()。
  • 在每个电梯的分请求队列中同理，不过主请求等待的是Input传入，分请求等待Manager的分配。

所以我只在上述两个函数里进行了notifyAll()。

Bug分析

强测和互测没有出现bug，需要注意的是：

  • 超载判断：我一开始在Strategy内判断需要是否需要开门的时候想着先下后上，因此没有在getAdvice中判断是否超载，只在电梯内执行getIn的时候进行了判断。但这造成了电梯一直在某层开关门停不下来的情况。原因是：openToOut(...) | openToIn(...)这一|关系代表着，在没有人在这一层要下电梯的时候才会进行判断有没有人要上电梯的操作，既然没人要下电梯就必然要判断是否超载，因为如果在这里不判断的话返回的就会是开门操作，开门又发现人进不去，于是就造成了上述的死循环。在openToIn中判断人数是否超载即可。
  • 由于会对请求队列的Map进行是否为空的判断，在进行Map的删除时，我都进行了这个键对应的List是否为空的判断，如果为空就直接把这个键删除，这样保证在没有请求（请求被删干净）之后Map也是空的。

UML类图&时序图

hw6

设计思路

第二次迭代新增了电梯RESET功能，电梯接收到重置请求后尽快停下，将所有人放出后修改相关属性，再投入使用，此外还需要自行设计电梯的分配。为了杜绝自由竞争的使用，需要电梯接到请求后输出RECEIVE后才能进行合法移动。

处理RESET请求

首先对于RESET的处理，调度器Manager类新增方法resetElevator，该方法修改需重置电梯对应 RequestTable的resetRequest属性，使其从原先的null变成相应的重置请求。那么电梯便可以在getAdvice时获得RESET的建议，从而执行重置请求。注意请求表类中的setResetReq方法需要notifyAll。此外结束条件需要加上一条：所有电梯都不在reset才能结束。

需要注意的是电梯的reset执行顺序。如果先把Person扔回总表再输出，可能出现同一个人被RECEIVE两次的情况，所以要先立即输出RESET_BEGIN。

public void reset() {
    allOut();//电梯内的乘客清空，扔回电梯请求队列

    TimableOutput.println("RESET_BEGIN-" + this.id);

    ArrayList<Person> personList = reqTable.delAllRequest();
    allRequest.getAllRequest(personList);

    //执行重置，sleep 1.2s
    
    TimableOutput.println("RESET_END-" + id);
    reqTable.setResetReq(null);
}
电梯调度

import java.util.Random;

为了保证正确性我直接采用随机策略。在随机到一个电梯之后只要不在reset就返回其id，如果恰好所有电梯都在reset状态就睡一会儿。这个策略使我在互测从上午10点被hack到第二天下午5点钟，原因在于当只剩下一部电梯可运行时，我的调度策略会把所有请求全部给剩下一部电梯，导致rtle。修改也很简单，就是判断一下仅当≥3部电梯在运行时才进行任务分配。

Bug分析

本次作业强测由于采取了随机策略分数不高但没有出现问题。互测则出现了上述未限流导致的一个问题。

此外，课下我在交中测时发现自己出现了近10s的cpu时间但不知道为什么一直没ctle，于是我开始寻找轮询的可能性。在使用idea自带的Profiler运行时我发现我的cpu浪费了大量资源在Manager的run方法中。打印输出发现在这个循环内出现了轮询的情况。当电梯输入全部结束且主请求表为空时，就会进入判断是否全都不在reset状态。如果得到了false，就会迅速无限重复上述过程造成了轮询，解决方法就是加一个else让程序睡过去。

public void run() {
    while (true) {
        if (allRequest.isEmpty() && allRequest.isEnd()) {
            if (allNotReset()) {
                //...
                //输入结束，将所有子table设为结束，本进程结束
                return;
            } else {
                sleep(100);
            }
        }
        Person per = allRequest.popPerson();
        if (per == null) {
            continue;
        }
        //将Person分配给电梯
    }
}

UML类图&时序图

hw7

第7次作业增加了双轿厢电梯的重置请求，复杂度进一步提高。

设计思路

本次作业我将Manager改为单例模式，这样做的好处是其他类需要使用总表allRequest的时候可以通过Manager直接获取，实现起来更加清晰和安全。此外前两次作业我在main函数让各个线程分别开始跑，本次作业改为层次化的start，使得程序层次更清晰。

我在Manager类中实现两类电梯的创建和管理。首先是Manager的构造方法负责创建总表，6个电梯的分请求表对象，以及6部电梯的启动。实际上我们在调度器Manager中并非直接管理电梯，甚至不需要专门设置管理Elevator电梯类的容器——我们实际上都是通过操作电梯所对应的requestTable来进行管理的。我先前使用List管理6个请求表，但考虑到之后有双轿厢电梯和普通电梯同时运行，本次作业我简单地使用HashMap<Integer, RequestTable> requestMap统一管理两种电梯。具体映射方法如下。初始就只需新建key为1-6的电梯请求表。查看给定id的电梯，如果是普通电梯就会存在key=id， 如果是双轿电梯则存在key=id + 6和key=id + 12。

Key Value
1-6 普通电梯1-6的请求表
7-12 双轿厢电梯A1-A6的请求表
13-18 双轿厢电梯B1-B6的请求表
双轿厢电梯RESET

这类请求相当于需要把原来的电梯直接弃用，再new两个新电梯。关于请求的设置思路与NormalReset相同，依然是在电梯相应的requestTable里修改属性，然后电梯通过Advice得到。不同的是原先的电梯线程执行完dcReset之后就可以光荣下岗了，我的实现中直接将其break掉，线程结束。

至于电梯的dcReset函数，同样需要将电梯里的人全都赶出去扔回总表，打印等流程，然后我令其调用Manager创建双轿厢电梯的方法，然后该电梯圆满完成任务。

createLine新建双轿厢电梯，引入Line类实现双轿厢电梯的管理，在其中设置新电梯的相关属性并使其start即可。

public synchronized void createLine(DoubleCarResetRequest dcReq) {
    //新创建 requestTableA，requestTableB

	requestMap.remove(eleId);
    requestMap.put(eleId + 6, requestTableA);
    requestMap.put(eleId + 12, requestTableB);

   //...
   //新建Line
}
电梯防撞

另一个重点就是如何避免电梯在A，B共享的停靠层相撞。引入Floor类作为一对双轿电梯的共享对象，在创建Line对象的时候将其作为电梯的属性分配给两个新电梯。

public class Floor {
    private boolean isOccupied;
    private RequestTable reqTableA;
    private RequestTable reqTableB; 
}

当双轿厢类型电梯在运行move()的时候需要特判一下：如果电梯下一步会move到换乘层，就需要判断Floor是否被占用。同样地使用RequestTable作为信息传递的媒介,新增isNeedAway属性即可。同样需要判断，如果双轿厢电梯离开了换乘层将occupied标志解除占用。

另一个重要的问题是如果电梯已经占有floor，移动到了换乘层，需要额外再获取一下Advice，如果这时候得到的是OPEN，就需要开门。

新增一个AWAY的Advice，如果这时有电梯在换乘层且挡道了就让其避开。最后，如果一个双轿厢电梯在得到结束的Advice时，如果还停在换乘层，同样让其AWAY以避免出现因电梯A停止运行而B电梯无法让A再避开的情况。

ADVICE的优先级问题：

public class Strategy {
    public Advice getAdvice(...) {
        if (reqTable.getNormalResetRequest() != null) { return Advice.RESET; }
        if (reqTable.getDcResetReq() != null) { return Advice.DCRESET; }
        
        if (openToOut(...) || openToIn(...) || OpenToTransfer(...)) { return Advice.OPEN; }
        if (curFloor == transFloor && reqTable.isNeedAway()) {  return Advice.AWAY; }
        
        if (curNum > 0) { 
            //look算法...
        }
    }

这一部分电梯的运行以及Advice的获取有很多细节要注意，一旦出现一些小问题就很容易出现电梯遁地，升天等停不下来的情况，不过相比死锁和轮询还是友好的。

至于互斥的实现，一开始的时候我使用了一种类似于下述代码的方法，先检查是否有占用标记，若没被占用留下标志。后来看到osppt明确说明了这样实现的问题，即：Occupied的读和写会出现一个空档，无法真正实现互斥。当时已经是周五晚，于是也直接通过sleep解决。

while(Occupied) { wait(); }
Occupied = true;
//访问Floor
Occupied = false;
双轿厢电梯乘客换乘

由于双轿厢电梯的出现，有些乘客一次分配是无法被送达目的地的。这时我会把人扔回总表。这时总表结束条件判断还需要新增一个条件，那就是所有需要换乘的乘客请求都完成。为此为Person新建needTransfer属性。在调度器中引入记录需要换乘的乘客数量transferNum。每当把一个personRequest分配给双轿电梯时，就需要判断一下这个A/B电梯是否能一趟把乘客送达。

public synchronized int getEleId(Person person) {
        int id = random.nextInt(6) + 1;
        if (requestMap.containsKey(id)) { //分配给单轿厢
            //... return id
        } else { //双轿电梯
            int tmp;//用于决定给A/B梯
            if (!isChange(from, to, transFloor)) { //不需要换乘
                //...确定tmp
            } else {
                transferNum++;
                person.setNeedTransfer(true);//该人分配给了双轿电梯，且需要换乘
                //...确定tmp
            }
            return tmp * 6 + id;
        }
    }

在Elevator开关门的时候也需要更改：

public void OpenAndClose() {
    //...
    getOut();
    if (type != 0 && curFloor == transferFloor) { transfer(); }
    Advice adv = strategy.getAdvice(...);
    if (adv == Advice.REVERSE) { reverse(); }
    getIn();
    //...
}

public void transfer() { //将电梯里所有需要换乘的人放出去, 扔回总表
        //...遍历电梯内剩下的乘客
        if (per.isNeedTransfer()) {
            //开门放人...
            per.setFromFloor(transferFloor);
            per.setNeedTransfer(false);
            Manager.getInstance().getAllRequestTable().addPerson(per);
            Manager.getInstance().decTransferNum();
            listIter.remove();//把这个人删去
        }
}

换乘函数transfer负责将电梯里所有需要换乘的人放出去, 扔回总表。这时，在我的实现下，最好先执行完getOut()，将所有本来就在该换乘层到达目的地的乘客送出去。这时双轿电梯剩下的乘客应该只剩下因被迫换乘而下电梯的乘客。依然要注意Map在对应键为空的时候要维护，将整个键也删除。

于是我在结束条件判断的时候，总共需要判断：①总表输入结束且总表为空 ②普通电梯不能在执行任意一种reset，且所有分请求表为空 ③需要换乘的乘客都送完了，transferNum != 0。这样结束条件的问题也解决了。

Bug分析

本次作业强测和互测都没有出现bug。一些细节是：
我在对RequestTable的属性(NormalResetReq，dcResetRequest，needAway)进行set的时候都进行了notifyAll。对于第二次作业会被hack的数据，我继续采用sleep，也就是如果随机到的电梯刚好在reset就睡，然后获取新的随机id，随到一个能用的电梯为止。这样既保证了很难被hack，又保证了这样一个最基本的策略分数注定很低。

UML类图&时序图

变和不变

我在三次迭代中总体架构没有太大的变化，基本是直接在原先的架构上增加新的功能。首先Input，Manager，Elevator三个线程类的共嫩没有改变，RequestTable作为共享资源的性质及其传递信息的功能也没有改变。同样我的调度策略由于没有也没有变化。

为了实现新增的两种类型RESET，我在Manager中分别新增了相关的同步方法，通过请求表共享信息。另外电梯的策略以及run方法也要做相关调整。对于双轿厢电梯的重置还为Person类新增了属性以辨别乘客换乘请求是否结束。

总结与心得

final

本单元让我对多线程有了深刻的体会，同时我也加强了合理进行规划设计，降低耦合，让线程间各司其职的意识，加深了我对面向对象思想的理解。我也又一次意识到保持代码的简洁和结构的清晰是多么重要。

传说中的电梯单元总算是快结束了，总体来看我三次作业的完成和debug过程果然是困难重重。之前我习惯性打断点调试的方法不再适用，我非常清晰地记得第三次迭代的周四周五的两点钟依然在宿舍debug，看到错误的输出仿佛能听到我电梯相撞的声音。。虽然最后没有出现很大的问题，但不足之处也很明显，就是为了保证最基本的正确性可以说是一点优化也没做了，几乎全是睡过去的。希望以后能在优化方面做得更好吧orz

最后，感谢X267三位神仙的巨大帮助orzzzzzzzz/(ㄒoㄒ)/~~

OO
  目录