주의!
이 글은 pintos 프로젝트의 정답 코드 및 이론을 포함하고 있습니다.
pintos의 취지 특성 상 개인의 공부, 고민 과정이 정말 중요하다고 생각하며
프로젝트 풀이에 대한 스포일러를 받고싶지 않으신 분은 읽으시는걸 비추천 합니다.
이 글을 읽기전에
cpu 스캐줄링에 대한 기본적인 이해를 필요로 합니다.
cpu 스캐줄링에 대한 간단한 정리를 해 놓았으며, 필요하시다면 추가적인 공부를 먼저 하고 읽는것을 추천드립니다.
https://velog.io/@kts5927/CPU-scheduling
thread
이 과제에서 가장 중요하다고 생각했던것은 thread의 생성과 작동이다.
첫번째 과제의 주제가 thread이기도 하고, 코치님들이 저번부터 항상 말했던 것이 '프로세스외 thread의 차이는 무엇인가요?' 였기 때문이다.
tid_t thread_create(const char *name, int priority,
thread_func *function, void *aux)
{
struct thread *t;
tid_t tid;
ASSERT(function != NULL);
/* Allocate thread. */
/* 스레드를 할당합니다. */
t = palloc_get_page(PAL_ZERO);
if (t == NULL)
return TID_ERROR;
/* Initialize thread. */
/* 스레드를 초기화합니다. */
init_thread(t, name, priority);
tid = t->tid = allocate_tid();
/* Call the kernel_thread if it scheduled.
* Note) rdi is 1st argument, and rsi is 2nd argument. */
/* 예약된 경우 kernel_thread를 호출합니다.
* 참고) rdi는 첫 번째 인자, rsi는 두 번째 인자입니다. */
t->tf.rip = (uintptr_t)kernel_thread;
t->tf.R.rdi = (uint64_t)function;
t->tf.R.rsi = (uint64_t)aux;
t->tf.ds = SEL_KDSEG;
t->tf.es = SEL_KDSEG;
t->tf.ss = SEL_KDSEG;
t->tf.cs = SEL_KCSEG;
t->tf.eflags = FLAG_IF;
/* Add to run queue. */
thread_unblock (t);
enum intr_level old_level;
old_level = intr_disable();
struct thread *now_running_thread = thread_current();
if(now_running_thread->priority < t->priority)
thread_yield();
intr_set_level(old_level);
return tid;
}
위 코드는 priority까지 끝마친 thread_create 함수이다.
위의 함수는 pintos에서 사용하기 위해 만들어진 함수인데 실제로 사용하는 pthread 함수와도 유사한 모양을 가지고 있다.
위의 thread_creat의 모양을 보면
-
thread의 이름
-
thread의 우선순위
-
thread에서 실행하는 함수
-
추가로 받을 인자
모양으로 되어 있다.
그럼으로 실제로 사용하는 thread가 어떻게 작용하는지에 대한 정보를 확인할 수 있었으며, 그 작동방식은 다음과 같다.
-
palloc을 통해 thread를 할당한다.
-
이후 init_thread를 통해 스레드를 초기화 하고
-
레지스터에 function을 매핑한 후
-
unblock을 통해 run queue로 이동한다.
-
이후 priority 비교를 통해서 우선순위 스캐줄링을 한다.
이러한 작동 이후 run 상태가 되면 매핑해놨던 function이 실행된다.
R.rdi와 R.rsi는 다음과 같다.
struct gp_registers {
uint64_t r15;
uint64_t r14;
uint64_t r13;
uint64_t r12;
uint64_t r11;
uint64_t r10;
uint64_t r9;
uint64_t r8;
uint64_t rsi;
uint64_t rdi;
uint64_t rbp;
uint64_t rdx;
uint64_t rcx;
uint64_t rbx;
uint64_t rax;
} __attribute__((packed));Alarm clock
핀토스 첫번째 과제인 alarm clock이다.
처음 받은 핀토스 코드를 보면 한가지 문제가 있다.
바로 이놈인데
// .../devices/timer.c
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
while(timer_elapsed (start) < ticks)
thread_yield(); // busy wait
}
타이머를 busy wait으로 쓴다는 것이다.
이 코드가 뭔가 하니 전역 tick을 받아서 시간이 안되면 그냥 ready 리스트의 맨 뒤로 보내는 것이다. 되게 간단하고 편리한 방법인것 같다.
그럼 뭐가 문제이겠는가?
시간이 안되면 그냥 쓰레드가지고 뒤로 보내고 보내고 계속 보내면서 자원낭비를 하는 것이다.
그래서 장단점을 정리해보면
장점
- 권한을 얻는데 많은 자원을 쓰지 않는 상황에서는 효율적이다.
- context switching을 안하기 때문에 빠르다
단점
- cpu 사용량이 크다
정도가 되겠다.
그러니까 우리는 이 busy wait 방법이 어떤것인지도 알았으니, os의 덩치를 키우기 위해서는 더 효율적인 방법으로 갈아끼워야 한다는 것이다.
실제로는 이런 뼈대만 남은 학습용 os로는 프로그램을 돌리거나 하지는 않을것이다.
Alarm Clock
우리가 프로젝트를 시작하기 전에 이 alarm clock이 뭐하는놈인지 봐야한다.
// .../devices/timer.c
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
}이놈이다.
timer_interrupt라는 이 놈은 os가 실행될때 자동으로 켜지는 놈이며(엄밀하게 말하면 아니긴한데 테스트 돌릴때 자동으로 켜지니까 그런가보다 하자.) tick라는 global 변수를 하나씩 올리는 역할을 한다.
그리고 이놈은 프로세스가 돌아가건 프로그램이 돌아가건 상관없이 개별적으로 작동하는 인터럽트이다.
그러니까 cpu 작동을 아파트로 본다면
프로그램이 돌아가는 집 옆에있는 별개의 집이라고 생각하면 편하다.(독립적으로 작동한다는 뜻)
그래서 이 tick을 활용하게 된다면 우리는 '객관적인 시간'을 사용해서 프로그래밍 할 수 있는 것이다.
문제 풀이
우리는 처음에 yield로 코딩된 코드를 받는다.(yield = list 맨 끝으로 보내기)
그럼으로 우리는 ready list 안에서 스레드가 빙글빙글 돌고있는 상황이라는 걸 알 수 있다.
우리는 이제 sleep list를 새로 만든 다음, (현재 틱 + 일정틱)이 지난 다음 깨어날 수 있게 바꾸는 것이다.
즉 ready -> run -> ready 순서에서
ready -> run -> sleep -> ready 순서로 바꾼다는 뜻이다.
이 설명만 읽고 밑의 코드를 읽는다면 의문점이 많이 들 수 있는데,
그것 또한 개인이 생각을 해보자!
코드
주의!
밑의 코드를 제외하고도 define 선언이나 structure 구조를 추가해야 합니다.
하지만 다 적지는 않을꺼고 주변의 코딩잘알의 도움을 받거나 혼자 고민해 보시는 것도 좋을 것 같습니다.
timer_sleep
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
if (timer_elapsed (start) < ticks)
thread_sleep(start + ticks);
}
sleep을 하는 함수이다.
thread_sleep에 (전역틱 +일정시간) 인자를 준다.
thread_sleep
void thread_sleep(int64_t ticks)
{
struct thread *curr = thread_current();
enum intr_level old_level;
old_level = intr_disable();
if (curr != idle_thread)
{
curr->status = THREAD_BLOCKED;
curr->tick = ticks;
// list_push_back (&sleep_list, &curr->elem);
list_insert_ordered(&sleep_list, &curr->elem, (list_less_func *)local_tick, NULL);
}
schedule();
intr_set_level(old_level);
}
thread를 block 상태로 만들고 sleep_list로 보내는 함수이다.
순서는 다음과 같다.
- interrupt를 비활성하고
- 만약 running스레드가 idle_thread가 아니라면
- thread를 THREAD_BLOCKED로 바꾸고
- tick을 갱신한 후
- sleep_list에 insert_orderd로 추가 한다.
- schedule을 한 후
- interrupt를 재실행 한다.
thread_wakeup
void thread_wakeup(int64_t tick)
{
if (list_empty(&sleep_list))
return;
enum intr_level old_level;
struct thread *to_wakeup = list_entry(list_front(&sleep_list), struct thread, elem);
old_level = intr_disable();
while (to_wakeup->tick <= tick)
{
list_pop_front(&sleep_list);
list_insert_ordered(&ready_list, &to_wakeup->elem, (list_less_func *)larger, NULL);
to_wakeup->status = THREAD_READY;
if (list_empty(&sleep_list))
return;
to_wakeup = list_entry(list_front(&sleep_list), struct thread, elem);
}
intr_set_level(old_level);
}좀 길다.
순서를 살펴보면
- 만약 빈 리스트가 아니라면 return (이거 안해주면 panic이 뜬다)
- interrupt를 비활성화 시킨 후
- 만약 front의 tick이 전역tick보다 작을때 순회한다.
- 만약에 전역tick보다 개인tick이 더 크다면
- sleep_list의 첫 스레드를 pop 한 후 ready에 넣고
- 이후 THREAD_READY로 바꾼다.
- 리스트가 비어있지 않다면
- sleep_list의 첫 요소로 돌아가서 위 과정을 반복한다.
- interrupt를 활성화 한다.
솔루션 참고를 완전히 배제하고 직접 코드를 짜는중인데 진짜 죽을맛이다.
c언어도 별로 안해봤는데 3만줄짜리 코드를 보고 직접 하라고?
