TAS/CAS에서 futex까지 보는 락 구현 경로

원자 명령

TAS와 CAS는 읽기와 쓰기를 하나의 중단 불가능한 하드웨어 동작으로 묶는다.

atomic

짧은 임계 구역은 문맥 전환보다 바쁜 대기가 더 싸서 spinlock을 쓴다.

busy wait

오래 기다릴 가능성이 있으면 커널에 잠들어 CPU를 양보하는 mutex가 낫다.

sleep

경합이 없으면 사용자 공간에서 끝내고 경합이 있을 때만 커널이 깨우기를 맡는다.

fast userspace

TAS/CAS

락 상태를 경쟁 없이 바꾸는 최소 원자 연산이다. CAS는 예상 값과 현재 값을 비교해 성공할 때만 갱신한다.

compare exchange

ABA

값이 A에서 B를 거쳐 A로 돌아오면 단순 CAS가 변화를 놓칠 수 있다. 버전 태그나 hazard pointer 같은 보완이 필요하다.

identity problem

futex

경합이 없는 common path를 커널 진입 없이 처리한다. 경합 시 wait queue와 wake syscall로 잠든 스레드를 관리한다.

kernel only on contention

임계 구역 길이 짧고 커널 안쪽이면 spin, 길거나 blocking 가능성이 있으면 mutex를 본다.

공정성 락 획득 순서와 starvation 가능성이 요구사항과 맞는지 확인한다.

메모리 순서 atomic 연산이 필요한 acquire/release 의미를 가진다.

unlocked -> CAS success -> critical section
locked -> spin or futex_wait -> futex_wake