檢查並設定

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

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

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

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（英語：Maurice Herlihy）證明test-and-set具有一個有限的consensus number（英語：consensus number），能解決不超過2個並行行程的無等待consensus（英語：Consensus (computer science)）問題。^[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實現互斥鎖

一種實現互斥鎖的辦法：^[5][6] 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）
• 公平
• 儲存^[7]

Test-and-set在匯流排流量與公平上較差。

另見

• Fetch-and-add
• Test and test-and-set（英語：Test and test-and-set）
• Load-link/store-conditional
• 比較並交換

參考文獻

1. Anderson, T. E. The performance of spin lock alternatives for shared-money multiprocessors. IEEE Transactions on Parallel and Distributed Systems. 1990-01-01, 1 (1): 6–16 [2020-09-11]. ISSN 1045-9219. doi:10.1109/71.80120. （原始內容存檔於2019-12-05）.
2. Herlihy, Maurice. Wait-free synchronization (PDF). ACM Trans. Program. Lang. Syst. January 1991, 13 (1): 124–149 [2007-05-20]. doi:10.1145/114005.102808. （原始內容存檔 (PDF)於2011-06-05）.
3. BTS—Bit Test and Set. www.felixcloutier.com. [2016-11-21]. （原始內容存檔於2016-12-22）.
4. IBM Knowledge Center. www.ibm.com. [2016-11-21]. （原始內容存檔於2016-11-22）.
5. Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces 0.91. Arpaci-Dusseau Books. 2015 –透過http://www.ostep.org/.
6. Solihin, Yan. Fundamentals of parallel computer architecture : multichip and multicore systems. 2009: 252. ISBN 9780984163007.
7. Solihin, Yan. Fundamentals of Parallel Architecture. Boca Raton, FL: CRC Press. 2016. ISBN 978-1-4822-1118-4.

外部連結

• 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 （頁面存檔備份，存於網際網路檔案館）