61_분산 조정 (Distributed Coordination)

61_분산 조정 (Distributed Coordination)

 

중앙 집중식 시스템에서는 하나의 공유 메모리와 클록을 사용하므로 두 개의 사건이 발생해도 그 순서를 결정하는 것이 가능하다. 많은 응용 분야에서 순서를 결정할 수 있다는 것은 매우 중요 하다.

 

분산 시스템에서는 공유 메모리와 공유 클록이 존재하지 않기 때문에 두 사건의 순서를 결정하기가 불가능한 경우가 있다. 사건의 전후 발생 관계는 분산 시스템에서 사건의 부분적인 순서(partial order)만을 정의 한다.

 

순차적인 프로세스들만 고려할 때 하나의 프로세스에서 수행되는 모든 사건들은 완전 순서화된다. 또한 인과 법칙에 따라 메시지가 보내진 후에 그 메시지는 수신된다. 사건은 자기 자신이 발생하기 전에는 발생될 수 없으므로 관계는 비반사적 부분 순서(irreflexive partial ordering)이다.

 

만약 두 사건 A와 B에서 A가 B이전에 발생하지 않았고 B도 A이전에 발생하지 않았으면 이는 병행으로 수행되었다고 한다. 우리는 각 시스템 사건들에 하나의 타임스탬프를 연관시켜 전역 순서화(global ordering)를 정의하면 모든 사건 쌍 A와B에 대해 A->B 이면 A의 타임스탬프는 B보다 작다. 그 역이 참일 필요는 없다.

 

분산환경에서는 전역 순서화 조건을 만족하기 위해 각 프로세스내에 논리 클록을 정의 한다. 논리 클록은 간단한 카운터로 사건 발생때마다 증가한다.

 

 

[상호 배제(mutual Exclusion)]

중앙 집중식 접근에서는 하나의 프로세스가 임계구역으로 진입을 조정하는 역할을 전담하도록 함으로써 상호 배제를 구현 한다. 상호 배제를 원하는 각 프로세스는 조정자에게 요청 메시지를 보낸다. 프로세스가 조정자로부터 응답 메시지를 받으면 임계 구역으로 진입할 수 있다. 조정자는 응답을 받으면 임계 구역에 다른 프로세스가 있는지를 검사한다. 임계 구역을 실행중인 프로세스가 없으면 조정자는 응답 메시지를 바로 보낸다. 그렇지 않으면 큐에 대기 한다.

 

이 방법은 상호 배제를 보장하며 기아 상태가 발생하지 않는다. 대신 한 번의 임계 구역 진입을 위해 세 개의 메시지(요청, 응답, 해제)를 필요로 한다.

 

완전 분산형 접근(Fully Distributed Approach)은 프로세스가 임계 구역에 들어가고자 할 때 그 프로세스는 새로운 타임스탬프를 생성하고 자신을 포함한 시스템 내의 모든 프로세스에게 요청 메시지를 보낸다. 상호 배제가 보장되며 교착 상태를 방지 한다. 임계 구역의 출입이 타임스탬프 순서에 의해 스케줄되므로 기아 상태가 발생하지 않는다.

 

토큰 패싱 접근은 하나의 토큰을 프로세스들 사이를 순환시키는 방법이다. 임의의 프로세스가 토큰을 받으면 그 토큰을 가지고 임계 구역에 진입할 수 있다. 그 프로세스가 임계구역에서 나오면 토큰을 다시 전달시킨다. 토큰을 받은 프로세스가 임계 구역에 진입을 시도중이 아니라면 그 토큰을 다시 전달 시킨다.

 

 

[동시성 제어 (Concurrency Control)]

분산 데이터베이스 시스템에서 트랜잭션 관리자의 기능은 지역 사이트에 저장된 자료를 접근하는 트랜잭션들의 수행을 관리하기 위한 것이다. 실행되는 트랜잭션들의 병행 실행을 조정하기 위해 적절한 병행성 제어 방법을 채택해야 한다.

 

락킹 프로토콜(Locking Protocol)은 자신의 사이트에 저장되어 있는 자료 항목들에 대해 락(lock)과 언락(Unlock) 요청들을 관리하기 위한 기능으로 지역 락 관리자를 가진다. 락 관리자에게 특정락 요청 메시지를 전송하면 각 관리자는 상태에 따라 락을 허용 또는 대기 시킨다.

 

• 자료 중복을 허용하는 시스템에서는 다수의 동시성 제어 기법이 사용될 수 있다. 단일 조정자 접근(Single coordinator Approach)라 하여 단일 락 관리자를 가지고 있다. 이 방법은 구현이 단순하며 교착상태 취급이 단순하지만 병목이나 병행성에는 취약하다. 이를 절충하기 위해 다중 조정자 접근(Multiple coordinator approach)방법을 통해서 달성 할 수 다.

 

• 다수결 프로토콜(Majority Protocol)은 비중복 방법을 다소 변경한 것이다. 시스템은 각 사이트에 락 관리자를 유지 한다. 각 관리자는 자신의 사이트에 저장되어 있는 모든 자료 혹은 자료의 복사본들에 대한 락을 관리한다. 다수결 프로토콜은 단일 조정자 접근보다 구현이 복잡하다

 

• 편견 프로토콜(Biased Protocol)은 다수결 프로토콜과 유사하지만 공유 락 요청이 배타적 락 요청보다 더 호의적인 취급을 받는 다는 부분에서 차이가 있다. 시스템은 각 사이트에 락 관리자를 두고 각 관리자는 해당 사이트에 저장된 모든 자료 항목에 대해 락을 관리한다. 공유와 배타적 락은 다르게 취급한다.
  • 공유 락 : 트랜잭션이 락을 요청 할 때 단순히 복사본을 가지고 있는 한 사이트의 락 관리자에게 락을 요청 한다.
  • 배타적 락 : 트랜잭션이 락을 요청 할 때 복사본을 가지고 있는 모든 사이트의 락 관리자에게 락을 요청 한다.

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사