Loading AI tools
来自维基百科,自由的百科全书
在計算機科學中,檢查並設置(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的实现是等价的:
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"。
某些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;
}
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在总线流量与公平上较差。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.