互斥演算法加上近端自轉：原則與實例演練

Abstract

在shared memory mutual exclusion algorithms中，免不了要busy waiting，為了減少shared memory contention，我們援用Mellor-Crummey and Scott之local spin概念，提出一種通用的方法（generic approach），一般在atomic read/write model下的mutual exclusion algorithms均可依此方法加上local spin機制，以Dijkstra’s、Knuth’s、Eisenburg-McGuire’s、Lamport’s bakery和Burns’ mutual exclusion algorithm為實例，透過safety property和progress property的證明，清楚分辨這些algorithms在trying region的結構之後，即可輕易加上local spin得到大幅降低shared memory contention的初步結果，再深入瞭解algorithms運作細節，若algorithm具備bounded waiting的性質，則可以再改進processes之互動而大幅降低remote memory access次數。

Gadi Taubenfeld提出local-spinning bakery mutual exclusion algorithm，我們嘗試引用相同的方式（使用2-dimensional permitted bits）為其它在atomic read/write model下的mutual exclusion algorithms加上local spin，利用tree的結構分析the generic approach與此方法之間的差異，並證明出此方法並不是所有的mutual exclusion algorithms都適用。

綜合實例演練的經驗，我們歸納出依據algorithm具備的性質較適合使用何種方式加上local spin機制，大致上可區分為兩大類：具有starvation狀況的algorithm適合使用2-dimensional permitted bits加上local spin；具備bounded waiting性質的algorithm適合the generic approach再加focused release的方式加上local spin。

Busy waiting is common in shared memory mutual exclusion algorithms. To reduce memory contention incurred by busy waiting, we follow the concept of local spin made popular by Mellor-Crummey and Scott and propose a generic approach for adding local spin to mutual exclusion algorithms of the atomic read/write model. Taking Dijkstra’s, Knuth’s, Eisenburg-McGuire’s, Lamport’s bakery and Burns’ mutual exclusion algorithm as examples, two levels of local spin version were obtained. The first is an easy product of the generic approach. The second, with better inter-process communication made possible by an in-depth understanding of the algorithm, e.g. bounded waiting, significantly reduces the number of remote memory accesses.

There is another approach used in Gadi Taubenfeld’s local-spinning bakery mutual exclusion algorithm by adding 2-dimensional permitted bits. We try this approach to add local spin to the other mutual exclusion algorithms of the atomic read/write model. We find out the difference between the generic approach and this approach by the tree structure. And this approach is not suitable for all mutual exclusion algorithms.

According to the experience of adding local spin, we divide mutual exclusion algorithms into two parts: the algorithms with starvation are suitable for using 2-dimensional permitted bits to add local spin; the algorithms with bounded waiting are suitable for the generic approach plus focused release to add local spin.