Pintos
Project 1-1 Alarm Clock
1. Thread 란?
스레드(thread)란 프로세스내에서 실제로 작업을 수행하는 주체를 의미합니다. 모든 프로세스에는 한 개 이상의 스레드가 존재하며, 두개 이상의 스레드를 가지는 프로세스를 멀티스레드 프로세스 라고 합니다.
pintos의 thread lifecycle은 다음과 같습니다.
2. Interrupt 란?
OS에서 커널의 스케쥴링 방식에 따라 커널 스레드가 CPU를 사용하고 있을 때, 다른 스레드에 의해 CPU를 선점할 수 있는지 없는지 여부가 정해집니다. pintos에서는 커널 스레드가 언제든지 선점이 가능한데 이를 Preemptible kernel이라고 합니다. pintos의 스레드 선점은 timer interrupt에 의해 일어나기 때문에 interrupt을 On/Off 함으로써 각 상황에 따라 효율적으로 쓰레드 선점 등을 사용할 수 있게 됩니다.
3. Alarm Clock
Alarm Clock이란?
운영체제(Operating System, OS)는 프로세스들을 재웠다가 일정 시간이 지나면 깨우는 기능이 있는데, 이를 Alarm Clock 이라고 부릅니다.
Pintos의 Alarm Clokc은 Busy Waiting 방식으로 구현되어 있습니다. Busy waiting 방식은 아래와 같습니다. 이러한 방식으로 Pintos의 Alarm Clock은 Busy waiting 방식으로 구현되어 있어서 CPU 점유량이 높아지고 소모 전력이 불필요하게 낭비되어, 전체적으로 OS에게 좋지 않은 방식으로 작동되고 있습니다.
프로세스(이하 주어 생략) 잠이 든다 -> 1분뒤에 깨운다 -> 1분 밖에 안지났네? 다시 잠이 든다 -> 1분뒤에 깨운다 -> 2분 밖에 안지났네? 다시 잠이 든다-> ....... -> 1분뒤에 깨운다 -> N분 밖에 안지났네???
Alarm Clock 개선 방향 및 목표
- 기존 loop기반 busy waiting 방식 대신 sleep/wake up 방식으로 변경
- 스레드 구조체 안에 wakeup_tick을 저장하여 일어날 시간에 대한 정보 저장
- sleep된 스레드를 저장할 list를 선언하고 timer_sleep을 호출하여 스레드를 저장
- wake up 수행 중 timer interrupt가 발생 시 tick을 체크하고 sleep list에서 삭제하고, read list에 추가
// thread 구조체 안에 wakeup_tick 멤버를 추가
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int64_t wakeup_tick; /*추가 깨어나야할 tick을 저장*/ // project 1 - Alarm Clock 추가// 기존의 busy waiting 방식의 코드
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
/*기존 코드 CPU를 계속 점유하게하는 코드
매 tick 마다 sleep -> ready 상태로 바꿔준다*/
while (timer_elapsed (start) < ticks)
thread_yield ();
}기존에 매 tick마다 스레드를 깨우는 방식을 아래와 같은 wakup_tick의 정보를 활용하여 알맞은 시간에 thread_sleep을 호출하여 스레드의 상태를 바꿔준다
//
void
timer_sleep (int64_t ticks) { //int
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
thread_sleep(start+ticks); // project 1 - Alarm Clock 추가
}
/* timer_sleep 에서 thread_sleep을 호출 */
void thread_sleep(int64_t ticks){
struct thread *curr = thread_current ();
enum intr_level old_level;
if (ticks <=0)
return;
else{
old_level = intr_disable (); //이전 interrupt 상태
if (curr != idle_thread){
curr -> wakeup_tick = ticks;
list_push_back (&sleep_list, &curr->elem);
update_next_tick_to_wakeup(ticks);
thread_block();
}
intr_set_level (old_level);
}
}중간에 intr_disable()을 활용하는 이유는 이 함수는 interrupt을 off 시켜줌으로써 외부의 interrupt에 영향을 받지 않고 off 이후의 코드를 실행할 수 있다. 즉 공통으로 사용할 수 있는 자원에 대해서 한쪽 function쪽에서 외부의 interrupt에 의한 사용을 막기 위함.
Alarm Clock을 수정하는데 있어서 수정되었던 코드는 아래와 같다.
- timer_interrupt -> tick이 하나씩 증가하면서 thread_wakeup을 불러온다
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
thread_wakeup(ticks); // project 1 - Alarm Clock 추가
}- thread_wakeup에서는 sleeplist에 있는 스레드들의 wakeup시간을 확인하고 wakeup 시간이 되어있는 경우 sleeplist에서 삭제하고, thread_unblock을 통해 read_list에 넣어준다.
/* project 1 - Alarm Clock 추가 */
void thread_wakeup(int64_t ticks){
struct list_elem * n = list_begin(&sleep_list);
while(n !=list_end(&sleep_list)){
struct thread *wake = list_entry(n, struct thread, elem);
if (wake->wakeup_tick <=ticks){
n = list_remove(n);
thread_unblock(wake);
}
else{
update_next_tick_to_wakeup(ticks);
n = list_next(n);
}
}
}
위와 같이 idle tick가 생긴것을 확인 할 수 있다.
4. Priority(우선 순위) Scheduling
Scheduling 이란
- 스케쥴링은 프로세스사 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미
- 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거침
- 스케쥴링은 CPU나 자원을 효율적으로 사용하기 위해 하는 정책
Scheduling 기법
비선점 스케쥴링
ㄴ 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗을 수 없다.
ㄴ 프로세스가 CPU를 할당 받으면 이를 완료할 때까지 CPU를 선점한다.
ㄴ 비선점 스케쥴링의 종류에는 FCFS, SJF, 우선순위, HRN 등의 알고리즘이 있음
선점 스케줄링 (Pintos 스케쥴링 기법)
ㄴ 하나의 프로세스가 CPU를 할당바당 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 빼앗아 실행한다.
ㄴ 우선 순위가 높은 프로세스를 빠르게 처리할 수 있으나 많은 오버헤드를 초래한다
ㄴ 선점 스케쥴링의 종류에는 라운드로빈, SRT, 선점 우선순위, 다단계 큐 등의 알고리즘이 있음
Priority Scheduling 구현
Pintos에서 Priority Schduling을 구현할 수 있는 방법은 두 가지가 가능하다.\
- ready_list에 push를 할 때 priority의 순서에 따라 push 해주는 방법
- ready_list에서 pop을 할 때 priority가 가장 높은 스레드를 찾아서 pop해주는 방법
첫번째 방법은 ready_list에 저장을 할 때 우선 순위가 가장 높은 스레드를 리스트의 제일 앞에 놓이기 때문에 꺼낼 때 시간이 단축된다. 두번째 방법은 ready_list에 저장할 때는 시간이 적게 걸리지만, pop을 진행할 때에 모든 리스트의 우선 순위를 비교해야하기 때문에 시간이 오래거릴 수 있다. 하지만 추 후에, 우선 순위가 리스트 안에서 변경이 되는 경우가 있어서 오히려 두번째 방법이 나을 수도 있다고 생각이 되지지만, 첫번째 방법을 구현하였다.
pintos lib/kernel/list.c에서 제공하는 list_insert_ordered 함수와 이를 활용하기 위해 추가적으로 함수를 몇 개 구현하였다. list_insert_ordered는 숫자가 작은 순서대로 list에 저장을 해주기 때문에 이함수에 들어가는 매개변수를 수정하여 넣어야 우리가 원하는 우선 순위 높은 순서대로 삽입이 가능하다.
- 위의 less함수를 cmp_priority로 변환하여 코드를 수정하였다.
project 1 - Priority Schedule*/
bool cmp_priority(const struct list_elem *a,
const struct list_elem *b,
void *aux){
return list_entry(a,struct thread, elem) -> priority
> list_entry(b,struct thread, elem) -> priority;
} // a의 우선 순위 쪽이 클때의 True를 반환 할 수 있는 함수- thread_current 즉, running하고 있는 스레드와 read_list에 있는 ready상태의 스레드의 우선순위를 비교하여 running하고 있는 스레드가 우선 순위가 낮을 경우 thread_yield를 통해 ready상태로 바꿔주며, ready에 있었던 우선 순위 높은 스레드는 자연적으로 running으로 바뀌게 된다.
thread_yield함수 위의 idle 스레드가 아닌경우를 체크한 이유는 idle 스레드를 ready상태로 바꿔주면 안되기 때문이다.
void test_max_priority(void){
struct thread *curr = thread_current();
int e = list_entry(list_begin(&ready_list), struct thread, elem) -> priority;
if (curr -> priority < e){
if(curr != idle_thread)
thread_yield();
}
}- thread_yield를 통해 ready_list에 넣어 줄때 우선 순위가 큰 순서대로 list의 제일 앞쪽으로 오게 해준다.
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable (); //이전 interrupt 상태
if (curr != idle_thread) // 현재상태가 가 아니라면
list_insert_ordered (&ready_list, &curr->elem,
cmp_priority, 0);
do_schedule (THREAD_READY);
intr_set_level (old_level); //
}
5. Priority Scheduling-Synchronization
추 후 업로드 예정....
