비교 및 스왑

Compare-and-swap

컴퓨터 과학에서 CAS(compare-and-swap)는 동기화를 달성하기 위해 멀티스레딩에서 사용되는 원자 명령입니다.메모리 로케이션의 내용을 소정의 값과 비교하고, 그것들이 같은 경우에만, 그 메모리 로케이션의 내용을 변경합니다.이것은 단일 원자 연산으로 이루어집니다.원자성을 통해 최신 정보를 기반으로 새 값이 계산됩니다. 그 사이에 다른 스레드에 의해 값이 업데이트되면 쓰기가 실패합니다.연산 결과는 치환을 실행했는지 여부를 나타내야 합니다.이는 단순한 부울 응답(이 변형은 종종 비교 세트라고 불린다) 또는 메모리 위치에서 읽은 값(기입된 값이 아님)을 반환함으로써 수행할 수 있습니다.

개요

비교 및 스왑 동작은 다음 의사 코드의 원자 버전입니다.*[1]는 포인터를 통한 액세스를 나타냅니다. 

함수 cas(p: int, old: int, new: int)는 *p ≠ old old return false *p ← new return true인 경우입니다.

이 작업은 세마포어나 뮤텍스 [1]등의 동기화 프리미티브와 보다 정교한 잠금 및 대기 없는 알고리즘을 구현하기 위해 사용됩니다.Maurice Herlihy(1991)는 CAS가 원자적인 읽기, 쓰기 또는 fetch-and-add보다 더 많은 알고리즘을 구현할 수 있다는 것을 증명하고 상당히 많은[clarification needed] 양의 메모리를 가정하면 CAS가 [2]이들 알고리즘을 모두 구현할 수 있다는 것을 증명했습니다.CAS는 로드링크/스토어 조건부와 동등합니다.즉, 어느 한쪽의 프리미티브 호출을 일정 횟수로 사용하여 다른 한쪽을 대기 [3]없이 구현할 수 있습니다.

CAS를 중심으로 구축된 알고리즘은 일반적으로 몇 가지 중요한 메모리 위치를 읽고 오래된 값을 기억합니다.이 오래된 값을 바탕으로 새로운 값을 계산합니다.그런 다음 CAS를 사용하여 새로운 값을 스왑하려고 합니다.CAS에서는 이전 값과 동일한 로케이션을 비교하고 있습니다.CAS가 시행이 실패했음을 나타내는 경우 처음부터 반복해야 합니다.로케이션을 재읽고 새로운 값을 재계산하여 CAS를 재시도합니다.CAS 조작이 실패한 후 즉시 재시도하는 것이 아니라 멀티프로세서시스템(많은 스레드가 특정 공유 변수를 항상 갱신하는 경우)에서 CAS 장애가 발생한 스레드가 지수 백오프를 사용하는 경우, 즉 CAS를 [4]재시도하기 전에 잠시 기다려 주십시오.

응용 프로그램 예: atomic adder

비교 및 스왑의 사용 예로서 정수를 원자적으로 증가 또는 감소시키는 알고리즘을 다음에 나타냅니다.이는 카운터를 사용하는 다양한 애플리케이션에서 유용합니다.add 함수는 *p ← *p + a(C와 같이 *로 포인터 방향 지정을 나타냄) 작업을 수행하고 카운터에 저장된 최종 값을 반환합니다.위의 cas 의사 코드와는 달리 cas를 제외한 모든 동작 시퀀스가 atomic이라는 요건은 없습니다. 

함수 add(p: pointer to int, a: int)는 int done ← false while done value ← *p // 이 작업도 atomic. done ← cas(p, value, value + a) 반환값 + a를 반환합니다.

이 알고리즘에서는 *p의 값이 Import 후(또는 while!) 및 CAS가 스토어를 실행하기 전에 변경되면 CAS는 이 사실을 인식하고 보고하고 알고리즘의 [5]재시도를 일으킵니다.

ABA 문제

주요 기사: ABA 문제

일부 CAS 기반 알고리즘은 잘못된 양의 일치 또는 ABA 문제의 영향을 받기 때문에 처리해야 합니다.오래된 값을 읽을 때부터 CAS를 시도할 때까지 일부 다른 프로세서 또는 스레드가 메모리 위치를 2회 이상 변경하여 오래된 값과 일치하는 비트 패턴을 얻을 수 있습니다.이 문제는 오래된 값과 완전히 동일한 이 새로운 비트패턴에 다른 의미가 있는 경우 발생합니다.예를 들어 재활용 주소나 랩된 버전카운터일 수 있습니다.

이에 대한 일반적인 해결책은 Double-Length CAS(DCAS; 더블렝스 CAS)를 사용하는 것입니다.예를 들어 32비트 시스템에서는 64비트 CAS를 사용할 수 있습니다.후반부는 카운터를 잡는데 사용됩니다.조작의 비교 부분에서는 포인터 및 카운터의 이전에 읽은 값을 현재 포인터 및 카운터와 비교합니다.일치하는 경우 스왑이 발생하며 새 값이 기록되지만 새 값에는 증분 카운터가 있습니다.즉, ABA가 발생한 경우 포인터 값은 동일하지만 카운터가 동일할 가능성은 매우 낮습니다(32비트 값의 경우 2회분의32 연산이 발생하여 카운터가 랩되고 그 시점에서는 포인터 값도 우연히 같아야 합니다).

또 하나의 형태(DCAS가 없는 CPU에서 유용)는 풀 포인터가 아닌 프리리스트에 인덱스를 사용하는 것입니다(예를 들어 32비트 CAS에서는 16비트인덱스와 16비트카운터를 사용합니다).단, 카운터 길이가 감소함에 따라 최신 CPU 속도에서 ABA가 가능해지기 시작합니다.

이 문제를 완화하는 간단한 방법 중 하나는 데이터 구조 전체에 대해 단일 ABA 카운터를 사용하는 것이 아니라 각 데이터 구조 요소에 ABA 카운터를 저장하는 것입니다.

보다 복잡하지만 효과적인 솔루션은 안전한 메모리 회수(SMR)를 구현하는 것입니다.이는 사실상 잠금 없는 가비지 컬렉션입니다.SMR을 사용하는 이점은 데이터 구조에서 특정 포인터가 한 번에 한 번만 존재함을 보증하기 때문에 ABA 문제는 완전히 해결됩니다.(SMR을 사용하지 않으면 프리리스트와 같은 기능을 사용하여 데이터 요소가 존재하지 않아도 안전하게 액세스(메모리 액세스 위반이 발생하지 않음)할 수 있습니다.e 데이터 구조SMR을 사용하면 현재 데이터 구조 내에 있는 요소만 액세스할 수 있습니다.)

비용과 이점

명령 시퀀스의 원자성은 명령 실행 중에 인터럽트를 디세블로 함으로써 실현될 수 있기 때문에 CAS 및 기타 원자 명령어는 단프로세서시스템에서는 불필요하다고 생각되는 경우가 있습니다.단, 인터럽트를 디세블로 하면 여러 단점이 있습니다.예를 들어, 그렇게 할 수 있는 코드는 악성코드가 아니라 CPU를 독점하고 있으며, 정확하고 실수로 머신을 무한 루프 또는 페이지 장애로 행하지 않도록 신뢰해야 합니다.또, 인터럽트를 무효로 하는 것은, 비용이 너무 많이 들어 실용적이지 않다고 생각되는 경우가 많습니다.따라서 Linux의 futex의 경우처럼 단일 프로세서 기계에서만 실행되는 프로그램도 원자 명령의 혜택을 받을 수 있습니다.

멀티프로세서 시스템에서는 보통 모든 프로세서에서 인터럽트를 동시에 디세블로 할 수 없습니다.그것이 가능하더라도, 두 개 이상의 프로세서가 동시에 같은 세마포의 메모리에 액세스하려고 시도할 수 있기 때문에 원자성은 달성되지 않습니다.비교 및 스왑 명령을 사용하면 프로세서가 메모리 위치를 원자적으로 테스트하고 수정할 수 있으므로 이러한 다중 프로세서의 충돌을 방지할 수 있습니다.

2010년대 서버급 멀티프로세서 아키텍처에서는 캐시에서 처리되지 않는 단순한 로드에 비해 비교 및 스왑이 저렴합니다.2013년의 한 논문에서 CAS는 캐시되지 않은 인텔 Xeon(Westmere-EX)의 1.15배, AMD Opteron(Magny-Cours)[6]의 1.35배에 불과하다고 지적하고 있습니다.

실장

비교 및 스왑(및 비교 및 스왑-더블)은 1970년부터 IBM 370(및 모든 후속 제품) 아키텍처에서 필수적인 부분이 되었습니다.이러한 아키텍처에서 실행되는 운영 체제는 이 명령을 광범위하게 사용하여 프로세스(시스템 및 사용자 작업)와 프로세서(중앙 프로세서) 병렬 처리를 용이하게 하는 동시에 이전 IBM 운영 체제에서 사용되었던 "비활성화된 스핀록"을 최대한 제거합니다.마찬가지로, 테스트와 세트의 사용도 없어졌습니다.이러한 운영 체제에서는 단일 비교 및 스왑 명령을 실행함으로써 글로벌 서비스 우선 순위 목록 또는 로컬 서비스 우선 순위 목록으로 "전역적으로" 새로운 작업 단위를 인스턴스화할 수 있습니다.이것에 의해, 이러한 operating system의 응답성이 큰폭으로 향상했습니다.

x86(80486 이후) 및 Itanium 아키텍처에서는 비교 및 교환(CMPXCHG) 명령으로 구현됩니다(멀티프로세서에서는 LOCK 프리픽스를 사용해야 합니다).

2013년 현재 대부분의 멀티프로세서 아키텍처는 하드웨어에서 CAS를 지원하며 비교 및 스왑 조작은 잠금 기반 및 논블로킹 동시 데이터 구조를 [4]구현하기 위한 가장 일반적인 동기화 프리미티브입니다.

Linux 커널의 아토믹카운터와 아토믹비트마스크 조작은 일반적으로 비교 및 스왑 명령을 사용합니다.SPARC-V8 및 PA-RISC 아키텍처는 하드웨어에서 CAS를 지원하지 않는 최근 몇 안 되는 아키텍처 중2개입니다이러한 아키텍처에 대한 Linux 포트에는 스핀록이 [7]사용됩니다.

C에서의 실장

많은 C 컴파일러가 C11과의 비교 및 스왑을 지원하고 있습니다. <stdatomic.h>함수 또는 특정 [9]C 컴파일러의 일부 [8]비표준 C 확장자를 사용하거나 비교 및 스왑 명령을 사용하여 어셈블리 언어로 작성된 함수를 직접 호출합니다.

다음 C 함수는 지정된 메모리 위치의 오래된 값을 반환하는 비교 및 스왑 배리언트의 기본 동작을 나타냅니다.다만, 이 버전에서는, 실제의 비교 및 스왑 조작에 의한 중요한 원자성의 보장은 제공되지 않습니다.

인트 compare_and_displicate(비교(인트* 조정하다, 인트 구식, 인트 신개념) {     아토믹();     인트 old_reg_val = *조정하다;     한다면 (old_reg_val == 구식)         *조정하다 = 신개념;     엔드_ATOMIC();     돌아가다 old_reg_val; }

old_reg_val항상 반환되지만 다음 순서로 테스트할 수 있습니다.compare_and_swap일치하는지 확인하기 위한 조작oldval다를 수 있지만, 이는 다른 프로세스가 경쟁 제품에서 성공적으로 성공했음을 의미합니다.compare_and_swap등록 값을 에서 바꾸다oldval.

예를 들어, 선거 프로토콜은 모든 프로세스가 다음 결과를 확인하도록 구현될 수 있습니다.compare_and_swap자체 PID(= newval)를 기준으로 합니다.우승 프로세스에서는compare_and_swap초기 비 PID 값(예: 0)을 반환합니다.패자는 이긴 PID를 반환한다. 

부울 compare_and_displicate(비교(인트 *축적하다, 인트 *증류, 인트 신개념) {     한다면 (*축적하다 == *증류) {         *증류 = 신개념;         돌아가다 진실의;     } 또 다른 {         *축적하다 = *증류;         돌아가다 거짓의;     } }

이것은 인텔 소프트웨어 매뉴얼 Vol 2A의 논리입니다.

내선번호

CAS는 단일 포인터 크기의 메모리 위치 상에서 동작하기 때문에 대부분의 잠금프리 알고리즘과 대기프리 알고리즘은 여러 위치를 변경해야 하지만 몇 가지 확장이 구현되어 있습니다.

이중 비교 및 스왑(DCAS)
관련이 없는 두 개의 메모리 위치를 두 개의 예상 값과 비교하고, 이 값이 같을 경우 두 위치를 새 값으로 설정합니다.DCAS를 복수의 (인접하지 않는) 워드로 일반화하는 것을 MCAS 또는 CASN이라고 부릅니다.DCAS 및 MCAS는 디큐 또는 바이너리 검색 [10][11]트리 등의 데이터 구조를 사용하기 쉬운(동시에) 실장하는 데 실질적으로 도움이 됩니다.DCAS 및 MCAS는 IBM POWER8 등의 최신 프로세서나 트랜잭션 동기 확장(TSX)을 지원하는 인텔 프로세서에 탑재된 보다 표현력이 뛰어난 하드웨어 트랜잭션[12] 메모리를 사용하여 구현할 수 있습니다.
더블 와이드 비교 및 스왑
인접한 2개의 포인터 크기 위치(또는 포인터 크기의 2배 크기)에서 작동합니다.최신 x86 프로세서에서는 CMPXCHG8B 및 CMPXCHG16B 명령이[13] 이 역할을 수행하지만 초기 64비트 AMD CPU는 CMPXCHG16B를 지원하지 않습니다(현재의 AMD CPU는 CMPXCHG16B를 지원합니다).Core 2 시대의 일부 인텔 메인보드도 프로세서가 이를 지원하지만 사용을 방해합니다.이러한 문제는 CMPXCHG16B의 [14]하드웨어 지원이 필요했기 때문에 Windows 8.1의 발매시에 주목을 받게 되었습니다.
단일 비교, 이중 스왑
1개의 포인터를 비교하지만 2개의 포인터를 씁니다.Itanium의 cmp8xchg16 명령어는 두 개의 포인터가 인접한 곳에서 이를 [15]구현합니다.
여러 단어 비교 및 스왑
일반 비교 및 스왑의 일반화입니다.임의로 배치된 메모리 위치 중 임의의 개수의 위치를 원자적으로 스왑하기 위해 사용할 수 있습니다.통상, 복수의 워드의 비교와 스왑은, 통상적인 배폭의 비교와 스왑 [16]조작을 사용해 소프트웨어로 실장됩니다.이 접근법의 단점은 확장성이 떨어진다는 것입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Mullender, Sape; Cox, Russ (2008). Semaphores in Plan 9 (PDF). 3rd International Workshop on Plan 9.
  2. ^ 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. S2CID 2181446. Retrieved 2007-05-20.
  3. ^ J. H. 앤더슨과 M.Moir. "다중 객체 연산을 위한 범용 구조"Proc. 14th Annual ACM Semposium on Distributed Computing Principles on Distributed Computing(분산 컴퓨팅의 원칙에 관한 연례 ACM 심포지엄), 184~193쪽, 1995년.특히 표 1, 그림 1과 그림 2 및 섹션 2를 참조하십시오.
  4. ^ a b Dice, Dave; Hendler, Danny; Mirsky, Ilya (2013). "Lightweight Contention Management for Efficient Compare-and-Swap Operations". arXiv:1305.5800 [cs.DC].
  5. ^ Goetz, Brian (23 November 2004). "Java theory and practice: Going atomic". IBM developerWorks.
  6. ^ 튜더 데이비드, 라히드 게라위, 바실레오스 트리고나키스."동기에 대해 항상 알고 싶었지만 묻기 두려웠던 모든 것." 운영체제 원리에 관한 제24회 ACM 심포지엄의 진행.ACM, 2013, 페이지 33-48.상세 (페이지 34)
  7. ^ 데이비드 S.밀러.Wayback Machine에서 2012-03-20 아카이브된 "Atomic 및 Bitmask Operations, Linux 포트 유지 관리자에 대한 의미 및 "Atomic 및 Bitmask Operations의 의미와 동작"
  8. ^ https://en.cppreference.com/w/c/atomic/atomic_compare_exchange
  9. ^ "C 언어군에 대한 GNU C 확장 기능: 원자 메모리 액세스를 위한 내장 함수"
  10. ^ Simon Doherty 등, "DCAS는 논블로킹 알고리즘 설계에 있어서 좋은 것은 아니다." 제16회 연례 ACM 심포지엄, 2004년, 페이지 216~224. doi: 10.1145/1007912.1007945
  11. ^ Keir Fraser (2004), "실용 잠금 프리덤" UCAM-CL-TR-579.pdf
  12. ^ Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum, Marrek Olszewski.(2009) "상용 하드웨어 트랜잭션 메모리 구현의 초기 경험"Sun Microsystems 기술 보고서(60페이지) SMLI TR-2009-180.ASPLOS'09 doi:10.1145/1508244.1508263에 쇼트버전이 표시되었습니다.풀렝스 보고서에서는 섹션5에서 HTM을 사용한DCAS의 실장 방법에 대해 설명합니다.
  13. ^ "Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M" (PDF). Retrieved 2007-12-15.
  14. ^ "New Windows 8.1 requirements strand some users on Windows 8".
  15. ^ "Intel Itanium Architecture Software Developer's Manual Volume 3: Instruction Set Reference" (PDF). Retrieved 2007-12-15.
  16. ^ "A Practical Multi-Word Compare-and-Swap Operation" (PDF). Retrieved 2009-08-08.

외부 링크

CAS를 사용하여 구현되는 기본 알고리즘

CAS의 실장