5/19일까지 해야할 Pintos - Project1
1. Alarm clock
2. Priority Scheduling
3. Advanced scheduler
1. Alarm clock
수정해야할 파일 => Threads/thread.* , devices/timer.*
busy waiting(spinlock) 방식에서 => sleep/wakeup로 바꾸는 것이 과제다.
현재의 Busy waiting 방식은 계속 cpu 자원 낭비하고 있다.
busy waiting: 특정 조건이 충족할 때까지 계속 조건 검사해서 리소스 소모, CPU 시간 낭비
=> 쓰레드가 준비될 때까지 계속 "너 준비됐니?"라고 묻는 것slee/wakeup: 특정 조건이 충족되지 않았을 때 쓰레드를 sleep, 다른 쓰레드가 실행될 수 있게끔. 조건이 충족되면 자고 있던 쓰레드를 깨워서 작업을 수행하게끔. -> CPU 자원의 효율적인 사용이 가능.
현재 쓰레드가 ticks 시간만큼 시간이 경과할 때까지 while문으로 계속 확인
pintos/src/device/timer.c
void tiemr_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
while (timer_elapsed (start) < ticks)
thread_yield ();
}thread_yield(): yield the cpu and insert thread to ready_list : 현재 쓰레드 cpu 사용 반납, Ready queue에 insert. -> 준비 상태인 다른 쓰레드에게 CPU 양보.timer_ticks(): return the value of the current tick. 현재 타이머 틱의 값 반환.timer_elapsed(): return how many ticks have passed since the start -> 특정 시작 시점으로부터 경과한 타이머 틱의 수 반환.
int64_t timer_elapsed (int64_t then) { return timer_ticks () - then; }
timer tick?
운영 체제에서 시간의 흐름을 추적하기 위해 사용하는 기본 시간 단위
운영체제의 타이머는 일정한 간격으로 틱을 발생 시킴. 틱 신호는 시스템이 정한 기본 시간 간격을 나타냄.
예) 시스템의 타이머 틱이 1ms => 시스템이 1ms 마다 시간의 흐름을 한 단위 측정
짧은 타이머 틱 -> 더 정밀한 시간 측정을 가능 but동시에 더 많은 오버헤드를 발생시킬 수 있음
thread_yield()
현재 쓰레드를 ready_list의 끝에 넣고, 스케줄러 호출하여 다음 쓰레드 실행 시킴.
void thread_yield (void) {
struct thread *cur = thread_current ();
enum intr_level old_level;
old_level = intr_disable();
if (cur != idel_thread)
list_push_back (&ready_list, &cur -> elem);
cur -> status = THREAD_READY;
schedule();
intr_set_level (old_level);
}현재 쓰레드가 idle thread가 아닐 경우, ready_list에 현재 쓰레드 추가.
현재 쓰레드의 상태를 READY로 변경, 다음 쓰레드를 스케줄링. -> ready_list에서 다음 실행할 쓰레드를 선택하고 CPU 넘겨줌.
이전에 저장했던 인터럽트 레벨 복원. 코드 실행 전의 인터럽트 상태로 돌아감.
thread_current(): 현재 실행 중인 쓰레드 정보 반환intr_disable(): 인터럽트 비활성화하고 이전 인터럽트의 상태 return. -> 중요한 데이터를 안전하게 처리, 인터럽트에 의한 방해를 받지 않고 특정 작업을 완료해야 할 때 사용intr_set_level (old_level): 인터럽트 상태 설정하고 이전 인터럽트 상태 Return -> disable한 뒤에 원래 상태로 돌아가기 위해list_push_back(&ready_list, &cur->elem)
:ready_list의 마지막에 insertschedule(): context_switch 수행. 현재 실행중인 쓰레드 중단하고 ready_list에서 다음 쓰레드 선택하여 스케줄링.
idle_thread?
: 시스템의 다른 쓰레드들이 모두 대기 상태일 때 실행되어 CPU가 완전히 유휴 상태가 되지 않도록 하는 역할
-> 시스템의 효율성 유지, 새로운 작업에 빠르게 반응하도록
=> 추후에 테스트 결과에서 idle tick이 많아졌음의 의미는 CPU 작업량이 줄었음을 의미하는 것이다! CPU 자원 소모가 적어짐을 의미하는 것
우리의 과제? => blocked status를 활용해서 timer_sleep() 만들기
sleep_list 사용해서blocked thread 관리하자!
static struct list sleep_list;어디다가 이 Sleep_list를 선언하고, 어디서 초기화할까?
-> thread.c 에서 ready_list와 똑같이 sleep_list를 선언해주고, thread_init할 때 같이 초기화해주었다.
Global tick vs. local tick
Global tick: 시스템 전체에서 사용하는 시간 단위, 커널의 타이머 인터럽트가 발생할 때마다 글로벌 틱 증가하며 시스템의 전반적인 시간 경과 추적
local tick: 각 쓰레드는 깨어날 시간 추적을 위해 자신만의 local tick 유지. 쓰레드가 언제 실행을 재개해야 하는지 결정하는데 사용됨.
구현하기!
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);
//현재 OS의 시간 + 재우고 싶은 시간 => thread_sleep(깨어나야 할 시각)
}
}start=> timer_ticks() 호출 - 현재 시간(시스템이 부팅된 이후부터의 틱 수)
if (timer_elapsed(start) < ticks)
호출된 시점부터 특정 ticks만큼 재우기 위해
start부터 현재까지 경과한 Ticks < ticks(함수에 전달된 대기 시간) 라면 아직 깰 때가 아님! 해당 쓰레드는 깨면 안된다. 재워야 한다.
thread_sleep(start + ticks) 함수 호출
start(현재 시간) + ticks(대기해야 하는 시간)= 쓰레드가 깨어나야 할 시각
thread_sleep()
//sleep해줄 쓰레드 -> sleep_list에 추가
// thread를 block 상태로 만들어줌
void thread_sleep(int64_t ticks) {
struct thread *cur;
enum intr_level old_level;
old_level = intr_disable();
cur = thread_current();
ASSERT(cur != idle_thread);
cur->wakeup = ticks;
//sleep_list wakeup 기준으로 정렬하여서 insert하기
list_insert_ordered(&sleep_list, &cur->elem, compare_thread_ticks, NULL);
thread_block();
intr_set_level(old_level);
}-
커널 영역에서 실행중인 코드가 인터럽트에 의해 방해받지 않도록 Disable해주 고 sleep 이후에 다시 원래 인터럽트레벨로 복원시켜준다.
-
ASSERT(cur != idle_thread): idle_thrad는 CPU가 할 일이 없을 때 실행되는 쓰레드로, 시스템이 놀고 있지 않도록 유지한다. idle thread를 재우는 건 시스템의 정상 작동에 필수적인 쓰레드를 재우는 것과 같아서 이를 방지하기 위해 사용한다. -
현재 쓰레드가 일어나야할 시각 wakeup을 인자로 받은 ticks로 저장해준다.
-
그리고 wakeup 시간을 기준으로 쓰레드를 비교해서 wakeup값이 작은 쓰레드부터 큰 쓰레드 순으로 정렬되도록하는 함수를 만들고,
bool compare_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, elem);
struct thread *thread_b = list_entry(b, struct thread, elem);
if (thread_a ->wakeup < thread_b ->wakeup) {
return true;
}
else return false;
}- sleep_list를 정렬해서 관리해주고 insert한다.
timer_interrupt()
/* Timer interrupt handler.
매 틱마다 쓰레드를 꺠워야할지 재워야할 지 체크하고 awake()*/
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
thread_awake(ticks);
}
타이머 인터럽트 핸들러
: 시스템이 정해진 시간 간격('틱')으로 인터럽트를 발생시켜 현재 시간을 업데이트하고, 필요한 작업을 수행
-> 현재 틱 시간에 기반해서 쓰레드를 깨워준다.
thread_awake()
//일정 시간이 지나 깨어나야 하는 쓰레드들을 sleep_list에서 제거하고 ready 상태로
//blocked 상태인 쓰레드를 꺠워준다.
void thread_awake(int64_t ticks){
enum intr_level old_level;
old_level = intr_disable(); // 인터럽트 비활성화
struct list_elem *e = list_begin(&sleep_list);
while (e != list_end(&sleep_list)) {
struct thread *t = list_entry(e, struct thread, elem);
// e를 인자로 e가 포함된 thread의 포인터 반환
//만약 쓰레드가 깰 시간이 되었다면
//sleep_list에서 쓰레드 제거하고 Unblock()
if (t->wakeup <= ticks) {
e = list_remove(e);
thread_unblock(t);
}
//깰 시간이 되지 않았다면 다음 쓰레드를 깨우려고 함
else {
e = list_next(e);
}
}
intr_set_level(old_level); //이전 인터럽트로 복원
}sleep_list의 처음부터 끝까지 순회하는데,
if (t->wakeup <= ticks)
만약 쓰레드의 wakeup 시간 <= 현재의 틱 시간: 꺨 시간이 다 되었다면 sleep_list에서 해당 쓰레드를 제거하고, thread_unblock함수를 호출하여 쓰레드를 READY 상태로 바꿔준다.
2. Priority Scheduling (1)
현재의 핀토스는 Round-Robin 방식으로 각 쓰레드에게 동일한 시간 할당량을 주고, 이 시간이 지나면 다음 쓰레드로 교체한다.
/* Scheduling. */
#define TIME_SLICE 4 /* # of timer ticks to give each thread. */한편 새로운 쓰레드가 ready_list에 추가될 때는 항상 리스트의 끝에 추가하고, cpu를 할당받을 쓰레드를 ready_list의 앞에서 부터 꺼내는 FIFO 특성을 가진다.
thread_unblock()
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
list_push_back (&ready_list, &t->elem);
t->status = THREAD_READY;
intr_set_level (old_level);
}그냥 list_push_back함수 사용 -> 쓰레드가 도착한 순서대로 Ready_list에 추가되고 있다.
next_thread_to_run
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list))
return idle_thread;
else
return list_entry (list_pop_front (&ready_list), struct thread, elem);
}그리고 그냥 도착한 순서대로 담긴 ready_list의 맨 앞에 있는 쓰레드를 선택해서 FIFO 스케줄링을 하고 있다.
but FIFO 스케줄링은 우선순위가 높은 작업이 도착했을 때 우선순위가 낮은 작업들 뒤에서 대기해야 한다.**
=> 우선순위 스케줄링이 필요하다.
priority scheduling 과제의 목표
- ready list 쓰레드의 우선순위 기준으로 정렬하기
: 가장 우선순위가 높은 쓰레드가 리스트의 맨 앞에 위치하면 스케줄러는 그냥 맨 앞의 쓰레드를 Run시키면 된다.- 동기화를 위한 Sempahore, condition variable 에 대기 중인 쓰레드 wait list 또한 우선순위에 따라 정렬되어야 한다.
preemption: 쓰레드가 ready_list에 추가될 때 현재 실행 중인 쓰레드 보다 더 높은 우선순위의 쓰레드가 추가되면, 현재 쓰레드를 선점하고 더 높은 우선순위의 쓰레드를 run
-> 타이머 인터럽트가 발생할 때마다 선점을 시도하기 보다, 쓰레드가 준비 리스트에 추가될 때 선점해야 불필요한 선점을 줄일 수 있다.
Priority in Pintos
핀토스에서 우선순위는 PRI_MIN(=0) ~ PRI_MAX(=63)
Default priority = 31
구현하기!
thread_yield, thread_unblock
list_push_back()=> list_insert_ordered() 함수를 사용해서 우선순위를 기준으로 ready_list를 정렬하여 insert해준다.
- 현재 실행 중인 쓰레드가 CPU 반환하고 ready_list에 다시 삽입될 때도 우선순위에 따라서 정렬해서 Insert
- 쓰레드가 blocked 상태였는데, ready_list에 insert하고 ready로 바꿀 때도 우선순위로 정렬해서 삽입해야 한다!
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
//우선순위에 따라 쓰레드 정렬
list_insert_ordered(&ready_list, &t->elem, compare_thread_priority, NULL);
t->status = THREAD_READY;
intr_set_level (old_level);
}compare_thread_priority
//쓰레드 간의 우선순위 비교 //thread_A의 우선순위가 더 높다면 True 반환 bool compare_thread_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){ struct thread *thread_a = list_entry(a, struct thread, elem); struct thread *thread_b = list_entry(b, struct thread, elem); if (thread_a->priority > thread_b->priority) { return true; } else return false; }우선순위가 높은 쓰레드가 더 빨리 실행되어야 하니까 compare_thread_wakeup과는 등호가 다르게 함수를 만들어준다.
preempt_thread()
현재 실행 중인 쓰레드와 Ready_list(정렬됐음)의
모든 쓰레드들 중에 가장 우선순위가 높은 쓰레드와 우선순위 비교 해서 yield할지 말지 결정해주는 함수
-> thread_create, set_thread_priority, sema_up 할 때 사용된다.
void preempt_thread(void) {
struct thread *cur = thread_current();
if (cur == idle_thread){
return;
}
if (list_empty(&ready_list)){
return;
}
// list_begin -> list_front로 수정함
// list_begin(): 리스트의 실제 요소에 접근하기 위한 것이 아니라 순회하기 위한 시작점으로 사용(리스트가 비어있을 때도 사용 가능함)
// list_front(): 리스트가 비어있지 않을 때만 사용. 리스트의 첫 번째 실제 요소에 접근할 목적으로 사용됨.
struct thread *ready_thread = list_entry(list_front(&ready_list), struct thread, elem);
//현재 쓰레드가 우선순위가 더 낮다면 yield
if (cur->priority < ready_thread->priority){
thread_yield(); //현재 실행중인 쓰레드 yield
}
}
list_begin: 리스트가 비어있어도 유효한 위치를 반환list_front: 리스트가 비어있지 않을 때 첫 번째 실제 요소를 반환함. 리스트가 비어있는 경우에 사용하면 안된다.
위에서list_empty를 사용해서 ready_list가 빈 리스트인지 확인해주기 때문에 안전하게list_front를 사용할 수 있다.
따라서 정렬된 ready_list의 맨 앞 쓰레드의 priority와 현재 쓰레드의 priority를 비교해서 현재 쓰레드의 우선순위가 더 낮으면 CPU를 반납한다. (선점)
=> 이를
thread_create,thread_set_priority할 때 추가해준다.
새로운 쓰레드가 만들어지거나 쓰레드의 우선순위를 새롭게 세팅할 때는
스케줄러가 현재 실행중인 쓰레드보다 높은 우선순위의 쓰레드가 Ready_list에 있는지 체크하고, 있다면 현재 쓰레드 실행을 멈추고 더 높은 우선순위의 쓰레드로 전환해야 함.
Things I learned:
thread_awake 함수에서 priority scheduling 구현을 위해 만들었던 preempt_thread(): 현재 쓰레드와 ready_list의 맨 앞 쓰레드의 우선순위를 비교해서 현재 쓰레드의 우선순위가 더 낮다면 thread_yield해주는 함수 함수를 처음에 넣어주었었는데
주석 처리를 해도 테스트 통과가 됐어서 의문이 생겼었다.
근데 테스트 케이스는 통과되지만 선점해주는 코드를 넣는다면, 우선순위 비교를 바로 실행할 수 있어서 쓰레드간의 응답시간이 짧아질 수 있을 것이다.
but, context switch가 빈번해져서 시스템 오버헤드가 증가할 수 있을 것이다.
수정이 필요한 부분이 있다면 댓글로 알려주세요
