Loading AI tools
fetch-and-add是CPU指令（FAA），對內存位置執行增加一個數量的原子操作。具體內容為：
- 令x 變為x + a，其中x是個內存位置，a是個值
1991年，Maurice Herlihy證明fetch-and-add具有一個有限的consensus數，能解決不超過兩個並發進程的無等待consensus問題。[1]
下述偽代碼用ticket lock算法實現了互斥鎖：
record locktype {
int ticketnumber
int turn
}
procedure LockInit( locktype* lock ) {
lock.ticketnumber := 0
lock.turn := 0
}
procedure Lock( locktype* lock ) {
int myturn := FetchAndIncrement( &lock.ticketnumber ) //must be atomic, since many threads might ask for a lock at the same time
while lock.turn ≠ myturn
skip // spin until lock is acquired
}
procedure UnLock( locktype* lock ) {
FetchAndIncrement( &lock.turn ) //this need not be atomic, since only the possessor of the lock will execute this
}
從8086起，以內存為目的操作數的ADD指令就是fetch-and-add。如果使用LOCK前綴，那麼它對多處理器是原子操作。但不能返回原值，直至486引入XADD指令。
void __fastcall atomic_inc (volatile int* pNum)
{
__asm
{
lock inc dword ptr [ECX]
ret
}
}
下述GCC編譯的C語言函數，在x86的32位與64位平台上，使用擴展asm語法：
static inline int fetch_and_add(int* variable, int value)
{
__asm__ volatile("lock; xaddl %0, %1"
: "+r" (value), "+m" (*variable) // input+output
: // No input-only
: "memory"
);
return value;
}
- Test-and-set
- Test and Test-and-set
- Compare-and-swap
- Load-Link/Store-Conditional
Wikiwand in your browser!
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.
