# Compare and Swap

gkfla668

Spinlock 잡으려는 lock이 avaliable 해 질 때 까지 계속 루프를 돌며 진입을 재시도한다. 이른바 바쁘게 기다리는 busy waiting의 한 종류이다. Busy waiting lock을 잡기 위해 다른 작업을 수행하지 않고 계속해서 기다리는 경우 Sofrware-only Algorithm Peterson's Algorithm 동기화 문제를 해결하기 위해 처음으로 고안된 방법 오직 두개의 context만이 존재하는 상황을 가정한다. 전역변수 flag, turn 선언 flag: critical section에 들어갈 준비가 되었는지 turn: 누가 critical section에 들어갈 차례인지 문제점 두개의 context만 존재하는 상황에서만 가능 atomic하지 않은 아키텍쳐에서 사용 불가능 Hardware Approaches **Disabling Inter

coral2cola

Concurrency: An Introduction process는 자신이 CPU와 memory를 소유하고 있다는 illusion을 가지고 있었고 single point of execution을 가졌다. thread는 single running process에 대한 새로운 abstraction이다. thread는 multiple execution flow를 가진다. multi-threaded program은 하나 이상의 point of execution을 가지며 여러 개의 PC를 가지고 있다. 하지만 address space는 공유한다. Context Switch Between Threads 각 thread는 자신만의 PC와 register set을 가지고 있다. 각 thread의 상태를 나타내기 위해 하나 이상의 thread control block(TCB)가 필요하다. running하고 있는 두 thread 사이의 switch를 할 때에는 한 t

kongkong2

Compare and Swap(CAS) 은 동시 알고리즘을 설계할 때 사용되는 기술입니다. 멀티 쓰레드 환경, 멀티 코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는게 아닌, 각 CPU의 캐시 영역에서 메모리를 값을 참조하게 됩니다. 이때, 메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우가 있습니다. (이를 가시성 문제라고 합니다.) 그래서 사용되는 것이 CAS 알고리즘입니다. 현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고, 일치 하지 않는 다면 실패하고 재시도를 합니다. 이렇게 처리되면 CPU캐시에서 잘못된 값을 참조하는 가시성 문제가 해결됩니다. 적용 두 개의 스레드가