共用記憶體多處理機上可延申互斥演算法:設計,証明與實驗

Abstract

持續等待的互斥演算法,被稱為 spin locks,普遍被使用在共用記憶體多 處理機上執行的平行作業系統及應用程式中.目前 spin locks 的設計方 向是要具有下列特色:除去因等待引起的記憶體或內部連接網路上的競爭, 及每個 lock 需定量的記憶空間.我們提出兩個可延伸的演算法,一個用在 有一致性 caches 的機器上,另一個在有分散共用記憶體而無一致性 caches 的多處理機上.因每個程序持續等待不同的 locally-accesible的 變數上,而當自其他程序的一個寫的動作抵達時才停止等待,此等待期間不 引起記憶體或網路上的競爭.此二演算法每個 lock 均只需定量且少數的 記憶空間及保証不會有程序餓死的現象.免於餓死的演算法可能對於多程 式系統中的程序更換極為敏感.若一程序在等待期間被更換,可能造成既無 程序在臨界區中,且其他程序均需等此被作業系統更換掉的程序用過臨界 區後,才得以進入此臨界區.為了降低程序更換的影響,我們提出另一演算 法用在多程式系統中.我們在一台有一致性 caches 的共用記憶體多處理 機 Sequent Symmetry 上測量多種 spin locks 的效能. Busy-wait mutual-exclusion algorithms, called spin locks, are used in the implementation of parallel operation system and application programs on shared-memory multioprocessors. Current trend in design of spin locks is to have the following features: eliminating memory or interconnecion network contention caused by spinning, and a constant amount of memory space requirement per lock. We propose two scalable algorithms, one for cache- coherent machines, and the other for distributed shared-memory multiprocessors without coherent caches. Since every process spins on separate locally-accesible variables and terminates the spin when a remote write operation from some other process arrives, the spinning induces no memoory or interconnection network contention. The two algorithms both requires a small constant amount of space per lock and quarantee starvation freedom. Starvation free algorithms can be very sensitive to preemption in multiprogrammed systems. If a process is preempted during its spin, it may lead to a situation that other processes must wait for the preempted one to enter the critical section even though no one is in the critical section at that time. To reduce the impact of preemption sensitively, we present another algorithm for multiprogrammed systems. We have measured time efficiency for a variety of spin locks on a Sequeny Symmetry, a shared-memory multiprocessor with coherent caches.