检查并设置

维基百科,自由的百科全书
跳转至: 导航搜索

計算機科學檢查並設置是一種不可中斷的基本(原子)運算。它會寫值到某個記憶體位置並傳回其舊值。在多程序可同時存取記憶體的情況下,如果一個程式正在執行檢查並設置,在它執行完成前,其它的程式不可以執行檢查並設置。中央處理器可使用可自行實作此指令,或利用其它電子元件如雙埠記憶體(Dual-ported RAM)所提供的檢查並設置機制。

以下則展示一種利用檢查並設置指令來實現的鎖:

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.

en:Maurice Herlihy (1991) proved that test-and-set has a finite en:consensus number, in contrast to the en:compare-and-swap operation. The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes.[1] However, more than two decades before Herlihy's proof, IBM had already replaced Test-and-set by Compare-and-swap, which is a more general solution to this problem. Ultimately, IBM would release a processor family with 12 processors, whereas Amdahl would release a processor family with the architectural maximum of 16 processors.

硬體實現[编辑]

在雙埠記憶體中,可以有許多方式來實作這指令。其中列出兩種方式說明對於一個提供兩個埠的雙埠記憶體要如何允許二個不同的電子元件(如兩個中央處理器)存取記憶。

方法一[编辑]

當處理器一要在某個記憶體位置引發執行檢查並設置指令時,記憶體會先在另一個記憶體中的特定區域先記下此位置,代表標上了一個 "內部記號"。如果處理器二在同一個位置引發了檢查並設置指令,記憶體會先檢查 "內部記號" ,若確認是時,則會產生一個 "忙碌" 的中斷以告訴處理器它須要等待後重試。這是一種利用中斷機制來實作en:busy waitingen:spinlock的方式。因為這是發生在硬體層,處理器要等待的時間很短。

不管處理器二是否重試著存取這個記憶體位置,記憶體完成了處理器一的測試。如果測試成功,記憶體會先此位置設成處理器一所指定的值。然後記憶體會清掉內部記號,此時,處理器二可以再次引發的檢查並設置,並能成功執行。

方法二[编辑]

軟體實現檢查並設置[编辑]

以檢查並設置實現互斥鎖[编辑]

硬體實作檢查並設置[编辑]

以檢查並設置實作旗號[编辑]

另見[编辑]

參考[编辑]

  1. ^ Herlihy, Maurice. Wait-free synchronization. ACM Trans. Program. Lang. Syst. January, 1991, 13 (1): 124–149 [2007-05-20]. doi:10.1145/114005.102808. 

外部連結[编辑]