alarm 테스트는 모두 pass했다!
이제 priority 테스트를 통과시켜보자.
구현 요구 사항
ready_list에 있는 스레드를 스케줄하여 running 상태로 만들 때 우선 순위에 맞게 스케줄링되도록 만들어야 한다. schedule()함수를 보면 항상 ready_list의 가장 앞에 있는 스레드가 실행되기 때문에 ready_list에 스레드를 넣을 때 마다 priority순서로 정렬되게 만들어야 한다.
그러면 저 세 가지 경로로 ready_list에 스레드를 넣는 부분을 변경해야 한다. alarm-clock에서 3번을 해결했으니 priority-scheduling에서 2번을 해결하면 된다!
1. 스케줄링하는 부분 이해하기
나는 alarm-clock에서 스레드를 wake할 때 sleep_list의 가장 앞에서부터 하나씩 꺼내서 레디 리스트에 넣었던 것처럼 priority-scheduling에서도 스레드를 schedule할 때 ready_list의 가장 앞에서부터 하나씩 꺼내서 cpu에 할당하고 있을 것이라고 예상하고 그 부분을 찾아봤다.
schedule()함수에서부터 쭉 따라가다 보니 next_thread_to_run()함수에 ready_list에서 다음에 스케줄될 스레드를 어떻게 꺼내는지 구현되어 있었다. schedule()함수 안에서 next_thread_to_run()으로 레디큐의 가장 앞에 있는 스레드를 꺼낸 후, thread_launch()의 인자로 스레드를 넘겨주어 컨텍스트 스위칭한다.
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list)) //ready_list가 비어있다면
return idle_thread; //idle_thread를 반환
else //레디큐가 비어있지 않다면
return list_entry (list_pop_front (&ready_list), struct thread, elem); //ready_list의 가장 앞에 위치하는 스레드를 반환
}
static void
schedule (void) {
struct thread *curr = running_thread ();
struct thread *next = next_thread_to_run (); //레디큐의 가장 앞에 있는 스레드 가져오기
ASSERT (intr_get_level () == INTR_OFF);
ASSERT (curr->status != THREAD_RUNNING);
ASSERT (is_thread (next));
/* 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 (curr && curr->status == THREAD_DYING && curr != initial_thread) {
ASSERT (curr != next);
list_push_back (&destruction_req, &curr->elem);
}
thread_launch (next); //스레드를 next로 컨텍스트 스위치
}
}
2. ready_list에 스레드를 삽입하는 부분 찾기
찾아봤는데 alarm-clock때 내가 구현한 thread_wake()함수 말고는 스레드를 ready_list에 삽입하는 부분이 없다. (thread_wake()내부에서 thread_unblock()을 할 때 ready_list에 스레드를 삽입한다.)
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
struct thread* now_thread = thread_current();
ASSERT (is_thread (t));
old_level = intr_disable (); //인터럽트 비활성화
ASSERT (t->status == THREAD_BLOCKED); //스레드가 block 상태이면 이후 코드 실행
list_insert_ordered(&ready_list, &t->elem, list_high_priority, NULL); //ready_list에 우선순위가 높은 순서대로 넣기
t->status = THREAD_READY; //스레드를 THREAD_READY 상태로 바꿈
if(!list_empty(&ready_list) && is_higher_priority(now_thread) && now_thread != idle_thread){ //ready_list가 비어있지 않고 현재 스레드의 우선순위가 ready_list의 맨 앞에 있는 스레드의 우선순위보다 더 높으면
thread_yield(); //문맥 교환
}
intr_set_level (old_level); //인터럽트 다시 활성화
}
3. priority-sema 테스트 pass하기
테스트 코드를 먼저 보자.
우선순위가 27, 26, …, 21, 30, 29, 28인 스레드 10개를 새로 생성했다.
- 우선순위를 21부터 30까지 차례로 만들면 되지 굳이 27부터 만든 이유?
- ready_list에 10개의 스레드들을 우선순위가 높은 순서대로 삽입하지 않았는데도 꺼낼 때 우선순위가 높은 스레드부터 나오는지 테스트하기 위함이다.
- 엄밀히 말하면 ready_list에 넣을 때 우선순위가 높은 순서대로 insert되는지 확인하기 위함
- 참고로 thread_create()는 새로운 스레드를 생성하고 나서 내부적으로 thread_unblock()을 호출하여 새롭게 생성된 스레드를 ready_list에 넣는다.
- 이 부분을 공부하면서 깨달은 건데 thread_unblock()은 단지 sleep_list에서 자고 있는 스레드를 깨워서 ready_list로 옮기는 역할만 하는 게 아니다. 스레드를 ready_list에 삽입하고싶을 때 호출하는, 범용적으로 쓰이는 함수이다!
- thread_create()에서도 새로운 스레드를 하나 생성하고 나서 thread_unblock()을 호출해서 생성한 스레드를 ready_list에 삽입한다.
- sema_up()에서도 세마포어 변수를 1 증가시키기 전에 thread_unblock()을 호출해서 sema→waiters의 제일 앞에 위치한 스레드를 ready_list에 삽입한다.
- 테스트 코드 실행 순서를 정리하면
- 첫 번째 for문을 돌면서 thread_create()로 10개의 스레드를 만들면 그 스레드들은 내부 로직으로 sema_down()을 한다. 세마포어 변수가 0인 상태에서 sema_down()을 하면 block이 걸려서 스레드가 모두 sema→waiters로 들어간다.
- 두 번째 for문을 돌면서 sema_up()으로 세마포어 변수를 1 증가시키고 sema→waiters에 기다리고 있는 10개의 스레드들 중 가장 앞에 있는 스레드를 unblock하여 ready_list에 올린다.
- ready_list에 10개의 스레드들을 우선순위가 높은 순서대로 삽입하지 않았는데도 꺼낼 때 우선순위가 높은 스레드부터 나오는지 테스트하기 위함이다.
void
test_priority_sema (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
sema_init (&sema, 0);//세마포어 변수를 0으로 초기화
thread_set_priority (PRI_MIN); //현재 스레드의 우선순위를 가장 낮은 값으로 초기화
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 3) % 10 - 1; //우선순위를 30부터 21까지로 설정
char name[16];
snprintf (name, sizeof name, "priority %d", priority); //배열 name에 "priority %d"라는 데이터가 저장됨
thread_create (name, priority, priority_sema_thread, NULL); //이름을 "priority %d"으로, 우선순위를 27~18로 설정, priority_sema_thread는 왜 넘겨주는 건지 모르겠음 아무튼 해당 우선순위를 가진 스레드를 생성함
}
for (i = 0; i < 10; i++)
{
sema_up (&sema); //sema->waiters에 스레드가 기다리고 있으면 하나 꺼내서 unblock 하고 세마포어 변수를 1 증가시킴
msg ("Back in main thread.");
}
}
일단 아무것도 구현하지 않고 테스트를 실행해봤다.
두 번째 턴을 보면 21 다음에 30이 실행되는 등 스레드의 우선순위가 맞지 않는 것을 확인할 수 있다.
$ make check TESTS="tests/threads/priority-sema”
(참고)
구현하다가 priority-sema 테스트가 fail조차 뜨지 않고 Error가 뜨길래 alarm-zero도 테스트 해봤는데 이것도 Error가 발생했다.
git diff로 가장 최근에 수정했던 부분을 주석처리 해보며 원인을 파악해봤는데 synch.c 파일 안에 선언한 list_high_priority()함수 구현부를 주석처리 하니까 alarm-zero 테스트가 다시 정상적으로 pass되는 것을 확인했다. 다시 에러 문구를 확인해보니 threads/synch.o에서 list_high_priority 함수가 multiple definition 즉 중복 정의되었다고 알려주고 있었다.
근데 synch.c 파일에서도 sema_down()할 때 list_insert_ordered()의 인자로 list_high_priority()함수를 써야 되는데… 이거 어떻게 끌어오지? 생각해봐야겠다.
아 찾았다. thread.c에 정의된 함수를 synch.c에서도 쓸 수 있는 방법..! synch.c에서는 이렇게 thread.h를 include해서 thread.c에 정의된 함수를 끌어다 쓸 수 있다.
#include "threads/thread.h"그런데 내가 정의한 함수인 list_high_priority()는 아직 thread.c에만 구현되어 있고 thread.h에는 포함되어있지 않다. 내가 안 넣었기 때문이다… thread.h에 list_high_priority()함수의 프로토타입을 추가하니까 synch.c에서도 해당 함수를 쓸 수 있게 되었다.
sema_down()에서 list_push_back()을 list_insert_ordered()로 바꾸어 다시 실행해봤다.
오잉… 이번에는 우선순위가 높은 스레드부터 차례대로 실행된 것 같은데 왜 test failed가 뜨지?ㅠㅠ…
음………..우선순위 역전 상황 이런 것도 같이 구현해야 이 테스트케이스가 통과되나?? 암튼 일단 지나가고 우선순위 역전에 대해서 공부하다가..!! 지나가던 우리반에게 우선순위 역전에 대한 설명을 듣고 같이 디버깅도 해서 해결했다.
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
struct thread *curr = thread_current();
old_level = intr_disable ();
while (sema->value == 0) {
//list_push_back (&sema->waiters, &thread_current ()->elem);
list_insert_ordered(&sema->waiters, &curr->elem, list_high_priority, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}
⚙️ 디버깅 과정 1 :
- 먼저 $ make check TESTS="tests/threads/priority-sema”를 실행하고 나서 터미널에 출력되는 게 진짜 내 코드 실행 결과가 아니라고 한다. priority-sama.output 파일을 봐야 한다. 이 파일을 봤더니 잘못된 실행 결과가 보였다. 우선순위 21번 스레드가 wake되지 않았다는 사실을 발견했다.
2. 테스트 코드에서 thread_create()로 스레드를 10개 생성해서 ready_list에 넣는데 이때 thread_create()를 할 때 3번째 인자로 뭘 주는지 모르겠어서 그냥 넘어갔었다. 그런데 이 부분이 가장 중요한 부분이었다. 지금 생성하고 있는 스레드가 어떤 로직을 수행하게 할건지 지정해주는 부분이었다. 이 사실을 알게 되고 나서 내가 이해가 안 되는 부분이 풀렸다.
🤔 나의 의문점 : thread_create() 안의 로직을 보면 새로 생성된 스레드들은 모두 ready_list에 바로 들어가게 하던데.. 그리고 테스트 코드 로직을 보면 어디에도 sema_down()을 하지 않아서 sema→waits에 스레드가 들어갈 일이 없는데.. sema_up()으로 뭘 깨운다는 거지? sema→waits는 비어있을 텐데?
👉🏻 테스트 케이스에서 thread_create()의 세 번째 인자로 priority_sema_thread()를 전달하고 있다. 즉 새로 생성된 10개의 스레드는 다음 로직을 수행하는 스레드로 정의된 것이다.
static void
priority_sema_thread (void *aux UNUSED)
{
sema_down (&sema);
msg ("Thread %s woke up.", thread_name ());
}그래서 10개의 스레드는 생성되자 마자 ready_list로 들어간 후 cpu에서 하나씩 실행되어 sema_down()을 한다. sema_down()은 ‘sema→value==0이면 sema→waiters에 현재 스레드를 우선순위가 큰 순서대로 추가하고 스레드를 blocked 상태로 바꾸는 로직’을 수행한다. 즉 sema_down()이 실행되고 sema→waiters로 들어가는 로직이 없는 줄 알았는데 있었다. ㅎ
그림으로 정리하면 위와 같다. 테스트 코드가 어떻게 돌아가는지 정리가 됐으니, 이제 우선순위가 21번인 스레드가 왜 wake되지 못 했는지 디버깅을 해보자.
void
test_priority_sema (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
sema_init (&sema, 0);
thread_set_priority (PRI_MIN);
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 3) % 10 - 1;
char name[16];
snprintf (name, sizeof name, "priority %d", priority);
thread_create (name, priority, priority_sema_thread, NULL);
}
for (i = 0; i < 10; i++)
{
sema_up (&sema);
msg ("Back in main thread.");
}
}
3. 우선순위가 21번인 스레드가 출력되지 않은 이유는 sema_up()에서 sema→value++;의 위치가 틀렸기 때문이다. thread_unblock()하기 전에 sema→value++를 해줘야 하는데 순서를 반대로 구현해서 통과되지 않았다.
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); //sema 변수가 NULL이 아닐 때만 아래 코드를 실행
old_level = intr_disable (); //인터럽트 disable
sema->value++;
if (!list_empty (&sema->waiters)) //sema->waiters가 비어있지 않다면
thread_unblock (list_entry (list_pop_front (&sema->waiters), //thread_unblock의 인자로 sema->waiters의 가장 앞에 있는 스레드를 전달
struct thread, elem));
intr_set_level (old_level);
}
4. 그리고 추가로 다른 팀 코어타임에 참여하면서 알게 된 건데, 리스트에 넣을 때 list_insert_ordered()로 정렬을 해주지만 리스트에서 꺼낼 때도 정렬을 해줘야 가장 큰 우선순위의 스레드를 꺼낼 수 있다고 한다. 예를 들어 리스트에 정렬된 상태로 스레드들이 들어가 있었는데도 중간에 우선순위 역전이 발생하여 스레드들의 우선순위가 바뀔 수 있기 때문이다. 따라서 리스트의 위치로 스레드 우선순위를 따져서 꺼내는 게 아니라 리스트에 저장된 스레드들의 우선순위를 직접 따져서 꺼내야 한다는 얘기다.
⚙️ 디버깅 과정 2..! :
priority-donate-sema, priority-donate-one을 구현하고 나서 priority-sema를 다시 테스트하니 fail이 발생했다.
printf를 찍어서 output을 확인해보니 priority_sema_thread() 로직이 아예 실행되지 않고 있었다.
일단 내가 수정한 부분은 thread_create()이 아니라 sema_down(), sema_up()이기 때문에 이 부분에 문제가 있는 것으로 판단하고 살펴보았다.
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); //sema 변수가 NULL이 아닐 때만 아래 코드를 실행
old_level = intr_disable (); //인터럽트 disable
sema->value++;
if (!list_empty (&sema->waiters)){
list_sort(&sema->waiters, list_high_priority, NULL);
thread_unblock (list_entry (list_pop_front (&sema->waiters), //thread_unblock의 인자로 sema->waiters의 가장 앞에 있는 스레드를 전달
struct thread, elem));
} //sema->waiters가 비어있지 않다면
intr_set_level (old_level);
}
세마포어 변수를 1 증가시키고 sema→waiters를 정렬한다.
정렬 기준은 initial_priority가 아니라 priority이다. gpt가 이 부분을 고려하라고 했다. 우선순위가 donate되었다면 둘 중 어떤 값을 기준으로 먼저 wake되어야 할까?
bool
list_high_priority(const struct list_elem *a, const struct list_elem *b, void *aux){
struct thread* t_a = list_entry(a, struct thread, elem);
struct thread* t_b = list_entry(b, struct thread, elem);
//a의 우선순위가 더 크면 true 리턴
return t_a->priority > t_b->priority;
}
이 테스트 케이스는 sema→waiters에 기다리고 있는 스레드들 중 가장 우선순위가 높은 스레드가 깨는지 확인하는 테스트이다. 근데 우선순위가 donate되었다면 priority값이 바뀌었을 것이고 list_high_priority에서 priority를 비교하고 있으므로 상관 없는 것 아닌가? 그리고 심지어 priority-sema 테스트에서는 lock을 쓰고 있지 않아서 donation이 일어나지도 않는다. 우선순위가 뒤바뀌어서 비교대상이 꼬이는 일이 일어나지 않을 것이다.
sema_down()을 보자. sema→waiters에 스레드를 넣고 스레드를 blocked상태로 바꾼다. 아 지지지지진짜 문제가 뭔지 모르겠다.
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
struct thread *curr = thread_current();
old_level = intr_disable ();
while (sema->value == 0) {
//list_push_back (&sema->waiters, &thread_current ()->elem);
list_insert_ordered(&sema->waiters, &curr->elem, list_high_priority, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}
정말 이해가 안 가서 내가 지피티한테 했던 질문들이다.
❔
이 문제를 해결하기 위해서
thread_set_priority 함수에서 priority 뿐만 아니라 우선순위를 donate받기 전의 priority도 new priority로 변경해줘야 이 문제가 해결된다고 하는데, 이유가뭐야? 어차피 donate받은 후의 priority로 sema->waits안에서 기다리는 스레드들을 정렬하잖아
근데 priority-sema라는 테스트를 할 때는 Lock을 사용하지 않잖아. 그러면 우선순위 기부가 일어날 일이 없으니까 상관 없는 거 아니야..?
지금 너가 말한 문제점이 우선순위가 기부되었을 때 priority 뿐만 아니라 initial\_priority까지 바꿔야 하는데 바꾸지 않았다는 거잖아. 그런데 lock을 얻기 위해 잠시 우선순위를 바꾸기 위해서 priority를 변경해놓는 것이고 나중에 lock을 release할 때 다시 inital\_priority로 돌아가야 하니까 inital\_priority값은 항상 불변이어야하는 거 아니야?
Prirority-sema 테스트코드에서 set\_priority가 어디 호출되는데???? 그냥 처음 PRI\_MIN값 설정할 때만 한 번 호출되는데?
내 코드 에서 내부 정렬 함수가 initial\_priority 기준으로 동작하는 부분은 없어...
→ 딱 여기까지 질문했을 때 문제가 뭔지 좀 파악이 되는 것 같았다. 그러니까 새로 생성한 10개의 스레드의 우선순위를 모두 thread_set_priority()로 바꾼 게 아니라 (코드 상에서 아무리 찾아도 없긴 했음;) 맨 처음에 메인 스레드의 우선순위를 낮추려고 thread_set_priority(PRI_MIN);을 호출한 부분에서 priority만 바꾸고 initial_priority를 바꾸지 않아서 발생한 문제라는 말인 것 같다. thread_set_priority()는 donation처럼 우선순위를 잠시 바꿨다가 lock을 반납할 때 다시 돌려야 하는 우선순위가 아니라 그냥 스레드의 우선순위를 자체적으로 바꾸는 함수라서 initial_priority까지 바꿔야 한다는 말인 것 같다. 그래서 main스레드의 우선순위를 강제로 바꾸는 이 부분을 변경해줘야 하나 보다.
그런데 아직도 의문인 건 음…메인 스레드의 우선순위를 강제로 바꿔줘서 initial_priority까지 수정해줘야 하는 건 알겠어. 그런데 두 스레드의 우선순위를 비교하는 함수에서는 다 priority끼리 비교해서 initial_priority까지 안 바꿔줘도 테스트 오류는 안 나지 않나?하는 생각이 드는데… 당연히 원래 바꿔줘야되는 값이긴 한데 그래도 테스트 패스하는 데는 영향을 안 주지 않나..?
그리고 또 생긴 의문점이 있다.
void
thread_set_priority (int new_priority) {
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority){
thread_yield();
}
thread_current ()->priority = new_priority;
thread_current ()->initial_priority = new_priority;
}
이렇게 하면 priority-change가 fail이 뜨고
void
thread_set_priority (int new_priority) {
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority){
thread_current ()->priority = new_priority;
thread_current ()->initial_priority = new_priority;
thread_yield();
}else {
thread_current ()->priority = new_priority;
thread_current ()->initial_priority = new_priority;
}
}
이렇게 하면 priority-change가 pass가 뜬다.
뭐가 다른 거지……? …..????????아 순서가 다르구나??오키
void
thread_set_priority (int new_priority) {
//우선순위를 new_priority로 변경하고
thread_current ()->priority = new_priority;
thread_current ()->initial_priority = new_priority;
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority)
thread_yield();
}
음 그런데 이렇게 구현했는데 또 fail이 떴다.
조건문에서 원래 우선순위와 new_priority를 비교하고 나서 !!!! 바꿔야 되는구나 ㅎㅎ… 오키….먼지 알았당
아아ㅏㅏㅏ그리고 우리 조원이 해결법을 이렇게 알려주셨는데
💡
기부 구현을 위해 original_priority 추가
- thread 구조체에 original_priority 필드를 두고,
- thread_init() 시점에 초기 우선순위(PRI_DEFAULT 등)를 복사해 놓습니다.
thread_set_priority() 호출과 테스트 검증
- sema/condvar 테스트들은 thread_set_priority(new_prio) 로 스레드 우선순위를 바꾼 뒤,
- 그 값(thread->priority)을 보고 “누구를 먼저 깨울지” 또는 “누구에게 CPU를 줄지”를 결정합니다.
문제 발생 지점
- 중간에 thread_set_priority() 로 우선순위가 변경되더라도,
- original_priority 는 초기값 그대로 남아 있기 때문에,
- lock_release() 등에서 thread->priority = thread->original_priority 복원 시에
- → 실제 사용자가 설정한 최신 우선순위가 아닌, 이전(낡은) 값 으로 돌아가 버립니다.
결과
- donate-one 테스트는 한 번만 기부·복원하기 때문에 우연히 통과될 수 있으나,
- sema/condvar 테스트처럼 우선순위 변경이 반복적으로 일어나는 시나리오에서는
- 잘못된(original_priority) 복원 때문에 스케줄러가 엉뚱한 순서로 작동해 테스트가 실패 합니다.
라고 gpt가 알려주네요간단하게 말하면 condvar나 sema 테스트는 thread_set_priority함수를 호출해서 우선순위를 변경을 하는데우선순위 변경할때 donate를 구현하기 위해 만든 original_priority도 바꿔줘야하는 안바꿔줘서 문제가 생기는겁니다그래서 thread_set_priority함수에 original_priority도 new_priority로 변경하는 함수를 추가 해주면 됩니다.
이걸 다시 읽고 다시 한 번 생각해보니까 뭔가 생각이 이어진다. 다시한 번 최종 정리를 하면 이렇다.
/* Tests that the highest-priority thread waiting on a semaphore
is the first to wake up. */
#include <stdio.h>
#include "tests/threads/tests.h"
#include "threads/init.h"
#include "threads/malloc.h"
#include "threads/synch.h"
#include "threads/thread.h"
#include "devices/timer.h"
static thread_func priority_sema_thread;
static struct semaphore sema;
void
test_priority_sema (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
sema_init (&sema, 0);
thread_set_priority (PRI_MIN);
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 3) % 10 - 1;
char name[16];
snprintf (name, sizeof name, "priority %d", priority);
thread_create (name, priority, priority_sema_thread, NULL);
}
for (i = 0; i < 10; i++)
{
sema_up (&sema);
msg ("Back in main thread.");
}
}
static void
priority_sema_thread (void *aux UNUSED)
{
sema_down (&sema);
msg ("Thread %s woke up.", thread_name ());
}
이 priority-sema 테스트에서 맨 처음에 main함수의 우선순위를 낮췄잖아
thread_set_priority (PRI_MIN);
이렇게?
이게 왜 우선순위를 낮춘 거냐면, 원래 스레드가 생성될 때는 항상 PRI_DEFAILT 즉 우선순위가 31값으로 설정된다.
따라서 이 코드를 실행하면 main함수의 우선순위가 0으로 낮아진다.
그리고 thread_set_priority() 내부 구현을 보면 스레드 우선순위가 낮아졌을 때 thread_yield를 호출하여 cpu 점유 스레드를 바꾼다.
void
thread_set_priority (int new_priority) {
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority){
thread_current ()->priority = new_priority;
thread_yield();
}else thread_current ()->priority = new_priority;
}
이렇게 !
근데 여기서 initial_priority는 안 바꿔줬기 때문에 계속해서 main 함수의 우선순위가 가장 높은 채로 남아있어서 cpu가 양보되지 않고 main 스레드만 계속 실행되다가 끝나는 것 같다. 아니 근데 아직도 ………….이해가 안 간다고. priority는 바꿔줬잖아. 아 ㅇ.ㅇ ㅏㅇ아아ㅏ,.
4. priority-change 테스트 pass하기
테스트 코드 해석 :
- 스레드 우선순위를 낮춰서 더 이상 가장 높은 우선순위가 아니게 만들면 곧바로 다른 스레드로 yield되는지 확인하는 테스트 코드.
- 우선순위가 32인 “thread 2”를 생성한다. thread 2는 changing_thread()를 수행하는 스레드이다.
- 현재 실행 중인 스레드의 우선순위를 2 감소시킨다.
void
test_priority_change (void)
{
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
msg ("Creating a high-priority thread 2.");
thread_create ("thread 2", PRI_DEFAULT + 1, changing_thread, NULL); //우선순위 32인 "thread2"를 생성
msg ("Thread 2 should have just lowered its priority.");
thread_set_priority (PRI_DEFAULT - 2); //현재 스레드 우선순위를 2 감소시킴
msg ("Thread 2 should have just exited.");
}
static void
changing_thread (void *aux UNUSED)
{
msg ("Thread 2 now lowering priority.");
thread_set_priority (PRI_DEFAULT - 1); //현재 스레드 우선순위를 1 감소시킴
msg ("Thread 2 exiting.");
}
아직 아무것도 구현하지 않은 상태에서 테스트를 실행하면 결과가 이렇게 나온다.
원래 Acceptable output처럼 나와야 하는데 Differences in diff -u format와 같은 결과가 나온 것.
스레드 우선순위가 변경되었을 때도 priority가 가장 큰 스레드 기준으로 꺼낼 수 있도록 ready_list에 스레드를 넣을 때 뿐만 아니라 ready_list에서 스레드를 꺼낼 때도 정렬을 수행해야 한다.
따라서 schedule에서 cpu에 올릴 때 ready_list에서 pop하기 전에 sort처리하기 위해 이 부분을 추가했다.
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list)) //ready_list가 비어있다면
return idle_thread; //idle_thread를 반환
else{
list_sort(&ready_list, list_high_priority, NULL); //정렬하는 부분 추가!
return list_entry (list_pop_front (&ready_list), struct thread, elem); //ready_list의 가장 앞에 위치하는 스레드를 반환
} //레디큐가 비어있지 않다면
}
그런데 output은 바뀌지 않았고 테스트는 여전히 fail이었다.
아까 참여한 2조 코어타임에서 두 부분을 바꾸면 이 테케를 통과할 수 있다고 들은 것 같아서 또 찾아봤다. 파일 전체에서 list_pop하는 부분을 검색했더니 sema_up() 부분에 sema→waiters 리스트에서 우선순위가 가장 높은 스레드를 pop해서 ready_list로 올리는 부분이 나왔다. 생각해보니 cpu에 올릴 때만 정렬해야하는 게 아니라, sema→waiters에서 ready_list로 올릴 때도 우선순위 순서로 정렬을 해야 했다..! 왜냐하면 semaphore(lock)을 차지하려고 기다리는 스레드들 중 가장 먼저 lock을 차지해야 하는 스레드는 우선순위가 가장 높은 스레드여야 하기 때문이다! 따라서 sema→waiters에서 ready_list로 올리는 경우도 우선순위 순서로 정렬을 해줘야 한다.
→ 이 부분은 우선순위 스케줄링에서 중요하다. lock을 차지하기 위해 기다리는 스레드들 중 우선순위가 가장 높은 스레드를 먼저 깨우지 않으면, 높은 우선순위를 가진 스레드가 lock을 얻지 못하고 block된 채로 대기하게 되기 때문에 우선순위를 무시(priority inversion)하게 된다!
자…그래서 여기도 이렇게 정렬 로직을 추가했는데 테스트가 또 fail이다. output도 그대로다. 음…
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL); //sema 변수가 NULL이 아닐 때만 아래 코드를 실행
old_level = intr_disable (); //인터럽트 disable
sema->value++;
if (!list_empty (&sema->waiters)){
list_sort(&sema->waiters, list_high_priority, NULL); //여기 정렬 로직 추가 !
thread_unblock (list_entry (list_pop_front (&sema->waiters), //thread_unblock의 인자로 sema->waiters의 가장 앞에 있는 스레드를 전달
struct thread, elem));
} //sema->waiters가 비어있지 않다면
intr_set_level (old_level);
}
/
지피티한테 살짝 힌트만 달라고 하니까 우선순위가 낮아졌을 때 즉시 cpu를 양보하게 했냐고 한다. 오… 우선순위가 낮아지면 무조건 cpu를 양보해야 하나? 그런 것 같다. 그래서 일단 이렇게 추가했는데 여전히 테스트가 fail이다. 확인 안 한 조건이 더 있나?
void
thread_set_priority (int new_priority) {
thread_current ()->priority = new_priority;
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority){ //로직 추가
thread_yield();
}
}아니다! 이렇게 해야 한다.
void
thread_set_priority (int new_priority) {
//우선순위가 낮아졌으면 cpu를 즉시 양보하게 한다.
if(new_priority < thread_current() -> priority){
thread_current ()->priority = new_priority;
thread_yield();
}else thread_current ()->priority = new_priority;
}통과!!!
5. priority-donate-sema 테스트 pass하기
테스트 코드 해석 :
이번 테스트 코드는 해석하기 정말 어려웠는데 세 명이 붙어서 같이 해석해주었다. 우리 반 최공 ㅎ-ㅎ
/* Low priority thread L acquires a lock, then blocks downing a
semaphore. Medium priority thread M then blocks waiting on
the same semaphore. Next, high priority thread H attempts to
acquire the lock, donating its priority to L.
Next, the main thread ups the semaphore, waking up L. L
releases the lock, which wakes up H. H "up"s the semaphore,
waking up M. H terminates, then M, then L, and finally the
main thread.
Written by Godmar Back <gback@cs.vt.edu>. */
#include <stdio.h>
#include "tests/threads/tests.h"
#include "threads/init.h"
#include "threads/synch.h"
#include "threads/thread.h"
struct lock_and_sema
{
struct lock lock;
struct semaphore sema;
};
static thread_func l_thread_func;
static thread_func m_thread_func;
static thread_func h_thread_func;
void
test_priority_donate_sema (void)
{
struct lock_and_sema ls;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
/* Make sure our priority is the default. */
ASSERT (thread_get_priority () == PRI_DEFAULT);
lock_init (&ls.lock); //lock->holder을 NULL로, lock->semaphore을 1로 초기화
sema_init (&ls.sema, 0); //sema->value를 0으로 설정, sema->waiters를 초기화
thread_create ("low", PRI_DEFAULT + 1, l_thread_func, &ls);
thread_create ("med", PRI_DEFAULT + 3, m_thread_func, &ls);
thread_create ("high", PRI_DEFAULT + 5, h_thread_func, &ls);
sema_up (&ls.sema); //sema->value를 1 증가시키고, sema->waiters에서 우선순위가 가장 높은 스레드를 unblock한다. 즉 blocked에서 ready상태로 바꾸고 ready_list에 추가한다. (이때 ready_list에 새로 추가된 스레드 우선순위가 현재 실행 중인 스레드 우선순위보다 높으면 문맥 교환 발생)
msg ("Main thread finished.");
}
static void
l_thread_func (void *ls_)
{
struct lock_and_sema *ls = ls_;
lock_acquire (&ls->lock); //sema_down()을 호출, lock->holder를 현재 스레드로 설정
msg ("Thread L acquired lock.");
sema_down (&ls->sema); //
msg ("Thread L downed semaphore.");
lock_release (&ls->lock);
msg ("Thread L finished.");
}
static void
m_thread_func (void *ls_)
{
struct lock_and_sema *ls = ls_;
sema_down (&ls->sema);
msg ("Thread M finished.");
}
static void
h_thread_func (void *ls_)
{
struct lock_and_sema *ls = ls_;
lock_acquire (&ls->lock);
msg ("Thread H acquired lock.");
sema_up (&ls->sema);
lock_release (&ls->lock);
msg ("Thread H finished.");
}- lock_and_sema 자료구조를 생성해서 lock과 semaphore 변수를 모두 쓸 수 있게 만든 것 같다. 이 부분은 왜 굳이 이렇게 자료구조 하나로 묶어뒀는지 잘 모르겠다.
- lock과 sema 변수를 사용할 수 있도록 초기화한다. sema 변수값은 0으로 설정하였다.
- thread_create()로 low, med, high라는 이름의 3 개의 스레드를 생성한다. 우선순위는 각각 32, 34, 36이다.
- thread_create()로 생성된 스레드는 바로 running 상태가 되어 cpu에서 실행된다. low, med, high 순서로 cpu에서 실행될 것이다.
- 스레드 low는 l_thread_func()을 로직으로 실행한다. lock_acquire()는 sema_down()을 호출하지만 sema변수가 0이기 때문에 lock을 얻지 못하고 block되어 sema->waiters로 들어간다.
- 스레드 med는 m_thread_func()을 로직으로 실행한다. sema_down()을 호출하지만 마찬가지로 sema변수가 0이기 때문에 lock을 얻지 못하고 block되어 sema->waiters로 들어간다.
- 스레드 high는 h_thread_func()을 로직으로 실행한다. lock_acquire()는 sema_down()을 호출
하지만 sema변수가 0이기 때문에 lock을 얻지 못하고 block되어 sema->waiters로 들어간다.- -> 취소선 그은 부분이 실행되기 전에 lock_acquire()에서 현재 스레드의 우선순위와 lock을 가지고 있는 스레드의 우선순위를 비교하여 현재 스레드 우선순위가 더 크면 lock을 가지고 있는 스레드에게 현재 스레드 우선순위를 부여한다. (donate)
- 현재 스레드가 lock을 점유하고 실행하려면 지금 lock을 가지고 있는 스레드가 빨리 실행을 끝내고 lock을 반환해야 하므로 우선순위를 기부하여 높여주는 것이다.
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
/* sema 변수가 0일 때, lock->holder의 우선순위가 더 낮으면 우선순위 donate하는 로직 추가 */
if(lock->semaphore.value==0){
if(thread_current()->priority > lock->holder->priority){
lock->holder->priority = thread_current()->priority;
}
}
sema_down (&lock->semaphore);
lock->holder = thread_current ();
}'정글 > Pintos' 카테고리의 다른 글
| [pintos] 2주차 - Argument Passing 구현 과정 (0) | 2025.05.24 |
|---|---|
| [pintos] 2주차 - 키워드 정리 (0) | 2025.05.24 |
| [pintos] 1주차 - Priority Scheduling 문서 해석 / 코드 해석 (1) | 2025.05.20 |
| [pintos] 1주차 - Alarm Clock 구현 과정 (0) | 2025.05.20 |
| [pintos] 1주차 - Alarm Clock 코드 정리 (1) | 2025.05.20 |