리카르트-아그라왈라 알고리즘

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

Ricart-Agrawala 알고리즘은 분산 시스템에서 상호 배제를 위한 알고리즘입니다.이 알고리즘은 Lamport 분산 상호 제외 $알고리즘$의 확장 및 최적화로$$ $\$^[1]$displaystyle$ack 메시지가 $필요$하지 않습니다.그것은 글렌 리카트와 아쇼크 아그라왈라에 의해 개발되었다.

알고리즘.

용어.

• 사이트는 Ricart-Agrawala 알고리즘을 실행하는 컴퓨팅 디바이스입니다.
• 요청 사이트는 중요한 섹션으로의 진입을 요청하는 사이트입니다.
• 수신 사이트는 요청 사이트로부터 요청을 수신하는 다른 모든 사이트입니다.

알고리즘.

요청 사이트

• 모든 사이트에 메시지를 보냅니다.이 메시지에는 사이트 이름과 논리 클럭에 따른 시스템의 현재 타임스탬프가 포함됩니다(다른 사이트와 동기화되어 있는 것으로 간주됩니다).

수신 사이트

• 요청 메시지를 수신하면 다음과 같은 경우에만 타임스탬프가 찍힌 응답 메시지를 즉시 발송합니다.

• 수신 프로세스가 현재 중요 섹션에 관심이 없습니다.
• 수신 프로세스의 우선순위가 낮다(통상, 이것은 타임 스탬프가 나중에 있는 것을 의미한다).

• 그렇지 않으면 수신 프로세스가 응답 메시지를 지연시킵니다.즉, 수신 프로세스가 크리티컬섹션 자체를 사용한 후에만 응답이 송신됩니다.

중요 섹션:

• 요청 사이트는 모든 응답 메시지를 수신한 후에만 critical 섹션에 들어갑니다.
• critical 섹션을 종료하면 사이트는 모든 지연 응답 메시지를 발송합니다.

성능

• 최대 네트워크 메시지 수: $2{\displaystyle \mathrm{}†}$ (${\displaystyle N}$ -${\displaystyle 1}$)$${$displaystyle$ 2 * ( N -$1$) }
• 동기화 지연:1개의 메시지 전파 지연

일반적인 최적화

$사이트{\displaystyle {}_{}}$ $(\$가 $사이트{\displaystyle {}_{}}$ $(\$로부터 ${\displaystyle \mathrm{re}}$ p ${\displaystyle l}$ $(\displaystyle$P_{j}) $메시지$를 수신하면 $사이트{\displaystyle {}_{}}$ $(\$})가$$ 이후 $(\$})의 허가를 받지 않고 여러 번 크리티컬섹션에 들어갈 수 있습니다.Pi$(\$가 $(\$에게 ${\displaystyle \mathrm{re}}$ ${\displaystyle p}$ ${\displaystyle l}$y(\$displaystyle$ 응답$)$ $메시지$를 보낸 $순간{\displaystyle {}_{}}$.이를 루카이롤-카르발류 최적화 또는 루카이롤-카르발류 알고리즘이라고 합니다.

문제

이 알고리즘의 문제 중 하나는 노드의 장애입니다.이러한 상황에서는 프로세스가 영원히 굶주릴 수 있습니다.이 문제는 타임아웃 후 노드의 장애를 검출함으로써 해결할 수 있습니다.

「 」를 참조해 주세요.

• 램포트의 베이커리 알고리즘
• Lamport 분산 상호 제외 알고리즘
• 마에카와 알고리즘
• 스즈키-카사미 알고리즘
• 레이먼드 알고리즘
• 나이미-트레헬 알고리즘

레퍼런스

• Maekawa, M., Oldehoft, A.올데호프트, R.(1987)운영 체제:고급 개념벤자민/커밍스 출판사, Inc.