티스토리 뷰

운영체제

[pintos] 1. Alarm System Call

bowbowbow 2016. 4. 22. 18:32
[pintos] Alarm System Call

과제 목표

운영체제는 프로세스를 잠시 재웠다가 일정 시간이 지나면 다시 깨우는 기능이 있습니다. 이 기능을 알람(Alarm)이라고 부릅니다.

Pintos의 알람의 기능은 기존에 Busy Waiting 방식을 이용해서 구현되어 있습니다. 이 방법을 3시간 낮잠자기에 비유하면 아래와 같습니다.

낮잠 자기 시작 -> 1분후 깸 -> 1분 지났네..? -> 다시 자야지 -> 1분후 깸 -> 2분 지났네..? -> 다시 자야지 -> … -> 1분 후 깸 -> 2시간 59분 지났네..? -> 다시 자야지 -> 1분 후 깸 -> 3시간 지났네? 이제 낮잠이 끝났구나…

이렇게 잠을 자면 자는게 자는게 아니겠죠..? 재우는게 미안할 만큼 핀토스의 프로세스는 현재 이렇게 바쁘고 힘들게 잠을 자고 있습니다. 즉 잠자는데 많은 시스템 자원(CPU점유, 소모 전력)을 낭비하고 있습니다.

Alarm System Call 과제의 목표는 핀토스가 고생안하고 정해진 시간 동안 푹자고 일어날 수 있도록 하는 것입니다. 즉 프로세스를 재울 때 시스템 자원 낭비를 최소화하는 것이 입니다.

처음에 핀토스 운영체제에서 프로세스와 스레드를 동일시하는 것을 보고 혼란을 겪었습니다. 왜 그럴까요? 최신 운영체제에서 멀티스레딩의 지원은 너무나 당연하지만 운영체제를 교육할 목적으로 만들어진 핀토스는 프로세스당 하나의 스레드로 구성되어있습니다. 그래서 프로세스와 스레드를 동일시 하여 구현하게 됩니다.

이 문제를 해결하기 위해 먼저 기존의 구현방식인 Busy Waiting을 살펴보고 문제의 해결책은 Sleep / Wake up 구현을 알아봅시다.

Busy Waiting 구현 살펴보기

기존 잠재우기의 구현 코드는 아래와 같습니다.

/* pintos/src/device/timer.c */
void timer_sleep(int64_t ticks){
int64_t start = timer_ticks();
while(timer_elapsed(start) < ticks)
thread_yield(); //현재 CPU점유 다른 스레드에게 양보하고 ready_list 제일 뒤로 이동
}

timer_sleep함수는 현재 스레드를 ticks 시간 동안 잠재우는 함수입니다.

tick(틱)이란 컴퓨터가 켜지고 1ms에 1씩 증가하는 값입니다. 하드웨어에 달린 타이머의해 증가합니다.

이 함수가 호출된 스레드는 while문 내부에 진입합니다. 그리고 스케줄링에 의해 자신의 차례가 올 때 마다 코드가 다시 실행되고 timer_elapsed(start) 함수를 호출합니다.

timer_elapsed(start)는 timer_sleep이 호출된 시점에서 몇 tick이 지났는지를 반환하는 함수입니다. 2.5초 전에 timer_sleep 함수가 호출됬다면 timer_elasped(start)는 2500을 반환합니다.

이 함수의 반환값이 timer_sleep의 인자인 ticks값보다 작으면 thread_yield()를 호출하여 ready list 에 있는 다른 스레드를 위해 CPU 점유를 반환하고 ready list 가장 뒤로 이동합니다. 이 과정은 ticks 동안 반복되고 이러한 방식으로 핀토스는 timer_sleep을 구현합니다.

내용을 이해하기 위해 프로세스 전이 상태 개념을 이해하고 있어야합니다.

푹쉬지 못하고 고생하는 프로세스를 위해 이제 해결책을 마련해줍시다.

Sleep / Wake up

아이디어

Sleep / Wake up 방식은 우리가 아는 상식적인 잠자기 방식입니다. 즉 3시간 낮잠자기로 했으면 푹자다가 3시간 후에 알림 시간 소리를 듣고 일어나는 방식입니다.

이전 방법의 가장 큰 문제점은 편히 자야할 애들(스레드들)을 Ready 상태로 둬서 스케줄링 되게 했다는 것입니다.

상태가 Ready인 스레드는 스케줄링 되어 ready_list에 줄을 서고 자신의 차례가 오면 CPU에 의해 프로세싱 됩니다.

이 문제점을 해결하는 핵심 아이디어는 자야할 애들을 방해받지 않게 Block 상태로 만들고 sleep_list에 넣어두고 깰 시간이 되면 친절하게 찾아가서 다시 Ready 상태로 바꿔주는 것입니다. 이러면 편히 잘 수 있겠죠? 이제 어떻게 구현해야할지 살펴봅시다.

구현

loop기반으로 wating을 하지않으면 각 스레드마다 언제 깨어나야할지에 대한 정보를 각각 가지고 있어야합니다. 이 변수를 thread 구조체에 추가합니다.

/* pintos/src/thread/thread.h */
struct thread{
...
/* 깨어나야 할 tick을 저장할 변수 추가 */
int64_t wakeup_tick;
...
}

이제 잠자는 애들을 모아둘 공간이 필요하겠죠? 이를 위해 sleep_list 구조체를 추가합니다.
또 지금 깨워야할 애들이 없는데 깨우려고 찾아다니면 낭비겠죠? 이 낭비를 막기 위해 잠자는 애들중에 가장 먼저 일어날 친구가 일어날 시각을 변수 next_tick_to_awake를 추가합니다. 그리고 sleep_list를 사용할 수 있도록 thread_init함수에서 sleep_list를 초기화하는 코드를 추가합니다.

/* pintos/src/thread/thread.c */

static struct list sleep_list;
static int64_t next_tick_to_awake;

...

void thread_init(void){
...
list_init (&sleep_list);
...
}

이제 next_tick_to_awake변수를 관리하는 함수를 만들어 줍니다. 이 두 함수는 next_tick_to_awake에 대한 getter와 setter 역할을 합니다.

/* pintos/src/thread/thread.c */

// 가장 먼저 일어나야할 스레드가 일어날 시각을 반환함
void update_next_tick_to_awake(int64_t ticks){
/* next_tick_to_awake 가 깨워야 할 스레드의 깨어날 tick값 중 가장 작은 tick을 갖도록 업데이트 함 */
next_tick_to_awake = (next_tick_to_awake > ticks) ? ticks : next_tick_to_awake;
}

// 가장 먼저 일어나야할 스레드가 일어날 시각을 반환함
int64_t get_next_tick_to_awake(void){
return next_tick_to_awake;
}

이제 스레드를 재워야하겠죠? 재우는 함수 thread_sleep를 구현합니다. 재울 애들은 sleep_list에 추가하고 block상태로 만들어주면 됩니다. 그런데 이 과정에서 인터럽트의 방해를 무시하고 온전히 함수 내부를 실행할 수 있어야하기 때문에 처음에 intr_disable()함수를 통해 인터럽트를 받아들이지 않도록 하고 내부가 다 실행되고 마지막 부분에 다시 intr_set_level(old_level) 함수를 통해 인터럽트를 받아들이도록 합니다.

이때 현재 스레드가 idle 스레드이면 슬립되지 않도록 해야합니다. idle 스레드란 운영체제가 초기화되고 ready_list가 생성되는데 이때 ready_list에 첫번째로 추가되는 스레드입니다. 굳이 이 스레드가 필요한 이유는 CPU가 실행상태를 유지하기 위해 실행할 스레드 하나 필요해서 입니다.

CPU가 할일이 없으면 아얘 꺼져버렸다가 할일이 생기면 다시 켜는방식에서 소모되는 전력보다 무의미한 일이라도 하고 있는게 더 적은 전력을 소모하기 때문입니다.

/* pintos/src/thread/thread.c */

//스레드를 ticks시각 까지 재우는 함수
void thread_sleep(int64_t ticks){
struct thread *cur;

// 인터럽트를 금지하고 이전 인터럽트 레벨을 저장함
enum intr_level old_level;
old_level = intr_disable();

cur = thread_current(); // idle 스레드는 sleep 되지 않아야 함
ASSERT(cur != idle_thread);
//awake함수가 실행되어야 할 tick값을 update
update_next_tick_to_awake(cur-> wakeup_tick = ticks);

/* 현재 스레드를 슬립 큐에 삽입한 후에 스케줄한다. */
list_push_back(&sleep_list, &cur->elem);

//이 스레드를 블락하고 다시 스케줄될 때 까지 블락된 상태로 대기
thread_block();

/* 인터럽트를 다시 받아들이도록 수정 */
intr_set_level(old_level);
}

이제 재우고 sleep_list에 넣어뒀으니 sleep_list에서 꺼내서 깨울 함수가 필요하겠죠? 이 함수가 thread_awake 함수입니다. sleep list의 모든 entry를 순회하면서 현재 tick이 깨워야 할 tick 보다 작다면 슬립 큐에서 제거하고 unblock해줍니다. 크다면 next_tick_to_awake변수를 갱신하기 위해 update_next_tick_to_awake()를 호출한다.

/* pintos/src/thread/thread.c */
//푹 자고 있는 스레드 중에 깨어날 시각이 ticks시각이 지난 애들을 모조리 깨우는 함수
void thread_awake(int64_t wakeup_tick){
next_tick_to_awake = INT64_MAX;
struct list_elem *e;
e = list_begin(&sleep_list);
while(e != list_end(&sleep_list)){
struct thread * t = list_entry(e, struct thread, elem);

if(wakeup_tick >= t->wakeup_tick){
e = list_remove(&t->elem);
thread_unblock(t);
}else{
e = list_next(e);
update_next_tick_to_awake(t->wakeup_tick);
}
}
}

이제 이 네 함수들을 컴파일러가 인식할 수 있게 thread.h에 프로토타입을 선언합니다.

/* pintos/src/thread/thread.h */

//스레드를 ticks시각까지 재우는 함수.
void thread_sleep(int64_t ticks);
//푹 자고 있는 스레드 중에 깨어날 시각이 ticks시각이 지난 애들을 모조리 깨우는 함수
void thread_awake(int64_t ticks);

// 가장 먼저 일어나야할 스레드가 일어날 시각을 반환함
int64_t get_next_tick_to_awake(void);
// 가장 먼저 일어날 스레드가 일어날 시각을 업데이트함
void update_next_tick_to_awake(int64_t ticks);

이제 스레드를 실제로 잠재우는 함수인 timer_sleep가 불렸을 때 반복문을 돌면서 기다는 부분을 지우고 방금 만들어준 thread_sleep함수를 호출하도록 변경합니다.

/* pintos/src/device/timer.c */
void timer_sleep (int64_t ticks)
{
int64_t start = timer_ticks ();

ASSERT (intr_get_level () == INTR_ON);

/*
기존의 busy waiting을 유발하는 코드를 삭제하고
새로 구현한 thread를 sleep list에 삽입하는 함수 호출함
*/

thread_sleep(start + ticks);
}

그리고 timer 하드웨어 의해 매 틱마다 타이머 인터럽트가 걸리는데 그때 timer_interrupt함수가 호출됩니다. 매 틱마다 get_next_tick_to_awake()함수를 통해 현재 깨워야할 스레드가 있는지 정보를 얻고 있다면 thread_awake(ticks) 함수를 호출하도록 합니다.

/* pintos/src/device/timer.c */
static void timer_interrupt (struct intr_frame *args){
...
/* 매 tick마다 sleep queue에서 깨어날 thread가 있는지 확인하여,
깨우는 함수를 호출하도록 함. */

if(get_next_tick_to_awake() <= ticks){
thread_awake(ticks);
}
}

결과

pintos/src/thread 폴더에서 sudo make로 컴파일 후 pintos – -q run alarm-multiple을 실행하면 아래와 같은 결과가 나타납니다.

실행결과실행결과

이 때 idle tick이 pintos를 처음 설치했을 때 처럼 0이 아니라 550값이 출력되었습니다. idle 스레드은 위에서도 설명했지만 CPU 가 아무 할일도 없을 때 실행되는 스레드로 idle tick는 idle 스레드가 실행된 tick수, 즉 시간 입니다. 550 idle ticks 는 idle 스레드가 550ms 실행되었음을 의미합니다.

이 변화는 이전에는 Busy-Waiting 방식이라서 Sleep상태에서도 여전히 CPU가 점유되고 있었고idle 스레드가 실행될 일이 없었으나 Sleep / Wake up 방식으로 변경 한 후 CPU가 잠자는 스레드를 점유하지 않고 idle 스레드를 점유했음을 알 수 있습니다.

즉 프로세스, 스레드가 잠자는 동안 시스템 자원을 낭비하지 않도록 수정하는 과제의 목표를 달성한 것입니다!


댓글
최근에 달린 댓글
Total
Today
Yesterday