램포트의 베이커리 알고리즘

Lamport's bakery algorithm
참고 항목: Lamport의 분산 상호 제외 알고리즘

Lamport의 베이커리 알고리즘은 동시 시스템의 형식적 정확성에 대한 오랜 연구의 일환으로 컴퓨터 과학자 Leslie Lamport가 고안한 컴퓨터 알고리즘으로, 상호 배제를 통해 여러 스레드 간의 공유 리소스 사용에 대한 안전성을 향상하는 것을 목적으로 하고 있습니다.

컴퓨터 과학에서는 여러 스레드가 동시에 동일한 리소스에 액세스하는 것이 일반적입니다.두 개 이상의 스레드가 같은 메모리 위치에 쓰려고 하거나 다른 스레드가 메모리 위치에 쓰기를 완료하기 전에 한 스레드가 메모리 위치를 읽으면 데이터가 손상될 수 있습니다.Lamport의 베이커리 알고리즘은 동시 스레드가 코드의 중요한 섹션에 동시에 들어가는 것을 방지하고 데이터 파손의 위험을 제거하기 위해 설계된 많은 상호 제외 알고리즘 중 하나입니다.

알고리즘.

유추

Lamport는 입구에 번호 매기기 기계가 있는 빵집을 구상하여 각 고객에게 고유한 번호를 부여했습니다.손님이 입점함에 따라 숫자가 1개씩 증가한다.글로벌 카운터는 현재 서비스를 받고 있는 고객의 수를 표시합니다.다른 모든 고객은 베이커에서 현재 고객의 서비스가 종료되고 다음 번호가 표시될 때까지 대기해야 합니다.고객이 쇼핑을 마치고 번호를 폐기하면 점원은 번호를 늘려 다음 고객을 응대할 수 있게 된다.그 고객은 다시 쇼핑하기 위해 번호 기계에서 다른 번호를 뽑아야 합니다.

유추에 따르면, "고객"은 글로벌 변수에서 얻은 문자 i로 식별되는 스레드입니다.

컴퓨터 아키텍처의 한계로 인해 Lamport의 일부 비유는 약간의 수정이 필요합니다.여러 스레드가 요구될 때 동일한 번호n을 얻을 수 있습니다.이것은 피할 수 없습니다(알고리즘의 목표인 상호 제외 문제를 먼저 해결하지 않으면).따라서 스레드 식별자 i도 priority로 간주됩니다.값 i가 작을수록 우선순위가 높아지며 우선순위가 높은 스레드가 먼저 위험 섹션에 들어갑니다.

[ Critical ]섹션

중요한 부분은 리소스에 대한 배타적 액세스가 필요하며 한 번에 하나의 스레드로만 실행될 수 있는 코드 부분입니다.제과점 비유에서, 고객이 제빵사와 거래할 때 다른 사람들은 기다려야 한다.

스레드가 크리티컬섹션에 들어가려면 지금 바로 들어갈 차례인지 확인해야 합니다.다른 모든 스레드 번호n을 체크하여 스레드가 가장 작은지 확인합니다.다른 스레드의 번호가 같을 경우 i가 가장 작은 스레드가 먼저 critical 섹션에 들어갑니다.

의사 코드에서는 스레드a와 b의 비교는 다음 형식으로 기술할 수 있습니다.

// na - 스레드 a의 고객 번호, // ia - 스레드 a의 고객 번호, (na, ia) < (nb, ib)

이는 다음과 같습니다.

(na < nb) 또는 (na == nb) 및 (ia < ib)

스레드는 중요한 작업을 종료하면 번호를 삭제하고 중요하지 않은 섹션에 들어갑니다.

중요하지 않은 섹션

중요하지 않은 섹션은 배타적 액세스가 필요하지 않은 코드 부분입니다.이는 다른 스레드의 리소스와 실행을 방해하지 않는 일부 스레드별 계산을 나타냅니다.

이 부분은 거스름돈을 지갑에 다시 넣는 것과 같은 쇼핑 후에 일어나는 행동과 유사합니다.

알고리즘의 실장

정의들

Lamport의 원본 문서에서는 입력 변수를 선택이라고 하며 다음 조건이 적용됩니다.

  • [i] 및 [i]를 선택하는 단어는 프로세스 i의 메모리에 있으며 처음에는 0입니다.
  • 숫자 [i]의 값 범위는 무제한입니다.
  • 프로세스는 언제든지 실패할 수 있습니다.장애가 발생하면 즉시 중요하지 않은 섹션으로 이동하여 정지한다고 가정합니다.그 후, 메모리에서 판독치가 임의의 값을 제공하는 기간이 있을 수 있습니다.최종적으로 메모리로부터의 판독치는 0이 됩니다.

코드 예시

유사 코드

이 예에서는 모든 스레드가 동일한 "기본" 함수인 스레드를 실행합니다.실제 응용 프로그램에서는 스레드마다 "주요" 기능이 다른 경우가 많습니다.

원본 문서와 마찬가지로 스레드는 임계 섹션에 들어가기 전에 스스로 점검합니다.루프 상태는 false로 평가되기 때문에 지연은 크지 않습니다. 

  // 전역 변수의 선언 및 초기 값   들어가는: 배열 [1..NUM_THREADS] 의 부울 = {거짓의};   번호: 배열 [1..NUM_THREADS] 의 정수 = {0};    잠그다(정수 i) {       들어가는[i] = 진실의;       번호[i] = 1 + 맥스.(번호[1], ..., 번호[NUM_THREADS]);       들어가는[i] = 거짓의;       위해서 (정수 j = 1; j <=> NUM_THREADS; j++) {           // 스레드 j가 번호를 받을 때까지 기다립니다.           하는 동안에 (들어가는[j]) { /* 아무것도 */ }           // 숫자가 작거나 같은 스레드가 모두 표시될 때까지 기다립니다.           // 번호이지만 우선순위가 높은 작업을 완료합니다.           하는 동안에 ((번호[j] != 0) & & ((번호[j], j) < > (번호[i], i))) { /* 아무것도 */ }       }   }      언락(정수 i) {       번호[i] = 0;   }    실(정수 i) {       하는 동안에 (진실의) {           잠그다(i);           // 중요한 섹션은 여기에 있습니다.           언락(i);           // 중요하지 않은 섹션...       }   }

각 스레드는 자체 스토리지만 쓰고 읽기만 공유합니다.이 알고리즘이 예를 들어 비교 및 스왑과 같은 하위 수준의 "원자" 연산 위에 구축되지 않은 것은 주목할 만하다.원본 증거는 동일한 스토리지 셀에 대한 읽기 및 쓰기가 중복되는 경우 쓰기만 [clarification needed]정확해야 한다는 것을 보여줍니다.읽기 작업은 임의의 번호를 반환할 수 있습니다.따라서 이 알고리즘을 사용하여 동기 프리미티브가 없는 메모리(예: 두 컴퓨터 간에 공유되는 단순한 SCSI 디스크)에서 상호 제외를 구현할 수 있습니다.

7 ~ 13행 주위에 '잠금'이 없기 때문에 Entering 변수의 필요성은 분명하지 않을 수 있습니다.그러나 변수가 제거되고 두 프로세스가 동일하게 계산되었다고 가정합니다.Number[i]설정 전에 우선순위가 높은 프로세스가 프리엠프트된 경우Number[i]priority가 낮은 프로세스에서는 다른 프로세스의 번호가 0인 것을 확인하고 크리티컬섹션에 들어갑니다나중에 priority가 높은 프로세스에서는 동등함을 무시합니다.Number[i]priority가 낮은 프로세스의 경우 및 critical 섹션에도 들어갑니다.그 결과, 2개의 프로세스가 동시에 크리티컬섹션에 들어갈 수 있습니다.베이커리 알고리즘에서는 Entering 변수를 사용하여 6행의 할당이 원자적인 것처럼 보이게 합니다.프로세스 i와 같은 번호를 선택하는 프로세스j에 대해 0과 같은 숫자는 표시되지 않습니다.

단일 프로세스 시스템에서 또는 공동 멀티태스킹 하에서 의사 코드를 구현하는 경우 "아무것도 하지 않음" 섹션을 운영체제에 즉시 다음 스레드로 전환하도록 통지하는 코드로 대체하는 것이 좋습니다.이 원시는 종종 다음과 같이 언급된다.yield.

Lamport의 베이커리 알고리즘은 시퀀셜 일관성 메모리 모델을 상정하고 있습니다.이러한 메모리 모델을 실장하는 언어 프로세서나 멀티 코어 프로세서는 거의 없습니다.따라서 알고리즘을 올바르게 구현하려면 일반적으로 펜스를 삽입하여 [1]재정렬을 금지해야 합니다.

PlusCal 코드

N을 프로세스 수로 선언하고 N을 자연수로 가정합니다. 

계속 N N Nat \in N \in

P를 프로세스의 집합 {1, 2, ..., N}으로 정의합니다. 

P == 1..n

변수 num 및 flag는 global로 선언됩니다. 

--syslog AtomicBakery { variable num = [i \in P -> 0], 플래그 = [i \in P -> FALSE];

다음은 다음을 정의합니다.LL(j, i)진짜 if<<num[j], j>는 통상적인 사전순으로 <<num[i], i>보다 작거나 같습니다. 

정의 { LL(j, i) == \/num[j] < num[i] \//\num[i] = num[j] /\j = < i }

P의 각 요소에 대해 로컬 변수가 읽지 않음, 최대 및 nxt인 프로세스가 있습니다.연속되는 라벨 p1, ..., p7, cs 사이의 스텝은 atomic으로 간주됩니다.와의 스테이트먼트(x \in S) { body }id를 set S의 결정적으로 선택되지 않은 요소로 설정하고 body를 실행합니다.expr 값이 TRUE일 경우에만 wait expr 문을 포함하는 단계를 수행할 수 있습니다.

프로세스(p \in P) 변수 읽지 않음 \in Subset P, max \in Nat, nxt \in P; { p1: while (TRUE) {읽지 않음 := P \self} ; max := 0; flag [ self] := TRUE; p2: while (i \in { self}) {while (i \in {\in p} {\in p} {\i } {with (i } )}}; p3: num[self] : = max + 1; p4: flag[self] : = FALSE; 읽지 않음 : = P \ { self } ; p5: while (self # ) { (i \in read) {nxt : i ; } ; wait ~ flag [ nxt } ; p6: wait \/nxt] ; nxt] = 0/nxt = 0 . nxt ）num [ self ] : = 0 ; } }

자바 코드

AtomicIntegerArray 클래스는 내장된 Atomic 작업이 아니라 get 및 set 메서드가 휘발성 읽기 및 쓰기처럼 작동하기 때문에 사용합니다.Java 메모리 모델에서는 쓰기가 모든 스레드에 즉시 표시됩니다. 

ATOMIC Integer Array 딱지 떼다 = 신규 ATOMIC Integer Array(스레드); // 줄에 있는 스레드에 대한 티켓, n - 스레드 수 // Java는 '티켓'의 각 요소를 0으로 초기화합니다.   ATOMIC Integer Array 들어가는 = 신규 ATOMIC Integer Array(스레드); // 스레드가 줄에 들어갈 때 1 // Java는 'Entering'의 각 요소를 0으로 초기화합니다.   일반의 무효 잠그다(인트 pid) // 스레드 ID {     들어가는.세트(pid, 1);     인트 맥스. = 0;     위해서 (인트 i = 0; i < > 스레드; i++)     {         인트 현재의 = 딱지 떼다.얻다(i);         한다면 (현재의 > 맥스.)         {             맥스. = 현재의;         }     }     딱지 떼다.세트(pid, 1 + 맥스.);      들어가는.세트(pid, 0);     위해서 (인트 i = 0; i < > 딱지 떼다.길이(); ++i)     {         한다면 (i != pid)         {             하는 동안에 (들어가는.얻다(i) == 1) { 실.산출하다(); } // 다른 스레드가 티켓을 선택할 때까지 기다립니다.             하는 동안에 (딱지 떼다.얻다(i) != 0 & & ( 딱지 떼다.얻다(i) < > 딱지 떼다.얻다(pid)                        (딱지 떼다.얻다(i) == 딱지 떼다.얻다(pid) & & i < > pid)))             { 실.산출하다(); }         }     }     // 중요한 섹션은 여기에 있습니다. }  일반의 무효 언락(인트 pid) {   딱지 떼다.세트(pid, 0); }

「 」를 참조해 주세요.

레퍼런스

  1. ^ 친메이 나라얀 시바시스 구하 SSC의 정확성 증명을 사용하여 Arun-Kumar 동시 프로그램에서의 펜스 추론
  • 원본 용지
  • Lamport는 출판물 페이지에서 알고리즘에 관한 몇 가지 의견을 추가했습니다.

외부 링크