Project 1 에서 구현해야 할 것
1. Alarm Clock 구현 완료
2. Priority Scheduling <- 여기 할 차례!
3. Advanced Scheduler
2. Priority Scheduling
Scheduling 은 Ready 상태에 있는 Thread 들의 순서를 관리하여
가장 높은 Priority 를 가진 Thread 가 Running 상태가 될 수 있도록 만들어 주는 것이다
🐣 운영체제 CH07 - CPU Scheduling 은 한 프로세스가 CPU 를 사용하는 동안 다른 프로세스가 대기하는 상황에서
CPU 를 효율적으로 활용할 수 있도록 우선순위를 정하고, 프로세스들을 적절하게 배치하는 기술이다
Scheduling 현재 방식
Running 상태로 될 수 있는 상태는 Ready 밖에 없으므로, Ready List 에 Thread 를 넣는 함수를 찾아보면
thread_unblock 과 thread_yield 에서, ready_list 에 Push Back (FIFO) 방식으로 Scheduling 하고 있음을 알 수 있다
1) thread_unblock (현재 방식 list_push_back)
/* Path - threads/thread.c */
void
thread_unblock (struct thread *t)
{
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
list_push_back (&ready_list, &t->elem);
t->status = THREAD_READY;
intr_set_level (old_level);
}2) thread_yield (현재 방식 list_push_back)
// path - threads/thread.c
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level; /* 인터럽트 비활성화 */
ASSERT (!intr_context ());
old_level = intr_disable ();
if (curr != idle_thread)
list_push_back (&ready_list, &curr->elem);
do_schedule (THREAD_READY); /* 컨텍스트 스위칭 */
intr_set_level (old_level); /* 인터럽트 원상복구 */
}
Ready List 에서 Thread 를 꺼낼 때는, Running Thread 가 CPU 를 양보해서 새로운 Running Thread 를 고르는 순간이다
🐣 Running Thread 가 CPU 를 양보하면, Ready List 에서 Thread 를 꺼내 Running 상태로 돌려주니까 🐣
Running 상태에서 변경될 수 있는 상태는 1) yield to Ready 2) sleep to Blocked 3) exit to Dying 세 가지가 있다
세 가지 함수 (thread/thread.c) 를 보면, 세 개 모두 do_schedule() 함수를 호출하고 끝나고
do_schedule() 함수는 schedule() 함수를 호출하고 끝난다
/* Path - threads/thread.c */
static void
do_schedule(int status) {
ASSERT (intr_get_level () == INTR_OFF);
ASSERT (thread_current()->status == THREAD_RUNNING);
while (!list_empty (&destruction_req)) {
struct thread *victim =
list_entry (list_pop_front (&destruction_req), struct thread, elem);
palloc_free_page(victim);
}
thread_current ()->status = status;
schedule ();
}
static void
schedule (void) {
struct thread *curr = running_thread ();
struct thread *next = next_thread_to_run (); /* CPU 의 점유권을 받는 함수 */
ASSERT (intr_get_level () == INTR_OFF); /* INTR OFF 상태 확인 */
ASSERT (curr->status != THREAD_RUNNING); /* RUNNING 상태 아님 확인 */
ASSERT (is_thread (next)); /* next 가 올바른 Thread 인지 검증 */
/* Mark us as running. */
next->status = THREAD_RUNNING;
/* Start new time slice. */
thread_ticks = 0;
#ifdef USERPROG
/* Activate the new address space. */
process_activate (next);
#endif
if (curr != next) {
/* If the thread we switched from is dying, destroy its struct
thread. This must happen late so that thread_exit() doesn't
pull out the rug under itself.
We just queuing the page free reqeust here because the page is
currently used by the stack.
The real destruction logic will be called at the beginning of the
schedule(). */
if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
ASSERT (curr != next);
list_push_back (&destruction_req, &curr->elem);
}
/* Before switching the thread, we first save the information
* of current running. */
thread_launch (next);
}
}
🐣 참고하고 있는 블로그에서는 *prev 로 switch_threads 를 해주는데, 우리 코드에는 process_Activate() 로 진행하는 듯 하다
thread_launch() 를 찾아가 보니 어셈블리어로 특정 상태를 저장하고 복구하는 일을 수행하는 컨텍스트가 있었다
그리고 do_schedule() 에서는 list_pop_front 로 꺼내고, schedule() 에서는 list_push_back 으로 넣는
전형적인 FIFO 방식의 입출력을 진행한다는 사실을 알 수 있다
그리고 왜 변수 이름이 victim 인지 궁금해져서 찾아봤는데
desctruction_req 리스트에서 가장 앞에 있는 Thread 를 꺼내고 palloc 으로 해제하여 메모리를 반환하기 때문에
메모리 반환의 "희생자" 가 되어 리스트에서 제거되는 의미라고, victim 으로 명명했다고 한다 🐣
그리고 next_thread_to_run() 으로 CPU 의 점유권을 넘겨주는데 이 함수는 이렇게 생겼다
이 칭구도 list_pop_front() 를 쓰고 있다
/* Path - threads/thread.c */
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list))
return idle_thread;
else
return list_entry (list_pop_front (&ready_list), struct thread, elem);
}
현재 PintOS 동작 방식을 정리하자면, Ready List 에 Thread 를 넣고 뺄 때
Thread 간의 우선 순위 없이 Push 는 맨 뒤에, Pop 은 맨 앞에서 하고 있음을 알 수 있다
Priority Scheduling 구현
List 를 정렬하기 위해서는 1) 넣을 때 정렬하는 방식과 2) 뺄 때 정렬하는 방식이 있는데
마침 어제 팀 스터디를 진행할 때 ㅈㅇ이가 넣을 때 정렬하는 방식이 더 효율적이라고 설명해줬다
하나의 리스트를 한 군데에서 사용한다면 넣을 떄나 뺄 때나 오버헤드는 똑같지만,
하나의 리스트를 다섯 군데에서 사용한다고 가정하면, 다섯 군데에서 정렬하고 출력하는 것보다
처음 만들 때 한 번 정렬하는 것이 훨씬 더 효율적인 방식이라고, 넣을 때 정렬을 추천했다
그래서 우리도 ready_list 에 Push 할 때 Priority 순서에 맞추어 Push 하는 방식으로 진행할 것이다
thread_create() 함수 안에서 thread_unblock() 함수를 호출하고 있다,
그래서 thread_unblock() 함수 안에서 list_push_back() 을 다른 함수로 대체해준다
lib/kernel/list.c 를 참고하여 list_insert_ordered() 함수를 이용하기로 했다
그리고 list_insert_ordered() 를 활용하기 위해 thread_compare_priority 함수도 만들어줬다
/* Path - threads/thread.c */
/* Thread 의 Priority 를 비교하는 함수 */
bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) {
return list_entry (l, struct thread, elem)->priority
> list_entry(s, struct thread, elem)->priority;
}그렇게 변경한 thread_unblock() 과 thread_yield() 함수
/* Path - threads/thread.c */
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
// list_push_back (&ready_list, &t->elem); /* ready_list 에 Thread 추가 */
/* thread_compare_priority 를 활용하여 우선순위 비교하고 ready_list 에 추가하기 */
list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0);
t->status = THREAD_READY;
intr_set_level (old_level);
}
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable ();
if (curr != idle_thread)
// list_push_back (&ready_list, &curr->elem); /* ready_list 에 Thread 추가 */
/* thread_compare_priority 를 활용하여 우선순위 비교하고 ready_list 에 추가하기 */
list_insert_ordered (&ready_list, &curr->elem, thread_compare_priority, 0);
do_schedule (THREAD_READY);
intr_set_level (old_level);
}기본적인 Priority Scheduling 을 완료한 이후 중간 점검 결과,
Alarm Clock 하고 나서의 결과는 안 찍어봐서 비교는 못 하겠는데, 지금 단계에서 맞는 결과라고 한다
2. Lock, Semaphore, Condition Variable
이제, 찍먹스터디에서 공부했던 Lock, Semaphore, Condition Variable 을 활용할 차례다
* Lock 공부 자료
* Semaphore 공부 자료
* Condition Variable 공부 자료
이 동기화 도구들은 synch.* 에 구현되어 있다
/* Path - threads/synch.h */
struct semaphore {
unsigned value; /* Current value. */
struct list waiters; /* List of waiting threads. */
};
struct lock {
struct thread *holder; /* Thread holding lock (for debugging). */
struct semaphore semaphore; /* Binary semaphore controlling access. */
};
struct condition {
struct list waiters; /* List of waiting threads. */
};Semaphore 는 공유 자원의 개수를 나타내는 Value, 공유 자원을 사용을 대기하는 Waiter List 를 가지고 있다
Lock 은 사용 가능/ 사용 중 두 가지 상태만 나타낼 수 있으므로 Binary Semaphore 로 구현되어 있고,
Lock 을 가지고 있는 Thread 정보와 Semaphore 를 멤버로 가지고 있다
Condition 은 Condition Variables 가 만족하기를 기다리는 Waiters 리스트를 가지고 있다
Semaphore
Semaphore 는 공유 가능한 자원의 개수이다
Semaphore 가 양수이면 그 숫자는 남아 있는 공유 자원의 개수이고 자원을 이용할 수 있다
0 인 경우는 자원이 모두 사용 중인 상태이므로 요청을 하려면 대기해야 한다
🐣 음수이면 자원을 이용하려고 대기하는 Thread 들의 개수라고 운영체제 책 CH31 P397 에 나와있는데
ChatGPT 가 말하기로는, 일반적으로 Semaphore 의 값은 자원이 남아 있는지 여부를 나타내기 때문에
음수가 되는 경우는 없고, 대기열에 있는 Thread 의 수는 Semaphore 내부적으로 관리된다고 한다
일반적으로는 0 이상의 값만 사용하니, 그렇구나 이해하고 알고 있으면 도움이 될 듯 하다 🐣
Semaphore Up/ Down 현재 방식
Semaphore Up/ Down 도 list_push_back()/ list_pop_front() 방식을 사용하고 있음을 알 수 있다
/* Path - threads/synch.c */
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); /* Semaphore 유효성 검사 */
ASSERT (!intr_context ()); /* 인터럽트 컨텍스트에서 블로킹 호출 방지 */
old_level = intr_disable (); /* 인터럽트 비활성화 */
/* 공유 자원이 없는 경우 Waiter Push Back 하고 Thread_block */
while (sema->value == 0) {
list_push_back (&sema->waiters, &thread_current ()->elem);
thread_block (); /* 자원이 반환될 때까지 대기 */
}
sema->value--; /* 공유 자원이 있는 경우 Semaphore -1 */
intr_set_level (old_level); /* 인터럽트 원상복구 */
}
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); /* Semaphore 유효성 검사 */
old_level = intr_disable (); /* 인터럽트 비활성화 */
/* Waiter 가 있다면 첫번째 Thread 를 thread_unblock 으로 깨워서
실행 대기 상태로 전환한다, thread_Unblock 은 pop Front 방식 */
if (!list_empty (&sema->waiters))
thread_unblock (list_entry (list_pop_front (&sema->waiters),
struct thread, elem));
sema->value++; /* 자원 사용을 마치고 반환하므로 Semaphore +1 */
intr_set_level (old_level); /* 인터럽트 원상복구 */
}
Semaphore Up/ Down 개선 구현하기
1) sema_down()
list_push_back 을 thread_compare_priority 를 이용하여 정렬되도록 한다
/* Path - threads/synch.c */
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); /* Semaphore 유효성 검사 */
ASSERT (!intr_context ()); /* 인터럽트 컨텍스트에서 블로킹 호출 방지 */
old_level = intr_disable (); /* 인터럽트 비활성화 */
/* 공유 자원이 없는 경우 Waiter Push Back 하고 Thread_block */
while (sema->value == 0) {
// list_push_back (&sema->waiters, &thread_current ()->elem);
list_insert_ordered(&sema->waiters, &thread_current()->elem,
thread_compare_priority, 0);
thread_block (); /* 자원이 반환될 때까지 대기 */
}
sema->value--; /* 공유 자원이 있는 경우 Semaphore -1 */
intr_set_level (old_level); /* 인터럽트 원상복구 */
}2) sema_up()
sema_up 은 sema_down 과 다르게, waiters 리스트에 있는 동안 우선순위의 변경이 생겼을 수도 있으므로
waiters 리스트는 list_sort 를 사용하여 내림차순으로 정렬하고, Unblock 된 Thread 가 Running Thread 보다
우선순위가 높을 수 있으므로 preempt_priority() 를 호출하여 CPU 선점이 진행될 수 있게 한다
/* Path - threads/synch.c */
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); /* Semaphore 유효성 검사 */
old_level = intr_disable (); /* 인터럽트 비활성화 */
/* Waiter 가 있다면 첫번째 Thread 를 thread_unblock 으로 깨워서
실행 대기 상태로 전환한다, thread_Unblock 은 pop Front 방식 */
if (!list_empty (&sema->waiters)) {
list_sort(&sema->waiters, thread_compare_priority, 0); /* 정렬 */
thread_unblock (list_entry (list_pop_front (&sema->waiters),
struct thread, elem));
}
sema->value++; /* 자원 사용을 마치고 반환하므로 Semaphore +1 */
preempt_priority(); /* 우선순위 비교하여 CPU 선점 결정 */
intr_set_level (old_level); /* 인터럽트 원상복구 */
}Lock
Lock 은 Acquire, Release 모두 sema_up/ down 이 처리해줘서 수정할 내용은 없었다
그래도 어떤 식으로 함수가 구성되어 있는지는 확인해 봤다
/* Path - threads/synch.c */
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
ASSERT (!intr_context ()); /* 인터럽트 컨텍스트가 아닌지 확인 */
/* 현재 Thread 가 이미 이 Lock 을 가지고 있지 않은지 확인 */
ASSERT (!lock_held_by_current_thread (lock));
/* Semaphore 를 감소시키며 Lock 을 획득하려 시도 */
sema_down (&lock->semaphore);
/* Lock 획득한 후 현재 Thread 를 Lock 소유자로 설정 */
lock->holder = thread_current ();
}
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
/* 현재 Thread 가 이미 이 Lock 을 가지고 있는지 확인 */
/* 다른 함수들과 달리 ! 가 없음, Lock 을 가지고 있어야 Release 할 수 있다 */
ASSERT (lock_held_by_current_thread (lock));
lock->holder = NULL; /* Lock 이 가지고 있는 Thread 해제 */
sema_up (&lock->semaphore);
}Semaphore 까지의 진행 결과
여기까지 했을 때, tests/threads/priority-sema 가 PASS 되어 Fail 수가 하나 줄었다
Condition Variables
Condition Variables 는 cond_wait() 와 cond_signal() 을 개선해야 한다
Condition Variables 현재 방식
cond_wait() 와 cond_signal() 모두 list_push_back() 과 list_pop_front() 를 이용한다
그래서 이걸 list_insert_ordered 로 바꿔야 하는데, thread 가 아닌 semaphore_elem.elem 을 받아오기 때문에
thread_compare_priority 함수 대신 semaphore_elem 구조체 안의 semaphore 구조체 안의
waiters 리스트 맨 앞 thread 끼리 Priority 를 비교하는 함수를 만들어야 한다
/* Path - threads/synch.c */
/* 조건 변수에서 특정 조건이 만족될 때까지 Thread 를 대기시키는 함수 */
void
cond_wait (struct condition *cond, struct lock *lock) {
struct semaphore_elem waiter; /* Semaphore Waiter List */
ASSERT (cond != NULL); /* 컨디션 유효성 검사 */
ASSERT (lock != NULL); /* Lock 유효성 검사 */
ASSERT (!intr_context ()); /* 인터럽트 컨텍스트 블로킹 방지 */
ASSERT (lock_held_by_current_thread (lock));
sema_init (&waiter.semaphore, 0); /* 대기 중인 Thread Sema 0 으로 초기화 */
list_push_back (&cond->waiters, &waiter.elem); /* 조건 변수 대기 리스트에 Waiter 추가 */
lock_release (lock); /* 다른 Thread 가 작업을 진행할 수 있도록 Lock 해제 (후 대기 상태로 변경) */
sema_down (&waiter.semaphore); /* Sema 가 0이면 Blocking(대기), 0보다 커지면 깨어남 */
lock_acquire (lock); /* Sema 가 1로 증가하면, Lock 다시 획득 */
}
/* 조건 변수에서 대기 중인 Thread 를 깨워 Ready 상태로 만드는 함수 */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
ASSERT (cond != NULL);
ASSERT (lock != NULL);
ASSERT (!intr_context ());
/* 현재 Thread 가 Lock Holder 인지 확인 */
ASSERT (lock_held_by_current_thread (lock));
/* 대기 중인 Thread Waiter 가 있다면 Waiter 의 Semaphore +1 */
/* list_entry(LIST_ELEM, STRUCT, MEMBER)*/
if (!list_empty (&cond->waiters))
sema_up (&list_entry (list_pop_front (&cond->waiters),
struct semaphore_elem, elem)->semaphore);
}Semaphore 구조체 안의 Waiters 리스트 맨 앞 thread 끼리 Priority 를 비교하는 함수
/* Semaphore 의 Waiters list Thread Priority 비교하는 함수 */
bool
sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED) {
/* list_entry 매크로를 통해 struct semaphore_elem 구조체에 접근한다 */
struct semaphore_elem *l_sema = list_entry(l, struct semaphore_elem, elem);
struct semaphore_elem *s_sema = list_entry(s, struct semaphore_elem, elem);
/* 두 Semaphore 의 대기 리스트 Waiters 참조한다 */
struct list *waiters_l_sema = &(l_sema->semaphore.waiters);
struct list *waiters_s_sema = &(s_sema->semaphore.waiters);
/* list_begin 으로 첫 번째 요소를 반환하고, list_entry 로 struct thread 의 포인터를 얻어서
Priority 필드에 접근할 수 있다, 그래서 두 개의 세마포어 대기자 리스트에서 가장 높은 우선순위 Thread 비교 */
return list_entry (list_begin (waiters_l_sema), struct thread, elem) -> priority
> list_entry (list_begin (waiters_s_sema), struct thread, elem) -> priority;
}Condition Variables 개선 구현하기
list_push_back() 대신 sema_compare_priority 를 활용한 list_insert_ordered 를 활용한다
/* Path - threads/synch.c */
/* 조건 변수에서 특정 조건이 만족될 때까지 Thread 를 대기시키는 함수 */
void
cond_wait (struct condition *cond, struct lock *lock) {
struct semaphore_elem waiter; /* Semaphore Waiter List */
ASSERT (cond != NULL); /* 컨디션 유효성 검사 */
ASSERT (lock != NULL); /* Lock 유효성 검사 */
ASSERT (!intr_context ()); /* 인터럽트 컨텍스트 블로킹 방지 */
ASSERT (lock_held_by_current_thread (lock));
sema_init (&waiter.semaphore, 0); /* 대기 중인 Thread Sema 0 으로 초기화 */
// list_push_back (&cond->waiters, &waiter.elem); /* 조건 변수 대기 리스트에 Waiter 추가 */
/* sema_compare_priority 를 활용하여 Waiter 를 cond->waiters 리스트에 우선순위에 맞게 추가*/
list_insert_ordered(&cond->waiters, &waiter.elem, sema_compare_priority, 0);
lock_release (lock); /* 다른 Thread 가 작업을 진행할 수 있도록 Lock 해제 (후 대기 상태로 변경) */
sema_down (&waiter.semaphore); /* Sema 가 0이면 Blocking (대기), 0보다 커지면 깨어남 */
lock_acquire (lock); /* Sema 가 1로 증가하면, Lock 다시 획득 */
}
/* 조건 변수에서 대기 중인 Thread 를 깨워 Ready 상태로 만드는 함수 */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
ASSERT (cond != NULL);
ASSERT (lock != NULL);
ASSERT (!intr_context ());
/* 현재 Thread 가 Lock Holder 인지 확인 */
ASSERT (lock_held_by_current_thread (lock));
/* 대기 중인 Thread Waiter 가 있다면 Waiter 의 Semaphore +1 */
/* list_entry(LIST_ELEM, STRUCT, MEMBER)*/
if (!list_empty (&cond->waiters)){
/* Wait 도중 Priority 가 바뀔 수 있으니 list_sort 로 정렬*/
list_sort (&cond->waiters, sema_compare_priority, 0);
sema_up (&list_entry (list_pop_front (&cond->waiters),
struct semaphore_elem, elem)->semaphore);
}
}동기화 도구까지 적용했을 때의 결과
짜잔 - 🐣
tests/threads/priority-condvar 까지 PASS 했다!
'크래프톤정글 > PintOS' 카테고리의 다른 글
| [정글] PintOS Project2 #1 Passing the Arguments and Creating a Thread (2) | 2024.11.18 |
|---|---|
| [정글] PintOS Project1 #3 Priority Scheduling 2/2 (3) | 2024.11.11 |
| [정글] PintOS Project1 #1 Alarm Clock (7) | 2024.11.07 |
| [정글] 정글 PintOS 주차 퀴즈 (0) | 2024.11.05 |
| [정글] PintOS - Gitbook (2) | 2024.11.01 |