检查并设置
| 此條目可参照英語維基百科相應條目来扩充。 |
在計算機科學中，檢查並設置（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實現互斥鎖 编辑
伪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在总线流量与公平上较差。
另見 编辑
参考文献 编辑
- ^ 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）.
- ^ 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）.
- ^ BTS—Bit Test and Set. www.felixcloutier.com. [2016-11-21]. （原始内容存档于2016-12-22）.
- ^ IBM Knowledge Center. www.ibm.com. [2016-11-21]. （原始内容存档于2016-11-22）.
- ^ Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces 0.91. Arpaci-Dusseau Books. 2015 –通过http://www.ostep.org/.
- ^ Solihin, Yan. Fundamentals of parallel computer architecture : multichip and multicore systems. 2009: 252. ISBN 9780984163007.
- ^ 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 （页面存档备份，存于互联网档案馆）