Pintos Project 1 Threads. 소개 및 Alarm Clock

pintos는 스탠포드에서 만든 교육용 OS이며, skeleton 코드만 주어지고 보통 학생이 비어있는 기능들을 채워나가며 과제를 수행한다. 국내외 대학교 중에 이를 운영체제 수업시에 전체 학기 동안 진행하는 과제로 선택하는 경우가 많다.

과제는 크게 Threads, User Program, Virtual Memory, File system으로 나눠진다.

학교에서 운영체제 수업을 들으면서 Threads 일부분, User Program은 전부, VM도 일부 해봤는데 그냥 전체를 다 해보고 싶어서 얼마 전부터 정말 조금씩 하고 있다.

현재 Threads의 일부를 마쳐서 그 내용을 정리하고자 글을 쓴다.

Project1 Threads

이 프로젝트는 세가지 부분으로 나뉜다. 첫째는 Alarm Clock(sleep)의 구현, 둘째는 Priority Scheduling, 셋째는 Multi-level-feedback-queue-scheduling이다.

첫 번째의 경우 현재의 Alarm clock(sleep)은 스레드가 일어날 때까지 busy waiting으로 대기하면서 언제 깨울 지를 기다리는데 이러면 아무것도 하지 않는, 즉 자고 있는 스레드가 CPU를 점유하게 된다. Alarm Clock의 방식을 바꿔서 자고 있는 스레드가 CPU를 점유하지 못하게 해야 한다.

두 번째의 경우 스레드의 Scheduling을 할 때, 우선순위를 부여해서 우선순위가 높은 스레드가 먼저 실행될 수 있도록 해야한다. 이 때, 우선순위가 추가됨에 따라서 생기는 동기화 문제들을 해결해주는 것까지가 목표이다.

우선순위 스케쥴링을 할 시에 우선순위가 낮은 스레드는 절대 실행되지 않는 문제가 발생할 수도 있다. 이를 starvation이라고 한다. 이를 해결하기 위한 스케쥴링방식의 하나로 multi-level-feedback-queue-scheduling이라는 것을 추가로 구현해서 starvation 문제를 해결하는 것이 세 번째 부분이다.

여기까지가 Project 1의 설명이다.

Alarm Clock

위에서 설명했듯이 현재 pintos 내부의 sleep은 busy waiting으로 구현되어 있다. 해당 내용은 devices/timer.c:timer_sleep에서 확인할 수 있다.

timer.c에 있는 timer_sleep

 

timer_sleep은 현재 스레드를 ticks만큼 재우는 역할을 하게 되는 함수이다. timer_elapsed는 인수로 받은 tick과 현재 tick과의 차이를 반환하는 함수가 된다.

즉, 해당 코드는 start로 부터 지난 tick이 ticks보다 작으면 thread_yield를 호출하는 함수가 되겠다.

여기서 thread_yield라는 함수가 무엇을 하는지 이해해야 한다. thread_yield 함수가 호출되면 해당 함수를 호출한 스레드는 다른 스레드에게 CPU를 양보(yield)한다. 그리고 실행될 준비가 되어 있는 스레드들이 존재하는 ready_list에 들어가게 된다.

thread_yield

양보한 스레드가 다시 실행될 타이밍이 되면 thread_yield의 다음 위치부터 실행된다. 따라서 이 코드는 아직 일어날 때가 안됐다면 바로 양보하고를 계속 반복하는 것이다. 그리고 양보해준 다음에 ready_list로 간다.

즉, 일어날 때가 되면 딱 한 번만에 일어나는 것이 아니라 일어날 때가 됐는지 계속해서 확인하는 것이다.

이는 쓸모없는 context switching이 많이 일어난다는 것이고 쓸데 없이 CPU를 많이 점유하고 있는 것이다.

그래서 이를 적절하게 바꿔서 때 되면 한 번만 일어나도록 하는 것이 목표이다.

일단, timer_sleep을 호출하면 CPU를 양보해야 되긴 한다. 자꾸 스레드가 일어날 타이밍인지 확인하는 이유는 자게 되는 스레드를 ready_list에 넣어서이다.

따라서, 자고 있는 스레드들을 ready_list에 넣지 말고 다른 곳에 넣어뒀다가 매 tick마다 거기서 일어날 때가 된 애들을 깨워서 ready_list에 넣는 형식으로 바꿔주면 좋을 거 같다.

자고 있는 스레드들을 보관할 sleep_list를 만들고, timer_sleep이 호출되면 현재 스레드를 thread_yield를 통해 양보하는 것이 아니라 sleep_list에 넣은 뒤에 thread_block으로 ready_list에 들어가지 않도록 해야한다.

깨워야 할 스레드를 찾기 위해 sleep_list의 모든 스레드를 찾아보는 것은 품이 많이 든다. 이를 좀 줄여보기 위해서 sleep_list에 존재하는 스레드들을 wakeup_tick의 오름차순으로 유지하자.

이 내용들을 반영해서 timer_sleep을 바꾼게 아래와 같다.

재우는 과정을 이렇게 바꿈으로 재운 스레드가 ready_list에 자꾸 들어가서 여러번 깨는 것은 막을 수 있다.

이제 깨우는 과정을 구현해야 하는데 이 깨우는 과정은 timer의 tick이 늘어날 때마다 수행해야 한다. ticks가 늘어나는 부분은 timer.c:timer_interrupt이다. 여기에 sleep_list에서 현재 ticks보다 작거나 같은 wakeup_tick을 가진 스레드를 ready_list에 넣어주자.

 

이걸로 Alarm Clock을 좀 더 효율적으로 바꿀 수 있다. 이를 눈으로 확인하는 방법은 alarm-single을 실행해서 idle tick을 확인해보는 것인데, busy waiting일 때는 항상 ready_list에 스레드가 존재해서 idle 스레드가 CPU를 점유하지 못하기 때문에 idle tick이 0인데 반해, 개선한 코드(오른쪽)는 idle tick이 270인걸 확인할 수 있다.

 

위 과정의 실제 코드는 이 링크에서 확인할 수 있다.