Distributed System 11

Coordination

전 글에 이어서 coordination에 대해 더 알아보겠다.

 

분산 시스템에서 여러 프로세스가 특정 자원에 대한 독점적 접근을 원할 때, 각 프로세스는 다른 프로세스와 동시에 해당 자원에 접근하지 못하도록 상호 배제(Mutual exclusion)이 필요하다.

• 허가 기반 해결 방법(Permission-based solution): 프로세스가 자신의 임계 영역에 들어가거나 자원에 접근하기를 원할 때, 다른 프로세스들로부터 허가를 받는 방식이다.
• 토큰 기반 해결 방법(Token-based sloution): 공유 자원에 접근할 수 있는 권한을 나타내는 토큰을 소유한 프로세스만 자원에 접근 가능한 방식이다. 토큰을 가진 프로세스만 접근 권한을 가지므로 상호 배제가 보장된다.

---

Permission-based solution

Centralized Algorithm

 

상호 배제를 위해 중앙 집중식 관리자(coordinator)를 사용한다.

 

(a) 프로세스 P1이 공유 자원에 접근하기 위해 관리자에게 허가를 요청한다. → 관리자가 허용한다.

(b) 같은 자원에 접근하려는 다른 프로세스 P2가 허가를 요청한다. → 하지만 P1이 사용 중이기 때문에 관리자는 답변하지 않는다.

(c) P1이 자원 사용을 완료하고 자원을 해제하면 괄리자에게 이를 알린다. → 관리자는 P2에게 자원 접근을 허가하는 응답을 보낸다.

 

하지만 관리자를 사용하는 상호배제 방식에도 문제점이 존재한다.

• 관리자는 단일 실패 지점(single point of failure)이기 때문에, 관리자가 장애를 일으키면 전체 시스템이 중단될 위험이 있다.
• 프로세스가 요청을 보낸 후 block 상태로 들어가게 되는데, 이 경우 관리자가 장애를 일으켜도 "허가 거부"와 구분할 수 없는 문제가 발생한다. 두 경우 모두 응답이 오지 않기 때문이다.
• 큰 시스템에서는 단일 관리자가 병목현상을 발생시킬 수 있다. 

---

Ricart and Agrawala's Distributed Algorithm

 

Ricart와 Agrawala의 알고리즘은 앞서 배운 Lamport의 알고리즘과 유사하지만, 승인 응답을 따로 보내지 않는다.

대신, 모든 이벤트에 대해 전체 순서가 필요하다. 즉, 모든 이벤트 쌍에 대해 어느 이벤트가 먼저 발생했는지 명확하게 구분되어야 한다.

 

프로세스가 공유 자원에 접근하려고 할 때,

• 자원의 이름, 자신의 프로세스 번호, 현재 (논리적) 시간을 포함한 메시지를 작성한다.
• 이 메시지를 자신을 포함한 모든 다른 프로세스에 보낸다. 

다른 프로세스로부터 요청 메시지를 받은 경우, 수신 프로세스는 다음과 같이 행동한다.

• 수신자가 자원에 대한 관심이 없는 경우, 요청을 보낸 프로세스에 OK메시지를 반환하여 자원 접근을 허가한다.
• 수신자가 이미 자원에 접근 중인 경우, 별도의 응답을 보내지 않고, 해당 요청을 대기열에 추가하거나 나중에 처리한다.
• 수신자가 자원 접근을 원하지만 아직 접근하기 않은 경우, 수신자는 들어온 메시지의 타임스탬프와 자신의 타임스탬프를 비교한다. 타임스탬프가 가장 낮은 프로세스가 자원 접근의 우선권을 가지게 된다.

 

(a) 두 개의 프로세스가 공유 자원을 동시에 접근하고 싶어한다. 각 화살표의 숫자는 논리적 시계를 뜻한다.

(b) P0가 가장 작은 타임스탬프 값을 가지고 있으므로, 우선권을 가진다. 이때, P1은 P2에도 OK 메시지를 반환하지만 P2는 모두에게서 승인 받지 못했으므로 임계 구역에 진입하지 못한다.

(c) P0가 자원 사용을 완료하면, P2에게 OK 메시지를 반환한다.

 

이 알고리즘에도 문제점이 존재한다.

• 이 알고리즘은 모든 프로세스가 서로에게 의존하므로, 각 프로세스가 잠재적인 실패 지점이 된다.
• 어떤 프로세스가 충돌하면 요청에 응답하지 않게 되며, 이는 다른 프로세스들이 응답이 없는 상태를 "허가 거부"로 잘못 해석하게 한다. 이로 인해 모든 프로세스가 임계 영역에 진입하려는 시도가 차단된다.

수신자가 허가를 부여하든 거부하든 항상 응답을 보내도록 하는 방식이 해결책이 될 수 있다.

각 요청을 멀티캐스트 방식으로 보내 통신이 보다 효율적으로 이루어지게 하며, 각 프로세스는 그룹 멤버십 목록을 자체적으로 유지해야한다. 모든 프로세스가 공유 자원에 관한 결정에 참여해야하며, 이는 자원이 제한된 장치에서 처리 부담이 될 수 있다.

---

Token-based solution

토큰이 논리적 링 구조로 조직된 프로세스들 사이에서 순차적으로 전달되며, 토큰을 소유한 프로세스만 (진입을 원할 경우에) 임계 영역에 진입할 수 있다.

여기서 논리적 링을 순환하는 토큰은 오버레이 네트워크에 구성된다.

---

Token Ring Algorithm

 

프로세스가 어떻게 조직되는지에 따라,

• 각 프로세스가 자원에 접근할 기회를 공정하게 가질 수 있으며, 이를 통해 기아 상태가 발생하지 않도록 할 수 있다.
• 여러 프로세스가 서로의 진행을 무기한 기다리는 교착 상태(deadlock)를 쉽게 방지할 수 있다.

하지만 프로세스가 충돌하면서 토큰이 사라지는 경우가 발생할 수 있다.

---

Election Algorithm

 

Election Algorithm은 동적인 coordination을 사용한다고 보면된다.

알고리즘 실행을 위해 특정 프로세스가 관리자 역할을 한다. 여기서 특별한 프로세스를 동적으로 선택하는 방법이 핵심이다.

 

많은 시스템에는 관리자가 수동으로 지정되지만, 이는 중앙 집중식 해결법을 초래하며, 단일 실패 지점이 발생할 수 있다.

따라서 이 알고리즘에서는 리더를 선출하는 작업을 수행한다.

 

Election 알고리즘에서는 몇가지 전제가 존재한다.

• 모든 프로세스는 고유한 ID를 가지고 있다.
• 모든 프로세스는 시스템 내 모든 프로세스의 ID를 알고 있지만, 각 프로세스가 현재 활성 상태인지 비활성 상태인지는 알지 못한다.
• 선출 과정은 가장 높은 ID를 가진 활성 프로세스를 식별하는 것을 의미한다.

이 선출 알고리즘도 두 가지의 알고리즘으로 나뉜다.

 

Bully Algorithm은, 모든 프로세스가 다른 모든 프로세스의 ID와 주소를 알고 있어야 한다는 가정을 한다.

Bully algorithm

 

N개의 프로세스가 있고, 각 프로세스는 P0 ... P(N-1)로 구성되어 있다. 각 프로세스 Pk의 ID는 k로 정의된다.

특정 프로세스 Pk가 관리자가 더 이상 요청에 응답하지 않는 것을 감지하면, 선출 절차를 시작한다.

Pk는 자신보다 높은 ID를 가진 모든 프로세스에게 ELECTION 메시지를 보낸다.

 

만약 아무도 응답하지 않으면, Pk는 선출에서 승리하여 새로운 관리자가 된다.

만약 상위 프로세스 중 하나가 응답하면, 그 상위 프로세스가 선출을 맡게 되고, Pk의 역할은 종료된다.

 

위 그림에서는 선출 절차를 시작한 P4에게 P5와 P6가 응답을 줬다.

그러므로 P5와 P6가 각각 자신보다 높은 프로세스에게 ELECTION 메시지를 보낸다.

P5의 요청에는 P6가 응답을 줬기 때문에 P5의 역할은 종료가 되고, P6는 P7에게 응답을 받지 못했기 때문에 자신이 관리자가 된다.

 

Ring-based Election Algorithm은, 각 프로세스가 바로 인접한 이웃 프로세스의 주소만 알면 된다.

Ring-based Election

 

프로세스의 우선순위는 논리적 링으로 구성하여 결정된다. 여기서 가장 높은 우선순위를 가진 프로세스가 관리자로 선출된다.

어떤 프로세스라도 선출을 시작할 수 있으며, 이때 자신의 후속 프로세스(successor)에게 선출 메시지를 보낸다.

만약 후속 프로세스가 비활성 상태라면, 메시지는 다음 후속 프로세스로 전달된다.

메시지가 전달될 때, 전송한 프로세스는 자신의 ID를 리스트에 추가한다. 만약 메시지가 다시 초기 프로세스로 돌아오면, 모든 프로세스가 자신을 알릴 기회를 갖게 된다. 그 후, 초기 프로세스는 링을 따라 모든 활성 프로세스의 목록을 담은 관리자 메시지를 보낸다.

이 리스트에서 가장 높은 우선순위를 가진 프로세스가 관리자로 선출된다.

 

위 그림에서는 P6이 선출을 시작했으며, 메시지가 한바퀴 돌아 자신에게 돌아왔다.

리스트에서 P6이 가장 우선순위가 높으므로, P6는 관리자가 된다.

 

Elction Algorithm in Wireless Network

무선 네트워크에서의 선출 알고리즘의 작동 방식이다.

무선 애드혹 네트워크에서 리더를 선출하기 위해, 소스(source)라 불리는 임의의 노드가 선출을 시작할 수 있다.

소스 노드는 ELECTION 메시지를 자신의 연결된 이웃노드들에게 전송하며 선출을 시작한다.

노드가 ELECTION 메시지를 처음 수신하면, 메시지 발신자를 부모로 지정하고, 이후 부모를 제외한 모든 이웃 노드에게 메시지를 전송한다.

무선 네트워크에서의 선출 알고리즘

 

위 그림에서는, b 노드가 선출을 시작했다.

g노드가 b에게서 메시지를 처음 수신했고, e노드가 g에게서 메시지를 처음 수신했다. 이후 우선 순위가 가장 높은 h 노드가 관리자가 된다.

---

분산처리 중간고사 역시 만족할만한 성적을 받았다.

과제를,, 좀 말아먹은게 문제인 것 같다만,, 어떻게든 복구했다 치고 다시 기말을 향해 가보자궁

 

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **