. [PintOS, Project1] Condition Variable을 이용한 Monitor System
본문 바로가기
Pintos Project/Project 1

[PintOS, Project1] Condition Variable을 이용한 Monitor System

by 불냥이_ 2021. 2. 4.

Monitor System은 Mutex와 Busy Waiting을 동시에 관리해주는 시스템이다. 

 

 어떤 CA(임계영역)의 Mutex를 보장하기 위해서, CA에 관련되어있는 thread는 모두 재우고(Busy waiting 관리, 재운다는 정확한 의미는 차후 서술하겠다.) 오직 하나의 thread만 CA에서 작업하도록 한다(Mutex). 그리고 그 CA에서 작업이 끝나면 자고 있는 thread 중에 한 thread에 signal을 보내서, CA에서 작업하도록 한다.

 

 즉, 어떤 thread가 한 임계영역에 대해 작업하고 있는데, 이 임계영역과 관계가 있는 thread들은 조건이 만족되기 전에는 활동하지 않는다. 이 '조건'을 이용하여 thread를 관리하는 시스템을 Condition Variable을 이용한 Monitor System이라고한다.

 

 Monitor는 구현하는 사람마다 조금씩 개념이나 메커니즘이 달라질 수 있는데, 여기서는 PintOS를 기준으로 설명하도록 하겠다.

 

 

 임계영역으로는 크기가 5인 배열이 있다. 여기에는 배열이 비어있으면 데이터를 채워놓을 수 있고(push), 데이터가 이미 들어있으면 뺄 수도 있다(pop).

 

 스레드 두 개를 가정해보자. thread PUSH은 데이터가 꽉 차 있지 않으면 데이터를 집어넣는다. 간단하게 1만 집어넣는다고 하자.  thread POP은 반대로 데이터가 비어있지 않으면 데이터를 빼낸다.

 

그림 1. PUSH와 POP

 

 아시다시피, 이 배열은 MUTEX를 보장받아야하며, 배열이 완전히 비어있다면 (empty) POP을 실행하지 않고, 반대로 꽉차있다면(full) PUSH를 실행하지 않는다고 해보자.

 

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

struct condition not_empty;
struct condition not_full;

 condition구조체의 not_empty와 not_full을 만들었다. 이 두 구조체는 한 lock에 의해 MUTEX상태가 된다. 상기한대로 PUSH가 반복되다가 배열이 꽉 차면, PUSH는 배열이 완전히 비기 전까지 실행되지 않는 조건(condition)을 가지고 있다 (그래서 완전히 비기 전까지는 실행되지 않아서 condition 구조체의 이름이 not_empty가 된다.). 그래서 우리는 이 경우 PUSH의 semaphore를 not_empty로 보낸다(cond_wait() 실행). 이는 아래와 같은 함수로 이루어진다.

 

 ※ 이 때, not_full에는 POP이 들어있을 수 있다. 그래서 배열을 꽉 채우는 순간에 cond_signal()로 POP을 깨울 수 있다. 이것을 처음 읽는다면 무시하고 일단 아래로 진행한 뒤, 나중에 다시 보라.

 

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(&not_empty, &empty_lock) 같은 형태로 호출될 것이다. 

sema_init으로 semaphore 구조체인 sema를 만들고 이 sema를 not_empty에 삽입한다. 주의할 점은, 이 때, PUSH는 자기 자신의 sema를 not_empty에 삽입하면서 not_empty의 배열 구조체의 MUTEX를 보장받기 위해 not_empty의 lock을 들고있다.

 

 

그림 2. cond_wait() 으로 condtion_varaible에 semaphore 삽입

 그래서 not_empty의 lock을 들고있는 동안 자기자신을 not_empty에 삽입한다. 그리고 삽입이 완료되면 not_empty의 lock을 풀어준다(lock_release()) 

 

 이제 PUSH를 재울 시간이다. 재운다는 것을 해당 스레드가 running 상태가 아니면서 CPU 자원도 소모하지 않는 상태를 말한다. PintOS에서는 status = blocked라고 말한다. 

 

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_push_back (&sema->waiters, &thread_current ()->elem);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 sema_down이 일어난 semaphore는 누군가가 시그널을 보내줘서 sema_up()이 일어나기 전에는 sema->value가 0이 된다. 그리고 이 동안 이 semaphore의 주인 thread (이 경우는 PUSH)는 blocked상태가 되어있다. 다른 누군가가 시그널을 보내줘서 sema->value > 0 이 되기 전에는 while문을 반복해서 돌 것이다. 

 

그러면 이 동안 POP이 일을해서 배열을 모두 비웠다고 해보자. 그러면 PUSH가 일어날 조건 (배열이 모두 비워짐) 을 만족하므로 POP이 PUSH에게 시그널을 줘야한다. 이는 아래와 같은 함수로 이루어져있다.

 

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;
	intr_set_level (old_level);
}

  not_empty에 PUSH의 sema가 있었다. 이것을 꺼내서 (list_pop_front()) 그 sema의 주인 thread를 불러오고 (list_entry()) 그 thread의 block상태를 해제한다. (thread_unblock())

 

 그리고 sema->value가 ++되었기 때문에, 상기의 sema_down()에서 while문을 벗어날 수 있게 된다. 이 while문을 벗어나면 cond_wait()에서 lock_acquire()로 lock을 획득할 수 있게되고, 다시 배열이 꽉 차서 자기자신에 대해 cond_wait()을 실행시키기 전에는 다른 어떠한 thread도 깨어나지 않을 것이다.

 

 

 이렇게 PUSH와 POP은 자기 자신의 작업을 완수하기 전까지, 다른 thread들은 CPU를 점유하지 않고(blocked), 해당 임계영역에 관계된 thread들은 임계영역에 접근하는 것이 봉쇄되어 있으므로(wait) MUTEX를 보장받음과 동시에 busy waiting 문제를 해결할 수 있다. 

댓글