检查并设置

在计算机科学中，检查并设置（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的实现是等价的：

- 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 (计算机科学)问题。

## 硬件实现

在双埠内存中，可以有许多方式来实作这指令。其中列出两种方式说明对于一个提供两个埠的双埠内存要如何允许二个不同的电子元件（如两个中央处理器）存取记忆。

### 方法一

当处理器一要在某个内存位置引发执行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语言实现：

```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实现

```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
 }
```

### 汇编实现

```nasm
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