Lock-free VS Wait-free

 

 

 

 

 

일단 Lock-Free와 Wait-Free의 상관관계를 보면 위와 같이 포함관계이다.

즉 모든 Wait-Free는 Lock-Free라고 볼 수 있다.

 

 

 

 

 

 

 

 

 

1. Lock-Free Algorithm

여러개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘을 말한다.가 보통의 번역이고 이걸 조금 풀어서 설명하자면

 

- 멀티쓰레드에서 동시에 호출해도 정확한 결과를 보증함.

- non-blocking으로 동작함.

- lock을 사용하지 않아야한다.

- 호출이 다른 쓰레드와 충돌하였을 경우, 적어도 하나의 승자가 있으며 그 승자 쓰레드는 딜레이 없이 완료된다.

 

 

 

 

즉, Lock을 사용해도 Lock-Free가 아니며, 

 

while (dataReady == false)

{

temp = g_data;

}

위 코드처럼 dataReady값이 언제 바뀔지 모르는 알고리즘의 경우 Lock-Free라고 할 수 없다.

 

 

자, 그러면 우리가 흔히 예로 드는 ABA Problem을 가진 Lock-Free Stack의 경우 (ABA Problem을 해결했다고 가정하자)

내부적으로 while 문이 돌면서 체크를 하는데, 이것은 왜 Lock-Free인것인가?

Lock-Free도 while loop는 허용한다. 다만 전체 쓰레드를 봤을 때 상수시간동안 반드시 하나 이상의 메소드가 종료해야 한다는 조건이 붙는다.

while의 조건이 위와 어디서 바뀔지 모르는 상황에는 언제 해당 동작이 완료될지 알수 없지만,

 

 

 

do

{

tempTop = m_currentTop;

newTop = tempTop->next;

}

while ( CAS(m_currentTop, tempTop, newTop));

위와 같이 다른 스레드의 방해가 없다면 언젠가는. 적어도 하나의 스레드는 바로 수행할 수 있는 while문의 경우 Lock-Free에 부합한다 할 수 있다.

다른 스레드의 방해가 없다면에서 알 수 있듯이, 이 알고리즘의 경우 다른 스레드가 계속 방해한다면 기아가 발생하여 계속적으로 수행을 실패하고 loop를 도는 스레드가 발생할 것이다.

 

 

 

 

 

 

 

 

 

 

 

2. Wait-Free Algorithm

그렇다면 Wait-Free는 무엇인가. 간단히 말하자면 바로 위에서 밑줄친 다른 스레드의 방해가 없다면 이 해결된 알고리즘이라고 볼 수 있다.

결과적으로 더 좋은 알고리즘이라고 할 수 있는것이다.

 

일단, Lock-Free와는 포함관계에 있으므로 모든 Wait-Free는 Lock-Free라고 볼 수 있다.

그러하므로 Lock-Free가 가지는 모든 조건을 만족해야 하며

여기에 추가적으로 다른 스레드와 충돌해도 모두 delay없이 완료되어야 한다는 조건이 붙는다.

Wait-Free의 경우에도 당연 while loop를 허용할것이다. 하지만 Lock-Free가 다른 스레드에 의해 방해 받아 기아 상태가 발생하는 반면,

Wait-Free는 상수 번 루프를 돌면 반드시 루프를 종료해야한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[참고]

http://www.slideshare.net/zzapuno/kgc2013-3