Lock algorithm과 Lock-free algorithm의 다른 점

Lock algorithm과 Lock-free algorithm의 차이점

Lock-free algorithm이란?

여러 개의 쓰레드에서 동시에 호출했을 때, 정해진 단위 시간 마다 적어도 한개의 호출이 완료되는 알고리즘

위의 그림에서 Lock algorithm은 다른 쓰레드를 기다리면서 루프를 돌고 있기 때문에, 운영체제가 Thread 1을 CPU scheduling에서 제외 했다(convoying 으로 인해)고 가정하면, Thread 3과 Thread 4는 Thread 1의 수행이 끝날 때 까지 무한정 기다려야 한다. 하지만, Lock-free algorithm은 비록 Thread 1이 convoying 현상으로 인해 빠져도, Thread 3과 Thread 4는 원래 정해진 단위 시간안에 자신의 호출을 마친다.

멀티코어 또는 멀티CPU 환경에서 공유 데이터를 여러 개의 쓰레드에서 Read and write를 해야할 때는 Lock-free 알고리즘을 써야 한다. 그렇지 않으면, 아래의 이유들로 인해 성능이 현저히 저하된다.

1. 우선순위 역전
2. Convoying
3. 병렬성이 떨어짐