跳转到内容

Szymanski算法

维基百科,自由的百科全书

Szymanski算法是解决多个线程并发访问一个共享资源的互斥问题的一个算法。由Boleslaw Szymanski于1988年提出。[1][2][3]该算法具有很多优良性能,如线性等待,解决了由Leslie Lamport提出的开问题[4]

算法的类比解释

该算法可以用等候室(waiting room)做一个直观地类比。等候室有一个入口门与一个出口门。起初,入口门是打开的。所有想要进入临界区的线程在差不多同一时间由入口进入等候室。最后一个进入的线程负责关闭进口门。然后在等候室的线程根据优先级高低依次进入临界区。最后退出临界区的线程负责打开入口门。

算法的实现

每个线程有一个flag变量表示该线程所处的状态。规定其含义为:

  • 0: 在外面,未申请访问临界区
  • 1: 在入口门外等待
  • 2: 在入口门内等待其它提出申请的进程都进入入口门
  • 3: 正在进入入口门
  • 4: 入口门关闭,在等候室里等待进入临界区,或正在访问临界区

可以把这些flag变量表示为一个数组,共有n个元素。每个进程只写属于自己的flag数组元素,只读取其它线程的flag数组元素。这种“单独写”策略有助于提高cache性能。入口门的状态由所有的flag变量共同确定。

算法的伪代码实现:

#进入临界区的协议:
flag[self]  1                    #站在入口门外,申请进入等候室
await_until(all flag[1..N]  {0, 1, 2}) #等待入口门打开。即不存在有进程处于3、4状态,包括正在进门、正在使用临界区
flag[self]  3                    #站在入口门处,即正在进入。
if any flag[1..N] = 1:            #如果还有在入口门外等待进入的线程
    flag[self]  2                #把自己置为在入口门内,等待所有提出申请的线程都完成进入等候室
    await_until(any flag[1..N] = 4)     #等待最后进门的线程关闭入口门

flag[self]  4                    #门处于关闭状态,线程在等候室
await_until(all flag[1..self-1]  {0, 1})   #等待所有具有更高优先级的线程访问完临界区,退出等候室

#这里是临界区
#...

#退出临界区的协议
await_until(all flag[self+1..N]  {0, 1, 4}) #确保所有比自己优先级低的已经通过入口门的线程都进入了等候室
flag[self]  0 #离开等候室,如果自己是最后离开的,则入口门被打开

上述伪代码中的"all"与"any"分别表示"所有"与"存在".

该算法容易直观理解其正确性。但是其正确性的形式验证比较难。一些文献给出了形式验证[2][5].

参考文献

  1. ^ Szymanski, Boleslaw K. A simple solution to Lamport's concurrent programming problem with linear wait. ICS '88: Proceedings of the 2nd international conference on Supercomputing (St. Malo, France: ACM). 1988: 621–626. ISBN 0-89791-272-1. doi:10.1145/55364.55425. 
  2. ^ 2.0 2.1 Manna, Zohar; Pnueli, Amir. An Exercise in Verification of Multi-Process Programs.. Beauty is Our Business: A Birthday Salute to Edsger W. Dijkstra. Springer Verlag. 1990: 289–301. ISBN 978-0-387-97299-2. 
  3. ^ Szymanski, Boleslaw. Mutual Exclusion Revisited (PDF). Fifth Jerusalem Conference on Information Technology (Jerusalem, Israel). 1990: 110–117 [2012-09-02]. (原始内容 (PDF)存档于2012-10-29). 
  4. ^ Lamport, Leslie. The mutual exclusion problem: partII—statement and solutions. Journal of the ACM (ACM). 1986, 33 (2): 327–348. doi:10.1145/5383.5385. 
  5. ^ de Roever, Willem-Paul; de Boer, Frank; Hannemann, Ulrich; Hooman, Jozef; Lakhnech, Yassine; Poel, Mannes; Zwiers, Job. Concurrency Verification. Number 54 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press. November 2002. ISBN 978-0-521-80608-4. doi:10.2277/0521806089. 

参见