void MPE_Mutex_lock_simple(MPI_Win win) { int value; MPE_Counter_inc_simple(win, &value, 1); while (value != 0) { MPE_Counter_inc_simple(win, &value, -1); MPE_Counter_inc_simple(win, &value, 1); } } void MPE_Mutex_unlock_simple(MPI_Win win) { int value; MPE_Counter_inc_simple(win, &value, -1); }以上代码有严重的效率问题2. 在进程数多了以后, 计数器的期望在进程数一半 处,只有非常小的概率在零附近, 从而使各进程不断的在
while 循环里. 简单 的加一个计数器是否大于零的测试再尝试加一, 减一的循环应该可以减少在 =while=循环里的进程数, 从而使计数器的值有较大概率在零附近.class comm_mutex { public: comm_mutex(Comm &comm) : m_counter(comm) { } void lock() { while (m_counter.add(1) > 1) { if (m_counter.add(-1) > 0) { while (m_counter.get() > 0); } } } void unlock() { m_counter.add(-1); } private: comm_counter m_counter; };分析两种实现的效率, 即 $n$ 个进程同时加锁, 马上释放, 给出计数器
add, get 的效率后, 估算两种实现从第一个进程进锁, 到最后一个进程离锁的时间. 为简化, 我们假设各 add,get 的时间是固定的, 不随计数器的访问进程数 变化, 且进一步假设 get 的时间和 add 一样. 我们还假设计数器的互斥访 问是随机的. 最后, 我们需要看, 到最后一个进程释放锁时, 访问计数器的总次 数.在第一个片段里, 标记程序在
unlock 里减一前为状态 L, 减一后, 为状态 R. 在 lock 里, 加一前为状态 A, 减一前为状态 S. 分别以 $l, r, a, s$ 记 某一时刻在某一状态的程序数目. 计数器的值为 $l + s$, 且 $l$ 只能为 0 或 1. 可以容易得到程序集从状态 $(l, r, a, s)$ 进一次计数器变换到另一个 状态的概率. 如从 $(l, r, a, s)$ 到 $(l, r, a + 1, s - 1)$ 的概率为 $\frac{s}{l + a + s}$.问题即是, 程序集从状态 $(0, 0, n, 0)$ 到状态 $(0, n, 0, 0)$ 的转移次数 的期望. 有转移概率, 即可在程序上求此数值, 但表达形式应该比较复杂, 不知 道极限有没有简单的形式. 从 $s$ 的期望近似为 $\frac{n - r}{2}$ 看, 转移 次数期望有关于 $n$ 的指数下限. 实测时, 在进程数到 $32$ 后, 普遍会在释放 一两个锁后, 僵锁在加一, 减一的循环里.
第二个片段类似. 标记程序在
unlock 里减一前为状态 L, 减一后, 为状态 R. 在 lock 里, 加一前为状态 A, 减一前为状态 S, get 前为状态 G, 分别 以 $l, r, a, s, g$ 记某一时刻在某一状态的程序数目. 问题变成程序集从状态 $(0, 0, n, 0, 0)$ 到状态 $(0, n, 0, 0, 0)$ 的转移次数的期望.$s$ 大后, 多数程序会转移到状态 G, 从而 $s$ 的期望为一个比较小的常数,从 而每次进锁的程序只需要常数次测试, 如是, 转移次数期望应有上限 $O(n^2)$. 实测显示, 第 $i$ 个进锁的进程大概需要 $3i$ 次
add, get, 与前一个的差为常值 $3$.用类似的方式, 可实现读写锁, 最简单的是加一个计数器. 在加读锁时, 按上面 方式, 加一, 减一循环, 使写锁计数器到一, 加读计数器, 减写锁计数器; 在加 写锁时, 使写锁计数器到一, 自旋至读计数器为零.
Footnotes:
2 我没找到非 simple 版的
MPE_Mutex_lock.
3 blogger 似乎不支持使用 Content-ID 资源的HTML邮件, 只得取消了 latex 图片展示.
No comments:
Post a Comment