[CS] 분산 상호 배제 (Distributed Mutual Exclusion)

Distributed Mutual Exclusion

 

분산 시스템에서 여러 프로세스가 공유 자원에 대한 접근을 조율하고, 한 번에 하나의 프로세스만이 해당 자원에 접근하도록 하는 기술이나 알고리즘을 의미한다.

 

다수의 프로세스가 동시에 공유 자원에 접근할 때 충돌이 발생하면 데이터 일관성 문제나 부정확한 결과를 야기할 수 있으며 따라서 이러한 상황을 피하기 위해 상호 배제가 필요하다.

 

특히 분산 시스템의 경우 여러 노드 간의 효율적인 협력이 필요한 환경에서 중요한 역할을 하면서 이를 처리하기 위한 과정이 단일 시스템에 비해서 복잡하다.

 

 

요구사항

리소스에 대한 동시 엑세스 방지 → 분산 시스템의 여러 프로세스는 일부 리소스에 대한 독점 엑세스를 원함

1. Safety : Mutual Exclusion(상호 배제) → Critical Section(임계구역)에는 최대 한 개의 프로세스 접근 허용
2. Liveness : Critical Section에 Enter/Exit가 결국 작동해야 함 → Lock을 보유하는 프로세스가 없으면 Critical Section에 접근 가능
3. Ordering : Fairness(공정성), Happend-before Ordering : 제한된 대기 및 순서대로
4. 메세지 트래픽을 최소화, Synchronization 지연 최소화

 

 

Message Passing을 통해 Mutual Exclusion 해결

1. 가정 : Network는 Reliable하고(메세지가 특정 시점에 결국 도착함), Async하며(시간이 오래걸릴 수 있음) 프로세스는 언제든지 실패할 수 있음
2. 아이디어
   1. Critical Section에 진입하기 전 다른 Process의 Permission을 얻어야 함
   2. Critical Section에서 나가기 이전, 다른 프로세스에게 작업을 마쳤음을 알림
   3. Processor은 자신보다 먼저 허가를 요청한 다른 Professor가 해당 Critical section을 사용하도록 허용함

 

Starvation과 Deadlock

 

https://sjh9708.tistory.com/12

[CS] 멀티 쓰레드 환경에서의 상호 배제(Mutex)와 데드락 (+ C#에서의 적용)

 

분산 시스템에서의 상호 배제 역시 기아 현상과 데드락에 유의해야 한다.

1. Starvation (기아 현상)
   • 리소스 액세스를 요청한 프로세스가 일정한 조건 하에 영원히 리소스를 얻지 못하는 상황
   • 공평한 우선순위 사용으로 기아 현상을 방지할 수 있음
2. Deadlock (교착 상태)
   • 둘 이상의 프로세스 또는 스레드가 서로의 보유한 리소스를 해제하지 않고 대기하고 있어서 전체 시스템이 멈춘 상태

 

---

분산 상호 배제의 알고리즘

 

1. Centralized Algorithm

 

 

Critical Section에 진입 시

1. 중앙 서버(Coordinator)로 Request 전송
2. 서버의 Permission 대기

Critical Section에서 나갈 시

1. 중앙 서버로 RELEASE를 보냄

Server

1. 수신되었지만 OK를 보내지 않은 Request의 Queue가 있음
2. Queue의 선두에 올 때까지 OK를 보내는 것을 지연시킴
3. Release를 얻은 후 Queue에서 프로세스를 제거함

 

장단점

장점

• 코디네이터에 의한 Mutual Exclusion 보장
• 구현이 간단함.
• Fair Sharing (공정성) , Starvation(아사) 방지

1.  

단점

• SPoF (Coordinator Crash)
• Dead Coordinator 감지 불가능
• Performance Bottleneck

→ Coordinator가 N개의 복제본이라면 Decentralized Algorithm 적용 가능

 

 

 

---

2-1. A ring-based algorithm

1. Ring으로 프로세스 구성, 각 프로세스는 후속 프로세스를 알고 있음
2. 토큰은 링을 따라 Passed됨. 프로세스가 자원을 얻으려면 토큰을 기다림
3. 토큰을 보유하고 있는 경우에만 Critical Section에 접근 가능
4. Node가 죽으면 프로세스가 이를 Skip하고 후속 프로세스에 토큰을 전달함

문제점 : 순서가 아님, 긴 Delay, 매우 Unreliable(신뢰할 수 없음) → 모든 프로세스의 Failure시 Ring이 깨짐, Token의 Lost

 

 

2-2. A fair ring-based algorithm

1. 시스템 내에 하나의 토큰이 존재하며 이 토큰은 우선 처리해야 하는 요청의 시간 정보(t)를 가지고 있다.
2. Critical Section 진입 : Request에 Timestamp 포함시킨 후(Tr), 토큰을 기다려야 함
3. 토큰을 받게 되면 Tr과 토큰이 가지고 있는 시간 t를 비교함
   1. 시간이 같다면 해당 프로세스는 토큰을 확보, Critical Section 진입
   2. Tr이 t보다 크다면, 다음 프로세스에게 양보함
   3. Tr이 t보다 작다면(혹은 t = null이라면), 토큰의 시간을 Tr로 설정하고, 다음 프로세스에게 토큰을 전달 후 기다림
4. Critical Section Leave : Token 시간(t)을 Null로 설정한 후, 토큰을 전달

 

 

 

---

3. Distributed Algorithm (Lamport’s Time Stamp)

1. Lamport의 Logical Clock 사용
2. Critical Section 사용을 위해서 다른 프로세스에게 Messaging을 보낸 후, OK 응답을 대기함
   1. 리소스에 관심이 없으면 OK로 응답
   2. 리소스 사용 중일 경우 요청을 Queue에 저장 후 응답하지 않음
   3. 리소스에 관심이 있지만, 다른 프로세스가 먼저 요청했다면 OK로 답장, 내가 먼저면 요청을 Queue에 저장 후 응답하지 않음
3. 장점
   1. Central Bottleneck이 없음
   2. Fully Distributed
4. 단점
   1. N Points of failure → 어느 노드의 실패로 인해 전체 시스템이 잠김
   2. 모든 프로세스는 모든 결정에 관여함 → Process Overload로 인한 Bottleneck

 

---

4. Ricart and Agrawala algorithm

 

요청 사이트 (Requesting Site)

• 특정 프로세스 (사이트)인 Pi가 임계 영역에 들어가고자 할 때, Pi는 모든 사이트에 대해 request(ts, i) 메시지를 냄.
  • ts는 Pi의 타임스탬프, i는 Pi의 고유 식별자

수신 사이트 (Receiving Site)

• request(ts, i) 메시지를 수신한 프로세스 Pj는 다음과 같은 조건 확인
  • Pj가 현재 임계 영역을 요청하거나 실행 중이 아니거나
  • Pj가 임계 영역을 요청하고 Pi의 타임스탬프 ts보다 더 높은 타임스탬프를 가진 요청이었다면 응답

응답 (Reply)

• 조건을 만족하는 경우, Pj는 reply(ts, j) 메시지를 Pi에게 보냄.
• 그러나 Pj가 임계 영역을 요청 중이면서, Pj의 타임스탬프가 Pi의 타임스탬프보다 낮은 경우, Pj는 응답을 보내지 않고 지연

 

장점: Fair(공정성), Short Delay(짧은 지연)

단점: Failure of Node → Starvation(기아) 야기

 

 

 

 

 

---

5. Majority rules

 

1. Critical Section에 진입할 시, 다른 프로세스들에게 Vote Request
2. 장점 : 최대 N/2 - 1 개의 실패한 프로세스가 있어도 진행 가능
3. 단점 : Not Fair, Deadlock 가능성(누구든지 다수의 표를 받는다는 보장이 없음)

 

 

---

알고리즘의 평가

 

 

평가 기준

1. 얼마나 많은 메시지가 필요한가?
2. Scalable한가? Node당 작업량은?
3. Centralized보다 나은가?
4. Point of Failure은 몇 개인가?
5. Failure를 Handling할 수 있는가?

 

결국 산업 표준에 가까운 것은 Centralized Model. → Fault Tolerance를 위해 Replicate하여 사용

 

 

 

 

 

 

 

 

---

Content / Image Reference 

 

Tannenbaum and Van Steen :: Distributed Systems: Principles and Paradigms (PDF)