개발 목표

- Alarm Clock

개선된 pintos OS scheduler를 제작 기존 pintos는 process state가 Running state와 Ready state만 반복하는 것을 볼 수 있다. Block state를 정의해 줌으로써, 기존의 busy waiting 방식을 개선한다.

-Priority Scheduling

기존 pintos의 round-robin scheduling을 prioirity에 따라 scheduling 해주는 방식으로 바꿔준다. 또한, priority aging을 해줌으로써 priority scheduling의 starvation을 방지해준다.

-BSD Scheduler

BSD Scheduler는 Multi Level Feedback Queue이다. 따라서, MLFQ를 nice, recent_cpu, load_avg value들을 사용하여 구현해준다. pintos kernel은 floating-point 연산을 지원하지 않기 때문에, recent_cpu와 load_avg 연산을 위해 fixed-point format 을 사용한다.
위 3가지를 구현함으로써, pintos scheduling system을 효율적으로 개선한다.

개발 범위 및 내용

개발 범위

Alarm Clock

기존의 Ready state와 Running State만 존재하는 busy waiting 방식에서 block state를 정의해주어 지정된 시간 동안 sleep 상태로 있을 수 있도록 구현한다. thread를 효율적으로 block 상태로 전환할 수 있도록 함으로써, overhead를 줄일 수 있다.

Priority Scheduling

Priority Scheduling을 구현함으로써, readylist에서 priority가 높은 순서로 삽입되고 더 먼저 Running state로 전환될 기회를 준다. 또한, thread aging을 구현해 줌으로써 list내 thread의 priority를 매 tick마다 증가시켜 줌으로써 starvation을 방지해준다. priority와 aging을 기반으로 한 scheduling은 turnaround time을 개선해준다.

Advanced Scheduler

floating-point 연산을 못하는 pintos를 fixed-point를 사용하여 소수점에 대한 연산을 가능하게 만들어준다. 만들어준 함수를 nice, recent_cpu, load_avg, priority를 계산할 때 사용해준다. 위 value들을 일정한 시간마다 갱신해주고, 이 값들을 기반으로 MLFQ를 구현한다. 구현된 MLFQ는starvation방지해주고 turnaround time을 더욱 개선해준다.

개발 내용

Blocked 상태의 스레드를 어떻게 깨울 수 있을까?

test case에서 timer_sleep이 호출될 때 timer_sleep함수 내에서 OS가 boot 될때 생성되는 ticks값을 start에 저장해준다. 그 후 현재 thread의 awake time에 start값과 timer_sleep이 호출될 때 받아온 ticks값(sleep 해야하는 시간)을 더해준다. thread의 awake time 연산을 마친 후 해당 thread를 sleep list에 넣어주고 block state로 만들어준다. block state에 돌입한 thread는 thread_unblock으로 깨워주기 전까지는 sleep list에 block state로 존재한다.이후 매 초마다 timer interrupt가 실행되면, sleep list를 순회하면서 os가 boot될때 시작된 ticks값과 thread_awake_time을 비교하여 일어날 때가 되었다면 unblock 상태로 바꿔주고 ready list에 넣어준다.

Ready list에 running thread보다 높은 priority를 가진 thread가 들어올 경우 priority scheduling에 따르면 어떻게 해야할까?

running thread보다 높은 priority를 가진 thread가 들어올 경우 current thread를 ready state로 바꾼 후 들어온 thread를 running state로 만들어줘야한다. 즉, thread_set_priority로 priority를 바꿔주거나 thread가 create되어서 priority의 순위가 바뀌면 current thread가 yield를 해주고 priority가 가장 높은 thread가 running state로 되어야한다.

Advanced Scheduler에서 priority 계산에 필요한 각 요소

• priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
  advanced scheduler는 매 4ticks 마다 모든 thread의 priority는 위 식으로 다시 계산된다. 이 priority는 0부터 63의 범위를 갖고 priority가 높을수록 우선순위가 높다. recent_cpu와nice을 연산할 때 사용함으로써 cpu를 최근에 사용하지 못한 thread의 우선순위가 높아진다. 이와 같은 방식은 starvation을 방지할 수 있게 해준다.
• recent_cpu = (2 load_avg) / (2 load_avg + 1) * recent_cpu + nice
  recent_cpu로 최근에 사용된 thread의 CPU time을 추측한다. runnint state인 thread는 매 tick마다 recent_cpu가 1 증가하고, 매 TIMER_FREQ마다 모든 state(running, ready, blocked) thread의 recent_cpu가 update된다.
• load_avg = (59/60) load_avg + (1/60) ready_threads
  load_avg는 thread마다 존재하는 것이 아니라 system wide하다. system이 booting 될 때 0으로 시작하며 매 second마다 update 된다. last 60sec 동안 평균 ready_threads 개수를 계산한다. 여기서 쓰이는 ready_threads는 running or ready state의 thread의 수를 뜻한다. ready_threads를 계산할 때 cpu가 실행상태를 유지하기 위해 공회전 되는 thread인 idle thread는 제외한다.
• nice (-20 ~ 20) : 이 값이 높을 수록 priority가 낮아진다
  즉, yield 확률과 비례하는 값이다. recent_cpu를 연산할때 쓰인다.

위 연산식들을 보면, floating-point 연산을 필요로 한다. 하지만, pintos에서는 floating-point연산을 지원하지 않는다. 따라서, fixed-point 연산을 해주는 함수를 pintos manual에 명시되어있는 대로 만들어줘야한다. 따라서, int를 fixed point로 바꿔주는 함수, fixed point를 반올림, 내림하여 int로 바꿔주는 함수, fixed point끼리의 덧셈, 뺄셈, 곱셈, 나눗셈을 연산해주는 함수, fixed point와 int를 덧셈, 뺄셈, 곱셈, 나눗셈을 해주는 함수를 구현하여 사용하였다.

추진 일정 및 개발 방법

추진 일정

10/30 ~ 10/31 : project3 강의 시청, ppt 정독
11/1 ~ 11/3 : alarm clock 구현
11/4 ~ 11/9 : priority scheduling, priority aging 구현
11/10 ~ 11/17 : advanced scheduler 구현

개발 방법

- Alarm Clock

devices/timer.c 파일내의 timer_sleep(ticks)호출 시 내에서 current thread의 thread_awake_time을 ticks(sleep시킬시간) + start(현재시간)로 설정해주고 current thread를 sleep_list에 push해준다. 마지막으로, thread를 block 해준다. 이 때 block 되고 sleep_list에 들어간 thread는 timer_interrupt함수에서 sleep_list를 begin부터 end까지 순회하며 일어날 시간이 된 경우 unblock해주게 만들어준다.

수정하거나 추가해야 하는 자료구조

• sleep_list
  devices/timer.c 파일 내에서 sleep(block) 상태의 thread를 넣어놓는 sleep_list를 만들었다. 생성된 sleep_list는 사용하기 위해 timer_init함수에서 sleep_list를 list_init으로 초기화 해줘야 한다.
• thread_awake_time
  threads/thread.h 헤더파일 내의 strcut thread에 각 thread의 sleep(block)에서 awake(unblock)되어야 하는 시간인 thread_awake_time을 정의 해 주었다.

- Prioirty Scheduling

• thread_yield (수정)
  list_insert_ordered, compare_pri함수를 사용하여 ready_list를 정렬함.
• compare_pri, compate_prio (추가)
  thread.c와 sync.c에 각각 compare_pri, compare_prio 함수를 선언해주었다. 이 함수들은 list_insert_ordered를 사용하여 priority에 맞는 자리에 들어가기 해줄 때 인자로 필요한 함수이다. 두 함수 구성은 같으며, 2개의 thread priority를 비교하여 bool값을 return한다.
• thread_set_priority (수정)
  thread_set_priority 함수에서 running thread의 priority를 new priority로 바꿀 때 ready list의 맨앞(ready list내에서 가장 높은 priority)와 비교하여 작아지면 yield하게 해줬다.thread_create (수정)thread_create함수 에서는 새롭게 thread가 create되면 running thread의 priority와 비교하여 더 높은 priority인 thread가 들어오면 yield 하게끔 해주었다.
• sema_down (수정)
  sync.c파일 내의 sema_down 함수에서 기존의 watiers lists는 fifo방식으로 구현되어있는데, priority에 따라 waiters list도 정렬되게해준다(위 compare_prio함수 사용).
• sema_up (수정)
  sema_up역시 compare_prio함수를 사용해 watiers list 내의 thread들을 priority를 기준으로 sort 해주고 priority가 높은 순으로 unblock 해준다. unblock 해준 thread의 priority가 현재 priority보다 높으면 running state thread를 yield 해준다.
• cond_wait (추가, 수정)
  또한, cond_wait에서 waiters list에 priority가 높은 순으로 list에 insert되도록 위 compare_pri처럼 waiters list의 priority비교를 위해 필요한 cmp_sema_pri함수를 정의해 줬고 list_insert_ordered에 사용하였다.
• cond_signal (수정)
  cond_signal함수 에서도 condition variable에서 기다리는 thread 중 priority가 가장 높은 thread에 signal을 보내기 위해 waiters list를 정렬하는 list_sort를 넣어주었다.
• thread_aging (추가)
  priority aging을 구현하기 위하여 ppt에 추가하라는 source code를 추가해 주었고, priority를 1씩 증가시켜주는 thread_aging함수를 구현하였다.

- Advaned Scheduling

pinots는 floating-point 연산을 지원하지 않기 때문에 fixed-point 연산을 위한 11가지 함수를 pintos manul을 기반으로 구현하였다. (nice, recent_cpu, load_avg, priority 계산때 씀)이 함수들은 새로 만든 alu.h 헤더파일 내부에 구현해주었다.

• n_to_fp: int를 fixed-point로 convert해준다.fp_to_n_round, fp_to_n : fixed-point를 각각 반올림, 내림 하여 int로 convert 해준다.
• add_fp, add_fp_n : 각각 fixed-point끼리의 연산, fixed-point와 int끼리의 덧셈을 해준다.
• sub_fp, sub_fp_n : 각각 fixed-point끼리의 연산, fixed-point와 int끼리의 뺼셈을 해준다.
• mul_fp, mul_fp_n : 각각 fixed-point끼리의 연산, fixed-point와 int끼리의 뺼셈을 해준다.
• div_fp, div_fp_n : 각각 fixed-point끼리의 연산, fixed-point와 int끼리의 뺼셈을 해준다.
• thread_get_nice : current thread의 nice 값을 return해준다. thread_init에서 0으로 초기화한다.
• thread_get_recent_cpu : recent_cpu에 100을 multiply 한 값을 return한다. thread_init에서 0으로 초기화한다.
• thread_get_load_avg : load_avg에 100을 multiply 한 값을 return한다. thread_start에서 0으로 초기화한다.
• load_avg_update : load_avg를 ppt를 기반으로 update 해준다.recent_increase : running thread의 recent_cpu가 1씩 증가하게 해준다.
• recent_cpu_tmp : alu_recent에서 쓰일 함수이다.alu_recent : 모든 thread의 recent_cpu를 update 해준다.
• pri_update_tmp : pri_update에서 쓰일 함수이다.pri_update : 모든 thread의 priority를 update 해준다.
  위 함수들은 제공된 ppt를 기반으로 작성하였다.

수정하거나 추가해야 하는 자료구조

thread.h 파일 내의 struct thread에 MLFQ구현을 위한 recent_cpu, nice를 0으로 선언해준다. load_avg는 system-wide하기 때문에 thread.c에 전역 변수로 선언해준다.

연구 결과

Flow Chart

1. Alarm Clock
   

2. Priority Scheduling
   

제작 내용

1. Alarm Clock

timer.c파일 내에서 block state의 thread를 넣어줄 sleep_list를 만들고 timer_init 함수에서 초기화 해 주었다. 또한, thread.h에 block상태의 state를 다루기 위해 thread_awake_time을 선언해 줌으로써, 기존 pintos의 busy waiting 방식을 ready, block, running 3개의 state로 개선해주었다.

current thread의 thread_awake_time을 ticks(sleep시킬시간) + start(현재시간)로 설정해주고 current thread를 sleep_list에 push해준다. 마지막으로, thread를 block 해준다. 이 때 block 되고 sleep_list에 들어간 thread는 timer_interrupt함수에서 sleep_list를 begin부터 end까지 순회하며 일어날 시간이 된 경우 unblock해주게 만들어준다. 위 과정 중에 interrupt가 없게끔 만들기 위해 intr_disable와 intr_set_level을 사용해주었다.

thread는 timer_interrupt함수에서 sleep_list를 begin부터 end까지 순회하며 일어날 시간이 된 경우 unblock해주게 만들어준다. sleep_list를 순회하는 동안 thread_awake_time이 ticks보다 작거나 같은지 확인해주며 만약 그렇다면 그 thread를 list에서 list_remove해준 후 thread_unblock을 통해 ready state로 바꿔주었다. block state를 이와 같이 관리함으로써 busy waiting(running, ready) 방식에서 3가지 state로 관리하는 방식으로 바꿔주었다.

2. Priority Scheduling

기존 pintos의 round-robin scheduling을 prioirity에 따라 scheduling 해주는 방식으로 바꿔줘야한다.

thread_set_priority 함수에서 running thread의 priority를 new priority로 바꿀 때 ready list의 맨앞(ready list내에서 가장 높은 priority)와 비교하였을 때 작아지면 thread_yield하게 해주었다. 이를 통해 running thread의 priority를 바꿔도 scheduling이 유지된다.

(중간부분 생략)

thread_create함수 에서는 새롭게 thread가 create되었을 때 running thread의 priority(trhead_get_priority() 로 가져온다)와 비교하여 더 높은 priority인 thread가 들어오면 yield 하게끔 해주었다. ready_list의 empty 여부를 list_empty로 확인해줘야지 make check 시 assert warning을 방지할 수 있다.

pintos에서 priority가 높을수록 우선순위를 갖기 땜문에 thread_yield 함수에서 ready_list를 list_insert_ordered함수를 통해 내림차순으로 정렬해주었다. 정렬해준 후 current_thread의 state를 ready state로 바꿔주었다.

yield함수에서 사용한 list_insert_ordered 함수이다. list_less_func *less에 들어갈 함수를 만들었다. 아래에서 설명하겠다.

priority가 높은 순으로 정렬하기 위해 2개의 ready list 내 thread의 priority를 위와 같이 비교해주는 함수를 만들어주었다. thread.c에 구현하여 사용하였다.

priority가 높은 순으로 정렬하기 위해 2개의 waiters list내 thread의 priority를 위와 같이 비교해주는 함수를 만들어주었다. sync.c에 구현하여 사용하였다.

priority-sema 를 pass 하기 위하여 sema_down 함수에서 기존의 watiers lists는 fifo방식으로 구현되어있는데, priority에 따라 waiters list에 삽입되게 해주었다. 위 compare_prio함수와 list_insert_ordered를 사용하였다.sema_up역시 compare_prio함수를 사용해 watiers list 내의 thread들을 priority를 기준으로 list_sort 해주고(waiters list에 있는 동안 priority가 변경되어도 올바르게 정렬해준다.) priority가 높은 순으로 unblock 해준다. sort한 후 watiers list의 front에 있는 thread가 가장 priority가 높기 때문에 해당 thread를 unblock 해준 후 이 thread의 priority가 current thread의 priority보다 높으면 running state thread를 yield 해준다.

thread_tick 함수 내에서 thread_prior_aging이 true일 때 thread_aging 함수로 aging을 구현해주었다. ready_list를 순회하며 내부 thread의 priority를 1씩 증가시켜준다. 만약, aging 도중 priority 최대값인 PRI_MAX(63)을 넘어가면 PRI_MAX로 설정해준다. thread_aging을 구현함으로써 starvation을 방지해주는 scheduling으로 만들어주었다.

채점기준표에는 존재하지 않지만, priority-condvar을 통과하기 위해 sync.c파일 내부 cond_wait, cond_signal 함수를 수정하였다. cond_wait 함수에서 list_insert_ordered 함수를 사용하여 condition var의 watiers list에 priority가 높은 순서로 insert 되도록 해주었고, cond_signal 함수에선 condition var의 watiers list를 priority 순대로 sort하게 해주었다.

3. Advanced Scheduling

thread_mlfqs == true일 때, 즉 mlfq mode 일 때 thread_tick함수 내부에 구현한 코드로, 1sec 에 한번씩 load_avg와 recent_cpu를 update해주고, 4 ticks 마다 priority를 update해주도록 만들어주었다. 여기서 사용한 load_avg_update, alu_recent, pri_update 세 함수는 밑에서 설명하겠다.

load_avg는 system-wide하기 때문에 thread.c에서 전역변수로 만들어주었다.

thread.h파일 내의 struct thread에 선언한 recent_cpu, nice를 thread_init 함수에서 0으로 초기화해주었다. 또한, load_avg 역시 0으로 초기화해준다.

pinots는 floating-point 연산을 지원하지 않기 때문에 fixed-point 연산을 위한 11가지 함수를 pintos manul을 기반으로 구현하였다. (nice, recent_cpu, load_avg, priority 계산때 씀)이 함수들은 새로 만든 alu.h 헤더파일 내부에 구현해주었다.

load_avg를 update 해주는 함수이다. ppt를 기반으로 작성하였다. idle_thread일때는 ready_threads의 수를 세지 않아야하기 때문에 조건문을 집어넣어 주었고, floatint-point 대신 fixed-point 연산을 적절하게 사용해주었다.

nice, load_avg, 그리고 recent_cpu를 get하는 함수를 주석을 바탕으로 만들어주었다. nice value는 그냥 받아오지만, load_avg와 recent_cpu는 fixed-point를 정수로 바꾼 후 받아온다. fp_to_n_round는 반올림 후 fixed-point를 정수로 바꿔준다.

recent_cpu 연산을 위한 함수들이다. recent_increase 함수에서 current thread가 idle thread가 아니라면 1씩 증가시켜주도록 구현하였다.alu_recent는 모든 thread들을 순회하면서 recent_cpu를 update하는 함수이다. recent_cpu_tmp 함수를 사용하여 update를 진행해 주는데, 만약 전달받은 thread가 idle thread 라면 역시 return 해주고 아니라면 제공된 ppt를 기반으로 하고, alu.h 파일 내의 fixed-point 연산 함수들을 사용하여 적절하게 계산해주었다.

최종적으로, 모든 thread의 priority를 update해주는 함수인 pri_update를 구현하였다. 모든 thread를 순회하며 priority를 update해준다. update해줄 때 pri_update_tmp 함수를 사용하였는데, 제공된 ppt를 기반으로 priority를 update 해준다.전달받은 thread가 idle thread 라면 역시 return 해주고 아니라면 제공된 ppt를 기반으로 하고, alu.h 파일 내의 fixed-point 연산 함수들을 사용하여 적절하게 계산해주었다. 연산을 마친 priority가 PRI_MAX보다 높다면 PRI_MAX로, PRI_MIN보다 낮다면 PRI_MIN으로 설정되게끔 해주었다. 또한, priority가 update되어 우선순위가 바뀌었을때 running thread를 yield하기 위해 priority 비교 후 thread_yield 대신 intr_yield_on_return()함수를 호출해주었다. 이 함수는 thread의 priority가 update되는 도중 preemtion해야하는 상황을 대처해준다.

thread_set_nice 함수는 recent_cpu_tmp 함수를 사용하여 recent_cpu를 update 해준 후 ready_list의 가장 앞에있는 thread와 현재 thread의 priority를 비교하고 만약, 현재 priority가 더 작아지면 thread_yield를 호출한다.

개발 중 발생한 문제나 이슈

1. 각각의 함수들에서 list를 참조할때, list_empty함수로 empty check를 하지 않으면 assert error가 뜨는것을 발견하였다. 계속해서 make 자체를 실패하다가 list_empty를 적절하게 전부 집어넣어 줌으로써 해결할 수 있었다.
2. fixed-point 연산을 올바르게 구현하고 사용했다고 생각했지만, mlfqs-nice-10의 pass와 fail을 반복했다. fixed-point와 정수 연산에서 실수가 이루어졌다고 생각해 코드를 계속해서 수정해가며 test 해봤지만, 원하는 ticks에 가까워지지 않고 항상 random으로 값이 나왔다. overflow를 대비해 int로 선언한 nice, recentcpu를 int64로 선언해보았지만 효과가 없었다.완벽하게는 해결하지 못하고 제출할 것 같다.

시험 및 평가 내용

priority-lifo.c 코드 및 priority-lifo 테스트 결과 분석

각각의 thread에 대하여 simple_thread_func을 호출한다. main thread가 256번을 돌면서 자신의 id를 출력하고 다음 thread에게 yield한다. 즉, priority 순서대로 name이 15인 thread부터 0까지 출력된다. 밑 그림은 위 설명대로 출력된 priority-lifo test 결과이다.

make check 수행 결과