book · system semaphore · 2015-01-18 · yuex

最近断断续续地在看一本非常棒的书,Allen B. Downey 的 The Little Book of Semaphores,理清了许多以前了解得不很确实的知识。

这两天看到的书中 3.7 节的 Exclusive Queue。书中介绍了一个可以 1:1 并发向前的队列。一个很自然的想法是如何将其推广到 n:m 的情形。但非常奇怪的是书中并没有像前几节中推广二人约定 Rendezvous1,使之成为多人约定 Barrier 那样,将 1:1 的 Exclusive Queue 推广到 n:m。所以我在这篇拙文中斗胆狗尾续貂,补上这个推广 2

首先,和书中之前的定义一样,n:m 情形下,要求有且仅有 n 个 leader 和 m 个 follower 同时进行 dance()。变量定义如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
n = number of leaders to proceed
m = number of followers to proceed
leader = follower = 0   # 用于记录已经到达的 leader 与 follower 个数 
countL = countF = 0     # 用于记录正在进行 dance() 的 leader 与 follower 个数 
mutex = Semaphore(1)    # 用于控制 leader 和 follower 的访问 
mutexCountL = Semaphore(1)  # 用于控制 countL 的访问 
mutexCountF = Semaphore(1)  # 用于控制 countF 的访问 
leaderQ = Semaphore(0)      # 用于 fire leader queue
followerQ = Semaphore(0)    # 用于 fire follower queue
rendezvous = Semaphore(0)   # 用于控制 leader 和 follower 的同步约定 

以下给出推广问题解的 leader 的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
mutex.wait()
if follower >= m and leader >= n-1:
    follower -= m
    leader -= n-1
    followerQ.signal(m)
    leaderQ.signal(n-1)
else:
    leader += 1
    mutex.signal()
    leaderQ.wait()

dance()
rendezvous.wait()

mutexCountL.wait()
countL += 1
if countL == n:
    countL = 0
    mutex.signal()
mutexCountL.singal()

以下给出推广问题解的 follower 的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
mutex.wait()
if leader >= n and follower >= m-1:
    leader -= n
    follower -= m-1
    leaderQ.signal(n)
    followerQ.signal(m-1)
else:
    follower += 1
    mutex.signal()
    followerQ.wait()

dance()

mutexCountF.wait()
countF += 1
if countF == m:
    countF = 0
    rendezvous.signal(n)
mutexCountF.singal()

代码,以上。

不过请注意,这里的 n 个 leader 只有在 m 个 follower 全部完成 dance() 之后,才能开始进行第一个 dance()。在 n == m 的情况下,或者更广泛一点讲,只要 n 和 m 互为整倍数关系时,可以有一个改进,使得固定的一个或几个 follower 完成 dance() 之后,就 fire 成比例的 rendezvous 给 leader。这样 follower 和 leader 就可以一定程度上的并发行进了。

拙文,以上。


  1. rendezvous 的词源是 render (to present) + vous (you),引申为约会、约会地、集会地。具体可以参考 etymonline 

  2. 书还没有看完,我怀疑书后面的章节中可能会有问题涉及到这个推广,所以在书的前面也就没有提及。倘若真是这种情况,之后再补上相关的说明。