Lamport의 베이커리 알고리즘: Lamport의 베이커리 알고리즘

Lamport's Bakery 방법이라는 동기화 방법은 병렬 컴퓨팅 시스템의 임계 섹션 문제를 해결합니다. 여러 프로세스가 동시에 공유 리소스를 사용해야 하는데 하나의 프로세스만 그렇게 할 수 있는 경우 이를 임계 영역 문제라고 합니다. 충돌을 방지하고 시스템 정확성을 보장하기 위한 과제는 각 프로세스가 상호 배타적인 방식으로 리소스를 사용하는지 확인하는 것입니다.

Lamport 베이킹 알고리즘의 의사 코드

다음은 Lamport의 베이킹 알고리즘에 대한 의사 코드입니다 -

• N 크기의 배열("select"라고 함)을 초기화합니다. 여기서 N은 총 프로세스 수를 모두 0으로 초기화합니다.

• 숫자라고 불리는 크기가 N이고 모두 0인 배열을 초기화합니다.

• 각 프로세스는 임계 섹션에 들어가고 싶을 때 다음 코드를 실행합니다. -

  • 선택 설정[i] = 1

  • 세트 수[i] = max(수[0], 수[1], ..., 수[N-1]) + 1

  • 선택 설정[i] = 0

  • 다른 모든 프로세스 j에 대해 (number[j] == 0) 또는 (number[i], i)

  • 핵심 부분을 입력하세요

• 각 프로세스는 중요 섹션을 떠날 때 다음 코드를 실행합니다 -

  • 설정된 숫자[i] = 0

Lamport 베이킹 알고리즘 코드

다음은 실제 Lamport의 베이킹 알고리즘을 설명하는 코드 조각입니다. 이 예제에서는 구현 언어로 C++를 사용합니다.

으아악

출력

으아악

Lamport 베이킹 알고리즘의 장점

Lamport 베이킹 알고리즘의 장점은 다음과 같습니다 -

• 공유 리소스에 대한 액세스를 요청하는 프로세스나 스레드에 서로 다른 토큰을 제공하여 공정성이 보장됩니다.

• 지정된 값에 따라 토큰을 배포하면 기아를 방지할 수 있습니다.

• 간단하고 이해하고 실행하기 쉬운 토큰 기반 전략을 사용하세요.

• 효율적이며 복잡한 데이터 구조나 프로세스 간 상호 작용이 필요하지 않습니다.

• 특수 하드웨어나 하드웨어 도움 없이 상호 배제를 제공합니다.

• 다양한 적용 범위와 강력한 적응성을 갖추고 있어 다양한 시나리오에 적용하여 동시 계산의 공정성과 상호 배제를 보장할 수 있습니다.

• 분산 또는 병렬 시스템에서 작업하는 소프트웨어 엔지니어에게 유용한 도구입니다.

램포트 베이킹 알고리즘의 단점

• Busy Wait - 이 알고리즘은 바쁜 대기를 호출합니다. 이로 인해 특히 동일한 공유 리소스에 액세스하기 위해 경쟁하는 프로세스나 스레드가 많은 경우 비효율성과 높은 CPU 사용률이 발생할 수 있습니다.

• Hungry - 알고리즘이 정의를 보장하지만 안전 장치는 없습니다. 경우에 따라 프로세스나 스레드가 반복적으로 중지될 수 있으며, 이로 인해 토큰을 얻고 리소스에 액세스할 수 없습니다.

• Overhead - 이 알고리즘은 각 프로세스 또는 스레드에 대한 상태 정보를 저장해야 하기 때문에 토큰 순서를 결정하는 데 더 많은 메모리와 처리 시간이 필요합니다.

• 복잡성 - 경쟁 조건과 교착 상태를 신중하게 처리해야 하고 뮤텍스나 세마포어와 같은 동기화 메커니즘을 사용할 수 있으므로 알고리즘 적용이 어려울 수 있습니다.

  李>

결론

Lamport의 베이킹 알고리즘이라는 상호 배타적 알고리즘은 개별 프로세스나 스레드가 서로 간섭하지 않고 공유 리소스를 활용할 수 있도록 보장합니다. 기아를 예방하고 정의를 보장하는 간단한 알고리즘입니다.

알고리즘은 리소스 액세스 요청을 하는 각 프로세스나 스레드에 토큰을 할당한 다음 이러한 토큰의 값을 비교하여 토큰이 제공된 순서를 결정하는 방식으로 작동합니다. 리소스는 가장 적은 토큰을 사용하는 작업부터 먼저 사용할 수 있습니다.

위 내용은 Lamport의 베이커리 알고리즘: Lamport의 베이커리 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!