[PintOS] 핀토스 뽀개기 - Threads 3 - Priority Scheduling and Synchronization
틀린 내용은 댓글 부탁드립니다.
목표
Pintos에서는 다수의 스레드가 동시에 실행될 수 있기 때문에, 공유 자원(Lock, Semaphore, Condition Variable)을 사용하는 경우 스레드 간 동기화가 필수입니다.
스레드들이 CPU를 점유할 때 우선순위를 부여하여 공정하고 효율적으로 경쟁시키고, 공유 자원(Lock, Semaphore, Condition Variable)을 얻기 위해 기다릴 때에도 우선순위에 따라 스케줄링이 되도록 수정합니다. 즉, 자원을 기다리는 스레드 중에서도 가장 높은 우선순위 스레드가 먼저 CPU를 얻을 수 있도록 합니다.
Lock과 Semaphore를 구현하는 이유
스레드 간 공유 자원 보호
Pintos는 하나의 커널(단일 주소 공간) 안에서 여러 스레드가 실행됩니다.
이때 메모리, 파일 시스템, 디바이스 등 다양한 자원을 공유하는데, 서로의 작업을 방해하지 않도록 보호해야 합니다.
→ 그래서 Lock과 Semaphore를 사용해 **임계 구역(Critical Section)**을 관리합니다.
선점형 스케줄러 환경에서 정확한 동작 보장
Pintos는 선점형(Preemptive) 스케줄러를 사용합니다.
스레드가 실행 도중 강제로 CPU를 빼앗길 수 있기 때문에,
공유 데이터를 읽거나 쓰는 동안 다른 스레드가 개입하지 못하게 막아야 합니다.
우선순위 기반 공정성 보장
만약 Lock/Semaphore 동작이 단순 FIFO라면,
우선순위가 높은 긴급 작업이 리소스를 기다리느라 낭비될 수 있습니다.
이를 막기 위해 waiters 리스트를 우선순위 순서로 정렬하여 항상 가장 높은 우선순위 스레드가 먼저 자원을 얻도록 합니다.
수정 파일
/threads/synch.c
/include/threads/synch.h
구현
쓰레드들이 기다리고 있는 리스트인 waiters가 우선순위로 정렬되어 가장 높은 우선순위의 쓰레드가 공유 자원을 점유하도록 변경합니다.
1. sema_down () 함수
세마포어를 얻으려고 대기할 때, 현재 스레드를 waiters 리스트에 삽입합니다. 삽입 시, 스레드 우선순위에 따라 정렬되도록 list_insert_ordered()를 사용합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/* /threads/synch.c */
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
old_level = intr_disable ();
while (sema->value == 0) {
list_insert_ordered (&sema->waiters, &thread_current ()->elem, cmp_priority, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}
|
쓰레드를 우선순위를 비교해주는 helper 함수인 cmp_priority으로 삽입합니다. cmp_priority() 함수는 thread 구조체의 priority 필드를 비교합니다.
2. sema_up () 함수
waiters 리스트를 항상 우선순위 기준으로 다시 정렬하여, 가장 높은 우선순위 스레드부터 깨워서 CPU를 점유하게 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/* /threads/synch.c */
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
old_level = intr_disable ();
if (!list_empty (&sema->waiters)) {
list_sort (&sema->waiters, cmp_priority, NULL);
thread_unblock (list_entry (list_pop_front (&sema->waiters),
struct thread, elem));
}
sema->value++;
test_max_priority ();
intr_set_level (old_level);
}
|
test_max_priority()는 깨운 스레드가 현재 실행 중인 스레드보다 우선순위가 높으면 CPU를 선점하도록 돕습니다.
3. Condition Variable 수정
Condition Variable(조건 변수)은 스레드가 특정 조건이 만족될 때까지 기다리게 하고, 조건이 만족되면 다시 실행될 수 있도록 하는 동기화 도구입니다. 단독으로 사용되지 않고 반드시 Lock과 함께 사용됩니다.
Lock을 획득한 상태에서 조건을 확인하고 조건이 만족되지 않으면 Lock을 잠시 내려놓고 기다립니다. 다른 스레드가 조건을 만족시키면 Signal을 보내어 대기 중인 스레드를 깨웁니다.
cond_wait() : Condition의 waiters 리스트에도 우선순위 삽입 적용
cond_signal() : 가장 높은 우선순위 스레드부터 깨우기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 |
/* /threads/synch.c */
void
cond_wait (struct condition *cond, struct lock *lock) { struct semaphore_elem waiter; sema_init (&waiter.semaphore, 0); list_insert_ordered (&cond->waiters, &waiter.elem, cmp_sem_priority, NULL); lock_release (lock); sema_down (&waiter.semaphore); lock_acquire (lock); } void cond_signal (struct condition *cond, struct lock *lock UNUSED) { if (!list_empty (&cond->waiters)) { list_sort(&cond->waiters, cmp_sem_priority, NULL); sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore); } } |
결과
Pintos에서 Lock과 Semaphore는 다수의 스레드가 공유 자원을 안전하게 접근하고, 우선순위 기반으로 효율적이고 공정하게 스케줄링하기 위해 필수적입니다.
이번 단계에서는 waiters 리스트를 우선순위로 관리하여 항상 가장 중요한 작업이 먼저 처리되도록 개선했습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs/mlfqs-load-1
FAIL tests/threads/mlfqs/mlfqs-load-60
FAIL tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block
14 of 27 tests failed.
|
GITHUB
깃허브 Merge pull request입니다.
https://github.com/laphayen/pintos-kaist/commit/95e2a01b9fc8e0b1b7152afe8224fe6b89cac67b
Merge pull request #4 from laphayen/PrioritySchedulingSynchronization · laphayen/pintos-kaist@95e2a01
Priority Scheduling and Synchronization
github.com