[OS/OSTEP] 32.threads-bugs, DeadLock(교착상태), 원자성 위반(atomicity violation), 순서 위반(order violation),

[OS/OSTEP] 31.threads-semaphore, 세마포어, 세마포어로 락 구현, 컨디션 변수로서의 세마포어, 생산자/소

 

 

[OS/OSTEP] 32.threads-bugs,

# 시작하며

 어느덧 쓰레드 단원의 마지막 포스팅이다. 글을 쓰며 정리하기 전까지만 해도 둥둥 떠다니는 개념들이 난잡하게 섞여서 정리되지 않았는데 지금은 어느정도 정리가 된 듯 하다. 시험 범위는 이 다음 챕터인 파일까지이기 때문에 앞으로 몇개를 더 포스팅해야 할 것 같기는 하다. 교수님께서 내주시는 퀴즈를 어떻게 어떻게 풀어 왔지만, 어느정도 개념이 정립된 지금 퀴즈를 다시 풀어볼 생각이다.

 

# 병행성 관련 오류

 지금까지 공부하면서 교착상태(DeadLock)상태가 발생할 수 있다는 사실을 알았기 때문에 쓰레드를 wait하기전에 가진 lock을 반납하도록 했었다. 그러나 우리가 사용하는 응용프로그램들은 또는 라이브러리들은 캡슐화가 되어 있기 때문에 어떤 락을 어디서 사용하는지 잘 알지 못하는 것이 사실이다. 나아가 이번 단원에서는 병행쓰레드를 사용하면서 생기는 오류의 대부분은 이러한 DeadLock이 유발하는 오류들은 적고, 사용자가 코드를 잘못 작성하여 임게영역을 보호하지 못하는 경우가 대부분이라고 한다. 여튼 어떤 오류가 발생하고 그러한 오류를 해결하기 위해서는 어떻게 해야하는지를 살펴보도록 하자.

 

# 오류의 종류

 병행성 오류들에는 어떤 것들이 있을까? 교과서에는 실제 사용되는 오픈소스 프로그램을 활용하여 오류들과 오류들의 빈도를 알아보았다. MySQL, Apache, Mozilla, OpenOffice가 그 대상군 이었다. 아래의 오류 통계를 살펴보면 총 105개의 오류가 있었고, 74개의 오류는 교착상태와 무관한 오류 있다.

 여기서 발생한 오류들을 교착상태(DeadLock)과 비교착상태(NotDeadLock)로 구분지어 원인을 분석해보도록 할 것이다. 교착상태를 예방하는 방법에는 예방(prevention)과 회피(avoidence)과 있음을 미리 알고 있으면 좋을 것이다.

 

# 비교착 상태 오류 - Not Dead Lock

 교착상태에서 발생하지 않는 오류를 살펴 보자. 비교착상태오류는 대표적으로 원자성 위반(atomicity violation)와 순서 위반(order violation)오류가 있다.

 

## 원자성 위반 오류 - atomicity violation

 원자적인 상황이지만 원자적이게 해결하지 않아서 생기는 오류이다. MySQL에서 발견한 간단한 예제를 살펴보자

 두개의 T1, T2쓰레드가 각각 존재한다. T1쓰레드는 생성한 쓰레드의 proc_info가 NULL인지 검사하고, 새로운 값을 넣는다. T2는 prco_info를 null로 만든다. 즉 T1의 4번라인 fputs()은 null인지 체크 후 null이 아닐때만 실행 되도록 해야한다. 지금까지 공부해왔던 것을 바탕으로 lock을 통해서 임계영역을 분리해 atomic하게 코드가 돌아가야 한다는 필요성을 느낄것이다. 빨간색으로 써놓은 것과 같이 2번이 실행 후 NULL이 아님을 체크했지만 인터럽트가 걸리면서 T2가 proc_info를 NULL로 바꾸게 된다면 원치 않는 상황이 펼쳐 질 것이다.  

### 해결

 간단히 락을 통해 임계영역으로 분리시켜버리자, 그렇다면 중간에 인터럽트가 걸리더라도 lock이 없기 때문에 쓰레드가 락을 반납할때까지(임계영역의 실행 완료)기다리게 될 것이다.

 

## 순서 위반 오류 - order violation

 앞에서 많이 봤던 parent-child와 같이 특정(parent)쓰레드가 기다(child)려야하는 상황이 분명히 존재 할 것이다.

위 예제에서도 T1과 T2과 존재한다. T2는 이미 쓰레드가 존재한다는 가정하에 실행된다. 그말은 즉 T1쓰레드가 이미 실행을 마친 후 T2의 11번 라인이 실행되어야 한다는 의미이다. 만약 T1이 먼저 실행되지 않았다면 T2는 NULL포인터를 사용하기 때문에 에러가 발생되어 프로그램이 종료될 것이다. 즉 T2가 항상 T1보다 먼저 실행되어 햔다는 순서가 지켜지지 않았다.

 

### 해결

 순서를 강제함으로써 위 문제를 해결 할 수 있다. 지금 껏 많이 사용했던 동기화 방법을 이용하면 될 것이다. 컨디션 변수를 활용하여 위 문제를 해결해보자.

 mtInit이라는 조건을 확인하고 이 조건이 1이 되면 T1이 실행됐다는 증거이다. 물론 세마포어를 활용할 수도 있을 것이다. 여튼 T2가 먼저 실행됐다면 기다리기 위해서 wait가 되고 mtCond이라는 컨디션 변수(큐)에서 대기하고 있게 된다. 그리고 T1이 실행되고 signal을 보내 wait에 깨운 후, mtInit을 다시 검사하고 그 뒷부분이 마저 실행되게 된다. 

 

# 교착상태 오류 - DeadLock

 복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서 교착상태(DeadLock)이라는 고전적인 문제가 발생한다. 즉 락을 어긋나게 소유한 상태로 어긋난 락을 반납하기를 기다리고 있기 때문에 결국 아무것도 실행되지 못하는 상태이다. 

T1 쓰레드는 L1락을 가지고 L2락을 가지려 하지만 T2가 이미 락을 가지고 있기 때문에 기다린다. T2역시 L2락을 가지고 있지만 L1락을 T1이 가지고 있기 때문에 기다리고 있는다. 결국 서로 기다리다가 끝나버린다. 상대방이 소유하고 있는 락을 대기하고 있기 때문에 누구도 실행 할 수 없게 된다. 이러한 사이클의 존재는 교착상태 발생 가능성을 야기한다.

 

# 교착 상태는 왜 발생하는가?

 쓰레드1과 2가 같은 순서로 락을 획득한다면 교착상태는 절대 발생하지 않을 것이다. 코드가 많아지면서 구성 요소간에 복잡한 의존성이 알게 모르게 생겨나게 되기 때문에 생긴다. 또한 캡슐화(encapsulation)의 성질 때문이다. 상세한 구현 내용을 감추게 되면서 그 안의 내용을 알 수 없기때문에 생겨난다. 

 위의 예와 같이 v1과 v2를 더하는 간단한 AddAll이라는 함수는 캡슐화 되어 있다. v1과 v2를 더하기 위해서는 각 벡터를 락으로 보호해야 한다. 그렇지 않으면 더하는 도중에 다른 코드가 해당 값을 건들여 버릴 수 도 있을 것이다. 그래서 AddAll은 v1에 대한 락을 획득하고 v2에 대한 락을 획득하게 코드가 짜여졌을 것이다. 이렇게 되면 문제 없어 보이지만 다른 쓰레드에서 v2.AddAll(v1)을 실행 했을때는 교착 상태의 발생 가능성이 있음을 짐작 할 수 있다. 

 

# 교착(DeadLock) 상태 발생 조건

 교착상태(DeadLock)이 발생하는 조건은 아래의 4가지 조건이 모두 충족되어야 한다는 것이다. 좋은 점은 4가지 중 한가지 요소만 제거시켜도 교착상태(DeadLock)이 발생하지 않는다는 것이다.

 

# 교착상태 예방 - prevention

## 순환 대기(Circular wait) 없애기

 교재에서 말하기로는 가장 실용적인 교착 상태 예방법 이라고 한다. 순환대기가 절대 발생하지 않도록 락 코드를 작성하는 것이다. 이말은 즉슨 위에서 봤던 의존그래프를 깨버리는 것이다. 서로가 어긋나게 락을 획득하고 기다리고 있는 순환의 구조를 없애자.

 전체 순서(total ordering)을 정의 함으로써 L1을 무조건 L2전에 획득하도록 정의 시킨다. 또는 부분 순서(parial ordering)을 제공하는 것인데, 교수님께서는 비슷한 개념이라고 하셨다.

락의 주소값을 활용함

위 처럼 락을 얻는 순서자체를 획일화 시켜 버리자. 

아까 봤던 벡터간 AddAll에서 v2.AddAll(v1)을 하면 문제가 발생한다 했지만, 위의 예처럼 락을 자체적으로 동일한 순서를 주어 얻도록 하는 것이다. 

 

## 점유 및 대기 ( Hold-and-Wait) 없애기

 교착 상태가 발생하는 조건인 점유 및 대기는 원자적으로 모든 락을 단번에 획득하도록 하면 예방 할 수 있다. 위 순환대기에서는 2개의 락을 얻는 순서를 동일시 시켜지만, 이번예제에서는 2개의 락을 얻는 과정을 하나의 원자적인 과정으로 만드는 것이다.  락을 가지고(Hold) 기다리는(Wait)하는 경우가 없어질 것이다. 이렇게 바꾸게 된다면, 큰 그림에서 보면 락을 가지거나 가지지 못하는 두가지의 상황만이 존재 할 것이다.

위 예에서는 prevention이라는 락을 만들어 사용하여 두개의(L1,L2)락을 얻는 과정을 원자적으로 만들었다. 그러나 이 해법에는 문제점이 많다. 캡슐화 되어 필요한 락들을 정확하게 파악하기 힘들고, 락이 실제 필요할때 요청하는 것이 아니라 미리 모든 락들을 한번에 획득하기 때문에 병행성이 저하되는 문제가 생긴다.

 

## 비선점(No Preemption) 없애기

 락을 이미 보유한채로 다른 락을 대기하고 있기 때문에 교착상태(DeadLock)이 발생했다. 그렇다면 L1,L2두개의 락을 가져야하는 쓰레드가 L1락을 가지고 L2락을 가지지 못한다면, L1락을 반납해버리면 되지 않을까? 이 비선점 방식이 그러하다. 락을 선점하고 있지 않는다는 것이다. trylock()루틴을 활용한다.. 해당 코드를 사용하면 락을 획득하거나 락을 획득하지 못하면 -1을 반환한다.

그러나 이 부분도 문제점은 존재한다. 순서가 정확히 계속 맞아 떨어진다면, 무한반복(live lock)의 여지가 발생한다. 그에 대한 해법으로는 반복문에 지연시각을 무작위로 조절하는 것이다. 병뚜껑을 돌릴때 속도를 달리해서 몇번 돌리다보면 언젠간 들어맞아 뚜겅이 닫히게 되는 것과 비슷하다. 

 

## 상호배제 ( Mutual Exclusion) 없애기

일반적인 코드는 모두 임계영역을 포함하고 있기 때문에 락을 사용했고 그러면서 교착상태(DeadLock)문제가 발생했다. Herlihy라는 사람은 대기없는(wait-free) 자료 구조를 고안했다. 명시적인 락이 필요없는 하드웨어 명령어를 사용하여 자료 구조를 만들면 된다는 것이다.

락을 획득하고 값을 갱신한 후에 락을 해제하는 대신에, Compare-And-Swap이라는 원자적인 명령어를 통해서 갱신하도록 만든다.

조금더 복잡한 문제를 살펴보자, 리스트에 삽입 예제를 생각해 볼 것이다.

위 삽입 예제를 간단히 도식화 하면 위 그림과 같을 것이다. 전형적인 락방식을 이용해서 구현했다. 

 이 코드는 next 포인터가 현재의 헤드를 가리키도록 갱신하고 새로 생성된 노드는 리시트의 헤드가 되도록 동작한다. 이 코드를 처리하는 도중 만약 어떤 쓰레드가 새로운 헤드를 성공적으로 추가하였다면, 이 Compare-And-Swap는 실패한다. 쓰레드는 삽입과정을 재 시도할 것이다.

 

# 스케줄링으로 교착 상태 회피하기 - Avoidence

어떤 시나리오에서는 교착 상태를 예방하는 대신 회피(avoidence)하는 것이 더 유용할 때가 있다. 회피하기 위해서는 실행 중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해서 전번작으로 파악하고 있어야 하낟. 그것을 바탕으로 쓰레드들을 스케줄링하여 교착상태가 발생하지 않도록 보장한다.

위와 같이 각각의 쓰레드들이 L1,L2락에 접근하게 되는 경우를 생각해본다. T1과 T2과 동시에 실행되지 않도록 하면 될 것이다.

또 다른 예시를 봐보자.

그러나 위와 같이 전체 작업이 끝나기까지 상당히 오랜 시간이 걸린다. 성능하락이 수반되는 것은 어쩔 수 없다.

 

# 발견 및 복구

 교착 상태를 발견하면 복구토록 하는 방법이다. 교착 상태(DeadLock)이 아주 가끔 발생한다면, 1년에 한번씩만 발생한다면, 재부팅하여 해결 할 수 있을 것이다.

 그러나 DB를 관리하는 서버에게는 아주 치명적일 수 있다. 이럴 경우 현재 DeadLock이 난 상태를 분석하고 해결하는 아법이 필요하다.