이번에 할 프로젝트의 주인공은 Threads이다. Pintos Manual에는 제일 처음 등장하는 파트인데 울 학교에서는 제일 마지막에 했다. 이번에 일정상 Virtual Memory 구현 부분이 빠졌다고 들었는데, 그게 좀 아쉬워서 깃헙을 통해 Virtual Memory 테스트코드도 구해볼 생각이다. (OS는 내 사랑이니까!)
이번 프로젝트에서 Process나 Threads가 Priority에 맞추어 동작하도록 한다.
현재 PintOS의 thread는 RUNNING과 READY를 왕복하며 busy waiting을 한다. 아무것도 하는 일 없이 왔다~갔다~ 하면서 CPU를 낭비하고 있는 셈이다. CPU 낭비를 막기 위해 busy waiting 방식을 수정해서 더욱 합당한 waiting 방식을 구현한다.
그리고 이번엔 다양한 Scheduler도 쓸건데 수업 때 배운 걸 떠올려보면 First In First Out : FIFO, Shortest Job First : SJF, Round Robin : RR 등을 배웠고 현재 PintOS는 Round-Robin Scheduler를 사용하고 있다. 이를 수정해서 thread의 Priority를 고려한 Priority Scheduler를 구현해야 한다.
이걸 Scheduler를 구현하려면 (1) Priority를 설정해야한다. 이를 위해서 thread에 관한 함수와 구조체를 수정해야 한다. 각기 다른 Priority thread가 잘 운영되도록 하려면 (2) Synchronization을 잘 해야 한다. 이걸 하려면 Semaphore와 lock에 관한 구조체와 함수를 수정해야 한다. 이 두 과정을 거쳐서 각기 다른 Priority를 지닌 Scheduler가 잘 작동할 수 있다. 뭔 소린 하냐고? 하다보면 다 알게되리니...
- 기본적인 스케쥴러 동작
일단 스케쥴러가 어떻게 동작하는 지 설명하자면
threads/thread.c에 보면 struct list ready_list가 선언되어있다. 여기가 THREAD_READY 인 thread가 줄지어서있는 곳이다.
여기서 next_thread_to_run을 호출한다. 이 함수는 ready_list 제일 앞에 있는 thread를 불러온다. 그리고 그걸 현재 thread와 switch한다.
- Alarm Clock
지금 보면 while문이 겁나 돌면서 thread_yield를 반복하고 있다. thread_yield()는 threads/thread.c에 있다. 그 내용을 보면 schedule 함수를 호출하는건데
이렇게 생겼다. 이 함수는 아까도 말했지만 현재 thread와 그 다음 돌려줄 thread를 찾아서 바꿔준다.
현재 PintOS는 timer_sleep()의 while 문을 계~~~~속 돌면서 scheduling을 한다. 즉 잠들어있는 thread들을 계ㅔㅔㅔㅔㅔㅔㅔ속 while문을 돌리고 있다. 우리는 이런 낭비를 막으려고 wake_up time이 도래한 thread만 깨워줄 거다.
아직 wake_up_time이 되지 않았으면? 계속 자야지 뭐 깰 시간도 안됐는데 깨우면 짜증나지않나,
Wake up time이 안된 thread는 BLOCKED state를 유지한다.
근데 문제가 있다. 어떤 thread가 잠들어있는지 알아야 하는데 지금은 그럴 방법이 없다. 그러니 device/timer.c에 sleep_thread를 관리해줄 sleep list를 만들어준다. 매 tick마다(이 tick이 PintOS 전체 System을 동기화시킨다고 보면 될 것 같다.) sleep_list에 있는 thread를 검사하면서 일어날 시간이 된 thread가 있다면 깨워준다(ready_queue에 넣는다.)
군대에서 불침번 서다가 그 다음에 불침번 서는 애를 깨우는 것과 같다.
timer_sleep() 함수가 호출되면 현재 ticks와 매개변수로 들어온 ticks를 더해서 wake_up_time을 설정한 후 아까 만들어뒀던 sleep_list에 추가한다. (list_push_back())그 후에 thread_block()을 호출해서 해당 thread의 state가 BLOCKED 되도록 한다.
위 함수는 timer_interrupt()라는 함수다. device/timer.c에 있다. 이 함수에서 ticks를 1씩 증가시킨다. 이 tick이 PintOS 안의 Clock이라고 볼 수 있다. tick이 증가할 때마다 thread_wake_up함수를 실행시켜서 sleep_list에 있는 잠든(Zzz) Thread 중 깨어날 thread가 있는 지 살핀다. (thread_wake_up())
Sleep_list를 돌면서 깨어날 시간이 된 thread를 찾고 그런 thread가 있으면 우선 그 thread를 sleep list에서 제거한 후 unblock을 해준다. unblock을 먼저 한 후에 list_remove를 하면 에러가 발생한다. 왜 그럴까, 생각해보면 thread_unblock()을 하면 해당 thread가 ready_list에 추가된다. ready_list는 CPU를 할당받으려는 thread가 대기하는 list이다. 그러니까
thread_unblock을 하고 list_remove를 하면 어떻게 될까?... sleep_list가 아니라 ready_list에 있는 thread에 대고 list_remove를 하는 셈이다. 구체적인 오류가 궁금하면 직접 실행해보자 ㅎ... 이렇게 하면 Alarm Clock을 구현했다고 볼 수 있다.
- Priority Scheduling
이제 Priority Scheduling을 구현해보자. 현재 PintOS는 Round-Robin Scheduling을 채택하고 있다.(RR) 한 thread에 할당 된 time quantum이 끝나면 자동으로 CPU를 반납하고 ready_list의 제일 끝에 삽입된다. 즉, Priority를 고려하지 않는 완전 평등 방식이다. 이번 프로젝트에서 Priority를 고려한 Scheduling을 구현한다.
thread가 만들어질 때 thread_create() 함수가 호출된다.
thread_create의 매개변수를 잘 보면 priority가 있다! PintOS에서 thread의 Priority는 0 ~ 63 사이이다. PintOS 내에서 각각 PRI_MIN과 PRI_MAX로 #define 되어 있다. 이 때 priority 값이 낮을수록 우선순위가 낮다. 그러니까 Priority 가 0이면 제일 priority가 우선순위가 낮다. (0이 PRI_MIN으로 정의된 까닭을 생각하자)
그리고 만들어진 thread의 priority가 현재 CPU를 점유하고 있는 thread의 Priority보다 크다면 thread_yield()를 호출해서 running thread를 교체한다.
Sema_down의 기능은 이전 프로젝트에서 다루었다. Sema 구조체는 waiters라는 list를 가지고 있다. Waiters는 sema를 기다리고 있는 thread의 list이다. 즉 semaphore에 의해 block되어있다. 그 list에 새롭게 block된 list를 넣을 때 priority에 따라 정렬해서 넣는다. 세 번째 매개변수인 thread_priority_comp는 다음과 같다.
매개변수로 들어온 두 list_elem의 thread를 비교해서 그 대소관계를 return 한다.
Sema_up을 할 때도 sema 구조체 waiters에서 semaphore를 기다리는 thread들 중 가장 priority가 높은 thread를 찾아서 sema_up을 한다. 사실 이런 작업을 Sema_down이나 Sema_up 둘 중 하나에서만 하면 되지만, 그냥 둘 다 했다 ㅎ.
Thread_set_priority는 thread의 priority를 바꾼다. Running thread의 priority와 비교해서 새롭게 설정된 priority가 더 크면 thread_yield()를 호출한다. (Preemptive Scheduling)
현재 thread의 priority를 return 하는 함수이다.
- Priority Aging
위 설정을 통해 thread_prior_aging과 thread_mlfqs를 구분해서 활용할 수 있다.
명세서에 나와있는대로 tick이 네 번 진행될 때마다 모든 thread의 priority를 update(aging) 해야 한다. 이 기능을 update_priority_with_aging() 함수가 한다. All_list에 저장된 모든 thread를 순회하면서 주어진 계산식에 맞게 priority를 update한다. 만약 priority가 PRI_MAX보다 높으면 PRI_MAX로 지정한다. PRI_MAX가 상한선이기 때문이다. 만약 priority가 PRI_MIN보다 낮으면 PRI_MIN으로 지정한다. PRI_MIN이 하한선이기 때문이다.
- Advanced Scheduler (BSD Scheduler)
lThread struct에 nice와 recent_cpu를 추가한다. 이 변수에 값을 저장할 것이다.
명세서에 나온대로 thread_init(thread가 처음 만들어 질 때)에서 각 thread의 nice와 recent_cpu 값을 0으로 초기화한다.
자식 thread는 부모 thread의 nice와 recent cpu 값을 물려받는다.
load_avg를 전역변수로 선언한다.
Mlfqs를 할 때 priority와 recent_cpu, load_avg는 위의 수식에 따라 계산해야 한다. 주의할 점은 recent_cpu와 load_avg는 소수점 연산이다. PintOS는 소수점 연산을 지원하지 않기 때문에 특별한 방법을 써야하는데 PintOS Manual에서 그 방법을 제공해준다.
lPintOS Manual에서 제공되는 방법을 그대로 사용한다.
정수 부분이 17 bit고 소수 부분이 14bit라는 점을 감안해서 Fixed Points는 LSB로부터 14번 왼쪽으로 bitwise 하면 된다.
이 연산을 위해서 FRACTION을 define 했다. 이제 nice와 priority, recent_cpu를 계산할 준비는 모두 되었다. 게다가 각 함수의 interface는 미리 구현되어있으므로 그 내용만 채우면 된다. 사람에 따라 소수점 연산을 미리 함수로 만들어서 적용하는 사람도 있다. 편할대로 하면 된다.
Thread_set_nice는 thread의 nice 값을 변경하고 priority를 새롭게 계산한다.
현재 thread의 nice 값을 return 한다.
현재 load_avg * 100을 return 한다 이 때 주의할 점은 load_avg 그대로 return 하는 게 아니라 load_avg * 100의 가장 가까운 integer를 return 한다는 점이다.
Real로 들어온 매개변수는 현재 Fixed Point value이다. 이를 반올림한 후 일반적인 Integer값으로 바꿔서 return 한다.
현재 thread의 recent cpu 값에 100을 곱한 후 가장 가까운 integer 값을 돌려준다. 위에서 소개한 nearest_int 함수가 쓰였다.
명세서에 나와있는 대로 ticks가 증가할 때마다 recent_one() 함수를 호출해서 CPU를 점유하고 있는 thread의 recent_cpu 값을 하나씩 증가시킨다.
l주의할 점은 recent_cpu가 Fixed Point Value이기 때문에 1을 증가할 때도 Fixed Point로 바꿔서 증가시켜야 한다는 점이다.
l그후에 1 second 마다 load_avg와 recent_cpu를 update 한다. 주의할 점은 1 second와1 ticks는 다르다는 점이다. Manual에서 1sec = ticks / TIME_FREQ라고 했으므로 그대로 구현한다. 그리고 명세서에서 제시한 대로 Ready_list에 있는 threads의 개수와, 현재 CPU를 점유하는 thread가 idle-thread가 아닐 경우 read_list에 있을 하나의 thread를 합쳐서 ready_threads 변수의 값을 정한다. 그 후 주어진 계산식 대로 계산한다.
l 마찬가지로 recent_cpu도 1초마다 새롭게 update 한다. 그 대상이 특정한 thread가 아니라 모든 thread 이므로 all_list에 저장된 모든 thread를 돌면서 recent_cpu를 update 한다.
각 Thread에 대한 Priority는 test case에서 알아서 설정할 것이니까 우리는 신경쓰지 말자! 대신 우리는 Priority에 따른 Starvation 문제를 고려해야 한다. Priority가 높은 thread가 계속 들어오면 priority가 낮은 애는 우주가 끝나고 신이 우주를 재창조할 때까지 일을 할 수가 없다. 이런 문제를 방지하려고 Priority Aging을 구현한다. ready_list에 머물러 있는 시간 등에 비례해서 thread의 Priority를 높여준다. 그러면 무한 대기상태에 빠지는 문제는 방지할 수 있다.
Virtual Memory도 구현해봐야지 히히
'개발 > PintOS' 카테고리의 다른 글
| Pintos Project(핀토스 프로젝트) 2 - User Program_File management (0) | 2020.07.21 |
|---|---|
| Pintos Project(핀토스 프로젝트) 1 - User Program (0) | 2020.07.21 |
