이번 포스팅은 donate 메커니즘을 pintos 운영체계의 lock에 코드로 적용한 방식을 리뷰해보겠다.
Lock 의 우선순위 donate 적용 과정
1. thread 구조체에 새롭게 무엇이 저장되어야 하는가?
2. 우선순위를 언제, 누가 donate 해야 하고, 어떻게 내 우선순위로 돌아올 수 있는가?
3. lock wait 때문에 어떤 상황이 발생할 수 있고, 그 대처를 어떻게 해주어야 하는가?
4. 이 외의 상황 인지
- 한개의 락을 여러 스레드가 기다리고 있을 수 있다.
- 여러개의 락을 한 스레드가 소유할 수 있다.
- 한 스레드는 단 하나의 락만 기다릴 수 있다.
- 락을 소유한 스레드가 다른 락을 기다릴 수 있다.
1. thread 구조체에 새롭게 무엇이 저장되어야 하는가?
thread.h에 선언한 thread 구조체의 새로운 멤버들을 확인해보자.
struct thread {
tid_t tid;
enum thread_status status;
char name[16];
int priority;
int64_t wake_time;
/* synch member */
struct list donation_list;
//기다리고 있는 쓰레드들 (donate-elem으로 연결)
struct list_elem donate_elem;
struct lock *wait_on_lock;
//기다리고 있는 락 (현재는 블록상태여야 함)
int real_priority;
//초기값 = priority
struct list_elem elem;
donation_list / donate_elem / wait_on_lock / real_priority 총 네 개의 새로운 멤버를 추가했다.
하나씩 그 목적을 살펴보면,
- donation_list는 이 쓰레드가 락을 쥐고 있는 임계영역 점유 쓰레드일 때
해당 락을 대기하고 있는 쓰레드들이 담기는 list이다.
다시 말해, 락을 잡고 있는 쓰레드의 멤버 속 list에 대기하고 있는 쓰레드들이 담기게 된다는 말이다.
이는 대기 중인 쓰레드 중 가장 큰 우선순위를 가지는 쓰레드로부터 우선순위를 기부받기 위해서 이다.
- donate_elem은 위 donation_list에 정렬되는 요소로 사용하기 위해 선언했다.
- wait_on_lock 은 내가 만약 락을 쥘려고 시도했다가 block된 쓰레드일 때,
블록되어 기다리고 있는 lock의 주소를 기억하기 위해 존재한다.
이는 나중에 lock을 쥔 쓰레드가 가지고 있는 donation 리스트에서
lock을 내려놓을 때 해당 lock을 기다리는 쓰레드들의 정보를 지우기 위해 사용하기도 하고
nest donation 상황에서 특정 쓰레드가 lock을 기억하고 있는 쓰레드인지 확인하기 위해 사용하기도 한다.
- real_priority 는 쓰레드의 실제 우선순위를 기억하도록 하기 위해서 사용한다.
초기 값은 priority와 동일한 값을 가지지만,
만약 우선순위를 증여받게 되면 real_priority에 기억된 실제 우선순위는 그대로 두고
쓰레드 스케줄링 되는 priority만 변경시킨다.
따라서 Thread는 lock을 내려 놓으면서 donation list에 기다리는 쓰레드들의 정보를 하나씩 지워가고,
전부 다 지워져서 기다리는 쓰레드들을 담는 donation 리스트가 비워진다면 다시 real_priority로 priority를 돌려놓을 수 있다.
2. 우선순위를 언제, 누가 donate 해야 하고, 어떻게 내 우선순위로 돌아올 수 있는가?
우선 순위를 donate해야 하는 상황은 소유된 lock을 다른 쓰레드가 획득하려는 순간 발생한다.
따라서 block될 상황에서 lock_acquire() 함수를 호출한 쓰레드에서
lock을 통해 주인에게 priority donation을 할지를 판단하는 함수를 호출하게 된다.
lock acquire() 변경 < 이미 획득 된 lock에 접근하려는 쓰레드 시점 >
void
lock_acquire (struct lock *lock) {
struct thread *curr = thread_current ();
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
enum intr_level old_level;
old_level = intr_disable ();
if (lock->semaphore.value == 0){
curr->wait_on_lock = lock;
list_insert_ordered(&lock->holder->donation_list,&curr->donate_elem,thread_more_lock_priority,NULL);
priority_donation(lock->holder , curr);
}
intr_set_level (old_level);
sema_down (&lock->semaphore);
curr->wait_on_lock = NULL;
lock->holder = thread_current ();
}
donate가 구현되기 전 코드에서는 이미 락의 주인이 있어서 통제될 쓰레드는 lock을 획득하려고 시도할 때,
sema_down() 구간에서 block되는 방식이었다.
그 과정에서 우리가 선언한 쓰레드의 구조체 멤버를 이용하여 donate를 적용하기 위해서 전조 과정들을 끼워 넣었다.
block될 쓰레드는 <if문> 안으로 들어오게 되고,
현재 블록된 쓰레드는 블록된 락의 주소를 기억하도록 한다.
그 후 lock의 주인의 donation 리스트로 우선순위 순으로 정렬 삽입되며
마지막으로 priority_donation을 진행한다.
여기서 오해하지 말아야 할 것이 있는데,
이 if문은 block되어 CPU로부터 격리되는 작업을 수행하는 것이 아니라,
sema_down에서 어차피 블록될 예정인 현재 쓰레드를 미리 if문으로 확인하여
lock의 주인과 현재 쓰레드의 멤버 변수에 해당 상황을 저장하고, 우선순위 donate를 수행시키는 과정이 추가된 것뿐이다.
실제로 현 쓰레드가 ready_list로부터 격리되어 sema_list로 들어가는 것은 sema_down의 while문까지 가서 진행된다.
+ priority_donation() 추가
이 함수는 락 걸린 상황에서 우선순위 기부를 진행하는 코드이다.
void priority_donation(struct thread *lock_holder, struct thread *donater_thread){
refresh_priority(lock_holder);
if (lock_holder->wait_on_lock != NULL){
struct thread *high_holder = lock_holder->wait_on_lock->holder;
priority_donation(high_holder,lock_holder);
}
}
첫번째 인자로 lock의 주인 쓰레드를 , 두번째 인자로 기부하는 thread를 집어 넣는다.
refresh_priority()를 통해 lock의 주인에게 priority를 donate 한다.
if문 밑의 코드는 nest donation 상황을 고려한 예외 처리 이다.
+ refresh_priority()
/* <우선순위 갱신 상황>
* 1. 락을 보유중인 쓰레드가 set_priority에 의해 real_priority가 변경되었을 때.
* 2. 락을 풀면서 기증받은 쓰레드가 기다리지 않게 되었을 때.
* 3. 락을 아예 소지하고 있지 않아서 real_priority로 되돌아와야 할 때.
*
*/
void refresh_priority(struct thread *refreshed_thread){
if(list_empty(&refreshed_thread->donation_list)){
refreshed_thread->priority = refreshed_thread->real_priority;
return;
}
struct thread *priority_thread = list_entry(list_begin(&refreshed_thread->donation_list),
struct thread,donate_elem);
if (refreshed_thread->real_priority >= priority_thread->priority) {
refreshed_thread->priority = refreshed_thread->real_priority;
}
else{
refreshed_thread->priority = priority_thread->priority;
}
}
인자로 들어온 쓰레드의 스케줄링하는 우선순위를 '실제 우선순위(real_priority)' vs '기부 리스트에서 가장 높은 쓰레드의 우선순위'
로 비교하여 더 높은 우선순위를 적용하는 함수이다.
리스트가 비었을 때의 예외처리 수행을 통해, 비어있는 쓰레드의 begin을 참조하여 에러가 나는 것을 방지했다.
lock release() 변경 < lock을 소유한 쓰레드가 lock의 소유권을 release 하는 시점 >
void
lock_release (struct lock *lock) {
struct thread *curr = thread_current();
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
lock->holder = NULL;
remove_with_lock(lock);
refresh_priority(curr);
sema_up (&lock->semaphore);
check_running_priority();
}
lock_acquire() 함수와 마찬가지로 lock_release()할 때도 donate를 제어해주기 위해 함수들이 추가된다.
remove_with_lock()은 현재 lock을 가지고 있는 curr 쓰레드가 lock을 내려놓기 전에
자기 구조체 멤버로 저장되어있는 donation list 속 현재 락을 기다리고 있는 쓰레드들의 정보를 삭제하는 것을 수행한다.
이제 이 스레드는 이 lock의 소유권을 내려놓기 때문에 더이상 이 lock과 관련이 없어서 삭제하는 것이다.
이 삭제를 수행하면 이 lock을 기다리는 스레드들은 donation list에서 사라진다.
(이때 조심해야 할 점은, 여기 리스트에서 제거한다고 block된 스레드들이 ready로 가는 것이 아니라, 실제로는 semaphore list에 block 된 상태로 저장되어 있다.)
donation list가 갱신되면 다시 refresh_priority() 함수를 통해, donation_list가 비었다면 원래 우선순위로 돌아오고
그게 아니라면 남은 스레드 중의 우선순위로 기부받을지를 정한다.
+ remove_with_lock() 추가
/* 해당 락을 풀기 전에 해당 락을 기다리는 쓰레드들을 기억하는 리스트에서 해당 락을 기다리는 쓰레드들 제거*/
void remove_with_lock(struct lock *lock) {
struct thread *curr = thread_current ();
if (list_empty(&curr->donation_list)){
return;
}
struct list_elem *wait_elem;
for(wait_elem = list_begin(&curr->donation_list); wait_elem != list_end(&curr->donation_list);){
struct thread *thread_wait = list_entry(wait_elem,struct thread,donate_elem);
if(thread_wait->wait_on_lock == lock){
wait_elem = list_remove(wait_elem);
}
else{
wait_elem = wait_elem->next;
}
}
}
위에서 얘기했던 remove_with_lock() 함수이다.
현재 락을 내려놓는 쓰레드의 donation_list를 완전 탐색하여
인자로 받은 현재 lock을 기다리는 thread를 list에서 삭제한다.
3. lock wait 때문에 어떤 상황이 발생할 수 있고, 그 대처를 어떻게 해주어야 하는가?
1. nest donation
nest donation은 서로 다른 lock 들로 줄줄이 release가 되기를 기다리고 있는 상황을 말한다.
+ priority_donation() 의 재귀 방식
이 함수를 잘 들여다 보면 재귀 형식으로 코드가 진행되는 걸 확인할 수 있다.
이 재귀는 nest donating 의 상황일 때를 해결 하기 위해서 <if문> 을 통해 lock의 주인에게도 기다리는 lock이 있는지 확인한다.
서로가 chain처럼 줄줄이 락을 들고 대기하고 있는 상황들은 맨 앞에 block 되지 않은 쓰레드에게 donate를 전달해야 한다.
따라서 코드에서는 donate를 전달받은 쓰레드가 wait_on_lock을 통해 대기하고 있는지 확인하고 인자를 적절히 바꿔 donation 함수를 재 실행 하게 했다.
2. donation 받은 락 소유 쓰레드가 thread_set_priority() 로 우선순위가 강제 변경된 경우
++ thread_set_priority() 함수 변경
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
struct thread *curr = thread_current();
curr->priority = new_priority;
curr->real_priority = new_priority;
refresh_priority(curr);
check_running_priority();
}
이 priority-donation 방식을 사용하면 thread_set_priority() 코드를 변경해야 했다.
이때 고민해봐야 할 포인트는 thread_set_priority()를 실행하여 우선순위를 증여받은 쓰레드의 우선순위를 변동시키려 할 때이다.
만약 이 함수로 현재 스레드의 priority를 변경하려 한다면, 그 의도는 이 스레드의 실제 우선순위를 변경하려는 것이다.
따라서 현재 priority가 기부받은 priority라면 여기서 변경되더라도 즉시 refresh를 통해 기부를 다시 받아야 하고,
의도에 맞게 real_priority도 변경해 주어야 한다.
++ init_thread() 함수 변경
/* Does basic initialization of T as a blocked thread named
NAME. */
static void
init_thread (struct thread *t, const char *name, int priority) {
ASSERT (t != NULL);
ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
ASSERT (name != NULL);
memset (t, 0, sizeof *t);
t->status = THREAD_BLOCKED;
strlcpy (t->name, name, sizeof t->name);
t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
t->priority = priority;
t->magic = THREAD_MAGIC;
t->real_priority = priority;
list_init(&t->donation_list);
}
그리고 한가지 유념할 점은 thread 구조체에 새로운 멤버를 추가해주었기 때문에
init_thread() 함수에서 real_priority와 donation_list를 초기화 해주어야 한다.
'Jungle' 카테고리의 다른 글
| [TIL] DP 알고리즘적 접근법 (1) | 2023.12.04 |
|---|---|
| [TIL] pintos - MLFQ 스케줄링 구현하기 - 트러블 슈팅 (0) | 2023.12.02 |
| [TIL] pintOS : synchronization 우선순위 스케줄링 구현 (1) (1) | 2023.11.29 |
| [TIL] pintos 프로젝트 - 쓰레드 우선순위 문맥 전환 (1) | 2023.11.29 |
| [TIL] 쓰레드 sleep 시 CPU 효율성 개선하기 - sleep_list 추가 (2) | 2023.11.27 |