[PintOS] 세마포어랑 조건 변수랑 뭐가 어떻게 다른거지

카테고리 없음

[PintOS] 세마포어랑 조건 변수랑 뭐가 어떻게 다른거지

나한나한나한나 2024. 5. 14. 20:39

조건 변수(Condition Variable)와 세마포어(Semaphore)는 모두 동시성 프로그래밍에서 중요한 동기화 도구입니다. 그러나 이들은 사용 목적과 동작 방식에서 몇 가지 중요한 차이점을 가지고 있습니다.

세마포어 (Semaphore)

세마포어는 일종의 카운터로, 공유 자원에 대한 접근을 제어하는 데 사용됩니다. 이 카운터는 공유 자원의 사용 가능한 인스턴스 수를 나타냅니다. 세마포어의 주요 연산은 두 가지입니다:

P (proberen, 시도하다) 또는 wait: 세마포어 값을 감소시키며, 값이 0이면 호출 스레드는 자원이 사용 가능해질 때까지 대기합니다.
V (verhogen, 증가시키다) 또는 signal: 세마포어 값을 증가시키고, 대기 중인 스레드 중 하나를 깨웁니다 (있을 경우).

세마포어는 자원의 개수를 제한하고, 해당 자원에 대한 접근을 여러 스레드가 안전하게 할 수 있도록 관리합니다.

조건 변수 (Condition Variable)

조건 변수는 스레드가 특정 조건이 충족될 때까지 대기하게 할 때 사용됩니다. 조건 변수는 보통 락(lock)과 함께 사용되며, 다음과 같은 두 가지 주요 연산을 가집니다:

wait: 스레드가 조건 변수에서 대기하게 하며, 이때 연결된 락을 해제합니다. 이로 인해 다른 스레드가 락을 획득하고 조건을 변경할 수 있게 됩니다. 조건이 충족되면 스레드는 다시 깨어나 락을 재획득합니다.
signal 또는 broadcast: 하나의 스레드(signal) 또는 모든 대기 중인 스레드(broadcast)를 깨워 조건의 변경을 알립니다.

조건 변수는 주로 특정 조건 하에서 스레드의 실행을 동기화하는 데 사용됩니다. 예를 들어, 버퍼가 비었을 때 생산자 스레드가 대기하고, 데이터가 추가되면 소비자 스레드를 깨우는 패턴에 자주 사용됩니다.

차이점

사용 목적: 세마포어는 자원의 수를 제어하는 데 사용되며, 조건 변수는 특정 조건의 충족을 기다리는 데 사용됩니다.
작동 방식: 세마포어는 자원의 개수를 카운팅하며, 조건 변수는 특정 조건에 대한 스레드의 대기와 깨우기를 관리합니다.
API의 복잡성: 세마포어는 비교적 단순한 API를 제공하는 반면, 조건 변수는 보통 락과 함께 사용되어 관리가 더 복잡합니다.

이러한 차이점을 이해하면, 각각의 도구가 적합한 상황을 판단하는 데 도움이 됩니다. 세마포어는 접근 제어가 필요한 상황에, 조건 변수는 특정 조건을 기다려야 하는 동기화가 필요한 상황에 적합합니다.

뭔 소린지 잘 모르겠다

소스코드에 달려 있는 주석을 살펴보자

/* Initializes condition variable COND.  A condition variable
   allows one piece of code to signal a condition and cooperating
   code to receive the signal and act upon it. */
void
cond_init (struct condition *cond) {
	ASSERT (cond != NULL);

	list_init (&cond->waiters);
}

이 코드는 조건 변수(condition variable)를 초기화하는 함수를 정의합니다. 조건 변수는 코드의 한 부분이 특정 조건을 신호할 수 있게 하고, 협력하는 다른 코드가 이 신호를 받아 그에 따라 행동할 수 있게 합니다. 다음은 이 코드의 해석과 설명입니다:

/* 조건 변수 COND를 초기화합니다. 
조건 변수는 한 코드 부분이 조건을 신호할 수 있도록 하고, 
협력하는 코드가 이 신호를 수신하고 그에 따라 행동할 수 있게 합니다. */
void
cond_init (struct condition *cond) {
	ASSERT (cond != NULL);

	list_init (&cond->waiters);
}

설명:

조건 변수 초기화 (cond_init 함수): 이 함수는 condition 타입의 객체인 cond를 매개변수로 받아 초기화합니다.
유효성 검사: ASSERT 매크로를 사용하여 cond가 NULL이 아님을 확인합니다. 이는 함수가 유효한 메모리 주소에서 동작하도록 보장합니다.
대기열 초기화: cond->waiters는 이 조건 변수를 대기 중인 스레드의 목록을 유지합니다. list_init 함수를 호출하여 이 리스트를 초기화합니다. 이렇게 하면 나중에 조건이 신호될 때 스레드를 깨우거나 관리할 수 있습니다.

조건 변수는 일반적으로 상호 배제(mutex) 락과 함께 사용되어, 특정 조건 하에서 스레드의 실행을 동기화하고, 스레드 간의 통신을 용이하게 합니다. 초기화 과정은 조건 변수가 올바르게 기능할 수 있도록 필요한 구조를 설정하는 기본적인 단계입니다.

/* Atomically releases LOCK and waits for COND to be signaled by
   some other piece of code.  After COND is signaled, LOCK is
   reacquired before returning.  LOCK must be held before calling
   this function.

   The monitor implemented by this function is "Mesa" style, not
   "Hoare" style, that is, sending and receiving a signal are not
   an atomic operation.  Thus, typically the caller must recheck
   the condition after the wait completes and, if necessary, wait
   again.

   A given condition variable is associated with only a single
   lock, but one lock may be associated with any number of
   condition variables.  That is, there is a one-to-many mapping
   from locks to condition variables.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_push_back (&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

이 코드는 조건 변수(condition variable)를 사용하여 특정 조건이 신호될 때까지 기다리는 동기화 메커니즘을 구현합니다. 이 함수는 특정한 동작을 수행하기 전에 락(lock)을 획득해야 하며, 조건이 신호되기를 기다린 후에는 다시 락을 획득해야 합니다. 다음은 이 코드의 해석과 설명입니다:

/* 원자적으로 LOCK을 해제하고, 다른 코드에 의해 COND가 신호될 때까지 기다립니다. 
COND가 신호된 후에는 반환되기 전에 LOCK을 다시 획득합니다. 
이 함수를 호출하기 전에 LOCK을 보유해야 합니다.
이 함수에 의해 구현된 모니터는 "Mesa" 스타일이며, "Hoare" 스타일이 아닙니다. 
즉, 신호를 보내고 받는 것이 원자적 연산이 아닙니다. 
따라서 일반적으로 호출자는 대기가 완료된 후 조건을 다시 확인해야 하며, 필요하다면 다시 대기해야 합니다.
주어진 조건 변수는 하나의 락만과 연관되지만, 하나의 락은 여러 개의 조건 변수와 연관될 수 있습니다. 
즉, 락에서 조건 변수로의 일대다 매핑이 있습니다.
이 함수는 스레드를 대기 상태로 만들 수 있으므로, 인터럽트 핸들러 내에서는 호출될 수 없습니다. 
이 함수는 인터럽트가 비활성화된 상태에서 호출될 수 있지만, 대기가 필요한 경우 인터럽트가 다시 활성화됩니다. */
void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_push_back (&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

설명:

조건 대기 (cond_wait 함수): 이 함수는 조건 변수 cond와 락 lock을 사용합니다. 함수 시작 전에 현재 스레드가 lock을 반드시 획득하고 있어야 합니다.
세마포어 초기화 및 대기열 추가: waiter라는 지역 세마포어 요소를 초기화하고 cond의 대기열에 추가합니다. 이 세마포어는 대기 상태의 스레드를 관리하는 데 사용됩니다.
락 해제 및 대기: 락을 해제하고 sema_down을 호출하여 waiter.semaphore의 값이 증가할 때까지 (즉, 조건이 신호되어 대기가 해제될 때까지) 스레드를 대기 상태로 만듭니다.
락 재획득: 조건이 신호되고 나면, 스레드는 다시 lock을 획득합니다.

이 코드는 "Mesa" 스타일의 모니터링을 구현하고 있어서, 신호를 받은 후에는 조건이 여전히 충족되는지 확인해야 할 수도 있습니다. 이는 signal 연산 후에 대기 상태로 돌아갈 수도 있다는 것을 의미합니다. 조건 변수와 락을 사용하는 이러한 방식은 특정 조건 하에서 스레드 간의 동기화를 안전하게 구현할 수 있게 해 줍니다.

신호를 보내고 받는 것이 원자적 연산이 아니라는 게 뭔 소리?

"신호를 보내고 받는 것이 원자적 연산이 아니다"라는 말은, 신호를 보내는 동작과 신호를 받는 동작이 단일, 불가분의 연산으로 동시에 발생하지 않는다는 의미입니다. 즉, 이 두 동작 사이에는 다른 동작들이 끼어들 수 있는 여지가 있습니다.

원자적(Atomic) 연산

원자적 연산은 중간 단계 없이 시작되어 완전히 완료되는 연산을 말합니다. 원자적 연산 중에는 어떠한 다른 동작도 끼어들 수 없으며, 연산은 완전히 성공하거나 아예 실행되지 않은 것처럼 남습니다. 이런 특성 때문에, 원자적 연산은 동시성 프로그래밍에서 데이터의 일관성과 무결성을 보장하는 데 중요한 역할을 합니다.

Mesa 스타일 vs Hoare 스타일

조건 변수와 관련하여 Mesa 스타일과 Hoare 스타일 모니터는 신호 전달 방식에서 차이를 보입니다:

Hoare 스타일: 이 스타일에서는 신호를 보내는 연산(signal)과 신호를 받는 스레드가 깨어나는 동작이 원자적으로 처리됩니다. 즉, signal을 호출한 스레드는 신호를 받는 스레드가 락을 획득하고 실행을 시작할 때까지 실행을 중지합니다. 이 방식은 신호를 보내고 받는 사이에 상태가 변경되지 않도록 보장합니다.
Mesa 스타일: Mesa 스타일에서는 signal 연산이 신호를 대기중인 스레드 목록에서 단지 스레드를 대기열에서 제거하는 것까지만 담당하고, signal을 호출한 스레드는 계속 실행됩니다. 신호를 받은 스레드는 실행 준비가 되었지만, 실행을 재개하기 전에 다시 락을 획득해야 하며, 이 과정에서 원래 대기하고 있던 조건이 여전히 만족하는지 검사해야 할 수도 있습니다. 이는 신호를 보낸 후 스레드가 깨어나 락을 획득하기 전에 다른 스레드가 락을 획득하고 상태를 변경할 수 있기 때문입니다.

결론적으로, Mesa 스타일 모니터에서는 조건을 다시 확인하고 필요에 따라 다시 대기해야 할 수 있으며, 이는 신호 전달이 원자적이지 않기 때문에 발생하는 상황입니다. 이로 인해 프로그래머는 조건 변수를 사용할 때 주의 깊게 조건을 검사하고 대기 로직을 설계해야 합니다.

여전히 잘 모르겠다... CV의 나머지 함수도 살펴보자

/* If any threads are waiting on COND (protected by LOCK), then
   this function signals one of them to wake up from its wait.
   LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

이 코드는 조건 변수(condition variable)에 대기 중인 스레드 중 하나를 깨우는 함수를 정의합니다. 이 함수는 특정 락(LOCK)으로 보호되는 조건 변수 COND에 대해 작동합니다. 다음은 이 코드의 해석과 설명입니다:

/* COND에 대기 중인 스레드가 있다면 (LOCK으로 보호되는), 
이 함수는 그 중 하나를 그들의 대기 상태에서 깨웁니다. 
이 함수를 호출하기 전에 LOCK을 획득해야 합니다.

인터럽트 핸들러는 락을 획득할 수 없으므로, 
인터럽트 핸들러 내에서 조건 변수에 신호를 보내려고 시도하는 것은 의미가 없습니다. */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

설명:

조건 신호 함수 (cond_signal 함수): 이 함수는 condition 타입의 객체인 cond와 lock을 매개변수로 받아, cond에 대기 중인 스레드 중 하나를 깨우는 역할을 합니다.
유효성 검사와 조건: 함수는 여러 ASSERT 매크로를 통해 cond와 lock이 NULL이 아님을 확인하고, 함수가 인터럽트 핸들러에서 호출되지 않으며, 현재 스레드가 lock을 보유하고 있는지를 확인합니다.
스레드 깨우기: cond->waiters 리스트가 비어 있지 않은 경우, 리스트의 맨 앞에서 대기 중인 semaphore_elem 구조체를 꺼내 sema_up 함수를 호출하여 해당 세마포어의 값을 증가시키고, 대기 중인 스레드를 깨웁니다.

이 과정을 통해 조건 변수와 연결된 세마포어를 사용하여 스레드가 깨어나도록 하며, 이는 다른 스레드가 락을 획득할 수 있도록 하여 상호작용을 진행합니다. 조건 변수를 사용하는 이러한 방식은 스레드 간의 동기화를 안전하고 효율적으로 관리할 수 있게 해 줍니다.

/* Wakes up all threads, if any, waiting on COND (protected by
   LOCK).  LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
void
cond_broadcast (struct condition *cond, struct lock *lock) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);

	while (!list_empty (&cond->waiters))
		cond_signal (cond, lock);
}

이 코드는 조건 변수(condition variable)에 대기 중인 모든 스레드를 깨우는 함수를 정의합니다. 이 함수는 특정 락(LOCK)으로 보호되는 조건 변수 COND에 대해 작동합니다. 다음은 이 코드의 해석과 설명입니다:

/* COND에 대기 중인 모든 스레드를 깨웁니다 (LOCK으로 보호되는). 
이 함수를 호출하기 전에 LOCK을 획득해야 합니다.

인터럽트 핸들러는 락을 획득할 수 없으므로, 
인터럽트 핸들러 내에서 조건 변수에 신호를 보내려고 시도하는 것은 의미가 없습니다. */
void
cond_broadcast (struct condition *cond, struct lock *lock) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);

	while (!list_empty (&cond->waiters))
		cond_signal (cond, lock);
}

설명:

조건 변수 전체 신호 함수 (cond_broadcast 함수): 이 함수는 condition 타입의 객체인 cond와 lock을 매개변수로 받아, cond에 대기 중인 모든 스레드를 깨우는 역할을 합니다.
유효성 검사: 함수는 ASSERT 매크로를 사용하여 cond와 lock이 NULL이 아님을 확인합니다.
모든 스레드 깨우기: cond->waiters 리스트가 비어 있지 않을 때까지 반복하며, cond_signal 함수를 호출하여 대기 중인 각 스레드를 순차적으로 깨웁니다. 이는 cond_signal을 여러 번 호출하여 리스트에 있는 모든 웨이터를 처리할 때까지 반복됩니다.

이 함수는 특정 조건 하에서 동시에 여러 스레드를 깨울 필요가 있을 때 사용됩니다. 예를 들어, 어떤 자원이 다시 사용 가능해졌을 때 모든 대기 중인 스레드에게 동시에 알려주어 경쟁 상황에서 자원을 재분배할 수 있도록 하는 경우에 유용합니다. 조건 변수를 이용한 이런 방식은 복잡한 동기화 문제를 효율적으로 해결할 수 있게 도와줍니다.

여전히 모르겠다!

인생의 스승 유튜브를 뒤져보자

경쟁 조건 race condition
- 여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
동기화 synchronization
- 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것
임계 영역 critical section
- 공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능한 영역
- 하나의 프로세스/스레드만 진입해서 실행 = Mutual Exclusion

스핀락 spinlock 예시
- T1이 global lock을 1로 만들고 임계 영역 진입
- T2는 test_and_set(&lock)의 리턴값이 0이 될때까지 == T1이 작업을 마치고 lock을 0으로 변경할 때까지
  while문을 탈출하지 못하고 계속해서 반복(대기)
- test_and_set()은 CPU atomic 명령어
  - 실행 중간에 간섭받거나 중단되지 않는다
  - 같은 메모리 영역에 대해 동시에 실행되지 않는다

락이 준비되면 나 깨워 -> 뮤텍스
- 스레드 중 하나가 락을 가지고 임계영역에 진입, 임계영역을 나오면서 언락(락을 반환)
- Mutex::lock()
  - 스레드가 락을 가지려면 -> value를 취득해야만 함
  - value가 0이면 -> wait list(큐)에 들어가서 sleep
  - value가 0이 아니면 -> lock을 얻고 value를 0으로 변경
- Mutex::unlock()
  - wait list(큐)에 하나라도 대기중이라면 그 중에 하나를 깨운다
  - wait list가 비어있으면 -> value를 1로 변경
- 그럼 guard는 뭐냐?
  - value값 변경이 발생할 때, 임계 영역 안에서 안전한 작업을 보장받기 위한 장치
  - 스핀락에서 value를 취득하듯이, while문 안에서 guard를 취득하는 절차가 존재
- 뮤텍스는 스핀락보다 항상 우월한가?
  - 아니다. 멀티 코어 환경이고, 임계 영역에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면, 스핀락이 뮤텍스보다 더 이점이 있다.

세마포어: signal mechanism을 가진, 하나 이상의 프로세스/스레드가 임계 영역에 접근 가능하도록 하는 장치
- value가 0/1 binary뿐만 아니라, +1, -1하면서 여러 정수로 변할 수 있다
- 임계 영역에 하나 이상의 스레드가 접근할 수 있도록 하기 위함
- value가 0/1 -> 이진 세마포어, 여러 정수 -> 카운팅 세마포어
  - 그러면 이진 세마포어랑 뮤텍스랑 뭐가 다름?
    - 소유권: 뮤텍스는 소유권과 소유권에 따른 책임이 명확하며, 이진 세마포어는 소유권 개념이 없습니다.
    - 사용 목적: 뮤텍스는 데이터의 일관성을 유지하기 위해 주로 사용되며, 이진 세마포어는 더 일반적인 동기화 및 스레드 간 통신에 사용될 수 있습니다.
    - 획득 및 해제: 뮤텍스는 같은 스레드에 의해서만 획득 및 해제가 가능하지만, 이진 세마포어는 한 스레드가 획득하고 다른 스레드가 해제할 수 있습니다.

세마포어의 특별한 기능: 시그널
P2는 P1의 task1이 끝나야만 task3를 수행할 수 있다.
다른 말로, 시그널 매커니즘을 가진다

우선순위 역전/기부 등의 개념은 뮤텍스에서 쓰인다. 락을 건 본인만 언락할 수 있기 때문에
따라서 상호 배제만 필요하다면 뮤텍스를, 작업 간의 실행 순서 동기화가 필요하다면 세마포어를 권장

모니터

mutual exclusion을 보장
조건에 따라 스레드를 대기(waiting)상태로 전환하는 기능
모니터는 언제 사용되는가?
- 한 번에 하나의 스레드만 실행되어야 할 때
- 여러 스레드와 협업이 필요할 때
모니터의 구성 요소
- mutex
  - 뮤텍스: 임계 영역에서 mutual exclusion을 보장하는 장치
  - 임계 영역에 진입하려면 mutex lock을 취득해야 함
  - mutex lock을 취득하지 못한 스레드는 큐에 들어간 후 대기(waiting)상태로 전환
  - mutex lock을 쥔 스레드가 락을 반환하면 락을 기다리며 큐에 대기 상태로 있던 스레드 중 하나가 실행
- condition variable(s)
  - waiting queue를 가짐 - 조건이 충족되길 기다리는 스레드들이 대기 상태로 머무는 곳
  - condition variable에서 주요 동작(operation)
    - wait
      - 스레드가 자기 자신을 condition variable의 waiting queue에 넣고 대기 상태로 전환
    - signal
      - waiting queue에서 대기중인 스레드 중 하나를 깨움
    - broadcast
      - waiting queue에서 대기중인 스레드 전부를 깨움
- 두 개의 큐
  - entry queue: 임계구역에 진입을 기다리는 큐
  - waiting queue: 조건이 충족되길 기다리는 큐
- bounded producer / consumer problem
  - 버퍼의 사이즈는 고정
    - 생산자는 아이템을 생산해서 버퍼에 삽입
    - 소비자는 버퍼에서 아이템을 꺼내 사용

여기서부터는 핀토스에 별다른 도움이 안 되는것 같아서 생략

필요할 것 같으면 이어서 진행