deadlock 문제를 식별하고 관리하는 방법을 살펴보기 전에, 먼저 POSIX mutex lock를 사용하서 멀티스레드 Pthread 프로그램에서 deadlock이 발생하는 방법을 설명한다. pthread_mutex_init() 함수는 unlock된 mutex를 초기화한다. 뮤텍스 락은 pthread_mutex_lock()과 pthread_mutex_unlock()을 사용하여 획득하고 해제한다. 만약 스레드가 lock된 뮤텍스를 얻으려고 하면, pthread_mutex_lock() 호출은 뮤텍스 락의 소유자가 pthread_mutex_unlock()을 호출할 때까지 스레드를 block한다.
다음 예제 코드에서는 두 개의 뮤텍스 락이 생성되고 초기화된다:
pthread_mutex_t first_mutex;
pthread_mutex_t `second_mutex`;
pthread_mutex_init(&first_mutex,NULL);
pthread_mutex_init(&second_mutex,NULL);다음으로, 두 스레드 thread_one과 thread_two가 생성되고, 두 스레드 모두 뮤텍스 락에 액세스할 수 있다. thread_one과 thread_two 각각 그림 8.1에서 보듯이 do_work_one()과 do_work_two() 함수에서 실행된다.
이 예에서, thread_one은 (1)first_mutex, (2)second_mutex 순서로 뮤텍스 락을 얻으려고 시도한다. 동시에, thread_two은 (1)second_mutex, (2)first_mutex 순서로 뮤텍스 락을 얻으려고 시도한다. thread_one이 first_mutex를 획득하는 동안 thread_two가 second_mutex를 획득하면 데드락이 발생할 수 있다.
⇒ 스레드 각각이 첫 번째 뮤텍스를 얻은 상태에서 서로가 두 번째 뮤텍스를 얻기 위해 대기하게 되면 데드락 발생
데드락이 발생할 수 있지만, thread_two가 락을 얻기 전에, thread_one이 first_mutex와 second_mutex에 대한 뮤텍스 락을 획득하고 해제할 수 있으면, 데드락은 발생하지 않을 것이다. 물론, 스레드가 실행되는 순서는 CPU 스케줄러가 어떻게 스케줄링하는지에 달려있다. 이 예는 데드락을 핸들링하는 데 문제를 보여준다: 특정 스케줄링 상황에서만 발생할 수 있는 데드락을 식별하고 테스트하는 것은 어렵다.
8.2.1 Livelock
Livelock은 다른 형태의 liveness failure이다. 이것은 데드락과 유사하다: 둘 다 두 개 이상의 스레드가 진행되지 못하게 하지만, 스레드는 서로 다른 이유로 진행할 수 없다. 데드락은 모든 스레드가 다른 스레드에서만 발생할 수 있는 이벤트를 기다리며 block될 때 발생하는 반면, livelock은 스레드가 실패하는 작업을 지속적으로 시도할 때 발생한다. Livelock은 두 사람이 복도에서 지나가려고 할 때 까끔 발생하는 일과 비슷하다. 한 사람은 오른쪽으로 이동하고. 다른 사람은 왼쪽으로 이동하여, 여전히 서로의 진행을 방해한다. 그런 다음 한 사람은 왼쪽, 다른 사람은 오른쪽으로 이동한다. 그들은 bolck되지 않았지만, 아무런 진전이 없다.
Livelock은 Pthread의 pthread_mutex_trylock() 함수로 설명할 수 있는데, 이 함수는 blocking 없이 뮤텍스 락을 얻으려고 시도한다. 그림 8.2의 코드 예제는 그림 8.1의 예제를 다시 작성하여 이제 pthread_mutex_trylock()을 사용한다.
이 상황은 livelock으로 이어질 수 있다 만약 thread_one이 first_mutex를 얻은 다음, thread_two가 second_mutex을 얻으면. 각 스레드는 pthread_mutex_trylock()을 호출한다. 이 호출이 실패하면, lock을 해제하고, 동일한 행동을 무기한으로 반복한다.
pthread_mutex_trylock(): 이미 누군가가 해당 뮤텍스를 잡고 있으면 즉시 실패 값을 반환
⇒ 그림 8.2의 예제에서 thread_one이 first_mutex를 획득한 뒤 second_mutex를 trylock()으로 얻으려고 시도하고, 실패하면 다시 first_mutex를 풀고 재시도한다. 동시에 thread_two는 second_mutex를 획득한 뒤 first_mutex를 trylock()으로 얻으려다가 실패하면 second_mutex를 풀고 재시도한다.
⇒ 결과적으로 두 스레드는 서로 번갈아 가며 락을 얻었다가 실패하면 다시 풀고 재시도하는 동작을 끊임없이 반복하게 되는데, 이 상태가 바로 livelock이다.
Livelock은 일반적으로 스레드가 동시에 실패한 작업을 재시도할 때 발생한다. 따라서, 일반적으로 각 스레드가 실패한 작업을 랜덤 시간에 재시도하면 피할 수 있다. 이는 정확하게 네트워크 충돌이 발생할 때, 이더넷 네트워크에서 취하는 접근 방식이다. 충돌이 발생한 직후에 패킷을 재전송하려고 시도하는 대신, 충돌에 관련된 호스트는 다시 전송을 시도하지 전에 랜덤 시간 동안 backoff(대기)한다.
이더넷(Ethernet): 컴퓨터 네트워크 기술 중 하나로, 다수의 시스템이 랜선 및 통신포트에 연결되어 통신이 가능한 네트워크 구조
패킷(packet): 네트워크를 통해 전송되는 데이터의 덩어리(조각, 블록, 전송단위...)
Livelock은 데드락만큼 일반적이지 않지만, 동시 애플리케이션을 설계하는데 어려운 문제이고, 데드락과 마찬가지로, 특정 스케줄링 상황에서만 발생할 수 있다.
Deadlock: 스레드들이 서로의 자원을 기다리며 영원히 블록된 상태
Livelock: 스레드들이 블록된 것은 아니지만, 서로 간섭하며 실제 작업을 전혀 진행하지 못하는 상태
