A 확장: LR/SC, AMO, aq·rl

7편까지는 하트(hart, 하드웨어 스레드) 하나가 명령어를 차례로 실행하는 세계였다. 하트가 둘 이상이 되어 같은 메모리를 함께 쓰면 새 문제가 생긴다. "읽고, 1 더하고, 쓴다" 사이에 다른 하트가 끼어들 수 있다. A 확장은 이 문제를 푸는 원자(atomic) 명령어를 더한다. 이 편에서는 명령어의 뜻과 규칙을 QEMU에서 확인하고, 하트를 여러 개 띄워 실제로 경쟁시킨다. 예약을 하드웨어에서 어떻게 추적하는지는 20편(A 확장 구현)에서, 순서 규칙의 정확한 정의는 9편(메모리 모델)에서 다룬다.

장비는 맥 M1 Max(10코어), QEMU 11.1.3 virt 보드, riscv64-elf-gcc 16.2다. QEMU는 하트마다 호스트 스레드를 따로 써서(MTTCG) 여러 하트가 실제로 동시에 돈다.

1. 왜 원자 명령어가 필요한가

공유 카운터를 하트 두 개가 올린다고 하자. RV32I만으로 쓰면 이렇다.

lw   t0, 0(a0)    # 읽기
addi t0, t0, 1    # 더하기
sw   t0, 0(a0)    # 쓰기

카운터가 5일 때 두 하트가 동시에 lw를 하면 둘 다 5를 읽고, 둘 다 6을 쓴다. 증가 두 번 중 하나가 사라진다. 실제로 QEMU에서 하트 2개가 10만 번씩 올리니 기대값 200,000 중 100,686·100,243·100,109만 남았다(3번 실행). 거의 절반이 사라졌다.

해결책은 두 가지 방향이다. 하나는 읽기-수정-쓰기를 명령어 하나로 만들어 메모리 쪽에서 쪼갤 수 없게 하는 것(AMO)이다. 다른 하나는 읽을 때 표시를 해 두고, 쓸 때 그 사이에 누가 건드렸으면 쓰기를 포기하고 다시 하는 것(LR/SC)이다. RISC-V는 둘 다 준다.

LR/SC는 Zalrsc 확장(lr.w·sc.w, RV64는 .d도)으로, AMO 9종은 Zaamo 확장으로 나뉘어 있고, A는 둘을 합친 것이다. 앞쪽은 임의의 읽기-수정-쓰기와 CAS(compare-and-swap)를, 뒤쪽은 카운터·스왑·비트 세트·락처럼 정해진 연산을 맡는다.

A 확장은 비준 버전 2.1에서 두 하위 확장으로 나뉘었다. 명세는 Zaamo만 있는 구성을 "캐시가 없어 LR/SC를 자연스럽게 지원하기 어려운 마이크로컨트롤러"용으로 설명한다.

2. 인코딩: opcode AMO, funct5와 aq·rl

모든 A 명령어는 R 형식을 변형해 쓴다. opcode는 AMO(0101111), funct3는 크기(010 = 워드, 011 = 더블워드)다. funct7 자리는 위 5비트(funct5)가 연산을, 아래 2비트가 aq(bit 26)와 rl(bit 25)을 담는다. 아래 값은 GNU as가 만든 기계어에서 뽑았다.

lr은 rs2 칸을 쓰지 않는다(0이어야 한다). 어셈블리에서는 amoadd.w.aq, amoadd.w.rl, amoadd.w.aqrl처럼 접미사로 두 비트를 켠다. 확인한 기계어에서 .aq는 bit 26만, .rl은 bit 25만, .aqrl은 둘 다 1이었다.

3. LR/SC: 예약을 걸고 조건부로 쓴다

lr.w rd, (rs1)(load-reserved)은 워드를 읽어 rd에 넣고, 그 주소를 포함하는 예약 집합(reservation set)을 등록한다. sc.w rd, rs2, (rs1)(store-conditional)은 예약이 아직 유효하고 주소가 예약 집합 안일 때만 rs2를 쓴다. 성공하면 rd에 0, 실패하면 0이 아닌 값을 넣고 메모리는 건드리지 않는다. 성공이든 실패든 sc를 실행하면 그 하트의 예약은 사라진다.

실패 코드는 지금 1만 정의되어 있다("이유 불명"). 명세는 1을 고른 이유를 "단순한 구현이 slt·sltu용으로 이미 있는 선택기로 낼 수 있게"라고 설명한다. 이식성 있는 소프트웨어는 0인지 아닌지만 봐야 한다.

언제 sc가 반드시 실패해야 하고, 언제 실패해도 되는지가 설계의 핵심이다. 명세의 규칙을 정리하면 이렇다.

QEMU에서 하트 하나로 각 경우를 실행했다(sc 결과, 메모리).

sc만 (lr 없음)          -> 1, 메모리 그대로
lr; sc                  -> 0, 씀
lr; sc; sc (둘째)        -> 1
lr x; sc y (다른 주소)   -> 1
lr; sw 99; sc           -> 1, 메모리 99
lr; sw 같은 값; sc       -> 0, 씀
lr; 다른 주소 lw; sc     -> 0, 씀

같은 하트의 저장은 명세가 구현에 맡긴 부분이라 QEMU의 두 결과(다른 값이면 실패, 같은 값이면 성공) 모두 명세 위반은 아니다. 그런데 하트 2개로 같은 시험을 하자 문제가 보였다. 하트 0이 lr.w로 5를 읽은 뒤 하트 1이 같은 주소에 쓰게 하고, 하트 0이 sc.w를 했다.

하트 1이 쓴 것   하트 0의 sc.w   명세
9 (다른 값)      1 (실패)        실패
5 (같은 값)      0 (성공)        실패해야 함
9 → 5 (ABA)      0 (성공)        실패해야 함

QEMU는 예약을 주소가 아니라 값 비교로 흉내 낸다. QEMU 소스(target/riscv/tcg/insn_trans/trans_rva.c.inc의 gen_sc)를 보면 sc.w를 "LR이 읽은 값과 지금 값이 같으면 저장"하는 compare-and-swap으로 번역한다. 그래서 다른 하트가 같은 값을 다시 쓰면(ABA) 알아채지 못한다. 명세가 LR/SC를 CAS 대신 고른 첫 번째 이유가 바로 "LR/SC는 주소에 대한 모든 쓰기를 감시하므로 ABA 문제가 없다"이다. RTL을 QEMU와 락스텝(33편)으로 비교할 때, 이 경우 RTL의 sc 실패가 정답인데 QEMU와 다르게 나온다는 점을 알아 둬야 한다.

진행 보장. LR/SC는 서로가 서로의 예약을 계속 깨면 아무도 못 끝나는 라이브락(livelock)이 생길 수 있다. 명세는 "제약된 LR/SC 루프(constrained LR/SC loop)"에 한해 결국 누군가는 성공한다고 보장한다. 조건은 루프 전체가 연속된 명령어 16개 이하, lr과 sc 사이에는 기본 I 명령어만(로드·스토어, 뒤로 가는 분기, jalr, fence, SYSTEM 제외), sc는 직전 lr과 같은 주소·크기다. 이 밖의 LR/SC 시퀀스는 어떤 구현에서는 영원히 실패해도 된다. 곱셈·나눗셈과 부동소수점도 금지다. 명세는 그 하드웨어가 없는 구현에서 운영체제가 이 명령어들을 흉내 내는 일을 단순하게 하려는 것이라고 설명한다.

4. AMO 9종: 읽고, 계산하고, 쓰기를 한 번에

AMO amoop.w rd, rs2, (rs1)은 메모리 [rs1]의 원래 값을 읽어 rd에 넣고, 그 값과 rs2로 연산한 결과를 같은 주소에 쓴다. 이 세 단계가 다른 하트에게는 쪼갤 수 없는 한 동작으로 보인다. 메모리 0x80000005(부호 있게 읽으면 음수), rs2 = 3으로 9종을 실행했다. 모든 AMO의 rd는 원래 값 0x80000005였고, 메모리에 남은 값은 다음과 같다.

max와 maxu가 정반대 답을 낸 것을 보자. 0x80000005는 부호 있게 읽으면 −2,147,483,643이라 3보다 작고, 부호 없이 읽으면 2,147,483,653이라 3보다 크다. 메모리 0x0c, rs2 = −6(0xfffffffa)으로도 9종을 돌려 모두 18개를 Python 기준 모델과 대조했고 18개 모두 일치했다.

결과를 버리려면 rd를 x0로 둔다. 명세는 이 경우 구현이 원래 값을 가져오는 일을 생략할 수 있다고 적는다. 메모리 컨트롤러나 공유 캐시 쪽에서 AMO를 실행하는 "먼 원자 연산"이 가능한 이유다. 반대로 간단한 구현은 AMO를 내부적으로 LR/SC 방식으로 만들어도 된다(반드시 끝난다는 보장이 있다면).

정렬. AMO와 LR/SC는 주소가 크기에 맞게 정렬되어야 한다(워드는 4의 배수). 어기면 주소 정렬 예외나 접근 오류 예외가 난다. QEMU에서 주소 0x800006a2(4의 배수 + 2)로 시험했다.

amoadd.w (주소+2) -> 트랩, mcause 6, mtval 0x800006a2
lr.w     (주소+2) -> 트랩, mcause 4, mtval 0x800006a2
lw       (주소+2) -> 트랩 없음 (QEMU가 처리)

mcause 6은 "스토어/AMO 주소 정렬 예외", 4는 "로드 주소 정렬 예외"다. AMO는 쓰기를 포함하므로 스토어 쪽 원인 번호를 쓰고, lr은 로드 쪽을 쓴다. 보통 lw의 정렬 안 된 접근은 4편에서 본 것처럼 구현이 처리해도 되지만, 원자 명령어는 흉내 낼 방법이 마땅치 않아 예외가 원칙이다. 명세는 예외로 정렬 완화를 허용하는 PMA(misaligned atomicity granule, 특권 명세)를 두었는데, AMO에만 적용되고 LR/SC에는 적용되지 않는다.

5. aq·rl: 한쪽 방향만 막는 순서 비트

원자 명령어는 그 자체만 원자적이면 끝이 아니다. 락을 잡고 임계 구역(critical section)에서 데이터를 고친 뒤 락을 놓는다고 하자. 다른 하트가 "락이 풀렸다"를 본 순간, 임계 구역의 쓰기도 반드시 보여야 한다. RISC-V의 기본 메모리 모델(RVWMO)은 같은 하트의 서로 다른 주소 접근이 다른 하트에게 순서가 바뀌어 보이는 것을 허용하므로, 순서를 따로 지정해야 한다.

그림처럼 aq는 아래에서 위로 넘어오는 것만, rl은 위에서 아래로 넘어가는 것만 막는다. 락 바깥의 접근이 임계 구역 안으로 들어오는 것은 허용된다. 이것이 fence보다 싼 이유다. 명세는 획득을 fence r,rw로, 해제를 fence rw,w로도 만들 수 있지만 그러면 불필요한 순서까지 강제한다고 설명한다. 순서는 같은 주소 영역(메모리 또는 I/O) 안에서만 적용되고, 두 영역에 걸친 순서는 fence로 지정한다.

LR/SC 쌍에서는 lr에 aq를, sc에 rl을 다는 것이 기본형이다. 명세는 lr.rl(aq 없이)이나 sc.aq(rl 없이)는 쓰지 말라고 한다. 더 강한 순서를 보장하지 않으면서 느려질 수만 있다. 명세의 스핀락 예제는 이렇게 생겼다. 이 글의 실습도 같은 모양이다.

      li   t0, 1
again:
      lw   t1, (a0)          # 잡혀 있나 먼저 본다
      bnez t1, again
      amoswap.w.aq t1, t0, (a0)  # 잡기 시도
      bnez t1, again
      # ... 임계 구역 ...
      amoswap.w.rl x0, x0, (a0)  # 0을 써서 놓기

첫 lw로 먼저 보고 비었을 때만 amoswap을 하는 것을 test-and-test-and-set이라 한다. 잡혀 있는 동안 AMO(쓰기)를 반복하지 않으므로 캐시 줄이 하트 사이를 덜 오간다.

6. 실습: 하트 1~8개로 카운터 경쟁

common/의 시작 코드는 하트 하나만 가정하므로 내 폴더(08/smp/)에 복사해 고쳤다. 시작할 때 mhartid를 읽어 하트마다 4KiB 스택을 따로 잡고 main(hartid)를 부른다. QEMU -bios none -smp N에서 모든 하트가 같은 진입점에서 출발하는 것을 먼저 확인했다.

다섯 방식으로 공유 카운터를 하트마다 10만 번 올렸다. 방식 사이에는 amoadd.w로 만든 장벽(barrier)으로 모든 하트를 맞춰 동시에 출발시켰다.

static void inc_amo(void) {
  __asm__ volatile("amoadd.w zero, %1, (%0)"
    :: "r"(&counter), "r"(1) : "memory");
}
static uint32_t inc_lrsc(void) {  /* sc 실패 수 */
  uint32_t t, f = 0;
  __asm__ volatile(
    "1: lr.w %0, (%2)\n addi %0, %0, 1\n"
    "   sc.w %0, %0, (%2)\n beqz %0, 2f\n"
    "   addi %1, %1, 1\n j 1b\n 2:"
    : "=&r"(t), "+r"(f) : "r"(&counter) : "memory");
  return f;
}

먼저 하트 1개에서 QEMU -icount로 반복 한 번의 명령어 수를 셌다(루프 제어 포함). 경쟁이 없으니 다섯 방식 모두 정확히 100,000이 나왔다.

LR/SC 루프의 8개에는 실패 횟수를 세는 명령어 2개가 들어 있다. 카운터 하나를 올리는 데는 AMO가 가장 짧다. 락은 임계 구역이 길어 여러 데이터를 함께 고칠 때 값을 한다.

이제 하트를 늘렸다. 각 설정을 3번씩 돌렸다.

원자적이지 않은 증가는 하트가 늘수록 더 많이 사라졌고, 매번 값이 달랐다. 원자 방식 4가지(amoadd.w, LR/SC, 두 스핀락)는 36번 실행(3설정 × 3회 × 4방식) 모두 기대값과 같았다. LR/SC의 sc.w 실패는 하트 2개에서 170,295·166,215·195,313번, 8개에서 793,259·775,984·793,356번이었다. 증가 한 번당 거의 한 번씩 실패한 셈이다. 실패 비율은 QEMU의 스레드 스케줄링에 좌우되므로 실제 칩의 숫자로 읽으면 안 된다. 그래도 경쟁이 심할수록 LR/SC는 재시도가 늘고, AMO는 재시도 없이 한 번에 끝난다는 구조적 차이는 그대로다. 스핀락에서 락을 기다리며 돈 횟수는 하트 2개에서도 3회 모두 1억 1천만~1억 6천만 번이었다(락을 잡은 하트 하나만 일하는 동안 나머지가 돈다).

Zaamo와 Zalrsc를 따로 주면. 같은 C 원자 연산을 세 -march로 컴파일했다.

            rv32ia     rv32i_zaamo   rv32i_zalrsc
fetch_add   amoadd.w   amoadd.w      LR/SC 루프
CAS         LR/SC 루프 라이브러리     LR/SC 루프

GCC는 Zalrsc만 있으면 fetch_add를 LR/SC 루프로 펼쳤다. Zaamo만 있으면 CAS를 만들 명령어가 없어 __atomic_compare_exchange_4 호출로 남겼다. 베어메탈에서는 이 함수를 따로 제공해야 링크된다. CAS가 필요한 코드(대부분의 락 없는 자료구조)를 돌릴 코어라면 Zalrsc가 필요하다는 뜻이다.

7. 설계 체크리스트: A 확장

마지막 줄이 하드웨어에 주는 뜻은 이렇다. 예약은 하트마다 하나뿐이고 sc가 언제나 지우므로, 트랩 처리기에서 따로 지우는 회로가 꼭 필요하지는 않다. 소프트웨어가 문맥 전환 때 sc로 지운다. 예약을 어디에 두고(코어 안 레지스터 한 벌 또는 캐시 줄 상태) 다른 하트의 저장을 어떻게 감지할지(캐시 일관성 무효화 메시지)는 20편에서 다룬다.

정리

• A 확장 = Zalrsc(lr/sc) + Zaamo(AMO 9종). 모든 명령어가 opcode AMO, funct5로 연산, bit 26·25로 aq·rl을 고른다.
• sc는 예약이 살아 있을 때만 쓰고 0을, 실패하면 1을 낸다. 다른 하트의 저장은 같은 값이어도 실패시켜야 하는데, QEMU는 같은 값·ABA 저장 뒤에도 성공시켰다.
• AMO 18개가 기준 모델과 일치했고, 정렬 안 된 AMO·LR은 mcause 6·4 예외를 냈다. 하트 8개 경쟁에서 일반 증가는 22%만 남았고 원자 방식 4가지는 모두 정확했다.
• aq는 뒤 접근이 앞서는 것을, rl은 앞 접근이 뒤처지는 것을 막는다. 락은 amoswap.w.aq로 잡고 amoswap.w.rl로 놓는다.

다음 글: 9편에서는 이 편에서 미뤄 둔 질문, "같은 하트의 접근이 다른 하트에게 어떤 순서로 보이는가"를 정면으로 다룬다. RISC-V의 메모리 모델 RVWMO, fence의 pred·succ 조합, aq·rl과 fence의 관계, 그리고 x86 같은 강한 순서를 주는 Ztso를 본다. 리트머스 시험(MP·SB·LB)에서 어떤 결과가 허용되는지 직접 세어 본다.

참고 문헌

• QEMU 소스 target/riscv/tcg/insn_trans/trans_rva.c.inc의 gen_sc. https://github.com/qemu/qemu

• The RISC-V Instruction Set Manual, Volume I: Unprivileged Architecture, Version 20240411. 14장 "A" 확장 v2.1(14.1 순서 지정, 14.2 Zalrsc, 14.3 저장 조건부의 최종 성공, 14.4 Zaamo). https://github.com/riscv/riscv-isa-manual

• The RISC-V Instruction Set Manual, Volume II: Privileged Architecture, Version 20240411. 3.1.15 mcause(예외 코드 4·6), 3.6 PMA(misaligned atomicity granule)

• D. Patterson, A. Waterman, The RISC-V Reader: An Open Architecture Atlas, 2017. 6장 RV32A

• K. Gharachorloo 외, "Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors," ISCA 1990 (release consistency)

• QEMU 다중 스레드 TCG(MTTCG) 문서. https://www.qemu.org/docs/master/devel/multi-thread-tcg.html