62_교착 상태 처리(Deadlock Handling)와 선출 알고리즘(Election Algorithm)

62_교착 상태 처리(Deadlock Handling)와 선출 알고리즘(Election Algorithm)

 

교착 상태 방지와 회피 알고리즘은 분산 시스템에서 자원들 간의 전역 순서화를 정의함으로써 자원 순서와 교착 방지 기법을 분산환경에 적용할 수 있다.

 

[교착 상태 방지와 회피(Deadlock Prevention and Avoidance)]

교착 상태 방지 기법은 다음 두 가지로 분류 된다.

• Wait-Die 기법 : 비선점 기법에 기반을 둔다. P1가 보유한 자원을 프로세스P2가 요청 할 때 P2가 P1보다 더 작은 타임스탬프를 가진 경우에만 기다리는 것이 허용된다. 그렇지 않은 경우 P2는 롤백한다.
• Wound-Wait 기법 : 선점 기법에 기반을 두며 wait-die 기법과는 상반된 특징을 가지고 있다. P2가 P1이 사용중인 자원을 요청할 경우 P2는 P1보다 타임스탬프가 클 때 기다리는 것이 허용 된다. 그렇지 않으면 P1은 롤백 된다.

 

두 기법 모두 롤백되는 프로세스에게 새로운 타임 스탬프를 다시 할당하지 않음으로써 기아 상태를 방지 할 수 있다. 타임스탬프는 항상 증가되므로 롤백되는 프로세스는 결국 가장 작은 타임 스탬프를 가지게 된다. 따라서 다시 롤백되지 않는다.

 

Wait-Die 와 Wound-Wait 차이점

Wait-Die	Wound-Wait
오래된 프로세스는 새로운 프로세스가 자원을 방출하기를 기다려야 한다. 따라서 프로세스가 오래되면 오래될수록 더 많은 시간을 기다리는 경향을 보인다.	오래된 프로세스가 결코 새로운 프로세스를 기다리지 않는다.
프로세스 P1가 프로세스 P2에 의해 점유된 자원을 요청해서 롤백되었다면 프로세스 P1는 다시 시작할 때 전과 같은 요청을 다시 행한다. 재요청시에 자원이 P2에 의해 점유되어 있으면 P1는 다시 롤백된다. 따라서 자원을 획득하기 전에 여러 번 롤백 될 수 있다.	프로세스 P2는 P1가 점유한 자원을 요청하면 P1가 자원을 방출하고 롤백된다. 이후 P1가 다시 시작해서 P2에 의해 점유된 자원을 요청하면 P1는 자원을 기다리는 상태가 된다. 따라서 롤백되는 경우가 적게 발생 한다.

 

이 두 가지의 가장 큰 문제점은 불필요한 롤백이 발생하는 것이다.

 

[교착 상태 탐지(Deladlock Detection)]

교착 상태 방지 알고리즘은 교착 상태가 발생하지 않았음에도 자원을 선점한다. 이러한 불필요한 선점을 방지 하기 위해 교착 상태 탐지 알고리즘을 사용한다.

 

분산 시스템에서 교착 상태 탐지를 위해 고려되어야 하는 중요한 문제는 대기 그래프를 어떻게 유지하는가이다.

 

어떤 지역 대기 그래프가 사이클을 가지면 교착 상태가 발생했음을 의미 한다. 그러나 역으로 어떤 지역 대기 그래프에서 사이클이 없다는 사실이 교착상태가 없다는 것을 의미하지는 않는다. 교착상태가 발생하지 않았음을 증명하기 위해서는 모든 지역 대기 그래프의 합집합에 사이클이 없음을 보여주어야 한다.

 

중앙 집중식 접근 방식에는 전역 대기 그래프가 모든 지역 대기 그래프의 합으로 이루어진다. 전역 대기 그래프는 교착 상태 탐지 코디네이터(Deadlock detection coordinator) 역할을 담당하는 단일 프로세스에 의해 유지된다.

 

중앙 집중식의 대기 그래프가 구성되는 시점은 다음 3가지가 있다.

• 지역 대기 그래프에서 새로운 간선이 삽입되거나 제거될 때마다
• 주기적으로 대기 그래프에서 많은 변화가 일어났을 때
• 코디네이터가 사이클 탐지 알고리즘을 수행할 필요가 있을 때마다

 

 

교착 상태 탐지 알고리즘이 수행되면 코디네이터는 전역 그래프를 탐색한다. 만약 사이클이 발견되면 롤백 될 희생자가 선택된다. 이후 코디네이터는 모든 사이트에게 특정 프로세스가 희생자로 선택되었다는 사실을 알려 주어야 한다. 그리고 사이트들은 희생자를 롤백한다.

1. 간선이 지역 대기 그래프에 삽입되거나 제거될 때마다 지역 사이트는 지역 그래프의 변경 사실을 알리는 메시지를 코디네이터에게 보내야만 한다. 이런 메시지를 받게 되면 코디네이터는 자신의 전역 그래프를 수정한다.
2. 한 지역 사이트가 여러 번의 그래프 변경 사실을 하나의 메시지에 담아 주기적으로 보내게 할 수도 있다.
3. 실제로 발생하는 모든 교착 상태를 탐지하고 거짓 교착 상태는 탐지하지 않는다. 거짓 교착 상태의 보고를 방지하기 위해서는 다른 사이트로부터 요청 메시지에 고유의 식별자(타임스탬프)가 붙어 있어야 한다.

 

탐지 알고리즘은 다음과 같다.

1. 코디네이터는 시스템 내의 모든 사이트에 초기화 메시지를 보낸다.
2. 이 메지시를 받으면 각 사이트는 자신의 지역 대기 그래프를 코디네이터에게 보낸다.
3. 코디네이터가 각 사이트로부터 회신을 받으면 전체 그래프를 구성 한다.
4. 구성된 그래프에 사이클이 있다면 시스템은 교착 상태에 있다고 볼 수 있다.

 

그래프에 사이클이 없다면 적어도 1단계에서 코디네이터에 의해 초기화 메시지가 보내진 후 탐지 알고리즘이 수행되는 동안에 교착 상태가 발생하지 않았음을 보장할 수 있다.

 

 

[완전 분산형 접근(Fully Distributed Approach)]

완전 분산형 교착 상태 탐지 알고리즘에서는 모든 사이트가 교착 상태 탐지에 대한 동등한 역할을 한다. 이 기법에서는 모든 사이트가 전체 그래프의 일부를 표현하는 대기 그래프를 동적으로 구성한다.

 

교착 상태가 존재하면 부분 그래프 중에서 적어도 어느 하나에는 사이클이 존재하도록 하는 것이 이 기법의 기본 원리이다.

 

각 사이트는 자신의 지역 대기 그래프를 유지하는데 지역 대기 그래프는 특수한 노드를 포함하는 것으로 앞에서 설명한 지역 그래프와는 다르다. 임의의 프로세스가 점유하고 있을 동안 다른 사이트의 한 자원을 기다린다면 간선 지역 대기 그래프에 표시 된다. 마찬가지로 현재 자신의 지역 사이트에 의해 점유되어 있는 자원을 다른 사이트의 프로세스가 기다리고 있다면 지역 대기 그래프가 표시 된다.

 

 

[선출 알고리즘(Election Algorithm)]

분산 알고리즘들은 시스템 내의 다른 프로세스들과의 공동 작업을 위해 필요한 기능을 담당하는 코디네이터 프로세스(coordinator process)를 가지고 있다. 상호 배재의 보장, 교착 상태의 탐지를 위한 전역 대기 그래프의 유지, 분실된 토큰의 재생성, 그리고 시스템 내의 입/출력 장치의 제어 등이 코디네이터 프로세스의 역할에 포함 된다.

 

사이트의 결함으로 코디네이터 프로세스의 수행이 불가능해지면 다른 사이트에 코디네이터 기능을 이전시킴으로써 시스템을 계속 작동시키는데 선출을 결정하는 알고리즘을 선출 알고리즘이라고 부른다. 이 선출 알고리즘에서는 시스템 내에서 활동하는 각각의 프로세스에 고유의 우선순위가 할당되어 있다고 가정한다.

 

코디네이터는 항상 큰 우선순위 번호를 가진 프로세스이다. 따라서 코디네이터에 결함이 발생하면 알고리즘은 활동중인 프로세스 중에서 우선순위가 가장 큰 프로세스를 선출해야 하고 이 번호는 시스템 내의 모든 활동중인 모든 프로세스에게 보내야 한다. 또한 이 알고리즘은 결함으로 복구된 프로세스가 현재의 코디네이터를 알 수 있는 방법도 제공해 주어야 한다.

• Bully 알고리즘 : 이 알고리즘을 끝낸 프로세스는 코디네이터로 선출되었음을 의미하고 우선순위가 가장 높다. 이 프로세스는 낮은 우선순위를 가진 모든 활동하는 프로세스에게 자신의 순위 번호를 알려준다. 고장난 프로세스가 복구되면 같은 알고리즘을 수행한다. 자신보다 높은 순위 번호의 프로세스가 없으면 현재 낮은 순위의 코디네이터가 있더라도 자신이 코디네이터가 된다는 사실을 알려주어야 한다.
• Ring 알고리즘 : 링크는 단방향이며 프로세스는 자신의 오른쪽 프로세스에게만 메시지를 보낸다. 이 알고리즘에 사용되는 자료구조는 활동 리스트(active list)인데 이 리스트는 알고리즘일 끝날 때 시스템 내의 활동하는 모든 프로세스의 우선순위 번호를 가진다. 각 프로세스는 자신의 활동 리스트를 유지하고 연산을 수행 한다. 이 알고리즘은 고장난 프로세스가 복구되었을 때 현재 코디네이터 프로세스의 순위를 결정하는 방법을 규정하지는 않는다. 한 가지 해결방법은 복구된 프로세스가 코디네이터에게 메지시를 보내 코디네이터가 자신의 번호를 수록한 응답을 보내도록 한다.

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사