18. 분산 조정(Distributed Coordination)

18. 분산 조정(Distributed Coordination) ▶ 이 장의 목표 - 중앙 집중 동기화 방법을 분산 환경으로 확장하는 방법 - 분산 시스템에서의 교착 상태 취급 방법 18.1 사건 순서화(Event Ordering) ▶ 분산 시스템: 공유기억장치나 클록 없음 → 사건의 순서 예측 어려움 * 사건 발생전 관계(happened-before relation): 분산 시스템에서 사건의 부분적인 순서를 나타냄 → 전체 사건의 순서를 결정하는 분산 알고리즘 소개 18.1.1 사건 발생 전후 관계(Happened-Before Relation) ▶ 사건 발생 전후 관계의 정의 - 프로세스내의 모든 사건들은 순차적임 - 인과 관계 법칙에 의해 메시지는 송신되어야 수신될 수 있음 * “→”: 사건 발생 전후 관계 표시 - 비반사적 부분 순서(irreflexive partial ordering) ex) A→B→A 허용 안함 ① A와 B가 동일 프로세스내의 사건이고, A가 B보다 먼저 수행된다면 A→B이다. ② A가 한 프로세스에 의해 메시지를 송신하는 사건이고, B가 다른 프로세스에 의해 그 메시지를 수신하는 사건이라면 A→B이다. ③ A→B이고 B→C이면, A→C이다. * 두 사건 A와 B가 → 관계가 없는 경우, 병행적으로 수행되었다고 말할 수 있음 ▶ 병행성과 사건 발생 전후 관계의 표현: “시공간 다이어그램(space-time diagram)” [그림 18.1] 세 개의 병행 프로세스들에 대한 상대적인 시간 - 수평 방향: 공간, 즉 서로 다른 프로세스 혹은 프로세서들 - 수직 방향: 시간의 흐름 * A에서 B로 또는 B에서 A로의 경로가 없으면 사건 A와 B는 병행성이 있음 (→ 관계의 예) (병행 관계의 예) , , , (∵, ) , 18.1.2 구현(Implementation) ▶ 전역 순서화(global ordering) 정의: 각 시스템 사건을 타임스탬프(time stamp)에 연관시키는 방법 → 임의의 쌍 A와 B에 대해 A→B이면 사건 A의 타임스탬프는 사건 B의 타임스탬프보다 작다. ▶ 시간 표식 순서화 기법 ① 각 프로세스 마다 논리적 클록 를 정의: 프로세스내의 사건마다 증가하는 계수기로 구현 → 동일 프로세스내의 임의의 두 사건에 대해 전역 순서화 요구를 만족시킬 수 있음 ex) 내의 사건 A가 사건 B보다 먼저 발생: ② 그러나, 프로세스간에는 전역 순서화 요구를 만족한다고 보장 못함 ex) (사건 A) 이 에게 메시지 보냄: (사건 B) 가 그 메시지를 받음: → 의 논리적 클록이 보다 느릴 수 있기 때문: A→B 만족 못함 ③ 이를 해결하기 위해, 프로세스의 논리적 클록의 현재 값보다 큰 타임스탬프를 갖는 메시지를 받게 되면, 논리적 클록을 증가시키는 것이 필요함 → (사건 B) 프로세스 가 타임스탬프 인 메시지를 받았을 때: ex) ④ 타임스탬프 순서화 기법으로 두 사건 A, B의 타임스탬프가 같으면, 병행성 있음을 의미함 → 전역 순서화를 위해, 프로세스 식별 번호를 사용할 수 있음 18.2 상호 배제(Mutual Exclusion) ▶ 분산 환경에서의 상호배제 구현 (가정) 각각 서로 다른 프로세서에 상주하는 n개의 프로세스로 구성되는 시스템 18.2.1 중앙 집중형 접근(Centralized Approach) ▶ 개념: 시스템 내의 프로세스 중 하나가 임계구역의 출입구를 관리하는 조정자 역할을 수행 “조정자(coordinator)” ① 요청 메시지 프로세스 Pi 임의의 스케줄링 알고리즘 사용가능 ④ if 해제시 선택 ③ if 사용중 대기시킴 ⑤ 응답 메시지 ② 검사(사용중 or 유휴중) ⑦ 해제 메시지 요청큐 임계구역 ⑥ 사용 ▶ 특성 - 상호 배제 보장 - 조정자의 스케줄링 알고리즘이 공정(FCFS)하면 기아 상태도 발생하지 않음 - 조정 프로세스의 고장 시 새로운 프로세스가 대신하게 됨 → 18.6절 참조 18.2.2 완전 분산형 접근(Fully Distributed Approach) ▶ 사건 순서화 정책에 기반을 둔 알고리즘: 임계 구역에 대한 모든 요청을 전역 순서화하고 FCFS 순서로 프로세스를 처리하는 방법 아직 응답을 안한 요청 메시지 리스트 ④ 임계구역에서 나온 후 요청 리스트에 있는 모든 프로세스에 응답 ③ 모든 프로세스로부터 응답 받으면 사용 ① 임계 구역 요청 시, - 시간 표식 TS를 생성하고 - 요청 메시지 를 자신을 포함한 모든 프로세스에게 전송 프로세서 다른 모든 프로세스들 임계구역 요청 리스트 ② 검사 (사용안함/사용중/대기중) ↙ ↓ ↘ 즉시응답 응답보류 타임스탬프 ↓ 참조 사용 후 응답 ▶ 요청 메시지의 회신/보류 결정 요령: ②에 해당 ⑴ 프로세스 가 임계 구역 내에 있으면, 회신 보류 → 사용 후 회신 ⑵ 가 임계 구역에 들어가길 원치 않으면, 즉시 응답 ⑶ 가 임계 구역에 들어가기 위해 대기중인 경우, → 상대 프로세스 의 요청의 타임스탬프와 자신의 타임스탬프를 비교: - 상대의 타임 스탬프가 작으면, 상대가 먼저 요청한 것이므로 즉시 응답 - 그렇지 않으면, 회신을 보류하고 요청 큐에 추가 ▶ 특성 - 상호 배제 보장 - 교착 상태 미발생 보장 - 타임스탬프 순서로 스케줄되므로(FCFS 방식), 기아 상태 미발생 보장 - 임계 구역 출입을 위한 메시지 수: 2×(n-1) ← “최소 메시지 수” ▶ (예) 프로세스 , , 로 구성된 시스템 1) 과 의 요청 발생: 각자 다른 모든 프로세스에게 요청 전송 → , 2) 는 즉시 회신 3) 은 요청의 타임스탬프(4)가 요청의 타임스탬프(10)보다 작으므로 즉시 회신 은 요청의 타임스탬프(10)가 요청의 타임스탬프(4)보다 크므로 회신 보류 4) 는 과 로부터 회신을 받았으므로 임계 구역에 들어감 5) 는 임계 구역에서 나오면 에게 회신을 보내 임계 구역에 들어 갈 수 있게 함 ▶ 모든 프로세스가 참여하는 방식에서 비롯되는 단점 (1) 각 프로세스는 다른 모든 프로세스를 구별해야 함 → 새로운 프로세스의 가담 시, - 그룹내의 모든 다른 프로세스의 이름을 알아야 함 - 자신의 새로운 프로세스 이름을 모두에게 알려야 함 (2) 임의 프로세스의 고장(응답 못함)은 전체 과정을 파괴시킴 → 체제 내의 모든 프로세스의 상태를 계속 조사해야 함 - 고장 발견시 - 해당 프로세스에 요청 메시지를 보내지 않음 - 회복 발견시 - 해당 프로세스에 대한 재 가담 프로시저를 호출함 18.2.3 토큰 패싱 접근(Token-Passing Approach) ▶ 개념: 시스템내의 프로세스들간에 토큰을 순환시키고, 유일하게 존재하는 토큰을 소유한 프로세스만이 임계 구역에 들어가게 하는 방법 → 토큰(token): 시스템에서 전달되는 일종의 특정한 메시지 형태 - 임의의 프로세스가 토큰을 받으면, 그 토큰을 보유하고 해당 임계 영역에 진입할 수 있음 - 그 프로세스가 임계 구역을 나오면, 토큰을 다시 전송함 - 토큰을 받은 프로세스가 임계 구역에 진입하는 것을 원치 않으면, 그 토큰을 단지 이웃에 전송함 ▶ 링 구조 시스템의 경우 1) 특성 - 논리적으로 구현 가능: 물리적인 통신 네트워크는 링 구조일 필요 없음 - 상호 배제 성립: 토큰이 유일하므로 - 기아 상태 미발생: 단방향 링의 경우 - 임계 구역의 상호 배제를 위한 메시지 수는 변동이 심함 → 경쟁이 심한 경우, 각 출입마다 하나의 토큰 메시지 필요 경쟁이 거의 없는 경우, 각 출입마다 다수의 토큰 메시지 필요 2) 두 가지 고장의 경우 - 토큰이 분실되면, 한 프로세스를 선택하여 새로운 토큰을 생성시킴 → 선택 알고리즘(18.6절) - 임의의 프로세스가 고장나면, 새로운 논리적 링을 재구성해야 함 18.3 원자성(Atomicity) ▶ 트랜잭션 조정자(transaction coordinator): 분산 시스템에서 트랜잭션 수행의 원자성을 보장하는 기능 담당 → 지역 트랜잭션 조정자: 해당 사이트에서 시작된 모든 트랜잭션의 실행을 조정하고 각 지역 사이트의 복구를 위해 로그(log)를 유지함 - 트랜잭션의 수행을 시작 - 트랜잭션을 서브 트랜잭션들로 나누어 여러 사이트에 분배 - 트랜잭션의 종료를 조정 - 모든 사이트에서 승인(commit)되지 않으면, 거부(abort)됨 18.3.1 2 단계 승인 프로토콜(The Two-Phase Commit Protocol) ▶ 2 단계 승인(Two-Phase Commit; 2PC) 프로토콜: 트랜잭션 를 수행하는 모든 사이트가 실행의 최종 결과에 동의하게 함으로써, 원자성을 보장하는 한 방법 (가정) 트랜잭션 는 사이트 에서 시작되고, 는 의 트랜잭션 조정자라고 하자. 가 실행을 완료할 때 - 즉, 를 수행한 모든 사이트가 에게 가 완료되었음을 알리면 - 는 다음의 2PC 프로토콜을 시작함 ① 단계 1: - 는 레코드 를 로그에 추가하고, 레코드를 보조기억장치에 저장 - 를 수행한 모든 사이트에 prepare 메시지를 전송 - 그 메시지를 받은 해당 사이트의 트랜잭션 관리자는 의 부분에 대해 승인 여부를 결정 1) 미승인시: 를 로그에 추가하고, abort 메시지를 에 전송 2) 승인시: 를 로그에 추가하고, 에 관계된 모든 레코드를 보조기억장치에 저장하고, ready 메시지를 에 전송 ② 단계 2: - 는 모든 응답을 받거나 일정 시간이 지난 후 의 승인 또는 거부를 결정 1) 관련된 모든 사이트로부터 ready 를 받은 경우: 승인(commit) 2) 그렇지 않은 경우: 거부(abort) - 결정에 따라 레코드 또는 를 로그에 추가하고 보조기억장치에 저장 - 조정자는 commit 또는 abort 메시지를 모든 관련 사이트에 전송하고, 각 사이트는 그 메시지를 받은 후 로그에 기록함 18.3.2 2PC에서 결함 처리(Failure Handling in 2PC) 18.3.2.1 관련 사이트 결함(Failure of a Participating Site) ▶ 관련 사이트 가 결함으로부터 복구될 때, 임의의 트랜잭션 에 대한 처리 ① 로그에 레코드를 유지하는 경우: redo() 수행 ② 로그에 레코드를 유지하는 경우: undo() 수행 ③ 로그에 레코드를 유지하는 경우: 에 문의 1) 가 정상인 경우: commit 또는 abort를 에게 알려줌 - redo() 또는 undo() 수행 2) 가 결함인 경우: - query-status 메시지를 모든 사이트에 보냄 - 메시지를 받은 사이트는 가 수행되었는지 로그를 살펴보고, 만일 수행된 경우 commit 또는 abort를 알림 - 만일 아무런 응답이 없으면 의 운면에 대한 결정은 미뤄지고, 주기적으로 query-status 메시지를 재전송함 ④ 로그에 에 대한 어떠한 메시지도 없는 경우: 로부터의 prepare 메시지를 응답하기 전에 결함이 발생했음을 의미 → 필연적으로 가 를 abort하게 되고, 따라서 는 undo() 수행하게 됨 18.3.2.2 조정자 결함(Failure of Coordinator) ▶ 조정자가 트랜잭션 에 대한 commit 프로토콜 수행 중에 고장이 발생하면, 관련 사이트들은 다음과 같이 의 운명을 결정함 ① 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 는 commit됨 ② 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 는 abort됨 ③ 활성 사이트가 자신의 로그에 레코드를 포함하지 않는 경우: 이 사이트는 ready 메시지를 에 보내지 않았으며 따라서 는 를 abort 시켰을 것이므로, 의 복구를 기다릴 필요 없이 를 abort시킴 ④ 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 의 복구를 기다림. 이때 는 활성 사이트에 있는 자료에 대해 잠금 기능을 수행하게 되고, 그로 인해 다른 트랜잭션들도 를 기다리게 됨 → 블록킹(blocking) 문제 18.3.2.3 네트워크 결함(Failure of Network) ▶ 링크의 결함이 발생하면, 이를 사용하는 사이트는 상대 사이트에 결함이 발생한 것으로 간주하게되고, 앞의 처리 과정이 잘 수행됨 → 네트워크 분할이 발생할 수 있음 - 조정자와 관련 사이트들이 동일 영역에 속하는 경우: commit 프로토콜에 영향을 미치지 않음 - 그렇지 않은 경우: 메시지 분실 발생 18.4 동시성 제어(Concurrency Control) ▶ 분산 데이터베이스 시스템의 트랜잭션 관리자: 지역 사이트에 저장된 자료를 접근하는 트랜잭션들의 수행을 관리 - 지역 트랜잭션: 자신의 사이트에서만 수행되는 트랜잭션 - 전역 트랜잭션: 여러 사이트에서 수행되는 트랜잭션 → 관리자는 트랜잭션 복구를 위해 로그를 유지해야 하고, 적절한 병행성 제어 방법을 채택해야 함 18.4.1 잠금 프로토콜(Locking Protocols) ▶ 6장의 2단계 잠금 프로토콜은 분산 환경에서도 적용 가능함 → 단, 잠금 관리자(lock manager) 구현 필요 18.4.1.1 비중복 방법(Nonreplicated Schemes) ▶ 시스템에 중복 자료가 없는 경우, - 각 사이트에 저장되어 있는 자료 항목에 대해 잠금과 해제 요청을 관리하는 기능의 지역 잠금 관리자(local lock manager)를 둠 - 트랜잭션이 사이트 에 있는 자료 항목 의 잠금을 원하는 경우, 사이트 에 있는 잠금 관리자에게 특정 잠금 모드로 메시지를 전송함 1) 수용할 수 없는 경우: 지연 2) 수용할 수 있는 경우: 승인 메시지를 반환 (장점) 구현이 간단: 잠금 요청 - 2개의 메시지, 해제 요청 - 1개의 메시지 (단점) 교착 상태 취급이 복잡 18.4.1.2 단일 조정자 접근(Single Coordinator Approach) ▶ 특정 사이트 에 있는 단일 잠금 관리자가 모든 잠금과 풀림 요청을 처리하게 하는 방법 - 읽기: 해당 자료 항목의 복사본이 있는 하나의 사이트로부터 읽음 - 기록: 해당 자료 항목의 복사본이 있는 모든 사이트에 기록 (장점) 1) 단순한 구현: 잠금 요청 - 2개의 메시지, 해제 요청 - 1개의 메시지 2) 단순한 교착 상태 취급: 한 사이트에서 모든 잠금과 해제가 수행되므로 7장의 교착 상태 취급 알고리즘을 직접 분산 환경에 사용할 수 있음 (단점) 1) 병목 현상(bottleneck): 사이트 에서 모든 요청을 처리해야 하기 때문 2) 취약성(vulnerability): 사이트 의 고장은 처리 중단이 초래되거나 복구 방법이 요구됨 18.4.1.3 다수결 프로토콜(Majority Protocol) ▶ 각 사이트에 잠금 관리자를 유지하여 그 사이트의 모든 자료나 복사본에 대해 잠금을 관리하게 하는 방법 → 트랜잭션은 자료 항목 의 대다수 복사본들에 대해 잠금을 요청해야 함: n/2 +1 이상 (장점) 분산형 (단점) 1) 복잡한 구현: 잠금 요청 - 2(n/2+1) 메시지 요구, 풀림 요청 - (n/2+1) 메시지 요구 2) 복잡한 교착 상태 취급 - 18.5절 참조 18.4.1.4 편의 프로토콜(Biased Protocol) ▶ 각 사이트마다 해당 관리자가 잠금과 해제를 관리하되, 공유 잠금과 배타 잠금을 구분하여 취급하는 방법 - 공유 잠금: 의 복사본을 가진 한 사이트의 잠금 관리자에게 잠금을 요청 → 읽기: 적은 부담 - 배타 잠금: 의 복사본을 가진 모든 사이트의 잠금 관리자에게 잠금을 요청 → 기록: 추가 부담 18.4.1.5 주 복사본(Primary Copy) ▶ 자료 항목 의 주 복사본을 유일한 주 사이트에 저장하고, 잠금을 주 사이트에게 하는 방법 (장점) 복사본이 없는 경우와 동일한 병행성 제어 가능 (단점) 주 사이트의 고장시 의 다른 복사본을 이용할 수 없음 18.4.2 타임스탬핑(Timestamping) ▶ 중앙 집중형의 타임스탬핑 방법을 그대로 사용하려면, 단일 타임스탬프를 생성하는 방안 필요함 18.4.2.1 단일 타임스탬프 생성(Generation of Unique Timestamps) ▶ 단일 타임스탬프를 생성하는 두 방법 1) 집중형 방법: 단일 사이트가 타임스탬프를 분배하기 위해 선정되는 방법 → 논리적 카운터 또는 지역 클록으로 구현 2) 분산형 방법: - 지역 단일 타임스탬프: 각 사이트마다 논리적 카운터나 지역 클록으로 구현 - 전역 단일 스탬프: 지역 단일 타임스탬프 + 사이트 식별자로 구현 [그림 18.2] 단일 타임스탬프 생성 → 다수의 지역 클록이 동기화되는 것을 보장하기 위한 방법: 타임스탬프 를 가진 트랜잭션 가 사이트 는 방문했을 때, 만일 가 의 현재 값보다 크면 는 를 로 증가시킴 18.4.2.2 타임스탬프 순서화 방법(Timestamp Ordering S초듣) ▶ 6.9절의 기본 타임스탬프 기법은 분산 시스템에 바로 확장될 수 있음 (단점) 트랜잭션들 사이의 충돌이 발생할 경우 대기 방법보다 롤백 방법을 통해 해결함 → 해결을 위한 핵심 1) 의 은 의 이 존재하고 이면 지연됨 2) 의 은 또는 를 수행하는 가 존재하고 이면 지연됨 18.5 교착 상태 처리(Deadlock Handling) ▶ 분산 환경을 위한 교착 상태의 방지(prevention), 회피(avoidance), 탐지(detection) 알고리즘 → 기존 방법(7장)과 거의 유사하게 사용할 수 있음 1) 교착 상태 방지: 자원 순서화에 의한 교착 상태 방지 기법 - 시스템의 모든 자원을 전역 순서화 함: 자원마다 유일한 번호를 부여함 - 프로세스는 자원 를 요청하기 위해서는 이 보다 큰 번호의 자원을 소유하지 않아야 함 → 구현 간단, 자원의 전역 순서화 필요 2) 교착 상태 회피: 은행가 알고리즘 - 시스템내의 한 프로세스를 은행가 알고리즘에 필요한 정보를 관리하는 은행가로 사용하면 됨 - 모든 자원의 요청은 은행가를 통해서 이루어짐 → 구현 간단, 은행가로의 병목 현상 심각 18.5.1 교착 상태 방지(Deadlock Prevention) ▶ 타임스탬프 순서화에 기반을 둔 교착 상태 방지 기법 1) wait-die 기법: 비선점 방식 → 가 의 보유중인 자원을 요구할 때, 가 보다 적은 타임스탬프(더 오래 기다림)를 가지고 있으면 기다릴 수 있고(wait), 그렇지 않으면 는 복귀함(die) ex) 요구 요구 → ← ⇒ 은 기다리고, 복귀함 (5) (10) (15) 2) wound-wait 기법: 선점 방식 → 가 의 보유중인 자원을 요구할 때, 가 보다 적은 타임스탬프를 가지고 있으면 는 의 자원을 선점하고(wound) 는 복귀한다. 그렇지 않으면 는 기다릴 수 있다(wait). ex) 요구 요구 → ← ⇒ 은 자원을 선점하고 는 복귀하며, 는 자원을 기다림 (5) (10) (15) ▶ 차이점 wait-die 기법 wound-wait 기법 오래된 프로세스가 기다림(선점 안함) 오래된 프로세스는 기다리지 않음(선점함) 는 로부터 필요한 자원을 획득하기 위해 여러 번 복귀될 수 있음 (다수의 roll back 발생) 가 에 의해 복귀된 후에는 가 보유중인 자원을 요청하고 기다리게 됨 (소수의 roll back 발생) ▶ 공통점 - 각 프로세스에 우선 순위를 부여: 타임 스탬프를 우선 순위로 사용 - 교착 상태 방지를 보장: 대기 그래프(wait-for graph)의 임의의 간선 에 대해 항상 가 보다 우선 순위가 높거나 항상 낮게 함으로써 사이클이 발생하지 않게 함 - 기아 상태(starvation) 가능: 낮은 우선 순위의 프로세스가 계속해서 복귀될 수 있음 → 복귀되는 프로세스의 타임스탬프를 갱신하지 않음으로써 기아 상태 방지 가능 - 두 기법 모두 교착상태가 아닌 경우의 불필요한 복귀 발생 → 교착 상태 탐지 기법 필요 18.5.2 교착 상태 탐지(Deadlock Detection) ▶ 지역 대기 그래프(local wait-for graph): 각 사이트에서의 대기 그래프 - 노드: 그 사이트의 자원을 점유하거나 요청하는 지역적 또는 비지역적 프로세스 - 아크: 자원 요청 ex) [그림18.3] 두 개의 지역 대기 그래프 ▶ 지역 대기 그래프의 구성: 동일 프로세스가 서로 다른 사이트에 존재할 수 있음 → 사이트 A의 프로세스 가 사이트 B의 프로세스 에 의해 점유된 자원을 필요로 하면, 요청 메시지가 에서 로 보내지고, 간선 가 사이트 B의 지역 대기 그래프에 포함됨 ▶ 교착 상태 점검 (가정) 자원 유형별로 하나의 자원이 존재 - 지역 대기 그래프에 사이클 존재 ○: 교착 상태 발생 의미 - 자원 대기 그래프에 사이클 존재 ×: 교착 상태 아니라고 장담 못함 → 교착 상태가 아님을 증명하려면, 모든 지역 그래프의 합집합(union)인 전역 대기 그래프에서 사이클이 없음을 보여야 함 ex) [그림 18.4] 전역 대기 그래프 ▶ 분산 시스템에서 대기 그래프를 구성하는 방법: 18.5.2.1-18.5.2.2 18.5.2.1 중앙 집중형 접근(Centralized Approach) ▶ 교착 상태 탐지 조정자(deadlock-detection coordinator): 모든 지역 그래프의 합으로 구성되는 전체 대기 그래프를 관리하는 프로세스 - 실제 그래프(real graph): 특정 시간에 존재하는 그래프 - 구성 그래프(constructed-graph): 통신 지연으로 조정자에 의해 생성된 실제 그래프의 근사치 ▶ 대기 그래프의 구성 시점 - 새로운 간선의 삽입 혹은 제거 시마다 - 주기적으로 대기 그래프에서 많은 변화가 일어났을 때마다 - 조정자가 사이클 탐지 알고리즘을 수행할 필요가 있을 때마다 → 교착 상태 탐지알고리즘으로 사이클이 발견되면, 조정자는 희생자를 선택하고 모든 사이트에게 특정 프로세스가 희생자로 선택되었다는 사실을 알려주어야 함 ▶ 불필요한 복귀의 발생 원인 1) 거짓 사이클(false cycle)이 전역 대기 그래프에 존재하는 경우 ex) [그림 18.5] 지역 및 전역 대기 그래프 ① 사이트 A의 가 점유하고 있는 자원을 해제: A의 간선 제거 ② 가 사이트 B의 가 점유하고 있는 자원을 요청: B에 간선 삽입 ③ 만일 조정자에게 제거 메시지보다 삽입 메시지가 먼저 도착하면, 전역 대기 그래프에 거짓 사이클 발생 → 교착 상태 회복 작업 시작 2) 실제 교착 상태가 발생하여 희생자가 선택될 때, 불필요한 복귀나 취소가 발생할 수 있음 ex) [그림 18.3] 참조 ① 사이트 A가 를 취소시키기로 결정하고, ② 동시에 조정자가 사이클 발견하여 를 희생자로 선택하면, → 와 가 복귀됨(실제로는 만 복귀되면 됨) ▶ 대기 그래프의 구성: 다른 사이트로부터의 요청에 유일한 식별자인 타임스탬프를 붙임 1) 사이트간 자원 요청시: 사이트 A의 가 사이트 B의 의 자원을 요청하는 경우 ① 사이트 A의 로컬 대기 그래프에 타임스탬프가 부착된 간선 을 추가 ② 가 즉시 자원을 줄 수 없는 경우에만 사이트 B의 로컬 대기 그래프에 그 요청 간선을 추가 2) 사이트내의 자원 요청시: 동일 사이트에 있는 가 의 자원을 요청하는 경우 → 해당 사이트에 타임스탬프가 없는 간선 을 즉시 추가 ▶ 중앙 집중형 교착 상태 탐지 알고리즘 → 모든 교착 상태를 탐지하면서 거짓 교착 상태는 탐지하지 않는 방법 1) 조정자는 시스템의 각 사이트에 초기화 메시지를 전송 2) 이 메시지를 받은 각 사이트는 자신의 지역 대기 그래프를 조정자에게 보냄 3) 각 사이트의 지역 대기 그래프를 받은 조정자는 전역 그래프를 구성 - 정점: 시스템내의 모든 프로세스에 대한 정점을 포함 - 간선: 다음 조건을 만족하는 간선 를 포함 ① 하나의 대기 그래프에 간선 가 존재하는 경우이거나, ② 둘 이상의 대기 그래프에 타임스탬프를 가진 간선 가 존재하는 경우 4) 사이클이 존재하면 교착 상태이고, 그렇지 않으면 교착 상태가 아님 18.5.2.2 완전 분산형 접근(Fully Distributed Approach) ▶ 기본 개념 - 각 사이트가 전체 그래프의 일부를 나타내는 확장된 지역 대기 그래프를 구성하고, - 교착 상태가 존재하면 적어도 하나의 부분 그래프에서 사이클이 나타나게 하는 방법 ▶ 확장된 지역 대기 그래프: 기존의 지역 대기 그래프의 확장 → 외부 그래프를 로 표현 - 추가: 가 다른 사이트의 임의의 프로세스가 점유하고 있는 자원을 요청한 경우 - 추가: 가 점유하고 있는 자원을 다른 사이트의 임의의 프로세스가 요청한 경우 ex) [그림 18.6] 확장된 지역 대기 그래프 ← [그림 18.3] → 확장된 지역 대기 그래프에 사이클 존재할 때 ① 를 포함하지 않는 경우: 교착 상태임 ② 를 포함하는 경우: 교착 상태일 가능성이 있음 → “교착 상태 탐지 알고리즘” 수행 ▶ 완전 분산형 교착 상태 탐지 알고리즘 1) 사이트 에서 를 포함하는 사이클 발견 2) 이 사이클을 파악하기 위해, 는 에 대응하는 에게 사이클 정보를 담고 있는 교착 상태 탐지(dead-lock detection) 메시지를 보냄 3) 는 이 메시지 정보를 이용하여 지역 대기 그래프를 갱신하고, 사이클이 존재하는지 검사함 - 사이클이 존재하지 않는 경우: 교착 상태 아님 - 를 포함하지 않고 사이클이 존재하는 경우: 교착 상태임 - 를 포함하는 사이클이 존재하는 경우: 마찬가지로, 에 대응하는 사이트 에 교착 상태 탐지 메시지를 보냄 ex) [그림 18.6] → [그림 18.7] 확장된 지역 대기 그래프 ① 이 를 포함하는 사이클 발견: [그림 18.6] ② 이 교착 상태 탐지 메시지를 에 전송함 ③ 는 지역 대기 그래프를 갱신함: [그림 18.7] ④ 는 를 포함하지 않는 사이클 발견: 교착 상태 → 복구 수행 * 이때, 과 가 동시에 교착 상태 탐지 알고리즘을 전송할 수 있음: 불필요한 중복 처리 ▶ 메시지 전달 횟수를 감소시키기 위한 방안 1) 각 트랜잭션 에 식별자를 붙임: 2) 사이트 가 사이클 를 발견하면, 일 경우에만 교착 상태 탐지 메시지를 전송함 ex) [그림 18.6] 참조 (가정) , 두 사이트가 동시에 사이클 발견 - : 사이클 발견 → : 교착 상태 탐지 메시지를 전송 안함 - : 사이클 발견 → : 교착 상태 탐지 메시지를 전송함 18.6 선출 알고리즘(Election Algorithms) ▶ 조정자 프로세스(coordinator process)의 역할 - 상호 배제 보장 - 교착 상태 탐지를 위한 전역 대기 그래프의 유지 - 시스템내의 입출력 장치의 조정 → 사이트의 결함으로 조정자 프로세스의 수행이 불가능해지면, 다른 사이트에 조정자 기능을 새로이 복사하여 시스템을 계속 동작시킬 수 있음 ▶ 선출 알고리즘: 조정자의 새로운 복사를 어느 곳에 하는가를 결정하는 알고리즘 - 프로세스 가 유일한 우선 순위 를 가지고 있고, 프로세스와 사이트는 1:1 대응관계이고, 조정자는 항상 가장 큰 우선 순위를 가진 프로세스라고 가정하면, 가장 큰 우선 순위를 가진 프로세스를 선택함 - 이 숫자는 체제내의 모든 활동하는 프로세스에 보내져야 하고, 고장으로부터 회복된 프로세스가 현재의 조정자를 구별할 수 있어야 함 ▶ 종류 ① Bully 알고리즘: 프로세스가 다른 모든 프로세스에 메시지를 보낼 수 있는 시스템에 적용 ② 링 알고리즘: 논리적 또는 물리적으로 구성된 링 구조의 시스템에 적용 → 두 알고리즘 모두 체제 내의 프로세스의 수가 이라면 선택에 메시지가 필요함 18.6.1 Bully 알고리즘(Bully Algorithm) ▶ 알고리즘 1) 프로세스 가 조정자에게 메시지를 보낸 후 시간 간격 이내에 응답을 받지 못함 → 조정자의 고장이라 간주 2) 프로세스 는 자신보다 높은 우선 순위를 가진 모든 프로세스에게 선택 메시지를 보내고, 그 프로세스들로부터의 응답을 시간 동안 기다림 3) 시간 내에 아무런 응답이 없으면, 보다 큰 우선 순위의 프로세스가 없다고 가정해서 자신이 조정자로 선택되고, 는 보다 낮은 우선 순위를 지닌 모든 활동하는 프로세스에게 가 새로운 조정자라는 메시지를 보냄 4) 만일 응답을 받게 되면, 는 높은 우선 순위를 지닌 프로세스가 선출되었다고 하는 메시지를 새로운 시간 동안 기다림. 만일 이내에 메시지가 도달하지 않으면 높은 우선 순위 프로세스가 고장이라 가정하여 알고리즘을 다시 수행함 ▶ 수행 중 조정자가 아닌 프로세스 는 로부터 다음의 두 메시지 중 하나를 받을 수 있음 ① 가 새로운 조정자이다(): 프로세스 는 이 정보를 기록 ② 가 선출 과정을 시작한다(): 는 에게 응답을 보내고, 아직 자신의 선출 과정을 시작하지 않았으면 시작함 → 자신의 선출 과정을 완료하면 낮은 우선 순위의 모든 프로세스에 자신의 우선 순위를 보냄 ▶ 고장난 프로세스가 회복된 경우에도 같은 알고리즘을 수행함 → 자신보다 높은 순위의 프로세스가 없으면 현재 낮은 순위의 조정자가 있더라도 자신이 조정자 프로세스가 된다는 사실을 알려 주어야 함 ▶ 프로세스 , , , 로 구성된 시스템의 예(가정: 첨자가 클수록 우선순위 높음) ① 모든 프로세스가 활동하며, 가 조정자 프로세스임 ② 과 가 고장이고, 는 시간 이내에 로부터 응답을 받지 못하므로, 에게 메시지를 보내 자신의 선출 알고리즘을 시작함 ③ 는 에게 응답을 하고, 에게 메시지를 보내 자신의 선출 알고리즘을 시작함 ④ 는 로부터 메시지를 받고 시간 동안 기다림 ⑤ 는 시간 이내에 로부터의 응답이 없으므로 자신을 새로운 조정자로 선택하여 과 에게 순위 3을 보냄. 단 은 고장이므로 받지 못함 ⑥ 얼마 후에 회복된 은 , , 에게 선출 요청을 보냄 ⑦ 와 가 에 응답하고 자신의 선출 알고리즘을 시작하고, 위와 같은 방법으로 가 다시 선출됨 ⑧ 끝으로 회복된 는 가장 높은 순위를 가진 프로세스이므로 선출 요청을 하지 않고 자신이 현재의 조정자라는 메시지를 , , 에게 전달함 18.6.2 링 알고리즘(Ring Algorithm) ▶ 기본 사항 - 링크는 단방향이고, 프로세스는 자신의 오른쪽 이웃에게만 메시지를 보냄 - 활동 리스트(active list): 알고리즘이 끝날 때 시스템 내의 모든 활동적인 프로세스의 우선 순위를 보유하는 자료 구조 → 각 프로세스마다 활동 리스트 유지 ▶ 알고리즘 1) 프로세스 가 조정자의 고장을 탐지하면, 새로운 빈 활동 리스트를 작성한 후, 우측 프로세스에 메시지를 보내고 활동 리스트에 를 추가함 2) 프로세스 가 좌측 프로세스로부터 메시지를 받으면 다음의 세 가지 중 하나의 형태로 응답함 ① 만일 이것이 첫 번째 메시지라면, 는 와 를 지닌 새로운 활동 리스트를 만들고, 를 보내고 를 보냄 ② 만일 이면, 는 를 활동 리스트에 더하고 우측 이웃에 메시지를 전달함 ③ 만일 이면, 의 활동 리스트에 시스템 내의 모든 활동하는 프로세스의 순위를 포함함 → 는 활동 리스트에서 가장 큰 순위의 프로세스를 새로운 조정자 프로세스로 선출함 ▶ 회복한 프로세스는 질문 메시지를 보내, 현재의 조정자로부터 그의 우선 순위 메시지를 받음 18.7 의견의 일치(Reaching Agreement) ▶ 시스템이 신뢰성을 갖기 위해서는 프로세스 집합이 어떤 공통 값에 일치하도록 하는 장치가 필요 → 불일치 원인: ① 통신 매체가 고장이 나서 메시지를 잃어버리거나 잘못 전달하는 경우 ② 프로세스에 고장이 나서 예측할 수 없는 프로세스 행동을 유발하는 경우 ex) 비잔틴 장군 문제: 적진을 포위한 모든 장군의 의견일치 필요 - 연락병에 의한 통신 - 연락병이 적군에 잡혀 메시지를 전달 못함 → 신뢰성 없는 통신 - 한 장군이 배반하여 교란함 → 고장난(오작동) 프로세스 18.7.1 신뢰성 없는 통신(Unreliable Communications) ▶ 가정: 프로세스의 잘못은 명백히 판별되지만, 통신 매체는 신뢰할 수 없음 1) 사이트 A의 프로세스 가 사이트 B의 프로세스 에게 메시지를 보낸 후 메시지의 전달 여부에 따라 수행해야 할 연산이 다른 경우(ex: 전달된 경우 함수 S를 연산; 미 전달된 경우 함수 F를 연산)에는 접수 메시지를 기다려야 함 → 시간 제한(time-out) 기법에 의해 기다리는 시간 간격을 정의하여 메시지를 보내고, 규정 시간이 초과되면 메시지를 재전송하고 다시 기다리는 과정을 접수 메시지를 받거나 고장 사실을 알게 될 때까지 반복함 2) 도 가 응답 메시지를 받았는지를 알 필요가 있는 경우(ex: 도 가 응답 메시지를 받은 경우에만 S를 연산)에는 마찬가지로 상대의 접수 메시지를 기다려야 함 → 즉, 와 는 상호 접수가 되어야 S를 연산할 수 있는데, 고장이 있는 경우에는 이 작업이 수행될 수 없음 * 일반적으로, 분산 환경에서는 와 가 각각의 상태에 완전히 일치할 수 없음 18.7.2 고장난 프로세스(Faulty Processes) ▶ 가정: 통신 매체는 신뢰할 수 있지만, 프로세스는 예측할 수 없는 방법으로 고장날 수 있음 ▶ 알고리즘: 전체 개의 프로세스 중 개 이하가 고장나 있고, 각 프로세스 가 개인 값 를 가진 시스템에서, 고장나지 않은 프로세스 가 다음을 만족하는 를 구성하는 알고리즘 ① 가 고장나지 않은 프로세스이면 ② 와 가 모두 고장나지 않은 프로세스이면 ▶ 알고리즘의 특성 ① 인 경우에만 알고리즘이 고안될 수 있음 ② 일치점 도달에 대한 최악의 지연 시간은 메시지 전달 지연에 비례 ③ 일치점 도달에 필요한 메시지 수는 모든 프로세스의 정보를 모아야 하므로 매우 많음 ▶ , 인 경우의 알고리즘 1) 두 단계의 정보 교환 ① 각 프로세스는 자신의 개인 값을 다른 모든 프로세스에게 보냄 ② 각 프로세스는 첫 번째 단계에서 얻었던 정보를 다른 모든 프로세스에게 보냄 → 이때, 고장난 프로세스는 값을 보내지 않거나 변조된 값을 보낼 수 있음 만일, 고장난 프로세스의 값이 도착하지 않으면 각 프로세스가 임의로 결정한 후 보냄 2) 고장나지 않은 프로세스 는 다음을 만족하는 를 구성 ① ② : 에 대해 보고된 세 값 중 적어도 두 개가 일치하면 그 다수 값을 사용하고, 그렇지 않으면 내정 값 NIL을 사용