Lec 23 · Release consistency·multi-copy atomicity 와 Synchronization(동기화)

1.122강에서 미룬 release consistency(RC): acquire/release 의미, eager RC·lazy RC 구현

1.2multi-copy-atomic vs non-multi-copy-atomic model, language memory model·DRF 로 마무리

1.3Synchronization: load/store 만의 mutual exclusion(deadlock·livelock) → Dekker's algorithm

1.4atomic RMW(amoswap) lock, relaxed model 의 fence 와 RISC-V AMO aq/rl 비교

1.5non-blocking synchronization 과 Compare&Swap, ABA problem·double CAS (LR/SC 는 다음 강의)

상황·문제SC 는 모든 memory access 를 program order 로 강제해 성능이 낮다 → relaxed memory consistency model(완화된 메모리 일관성 모델) 복습

원인TSO(Total Store Order) 는 read 가 write 를 bypass 하도록 허용, W→W·R→R 순서는 유지

해결model 이 보장하지 않는 순서는 fence 로 강제: producer 는 data store 와 flag store 사이 fence w,w, consumer 는 flag load 와 data load 사이 fence r,r

상황·문제RC: control·data dependence 만 지키면 read·write 가 read·write 를 모두 bypass 가능 (TSO 보다 약함)

원인순서가 필요한 곳을 hardware 가 모름 → programmer 가 acquire·release 로 표시해야 함

해결release: 앞선 write 가 모두 완료돼야 release 완료. acquire: 뒤 read 는 acquire 뒤에 실행. acquire(=read)·release(=write) 끼리는 SC

상황·문제RC 를 hardware 로 어떻게 구현할지: write 를 가능한 빨리 전파하는 방식

원인write 마다 즉시 coherence transaction(invalidation) 발생 → 같은 위치를 여러 번 쓰면 transaction 이 많아짐

해결write 는 write buffer 에서 out-of-order 완료, release 때 write buffer drain, acquire 뒤 load 는 acquire 뒤 issue. invalidation 이 LSQ 를 snoop 할 필요 없음(SC 와 차이)

상황·문제eager RC 의 coherence transaction overhead 를 줄이고 싶다

원인write 마다 invalidation 을 보내면 여러 write 를 결합할 수 없음

해결write 는 local cache 에만 기록(invalidation 없음), release 때 dirty block 을 lower-level cache 로 flush, acquire 때 local cache self-invalidation. local/shared 를 추적하면 local line 은 flush·invalidate 생략

상황·문제여러 processor 가 같은 위치의 copy 를 가질 때 write 가 모두에게 같은 순서로 보이는가

원인hierarchical shared buffer: 같은 buffer 를 공유하는 processor 가 write 를 먼저 봄 → store 가 atomic 하게 보이지 않음(non-MCA)

해결MCA: global visibility 지점을 넘은 write 는 모든 thread 가 관측. non-MCA 는 local fence 로 부족하고 더 global 한 memory barrier 필요

상황·문제hardware 가 제공하는 model 과 programmer 가 보는 model 을 분리할 수 있음

원인hardware 가 relaxed 여도 compiler 가 fence 를 넣으면 SC 를 제공할 수 있음

해결C/C++/Java 등 language-level model, DRF(data-race-free): 잘 synchronize 된 program 에 SC 보장 → 다음 주제 synchronization 으로 연결. 이후 출석(손들기) 확인

상황·문제concurrent process 가 memory 의 data 를 공유하면 synchronization 이 필요 (uniprocessor 에서도)

원인두 thread 가 ld→add 1→sd 를 동시에 하면 둘 다 1 을 읽어 2 를 씀 (기대값 3)

해결producer-consumer 와 mutual exclusion(상호 배제) 두 유형, 올바른 동기화 필요

상황·문제SC 가정, 공유 변수 c1·c2 로 critical section 진입 의사를 표시

원인1차: 둘 다 c=1 이면 서로 spin 하며 deadlock. 2차: 대기 시 c 를 0 으로 되돌리면 deadlock 은 없지만 동시 실행 시 livelock, 운 나쁜 process 는 starvation

해결turn 변수를 추가한 Dekker 방식으로 해결 (다음 섹션)

상황·문제c1·c2 만으로는 livelock·unfairness 가 남음

원인누가 기다릴지 정하는 정보가 없음

해결turn 변수 추가: c_i=1, turn=i 후 상대 c 가 1 이고 turn==i 면 대기. 늦게 turn 을 쓴 쪽이 대기해 livelock 없이 교대 진입

상황·문제load/store 로도 SC 에선 mutual exclusion 가능하나 weak model 에선 fence 가 필요해 코드가 비효율적·복잡

원인읽기와 쓰기 사이에 다른 thread 가 끼어들 수 있음

해결atomic read-modify-write(RMW) 명령어 추가: test-and-set, swap. amoswap 으로 lock 에 1 을 쓰고 old 값이 0 이면 진입, 끝나면 sd x0 로 해제

상황·문제relaxed model 에선 lock 획득 전에 shared data 를 건드리거나 해제 뒤에 write 가 완료될 수 있음

원인amoswap 자체는 주변 load/store 와 순서를 보장하지 않음

해결획득 뒤 fence r,rw, 해제 앞 fence rw,w. 또는 RISC-V AMO 의 aq bit(뒤 연산보다 먼저)·rl bit(앞 연산 뒤에) → amoswap.w.aq / amoswap.w.rl 로 fence 제거

상황·문제fence 와 aq/rl AMO 는 같은 일을 하는 것처럼 보임

원인fence 는 fence 앞뒤 모든 load/store 를 순서화, AMO 는 AMO 자신과 다른 연산 사이만 순서화

해결aq/rl 버전: critical section 앞 unrelated load 가 AMO 뒤로, 뒤 unrelated store 가 release AMO 앞으로 이동 가능. fence 버전은 이 reorder 불가 → fence 가 더 강함

상황·문제lock 을 잡은 software thread 가 de-schedule 되면 다른 thread 가 critical section 에서 진전 못 함

원인lock 기반 동기화는 lock 보유자에 의존

해결lock 없이 atomic 하게: Compare&Swap(m),Rt,Rs — M[m]==Rt 면 M[m]=Rs, status(implicit flag)=success. queue pop: head 를 읽고 Rhead+1 로 CAS, 실패면 retry

상황·문제CAS 는 source operand 3개(address·comparand·new value)+return 값 → RISC ISA 에 부적합, 구현 비용 큼

원인ABA problem: 값만 비교하므로 다른 task 가 A→B→A 로 바꿔도 CAS 성공

해결counter 를 붙인 double compare-and-swap(x64 CMPXCHG16B, operand 5개) → 더 복잡. RISC 에 맞는 LR/SC 는 다음 강의

acquire/release 로 표시된 synchronization 만 SC, 나머지 read·write 는 자유롭게 reorder

eager: write 즉시 invalidation, release 때 write buffer drain. lazy: local cache 에만 쓰고 release 때 flush, acquire 때 self-invalidate

한 thread 에 보인 store 는 모든 thread 에 보임 → 모두 같은 write 순서 관측

conflicting 연산을 label 해 잘 synchronize 된 program 에 SC 보장

deadlock: 서로 기다려 정지, livelock: 상태는 변하나 진전 없음, starvation: 특정 process 만 계속 진입 못 함

c1·c2·turn 으로 load/store 만으로 두 process 상호배제 (SC 가정)

read-modify-write 를 atomic 하게 수행, spin lock 구현

aq: AMO 가 뒤 연산보다 먼저, rl: 앞 연산 뒤에. fence 보다 약함(AMO 자신만 순서화)

M[m]==Rt 면 Rs 로 교체, status 반환. lock 없는 non-blocking 동기화

값만 비교하는 CAS 가 A→B→A 변경을 감지 못함, counter+double CAS 로 완화

4.1RC 에서 acquire 앞의 read/write 는 acquire 뒤로 이동할 수 있는가?

4.2lazy RC 에서 acquire 때 local cache 를 self-invalidate 하는 이유는?

4.3non-MCA 예제에서 P3 의 fence r,r 로 x2=0 을 막지 못하는 이유는?

4.4c1·c2 만 쓰는 2번째 시도의 문제는?

4.5amoswap.w.aq/rl 과 fence r,rw/fence rw,w 의 차이는?

4.6ABA problem 은 무엇이고 double CAS 는 어떻게 막는가?