|
In computer science, the fetch-and-add CPU instruction that atomically modifies the contents of a memory location. That is, fetch-and-add performs the operation :set to , where is a memory location and is some value, in such a way that if this operation is executed by one process in a concurrent system, noother process will ever see an intermediate result. Fetch-and-add can be used to implement concurrency control structures such as mutex locks and semaphores. ==Overview== The motivation for having an atomic fetch-and-add is that operations that appear in programming languages as : are not safe in a concurrent system, where multiple processes or threads are running concurrently (either in a multi-processor system, or preemptively scheduled onto a single processor). The reason is that such an operation is actually implemented as multiple machine instructions: # Fetch the value at the location , say , into a register; # add to in the register; # store the new value of the register back into . When one process is doing and another is doing concurrently, there is a race condition. The might both fetch and operate on that, then both store their results with the effect that one overwrites the other and the stored value becomes either or , not as might be expected. In uniprocessor systems with no kernel preemption supported, it is sufficient to disable interrupts before accessing a critical section. However, in multiprocessor systems (even with interrupts disabled) two or more processors could be attempting to access the same memory at the same time. The fetch-and-add instruction allows any processor to atomically increment a value in memory, preventing such multiple processor collisions. Maurice Herlihy (1991) proved that fetch-and-add has a finite consensus number, in contrast to the compare-and-swap operation. The fetch-and-add operation can solve the wait-free consensus problem for no more than two concurrent processes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fetch-and-add」の詳細全文を読む スポンサード リンク
|