A 확장과 원자적 연산
하트가 하나뿐이라면 counter++는 아무 문제가 없다. 그런데 두 하트가 같은 변수를 동시에 올리면 결과가 2가 아니라 1이 되는 일이 생긴다. 읽기와 쓰기 사이에 다른 하트가 끼어들기 때문이다. A 확장은 “읽고-바꾸고-쓰기”를 아무도 끼어들 수 없는 한 덩어리로 만드는 명령을 제공한다. 이 장에서는 LR/SC와 AMO라는 두 가지 방법, 순서를 정하는 aq/rl 비트, 그리고 그 위에 쌓아 올린 스핀락과 최신 확장(Zacas·Zabha·Zawrs·Zalasr)을 차례로 살펴본다.
- 두 하트가 같은 변수를 갱신할 때 “잃어버린 갱신”이 생기는 과정을 단계별로 설명한다.
- A 확장이 Zalrsc(LR/SC)와 Zaamo(AMO) 두 부분으로 나뉜 이유를 안다.
- aq·rl 비트가 만드는 acquire·release·순차 일관 순서를 구별한다.
- LR/SC의 예약 집합, SC 성공·실패 규칙, 제약된 LR/SC 루프의 진행 보장을 이해한다.
- AMO 명령의 인코딩(opcode 0101111, funct5)과 부호 있는/없는 max·min의 차이를 계산한다.
- amoswap 기반 스핀락, 티켓 락, 그리고 Zawrs로 “잠들며 기다리는” 방법을 비교한다.
- Zacas(비교-교환), Zabha(바이트·하프워드 AMO), Zalasr(load-acquire·store-release)의 역할을 안다.
counter++ 하나가 깨지는 순간
C의 counter++는 RISC-V에서 세 명령이 된다. 메모리에서 읽고(lw), 레지스터에서 1을 더하고(addi), 다시 메모리에 쓴다(sw). 하트 하나만 있으면 이 세 명령은 늘 붙어서 실행되는 것처럼 보인다. 그러나 두 하트가 동시에 같은 counter를 올리면 세 명령 사이사이에 상대방의 명령이 끼어들 수 있다.
sw가 하트 0의 결과를 덮어써 버린다.이런 상황을 경쟁 상태(race condition)라 한다. 결과가 실행 순서라는 “운”에 좌우된다. 문제의 뿌리는 읽기와 쓰기가 떨어져 있다는 데 있다. 해결책은 둘 중 하나다.
- 낙관적으로 시도하고, 끼어들었으면 다시 한다 — 읽을 때 “찜”해 두고, 쓸 때 그동안 아무도 건드리지 않았는지 확인한다. 이것이 LR/SC다.
- 읽기-계산-쓰기를 메모리 쪽에서 한 번에 한다 — “이 주소에 1을 더하고 원래 값을 알려 달라”는 하나의 명령을 보낸다. 이것이 AMO다.
인터럽트 처리기가 같은 변수를 건드리거나, DMA 장치가 메모리를 쓰는 경우에도 같은 문제가 생긴다. 하지만 RISC-V 규격이 원자적 명령을 정의하는 주된 목적은 “같은 메모리 공간에서 도는 여러 하트 사이의 동기화”다.
A 확장의 구성: Zalrsc + Zaamo, 그리고 친척들
오랫동안 A 확장은 한 덩어리였다. 현재 규격(A v2.1)은 이것을 두 개의 하위 확장으로 나눠 정의한다. “The A extension comprises instructions provided by the Zaamo and Zalrsc extensions.” 나눈 이유는 구현 비용이 다르기 때문이다. LR/SC는 보통 캐시에서 예약을 추적해야 해서 캐시가 없는 마이크로컨트롤러에는 부담이고, AMO는 버스나 메모리 컨트롤러 쪽에서 처리할 수 있다. 그래서 작은 코어는 Zaamo만 구현할 수 있게 했다.
| 확장 | 버전 (v20260120) | 주요 명령 | 한 줄 요약 |
|---|---|---|---|
| A | 2.1 | Zalrsc + Zaamo 전부 | G(= IMAFD_Zicsr_Zifencei)에 포함되는 표준 원자 확장 |
| Zalrsc | (A의 일부) | lr.w/d, sc.w/d | 예약을 걸고, 아무도 안 건드렸으면 쓴다 |
| Zaamo | (A의 일부) | amo<op>.w/d | 읽기-연산-쓰기를 한 명령으로 |
| Zawrs | 1.01 | wrs.nto, wrs.sto | 예약 집합이 바뀔 때까지 저전력 대기 |
| Zacas | 1.0 | amocas.w/d/q | 비교 후 같으면 교환 (128비트까지) |
| Zabha | 1.0 | amo<op>.b/h, amocas.b/h | 8·16비트 원자 연산 |
| Zalasr | 1.0 | lw.aq, sw.rl 등 | 순서 표시가 붙은 단독 원자 load·store |
aq와 rl: 원자 명령에 붙는 순서 표시
원자성만으로는 부족하다. 잠금을 얻은 뒤의 읽기·쓰기가 잠금을 얻기 전으로 당겨져 보이면 잠금이 아무 소용이 없다. RISC-V의 메모리 모델(RVWMO, 11장)은 느슨해서, 서로 다른 주소에 대한 접근은 다른 하트가 보기에 순서가 바뀔 수 있다. 그래서 모든 원자 명령에는 순서를 조이는 두 비트, aq(acquire)와 rl(release)가 있다.
| aq | rl | 의미 | 대표 용도 |
|---|---|---|---|
| 0 | 0 | 추가 순서 제약 없음 (원자성만) | 통계 카운터, 병렬 합산 |
| 1 | 0 | acquire: 이 하트의 뒤따르는 메모리 접근은 이 명령보다 먼저 일어난 것으로 관찰될 수 없다 | 잠금 획득 |
| 0 | 1 | release: 이 명령은 이 하트의 앞선 메모리 접근보다 먼저 일어난 것으로 관찰될 수 없다 | 잠금 해제 |
| 1 | 1 | 순차 일관(sequentially consistent): 앞뒤 어느 쪽과도 재배치되지 않는다 | C++ memory_order_seq_cst RMW |
“If only the aq bit is set, the atomic memory operation is treated as an acquire access, i.e., no following memory operations on this RISC-V hart can be observed to take place before the acquire memory operation.”
Unprivileged ISA, "A" Extension — Specifying Ordering of Atomic Instructions — 순서 표시는 원자 명령이 접근하는 주소 영역(메모리 또는 I/O) 한쪽에만 적용된다. 두 영역을 함께 묶으려면 FENCE를 쓴다.
규격 해설에 따르면 fence r,rw로도 acquire를, fence rw,w로도 release를 만들 수 있다. 하지만 FENCE는 앞뒤의 모든 읽기/쓰기를 묶어 버려서 필요 이상으로 순서를 조인다. aq/rl은 “이 명령 하나를 기준으로 한쪽 방향만” 막으므로 하드웨어가 더 자유롭게 재배치할 수 있다. RVWMO 쪽 이야기는 11장에서 자세히 다룬다.
LR/SC: 찜해 두고, 아무도 안 건드렸으면 쓴다
lr.w rd, (rs1)(load-reserved)는 주소의 워드를 읽어 rd에 부호 확장해 넣고, 그 워드를 포함하는 예약 집합(reservation set)을 등록한다. sc.w rd, rs2, (rs1)(store-conditional)는 예약이 아직 유효할 때만 rs2를 메모리에 쓴다. 성공하면 rd에 0을, 실패하면 0이 아닌 값을 쓰고 메모리는 건드리지 않는다. 성공이든 실패든 SC를 실행하면 이 하트의 예약은 사라진다.
0101111)를 쓰는 원자 명령의 형식. R형과 같지만 funct7 자리를 funct5 + aq + rl로 쪼갰다. LR은 rs2 자리를 0으로 둔다. 폭(funct3)은 일반 load/store와 같은 규칙으로 B·H·W·D를 고른다.예약 집합은 “워드 하나”보다 클 수 있다
규격은 예약 집합의 크기를 정하지 않는다. 주소한 워드(또는 더블워드)의 바이트를 모두 포함하기만 하면 얼마든지 크게 잡아도 된다. 실제 구현은 보통 캐시 줄 하나를 예약한다. 그러면 같은 캐시 줄의 다른 변수에 다른 하트가 써도 SC는 실패한다. 이를 거짓 공유(false sharing)에 의한 실패라 부르며, 잠금 변수를 캐시 줄 단위로 띄워 두는 이유다.
A+8에 썼을 뿐이지만, 그 바이트가 하트 0의 예약 집합 안에 있으므로 하트 0의 SC는 실패한다. 반대로 집합 밖(A+64)에 쓴 것은 SC에 영향을 주지 않는다.“If the SC.W succeeds, the instruction writes the word in rs2 to memory, and it writes zero to rd. If the SC.W fails, the instruction does not write to memory, and it writes a nonzero value to rd.”
Unprivileged ISA, "Zalrsc" Extension — 실패 코드 1은 “이유 불명의 실패”로 정해져 있고 다른 값은 예약되어 있다. 이식성 있는 소프트웨어는 “0이 아니면 실패”로만 판단해야 한다.
SC가 반드시 실패하는 경우
- SC의 주소가 가장 최근 LR의 예약 집합 안에 없을 때
- LR과 SC 사이에 다른 하트가 예약 집합에 쓴 것이 관찰될 때
- LR과 SC 사이에 하트가 아닌 장치(DMA 등)가 LR이 접근한 바이트에 쓴 것이 관찰될 때
- LR과 SC 사이에 프로그램 순서상 다른 SC(주소 무관)가 있을 때
또한 구현은 아무 이유 없이 SC를 가끔 실패시켜도 된다(아래의 진행 보장만 지키면). 그래서 SC는 늘 재시도 루프 안에 둔다. 규격이 예로 든 비교-교환(CAS) 함수가 그 전형이다.
인라인으로 넣으면 비교-교환의 핵심은 lr.w, bne, sc.w, bnez 네 명령뿐이다.
제약된 LR/SC 루프와 진행 보장
LR/SC의 약점은 라이브락(livelock)이다. 두 하트가 서로의 예약을 계속 깨면 둘 다 영원히 실패할 수 있다. 규격은 다음 조건을 만족하는 제약된 LR/SC 루프(constrained LR/SC loop)에 한해 “결국 누군가는 빠져나간다”고 보장한다.
| 조건 | 내용 |
|---|---|
| 길이 | 루프는 LR/SC 시퀀스와 재시도 코드로만 이루어지며, 메모리에 연속으로 놓인 최대 16개 명령(기본 ISA 기준 64바이트) |
| LR과 SC 사이 | 기본 I 명령만. 단, load·store, 뒤로 가는 점프, 성립하는 뒤로 가는 분기, JALR, FENCE, SYSTEM 명령은 금지. C(Zca)·Zcb의 압축형은 허용 |
| 재시도 코드 | 시퀀스를 반복하기 위한 뒤로 가는 점프·분기는 허용, 그 밖에는 위와 같은 제약 |
| 메모리 영역 | LR/SC 주소가 LR/SC eventuality 속성을 가진 영역에 있어야 함 (실행 환경이 알려 줌) |
| 주소와 크기 | SC는 같은 하트가 실행한 가장 최근 LR과 같은 유효 주소·같은 데이터 크기 |
이 조건을 지키면, 하트 H가 루프에 들어간 뒤 결국 다음 중 하나가 일어난다: H 또는 다른 하트가 그 예약 집합에 성공적인 SC를 하거나, 다른 하트·장치가 그 집합에 일반 store나 AMO를 하거나, H가 루프를 빠져나가는 분기를 하거나, H가 트랩된다. 곱셈·나눗셈과 부동소수점을 금지한 이유는 그 명령이 없는 구현에서 운영체제가 에뮬레이션할 때 예약이 깨지기 때문이다.
조건을 어긴 비제약(unconstrained) LR/SC는 어떤 구현에서는 성공하지만, 다른 구현에서는 한 번도 성공하지 않아도 규격 위반이 아니다. 이식성 있는 코드는 반복 실패를 감지해 다른 방법으로 넘어가야 한다. 예를 들어 LR과 SC 사이에서 함수를 호출하거나 다른 변수를 읽으면 이미 제약을 벗어난다.
직접 경쟁시켜 보기
아래 시뮬레이터에서 두 하트가 같은 counter(처음 값 0)를 하나씩 올린다. 어느 하트를 먼저 한 걸음 움직일지 여러분이 정한다. 세 가지 방법(일반 load/add/store, amoadd.w, LR/SC 루프)을 바꿔 가며, 어떤 순서에서 갱신이 사라지는지, LR/SC에서는 SC가 언제 실패하는지 확인해 보자.
두 하트 경쟁 시뮬레이터
AMO: 읽고-연산하고-쓰기를 한 명령으로
AMO(atomic memory operation)는 rs1의 주소에서 값을 읽어 rd에 넣고, 그 값과 rs2에 이항 연산을 적용한 결과를 같은 주소에 다시 쓴다. 이 전체가 하나의 메모리 연산으로 원자적으로 일어난다. RV64에서 .w AMO는 rd에 넣는 32비트 값을 부호 확장하고 rs2의 위쪽 32비트는 무시한다.
amoadd.w a0, a1, (a2)의 흐름. 하트는 “주소·연산·값”을 보내고, 읽기→연산→쓰기는 원자적 단위 안에서 한 번에 끝난다. rd로 돌아오는 것은 연산 전의 옛 값이다. 단순한 구현은 이것을 내부적으로 LR/SC처럼 처리하고, 큰 시스템은 메모리 컨트롤러나 공유 캐시에서 직접 처리하기도 한다.| 명령 (.W / .D) | funct5 | 메모리에 남는 새 값 | 비고 |
|---|---|---|---|
| lr | 00010 | (쓰지 않음) | rs2 = 0, 예약 등록 |
| sc | 00011 | rs2 (성공 시에만) | rd = 0 성공 / ≠0 실패 |
| amoswap | 00001 | rs2 | 잠금 획득·해제 |
| amoadd | 00000 | mem + rs2 | 카운터, 티켓 발급 |
| amoxor | 00100 | mem ^ rs2 | 비트 뒤집기 |
| amoand | 01100 | mem & rs2 | 비트 지우기 |
| amoor | 01000 | mem | rs2 | 비트 세우기 |
| amomin | 10000 | min(mem, rs2) 부호 있음 | |
| amomax | 10100 | max(mem, rs2) 부호 있음 | |
| amominu | 11000 | min(mem, rs2) 부호 없음 | |
| amomaxu | 11100 | max(mem, rs2) 부호 없음 | |
| amocas (Zacas) | 00101 | mem == rd 이면 rs2 | funct3 010/011/100 = W/D/Q |
모든 AMO는 주소가 피연산자 크기에 맞게 자연 정렬되어 있어야 한다(워드는 4바이트, 더블워드는 8바이트 경계). 정렬되지 않으면 주소 정렬 예외나 접근 폴트가 난다. 다만 특권 규격의 misaligned atomicity granule PMA가 있으면, 그 크기 안에 모두 들어가는 접근은 예외 없이 원자적으로 실행될 수 있다.
AMO 놀이터 (32비트)
실행 전후
인코딩
병렬 합산처럼 옛 값이 필요 없으면 amoadd.w x0, t1, (a0)로 쓴다. 규격 해설은 큰 구현이 이 경우 옛 값을 돌려보내는 과정을 생략하고 메모리 쪽에서 처리하는 최적화를 할 수 있다고 설명한다. AMO가 LR/SC보다 많은 코어에서 더 잘 확장되는 이유다.
잠금 만들기: 스핀락, 티켓 락, 그리고 잠들며 기다리기
규격은 AMO의 쓰임새를 보여 주려고 test-and-test-and-set 스핀락 예제를 싣고 있다. 먼저 평범한 lw로 잠금이 풀렸는지 보고(test), 풀려 보이면 그때 amoswap.w.aq로 1을 써 넣으며 옛 값을 확인한다(test-and-set). 옛 값이 0이었으면 내가 잠금을 얻은 것이다.
획득 쪽 AMO에는 aq가 붙어 임계 구역의 접근이 잠금 획득보다 앞당겨 보이지 않게 하고, 해제 쪽 AMO에는 rl이 붙어 임계 구역의 접근이 해제보다 늦게 보이지 않게 한다. 규격은 잠금 해제도 sw 대신 amoswap으로 하길 권한다. 그래야 투기적 잠금 생략(speculative lock elision) 같은 하드웨어 최적화가 잠금 패턴을 알아보기 쉽다.
티켓 락: 줄 서서 기다리기
단순 스핀락은 공정하지 않다. 운 좋은 하트가 계속 잠금을 가져갈 수 있다. 티켓 락은 은행 번호표처럼 순서를 보장한다. 들어올 때 amoadd.w로 번호표를 하나 뽑고, “지금 부르는 번호”가 내 번호가 될 때까지 기다린다.
amoadd.w로 원자적이면 된다. now_serving은 잠금을 가진 하트만 올리므로 경쟁이 없다. 들어온 순서대로 잠금을 얻으니 굶주림(starvation)이 없다.돌며 기다리기 vs 잠들며 기다리기 (Zawrs)
스핀락의 대기 루프는 아무 일도 하지 않으면서 명령을 계속 실행한다. 전력도 쓰고, SMT 코어라면 옆 하트의 실행 자원도 빼앗는다. Zawrs는 이 낭비를 줄인다. lr.w로 잠금 변수에 예약을 걸어 둔 뒤 wrs.nto(no timeout)를 실행하면, 하트는 예약이 유효하고 대기 중인 인터럽트가 없는 동안 저전력 상태로 멈춘다. 다른 하트가 잠금 변수에 쓰면 예약이 깨지고 하트가 깨어난다. wrs.sto(short timeout)는 구현이 정한 짧은 시간이 지나면 스스로 깨어난다.
세 하트의 잠금 쟁탈전
최신 원자 확장: Zacas, Zabha, Zawrs, Zalasr
Zacas — 하드웨어 비교-교환
A 확장 설계자들은 처음에 CAS 대신 LR/SC를 택했다. 규격 해설은 그 이유로 CAS의 ABA 문제(ABA problem), 피연산자가 셋이라 새 형식이 필요한 점 등을 든다. 그러나 CAS 기반 알고리즘이 널리 쓰이고 많은 코어에서 더 잘 확장되기 때문에 Zacas가 추가되었다. amocas.w rd, rs2, (rs1)은 메모리 값을 읽어 rd의 기대값과 비교하고, 같으면 rs2를 쓴다. 어느 경우든 읽은 값은 rd에 돌아온다.
- AMOCAS.D는 RV32에서 레지스터 쌍(rd, rd+1)을 쓴다. 첫 레지스터는 짝수여야 하며, 홀수 번호 인코딩은 예약되어 있다. x0을 쌍으로 지정하면 원본은 둘 다 0으로 읽히고 결과는 버려진다.
- AMOCAS.Q(RV64 전용)는 128비트를 비교·교환한다. 포인터와 수정 횟수를 함께 바꿔 ABA 문제를 피하는 무잠금 큐에 쓰인다.
- 실패한 AMOCAS는 쓰기를 하지 않거나 옛 값을 다시 쓸 수도 있다. 그래서 항상 쓰기 권한을 요구한다. 성공했을 때만 rl의 release 의미가 있고, aq의 acquire 의미는 성공·실패와 무관하다.
Zabha — 바이트와 하프워드 AMO
A 확장에는 8·16비트 AMO가 없어서 컴파일러가 워드 AMO나 LR/SC 루프로 흉내를 냈다. 이 방법은 코드가 길어지고, I/O 영역에서는 옆 바이트까지 건드리는 부작용이 있으며, 큰 시스템에서 공정성 문제가 생긴다. Zabha는 amo<op>.b/h를 funct3 = 000(B), 001(H)로 추가하고, Zacas도 있으면 amocas.b/h까지 제공한다. 결과는 늘 부호 확장된다. LR/SC의 바이트·하프워드 버전은 “쓸모가 적다”며 넣지 않았다.
Zawrs — 예약 집합 위에서 잠들기
WRS는 모든 특권 모드에서 쓸 수 있다. WFI와 달리 사용자 모드에서 쓰라고 만든 명령이다. 다만 mstatus.TW가 1이면 M 모드가 아닌 모드에서 실행한 wrs.nto가 구현이 정한 시간 안에 끝나지 않을 때 illegal-instruction 예외가 난다(가상화 환경에서는 hstatus.VTW에 따라 virtual-instruction 예외). 운영체제가 “너무 오래 자는” 하트를 되찾을 수 있게 한 장치다.
Zalasr — 단독 load-acquire / store-release
A 확장의 LR과 SC는 짝으로만 쓰도록 설계되어 있다. 그래서 C++의 atomic_load(acquire)는 지금까지 lw; fence r,rw, atomic_store(release)는 fence rw,w; sw로 번역했다. Zalasr는 이를 한 명령으로 만든다.
| 명령 | funct5 | 필수 비트 | 규칙 |
|---|---|---|---|
l{b|h|w|d}.{aq|aqrl} rd, (rs1) | 00110 | aq = 1 (rs2 = 0) | aq가 0인 인코딩은 예약. ld.aq는 RV64 전용 |
s{b|h|w|d}.{rl|aqrl} rs2, (rs1) | 00111 | rl = 1 (rd = 0) | rl이 0인 인코딩은 예약. sd.rl은 RV64 전용 |
예를 들어 lw.aq a0, (a1)은 0x3405a52f, sw.rl a0, (a1)은 0x3aa5a02f다. 규격은 “Zaamo, Zabha, Zalasr를 함께 쓰면 모든 C++ 원자 연산을 단일 명령으로 지원할 수 있다”고 정리한다. 비트가 하나도 없는 버전은 정렬된 일반 load/store로 충분하고, load-release나 store-acquire는 언어 메모리 모델에서 쓰이지 않아 넣지 않았다.
이 책이 기준으로 삼는 ISA 매뉴얼 v20260120 서문의 변경 사항 첫 줄이 “Addition of the Zalasr extension for Load-Acquire/Store-Release operations”다. 같은 문서의 확장 목록에서 Zalasr 1.0은 Ratified 상태로 실려 있다.
핵심 정리
- 읽기와 쓰기 사이에 다른 하트가 끼어들면 잃어버린 갱신이 생긴다. A 확장은 이를 막는 원자 명령을 제공하며, Zalrsc(LR/SC) + Zaamo(AMO)로 이루어진다.
- 모든 원자 명령에는 aq·rl 비트가 있다. aq는 뒤의 접근이 앞으로, rl은 앞의 접근이 뒤로 새는 것을 막고, 둘 다면 순차 일관이다.
- LR은 예약 집합을 등록하고, SC는 예약이 유효할 때만 쓴다. 성공하면 rd = 0, 실패하면 0이 아닌 값. SC는 성패와 무관하게 예약을 없앤다.
- 최대 16개 명령·기본 I 명령만·LR과 SC 사이에 load/store 없음 등 조건을 지킨 제약된 LR/SC 루프만 진행이 보장된다.
- AMO는 opcode
0101111, funct5로 연산을 고른다(swap 00001, add 00000, xor 00100, and 01100, or 01000, min 10000, max 10100, minu 11000, maxu 11100). rd에는 옛 값이 돌아온다. - 스핀락은
amoswap.w.aq로 얻고amoswap.w.rl x0, x0로 푼다. Zawrs의wrs.nto/sto는 LR 예약 위에서 저전력으로 기다리게 한다. - Zacas는 AMOCAS.W/D/Q(비교-교환), Zabha는 8·16비트 AMO, Zalasr는 단독 load-acquire/store-release를 더한다.
확인 퀴즈
sc.w t2, t0, (a0) 실행 후 t2가 0이었다. 무슨 뜻인가?
A 확장을 둘로 나눈 하위 확장의 조합으로 옳은 것은?
메모리 값이 0xffffffff, rs2가 1일 때 amomaxu.w 후 메모리에 남는 값은?
잠금 해제에 amoswap.w.rl x0, x0, (a0)를 쓰는 이유로 가장 알맞은 것은?
다음 중 제약된 LR/SC 루프의 LR과 SC 사이에 둘 수 있는 명령은?
Zawrs의 wrs.nto를 실행한 하트가 깨어나는 조건이 아닌 것은?
RV32에서 amocas.d가 64비트 기대값을 읽어 오는 곳은?
더 읽을거리
- "A" Extension for Atomic Instructions, Version 2.1 (Unprivileged ISA v20260120)
- "Zawrs" Extension for Wait-on-Reservation-Set instructions, Version 1.01
- "Zacas" Extension for Atomic Compare-and-Swap (CAS) Instructions, Version 1.0.0
- "Zabha" Extension for Byte and Halfword Atomic Memory Operations, Version 1.0
- "Zalasr" Atomic Load-Acquire and Store-Release Instructions, Version 1.0
- RVWMO Memory Consistency Model — 원자성 공리(Atomicity Axiom)의 정확한 정의 (11장)
- Maged M. Michael, Michael L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms” (PODC 1996) — Zacas 규격의 AMOCAS.Q 큐 예제가 따르는 알고리즘