BUAA OO UNIT2 目的选层电梯 单元总结
同步块&锁
hw5
| 类 | Qu | Rlist | Elv | ElvMotor |
|---|---|---|---|---|
| IN | run() | |||
| Trans | Close(), tr(), run() | |||
| Rlist | add(), done(), qry(), poll() | |||
| Elv | setClsd(), add(), done(), redir(),port(), run() | redir(), port(), wk(), run() | ||
| ElvMotor | flr(), gate(), up(), dn(), open(), close(), cmd(), run() |
hw6
| Qu | Trans | Elv | ElvMotor | |
|---|---|---|---|---|
| IN | run() | |||
| Trans | close(), launch(), nalloc(), run() | Newelv(), launch(), run() | Launch() | |
| Elv | porti(), run() | wtf(), dir(), launch(), tp(), dis(), done(), ori(),wk(), run() | ||
| ElvMotor | flr(), gate(), cmd(), up(), dn(), run() |
hw7
| Qu | Elv | |
|---|---|---|
| Base | req(), alloc() | alloc() |
| Elv | release() | go(), open(), close(), port()s |
调度器&线程交互
hw5
调度器仅负责把请求从主等待队列转储到电梯等待队列中，直接用synchronized块解决即可。
hw6
调度器负责把电梯“发射”至目标楼层，目标楼层可以是出现请求的楼层，也可以是约定好当没有可分配请求时应去往的停泊楼层。
调度器有主动入口和被动入口：新增请求时输入线程激活调度器，使用主动入口；电梯轿厢为空时调用调度方法，使用被动入口。
hw7
调度器每隔200ms扫描一遍等待队列，刷新每个请求分配的电梯号码，刷新每个电梯的目标楼层。依次trylock所有电梯，若成功则signal()。除sleep(200)外，调度器永不休眠，因而也不需要被唤醒。调度器给每个电梯设置目标楼层时赋值语句是原子语句，不需要加锁。
平衡&可拓展性
hw5
电梯自身调度是魔改的莫队算法，希望利用请求出现的局部性，优先在一段小区间里往返送人。人少的时候效果极差。类图中Rlist类是莫队实现的主要基础。在此基础上增加电梯非常容易，只要继承电梯类，并重写与停靠楼层、运行速度相关的方法即可，调度器也只需改为转储时向不同电梯写入请求即可。
性能：失败；可拓展性：良好。
hw6
使用共享等待队列，Rlist被弱化为仅包含判断方向是否相同、比较距离远近的静态方法。共享队列 + 调度器分配目标楼层 的架构兼具抢人和分配两种思路的优势，性能优秀。但共享队列带来了一些线程安全问题，其解决较复杂。由于调度时认为各电梯之间没有属性上的差异，因此增加电梯种类可能导致调度器出现较大改动。
性能：优秀；可拓展性：一般。
hw7
共享队列plus。调度器每隔200ms刷新一次，重新分配请求，设置每部电梯的目标楼层。每个请求增加权限部分，可以只允许指定电梯载客，考虑了每部电梯之间属性差异。通过删除调度器唤醒电梯以外的所有唤醒操作、删除与等待队列或电梯线程无关的所有临界区，成功杜绝了线程安全问题。实现了简单的换乘，但总体性能似乎没有不换乘好。
性能：较优秀；可拓展性：尚可。
bug
hw5
- 没有发现bug
hw6
-
没有互测中发现的bug
-
强测第9个点运行过慢的"bug"
-
特征：贪心算法在极端情况下失效
Class CogC ev(G) iv(G) v(G) Trans.nearq() 5 4 2 5 -
位置：Trans(调度器)类，nearq方法
-
修复：qu.size()>=6则改成裸的抢人
-
-
本地以1/30的频率稳定复现调度器唤醒电梯时被阻塞，导致电梯请求调度时发生死锁的bug。
-
特征：在需要系统原语的地方使用了两步判定
Class CogC ev(G) iv(G) v(G) Trans.run() 22 4 10 11 -
位置：Trans(调度器)类，run方法
-
修复：改用trylock()
-
hw7
-
print过于靠后的bug
-
特征：代码长度7，圈复杂度1
Class CogC Ev(G) iv(G) v(G) Elv.Stop.release() 1 1 2 2 -
位置：Elv(电梯类)->Stop子类，release方法
-
修复：print语句移到该方法第一行
-
-
分配时发生数组越界的bug
-
特征：未考虑参数在执行过程中被其他线程修改的情况
Class CogC ev(G) iv(G) v(G) Trans.run() 39 8 13 16 -
位置：Base(调度器)类，alloc方法
-
修复：cnt改为tmp.length
-
分析别人bug
- 测试策略
- 黑盒测试，一次运行30个子进程
- 有效性：模拟评测机运行情况，并发现了强测未发现bug
- 线程安全相关
- 所有测试数据均为随机生成，实际上由于线程安全问题的不确定性，我不认为手动构造有明显效果
- 同时运行多个测试进程，增大了线程安全问题出现的概率
- 与第一单元的差异
- 第一单元hack重心在于正确性判定，第二单元重心在于线程安全问题。
- 第一单元数据构造策略显著影响hack效率，需要用心构造高强度数据。
- 第二单元如何运行多进程，如何判定CTLE和RTLE，如何杀死TLE的死锁进程显著影响hack效率。