모니터 (동기화)

3. 조건 변수 (Condition Variables)

조건 변수는 특정 조건이 참이 될 때까지 스레드가 대기할 수 있도록 하는 동기화 메커니즘이다. 조건 변수는 뮤텍스와 관련된 스레드들의 큐를 가지며, 스레드는 조건 변수에서 대기하면서 모니터 점유를 일시적으로 해제한다.

많은 애플리케이션에서 상호 배제만으로는 충분하지 않다. 스레드는 특정 조건 가 참이 될 때까지 기다려야 할 수 있다. 바쁜 대기 루프는 상호 배제가 다른 스레드가 조건을 참으로 만들기 위해 모니터에 들어가는 것을 막기 때문에 작동하지 않는다.

해결책은 조건 변수를 사용하는 것이다. 개념적으로 조건 변수는 뮤텍스와 관련된 스레드 큐이며, 스레드는 특정 조건이 참이 될 때까지 대기할 수 있다. 각 조건 변수 는 어설션 와 관련이 있다. 스레드가 조건 변수를 기다리는 동안에는 모니터를 점유하지 않으므로, 다른 스레드가 모니터에 들어가 상태를 변경할 수 있다.

조건 변수와 관련된 세 가지 주요 연산은 다음과 같다.

• `'''wait''' c, m`: 조건 변수 `c`와 모니터와 관련된 뮤텍스(잠금) `m`을 사용한다. 어설션 가 참이 될 때까지 기다린 후 진행해야 하는 스레드에 의해 호출된다. 스레드가 대기하는 동안에는 모니터를 점유하지 않는다.
• `'''signal''' c` (또는 `'''notify''' c`): 어설션 가 참임을 나타내기 위해 스레드에 의해 호출된다.
• `'''broadcast''' c` (또는 `'''notifyAll''' c`): `c`의 대기 큐에 있는 모든 스레드를 깨운다.

• 공유 자원을 조작하는 프로시저군
• 뮤텍스 락
• 자원과 연결된 변수
• 경쟁 상태를 방지하기 위해 가정되는 모니터 불변 조건

3. 1. 조건 변수의 연산

`wait` 연산의 원자성:`wait` 연산 내에서 뮤텍스 해제, 대기 큐로 이동, 스레드 일시 중단(1a, 1b, 1c 단계)은 원자적으로, 즉, 다른 스레드에 의한 간섭 없이 한 번에 수행되어야 한다. 이는 경쟁 조건, 특히 "놓친 깨우기(missed wakeup)" 문제를 방지하기 위해 필수적이다. "놓친 깨우기"는 스레드가 대기 큐에 들어가기 직전에 다른 스레드가 신호를 보내어, 해당 스레드가 영원히 대기 상태에 빠지는 현상이다.
`signal` vs. `broadcast`:`signal`은 대기 중인 스레드 중 하나만 깨우는 반면, `broadcast`는 모든 대기 중인 스레드를 깨운다. `broadcast`는 동일한 조건 변수에 대해 여러 개의 조건(술어)이 연결된 경우에 유용하다. 예를 들어, 생산자-소비자 문제에서 큐가 비어있지 않기를 기다리는 소비자와 큐가 가득 차지 않기를 기다리는 생산자가 동일한 조건 변수를 사용할 수 있다. 이 경우, `signal`은 잘못된 유형의 스레드를 깨울 수 있으므로 `broadcast`를 사용해야 한다.
모니터 사용 패턴:모니터를 사용할 때는 일반적으로 다음과 같은 패턴을 따르며, 조건 변수 `cv`를 기다리기 전에 조건 `p`를 확인하고, `wait` 호출 후에도 조건을 다시 확인하는 것이 중요하다.

```cpp

acquire(m); // 뮤텍스 m 획득

while (!p) { // 조건 p가 참이 아닐 동안

wait(m, cv); // 뮤텍스 m을 해제하고 조건 변수 cv에서 대기

}

// ... 임계 영역 ...

signal(cv2); // 또는 broadcast(cv2); // 다른 조건 변수 cv2에 신호

release(m); // 뮤텍스 m 해제

```

이는 `wait`에서 복귀한 후에도 다른 스레드에 의해 조건이 다시 거짓이 될 수 있기 때문이다(가짜 깨우기, spurious wakeup).

3. 2. 블로킹 조건 변수 (Blocking Condition Variables)

• `e`는 입장 큐이다.
• `s`는 신호를 보낸 스레드의 큐이다.

• `.q`는 조건 변수 에서 대기하는 스레드의 큐이다.

3. 3. 논블로킹 조건 변수 (Nonblocking Condition Variables)

• 모니터 진입:
• 메서드 진입 시 모니터가 잠겨 있으면 이 스레드를 `e`에 추가하고 차단한다.
• 모니터가 잠겨 있지 않으면 모니터를 잠근다.
• 모니터 나가기:
• 스케줄을 호출하고 메서드에서 반환(`return`)한다.
• '''대기''' (wait) :
• 이 스레드를 .q에 추가한다.
• 스케줄을 호출하고 이 스레드를 차단한다.
• '''알림''' (notify) :
• .q에 대기 중인 스레드가 있으면 그 중 하나를 선택하여 제거하고 `e`로 이동한다. (이 스레드를 "알림을 받은 스레드"라고 한다.)
• '''모두 알림''' (notifyAll) :
• .q에 대기 중인 모든 스레드를 `e`로 이동한다.
• 스케줄:
• `e`에 스레드가 있으면 그 중 하나를 선택하여 제거하고 다시 시작한다.
• `e`에 스레드가 없으면 모니터 잠금을 해제한다.

'''모니터 클래스''' ''Account'' {

    '''private''' ''int'' balance := 0

    '''invariant''' balance >= 0

    '''private''' ''NonblockingCondition'' balanceMayBeBigEnough

    '''public method''' withdraw(''int'' amount)

        '''precondition''' amount >= 0

        {

            '''while''' balance < amount '''do''' '''wait''' balanceMayBeBigEnough

            '''assert''' balance >= amount

            balance := balance - amount

        }

    '''public method''' deposit(''int'' amount)

        '''precondition''' amount >= 0

        {

            balance := balance + amount

            '''notify all''' balanceMayBeBigEnough

        }

}

3. 4. 암시적 조건 변수 (Implicit Condition Variables)

• 공유 자원을 다루는 프로시저 (모니터 프로시저, 모니터 함수)
• 뮤텍스 락
• 자원과 연결된 변수
• 경쟁 상태 방지를 위한 모니터 불변 조건

3. 5. 암시적 신호 (Implicit Signaling)

• '''wait''':
• '''사전 조건'''
• '''수정''' 모니터의 상태
• '''사후 조건''' '''그리고'''

3. 6. 생산자-소비자 문제 (Producer-Consumer Problem)

4. 세마포어와 모니터

세마포어는 동기화 함수의 제약 조건을 고려해야 하는 반면, 모니터는 프로시저를 호출하여 간단히 해결할 수 있다. 스레드가 스레드 안전 객체의 메서드를 실행하는 동안, 해당 객체의 뮤텍스(잠금)을 보유함으로써 해당 객체를 '점유'한다고 말한다.^[1] 스레드 안전 객체는 '각 시점에서, 최대 하나의 스레드만이 객체를 점유할 수 있도록' 구현된다.^[1] 처음에 잠금 해제된 락은 각 공용 메서드의 시작 부분에서 잠기고, 각 공용 메서드에서 반환될 때 잠금 해제된다.^[1]

메서드 중 하나를 호출하면, 스레드는 다른 스레드가 스레드 안전 객체의 메서드를 실행하고 있지 않을 때까지 대기해야 한다.^[2] 이 상호 배제가 없으면 두 개의 스레드가 이유 없이 돈을 잃거나 얻을 수 있다.^[2] 예를 들어, 두 개의 스레드가 계정에서 1000USD을 인출할 때 둘 다 true를 반환할 수 있지만 잔액은 1000USD만 감소한다.^[2] 먼저, 두 스레드 모두 현재 잔액을 가져와서 1000USD보다 크다는 것을 확인하고 1000USD을 뺀다.^[2] 그런 다음 두 스레드 모두 잔액을 저장하고 반환한다.^[2]

모니터는 다음으로 구성된다.^[3]

• 공유 자원을 조작하는 프로시저군 (모니터 프로시저, 모니터 함수)^[4]
• 뮤텍스 락^[4]
• 자원과 연결된 변수^[4]
• 경쟁 상태를 방지하기 위해 가정되는 모니터 불변 조건^[4]

5. 역사

브린치 한센과 앤서니 호어(C. A. R. Hoare)는 1970년대 초, 자신들과 에츠허르 데이크스트라의 이전 아이디어를 바탕으로 모니터 개념을 개발했다.^[6] 브린치 한센은 시뮬라의 클래스 개념을 채택하여 최초의 모니터 표기법을 발표했으며,^[1] 큐잉 메커니즘을 발명했다.^[7] 호어는 프로세스 재개 규칙을 개선했다.^[2] 브린치 한센은 Concurrent Pascal에서 모니터의 첫 번째 구현을 만들었다.^[6] 호어는 이를 세마포어와 동등함을 입증했다.

모니터(및 Concurrent Pascal)는 곧 Solo 운영 체제에서 프로세스 동기화를 구조화하는 데 사용되었다.^[8][9]

6. 모니터를 지원하는 프로그래밍 언어

다음은 모니터를 지원하는 프로그래밍 언어 목록이다.

Pthreads와 같이 모니터를 기본적으로 지원하지 않는 언어에서도 여러 라이브러리를 통해 모니터를 구축할 수 있다. 라이브러리 호출이 사용될 때는 상호 배타적으로 실행되는 코드의 시작과 끝을 프로그래머가 명시적으로 표시해야 한다.

참조

_[1] 서적 Operating System Principles https://archive.org/[...] Prentice Hall
_[2] 논문 Monitors: an operating system structuring concept 1974-10
_[3] 논문 The programming language Concurrent Pascal https://authors.libr[...] 1975-06
_[4] 간행물 Signaling in monitors http://dl.acm.org/ci[...] IEEE Computer Society Press
_[5] 논문 Monitor classification 1995-03
_[6] 간행물 Monitors and concurrent Pascal: a personal history Association for Computing Machinery
_[7] 논문 Structured multiprogramming (Invited Paper) 1972-07
_[8] 논문 The Solo operating system: a Concurrent Pascal program http://brinch-hansen[...] 1976-04
_[9] 서적 The Architecture of Concurrent Programs Prentice Hall
_[10] 웹사이트 sync - The Go Programming Language https://golang.org/p[...] 2021-06-17
_[11] 웹사이트 What's the "sync.Cond" {{!}} dtyler.io https://dtyler.io/ar[...] 2021-06-17
_[12] 문서 Monitor Class (System.Threading) | Microsoft Learn https://learn.micros[...]
_[13] 문서 lock ステートメント - 共有リソースへのスレッド アクセスを同期します - C# | Microsoft Learn https://learn.micros[...]
_[14] 문서 std::condition_variable - cppreference.com https://ja.cpprefere[...]
_[15] 문서 条件変数の利用方法 - cpprefjp C++日本語リファレンス https://cpprefjp.git[...]
_[16] 문서 System.SyncObjs.TConditionVariableMutex - RAD Studio API Documentation https://docwiki.emba[...]
_[17] 문서 pthread_cond_timedwait, pthread_cond_wait - wait on a condition | The Open Group Base Specifications Issue 6 / IEEE Std 1003.1, 2004 Edition https://pubs.opengro[...]
_[18] 문서 Synchronization - 1.84.0 / §Condition Variables https://www.boost.or[...]
_[19] 문서 thread/include/boost/thread/win32/condition_variable.hpp at boost-1.84.0 · boostorg/thread · GitHub https://github.com/b[...]
_[20] 문서 Condition Variables - Win32 apps | Microsoft Learn https://learn.micros[...]