Lamport의 베이커리 알고리즘: Lamport의 베이커리 알고리즘-C++-php.cn

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

WBOY

풀어 주다： 2023-08-25 20:45:17

앞으로

1815명이 탐색했습니다.

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 - 이 알고리즘은 각 프로세스 또는 스레드에 대한 상태 정보를 저장해야 하기 때문에 토큰 순서를 결정하는 데 더 많은 메모리와 처리 시간이 필요합니다.
복잡성 - 경쟁 조건과 교착 상태를 신중하게 처리해야 하고 뮤텍스나 세마포어와 같은 동기화 메커니즘을 사용할 수 있으므로 알고리즘 적용이 어려울 수 있습니다.
李>