가져오기 및 추가

Fetch-and-add

컴퓨터 과학에서 CPU 명령어(FAA)는 원자적으로 메모리 위치의 내용을 지정된 값만큼 증가시킨다.

즉, 가져오기 및 추가가 작업을 수행한다.

주소 x에서 값을 a로 증가시키고 여기서 x는 메모리 위치이고 a는 일부 값이며 x에서 원래 값을 반환한다.

이 작업이 동시 시스템에서 한 프로세스에 의해 실행될 경우 다른 프로세스는 중간 결과를 보지 못할 것이다.

가져오기와 추가는 뮤텍스 잠금장치세마포어와 같은 동시성 제어 구조를 구현하는 데 사용될 수 있다.

개요

원자핵 가져오기 및 추가 기능을 갖는 동기는 프로그래밍 언어에 다음과 같이 나타나는 연산이다.

x = x + a

여러 프로세스 또는 스레드가 동시에 실행되는 동시 시스템에서는 안전하지 않다(다중 프로세서 시스템에서 실행되거나 일부 단일 코어 시스템으로 사전 예약).그 이유는 다음과 같은 여러 기계 지침으로 실제로 그러한 조작이 실행되기 때문이다.

  1. x 위치old 값을 레지스터로 가져오십시오.
  2. 레지스터의 xaold 추가한다.
  3. 레지스터의 새 값을 x에 다시 저장한다.

공정이 x = x + a를 하고 다른 공정이 x = x + b를 동시에 하는 경우, 경주 조건이 있다.이들은 모두 xold 가져와 작업할 수 있으며, 그 다음 둘 다 다른 하나를 덮어쓰고 저장된 값이 예상대로old x + a 또는 x + b가 아닌 xold + a 또는 xold + b가 되는 효과로 결과를 저장할 수 있다.

커널 선점이 지원되지 않는 단일 프로세서 시스템에서는 중요한 섹션에 액세스하기 전에 인터럽트를 비활성화하는 것으로 충분하다.그러나 멀티프로세서 시스템(인터럽트가 비활성화된 경우에도)에서는 두 개 이상의 프로세서가 동시에 동일한 메모리에 액세스하려고 시도할 수 있다.가져오기 및 추가 명령을 사용하면 모든 프로세서가 원자적으로 메모리의 값을 증가시켜 이러한 다중 프로세서 충돌을 방지할 수 있다.

모리스 헐리히(1991)는 비교-스왑 작업과 대조적으로, 반입-추가 숫자가 유한하다는 을 증명했다.가져오기 및 추가 작업은 두 개 이하의 동시 프로세스에 대해 대기 없는 합의 문제를 해결할 수 있다.[1]

실행

가져오기 및 추가 명령은 다음과 같은 기능과 같이 동작한다.결정적으로, 전체 기능은 원자적으로 실행된다: 어떤 프로세스도 기능을 중간 실행 중에 중단할 수 없으며 따라서 기능 실행 중에만 존재하는 상태를 볼 수 있다.이 코드는 단지 반입과 추가의 행동을 설명하는 데 도움이 될 뿐이다. 원자성은 명시적인 하드웨어 지원을 필요로 하기 때문에 단순한 상위 수준의 함수로 구현될 수 없다.

<< atomic> 함수 FetchAdd(주소 위치, inc) { int값 := *location *위치 :=값 + inc 반환값}

상호 제외 잠금을 구현하기 위해 FetchAdd with inc=1과 동등한 FetchAddIncrement 작업을 정의한다.이 조작으로, 상호 배제 잠금은 다음과 같이 티켓 잠금 알고리즘을 사용하여 구현될 수 있다.

기록locktype{intticketnumber int 켜}절차 LockInit(locktype* 자물쇠){lock.ticketnumber:=0lock.turn:=0}절차 Lock(locktype* 자물쇠){int myturn:lock.turn≠myturn 스키부터 많은 실을 자물쇠를 동시에 물을 수도 있어요)FetchAndIncrement(&lock.ticketnumber)을 끓여, 원자야 한다.p//잠금 장치를 획득할 때까지 회전 } 절차 UnLock(locktype* lock) { PetchAndIncrement(&lock.turn) // 잠금 장치의 소유자만 이 절차를 실행할 수 있으므로 원자적일 필요는 없음 }

이러한 루틴은 다음 조건이 충족될 때 상호 배제 잠금을 제공한다.

  • Locktype 데이터 구조는 LockInit 기능으로 초기화 후 사용
  • 잠금 대기 중인 작업 수가 언제든지 INT_MAX를 초과하지 않음
  • 잠금 값에 사용되는 정수 데이터 형식이 계속 증가하면 '뒤집고 다닐 수 있음'

하드웨어 및 소프트웨어 지원

원자 petch_add 함수는 C++11 표준에 나타난다.[2]Itanium ABI 규격에서는 [3]C에 대한 독점적 확장으로, GCC에서는 (동일한 구문으로) 이용할 수 있다.[4]

x86 구현

x86 아키텍처에서 메모리 위치를 지정하는 목적지 피연산자가 명령 ADD는 8086년(그때는 그렇게 불리지 않았을 뿐), LOCK 접두사가 있는 명령어 Atomic이다.그러나 486이 XADD 명령을 도입할 때까지 메모리 위치의 원래 값(일부 플래그를 반환했음에도 불구하고)을 반환할 수 없었다.

다음은 확장 asm 구문을 기반으로 32비트 및 64비트 x86 Intel 플랫폼 모두에 대해 GCC 컴파일러를 위한 C 구현이다.

정태의 횡대로 인트로 fetch_and_add(인트로* 가변적, 인트로 가치를 매기다) {     __asm___ 휘발성이 있는("잠금; xaddl %0, %1"       : "+r" (가치를 매기다), "+m" (*가변적) // 입력 + 출력       : // 입력 전용 없음       : "기억"     );     돌아오다 가치를 매기다; } 

역사

Fetch-and-add는 Ultracomputer 프로젝트에 의해 도입되었는데, 이 프로젝트에서는 또한 Petch-and-adds를 지원하는 멀티프로세서를 생산하고 사용자 지정 VLSI 스위치를 포함하고, 동시 메모리 참조(Petch-and-adds 포함)를 결합하여 대상 피연산자가 포함된 메모리 모듈에서 직렬화를 방지할 수 있었다.

참고 항목

참조

  1. ^ Herlihy, Maurice (January 1991). "Wait-free synchronization" (PDF). ACM Trans. Program. Lang. Syst. 13 (1): 124–149. CiteSeerX 10.1.1.56.5659. doi:10.1145/114005.102808. Retrieved 2007-05-20.
  2. ^ "std::atomic::fetch_add". cppreference.com. Retrieved 1 June 2015.
  3. ^ "Intel Itanium Processor-specific Application Binary Interface (ABI)" (PDF). Intel Corporation. 2001.
  4. ^ "Atomic Builtins". Using the GNU Compiler Collection (GCC). Free Software Foundation. 2005.