OO_Unit2

[TOC]

架构 && 迭代

在 如何让系统结束 上，我起初采用了递进式 kill：MainCtrl 判定总队列空且已经输入了 NULL，就 kill 自己并把信号传递给所有电梯，电梯接收到 kill 信号后根据自身进度决定什么时候结束。这个方法很不靠谱，导致我互测被刀了。我后来根据水群里大佬们的分享改成了计数器：维护一个 cntRest 之类的东西，+1，-1，当 cntRest == 0 并且已经输入了 NULL 就全终止，优雅又省心。

锁 && 同步块

总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系

调度器设计

我在 HW6 一共写了 4 种调度器算法，在 HW6 跑了 2000 轮数据排名：影子电梯 > (自由竞争，随机) > 均匀。所以我在 HW7 只迭代了影子电梯。

我没有尝试纯启发式，但互测的时候看到我们房多数人用了纯启发，不过没有发现性能很好的。不知道有没有人纯启发很成功的。

均匀分配

均匀分配全方位倒第一，所以很快就被淘汰了。

Random

随机性能挺好的（但远远不如影子和自由竞争），而且（>50组数据时）很稳定，但它有一个让人很难受的问题：它没办法设计预定队列，所以想避开一次性维修 5 台电梯压力最后一台电梯只能靠接收上限，但这样写不好容易搞出来轮询。

自由竞争

这是一种下限很低，但上限很高的算法，如果实现的好的话可能仅次于完善的影子电梯。但不知道为什么我写出来的自由竞争显著倾向于节省电量（比影子电梯省 1/3），时间性能不好（比影子电梯多 1/4），后来渐渐放弃了。

核心思路是计算所有电梯接到这个乘客的时间加以比较。这个方案是如何处理时长与电量之间的关系的？我感到很迷惑。我只是机械的操作了 “计算接到乘客的时长”，我没有想为什么最快接到人的就是最好的。如果说是从 “最快接到” 的角度让 “平均时长” 尽可能的短……可我写出来效果不是这样的。

自由竞争里也有小模拟，和影子电梯有一点点像，只是轻量很多，也不用起线程。另外这好像是唯一一个能直接反映 “平均时长” 的算法，影子电梯完全没法管 “平均时长“ 的。

影子电梯

这个上限更高，也更让人越优化越绝望。影子电梯理论上可以获取最佳的运行方案，但考虑到不断有乘客到来，影子电梯不可能做到真正的一比一复刻，即使想做到高度复刻也是很困难的。还有 “平均完成时间” 的概念完全无法计算，只能考虑总时长和电量然后研究怎么加权。

我的影子电梯的核心思路是假设当前乘客是最后一名乘客，计算选中的电梯送完所有人的时间 cost 和耗电量 power。有关 cost 和 power 的权重我想了很久，最终得出的结论是我不应该给 power 任何权重，因为这个 power 跟新加的人相关性实在太小了。（我尝试分别赋 10:0、9:1、8:2、……、1:10 的权重跑了几个 100 轮，跑出来的名次不稳定，但总的来说差距比较小，而且当时我的代码还有 2/1000 左右的 bug，就不了了之了）。

在 HW6 我的影子电梯运行策略与原电梯完全一致，对于正在维修的电梯，我设置了一个 preQueue 用来存要分配给他但不能输出 RECEIVE 的乘客，这样一来就不存在不能接人的电梯，所以影子电梯的维修时行为也和原电梯完全一致。

在 HW7，我总共设计了 4 种模拟双轿厢的影子：

  • 给广义电梯类（或者说电梯井类）也写影子，然后全模拟
  • 限制电梯的运行范围，然后统计所有没到达目的地的乘客距离目的地的距离，除以 3 （核载人数-1）然后 × 一个数字
  • 统计 time/perFloor,perPerson
  • 假设电梯可以运行全程，然后罚时（×权重）

理论来讲最好的应该是第一种，但我肯定是哪儿写错了，效果不如最后一种。所以说我写了一大圈，最后交的是只需要加半行的策略……所以说影子电梯它很让人绝望。

不过总的来说性能挺好的。

手动构造数据策略

吸取上一个月的教训，不能完全依赖数据生成器。我采用以下几点策略尽可能地强化数据点。

  • 压力某一台电梯：通过维修、设计距离之类的方法试着把人逼上同一台电梯，然后就离 RTLE 不远了。

bugs

在 HW5 强测出现一个 bug，互测也是同一个 bug；HW6 互测出现一个 bug；HW7 没有 bug。

HW5 强测 && 互测

强测 WA 了一个点。很奇怪。在电梯月 WA 了。

问题出在：必须先 RECEIVE 后加入队列！！！

我猜测这个限制或许是为了 ban 掉量子电梯抢跑，因为如果不强制要求先 RECEIVE 后采取任何行动的话，评测机无法得知在 RECEIVE 乘客前的那 0.4s 电梯在做什么，也就是说乘客可以同时 向上/不动/向下（薛定谔的量子电梯），而且这似乎是唯一一种确定可以提升效率的量子电梯。但它也同时 ban 掉了先加入队列后输出 RECEIVE 的人，因为加入队列后电梯就可以行动了，但这时可能还没来得及输出 RECEIVE。于是我这个二百五就这样被打了。

当然虽然这个点真的很蠢，但我会 WA 根本上还是因为不习惯从多线程的角度思考问题，对并行中可能出现的问题不够敏感（是完全没有知觉，我天真的以为搞定同步互斥问题就 ok 了），不然也不会在题目明确要求的情况下仍然随随便便写这两行代码。

不难发现，当时我的评测机也并没有针对 RECEIVE 顺序的测试。

课下 bug 0

我在 HW6 及以前没有给电梯设任何楼层范围的限制（按理说用不着），但测试 HW6 的时候莫名卡死。经检查发现竟然是我的影子电梯飞天遁地了！因为电梯快照照的不同步导致出现了 weight != 0 但 destMap 空着的尴尬情况，我的 LOOK 又是很纯粹的接不到反向乘客、weight 不为 0 就一直走的 LOOK，根本停不下来……

解决方案：我把电梯快照改成了原子操作，这样虽然保证不了分配策略拿到最新数据，但起码能正常运行结束了，顶多就是数据不够新导致策略不太好。

课下 bug 1

这个 bug 没有以任何形式被测出来，是我静态臆想出来的，所以我不确定它是否真的有问题或者有可能被打到。

我继承自 HW5 的代码中，系统结束过程是递进式的：MainCtrl 判定总队列空且已经输入了 NULL，就 kill 自己把信号传递给所有电梯，电梯接收到 kill 信号后根据自身进度决定什么时候结束。这样在 HW5 很好，但在 HW6 不行，因为我处理维修电梯中乘客的方法是把它们丢回总队列，设想：

输入的最后一句是 MAINT 6 号电梯，MainCtrl 将该信号传递给 6 号电梯后自杀，6 号电梯歇了一会儿后开门把人都撵回主队列，结果发现主队列已经不复存在了，可怜的乘客成了孤魂野鬼。

解决方案是在 MainCtrl 的判定条件中加入当前是否有电梯在维修。不幸的是，这个解决方案引入了新的 bug：

HW6 强测 && 互测

强测侥幸过了，互测被刀了 14 刀，玉衡星来给大家发福利啦 😉。

被刀中的原因是死锁。这个死锁来的猝不及防，因为我其实是地毯式检查过死锁的，但不幸的是这个死锁是在检查之后被引入的……

我的 MainCtrl 里有这样一段代码：

1
2
3
4
5
6
7
8
9
Person person = mainWaitQueue.getaRequest(); // 从总队列里取一个人
if (person == null) {
    synchronized (validElevatorLock) { // 检查一下是不是在检修，否则可能最后一个人刚下电梯，MainCtrl 就下班了
        while (hasMaintainingElevator()) {
            ......
        }
    }
    ......
}

这个 hasMaintainingElevator 调用了 synchronized boolean isMaintaining()，而 validElevatorLock 是个全局变量锁，这样就诞生了一个教科书式的所顺序反转。而这个 validElevatorLock 是我在 debug 过程中加入的，目的是维护 “整个系统中是否有电梯正在维修” 状态的一致性，设置这个状态的目的是为了解决 bug1。

或许可以靠顺序修改解决这个问题，但我在修改的时候看到群里有人说采用计数器的方法来停掉 MainCtrl，也就是从根本上改掉我那个不靠谱的递进式 kill，这个方法明显比我那个优雅的多，所以我改成了计数器，这个修改让我得以顺利度过 HW7。

HW7 强测 && 互测

没有刀，但其实有一处很危险。

因为我的影子电梯是可以预定的，在维修状态的电梯可以把人收进预队列里，所以我就没写一个电梯接受人数上限的设置。但我的双轿厢罚时设计的不好，所以 5 台电梯升级加同时爆发大量请求可以把人都逼到同一台电梯里，最长可达 180.059 s 左右。不难想象这个点有多难打，不知道是不是有人发现了但刀不中。

HW7 房间有个人大约有 15% 的数据点维修超时或者升级超时，但我始终没能刀中。

线程安全 && 层次化设计

  • 没有绝对安全的线程……当然是假的，但我 de 同步问题 de 的很痛苦。
  • 或许可以给电梯设计一个基类，然后让 1~6 电梯和影子电梯都继承它，这样就不要每次都费劲让它们保持一致了。

大模型

  • GPT 从 HW5 开始写的评测机和数据生成器，一直写到 HW7。每次把迭代内容输入/输出、数据强化思路总结给它。好处是写的快、省事儿而且足够强，坏处是从 HW6 开始我就看不懂也懒得看了。这个评测机测出了我绝大多数的 bug，从 5/100 RTLE 到 10000/10000 AC。
  • 我让 GPT 写了一个根据输入/错误的输出自动生成格式化报告的程序，总结出程序结束（其实是卡死）时 MainQueue 中的人和所有电梯没送完的人，以便于检查死锁。
  • 代码是古法的。

心得体会

可能的建议

  • 诚挚地建议提高电梯月互测中的代码运行次数，哪怕 2 次也可以……刀不到的 bug 太难受了……这样也可以变相减少总的提交次数
  • 希望有关 “恶意 hack 同质 bug” 可以有 更明确的说明，比如 保证在被判定为恶意 hack 之前会有助教联系确认情况 之类的……因为很多时候都存在：“A 和 B 有相同的问题，但 A 的问题更严重，我可能永远刀不到 B，但我会稳定地误伤 A” 的问题。
  • 助教哥哥姐姐们辛苦了。