检查并设置

在计算机科学中，检查并设置（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在总线流量与公平上较差。

另见

参考文献

  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. 

外部链接