정리된 내용은 Related Posts에 있다.
- algorithm
- tournamant 경기 수 세기: 토너먼트는 우승 팀 빼고 모든 팀이 1회씩 지면 우승팀이 결정된다는 것 이용함.
- CAS
- Compare And Swap은 값을 비교하고 교환하는 과정을 원자적으로 수행해주는 연산이다.
- 이 명령에는 '1) 특정 메모리의 위치 값, 2) 기준 값, 3) 새로운 값' 이 필요하다. 1) 특정 메모리의 위치 값이 2) 기준 값과 같으면 3) 새로운 값으로 대체하며, atomic한 연산을 보장한다. 연산 중 다른 스레드가 간섭할 수 없다는 뜻이다.
- CPU-level 1 tick(CPU가 한 번의 클록 사이클 동안 수행하는 기본적인 작업 단위)에서 연산을 수행하므로 atomic 한 연산을 보장한다.
- semaphore, mutex를 구현하는데 사용하기도 하고 lock-free algorithm을 구현하는데 사용되기도한다.
- 물론 ABA problem 등의 문제가 있다. ABA problem은 CAS 연산과 관련해서 공유 객체의 변경을 감지하지 못하는 현상이다. ABA 문제와 해결은 따로 정리해봐야겠다.