모니터(동기화)

Monitor (synchronization)

동시 프로그래밍에서 모니터는 스레드가 상호 제외와 특정 조건이 거짓이 될 때까지 기다리는(차단) 기능을 모두 가질 수 있도록 하는 동기화 구성입니다.모니터에는 다른 스레드에 조건이 충족되었음을 알리는 메커니즘도 있습니다.모니터는 뮤텍스(잠금) 개체와 조건 변수로 구성됩니다.조건 변수는 기본적으로 특정 조건을 기다리는 스레드의 컨테이너입니다.모니터는 스레드가 특정 조건이 충족될 때까지 대기하기 위해 일시적으로 배타적 접근을 포기하고 작업을 재개하는 메커니즘을 제공합니다.

모니터의 또 다른 정의는 여러 스레드에서 메서드 또는 변수에 안전하게 액세스할 수 있도록 뮤텍스를 감싸는 스레드 세이프 클래스, 객체 또는 모듈입니다.모니터의 정의적인 특징은 그 방법이 상호 배타적으로 실행된다는 것입니다.각 시점에서 최대 1개의 스레드가 메서드 중 하나를 실행할 수 있습니다.또한 하나 이상의 조건 변수를 사용함으로써 스레드가 특정 조건에서 대기하는 기능을 제공할 수 있습니다(따라서 위의 "모니터" 정의를 사용).이 문서의 나머지 부분에서는 이러한 '모니터'의 의미를 '스레드 세이프 오브젝트/클래스/모듈'이라고 부릅니다.

모니터는 Per Brinch[1] Hansen과 C에 의해 발명되었다. A. R. Hoare는 [2]브린치 한센의 동시 파스칼 [3]언어로 처음 구현되었습니다.

상호 배타

간단한 예로 은행 계좌에서 트랜잭션을 수행하기 위한 스레드 세이프 개체를 생각해 보십시오.

모니터 클래스 계정 다른{균형= 균형-양 복귀 진정한}}public메서드 출발{민간int 균형= 0고정 균형>=0public메서드 부울 withdraw(int양)전제 조건 금액>=0{만약 균형 <, 양{반환 거짓}.osit(int금액) 전제조건 금액 > = 0 {잔액 : = 잔액 + 금액 } }

스레드가 스레드 세이프 오브젝트의 메서드를 실행하는 동안 뮤텍스(잠금)를 유지함으로써 오브젝트를 점유한다고 합니다.스레드 세이프 오브젝트는 각 시점에서 최대 1개의 스레드가 오브젝트를 점유할 수 있도록 하기 위해 구현됩니다.이 잠금은 처음에 잠금 해제되어 각 공개 메서드의 시작 시에 잠기고 각 공개 메서드에서 반환될 때마다 잠금이 해제됩니다.

메서드 중 하나를 호출할 때 스레드는 메서드 실행을 시작하기 전에 스레드 세이프 개체의 메서드를 실행하는 다른 스레드가 없을 때까지 기다려야 합니다.이 예에서는 이러한 상호 배제를 하지 않으면 두 개의 스레드로 인해 이유 없이 돈이 손실되거나 획득될 수 있습니다.예를 들어 계정에서 1000을 인출하는2개의 스레드 모두 true를 반환하고 잔액은 1000만 떨어집니다.첫 번째로 두 스레드 모두 현재 잔액을 가져오고 1000보다 큰 값을 찾아내고 그 값에서 1000을 뺀 다음 두 스레드 모두 잔액을 저장하고 반환할 수 있습니다.

위의 예에서 구문설탕 "모니터 클래스"는 각 함수의 실행을 뮤텍스로 포장함으로써 다음과 같은 코드 기본 표현을 구현하고 있습니다.

등급 계정 다른{균형= 균형{개인 자물쇠 myLock 민간int 균형= 0고정 균형>=0public메서드 부울 withdraw(int양)전제 조건 금액>만약 균형 <=0{myLock.acquire(){노력하세요;양{반환 거짓}. -양true }을(를) 반환한다. 마침내 {myLock.release() } 공개 메서드 보증금(int 금액) 전제 조건 금액 >= 0 {myLock.acquire() try { balance : = balance + } 마침내 {myLock.release() } } } } }

조건 변수

문제문

많은 어플리케이션에서 상호 배제는 충분하지 않습니다.작업을 시도하는 스레드는 특정 상태가 될 때까지 기다려야 할 수 있습니다.P맞는 말이다.비지 대기 루프

 휘날리다P ) 스킵

는 동작하지 않습니다.상호 제외로 인해 다른 스레드가 모니터에 들어가지 않고 상태가 실현되기 때문입니다.모니터의 잠금을 해제하고 일정 시간 대기하며 모니터를 잠그고 상태를 체크하는 루프가 있는 등 기타 '솔루션'이 존재합니다.P. 이론적으로는 작동하며 교착 상태가 되지 않지만 문제가 발생합니다.적절한 대기시간을 결정하는 것은 어렵습니다.너무 작아서 스레드가 CPU를 너무 많이 차지하기 때문에 응답이 없는 것이 분명합니다.필요한 것은 조건 P가 true(또는 true)일 때 스레드에 신호를 보내는 방법입니다.

도입 사례: 전형적인 생산자/소비자 문제

일반적인 동시성 문제는 한정된 생산자/소비자의 문제로, 최대 크기의 작업 큐 또는 링 버퍼가 존재하며, 1개 이상의 스레드는 큐에 작업을 추가하는 "프로덕터" 스레드이며, 다른 1개 이상의 스레드는 큐에서 작업을 꺼내는 "소비자" 스레드입니다.큐 자체는 스레드세이프 이외의 것으로 간주되며 빈 큐, 가득 큐 또는 빈 큐와 가득 큐 사이입니다.큐에 태스크가 가득 차면 컨슈머 스레드 디큐잉 태스크에서 벗어날 수 있을 때까지 프로듀서 스레드를 차단해야 합니다.한편, 큐가 비어 있을 때는 생산자 스레드가 추가되어 더 많은 작업을 사용할 수 있을 때까지 컨슈머 스레드를 차단해야 합니다.

큐는 스레드 간에 공유되는 동시 객체이므로 큐에 대한 액세스는 아토믹하게 해야 합니다.이는 큐액세스가 큐액세스 중에 일관성이 없는 상태가 될 수 있기 때문입니다.따라서 큐에 액세스하는 모든 코드는 상호 제외에 의해 동기화되어야 하는 중요한 섹션을 구성합니다.큐에 액세스하는 코드의 중요한 섹션의 코드와 프로세서 명령이 같은 프로세서 상의 스레드 간에 임의의 컨텍스트스위치를 사용하거나 여러 프로세서에서 스레드를 동시에 실행하여 인터리브할 수 있는 경우 부정합 상태가 노출되어 레이스 상태가 발생할 위험이 있습니다.

동기화하지 않으면 잘못됨

순진한 어프로치는 비지웨이팅과 동기화가 없는 코드를 설계하여 코드를 레이스 조건의 대상이 되도록 하는 것입니다.

세계적인 링 버퍼 큐잉; // 스레드 안전하지 않은 링 버퍼 태스크입니다.  // 각 생산자 스레드의 동작을 나타내는 메서드: 일반의 방법 제작자() {     하는 동안에 (진실의) {         작업 마이태스크 = ...; // 프로듀서가 추가할 새 작업을 만듭니다.         하는 동안에 (큐잉.꽉 찼다()) {} // 비지 큐가 가득 찰 때까지 대기합니다.         큐잉.큐잉(마이태스크); // 작업을 큐에 추가합니다.     } }  // 각 소비자 스레드의 동작을 나타내는 메서드: 일반의 방법 소비자() {     하는 동안에 (진실의) {         하는 동안에 (큐잉.비어 있다()) {} // 비지 큐가 비어 있지 않을 때까지 기다립니다.         마이태스크 = 큐잉.큐잉을 해제하다(); // 큐에서 작업을 제거합니다.         doStuff(마이태스크); // 작업을 중지하고 작업을 수행합니다.     } }

이 코드는 큐에 대한 액세스가 중단되고 큐에 대한 다른 스레드의 액세스와 인터리브될 수 있다는 점에서 심각한 문제가 있습니다.queue.enqueue 및 queue.dequeue 메서드에는 큐의 멤버 변수(크기, 시작 및 종료 위치, 큐 요소의 할당 및 할당 등)를 갱신하는 명령이 포함되어 있습니다.또한 queue.is Empty() 및 queue.isFull() 메서드도 이 공유 상태를 읽습니다.enqueue/dequeue 콜 중에 생산자/소비자 스레드를 인터리빙할 수 있는 경우 큐의 일관되지 않은 상태가 노출되어 레이스 상태가 발생할 수 있습니다.또한 다른 사용자가 비지 대기 중 종료 후 "dequeue" 호출 사이에 큐를 비워두면 두 번째 사용자가 빈 큐에서 큐 해제를 시도하여 오류가 발생합니다.마찬가지로 다른 생산자가 비지 대기 중 종료 후 "enqueue" 호출 사이에 큐를 가득 채우면 두 번째 생산자가 큐에 추가하려고 시도하여 오류가 발생합니다.

스핀 대기

앞서 언급한 바와 같이 동기화를 달성하기 위한 간단한 접근법 중 하나는 "spin-waiting"을 사용하는 것입니다.이 방법에서는 코드의 중요한 부분을 보호하기 위해 뮤텍스를 사용하고 비지-대기 체크 사이에 잠금이 취득되어 해제됩니다. 

세계적인 링 버퍼 큐잉; // 스레드 안전하지 않은 링 버퍼 태스크입니다. 세계적인 잠그다 queueLock; // 태스크의 링 버퍼용 뮤텍스.  // 각 생산자 스레드의 동작을 나타내는 메서드: 일반의 방법 제작자() {     하는 동안에 (진실의) {         작업 마이태스크 = ...; // 프로듀서가 추가할 새 작업을 만듭니다.          queueLock.얻다(); // 초기 비지 대기 체크를 위한 잠금을 획득합니다.         하는 동안에 (큐잉.꽉 찼다()) { // 비지 큐가 가득 찰 때까지 대기합니다.             queueLock.풀어주다();             // 다른 스레드를 사용할 수 있도록 잠금을 일시적으로 해제합니다.             // 소비자가 작업을 수행할 수 있도록 queueLock을 실행해야 합니다.             queueLock.얻다(); // "queue.isFull()" 에 대한 다음 콜의 잠금을 다시 취득합니다.         }          큐잉.큐잉(마이태스크); // 작업을 큐에 추가합니다.         queueLock.풀어주다(); // 다음 작업을 추가하기 위해 다시 필요할 때까지 큐 잠금을 해제합니다.     } }  // 각 소비자 스레드의 동작을 나타내는 메서드: 일반의 방법 소비자() {     하는 동안에 (진실의) {         queueLock.얻다(); // 초기 비지 대기 체크를 위한 잠금을 획득합니다.         하는 동안에 (큐잉.비어 있다()) { // 비지 큐가 비어 있지 않을 때까지 기다립니다.             queueLock.풀어주다();             // 다른 스레드를 사용할 수 있도록 잠금을 일시적으로 해제합니다.             // 프로듀서가 작업을 추가할 수 있도록 queueLock을 실행해야 합니다.             queueLock.얻다(); // "queue.is Empty()" 에 대한 다음 콜의 잠금을 다시 취득합니다.         }         마이태스크 = 큐잉.큐잉을 해제하다(); // 큐에서 작업을 제거합니다.         queueLock.풀어주다(); // 다음 작업을 취소하기 위해 다시 필요할 때까지 큐 잠금을 해제합니다.         doStuff(마이태스크); // 작업을 중지하고 작업을 수행합니다.     } }

이 방법을 사용하면 불일치 상태가 발생하지 않지만 불필요한 비지 대기 때문에 CPU 리소스가 낭비됩니다.큐가 비어 있고 프로듀서 스레드가 오랫동안 추가할 것이 없는 경우에도 컨슈머 스레드는 항상 불필요하게 대기하고 있습니다.마찬가지로 소비자는 현재 작업 처리에 오랜 시간 차단되어 큐가 꽉 차도 생산자는 항상 바삐 대기하고 있습니다.이것은 낭비적인 메커니즘입니다.필요한 것은 큐가 가득 찰 때까지 프로듀서 스레드를 차단하는 방법과 큐가 비어 있지 않을 때까지 컨슈머 스레드를 차단하는 방법입니다.

(N.B.: 뮤텍스 자체는 잠금을 얻기 위해 비지웨이팅이 수반되는 스핀록이 될 수도 있지만 CPU 자원의 낭비 문제를 해결하기 위해 queueLock은 스핀록이 아니며 블로킹록 큐 자체를 적절하게 사용하고 있다고 가정합니다).

조건 변수

해결책은 조건 변수를 사용하는 것입니다.개념적으로 조건 변수는 뮤텍스와 관련된 스레드의 큐로, 스레드는 어떤 조건이 참이 될 때까지 대기할 수 있습니다.따라서 각 조건 변수 c는 어설션c P와 관련지어집니다.스레드가 조건 변수에서 대기하고 있는 동안에는 해당 스레드가 모니터를 점유하는 것으로 간주되지 않으므로 다른 스레드가 모니터에 들어가 모니터 상태를 변경할 수 있습니다.대부분의 모니터 유형에서 이들 다른 스레드는 조건 변수 c에 신호를 보내 현재 상태에서 어설션c P가 참임을 나타낼 수 있습니다.

따라서 조건 변수에 대한 세 가지 주요 연산이 있습니다.

  • wait c, m,어디에c조건 변수입니다.m는 모니터와 관련된 뮤텍스(잠금)입니다.이 작업은 계속하기 전에 어설션c P가 참일 때까지 기다려야 하는 스레드에 의해 호출됩니다.스레드가 대기하고 있는 동안에는 모니터를 점유하지 않습니다."대기" 작업의 기능과 기본 계약은 다음 단계를 수행하는 것입니다.
    1. 아토믹:
      1. 뮤텍스를 방출하다m,
      2. 이 스레드를 '실행'에서 '실행'으로 옮기다c스레드의 "wait-time"(일명 "sleep-time"(sleep-time)) 및
      3. sleep this thread. (콘텍스트는 다른 스레드로 동기화됩니다.)
    2. 이 스레드가 그 후에 통지/시그널링되었다가 재개되면(아래 참조), 자동으로 뮤텍스를 다시 취득합니다.m.
    스텝 1a와 1b는 어느 순서로도 실행할 수 있습니다.보통은 그 후에 1c가 발생합니다.실이 잠들어 있는 동안c의 wait-display, 다음 실행 프로그램카운터는 "wait" 함수/서브루틴 중간에 있는 스텝2에 있습니다.따라서 스레드는 sleep 상태이고 나중에 "wait" 작업 도중 웨이크업됩니다.
    스텝 1 내의 동작의 원자성은 그 사이에 프리엠프티브스레드 스위치로 인해 발생하는 레이스 조건을 피하기 위해 중요합니다.Atomic이 아닌 경우 발생할 수 있는 장애 모드는 스레드가 켜져 있을 수 있는 웨이크업 누락입니다.c는 sleep-disable로 mutex를 해제했습니다만, 스레드가 sleep 상태가 되기 전에 프리엠프티브스레드 스위치가 발생하고, 다른 스레드도 signal operation(아래 참조)이라고 불립니다.c첫 번째 실을 밖으로 되돌리는 것c의 큐입니다.문제의 첫 번째 스레드가 다시 전환되는 즉시 해당 프로그램 카운터는 스텝 1c가 되며, sleep 상태가 되어 다시 sleep 상태가 될 수 없으며, 이는 켜져 있어야 하는 불변성을 위반합니다.c잘 때 잠든 것 같아요다른 레이스 조건은 스텝 1a와 1b의 순서에 따라 달라지며 컨텍스트스위치가 발생하는 위치에 따라 달라집니다.
  • signal c, 일명notify c는 스레드에 의해 호출되어 어설션P가c 참임을 나타냅니다.모니터의 종류와 실장에 따라 1개 또는 여러 스레드가 이동합니다.c는 "ready queue" 또는 실행하는 다른 큐에 sleep-passing 합니다.일반적으로 뮤텍스를 해제하기 전에 "신호" 작업을 수행하는 것이 좋습니다.m관련지어져 있다c단, 코드가 적절히 동시성을 위해 설계되어 있고 스레드 구현에 따라서는 시그널링 전에 잠금을 해제하는 것도 허용됩니다.스레드 실장에 따라서는, 이 순서는 스케줄링 우선순위에 영향을 줄 수 있습니다(일부[who?] 작성자는 시그널링 전에 잠금을 해제하는 것을 선호합니다).스레드화 실장은 이 주문에 관한 특별한 제약사항을 문서화해야 합니다.
  • broadcast c, 일명notifyAll c는 c의 대기시간 내의 모든 스레드를 웨이크업하는 것과 같은 조작입니다.그러면 대기열이 비워집니다.일반적으로 복수의 술어 조건이 같은 조건 변수에 관련지어져 있는 경우 잘못된 조건을 기다리는 스레드가 웨이크업된 후 막 true가 된 올바른 조건을 기다리는 스레드를 웨이크업하지 않고 바로 sleeve로 돌아갈 수 있기 때문에 어플리케이션은 신호 대신 브로드캐스트를 요구합니다.그렇지 않으면 술어 조건이 조건 변수와 1 대 1일 경우 신호가 브로드캐스트보다 효율적일 수 있습니다.

설계 규칙으로서 여러 조건 변수를 동일한 뮤텍스와 연결할 수 있지만, 그 반대도 아닙니다(이것은 일대다 대응 관계입니다).이는 P라는c 용어가 모니터를 사용하는 모든 스레드에 대해 동일하기 때문에 조건이 변경되거나 해당 스레드로 인해 변경되는 동안 읽을 수 있는 다른 모든 스레드로부터 상호 배제를 통해 보호되어야 하지만 다른 스레드가 있을 수 있습니다.동일한 변수를 사용하려면 동일한 뮤텍스를 사용해야 합니다.위의 producer-consumer 예제에서는 큐는 하나의 뮤텍스 객체에 의해 보호되어야 합니다.m. "프로덕터" 스레드는 잠금을 사용하여 모니터에서 대기합니다.m및 큐가 가득 찰 때까지 차단하는 c {\full}.'컨슈머' 스레드는 같은 뮤텍스를 사용하여 다른 모니터에서 대기합니다.m단, 큐가 비워지지 않을 때까지 차단하는 다른 조건 e p y { 입니다.같은 조건 변수에 대해 서로 다른 뮤텍스를 갖는 것은 결코 의미가 없지만, 이 고전적인 예에서는 같은 뮤텍스를 사용하여 여러 조건 변수를 갖는 것이 확실히 의미가 있는 이유를 보여 줍니다.하나 이상의 조건 변수(하나 이상의 모니터)에 의해 사용되는 뮤텍스는 조건 변수를 사용하지 않는 코드(및 대기/신호 조작 없이 단순히 취득/해제하는 것)와 공유할 수도 있습니다.단, 이러한 중요한 섹션이 동시 데이터에 대해 특정 조건을 기다릴 필요가 없는 경우입니다.

사용 상황 감시

모니터의 적절한 기본적인 사용법은 다음과 같습니다.

얻다(m); // 이 모니터의 잠금을 획득합니다. 하는 동안에 (!p) { // 기다리는 조건/사전 증명/주장이 사실이 아닌 경우...  잠깐만요.(m, 이력서); // 이 모니터의 잠금 및 조건 변수를 기다립니다. } //... 코드의 중요한 섹션이 여기에 들어갑니다... 신호.(cv2); // 또는: 브로드캐스트(cv2);              // cv2는 cv와 같거나 다를 수 있습니다. 풀어주다(m); // 이 모니터의 잠금을 해제합니다.

보다 정확하게 말하면, 이것은 같은 의사 코드입니다만, 보다 상세한 코멘트를 붙여, 상황을 보다 정확하게 설명합니다.

// ... (이전 코드) // 모니터에 들어가려고 합니다. // 동시와 관련된 어드바이저리 뮤텍스(잠금)를 취득합니다. // 스레드 간에 공유되는 데이터, // 2개의 스레드를 사전에 인터리브하거나 // 크리티컬한 상황에서 다른 코어에서 동시에 실행 // 동일한 동시 데이터를 읽거나 쓰는 섹션.다른 경우 // 스레드가 이 뮤텍스를 보유하고 있으면 이 스레드가 sleeve 상태가 됩니다. // (슬립) 및 m의 sleep 큐에 배치됩니다.(뮤텍스 "m"은 다음과 같을 수 없다. // 스핀 잠금). 얻다(m); // 이제 잠금 장치를 잡고 있습니다. //처음입니다.  // 위 이후 while loop 조건을 처음 실행하는 경우 // "취득" "조건/사전 증명/주장" // 우리가 기다리고 있는 것은 이미 사실입니까?"  하는 동안에 (!p())  // "p"는 임의의 식입니다(예: 변수 또는   // function-call) 상태를 체크하고   // 부울로 평가됩니다.이 자체는 매우 중요합니다.   // 섹션, 따라서 *Must*는 잠금을 유지하고 있어야 합니다.   // 이 "while" 루프 조건을 실행합니다.      // "while" 상태가 처음 체크되는 것이 아니라면 // 그러면 다음과 같은 질문을 합니다. "이제 다른 스레드가 이것을 사용하고 있습니다. // 모니터에서 알림과 깨움, 컨텍스트 전환 완료 // 현재 대기하고 있는 상태/증명서/증명서/증명서/증명서가 있습니까? // 깨어났을 때부터 다시 얻은 시간까지 true입니다. // 이 루프의 마지막 반복 시 "wait" 콜 내부의 잠금 또는 // 다른 스레드로 인해 이 상태가 다시 false가 되었습니까? // 그 사이에 가짜 깨우기가 되는 건가요?  {  // 이것이 루프의 첫 번째 반복일 경우 답은 다음과 같습니다.  // "no" -- 조건이 아직 준비되지 않았습니다.그렇지 않으면 답은 다음과 같습니다.  // 후자.이것은 스플리어스 웨이크업으로, 다른 스레드가 발생했습니다.  // 먼저 상태가 다시 false가 되도록 합니다.  // 다시 기다립니다.   잠깐만요.(m, 이력서);   // 코어상의 다른 스레드가 일시적으로 동작하지 않도록 합니다.   // m 또는 cv에 대한 연산.   // release(m) // 잠금 "m"을 자동으로 해제하여 기타   // 이 동시 데이터를 사용하여 코드화   // // 작동 가능, 이 스레드를 CV로 이동   // // 알림이 전송되도록 대기 중   // // 상태가 되었을 때   // true, 이 스레드를 sleeve 합니다.재활성화   // // 기타 스레드 및 코어 작업   // // m 및 cv에 대한 연산   //   // 이 코어로 컨텍스트스위치가 발생합니다.   //   //앞으로 우리가 기다리는 조건은   // true 및 이 모니터(m, cv)를 사용하는 다른 스레드는 다음 중 하나를 수행합니다.   // 이 스레드를 웨이크업할 때 발생하는 신호 또는   // 우리를 깨우는 브로드캐스트, 즉 우리가 제거되었다는 의미   // cv의 대기 시간.   //   // 이 시간 동안 다른 스레드로 인해 이 상태가 발생할 수 있습니다.   // 다시 false가 되거나 조건이 하나 또는 여러 개 전환될 수 있습니다.   // 횟수, 그렇지 않으면 그대로 유지될 수 있습니다.   //   // 이 스레드는 일부 코어로 다시 전환되었습니다.   //   // acquire(m) // 잠금 "m"을 다시 획득합니다.     // 이 루프 반복을 종료하고 "while" 루프 조건을 다시 확인하여  // 술어가 여전히 참임을 확인합니다.   }  // 기다리고 있는 조건이 참입니다! // 모니터에 들어가기 전 또는 모니터에서 // "wait"의 마지막 실행.  // 코드의 중요한 섹션이 여기에 들어갑니다.이것은 우리의 술어가 // true여야 합니다. // 이 코드는 cv의 조건을 false로 만들거나 다른 조건 변수를 만들 수 있습니다. // 는 true 입니다.  // 어떤 조건 변수에 따라 호출 신호 또는 브로드캐스트' // (mutex m을 공유하는) 술어가 참이 되었거나 참이 되었을 수 있습니다. // 및 사용되는 모니터시멘틱 타입.  위해서 (cv_x 에 cvs_to_module) {  신호.(cv_x); // 또는: broadcast(cv_x); } // 하나 이상의 스레드가 웨이크업되었지만 시도하는 즉시 차단됩니다. // m을 획득합니다.  // 통지된 스레드 등이 critical을 입력할 수 있도록 뮤텍스를 해제합니다. // 섹션. 풀어주다(m);

한정된 생산자/소비자 문제 해결

조건 변수의 사용을 소개했으므로, 이를 사용하여 기존의 한정 생산자/소비자 문제를 다시 살펴보고 해결합시다.일반적인 솔루션은 2개의 모니터를 사용하는 것입니다.이 모니터는 큐에 대해 1개의 잠금을 공유하는2개의 조건변수로 구성됩니다.

세계적인 휘발성의 링 버퍼 큐잉; // 스레드 안전하지 않은 링 버퍼 태스크입니다. 세계적인 잠그다 queueLock; // 태스크의 링 버퍼용 뮤텍스입니다(스핀 잠금이 아닙니다). 세계적인 이력서 queue Empty(비어 있음)이력서; // 큐 대기 중인 소비자 스레드의 조건 변수             // 공백이 아닙니다.관련된 잠금은 "queueLock"입니다. 세계적인 이력서 큐풀CV; // 큐 대기 중인 프로듀서 스레드의 조건 변수            // 가득 차지 않게 됩니다.관련된 잠금도 "queueLock"입니다.  // 각 생산자 스레드의 동작을 나타내는 메서드: 일반의 방법 제작자() {     하는 동안에 (진실의) {         // 프로듀서가 추가할 새 작업을 만듭니다.         작업 마이태스크 = ...;          // 초기 술어 체크를 위해 "queueLock"을 획득합니다.         queueLock.얻다();          // 큐가 꽉 찼는지 여부를 확인하는 중요한 섹션입니다.         하는 동안에 (큐잉.꽉 찼다()) {             // "queueLock"을 해제하고 이 스레드를 "queueFullCV"에 큐잉한 후 이 스레드를 sleeve 상태로 만듭니다.             잠깐만요.(queueLock, 큐풀CV);             // 이 스레드가 깨면 다음 술어 검사를 위해 "queueLock"을 다시 가져옵니다.         }          // 작업을 큐에 추가하는 중요한 섹션입니다('queueLock'을 보유하고 있습니다).         큐잉.큐잉(마이태스크);          // 대기 중인 하나 또는 모든 소비자 스레드가 비어 있지 않을 때까지 웨이크업합니다.         // 소비자 스레드가 작업을 수행할 수 있도록 보장되었습니다.         신호.(queue Empty(비어 있음)이력서); // 또는: broadcast(queue Empty)CV);         // 중요 섹션의 끝.          // 다음 작업을 추가하기 위해 다시 필요할 때까지 "queueLock"을 해제합니다.         queueLock.풀어주다();     } }  // 각 소비자 스레드의 동작을 나타내는 메서드: 일반의 방법 소비자() {     하는 동안에 (진실의) {         // 초기 술어 체크를 위해 "queueLock"을 획득합니다.         queueLock.얻다();          // 큐가 비어 있지 않은지 확인하는 중요한 섹션입니다.         하는 동안에 (큐잉.비어 있다()) {             // "queueLock"을 해제하고 이 스레드를 "queueEmptyCV"에 큐잉한 후 이 스레드를 sleeve 상태로 만듭니다.             잠깐만요.(queueLock, queue Empty(비어 있음)이력서);             // 이 스레드가 깨면 다음 술어 검사를 위해 "queueLock"을 다시 가져옵니다.         }          // 큐에서 작업을 제거하는 중요한 섹션입니다('queueLock'을 보유하고 있습니다).         마이태스크 = 큐잉.큐잉을 해제하다();          // 큐가 꽉 차기를 기다리는 하나 또는 모든 프로듀서 스레드를 웨이크업합니다.         // 이제 그것이 보증되므로 생산자 스레드가 작업을 추가합니다.         신호.(큐풀CV); // 또는: broadcast(queueFullCV);         // 중요 섹션의 끝.          // 다음 작업을 수행하기 위해 다시 필요할 때까지 "queueLock"을 해제합니다.         queueLock.풀어주다();          // 작업을 중지하고 작업을 수행합니다.         doStuff(마이태스크);     } }

이렇게 하면 작업 큐를 공유하는 생산자와 소비자 스레드 간의 동시성이 보장되며, 스핀 잠금을 사용하여 전술한 접근법에 나타나 있듯이 비지 대기하는 것보다 아무 관련이 없는 스레드를 차단할 수 있습니다.

이 솔루션의 변형은 생산자와 소비자 모두에 대해 단일 조건 변수인 "queueFullOrEmptyCV" 또는 "queueSizeChangedCV"를 사용할 수 있습니다.이 경우 조건 변수가 개별 스레드에 의해 체크되는 조건보다 약한 조건을 나타내도록 조건 변수에 여러 조건이 관련되어 있습니다.condition 변수는 큐가 가득 차기를 기다리는 스레드와 비어 있지 않을 때까지 기다리는 스레드를 나타냅니다.단, 이를 수행하려면 조건 변수를 사용하여 모든 스레드에서 브로드캐스트를 사용해야 하며 일반 신호를 사용할 수 없습니다.이는 일반 신호가 아직 조건이 충족되지 않은 잘못된 유형의 스레드를 웨이크업하고 올바른 유형의 스레드가 시그널링되지 않으면 스레드가 sleep 상태로 돌아갈 수 있기 때문입니다.예를 들어, 생산자가 대기열을 가득 채우고 소비자 대신 다른 생산자를 깨우면, 잠에서 깬 생산자는 다시 잠들게 된다.보완적인 경우, 소비자는 대기열을 비우고 생산자가 아닌 다른 소비자를 깨울 수 있으며 소비자는 다시 수면 상태로 돌아갈 수 있다.브로드캐스트를 사용하면 올바른 유형의 스레드 중 일부가 문제 설명에서 예상한 대로 처리됩니다.

조건 변수와 브로드캐스트를 1개만 사용하는 바리안트를 다음에 나타냅니다.

세계적인 휘발성의 링 버퍼 큐잉; // 스레드 안전하지 않은 링 버퍼 태스크입니다. 세계적인 잠그다 queueLock; // 태스크의 링 버퍼용 뮤텍스입니다(스핀 잠금이 아닙니다). 세계적인 이력서 queueFullOrEmpty이력서; // 큐에 스레드가 준비되지 않은 경우의 단일 조건 변수                               // 즉, 큐가 가득 차지 않을 때까지 기다리는 프로듀서 스레드의 경우                               // 및 큐가 비어 있지 않을 때까지 대기하는 소비자 스레드입니다.                               // 연관된 잠금은 "queueLock"입니다.                               // 일반 "신호"는 다음과 관련되어 있으므로 안전하지 않습니다.                               // 복수의 술어 조건(조건).  // 각 생산자 스레드의 동작을 나타내는 메서드: 일반의 방법 제작자() {     하는 동안에 (진실의) {         // 프로듀서가 추가할 새 작업을 만듭니다.         작업 마이태스크 = ...;          // 초기 술어 체크를 위해 "queueLock"을 획득합니다.         queueLock.얻다();          // 큐가 꽉 찼는지 여부를 확인하는 중요한 섹션입니다.         하는 동안에 (큐잉.꽉 찼다()) {             // "queueLock"을 해제하고 이 스레드를 "queueFullOrEmptyCV"에 큐잉한 후 이 스레드를 sleep합니다.             잠깐만요.(queueLock, queueFullOrEmpty이력서);             // 이 스레드가 깨면 다음 술어 검사를 위해 "queueLock"을 다시 가져옵니다.         }          // 작업을 큐에 추가하는 중요한 섹션입니다('queueLock'을 보유하고 있습니다).         큐잉.큐잉(마이태스크);          // 대기 중인 모든 생산자 스레드와 소비자 스레드를 각각 웨이크업합니다.         // non-full 및 non-empty가 보증되므로 컨슈머 스레드가 작업을 수행할 수 있습니다.         브로드캐스트(queueFullOrEmpty이력서); // "signal"을 사용하지 마십시오(다른 생산자 스레드만 웨이크업될 수 있음).         // 중요 섹션의 끝.          // 다음 작업을 추가하기 위해 다시 필요할 때까지 "queueLock"을 해제합니다.         queueLock.풀어주다();     } }  // 각 소비자 스레드의 동작을 나타내는 메서드: 일반의 방법 소비자() {     하는 동안에 (진실의) {         // 초기 술어 체크를 위해 "queueLock"을 획득합니다.         queueLock.얻다();          // 큐가 비어 있지 않은지 확인하는 중요한 섹션입니다.         하는 동안에 (큐잉.비어 있다()) {             // "queueLock"을 해제하고 이 스레드를 "queueFullOrEmptyCV"에 큐잉한 후 이 스레드를 sleep합니다.             잠깐만요.(queueLock, queueFullOrEmpty이력서);             // 이 스레드가 깨면 다음 술어 검사를 위해 "queueLock"을 다시 가져옵니다.         }          // 큐에서 작업을 제거하는 중요한 섹션입니다('queueLock'을 보유하고 있습니다).         마이태스크 = 큐잉.큐잉을 해제하다();          // 대기 중인 모든 생산자 스레드와 소비자 스레드를 각각 웨이크업합니다.         // non-full 및 non-empty (전자가 보증되므로 작성자 스레드가 작업을 추가합니다.         브로드캐스트(queueFullOrEmpty이력서); // "signal"을 사용하지 마십시오(다른 소비자 스레드만 웨이크업될 수 있음).         // 중요 섹션의 끝.          // 다음 작업을 수행하기 위해 다시 필요할 때까지 "queueLock"을 해제합니다.         queueLock.풀어주다();          // 작업을 중지하고 작업을 수행합니다.         doStuff(마이태스크);     } }

동기화 프리미티브

뮤텍스 및 조건 변수를 구현하려면 원자성을 제공하는 하드웨어 지원에 의해 제공되는 일종의 동기화 프리미티브가 필요합니다.잠금 및 조건 변수는 이러한 동기화 프리미티브에 대한 상위 수준의 추상화입니다.유니프로세서에서는 인터럽트를 디세블로 하여 이노블로 하는 것은 잠금 및 조건 변수의 중요한 섹션 중에 컨텍스트스위치를 방지함으로써 모니터를 실장하는 방법입니다만, 멀티프로세서에서는 이것만으로는 불충분합니다.멀티프로세서에서는 명령어세트 아키텍처가 제공하는 내용에 따라 보통 메모리 상의 특별한 원자 읽기-수정-쓰기 명령어(test-and-set, compare-and-swap 등)가 사용됩니다.일반적으로 내부 잠금 상태 자체에 대한 스핀 잠금으로 미뤄야 하지만, 이 잠금은 매우 짧습니다.구현에 따라서는 원자적인 읽기-수정-쓰기 명령이 다른 코어의 액세스로부터 버스를 잠그거나 CPU에서의 명령 재순서를 방해할 수 있습니다.다음으로 테스트 앤 세트정책과 선착순 정책을 사용하여 스레딩 시스템의 일부와 뮤텍스 및 Mesa 스타일의 조건 변수의 의사 코드 구현 예를 나타냅니다.이는 스레드화 시스템의 작동 방식을 대부분 설명하지만 뮤텍스 및 조건 변수와 관련된 부분을 보여 줍니다.

테스트 앤 세트를 사용한 Mesa 모니터 구현 예시

// 스레드 시스템의 기본 부품: // "ThreadQueue"가 랜덤 액세스를 지원한다고 가정합니다. 일반의 휘발성의 스레드큐 ready 큐; // 준비 스레드의 스레드 비안전 큐.요소는 (스레드*)입니다. 일반의 휘발성의 세계적인 실* current Thread(쓰레드); // 이 변수가 코어 단위라고 가정합니다(다른 변수는 공유됩니다).  // 스레드 시스템 자체의 동기화된 상태에만 스핀 잠금을 구현합니다. // 이것은 동기화 프리미티브로 테스트 및 설정과 함께 사용됩니다. 일반의 휘발성의 세계적인 부울 스레드 시스템 비지 = 거짓의;  // Context-Switch Interrupt Service Route(ISR; 컨텍스트스위치 인터럽트 서비스 루틴): // 현재 CPU 코어에서 먼저 다른 스레드로 전환합니다. 일반의 방법 콘텍스트 스위치ISR() {     한다면 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {         돌아가다; // 지금은 컨텍스트를 전환할 수 없습니다.     }      // 콘텍스트스위치를 망가뜨리는 이 인터럽트가 재발하지 않도록 합니다.     systemCall_disable인터럽트();      // 현재 실행 중인 프로세스의 모든 레지스터를 가져옵니다.     // Program Counter (PC; 프로그램 카운터)의 경우, 다음 명령 위치가 필요합니다.     // 아래의 "유효한" 라벨.레지스터 값의 취득은 플랫폼에 따라 다르며 다음 작업이 필요할 수 있습니다.     // 현재 스택프레임 읽기, JMP/CALL 지시 등 (상세한 내용은 이 범위를 벗어납니다)     current Thread(쓰레드)->레지스터 = get All Registers(); // 레지스터를 "현재"에 저장합니다.스레드" 오브젝트.     current Thread(쓰레드)->레지스터.PC = 이력서; // 이 방법에서는 다음 PC를 아래의 "재개" 라벨로 설정합니다.      ready 큐.큐잉(current Thread(쓰레드)); // 나중에 실행할 수 있도록 이 스레드를 대기열에 다시 넣습니다.          실* 기타 스레드 = ready 큐.큐잉을 해제하다(); // Ready 큐에서 실행할 다음 스레드를 제거하고 가져옵니다.          current Thread(쓰레드) = 기타 스레드; // 다음 스레드에 사용할 수 있도록 글로벌 전류 스레드 포인터 값을 바꿉니다.      // 현재 레지스터에서 복원스레드/otherThread(다른 스레드의 저장된 PC로의 점프 포함)     // (아래의 "timeout"에서).다시 말씀드리지만, 이 작업의 자세한 내용은 이 범위를 벗어납니다.     restore 레지스터(기타 스레드.레지스터);      //*** "other Thread" (현재 "current")를 실행하고 있습니다.스레드!원래 스레드는 "sleep" 상태입니다.***      이력서: // 여기서 컨텍스트를 전환할 때 다른 contextSwitch() 콜이 PC를 설정해야 합니다.      // 다른 곳으로 돌아가기스레드가 끊어졌습니다.      스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.     systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다. }  // 스레드 슬립 방법: // 현재 CPU 코어에서는 동기 컨텍스트가 다른 스레드로 전환됩니다. // 준비 큐의 현재 스레드. // 이 메서드가 실행되도록 "스레딩 시스템 비지"를 유지하고 인터럽트를 비활성화해야 합니다. // contextSwitchISR()을 호출하는 스레드 스위칭타이머에 의해 중단되지 않습니다. // 이 메서드에서 돌아온 후에는 "threadingSystemBusy"를 삭제해야 합니다. 일반의 방법 스레드 슬립() {     // 현재 실행 중인 프로세스의 모든 레지스터를 가져옵니다.     // Program Counter (PC; 프로그램 카운터)의 경우, 다음 명령 위치가 필요합니다.     // 아래의 "유효한" 라벨.레지스터 값의 취득은 플랫폼에 따라 다르며 다음 작업이 필요할 수 있습니다.     // 현재 스택프레임 읽기, JMP/CALL 지시 등 (상세한 내용은 이 범위를 벗어납니다)     current Thread(쓰레드)->레지스터 = get All Registers(); // 레지스터를 "현재"에 저장합니다.스레드" 오브젝트.     current Thread(쓰레드)->레지스터.PC = 이력서; // 이 방법에서는 다음 PC를 아래의 "재개" 라벨로 설정합니다.      // contextSwitchISR()과 달리 전류는 배치하지 않습니다.readyQue에 스레드백합니다.     // 대신 이미 뮤텍스 또는 조건 변수의 큐에 배치되어 있습니다.          실* 기타 스레드 = ready 큐.큐잉을 해제하다(); // Ready 큐에서 실행할 다음 스레드를 제거하고 가져옵니다.          current Thread(쓰레드) = 기타 스레드; // 다음 스레드에 사용할 수 있도록 글로벌 전류 스레드 포인터 값을 바꿉니다.      // 현재 레지스터에서 복원스레드/otherThread(다른 스레드의 저장된 PC로의 점프 포함)     // (아래의 "timeout"에서).다시 말씀드리지만, 이 작업의 자세한 내용은 이 범위를 벗어납니다.     restore 레지스터(기타 스레드.레지스터);      //*** "other Thread" (현재 "current")를 실행하고 있습니다.스레드!원래 스레드는 "sleep" 상태입니다.***      이력서: // 여기서 컨텍스트를 전환할 때 다른 contextSwitch() 콜이 PC를 설정해야 합니다.      // 다른 곳으로 돌아가기스레드가 끊어졌습니다. }  일반의 방법 잠깐만요.(뮤텍스 m, 상태 변수 c) {     // 코어 상의 다른 스레드가 이 개체의 스레드에 액세스하는 동안 내부 스핀 잠금     // "hold" 및 "threadQueue" 또는 "readyQueue"입니다.     하는 동안에 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {}     // N.B.:"threading SystemBusy"가 True가 되었습니다.          // threadSleep()이 중단되지 않도록 이 코어의 인터럽트를 비활성화하기 위한 시스템 호출     // contextSwitchISR()을 호출하는 이 코어의 스레드 스위칭타이머     // threadSleeve() 외부에서 실행되어 이 스레드가 sleeve 상태가 되도록 합니다.     // 상태 확인 큐에 들어간 직후.     systemCall_disable인터럽트();       주장하다 m.열렸다.; // (구체적으로는 이 스레드가 해당 스레드를 보유하고 있어야 합니다.          m.풀어주다();     c.대기 스레드.큐잉(current Thread(쓰레드));          스레드 슬립();          // 스레드 슬립...스레드는 신호/브로드캐스트에서 웨이크업됩니다.          스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.     systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다.          // 메사 스타일:     // 여기서 컨텍스트스위치가 발생하여 클라이언트 호출자의 술어가 false가 될 수 있습니다.          m.얻다(); }  일반의 방법 신호.(상태 변수 c) {     // 코어 상의 다른 스레드가 이 개체의 스레드에 액세스하는 동안 내부 스핀 잠금     // "hold" 및 "threadQueue" 또는 "readyQueue"입니다.     하는 동안에 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {}     // N.B.:"threading SystemBusy"가 True가 되었습니다.          // threadSleep()이 중단되지 않도록 이 코어의 인터럽트를 비활성화하기 위한 시스템 호출     // contextSwitchISR()을 호출하는 이 코어의 스레드 스위칭타이머     // threadSleeve() 외부에서 실행되어 이 스레드가 sleeve 상태가 되도록 합니다.     // 상태 확인 큐에 들어간 직후.     systemCall_disable인터럽트();          한다면 (!c.대기 스레드.비어 있다()) {         웨이크업 스레드 = c.대기 스레드.큐잉을 해제하다();         ready 큐.큐잉(웨이크업 스레드);     }          스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.     systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다.          // 메사 스타일:     // 웨이크업된 스레드에는 priority가 부여되지 않습니다. }  일반의 방법 브로드캐스트(상태 변수 c) {     // 코어 상의 다른 스레드가 이 개체의 스레드에 액세스하는 동안 내부 스핀 잠금     // "hold" 및 "threadQueue" 또는 "readyQueue"입니다.     하는 동안에 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {}     // N.B.:"threading SystemBusy"가 True가 되었습니다.          // threadSleep()이 중단되지 않도록 이 코어의 인터럽트를 비활성화하기 위한 시스템 호출     // contextSwitchISR()을 호출하는 이 코어의 스레드 스위칭타이머     // threadSleeve() 외부에서 실행되어 이 스레드가 sleeve 상태가 되도록 합니다.     // 상태 확인 큐에 들어간 직후.     systemCall_disable인터럽트();          하는 동안에 (!c.대기 스레드.비어 있다()) {         웨이크업 스레드 = c.대기 스레드.큐잉을 해제하다();         ready 큐.큐잉(웨이크업 스레드);     }          스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.     systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다.          // 메사 스타일:     // 웨이크업된 스레드에는 우선순위가 부여되지 않습니다. }  학급 뮤텍스 {     보호되고 있다 휘발성의 부울 열렸다. = 거짓의;     사적인 휘발성의 스레드큐 막는스레드; // 차단된 스레드의 스레드 안전하지 않은 대기열입니다.요소는 (스레드*)입니다.          일반의 방법 얻다() {         // 코어 상의 다른 스레드가 이 개체의 스레드에 액세스하는 동안 내부 스핀 잠금         // "hold" 및 "threadQueue" 또는 "readyQueue"입니다.         하는 동안에 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {}         // N.B.:"threading SystemBusy"가 True가 되었습니다.                  // threadSleep()이 중단되지 않도록 이 코어의 인터럽트를 비활성화하기 위한 시스템 호출         // contextSwitchISR()을 호출하는 이 코어의 스레드 스위칭타이머         // threadSleeve() 외부에서 실행되어 이 스레드가 sleeve 상태가 되도록 합니다.         // 잠금 큐에 들어간 직후.         systemCall_disable인터럽트();          주장하다 !막는스레드.포함하다(current Thread(쓰레드));          한다면 (열렸다.) {             // "current"를 입력합니다.스레드"가 이 잠금 큐에 있기 때문에             // 이 잠금에서 "실행"으로 간주됩니다.             // "전류"에 주의합니다.스레드'는 여전히 threadSleep()에서 처리해야 합니다.             ready 큐.제거한다.(current Thread(쓰레드));             막는스레드.큐잉(current Thread(쓰레드));             스레드 슬립();                          // 이제 우리는 깨어났는데, 이는 "hold"가 거짓이 되었기 때문일 것입니다.             주장하다 !열렸다.;             주장하다 !막는스레드.포함하다(current Thread(쓰레드));         }                  열렸다. = 진실의;                  스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.         systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다.     }                      일반의 방법 풀어주다() {         // 코어 상의 다른 스레드가 이 개체의 스레드에 액세스하는 동안 내부 스핀 잠금         // "hold" 및 "threadQueue" 또는 "readyQueue"입니다.         하는 동안에 (testAndSet(테스트 & 세트(스레드 시스템 비지)) {}         // N.B.:"threading SystemBusy"가 True가 되었습니다.                  // 효율을 높이기 위해 이 코어의 인터럽트를 무효로 하는 시스템콜         systemCall_disable인터럽트();                  주장하다 열렸다.; // (잠금이 유지된 상태에서만 해제)          열렸다. = 거짓의;                  한다면 (!막는스레드.비어 있다()) {             실* 차단되지 않았다실 = 막는스레드.큐잉을 해제하다();             ready 큐.큐잉(차단되지 않았다실);         }                  스레드 시스템 비지 = 거짓의; // 원자 할당이어야 합니다.         systemCall_enable인터럽트(); // 이 코어로 프리엠프티브스위칭을 다시 켭니다.     } }  구조 상태 변수 {     휘발성의 스레드큐 대기 스레드; }

세마포

예를 들어 세마포를 구현하는 스레드 세이프 클래스를 생각해 보겠습니다.개인 정수를 증가(V) 및 감소(P)하는 방법이 있습니다.s단, 정수는 0 이하로 감소하지 마십시오. 따라서 감소하려는 스레드는 정수가 양수가 될 때까지 기다려야 합니다.조건 변수를 사용합니다.sIsPositive i e ( >) { P_}=(의 어설션을 나타냅니다.

모니터 클래스 Semaphore;0신호 sI public메서드 V(){s:=의+1를 설파하다. s을{개인을 natives:=0s고정>=0민간 실태sIsPositive 및 s을과 관련된;0*/ public메서드 P(){는 반면 0:sIsPositive다고 주장하는 s을 기다려야;0s:조향 개시=의-1}.sPositive} }

모든 동기화를 표시(스레드 세이프 클래스의 전제 조건을 삭제하고 뮤텍스를 표시): 

클래스 Semaphore{개인 휘발성을 natives:=0s고정>=0민간ConditionVariablesIsPositive 및 s을과 관련된;0*/ 민간 뮤텍스 myLock /* Lock"s"*/ public메서드 P()에{myLock.acquire()는 반면 0:초기 조향 순간 wait(myLock,sIsPositive)다고 주장하는 s>0s:=의-1myLoc.k.release( ) } 공용 메서드 V() {myLock.acquire() s := s + 1 assert s > 0 신호 sIsPositive myLock.release() }

세마포어를 사용하여 구현된 모니터

반대로 잠금 및 조건 변수는 세마포에서 파생될 수 있으므로 모니터와 세마포는 서로 축소할 수 있습니다.

여기에 제시된 구현은 올바르지 않습니다.broadcast()가 호출된 후 스레드가 wait()를 호출하면 broadcast()는 이미 대기하고 있는 스레드에 대해서만 세마포어를 늘리기 때문에 원래 스레드는 무기한 고정될 수 있습니다. 

일반의 방법 잠깐만요.(뮤텍스 m, 상태 변수 c) {     주장하다 m.열렸다.;      c.내부 뮤텍스.얻다();          c.numWaiters++;     m.풀어주다(); // 인접 회선 앞/뒤로 이동할 수 있습니다.     c.내부 뮤텍스.풀어주다();      // 여기서 다른 스레드가 신호를 보낼 수 있지만 다음 방법 때문에 괜찮습니다.     // 세마포 수만약 c.sem의 숫자가 1이 되면, 우리는 아무것도 없을 것이다.     // 대기 시간.     c.반.얻다(); // CV에서 차단합니다.     // 웨이크업     m.얻다(); // 뮤텍스를 다시 획득합니다. }  일반의 방법 신호.(상태 변수 c) {     c.내부 뮤텍스.얻다();     한다면 (c.numWaiters > 0) {         c.numWaiters--;         c.반.풀어주다(); // (c.internal Mutex에 의해 보호될 필요는 없습니다.)     }     c.내부 뮤텍스.풀어주다(); }  일반의 방법 브로드캐스트(상태 변수 c) {     c.내부 뮤텍스.얻다();     하는 동안에 (c.numWaiters > 0) {         c.numWaiters--;         c.반.풀어주다(); // (c.internal Mutex에 의해 보호될 필요는 없습니다.)     }     c.내부 뮤텍스.풀어주다(); }  학급 뮤텍스 {     보호되고 있다 부울 열렸다. = 거짓의; // 어설션의 경우에만 sem의 번호가 1을 넘지 않도록 합니다.     보호되고 있다 세마포 반 = 세마포(1); // 번호는 항상 최대 1이어야 합니다.                                           // <--> 1은 유지되지 않고 <--> 0은 유지되고 있습니다.      일반의 방법 얻다() {         반.얻다();         주장하다 !열렸다.;         열렸다. = 진실의;     }          일반의 방법 풀어주다() {         주장하다 열렸다.; // 반드시 1 이상의 sem을 획득하지 마십시오.그건 안 좋을 것 같아.         열렸다. = 거짓의;         반.풀어주다();     } }  학급 상태 변수 {     보호되고 있다 인트 numWaiters = 0; // sem 단위로 차단된 대기자 수를 대략적으로 추적합니다.                                 // (세마포의 내부 상태는 반드시 비공개입니다.)     보호되고 있다 세마포 반 = 세마포(0); // 대기 큐를 제공합니다.     보호되고 있다 뮤텍스 내부 뮤텍스; // (정말 또 다른 세마포어입니다."numWaiters" 보호) }

적어도 1개의 다른 스레드가 대기하고 있는 상태 변수에서 신호가 발생하면 적어도2개의 스레드가 모니터를 점유할 수 있습니다.신호를 보내는 스레드와 대기하고 있는 스레드 중 하나입니다.한 번에 최대 1개의 스레드가 모니터를 차지하도록 선택할 필요가 있습니다.이 선택을 가장 잘 해결할 수 있는 방법에 대해 두 가지 학파가 존재한다.그 결과, 다음의 2 종류의 조건 변수가 조사됩니다.

  • 블로킹 조건 변수는 시그널링된 스레드에 우선순위를 부여합니다.
  • 논블로킹 조건 변수는 시그널링 스레드에 우선순위를 부여합니다.

블럭화 조건 변수

C의 원래 제안서. A. R. Hoare와 Per Brinch Hansen은 조건 변수를 차단하기 위한 것이었다.블로킹 조건 변수를 사용하는 경우 시그널링 스레드는 적어도 시그널링 스레드가 조건 변수를 반환하거나 다시 대기함으로써 모니터 점유율을 포기할 때까지 모니터 밖에서 대기해야 합니다.차단 조건 변수를 사용하는 모니터는 종종 Hoare 스타일 모니터 또는 신호 및 긴급 대기 모니터라고 불립니다.

두 가지 조건 변수가 있는 Hoare 스타일 모니터a그리고.bBuhr et al 이후.

각 모니터 오브젝트에는 2개의 스레드 큐가 관련되어 있다고 가정합니다.

  • e입구 큐입니다.
  • s는 시그널링한 스레드의 큐입니다.

또한 각 조건 변수 c에 대해 큐가 있다고 가정합니다.

  • c.q조건 변수 c에서 대기하는 스레드 큐입니다.

일반적으로 모든 큐는 균등성이 보장되며 일부 구현에서는 선입선출이 보장될 수 있습니다.

각 조작의 실장은 다음과 같습니다.(각 조작은 다른 조작과 상호 배타적으로 실행된다고 가정합니다.따라서 재시작된 스레드는 조작이 완료될 때까지 실행을 시작하지 않습니다.) 

모니터로 들어갑니다.모니터가 잠겨 있는 경우 이 스레드를 입력합니다.이 스레드를 블록에 추가합니다.그렇지 않으면 모니터를 잠그십시오.스케줄 리턴을 메서드에서 c: 이 스레드를 c.q schedule에 추가합니다.c.q schedule 이 스레드 신호를 c.q se에 대기하고 있는 스레드가 c.q se에 대기하고 있는 경우 이 스레드 신호를 차단합니다.이러한 스레드 t를 c.q에서 1개 삭제하고(t는 "시그널링 스레드"라고 부릅니다), 이 스레드를 s재시작 t에 추가합니다(따라서 t가 다음에 모니터를 차지합니다).에 스레드가 있는 경우는, 에서 스레드를 1개 선택해 삭제해 재기동합니다(이 스레드는 모니터를 점유합니다).ext) 그렇지 않으면 e에 스레드가 있는 경우 e에서 스레드 하나를 선택하여 삭제한 후 재시작합니다(이 스레드가 다음에 모니터를 점유합니다). 그렇지 않으면 모니터의 잠금을 해제합니다(모니터가 점유되지 않습니다).

그scheduleroutine은 모니터를 점유할 다음 스레드를 선택하거나 후보 스레드가 없는 경우 모니터의 잠금을 해제합니다.

결과적으로 발생하는 시그널링 규율은 시그널러가 대기해야 하지만 입구 큐의 스레드보다 우선하기 때문에 "signal and ergent wait"라고 불립니다.다른 대안은 "신호 후 대기"입니다. 이 방법에는s큐와 시그널러가 대기하고 있다.e큐잉을 합니다.

실장에 따라서는 시그널링과 프로시저로부터의 리턴을 조합한 시그널링과 리턴 조작이 제공됩니다. 

signal c와 return: c.q에 스레드가 대기하고 있는 경우 이러한 스레드 중 하나를 선택하여 c.q에서 삭제(t는 "시그널드 스레드"라고 불립니다)를 재시작합니다(그렇지 않으면 t가 다음에 모니터를 점유합니다).그렇지 않으면 메서드에서 반환을 스케줄링합니다.

어떤 경우("signal and urgent wait") 또는 "signal and wait")든 조건 변수가 시그널링되고 조건 변수에 적어도1개의 스레드가 대기하고 있을 때 시그널링 스레드는 시그널링 스레드에 점유율을 심리스하게 인계하여 그 사이에 점유율을 얻을 수 없다.각c 신호 c 동작 시작 시 P가 참일 경우 각 대기 c 동작 종료 시 참이 됩니다.이는 다음과 같은 계약으로 요약된다.이 계약에서 나는 모니터의 불변자이다. 

모니터에 들어갑니다: postcondition I leave monitor: precondition I wait c: preconditionc P 및 I signal c: preconditionc P 및 I signal c: preconditionc P 및 I signal c: precondition P 및 I signal c: pronitor postcondition I sign c를 변경하여 반환한다.

이러한 계약에서는 I와c P는 큐의 내용 또는 길이에 의존하지 않는 것으로 간주됩니다.

(조건 변수를 큐에서 대기하는 스레드 수에 대해 쿼리할 수 있는 경우 보다 정교한 계약을 제공할 수 있습니다.예를 들어, 불변성을 설정하지 않고 점유율을 이전할 수 있는 유용한 계약 쌍은 다음과 같다.

wait c: precondition 모니터의 postconditionc P 신호 precondition(빈(c)과 P가 아님c) 또는 (empty(c)와 I)가 모니터의 postcondition I의 상태를 변경합니다.

(자세한 내용은 Howard 및 Buhr [5]등 참조[4]).

여기에서 어설션c P는 전적으로 프로그래머에게 달려있다는 것을 주목하는 것이 중요합니다. 프로그래머는 단지 그것이 무엇인지에 대해 일관성을 가질 필요가 있습니다.

이 섹션은 경계된 스레드 세이프 스택을 구현하는 블로킹모니터를 사용한 스레드 세이프 클래스의 예시로 마무리하겠습니다 

모니터 클래스 SharedStack{개인 const 용량:=10여개 현지 민간 int[용량]의 한 개인을 native크기:=0고정 0<>)크기와 크기<>= 능력 개인 BlockingConditiontheStackIsNotEmpty 및 0개체와 관련된, 크기, 크기를<>)용량 */ 민간 BlockingCondition theStackIsNotFull 및 0<>와 관련 컵의 크기 and 크기<>capacIty{만약 크기)용량 다음 theStackIsNotFull다고 주장하는 0<>)크기와 크기<>용량 A[크기] 기다리:=가치, 크기:)크기+1를 설파하다. 0<, 크기, 크기를<>= 용량 신호 및 반환theStackIsNotEmpty}public메서드int pop()push(int값){만약 크기=0public메서드 */. 그 번째 기다리eStackIsNotEmpty 아사트 0 < size and size < = capacity size : = size - 1 > 아사트 0 < = size > stackIsNotFull 및 return A [ size ] }

이 예에서는 스레드세이프 스택이 내부적으로 뮤텍스를 제공하고 있습니다.이 뮤텍스는 앞의 생산자/소비자 예시와 마찬가지로 동일한 동시 데이터상의 다른 조건을 체크하는 두 조건 변수에 의해 공유됩니다.유일한 차이점은 생산자/소비자 예가 일반 비스레드 세이프 큐를 가정하고 스탠드아론 뮤텍스 및 조건 변수를 사용했다는 것입니다.여기서와 같이 모니터의 상세 내용은 추상화되지 않았습니다.이 예에서는 "wait" 작업이 호출될 때 "wait" 작업이 "monitor class"에 통합된 부분인 경우 등 스레드 세이프 스택의 뮤텍스와 함께 제공해야 합니다.이러한 추상화된 기능 외에도 "raw" 모니터를 사용할 때는 항상 각 조건 변수에 고유한 뮤텍스와 조건 변수를 포함해야 합니다.

논블로킹 조건 변수

비블로킹 조건 변수('Mesa 스타일' 조건 변수 또는 '신호 및 계속' 조건 변수라고도 함)에서는 시그널링 스레드가 모니터 점유율을 잃지 않습니다.대신 시그널링된 스레드는e큐잉을 할 필요가 없습니다.s큐잉을 합니다.

두 개의 조건 변수가 있는 Mesa 스타일 모니터a그리고.b

비블로킹 조건 변수에서는 신호 연산을 notify라고 부르기도 합니다.이러한 용어는 여기서 설명하는 것입니다.또한 조건 변수에서 대기하는 모든 스레드를 Notify all 조작을 제공하는 것이 일반적입니다.e큐잉을 합니다.

여기에서는, 다양한 조작의 의미를 설명합니다.(각 조작은 다른 조작을 제외하고 실행한다고 가정합니다.따라서 재시작된 스레드는 조작이 완료될 때까지 실행을 시작하지 않습니다.) 

모니터로 들어갑니다.모니터가 잠겨 있는 경우 이 스레드를 입력하세요.이 스레드를 블록에 추가합니다.그렇지 않으면 모니터를 잠그세요.스케줄 반환: 메서드에서 이 스레드를 c.q schedule block this thread notify c.q schedule block this thread notify c.하나의 스레드 t를 c.q에서 삭제(t는 "알림된 스레드"라고 함)한 후 모든 c로 이동합니다.c.q에서 대기하고 있는 모든 스레드를 e 스케줄로 이동합니다.e에 스레드가 있는 경우 선택하고 e에서 스레드 하나를 삭제한 후 모니터를 재시작합니다.

이 스킴의 변형으로서 통지된 스레드는 다음과 같은 큐로 이동할 수 있습니다.w(이것보다 우선합니다)e자세한 내용은 Howard 및 Buhr [5]등을 참조하십시오[4].

어설션c P를 각 조건 변수 c에 관련지을 수 있기 때문에c P가 반드시 true가 되도록 할 수 있습니다.wait c단, 통지 스레드가 점유를 포기한 시점부터 통지 스레드가 선택되어 모니터에 재진입할 때까지 P가 유지되도록c 해야 합니다.이 시간 사이에 다른 탑승자의 활동이 있을 수 있습니다.따라서c P가 단순히 참인 것이 일반적입니다.

이 때문에, 통상, 다음과 같이 각 대기 조작을 루프에 둘러싸야 합니다.

( P )가 아닌 동안 c를 기다립니다.

여기서 P는 P보다 강한c 조건입니다.조작notify c그리고.notify all c는 일부 대기 스레드에 대해 P가 참일 수 있다는 "힌트"로 취급됩니다.이러한 루프가 첫 번째 루프를 통과할 때마다 알림이 손실되었음을 나타냅니다.따라서 논블로킹모니터에서는 너무 많은 알림이 손실되지 않도록 주의해야 합니다.

「힌트」의 예로서, 계좌에 충분한 자금이 확보될 때까지 인출 스레드가 대기하는 은행 계좌를 생각해 주세요.

모니터 클래스 계정{개인int 균형= 0고정 균형>=0민간 NonblockingCondition balanceMayBeBigEnough public메서드 withdraw(int양)전제 조건 금액>=0{는 동안 균형 <,는 기다리balanceMayBeBigEnough를 과시하다 균형>=amount 균형= 균형-a마운트}공개 메서드 예금(int 금액) 전제 조건 금액 > = 0 { 잔액 : = 잔액 + 모든 잔액 알림MayBeBigEnough } }

이 예에서 대기하고 있는 조건은 인출되는 금액의 함수이기 때문에 예금 스레드는 그러한 조건을 실현했음을 알 수 없습니다.이 경우 모니터에 대기하고 있는 각 스레드(한 번에 하나씩)가 해당 어설션이 사실인지 여부를 확인할 수 있도록 하는 것이 좋습니다.

암묵적 조건 변수 모니터

Java 스타일 모니터

Java 언어에서는 각 개체를 모니터로 사용할 수 있습니다.상호 제외가 필요한 메서드는 synchronized 키워드로 명시적으로 표시해야 합니다.코드 블록은 동기화에 의해 마크될 수도 있습니다.

각 모니터(즉 객체)에는 명시적 조건 변수가 있는 것이 아니라 입구 큐 외에 단일 대기 큐가 설치되어 있습니다.모든 대기는 이 단일 대기 큐에서 수행되며 모든 대기가 알림 및 알림모든 작업이 이 큐에 적용됩니다.이 접근방식은 다른 언어(예: C#)에서도 채택되고 있습니다.

암묵적 시그널링

시그널링의 또 다른 접근법은 신호 동작을 생략하는 것입니다.스레드가 모니터에서 나올 때마다(돌아가거나 대기함으로써) 모든 대기 스레드의 어설션이 참임을 확인할 때까지 평가됩니다.이러한 시스템에서는 조건 변수가 필요하지 않지만 어설션을 명시적으로 코드화해야 합니다.기다리는 계약서는

잠깐만요. P: 전제조건 I     모니터의 포스트 컨디션 상태를 변경합니다. P 그리고. I

역사

Brinch Hansen과 Hoare는 그들 자신과 Edsger Dijkstra의 초기 [6]아이디어를 바탕으로 1970년대 초에 모니터 개념을 개발했습니다.Brinch Hansen은 Simula 67의 [1]클래스 개념을 채택한 최초의 모니터 표기법을 발표하여 큐잉 메커니즘을 [7]발명했습니다.Hoare는 프로세스 [2]재개 규칙을 개선했습니다.Brinch Hansen은 Concurrent [6]Pascal에서 모니터의 첫 번째 구현을 만들었습니다.호어는 그들이 세마포어와 동등하다는 것을 증명했다.

모니터(및 동시 파스칼)는 곧 Solo 운영 [8][9]체제에서 프로세스 동기화를 구성하기 위해 사용되었습니다.

모니터를 지원하는 프로그래밍 언어는 다음과 같습니다.

모니터를 네이티브로 지원하지 않는 언어로 구성할 수 있는 라이브러리가 다수 작성되었습니다.라이브러리 호출을 사용할 경우 상호 제외된 코드의 시작과 끝을 명시적으로 표시하는 것은 프로그래머에게 달려 있습니다.Pthreads는 그러한 라이브러리 중 하나입니다.

「 」를 참조해 주세요.

메모들

  1. ^ a b Brinch Hansen, Per (1973). "7.2 Class Concept" (PDF). Operating System Principles. Prentice Hall. ISBN 978-0-13-637843-3.
  2. ^ a b Hoare, C. A. R. (October 1974). "Monitors: an operating system structuring concept". Comm. ACM. 17 (10): 549–557. CiteSeerX 10.1.1.24.6394. doi:10.1145/355620.361161. S2CID 1005769.
  3. ^ Hansen, P. B. (June 1975). "The programming language Concurrent Pascal" (PDF). IEEE Trans. Softw. Eng. SE-1 (2): 199–207. doi:10.1109/TSE.1975.6312840. S2CID 2000388.
  4. ^ a b Howard, John H. (1976). "Signaling in monitors". ICSE '76 Proceedings of the 2nd international conference on Software engineering. International Conference on Software Engineering. Los Alamitos, CA, USA: IEEE Computer Society Press. pp. 47–52.
  5. ^ a b Buhr, Peter A.; Fortier, Michel; Coffin, Michael H. (March 1995). "Monitor classification". ACM Computing Surveys. 27 (1): 63–107. doi:10.1145/214037.214100. S2CID 207193134.
  6. ^ a b Hansen, Per Brinch (1993). "Monitors and concurrent Pascal: a personal history". HOPL-II: The second ACM SIGPLAN conference on History of programming languages. History of Programming Languages. New York, NY, USA: ACM. pp. 1–35. doi:10.1145/155360.155361. ISBN 0-89791-570-4.
  7. ^ Brinch Hansen, Per (July 1972). "Structured multiprogramming (Invited Paper)". Communications of the ACM. 15 (7): 574–578. doi:10.1145/361454.361473. S2CID 14125530.
  8. ^ Brinch Hansen, Per (April 1976). "The Solo operating system: a Concurrent Pascal program" (PDF). Software: Practice and Experience.
  9. ^ Brinch Hansen, Per (1977). The Architecture of Concurrent Programs. Prentice Hall. ISBN 978-0-13-044628-2.
  10. ^ "sync - The Go Programming Language". golang.org. Retrieved 2021-06-17.
  11. ^ "What's the "sync.Cond" dtyler.io". dtyler.io. Retrieved 2021-06-17.

추가 정보

  • 모니터: 운영체제 구조화 개념, C. A. R. Hoare – Communications of the ACM, v.17 n.10, 페이지 549-557, 1974년 10월 [1]
  • 모니터 분류 P.A.M.H. Coupon, Buhr, M. Fortier – ACM Computing Survices, 1995년 [2]

외부 링크