지난 포스팅에서 못다한 과제는 총 세개다.
1. condvar 테스트
2. donate 테스트
3. MLFQ 테스트

하지만 분명 synch.c 파일에서 정의된 cond 관련 함수들을 수정했었다.
semaphore 관련 테스트는 통과하는데 왜 cond 관련 테스트는 통과하지 못한 걸까?!

---

condition이 뭔지, 왜 내부 waiters 의 원소로 semaphore 구조체를 가지는지 이해하지 못했다.

이해하지 않고 무작정
'condition 안에도 리스트가 있다?'
→ '일단 그 리스트도 우선순위로 정렬!'
그렇게 waiters 내의 semaphore를 정렬했는데 이게 문제였다.

우선 이해해보자.
condition은 왜 대기열(waiters)의 원소로 semaphore를 가질까?

우리가 여태까지 semaphore만으로 공유자원을 관리했던 상황을 생각해보자.

[ 일반 자원 ]

일반 자원은 lock을 가진 스레드가 lock을 반환하면 그 자원을 기다리고 있는 대기열의 스레드가 점유하게 된다.(lock 획득)

그런데, 이런 경우가 있을 것이다.

[ 조건 변수를 가진 자원 ]

어떤 자원은 그 자원의 값이 양수여야만 접근할 수 있다고 하자. 더 쉽게 빵집으로 비유할 수 있다.
빵집에 빵을 사러 간 손님들은 빵이 있어야만 그 자원에 접근할 수 있다. 즉, 빵이 있어야 빵을 살 수 있다는 말이다.

그런데 빵이 없다면 어떨까?
절대 접근해서는 안 된다. 즉, 절대 빵을 살 수 없다.

이럴 때를 대비하여 condition variable이 등장하였다.

정리해보자.

condition variable

자원의 value가 특정 조건에 충족해야만(e.g.양수여야만) 스케줄링될 수 있다.
자원의 value가 특정 조건에 충족해하지 않는다면(e.g. 음수라면) condition variable 대기열에서 대기해야한다.
그런 다음 자원이 양수가 되면 대기열에 있는 스레드(semaphore)는 스케줄링될 수 있다.

실은 condition variable 대기열이 있다는 것은 이미 cond var를 충족하지 않은 상황인 것이다.
대기열(cond->waiters)에서 기다리다가, 어느 시점에서 cond var가 충족된다면 순차적으로 ready queue로 이동된다.

Why semaphore?

그런데 왜 condition variable의 대기열 cond->waiters 는 리스트의 원소로 semaphore의 구조체를 가질까?

어차피 대기하는 주체는 thread이지 않나?
만약, thread 구조체라고 가정해보자.

thread 1이 어떠한 조건 변수 자원을 획득하기 위해 기다리는 상황이 되면 blocked 상태로 대기열에서 기다린다.
하지만 평번한 일반 자원에서처럼 lock이 release 되는 상황에서 대기 중인 thread 1은 lock을 획득하게 될까?

아니다.
조건 변수의 충족 여부를 알 수 없기 때문이다.
condition variable의 대기열은 조건 변수의 충족 여부에 따라서 ready list로 옮겨주느냐 마느냐의 이야기이다.
단순히 lock의 holder가 있느냐 없느냐, 있으면 대기하고 없으면 자원을 획득할 수 없다.
.
.
좀 더 이해하기 쉽게 좀 전의 빵집을 예로 들자.

빵을 기다리는 손님이 3명이 있고 나는 2번째 순서다.
진열대에서 빵을 고르던 내 앞의 손님이 이제 계산을 하고 나갔다.
→ 이제 내 차례다!
엇 그런데 앞 손님이 남은 빵을 전부 사간 것이다..
나는 내 차례가 되었지만, 빵을 살 수 없다🥲
제빵사가 빵을 다시 만들어주어야만 빵을 살 수 있다.

이런 경우에 사용하는 것이 condition variable 대기열이다. '자원을 이미 점유하고있냐 없냐'의 문제에 더하여, '현재 자원이 접근 가능한 상태이냐'의 문제까지 고려된다.

.
.

결과적으로,
semaphore를 이용하는 이유는 어떠한 자원을 기다리기 위해 blocked상태로 들어가고,
그 자원을 획득할 수 있게 되어 ready 상태로 이동되는 흐름을
sema_up(), sema_down() 을 통해 일관적으로 구성하려 하기 때문이다.

pint os의 의도적인 설계라고 보면 된다.

.
.

다시 돌아가 한 번 더 정리하자.

condition variable 충족되지 않은 경우

cond_wait()를 호출하여 대기열(cond->waiters)에 추가한다.

• 해당 스레드만을 가지는 semaphore를 생성한다.
• condition variable이 충족될 때까지 waiting 상태로 기다린다.

condition variable 충족된 경우

cond_signal()을 호출하여 대기열(cond->waiters)의 semaphore를 깨운다.

• 우선순위가 가장 높은 semaphore(즉, 스레드)를 ready 상태로 진입시킨다.(sema_up())

  여기에서 semaphore는 여러 thread를 담는 list의 개념이 아니다. cond 대기열에서의 semaphore는 어차피 단일한 스레드만 가지기 때문에 스레드로 가정하고 봐도 좋다.

---

이렇게 개념을 잡고 보니,
기존에 cond->waiters 대기열에 있는 각 semaphore의 semaphore->waiters, 즉 thread를 정렬했던 점이 완전히 잘못되었다는 사실을 꺠닫는다.

실은 semaphore->waiter에는 단일한 thread만 들어가기 때문에 정렬될 필요가 없다.

실제로 정렬되어야 하는 것은
cond->waiters의 각 semaphore elem 자체이다.

따라서 나는 semaphore elem 구조체에 priority 필드를 추가하여 관리하는 방법을 택했다.
방법은 다양할 것 같다.

구현 아이디어

• semaphore_elem
  구조체에 priority 필드를 추가한다.

struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
	int priority;
};

• cond_wait()
  추가되는 semaphore_elem waiter 에 priority를 초기화해준다.

void
cond_wait(struct condition* cond, struct lock* lock) {
	struct semaphore_elem waiter;
	waiter.priority = thread_current()->priority;

	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); sema_compare_priority, NULL);

	lock_release(lock);
	sema_down(&waiter.semaphore);
	lock_acquire(lock);
}

• cond_signal()
  우선순위의 semaphore_elem의 thread를 깨운다.sema_up()

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))
	{
		list_sort(&cond->waiters, sema_compare_priority, NULL);

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

이해하니 구현은 정말 쉽게 느껴진다.
다음 포스팅에서는 priority-donation을 다룬다.