BUAA-OO-Unit2

这是2025年北航OO第二单元的总结博客，希望能对你有所帮助😊

  • 魔鬼般的OO-Unit2终于结束啦😭😭😭😁😁😁

龙猫3

  • 进入正题

  • 这是三次迭代后hw7的代码行数统计，源代码行数762行，应该算少的吧
  • 这也反映出本人力求简洁的迭代追求，能少写的就少写，几行代码就能解决的问题绝不去卷高深复杂的方法
  • 下面是本单元的总结与分析

同步块与锁的选择

我们为什么需要同步块？因为多个线程同时运行时可能会对同一共享资源进行访问和修改，这样就会造成竞争与同步问题，因此我们需要锁和同步块来解决这一问题。

在我的代码中，hw5最开始我有一个MainRequests主类和SubRequests子类，后来我发现这两个类里面的属性和方法竟然一模一样(●’◡’●)，后面索性就只有Requests这一个类了

  • 因为Requests类被inputThread和DispatchThread所共享，因此这两个类中对Requests类调用的方法都需要加锁，设置同步块，具体如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public synchronized void sortByPriority() {
       requests.sort(Comparator.comparingInt(r -> ((PersonRequest) r).getPriority()).reversed());
   }

   public synchronized void push(Request request) {
       //TimableOutput.println("from-" + elevatorId + "-request need
       // to be dispatched-" + isDone() + "-" + isEmpty());
       requests.add(request);
       notifyAll();
   }

   public synchronized Request pop() {
       if (!isDone() && isEmpty()) {
           try {
               wait();
           } catch (InterruptedException e) {
               throw new RuntimeException(e);
           }
       }
       if (isEmpty()) {
           return null;
       }
       notifyAll();
       return requests.remove(0);
   }

   public synchronized void setDone() {
       done = true;
       notifyAll();
   }

   public synchronized boolean isDone() {
       return done & (arrivedRequests == needRequests.size());
       //return done;
   }

   public synchronized boolean isEmpty() {
       return requests.isEmpty();
   }
  • 此外还有电梯线程中，在临时调度到达目的地需要将人请下去时，需要设置同步块，保证这是一个原子操作，在这个过程不允许分派线程再将请求添加给电梯的请求队列中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void scheOutPerson() {
        synchronized (subRequests) {
            Iterator<Request> iterator = subRequests.getRequests().iterator();
            while (iterator.hasNext()) {
                PersonRequest preq = (PersonRequest)iterator.next();
                String strFloor = Strategy.toStr(floor);
                int toFloor = Strategy.toInt(preq.getToFloor());
                int id = preq.getPersonId();
                if (peopleInEle.contains(id)) {
                    people--;
                    peopleInEle.remove(Integer.valueOf(id));
                    if (toFloor == floor) {
                        iterator.remove();
                        mainRequests.addArrive();
                        TimableOutput.println("OUT-S-" + id + "-" + strFloor + "-" + elevatorId);
                    } else {
                        ReArrangeRequest raq = new ReArrangeRequest(floor, preq);
                        TimableOutput.println("OUT-F-" + id + "-" + strFloor + "-" + elevatorId);
                        mainRequests.push(raq);
                        iterator.remove();
                    }
                }
            }
        }
    }

调度分配策略

hw5

  • hw5的请求是指定了电梯的，因此直接分配给对应编号的电梯即可，无需过多设计

hw6

  • 最开始我的设计是将所有的主请求按照 1 2 3 ……6 1 2 ……的循环==顺序分配==给6部电梯，这样的设计比较简单，而且在大量的请求加持下，性能也不会很差劲，写法大致如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void personDispatch(PersonRequest request) {
            int elevatorId = inOrder();
            subRequestMap.get(elevatorId).push(request);
            TimableOutput.println("RECEIVE-" + request.getPersonId() + "-" + elevatorId);
        }

    public int inOrder() {
            counter++;
            counter %= 6;
            return counter + 1;
        }

  • 但随后发现hw6新增了临时调度，临时调度期间的电梯无法进行分配，因此在分配调度时必须要考虑电梯是否在临时调度，这也会带来一系列问题：

    • 遇到了临时调度的电梯怎么办，是等待它结束还是重新分派一个新的电梯呢？
    • 如果所有的电梯都临时调度了，怎么办？

    我的策略是遇到了临时调度的电梯，就遍历电梯，找一个Free的电梯分配给它，如果没有电梯Free，则随机决定一个电梯并等它结束临时调度。

    这里有一个很经典也很有趣的问题，如果5部电梯都临时调度，并且在同一时间来了大量请求，那么是否要将这些请求全部分配给那一个空闲的电梯呢？这就是==经典的围师必阙问题==，也是中测mid5的测试意图，如果盲目地全部塞给一个电梯，那么其他电梯结束临时调度后无事可干，但这个电梯后面很有可能吃不消，最终导致TLE，因此我们还需要加一些逻辑，比如设定一个最高分配上限，我设计的是20，当然你也完全可以设置为其他你认为合适的值。把之前的判断加一个条件即可

    1
    if (subRequestMap.get(i).getFree() && subRequestMap.get(i).getSize() < 20)

    我的调度器的核心代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    public void personDispatch(PersonRequest request) {
            counter++;
            counter %= 6;
            Requests requests = subRequestMap.get(counter + 1);
            synchronized (requests) {
                if (!requests.getFree()) {
                    for (int i = 1;i <= 6;i++) {
                        synchronized (subRequestMap.get(i)) {
                            if (subRequestMap.get(i).getFree() && subRequestMap.get(i).getSize() < 20) {
                                TimableOutput.println("RECEIVE-" + request.getPersonId() + "-" + i);
                                subRequestMap.get(i).push(request);
                                return; }
                        }
                    }
                } else {
                    TimableOutput.println("RECEIVE-" + request.getPersonId() + "-" + (counter + 1));
                    subRequestMap.get(counter + 1).push(request);
                    return;
                }
            }
        	//all elevators are not free
            int random = random();
            requests = subRequestMap.get(random);
            synchronized (requests) {
                while (!requests.getFree()) {
                    try {
                        requests.wait();
                    } catch (InterruptedException e) {
                        throw new RuntimeException(e); }
                }
                TimableOutput.println("RECEIVE-" + request.getPersonId() + "-" + random);
                subRequestMap.get(random).push(request);
            }
        }

hw7

  • 在hw6中我们的分派策略已经相对完善了，我们此时只需要考虑哪些地方变了，根据需要增加条件即可
  • 不难发现，如果采用LOCK运行策略，那么在经过UPDATE改造后决不能给电梯分配一个无法到达的请求，我们在分配时还需要获取电梯可到达楼层范围的属性，在我的设计中，可到达范围由一个int型的共享楼层和一个boolean型的是否为A属性来表征。如果为A，也就是电梯改造后在上面运行的电梯，那么运行范围就是共享楼层到顶楼，反之就是底层到共享楼层
  • 明白了hw7中变化的地方后，我们在每次分配前，还需要判断该电梯是否可到达，具体来说，如下
  • 我给电梯的共享楼层属性默认值为100，则未改造前，电梯可到达B4-F7任意楼层，因此直接返回true。下面的判断主要由两种情况，一种是请求的起始楼层无法到达，另一种是起始楼层是共享楼层，但终点无法到达
  • 之后再分配的条件里加上这个isInRange的判断即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean isInRange(int eleId, PersonRequest request) {
        ElevatorThread ele = elevatorMap.get(eleId);
        int sharedFloor = ele.getSharedFloor();
        if (sharedFloor == 100) {
            return true;
        }
        else {
            int fromFloor = Strategy.toInt(request.getFromFloor());
            int toFloor = Strategy.toInt(request.getToFloor());
            if (ele.isA()) {
                if (fromFloor > sharedFloor) {
                    return true;
                } else if (fromFloor == sharedFloor) {
                    return toFloor > sharedFloor;
                }
            } else {
                if (fromFloor < sharedFloor) {
                    return true;
                } else if (fromFloor == sharedFloor) {
                    return toFloor < sharedFloor;
                }
            }
            return false;
        }
    }

性能

强测的请求数量一般比较多，而且很多是同一时间投放的，因此个人觉得无论是采用随机分配还是顺序分配，性能都不会太差，也无需去卷影子电梯了，而且影子电梯在hw7中的修改似乎还比较麻烦，有不少hw6成功实现影子电梯的同学在hw7中放弃了影子电梯，因为模拟的难度比较大，而且可能还有别的bug。而本人的这种杂糅随机分配和顺序分配的方式，在hw7的强测中，性能也还不错😁没有WA的点基本都是94-96之间（WA了两个点。。。😭）

协作图

Unit2_seq-电梯系统协作图

稳定内容

  • 整体架构，MainClass –> Inputthread –> DispatchThread –> ElevatorThread
  • 电梯运行策略：LOOK算法
  • 电梯运行架构：Strategy –> Action –> Elevator

变化内容

  • 分派策略：指定电梯 –> 混合策略
  • 结束逻辑： hw6以后的线程结束需要增加逻辑，详见后面的bug分析部分
  • 电梯运行限制增加，hw7有了楼层限制，共享层进入限制

双轿厢与共享楼层

分析

  • 双轿厢输出begin必须要等两部电梯都把人清空完毕，这就需要建立电梯线程之间的通信机制，这也是之前的架构与设计中所没有的内容。
  • 那么如何建立这种通信机制呢？如果将电梯视为主、子电梯，直接将子电梯的属性或者子电梯本身暴露给主电梯，这样的设计或许实现起来不难，但是却违背了设计的初衷与简洁性，将一个电梯线程暴露给另一个电梯线程，也不符合直觉与常理。
  • 那么，要想实现两电梯线程之间的痛心，就得有一个共享对象，然后由这个共享对象来监听电梯的状态，然后输出begin和end。这里我们==把共享楼层作为一种共享资源，建立一个协作类-Coordinate==
  • 在这个协作类中，不仅可以实现双轿厢改造，还可以实现对共享楼层的互斥访问

双轿厢改造

  • 在输入类读取到双轿厢改造请求时，实例化一个coordinate对象并将其传递给两个电梯线程
  • 在电梯线程内进行改造时，按照如下步骤：
    • free置为false，不再添加请求
    • 将电梯内的人赶下去，赶完后通过coordinate的方法setReady()告诉协作类准备好了
    • 电梯线程准备好后即开始等待另一个电梯准备，在协作类中收到两个电梯准备好的信号后即输出UPDATE-BEGIN- 并唤醒等待的电梯线程
    • 电梯进行改造，设置楼层、速度（其实可以提到前面就完成改造）
    • 告诉协作类改造好了并开始等待，协作类收到两个电梯改造好的信号后即输出UPDATE-END-并且唤醒等待的电梯线程
    • 改造完毕，free置为true

共享楼层互斥

  • 在进入共享楼层前查询是否已被占用，如果是则等待
  • 退出共享楼层前释放锁
  • 就这么简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//Coordinate.java
public synchronized void inShared( ) {
        if (isbusy) {
            try {
                wait();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
        isbusy = true;
    }

public synchronized void outShared( ) {
    isbusy = false;
    notifyAll();
}

debug

hw5

  • hw5大部分人都很漂亮，没有bug，而我重蹈第一单元的覆辙，犯了一个愚蠢的错误：没有控制电梯内人数小于等于6
  • 好笑吧，确实有点幽默了😆😆

hw6

  • 最大的bug是两条语句的顺序反了，，导致我强测爆了近一半的点，气死我了😭😭

    1
    2
    mainRequests.push(raq);
    TimableOutput.println("OUT-F-" + id + "-" + strFloor + "-" + elevatorId);
    • 这是我==错误的代码==，在乘客尚未到达目的地而下电梯的时候，我先将其送回了主请求队列，再进行了输出
    • 如果分派器很快地将这个请求分派给其他电梯，则到导致该乘客还未下电梯就重新分配了
    • 将这两条语句换一下顺序即可

  • 这里我不得不提一嘴，凡是涉及到输出的地方，都==一定要认真认真再认真地检查语句的执行顺序是否有潜在隐患==，不然就会像我一样寄掉

  • 还有一个值得一提的是==程序结束的问题==，在hw5中主请求对列为空且输入线程结束，那么分派器线程也就结束了，但是本次hw6不一样，可能在主请求对列为空且输入线程结束后，还会有人被电梯“遣送”回住请求队列，如果此时分派器线程已经结束，那么这个人就被抛弃了😆，因此需要统计所有要送的乘客数和已到达的乘客数，二者相等才能结束

1
2
3
public synchronized boolean isDone() {
        return done & (arrivedRequests == needRequests.size());
    }

hw7

  • 没什么特别的bug

debug方法

  • 如果有精力有兴趣，最好自己或者与别人合作==搭建评测机==。从数据的生成，到批量运行测试点，再到评测结果与性能，自己一个人还是有些费力的，如果搭建了一个数据够强，覆盖全面，并且能正确评测，批量运行的评测机。相信我，你肯定能找出你的bug。当然，如果你能要到别人的评测机，坐享其成也是不错的
  • 在调试过程中，本人最擅长的还是==print大法==，在各个关键节点，将你所需要的信息统统打印出来，这样可以轻松判断
    • 数据是否正确，状态是否正确
    • 分支进入是否符合预期
    • 线程是否等待、被唤醒、结束
    • ……
  • 如果程序无法结束或者死锁了，我建议用睿睿的输入类结合重定向输入，然后在IDEA里面调试，可以查看各个线程的状态。其他情况还是建议用课程组提供的官方输入包运行，毕竟二者行为可能会不一样。
  • ==多和室友、朋友、同学交流，别自己闭门造车==，很多时候大家都在踩同样的坑或者你踩的坑别人早就踩过啦

心得体会

  • 从最初对多线程一无所知到现在勉强能写个简单的多线程程序，我在第二单元还是学会了很多新的东西，对多线程编程、同步与互斥，并发、数据竞争等有了进一步的更深的理解。
  • Unit2也让我对线程安全有了更深刻的理解，以后的业务方向毫无疑问大部分都是多线程的问题，这时候线程的安全、数据读取的安全就尤为重要，必须要对共享资源的读写进行保护，除了基本的synchronized与notifyAll，我们还可以用读写锁来实现更高的效率与性能。当然，还有更多更高深的方法等待我去学习
  • 印象最深的还是本单元每周五的通宵debug时刻，我清楚地记得
    • hw5的周五我一直de到第二天早上4点
    • hw6几乎占据了整个清明假期，最后也是在第三天凌晨2点通过了中测
    • hw7我周五晚上才开始写，直接通宵了，到第二天5点通过中测，浑然不知天已经亮了
  • 我也在社交平台上每周发一篇帖子，写下自己对OO的抱怨、对debug痛苦的倾诉、对压力的宣泄，也得到了很多学长学姐的鼓励与指导（甚至还有U2猪脚）

鸣谢❤️

  • 感谢OO课程组的老师以及可爱的助教们
  • 感谢与我讨论架构、交流bug、分享经验的朋友们
  • 感谢一起搭建评测机的室友小哥哥
  • 感谢给予我温暖与鼓励的学长学姐们
  • 感谢一路奋斗、顽强拼搏的自己
OO
#OO #Java
BUAA-OO-Unit2
http://pzhwuhu.github.io/2025/04/18/OO-Unit2/
本文作者
pzhwuhu
发布于
2025年4月18日
更新于
2025年4月18日
许可协议