Lock-Free 기초

From DevNote

Contents 1 Intro 2 FAQ 3 Lock-Free에 관해 공부하려면 4 참고 문서와 각주

Intro

언젠가 게임 개발자 커뮤니티에 Lock-Free에 관한 글을 올리자 몇몇 개발자들이 매우 회의적인 반응을 보였다. 뿐만 아니라, 일부는 잘못된 정보를 올리는 사람으로 몰아 붙이려고 하는 것이었다. 많은 개발자들이 Lock-Free에 관해 들어 보지도 못했고 많은 편견을 가지고 있는 것으로 보인다. 아래 FAQ에 Lock-Free에 관해 자주 묻는 몇가지 질문에 대한 답을 달았다. 이것이 Intro를 대신할 수 있을 것이라 생각한다.

FAQ

• Lock-Free가 무엇입니까?

  Lock-Free란 쉽게 말해 Lock이 없다는 것입니다. 따라서 Lock-free를 말하기 전에 우선 Lock 이란 무었인지 알 필요가 있습니다. Lock이란 스레드간 동기화 (synchronization)에서 Mutual Exclusion 을 만들기 위해 사용되는 것을 말한다. 윈도우즈를 예로들면 가장 많이 사용하는 Critical Section 이다. 대부분의 개발자들은 Critical Section에 관해 알고 있으며 직접 사용해 본 경험이 있을 것입니다. 그런데 Lock 을 사용함에 있어 몇 가지 중대한 문제가 발생할 수 있습니다. 그 중 대표적인 것은 Deadlock^[1] 입니다. 두개 혹은 그 이상의 스레드가 서로 상대방이 Lock하고 있는 리소스를 기다리고 있습니다면 이른바 Circular Wait 상태가 되어, deadlock이 발생한다는 것을 알고 있을 것입니다.

  
  

  멀티스레드 프로그램에서 데드락이 발생하면 프로그램 전체가 응답을 하지 않아 더 이상 진행이 불가능한 상태가 될 수 있으며, 이러한 데드락은 소프트웨어 개발 단계에서 발견하기 매우 어렵고 고치기도 쉽지 않습니다. 또 다른 예는 Priority Inversion과 같은 문제입니다. 이것은 우선 순위가 낮은 프로세스나 스레드가 lock을 가지고 있어 우선순위가 높은 프로세스가 진행을 하지 못하고, 낮은 우선 순위의 프로세스에게 CPU를 양보해야만 하는 상황을 말합니다. Priority Inversion은 특히, 실시간 운영체재 (real-time OS)에서 매우 중요한 문제입니다.

  
  

  나사(NASA)의 화성 탐사계획의 일부인 Pathfinder는 Priority Inversion버그로 인해 계속 시스템이 재부팅되는 현상을 보인 것으로 알려져 있습니다. ^[2]

  
  

  또, 시분할 멀티태스킹 시스템에서 Lock을 가진 스레드가 컨텍스트 전환(context switch)으로 인해 다른 스레드에게 CPU를 양보하였고, 이 lock을 기다리는 다른 스레드들이 있다고 한다면, 이들 스레드들은 lock을 가진 스레드가 다시 CPU 시간을 할당받아 lock을 풀어 줄때 까지 아무일도 하지 못하고 기다리게 됩니다.

  
  

  Herlihy 교수는 아래와 같이 lock-free와 wait-free에 관해 정의하고 있습니다.

The lock-free condition guarantees that some 
process will always make progress despite arbitrary halting failures or delays 
by other processes, while the wait-free condition guarantees that all nonhalted 
processes make progress. Either condition rules out the use of critical 
sections, since a process that halts in a critical section can force other 
processes trying to enter that critical section to run forever without making 
progress. [3]

• Lock-Free가 좋다면 왜 모든 프로그램을 Lock-Free로 만들지 않습니까?

  Lock 없이 멀티스레드 프로그램을 하는 여러 방법들이 개발되어 있으나 아직 완벽한 해결책을 제시하지는 못하고 있습니다.

  모든 알고리즘이나 데이터구조가 lock이 없이 스레드 세이프(thread safe)한, lock-free가 될 수 있다면 아주 이상적일 것입니다, 하지만 99%의 경우 lock-free로 만들기 위해 소모되는 노력과 시간에 비해 얻어지는 성능향상은 미미합니다. 따라서 OS의 태스크 스케줄러, 고성능을 요구하는 서버 프로그램의 중요 함수들에서 lock-free 방법이 사용되고 있습니다. 그외에는 Critical Section을 사용하는 것이 이해하기 쉽고 성능에도 별다른 영향이 없습니다.

Lock-Free에 관해 공부하려면

http://erdani.org/publications/cuj-2004-12.pdf

http://erdani.org/publications/cuj-2004-10.pdf

참고 문서와 각주