어제 드디어 priority까지 끝냈다.. 발제한 지 8일 만에...
확실히 priority가 더 어려웠다.
alarm은 처음에 아무것도 모르는 상태에서 감 잡느라 더 어렵게 느껴졌던 거 같다.
아무튼 mlfqs 들어가기 전에 priority도 가볍게 정리하고 마무리 해야겠다.
📍alarm-priority Test-case
사실 각 스레드에는 이미 priority가 있다.
그런데 우리는 그 priority를 아예 활용하지 않았던 것 뿐이다.
그래서 따로 구조체에 priority를 추가 할 필요는 없다. 그냥 가져다 쓰면 된다.
첫 번째 과제 alarm-clock 글에서는 alarm-priority가 pass되지 않았을 것이다.
(priority를 고려했던 사람이라면 pass 했겠지만ㅎ...)
이제 맨 처음에 그 테스트 케이스를 통과하기 위한 코드부터 작성해보자.
동일한 tick에 일어나는 애들이 있다면, 우선순위 순으로 일어나야 한다.
그런데 우린 지금까지 fifo 형식으로 깨웠을 것이다.
그럼 어떻게 우선순위 순으로 일어날까?? 🤔
바로 ready_list에 넣을 때 우선순위 순으로 정렬 삽입하는 것이다.
그렇게 하면 list의 front가 우선순위가 가장 높은 스레드니까, 원래 방식대로 맨 앞에 있는 thread를 꺼내기만 하면 된다.
ready_list에 삽입하는 경우: unblock() & yield()
두 함수에서 ready_list에 삽입할 때 push_back이 아닌 insert_ordered를 활용해 우선순위 순으로 정렬되도록 수정해준다.
이 두 부분만 수정하면, alarm-priority 테스트 케이스까지 alarm-clock은 모두 pass 된다.
이제 대망의 priority-scheduling을 구현해보자.
📍Project(2)의 두 번째 과제, Priority-Scheduling 구현
기존의 pintos는 Round-Robin 방식으로 구현되어 있다.
Round-Robin: 동일한 시간동안 프로세스/스레드가 cpu를 선점해 일하고, 시간이 다 되면 선점 당하면서 ready_list로 빠지는 방식이걸 priority-scheduling 방식으로 수정하는 것이 main goal이다.
스레드들이 우선순위 순으로 스케줄링 될 수 있도록 구현하는 것
위에서 구현한대로 ready_list에 우선순위 순으로 삽입되어 스케줄링 되고 있을 것이다.
그런데 한 가지 더 생각해야 할 점이 있다. ready_list에 새로운 스레드가 삽입되었을 때, 실행 중인 스레드보다 우선순위가 높다면? 새로 삽입된 스레드에게 cpu를 양보해야 한다.
void thread_compare_yield(void)
{
if (thread_current() == idle_thread)
{
return;
}
if (list_empty(&ready_list))
{
return;
}
if (thread_current()->priority < list_entry(list_begin(&ready_list), struct thread, elem)->priority)
thread_yield();
}ready_list에 새 스레드가 삽입될 때와 우선순위가 바뀔 때 해당 함수를 호출하도록 구현하면 된다.
-> thread_wakeup(), thread_set_priority(), thread_create()
트러블 슈팅) 예외처리를 제대로 해주지 않아 wakeup 내에 thread_compare_yield()를 하면 kernel panic이 나는 문제가 발생했었음여기까지 구현한 후 생각해야 할 일이 하나 있다.
공유 자원에 여러 스레드가 접근하는 동시성 현상이다. 해당 문제를 해결하기 위해 pintOS에서는 동기화 기법인 sema와 lock, condition을 사용하고 있는데, 이로 인해 또 해결해야 하는 문제가 있다.
그 전에 먼저 sema와 condition 구조체에는 waiters list가 있다. 해당 sema와 condition을 요청하고, 사용 중인 애가 있어서 바로 받지 못 하면 그를 기다리는 list들이다.
마찬가지로 이 리스트들도 우선순위 순으로 정렬되어야 하기 때문에 waiters에 삽입되는 부분을 push_back에서 insert_ordered 방식으로 수정해준다.
수정할 부분: sema_down() & cond_wait()+) 구조체가 너무 헷갈려서 그림을 그려봤다. list_elem? elem? 너무 많다;;
정확하진 않지만 이런 식으로 구성되는 느낌이다.
대충 sema와 cond에 대해 이해한 후 두 번째 과제에서 제일 중요하고 복잡하고 어려운 부분인
Priority Inversion을 해결해보자.
📍Priority Inversion
priority inversion이란,
우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 현상을 말한다.
어떻게 우선순위 순으로 삽입하고, 뽑아오는데 이런 일이 발생하지??
바로 sema, lock을 대입하면 이런 일이 발생한다.
다음 그림을 보자.
두 개의 스레드가 같은 공유자원에 접근한다. 그렇지만 동시에 접근할 수 없다. (Race Condition)
먼저 도착한 놈(C)이 해당 공유자원에 접근할 수 있는 권한인 lock을 점유하고 cpu를 할당받는다.
그런데 그 뒤에 도착한 thread(A)가 먼저 도착한 놈보다 우선순위가 높아 yield가 일어나면서 cpu를 할당받고, lock을 요청했더니 먼저 왔던 놈이 lock을 가져가버렸다. 그래서 해당 lock을 기다리는 waiters에 들어간다.
다시 먼저 도착한 놈(C)이 cpu를 할당받아 일을 하려는데? B가 도착한다. 근데 또 C보다 우선순위가 높아서 cpu를 선점해 일해버린다. 그럼 A가 우선순위가 가장 높지만, lock을 기다리느라 가장 마지막에 일하게 되는 현상이 일어난다. 이게 Priority Inversion이다.
이런 현상을 어떻게 해결할 수 있을까?
📍Priority Donation
바로 A가 lock을 요청하면서 자신의 우선순위를 '빌려주는' 것이다.
그럼 C가 B보다 우선순위가 높아져, cpu를 빼앗기는 일을 방지할 수 있다.
그런데, 이렇게 우선순위를 빌려주는 상황의 종류가 더 있다.
Multiple Donation
Multiple Donation은 Donation이 여러번 발생한 상황이다.
하나의 스레드가 공유자원 두 개 이상을 필요로 해 두 개를 가져간 상황에서 다른 스레드들이 각기 다른 lock을 요청하는 상황이 발생한다.
그럼 가장 우선순위가 높은 스레드에게서 donation 받고 일을 처리하고, 다음으로 높은 스레드의 우선순위를 받아와야 한다.
Nested Donation
Nested Donation은 스레드들이 마치 체인처럼 우선순위를 Donate 해주는 상황이다.
이 모든 상황을 고려해 Priority-Inversion을 Priority-Donation으로 해결하기 위해선
다음과 같은 사항을 수정해야 한다.
검정 글씨는 수정 사항에 대한 내용
빨간 글씨는 내가 생각한 방법
alarm&priority all-passed 코드 깃허브
<priority 구현하면서 주의해야 할 점>
1) remove_donations()
lock_release 할 때, Donation list에서 while문으로 돌면서 해당 lock을 wait하던 스레드들을 지울 때 구조체 선언에 주의하기
list 관련 함수들은 list_elem을 반환한다. thread 형식으로 받아오고 싶다면 list_entry를 씌워야 함
또한 인자 형식도 잘 맞춰서 넣어주기... 이것 때문에 결과가 안 나오고 터져서 뭐가 문젠지 1-2시간을 끙끙 앓았다 아무리 봐도 로직은 틀리지 않은 것 같은데 왜 터지지?!ㅠ 같은...2. list_sort()
donation을 하다보면 priority가 빈번하게 바뀌겠지
그래서 donations도 우선순위 순으로 정렬되어 있게끔 list_sort 해야 할 부분을 꼼꼼히 체크해야 한다. 나같은 경우는 이제 priority 거의 다 pass 뜨는데, priority-donate-sema 테스트 케이스만 fail이 떠서 test 소스코드를 뜯어봤더니 L_thread 다음 M이 와도 선점 당하면 안 되는데 선점을 당해버리는 문제가 생겼었다. sema의 waiters에서 정렬이 안 되어서 L가 먼저 나와야 하는데 M이 먼저 나와버리는 문제 같아서 sema_up()에서 unblock 하기 전에 waiters를 정렬해주었더니 문제가 해결됐다.3) original priority & priority
우선순위를 기부받으면서 priority가 변하기 때문에, original_priority를 새로 구조체에 생성해줬을 것이다. 그러고서 original_priority가 쓰이는 부분은 donations가 비었을 때 뿐이라고 생각했는데, thread_set_priority 부분이 있었다. thread_set_priority에서 우선순위를 바꾸는 건 original을 바꿔야 한다.그냥 priority는 donation에 의해 계속 바뀌기 때문에.
