https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=Fetch-and-add
Fetch-and-add - 版本历史
2026-07-16T17:54:40Z
在这个wiki上该页的修订历史
MediaWiki 1.43.9
https://arolstar52-zhtest.hf.space/index.php?title=Fetch-and-add&diff=2976572&oldid=prev
imported>Jimmy-bot：机器人: 尚未清空的已重定向分类（Cat:協同控制→Cat:并发控制）
2023-12-05T02:21:41Z
<p>机器人: 尚未清空的已重定向分类（<a href="/index.php?title=Cat:%E5%8D%94%E5%90%8C%E6%8E%A7%E5%88%B6&action=edit&redlink=1" class="new" title="Cat:協同控制（页面不存在）">Cat:協同控制</a>→<a href="/index.php?title=Cat:%E5%B9%B6%E5%8F%91%E6%8E%A7%E5%88%B6&action=edit&redlink=1" class="new" title="Cat:并发控制（页面不存在）">Cat:并发控制</a>）</p>
<p><b>新页面</b></p><div>'''fetch-and-add'''是[[CPU]]指令（FAA），对内存位置执行增加一个数量的原子操作。具体内容为：<br />
:令{{mvar|x}} 变为{{math|''x'' + ''a''}}，其中{{mvar|x}}是个内存位置，{{mvar|a}}是个值<br />
<br />
FAA可用于实现[[互斥锁]]、[[信号量]]。<br />
<br />
1991年，{{tsl|en|Maurice Herlihy}}证明fetch-and-add具有一个有限的{{tsl|en|Consensus (computer science)|consensus (计算机科学)|consensus}}数，能解决不超过两个并发进程的无等待consensus问题。<ref>{{cite journal |last=Herlihy |first=Maurice |title=Wait-free synchronization |journal=ACM Trans. Program. Lang. Syst. |volume=13 |issue=1 |date=January 1991 |pages=124–149 |url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |accessdate=2007-05-20 |doi=10.1145/114005.102808 |archive-date=2011-06-05 |archive-url=https://web.archive.org/web/20110605003208/http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |dead-url=no }}</ref><br />
<br />
==用途==<br />
下述伪代码用[[ticket lock]]算法实现了互斥锁：<br />
<br />
'''record''' locktype {<br />
''int'' ticketnumber<br />
''int'' turn<br />
}<br />
'''procedure''' LockInit( ''locktype''* lock ) {<br />
lock.ticketnumber := 0<br />
lock.turn := 0<br />
}<br />
'''procedure''' Lock( ''locktype''* lock ) {<br />
''int'' myturn := FetchAndIncrement( &lock.ticketnumber ) //must be atomic, since many threads might ask for a lock at the same time<br />
'''while''' lock.turn ≠ myturn <br />
'''skip''' // ''spin until lock is acquired''<br />
}<br />
'''procedure''' UnLock( ''locktype''* lock ) {<br />
FetchAndIncrement( &lock.turn ) //this need not be atomic, since only the possessor of the lock will execute this<br />
}<br />
<br />
==硬件软件支持==<br />
[[C++11]]标准定义了原子的{{mono|fetch_add}}函数。<ref>{{cite web |title=std::atomic::fetch_add |website=cppreference.com |url=http://en.cppreference.com/w/cpp/atomic/atomic/fetch_add |accessdate=1 June 2015 |archive-date=2017-11-23 |archive-url=https://web.archive.org/web/20171123082739/http://en.cppreference.com/w/cpp/atomic/atomic/fetch_add |dead-url=no }}</ref> GCC把它作为对C语言的扩展。<ref>{{cite web |title=Atomic Builtins |website=Using the GNU Compiler Collection (GCC) |publisher=Free Software Foundation |year=2005 |url=https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html |accessdate=2017-11-22 |archive-date=2017-11-08 |archive-url=https://web.archive.org/web/20171108015543/http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html |dead-url=no }}</ref><br />
<br />
===x86实现===<br />
从[[8086]]起，以内存为目的操作数的ADD指令就是fetch-and-add。如果使用LOCK前缀，那么它对多处理器是原子操作。但不能返回原值，直至[[80486|486]]引入XADD指令。<br />
<syntaxhighlight lang="c"><br />
void __fastcall atomic_inc (volatile int* pNum)<br />
{<br />
__asm<br />
{<br />
lock inc dword ptr [ECX]<br />
ret<br />
}<br />
}<br />
</syntaxhighlight><br />
<br />
下述GCC编译的[[C语言]]函数，在x86的32位与64位平台上，使用扩展asm语法：<br />
<syntaxhighlight lang="c"><br />
static inline int fetch_and_add(int* variable, int value)<br />
{<br />
__asm__ volatile("lock; xaddl %0, %1"<br />
: "+r" (value), "+m" (*variable) // input+output<br />
: // No input-only<br />
: "memory"<br />
);<br />
return value;<br />
}<br />
</syntaxhighlight><br />
<br />
==参见==<br />
*[[Test-and-set]]<br />
*[[Test and Test-and-set]]<br />
*[[Compare-and-swap]]<br />
*[[Load-Link/Store-Conditional]]<br />
<br />
==参考文献==<br />
<references/><br />
<br />
[[Category:并发控制]]</div>
imported>Jimmy-bot