스즈키-카사미 알고리즘

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '스즈키-카사미 알고리즘'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2014년 9월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

스즈키-카사미^[1] 알고리즘은 분산 시스템에서 상호 배제를 실현하기 위한 토큰 기반 알고리즘입니다.토큰을 보유하는 프로세스는 중요한 섹션에 들어갈 수 있는 유일한 프로세스입니다.

이는 REQUEST 메시지와 REPLY 메시지가 크리티컬섹션에 도달하기 위해 사용되는 Ricart-Agrawala^[2] 알고리즘의 변경입니다.단, 이 알고리즘에서는 단일 PRIVE 메시지를 다른 노드에 송신함으로써 연공서열과 다른 노드에 크리티컬섹션을 넘기는 방식이 도입되었습니다.따라서 권한이 있는 노드는 크리티컬섹션을 사용할 수 있으며 권한이 없는 노드는 사용할 수 없습니다.프로세스가 크리티컬섹션에 들어가려고 하는데 토큰이 없는 경우 요청 메시지를 시스템 내의 다른 모든 프로세스에 브로드캐스트합니다.토큰이 있는 프로세스가 현재 중요한 섹션에 없는 경우 토큰을 요청 프로세스로 보냅니다.알고리즘에서는 요청 번호를 증가시켜 메시지가 순서대로 도착할 수 있도록 합니다.

알고리즘 설명

n$\displaystyle$n을$$ 프로세스 수로 $합니다{\displaystyle }$.각 프로세스는 1${\displaystyle }$,${\displaystyle }$.${\displaystyle }$,$$ \ $displaystyle$ 1, $...n$의 정수로 식별됩니다.

데이터 구조

각 프로세스에서 하나의 데이터 구조를 유지합니다.

• $array{\displaystyle }$ ${\displaystyle {RN}_{}}$ i${\displaystyle {}_{}}$[ $]{$ $display style$ $RN$_ { $i$$$} [ $n$} $$（ Request Number ）$$。${\displaystyle {}_{}}$서 ${\displaystyle {RN}_{}i}$ [ j $]{$ $display style$$$RN _ { $i$}[ $j$}는$jdisplay style$에서 $받은$ 마지막 Request Number를 저장합니다.

토큰에는 다음 두 가지 데이터 구조가 포함됩니다.

• $배열{\displaystyle }$ ${\displaystyle \mathrm{LN}}$ $]$ {$displaystyle$LN [${\displaystyle n}$$]$ $$（ Last request Number ） 。${\displaystyle \mathrm{여기}}$서${\displaystyle }$LN [ j$]{$ $displaystyle$LN [ $j ]$에는 토큰이 정상적으로 부여된 $프로세스$의 최신 Request Number$$j {$displaystyle$ j}가$$ 저장됩니다.
• $큐{\displaystyle }$ Q$($$토큰을 기다리는$ 프로세스의 ID를 저장함$)$

알고리즘.

크리티컬 섹션 요구(CS)

$프로세스{\displaystyle }$i(\$displaystyle$i$$)가 CS에 들어가는 경우 토큰이 없는 경우 다음과 같이 처리됩니다.

• 시퀀스 $번호{\displaystyle }$ ${\displaystyle {RN}_{}}$i [$]{displaystyle RN_{i}[i]}$가 증가합니다.
• 새로운 시퀀스 번호를 포함한 요구 메시지를 시스템 내의 모든 프로세스에 송신합니다.

CS의 릴리스

$프로세스$i가$$ CS를 떠나면 다음과 같이 처리됩니다.

• 토큰의 ${\displaystyle \mathrm{LN}}$[$]({displaystyle LN[$i])을$$ ${\displaystyle {}_{}}$[$]({displaystyle RN_{i}[i$와 $동일$하게 $설정$합니다.$이$는 요청 ${\displaystyle {RN}_{}i}$ [${\displaystyle }$i$$]{$displaystyle RN_{i}[i]}$이(가) 실행되었음을 나타냅니다.
• 토큰 큐 $Q$에 없는 $프로세스{\displaystyle }$ k$(\$$displaystyle$ Q$)$마다$$RNi [$=$ ${\displaystyle \mathrm{LN}}$ ${\displaystyle [k]}$ +$$(\$displaystyle RN_{i}[k$]=의 $경우{\displaystyle }$ k($style$ k$)$가 Q$(\displaystyle$ Q$)$에 $추가$됩니다.$LN[k]+1$$이$는 프로세스$$k\$displaystyle$k에$$ 미결 요청이 있음을 나타냅니다.
• 이 업데이트 후에도 토큰 큐$Q{\displaystyle }$(\$displaystyle$Q)가$$ 비어 있지 않으면 Q$(\displaystyle$ Q$)$에서 프로세스 $ID{\displaystyle }$j(\$displaystyle$ j$)$를 팝하여 j$(\displaystyle$ j$)$로 토큰을 전송합니다.
• 그렇지 않으면 토큰이 유지됩니다.

요청 접수

$프로세스{\displaystyle }$j(\$displaystyle$ j$)$가 시퀀스 $번호{\displaystyle }$s(\$displaystyle$ s$)$의 요청을 i$(\displaystyle$ i$)$로부터 수신하면 다음과 같이 됩니다.

• ${\displaystyle {}_{}}$ ${\displaystyle N_{}j}$ [i$$]{$display style RN_{$j}[$i]}$을(를)${\displaystyle x{}_{}}$(${\displaystyle R_{}}$ N j [${\displaystyle i]}$ ,${\displaystyle s}$){$displaystyle$ $(RN_$${j}[i$$],s)$로 $설정$합니다(s $R$ [ { $displaystyle$ s }의 ).
• $프로세스{\displaystyle }$j {$displaystyle$ j$}$에 토큰이 있고 CS에 없는 경우 $및{\displaystyle }$ R ${\displaystyle N_{}}$j [${\displaystyle i]}$ $==$ ${\displaystyle L}$N [${\displaystyle i]}$ +$$ {\$displaystyle RN_{j}[i$]==LN$[i]+1}($미결 요청을 나타냄), 토큰을 i$\displaystyle$i로 $전송$합니다.

CS의 실행

프로세스는 토큰을 취득하면 CS에 들어갑니다.

성능

• $CS{\displaystyle \mathrm{}}$ 호출에 대해 0$(\displaystyle$ 0$)$ $또는$ N$(\displaystyle$ N$)$ 메시지$$ 중 하나(프로세스가 토큰을 보유하고 있는 경우 메시지 없음, $그렇지{\displaystyle }$않은 ${\displaystyle \mathrm{경우}}$N - 1(\$displaystyle$$$N-1$$) $요구{\displaystyle \mathrm{}}$및 1(\$displaystyle$ 1) 응답$$)
• 동기화 $지연$은 0$(\displaystyle$ 0$)$$$ $또는$ N$displaystyle$$$$N-1)$ $요구$와 1$(\displaystyle$1) $$입니다.

알고리즘에 관한 주의사항

• 현재 토큰을 보유하고 있는 사이트만 CS에 액세스할 수 있습니다.

• CS 할당에 관련된 모든 프로세스

• 모든 노드에 보낸 요청 메시지

• Lamport의 논리 클럭을 기반으로 하지 않음
• 알고리즘은 대신 시퀀스 번호를 사용합니다.

• 오래된 요청을 추적하는 데 사용됩니다.
• 각 사이트에서 독립적으로 진행됩니다.

알고리즘의 주요 설계상의 문제점은 다음과 같습니다.

• 현재 요청과 오래된 요청 구분
• 다음에 토큰을 가져올 사이트 결정

레퍼런스