스즈키-카사미 알고리즘
Suzuki–Kasami algorithm이 글은 검증을 위해 추가 인용문이 필요합니다. : · · · · JSTOR (2014년 9월 (이 메시지 및 ) |
스즈키-카사미[1] 알고리즘은 분산 시스템에서 상호 배제를 실현하기 위한 토큰 기반 알고리즘입니다.토큰을 보유하는 프로세스는 중요한 섹션에 들어갈 수 있는 유일한 프로세스입니다.
이는 REQUEST 메시지와 REPLY 메시지가 크리티컬섹션에 도달하기 위해 사용되는 Ricart-Agrawala[2] 알고리즘의 변경입니다.단, 이 알고리즘에서는 단일 PRIVE 메시지를 다른 노드에 송신함으로써 연공서열과 다른 노드에 크리티컬섹션을 넘기는 방식이 도입되었습니다.따라서 권한이 있는 노드는 크리티컬섹션을 사용할 수 있으며 권한이 없는 노드는 사용할 수 없습니다.프로세스가 크리티컬섹션에 들어가려고 하는데 토큰이 없는 경우 요청 메시지를 시스템 내의 다른 모든 프로세스에 브로드캐스트합니다.토큰이 있는 프로세스가 현재 중요한 섹션에 없는 경우 토큰을 요청 프로세스로 보냅니다.알고리즘에서는 요청 번호를 증가시켜 메시지가 순서대로 도착할 수 있도록 합니다.
알고리즘 설명
nn을 프로세스 수로 .각 프로세스는 1,., \ 1, 의 정수로 식별됩니다.
데이터 구조
각 프로세스에서 하나의 데이터 구조를 유지합니다.
- i[ _ { } [ } ( Request Number )。서 [ j RN _ { }[ }는에서 마지막 Request Number를 저장합니다.
토큰에는 다음 두 가지 데이터 구조가 포함됩니다.
- {LN [ ( Last request Number ) 。서LN [ j LN [ 에는 토큰이 정상적으로 부여된 의 최신 Request Numberj { j}가 저장됩니다.
- Q 프로세스의 ID를 저장함
알고리즘.
크리티컬 섹션 요구(CS)
i(\i)가 CS에 들어가는 경우 토큰이 없는 경우 다음과 같이 처리됩니다.
- 시퀀스 i [가 증가합니다.
- 새로운 시퀀스 번호를 포함한 요구 메시지를 시스템 내의 모든 프로세스에 송신합니다.
CS의 릴리스
i가 CS를 떠나면 다음과 같이 처리됩니다.
- 토큰의 [i])을 [와 하게 합니다.는 요청 [i]{이 (가) 실행되었음을 나타냅니다.
- 토큰 큐 에 없는 k Q마다RNi [ +(\]=의 k( k가 Q Q에 됩니다.는 프로세스k\k에 미결 요청이 있음을 나타냅니다.
- 이 업데이트 후에도 토큰 큐(\Q)가 비어 있지 않으면 Q Q에서 프로세스 j(\ j를 팝하여 j j로 토큰을 전송합니다.
- 그렇지 않으면 토큰이 유지됩니다.
요청 접수
j(\ j가 시퀀스 s(\ s의 요청을 i i로부터 수신하면 다음과 같이 됩니다.
- [i]{j}[을 (를)( N j [ ,){ 로 합니다(s [ { s }의 ).
- j { j에 토큰이 있고 CS에 없는 경우 R j [ N [ + {\]==LN미결 요청을 나타냄), 토큰을 ii로 합니다.
CS의 실행
프로세스는 토큰을 취득하면 CS에 들어갑니다.
성능
- 호출에 대해 0 0 N N 메시지 중 하나(프로세스가 토큰을 보유하고 있는 경우 메시지 없음, 않은 N - 1(\N-1) 및 1(\ 1) 응답)
- 동기화 은 0 0 N 와 11) 입니다 .
알고리즘에 관한 주의사항
- 현재 토큰을 보유하고 있는 사이트만 CS에 액세스할 수 있습니다.
- CS 할당에 관련된 모든 프로세스
- 모든 노드에 보낸 요청 메시지
- Lamport의 논리 클럭을 기반으로 하지 않음
- 알고리즘은 대신 시퀀스 번호를 사용합니다.
- 오래된 요청을 추적하는 데 사용됩니다.
- 각 사이트에서 독립적으로 진행됩니다.
알고리즘의 주요 설계상의 문제점은 다음과 같습니다.
- 현재 요청과 오래된 요청 구분
- 다음에 토큰을 가져올 사이트 결정