在電腦科學中，檢查並設定（test-and-set-lock，TSL）是一種不可中斷的原子運算。TSL對某個記憶體位置寫入1（set）並返回其舊值。
 | 此條目可參照英語維基百科相應條目來擴充。 |
在多個行程可同時訪問記憶體同個位址時，如果一個程式正在執行TSL，其他程式在它執行完成前不能執行TSL。中央處理器可提供TSL指令，或利用如雙埠隨機存取記憶體（Dual-ported RAM）等其它電子元件所提供的機制實現TSL。
function Lock(boolean *lock) {
while (test_and_set (lock) == 1)
;
}
當舊值為 0 時，這程式可以得到鎖。否則的話，它會一直嘗試將 1 寫入記憶體位置，直到舊值為 0。
鎖(lock)的狀態一般是0(未鎖)與1(已鎖)。因此下列test_and_set的實現是等價的：
- if (lock==0) then 置鎖, 進入臨界區; else 忙等待, 重新測試; endif
- 讀取lock狀態; lock被置為1; 測試讀出的lock狀態，判斷進入臨界區還是忙等待;
x86組譯指令BTS，意味Bit Test and Set，就是一條原子操作的CPU指令。它把由運算元指定位址的鎖的狀態儲存入CF暫存器，然後鎖被設定為1.
1991年Maurice Herlihy證明test-and-set具有一個有限的consensus number，能解決不超過2個並行行程的無等待consensus問題。[2]
硬體實現
在雙埠記憶體中，可以有許多方式來實作這指令。其中列出兩種方式說明對於一個提供兩個埠的雙埠記憶體要如何允許二個不同的電子元件（如兩個中央處理器）存取記憶。
當處理器一要在某個記憶體位置引發執行TSL指令時，DPRAM先在特定主記憶體區域記下此位置，代表標上了一個 "內部記號"。如果處理器二在同一個位置引發了TSL指令，DPRAM會先檢查 "內部記號" ，若確認是時，則會產生一個 "忙碌" 的中斷以告訴處理器它須要等待後重試。這是一種利用中斷機制來實作忙等待或自旋鎖。因為這是發生在硬體層，處理器要等待的時間很短。
不管處理器二是否重試著存取這個記憶體位置，DPRAM完成了處理器一的測試。如果測試成功，記憶體會先此位置設成處理器一所指定的值。然後記憶體會清掉內部記號，此時，處理器二可以再次引發的檢查並設定，並能成功執行。
CPU 1發出test-and-set指令，表示寫回"主記憶體位置A"。DPRAM並不立即寫入主記憶體位置A，而是放到一個特殊暫存器中，並在主記憶體位置A設為"flag value"。
軟體實現TSL
某些CPU架構直接提供了test-and-set指令。如x86[3]與IBM System/360及其後繼(包括 z/Architecture)。[4]沒有這種機器指令的，需要用read-modify-write或 compare-and-swap指令來實現。
C語言實現：
#define LOCKED 1
int TestAndSet(int* lockPtr) {
int oldValue;
// Start of atomic segment
// The following statements should be interpreted as pseudocode for
// illustrative purposes only.
// Traditional compilation of this code will not guarantee atomicity, the
// use of shared memory (i.e. not-cached values), protection from compiler
// optimization, or other required properties.
oldValue = *lockPtr;
*lockPtr = LOCKED;
// End of atomic segment
return oldValue;
}
TSL實現互斥鎖
volatile int lock = 0;
void Critical() {
while (TestAndSet(&lock) == 1);
critical section // only one process can be in this section at a time
lock = 0 // release lock when finished with the critical section
}
enter_region: ; A "jump to" tag; function entry point.
tsl reg, flag ; Test and Set Lock; flag is the
; shared variable; it is copied
; into the register reg and flag
; then atomically set to 1.
cmp reg, #0 ; Was flag zero on entry_region?
jnz enter_region ; Jump to enter_region if
; reg is non-zero; i.e.,
; flag was non-zero on entry.
ret ; Exit; i.e., flag was zero on
; entry. If we get here, tsl
; will have set it non-zero; thus,
; we have claimed the resource
; associated with flag.
leave_region:
move flag, #0 ; store 0 in flag
ret ; return to caller
test-and-set鎖的效能評價
鎖的效能評價可分為四個方面：
- 無競爭地取得鎖的延遲（uncontended lock-acquisition latency）
- 匯流排流量（bus traffic）
- 公平
- 儲存[7]
Test-and-set在匯流排流量與公平上較差。
另見
- Fetch-and-add
- Test and test-and-set
- Load-link/store-conditional
- 比較並交換
參考文獻
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
