• Lock-free VS Wait-free

    2016. 10. 19.

    by. bluezc

     

     

     

     

     

    일단 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

     

     

     

     

    'Programming > System' 카테고리의 다른 글

    Lock-free VS Wait-free  (0) 2016.10.19
    ABA Problem  (0) 2016.10.19
    타이머의 해상도  (0) 2014.12.31
    SSE (Streaming SIMD eXtensions)  (0) 2014.07.23

    댓글 0