檢查並設置

在計算機科學中，檢查並設置（test-and-set-lock，TSL）是一種不可中斷的原子運算。TSL對某個記憶體位置寫入1（set）並返回其舊值。

在多個進程可同時訪問記憶體同個地址時，如果一個程式正在執行TSL，其他程式在它執行完成前不能執行TSL。中央處理器可提供TSL指令，或利用如雙埠隨機存取記憶體（Dual-ported RAM）等其它電子元件所提供的機制實現TSL。

下述為一種利用TSL指令來實現自旋鎖：

function Lock(boolean *lock) {
    while (test_and_set (lock) == 1)
      ;
}

當舊值為 0 時，這程序可以得到鎖。否則的話，它會一直嘗試將 1 寫入記憶體位置，直到舊值為 0。

鎖(lock)的狀態一般是0(未鎖)與1(已鎖)。因此下列test_and_set的實現是等價的：

1. if (lock==0) then 置鎖, 進入臨界區; else 忙等待, 重新測試; endif
2. 讀取lock狀態; lock被置為1; 測試讀出的lock狀態，判斷進入臨界區還是忙等待;

x86匯編指令BTS，意味Bit Test and Set，就是一條原子操作的CPU指令。它把由操作數指定地址的鎖的狀態保存入CF寄存器，然後鎖被設置為1.

1991年Maurice Herlihy證明test-and-set具有一個有限的consensus number，能解決不超過2個並發進程的無等待consensus問題。

硬體實現

在雙埠記憶體中，可以有許多方式來實作這指令。其中列出兩種方式說明對於一個提供兩個埠的雙埠記憶體要如何允許二個不同的電子元件（如兩個中央處理器）存取記憶。

方法一

當處理器一要在某個記憶體位置引發執行TSL指令時，DPRAM先在特定內存區域記下此位置，代表標上了一個 "內部記號"。如果處理器二在同一個位置引發了TSL指令，DPRAM會先檢查 "內部記號" ，若確認是時，則會產生一個 "忙碌" 的中斷以告訴處理器它須要等待後重試。這是一種利用中斷機制來實作忙等待或自旋鎖。因為這是發生在硬體層，處理器要等待的時間很短。

不管處理器二是否重試著存取這個記憶體位置，DPRAM完成了處理器一的測試。如果測試成功，記憶體會先此位置設成處理器一所指定的值。然後記憶體會清掉內部記號，此時，處理器二可以再次引發的檢查並設置，並能成功執行。

方法二

CPU 1發出test-and-set指令，表示寫回"內存位置A"。DPRAM並不立即寫入內存位置A，而是放到一個特殊寄存器中，並在內存位置A設為"flag value"。

軟體實現TSL

某些CPU架構直接提供了test-and-set指令。如x86與IBM System/360及其後繼(包括 z/Architecture)。沒有這種機器指令的，需要用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實現互斥鎖

一種實現互斥鎖的辦法： as follows:

偽C實現

 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）
• 公平
• 存儲

Test-and-set在總線流量與公平上較差。

另見

• Fetch-and-add
• Test and test-and-set
• Load-link/store-conditional
• 比較並交換

外部連結

• Description （頁面存檔備份，存於網際網路檔案館） from Encyclopaedia of Delay-Insensitive Systems
• "Wait-free Test-and-Set （頁面存檔備份，存於網際網路檔案館）" by Yehuda Afek
• int testandset(int *lock) （頁面存檔備份，存於網際網路檔案館） - C-callable routine written in Sun SPARC assembly language
• Intel Developer Manual （頁面存檔備份，存於網際網路檔案館）