•  03-07-2019
  •  | 
  •  

문제

다음 의사 코드를 살펴보십시오.

boolean blocked[2];
int turn;
void P(int id) {
      while(true) {
             blocked[id] = true;
             while(turn != id) {
                    while(blocked[1-id])
                    /* do nothing */;
                    turn = id;
             }
             /* critical section */
             blocked[id] = false;
             /* remainder */
      }
}
void main() {
      blocked[0] = false;
      blocked[1] = false;
      turn = 0;
      parbegin(P(0), P(1)); //RUN P0 and P1 parallel
}

A는 위의 코드를 사용하여 간단한 상호 배제 솔루션을 구현할 수 있다고 생각했습니다. 그러나 그것은 작동하지 않습니다. 왜 그런지 아이디어를 얻었습니까?

모든 도움이 정말 감사하겠습니다!

도움이 되었습니까?

해결책

상호 배제는 다음과 같은 예를 들어 보장되지 않습니다.

우리는 다음과 같은 상황으로 시작합니다.

blocked = {false, false};
turn = 0;

P1은 이제 실행되고 건너 뜁니다

  blocked[id] = false; // Not yet executed.

상황은 이제 다음과 같습니다.

blocked {false, true}
turn = 0;

이제 P0이 실행됩니다. 중요한 섹션을 실행할 준비가 된 두 번째 While 루프를 통과합니다. 그리고 P1이 실행되면 1으로 전환하고 중요한 섹션을 실행할 준비가되었습니다.

BTW,이 방법은 원래 Hyman에 의해 발명되었습니다. 그는 1966 년 ACM의 커뮤니케이션으로 보냈습니다.

다른 팁

상호 배제는 다음과 같은 예를 들어 보장되지 않습니다.

우리는 다음과 같은 상황으로 시작합니다.

turn= 1;
blocked = {false, false};

실행은 다음과 같이 실행됩니다.

P0: while (true) {
P0:   blocked[0] = true;
P0:   while (turn != 0) {
P0:     while (blocked[1]) {
P0:     }
P1: while (true) {
P1:   blocked[1] = true;
P1:   while (turn != 1) {
P1:   }
P1:   criticalSection(P1);
P0:     turn = 0;
P0:   while (turn != 0)
P0:   }
P0:   critcalSection(P0);

이 숙제입니까, 아니면 일부 임베디드 플랫폼입니까? pthreads 또는 win32 (관련) 동기화 프리미티브를 사용할 수없는 이유가 있습니까?

아마도 차단하고 변동성을 선언해야 할 수도 있지만 프로그래밍 언어를 지정하지 않으면 알 수있는 방법이 없습니다.

특히 다중 프로세서 (또는 멀티 코어) 환경에서 동시성을 구현할 수 없습니다. 다른 코어/프로세서마다 캐시가 다릅니다. 이러한 캐시는 일관성이 아닐 수 있습니다. 아래의 의사 코드는 표시된 순서대로 실행될 수 있으며 결과가 표시됩니다.

get blocked[0] -> false   // cpu 0
set blocked[0] = true     // cpu 1 (stored in CPU 1's L1 cache)
get blocked[0] -> false   // cpu 0 (retrieved from CPU 0's L1 cache)
get glocked[0] -> false   // cpu 2 (retrieved from main memory)

너 필요 동시성을 구현하기위한 하드웨어 지식.

컴파일러는 루프와 함께 "빈"을 최적화했을 수 있습니다. 변수를 휘발성으로 선언하면 도움이 될 수 있지만 멀티 프로세서 시스템에서는 충분하지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top