priority-condvar

사실 해당 테스트 케이스가 금방 끝난다고 해서 먼저한건데, 하루정도 걸렸습니다…

condvar은 condition variable (조건 변수) 를 잘 구현했는지 확인하는 테스트 케이스 입니다.

condition variable(조건 변수)

스레드가 어떤 특정 조건이 만족될 때까지 기다릴 수 있도록 도와주는 동기화 도구 입니다.

비유를 통한 조건 변수 이해

• 카페에 줄 서서 주문하려는 손님들 = 여러 스레드
• 바리스타가 “주문해주세요!”라고 말할 때까지 기다려야 함 = 어떤 조건이 만족될 때까지 기다림
• 각 손님은 자기 차례가 올 때까지 줄에서 대기 (wait)
• 바리스타가 손님을 부르면 (signal), 한 명이 대기열에서 빠져서 주문을 함 (깨움)

→ ‘대기했다가, 어떤 조건이 만족되면 깨워줌’을 구현한 것이 condition variable

cond_wait 함수의 동작 흐름

1. 현재 스레드는 lock을 들고 있습니다.
2. 조건이 아직 만족되지 않아서 기다리기로 결정합니다. (signal 호출 전까지)
3. 스레드는 lock을 놓고(cond_wait 내부에서), 대기열(cond->waiters)에 자신을 등록하고 세마포어로 블록됩니다.
4. 나중에 cond_signal()이 호출될 때까지 대기합니다.

→ cond_wait()는 lock_release()와 sema_down()을 세트로 합니다.

cond_signal 함수의 동작 흐름

1. 어떤 조건이 만족됩니다. (ex: 자원이 들어옴)
2. 대기하고 있는 스레드 중 하나를 꺼냅니다.
3. 그 스레드의 세마포어를 sema_up()으로 깨워줍니다.

→ 신호를 받은 스레드는 sema_down()에서 깨어나서, 다시 lock_acquire()를 하고 원래 하던 일을 마저 수행합니다.

구현

• cond->waiters: 세마포어 리스트 (struct semaphore_elem)
• 각 스레드마다 semaphore_elem (개인적인 세마포어)를 가집니다. (value = 0)
• cond_wait()는 자신만의 세마포어를 초기화해서 waiters에 추가하고 block
• cond_signal()은 waiters에서 하나 꺼내서 그 세마포어를 sema_up() 호출

Pintos 에서는 조건 변수에서 세마포어를 사용한다.

저는 사실 조건 변수로 세마포어를 사용한다는 개념이 이해되지 않았습니다. 그래서 예시를 좀 더 명확하게 알아보도록 하겠습니다.

기본적으로 조건을 기다리는 각 스레드마다 개인적인 세마포어(초기값 0)을 하나 만들고, 이 세마포어를 통해 block / unblock 을 컨트롤 합니다. 각 함수에서 세마포어를 어떤 식으로 사용하는지 알면 이해하기 쉬울 것 같습니다.

cond_wait()의 세마포어 사용

1. waiter.semaphore = 0 (아직 신호 없음)
2. cond->waiters 리스트에 나를 추가
3. lock_release() — 내가 공유 데이터에 접근하지 않겠다고 밝입니다
4. sema_down(&waiter.semaphore); ← 여기서 block
   (value가 0이라서 sema_down은 block됨)

cond_signal()의 세마포어 사용

1. waiters 리스트에서 가장 우선순위 높은 스레드를 선택
2. 그 스레드의 waiter.semaphore를 sema_up()
   → value가 1이 되므로 block되었던 sema_down()이 깨어집니다
3. 깨어난 스레드는 sema_down() 이후에 다시 lock_acquire()

비유법

• 스레드 A, B, C가 호텔 리셉션 앞 의자에 앉아 대기 중 (조건 변수 waiters)
• 각자 손에 호출 벨🔔(세마포어)을 들고 있습니다
• 직원이 호출하면 특정 스레드의 벨을 누름 → 그 스레드가 깨어남

"깨우기 위한 벨 역할"을 세마포어가 해주는 것입니다!

→ 결론적으로 condition 변수 자체는 스레드를 queue에만 넣는 도구이고, 실제 block과 unblock은 세마포어를 이용해 이루어집니다.

synch.c 수정사항

경로: threads/synch.c

cond_wait

세마포어를 사용하여 signal이 오기전까지 리소스를 낭비하지 않고 잠을 잡니다.
해당 과정을 위해서는 세마포어들 사이에서도 우선순위에 따라 스레드를 정렬(waiters 리스트)할 필요가 있습니다. 그래서 다음과 같이 코드를 작성하고, priority_cond_cmp라는 함수를 통해 정렬을 합니다.

// 원본
list_push_back (&cond->waiters, &waiter.elem);

// 수정본
list_insert_ordered (&cond->waiters, &waiter.elem, priority_cond_cmp, NULL);

priority_cond_cmp 추가

해당 코드를 구현하는데 시간이 생각보다 굉장히 오래 걸렸습니다. 중간의 if문이 그 이유입니다.

앞전에서 했던 cmp 비교함수들과 달리, 각 스레드의 세마포어 인자에 대해 생각하고 priority에 따라서 정렬을 해야됐기 때문입니다.

여기서 끝나는 것이 아니라 waiters 리스트가 비었는데도 비교를 수행하는 경우에 대해서 false 값을 반환해야됩니다. 왜냐하면, 리스트가 비어 있는데도 list_front()로 비교를 시도하면 커널 패닉이 발생하고, 또는 의미 없는 비교 결과가 나와 잘못된 스케줄링이 일어날 수 있기 때문입니다.

bool priority_cond_cmp (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct semaphore_elem *sema_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sema_b = list_entry(b, struct semaphore_elem, elem);
	if (list_empty (&sema_a -> semaphore.waiters) && list_empty (&sema_b -> semaphore.waiters)) return false; // 리스트 비었을때 예외처리
	if (list_empty (&sema_a -> semaphore.waiters)) return false;   // 리스트 비었을때 예외처리
	if (list_empty (&sema_b -> semaphore.waiters)) return true;    // 리스트 있을땐 true
	struct thread *T_A = list_entry(list_front(&sema_a -> semaphore.waiters), struct thread, elem);
	struct thread *T_B = list_entry(list_front(&sema_b -> semaphore.waiters), struct thread, elem);

	return T_A -> priority > T_B -> priority;
}

cond_signal

시그널을 받음에 따라 세마업을 하는 경우에도 pop전에 waiters 리스트 정렬을 수행하여야 잘못된 정렬값을 가져올 경우를 없앨 수 있습니다. 그러므로 list_sort 를 통해 priority_cond_cmp 사용하여 재정렬을 수행합니다.

**// 원본**
sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);

// 수정본
list_sort(&cond->waiters, priority_cond_cmp, NULL);  // pop하기 전에 재정렬
sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);

테스트해보기

make tests/threads/priority-condvar.result VERBOSE=1

pintos / threads / build 폴더에서 위의 명령어를 통해 priority**-**condvar 테스트 케이스만 실행시킬 수 있습니다. 그러면 결과는 다음과 같이 나옵니다.