피터슨 알고리즘

Peterson's algorithm

Peterson's 알고리즘(또는 Peterson's 솔루션)은 상호 배제를 위한 동시 프로그래밍 알고리즘으로, 두 개 이상의 프로세스가 통신용 공유 메모리만 사용하여 단일 사용 리소스를 충돌 없이 공유할 수 있습니다.1981년 [1]게리 L. 피터슨에 의해 공식화 되었다.Peterson의 원래 공식은 두 개의 공정에서만 작동했지만, 알고리즘은 두 [2]개 이상에 대해 일반화할 수 있습니다.

알고리즘

알고리즘은 다음 두 가지 변수를 사용합니다.flag그리고.turn.aflag[n]의 가치true프로세스가n중요한 섹션으로 들어가려고 합니다.P1이 크리티컬섹션으로 들어가지 않고 P1이 설정에 의해 P0에 우선순위를 부여한 경우 프로세스 P0에 대해 크리티컬섹션으로의 입구가 허가됩니다.turn로.0.

피터슨 알고리즘
부울 깃발[2] = {거짓의, 거짓의}; 인트 돌다; 
P0:      깃발[0] = 진실의; P0_gate: 돌다 = 1;          하는 동안에 (깃발[1] == 진실의 & & 돌다 == 1)          {              // 비지 대기          }          // 크리티컬 섹션          ...          // 중요 섹션의 끝          깃발[0] = 거짓의; 
P1:      깃발[1] = 진실의; P1_gate: 돌다 = 0;          하는 동안에 (깃발[0] == 진실의 & & 돌다 == 0)          {              // 비지 대기          }          // 크리티컬 섹션          ...          // 중요 섹션의 끝          깃발[1] = 거짓의;

이 알고리즘은 임계 섹션 문제를 해결하기 위한 세 가지 필수 기준을 충족합니다.while 조건은 [1]프리엠프션에서도 동작합니다.

세 가지 기준은 상호 배제, 진행 및 제한 [3]대기입니다.

부터turn는 2개의 값 중 하나를 취할 수 있으며, 1비트로 대체할 수 있습니다.즉, 알고리즘에 필요한 메모리는 [4]: 22 3비트뿐입니다.

상호 배타

P0과 P1은 동시에 크리티컬섹션에 있을 수 없습니다.P0이 크리티컬섹션에 있는 경우flag[0]정말이에요.또, 다음의 어느 쪽인가flag[1]이false(즉, P1이 크리티컬섹션을 떠났다는 의미), 또는turn이0(즉, P1이 중요한 섹션으로 들어가려고 하고 있습니다만, 대기하고 있습니다)또는 P1이 라벨에 표시되어 있습니다.P1_gate(설정 후 크리티컬섹션에 들어갈 수 없습니다).flag[1]로.true설정하기 전에turn로.0기다리느라 바쁘네요.따라서 두 프로세스가 모두 중요한 부분에 있다면 주정부는 이 문제를 반드시 해결해야 한다는 결론을 내리게 됩니다.flag[0]그리고.flag[1]그리고.turn = 0그리고.turn = 1어떤 상태도 두 가지를 모두 만족시킬 수 없다.turn = 0그리고.turn = 1따라서 두 프로세스가 모두 중요한 섹션에 있는 상태는 없습니다.(이것에는, 엄밀한 논점이 기재되어 있습니다).[5]

진보.

진행상황은 다음과 같이 정의됩니다.중요한 섹션에서 프로세스가 실행되고 있지 않고 일부 프로세스가 크리티컬 섹션에 들어가기를 원하는 경우, 나머지 섹션에서 실행되지 않은 프로세스만이 다음 중 어느 프로세스가 크리티컬 섹션에 들어갈 것인지를 결정하는 데 참여할 수 있습니다.프로세스 또는 스레드의 경우 나머지 섹션은 중요한 섹션과 관련이 없는 코드의 일부입니다.이 선택은 무기한 [3]연기할 수 없습니다.다른 프로세스가 크리티컬섹션에 들어가겠다는 플래그를 설정한 경우 프로세스는 즉시 크리티컬섹션에 다시 들어갈 수 없습니다.

제한 대기

경계 대기(bounded waiting) 또는 경계 바이패스(bounded bypass)는 프로세스가 임계 섹션에 진입하려는 욕구를 나타낸 후 다른 프로세스에 의해 우회되는 횟수를 의미합니다.[3][4]: 11 Peterson 알고리즘에서는 프로세스가 임계 섹션에 들어갈 때까지 한 바퀴 이상 기다리지 않습니다.

필터 알고리즘: 3개 이상의 프로세스에 대한 Peterson 알고리즘

10개의 프로세스가 진행 중인 필터 알고리즘의 스냅샷입니다.마지막으로 입력할 때는 굵은 글씨와 밑줄이 표시됩니다.(NB: 스케줄에 따라 마지막으로 입력되는 항목이 올바르지 않을 수 있습니다.)언제든지 테이블에 대한 갱신은 레벨0의 새로운 프로세스 삽입, 소정의 레벨에서 마지막으로 시작하는 프로세스로의 변경 또는1레벨 위로 이동하는 프로세스(최종 입력이 아닌 경우 또는 그 레벨 이상의 프로세스가 존재하지 않는 경우)입니다.

필터 알고리즘은 Peterson의 알고리즘을 N [6]> 2 프로세스로 일반화합니다.부울 플래그 대신 프로세스당 정수 변수를 Single-Writer/Multiple-Reader(SWMR; 싱글 라이터/멀티 리더) 원자 레지스터에 저장하고 N - 1개의 변수를 유사한 레지스터에 추가해야 합니다.레지스터는 의사 코드로 배열로 나타낼 수 있습니다.

level : n개의 정수 배열 last_to_enter : N - 1개의 정수 배열

그레벨 변수는 N - 1까지의 값을 취하며, 각 값은 임계 [6]섹션 앞에 있는 개별 "대기실"을 나타냅니다.프로세스는 한 룸에서 다음 룸으로 진행되며 중요한 섹션인 N-1 룸에서 종료됩니다.특히 잠금을 취득하려면 프로세스 i를[4]: 22 실행합니다. 

i ← 0 ~ N - 1 배타적 수준 [i] ← last last_to_enter[filter] ← i인 반면 last_to_enter[filter] = i이며 k there i가 존재하며 이 수준 [k] ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ i i i 。

중요 섹션을 종료할 때 잠금을 해제하려면 프로세스 i는 레벨 [i]를 -1로 설정합니다.

이 알고리즘이 상호 배제를 달성한다는 것은 다음과 같이 입증할 수 있다.레벨 [i]보다 높은 레벨의 프로세스가 존재하지 않는 경우 프로세스i는 내부 루프를 종료합니다.따라서 다음 대기실은 비어 있습니다.또한 마지막 대기실에서는 다른 프로세스가 대기실에 가입합니다.레벨 0에서는 모든 N개의 프로세스가 동시에 대기실 0에 진입하더라도 N-1을 넘지 않고 마지막 1이 마지막으로 대기실에 진입한다.마찬가지로 다음 단계에서는 N - 2가 진행되며, 최종 단계에서는 1개의 프로세스만 대기실에서 나와 임계구간에 들어갈 수 있으며 상호 [4]: 22–24 배제를 허용한다.

알고리즘은 굶주림이 없는 것으로 나타날 수도 있습니다.즉, 루프로 들어가는 모든 프로세스가 최종적으로 루프를 종료합니다(중요한 섹션에 무기한 머무르지 않는 것을 전제로 합니다).입증이 N - 1에서 아래로 진행됩니다.N - 1에 있는 프로세스는 임계 섹션에 있으며, 이를 종료하는 것으로 가정합니다.모든 하위 레벨 ,에서는 프로세스 i가 영원히 대기하는 것은 불가능하다. 왜냐하면 다른 프로세스 j가 대기실에 들어가 last_to_enter[disable] ← j와 "liveing" i를 설정하기 때문이다.그렇지 않으면 대기실에 있는 모든 프로세스 j는 상위 레벨이어야 하며 귀납 가설에 따라 최종적으로 종료된다.h 루프를 실행하고 레벨을 리셋하여 모든 kµi에 대해 레벨 [k]< 및 i가 다시 [4]: 24–25 루프를 종료하도록 합니다.

기아의 자유는 사실 알고리즘이 제공하는 가장 높은 생존 보장이며, 2프로세스의 Peterson 알고리즘과는 달리 필터 알고리즘은 경계 [4]: 25–26 대기를 보장하지 않습니다.

메모

하드웨어 수준에서 작업할 때 일반적으로 Peterson의 알고리즘은 원자적 접근을 달성하기 위해 필요하지 않습니다.일부 프로세서는 메모리 버스를 잠그는 것으로 SMP 시스템에서 상호 배제를 제공하기 위해 사용할 수 있는 테스트 및 설정이나 비교 및 스왑과 같은 특별한 명령을 가지고 있습니다.

대부분의 최신 CPU는 실행 효율성을 높이기 위해 메모리 액세스를 재정렬합니다(정렬 가능한 유형에 대해서는 메모리 순서 참조).이러한 프로세서는 일반적으로 메모리 장벽 명령을 통해 메모리 액세스 스트림에서 순서를 강제하는 방법을 제공합니다.메모리 액세스를 재정렬하는 프로세서에서 Peterson 및 관련 알고리즘을 구현하려면 일반적으로 이러한 연산을 사용하여 순차 연산이 잘못된 순서로 발생하는 것을 방지해야 합니다.메모리 액세스의 순서 변경은 명령을 다시 정렬하지 않는 프로세서(Xbox [citation needed]360의 PowerPC 프로세서 등)에서도 발생할 수 있습니다.

이러한 CPU의 대부분은 다음과 같은 일종의 보증된 아토믹 동작도 가지고 있습니다.XCHGAlpha, MIPS, PowerPC 및 기타 아키텍처에서 로드링크/스토어컨디셔닝이 가능합니다.이러한 순서는, 순수한 공유 메모리 어프로치보다, 동기 프리미티브를 보다 효율적으로 구축하는 방법을 제공하는 것을 목적으로 하고 있습니다.

「 」를 참조해 주세요.

각주

  1. ^ a b G. L. Peterson: "상호 배타 문제에 관한 신화", 정보처리 서신 12(3) 1981, 115~116
  2. ^ 운영체제 리뷰(Operating Systems Review, 1990년 1월)에서 설명한 바와 같이("상호 제외 알고리즘의 증명", M Hoffri).
  3. ^ a b c 실버즈차츠.운영체제 개념:제7판John Wiley and Sons, 2005, 194페이지.
  4. ^ a b c d e f Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. ISBN 3642320279.
  5. ^ F. B. 슈나이더동시 프로그래밍, Sringer Verlag, 1997, 185~196페이지.
  6. ^ a b Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. p. 28–31. ISBN 9780123977953.

외부 링크

  • https://elixir.bootlin.com/linux/latest/source/arch/arm/mach-tegra/sleep.S Peterson 알고리즘 구현