检查并设置
 | 此条目可参照英语维基百科相应条目来扩充。 |
在计算机科学中，检查并设置（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 （页面存档备份，存于互联网档案馆）