기아현상을 방지하기 위해서 스레드의 우선순위 값을 동적으로 변함(priority, nice, recent_cpu, load_avg
기아현상
컴퓨터 시스템에서 자원이 한정된 상황에서 특정 프로세스나 스레드가 필요한 자원을 장기간 동안 할당받지 못하는 상태를 말한다.
주로 자원 스케줄링과 관련된 문제로 발생하며, 우선순위가 낮은 작업이 지속적으로 자원을 할당받지 못하는 경우에 발생.
원인
우선순위가 높은 프로세스가 자원을 독점적으로 사용할 수 있게 되면, 우선순위가 낮은 프로세스는 자원을 할당받지 못하고 계속 기다리게 된다.
여러 프로세스나 스레드가 동일한 자원을 요청할 때, 특정 프로세스가 계속해서 자원을 할당받지 못하는 경우가 발생.
자원을 분배하는 알고리즘이 공평하지 않아서 특정 프로세스에게 자원이 집중적으로 할당되는 경우 기아현상이 발생할 수 있다.
(2 load_avg) / (2 load_avg + 1) * recent_cpu + nice
스레드의 현재 recent_cpu의 100배 (rounded to the nearest integer) 를 반환
(59/60) load_avg + (1/60) ready_threads
현재 system load average의 100배 (rounded to the nearest integer) 를 반환
timer_ticks() % TIMER_FREQ == 0
-20 ~ 20. 임의로 정해준 나이스 값. 이 값이 올라가면 > 우선순위가 낮아지고, 이 값이 낮아지면 > 우선순위가 높아진다. 우선순위와 반비례
PRI_MAX – (recent_cpu / 4) – (nice * 2)
1tick은 10msec (src/thread.c)
연산기 구현
#define F (1 << 14) //fixed point 1
#define INT_MAX ((1 << 31) - 1)
#define INT_MIN (-(1 << 31))
// x and y denote fixed_point numbers in 17.14 format
// n is an integer
int int_to_fp(int n); /* integer를 fixed point로 전환 */
int fp_to_int_round(int x); /* FP를 int로 전환(반올림) */
int fp_to_int(int x); /* FP를 int로 전환(버림) */
int add_fp(int x, int y); /* FP의 덧셈 */
int add_mixed(int x, int n); /* FP와 int의 덧셈 */
int sub_fp(int x, int y); /* FP의 뺄셈(x-y) */
int sub_mixed(int x, int n); /* FP와 int의 뺄셈(x-n) */
int mult_fp(int x, int y); /* FP의 곱셈 */
int mult_mixed(int x, int y); /* FP와 int의 곱셈 */
int div_fp(int x, int y); /* FP의 나눗셈(x/y) */
int div_mixed(int x, int n); /* FP와 int 나눗셈(x/n) */
/* 함수 본체 */
/* integer를 fixed point로 전환 */
int int_to_fp(int n)
{
return n * F;
}
/* FP를 int로 전환(버림) */
int fp_to_int(int x)
{
return x / F;
}
/* FP를 int로 전환(반올림) */
int fp_to_int_round(int x)
{
if (x >= 0)
return (x + F / 2) / F;
else
return (x - F / 2) / F;
}
/*FP의덧셈*/
int add_fp(int x, int y)
{
return x + y;
}
/* FP와 int의 덧셈 */
int add_mixed(int x, int n)
{
return x + n * F;
}
/* FP의 뺄셈(x-y) */
int sub_fp(int x, int y)
{
return x - y;
}
/* FP와 int의 뺄셈(x-n) */
int sub_mixed(int x, int n)
{
return x - n * F;
}
/* FP의곱셈 */
int mult_fp(int x, int y)
{
return (int)((((int64_t)x) * y) / F);
}
/* FP와 int의 곱셈 */
int mult_mixed(int x, int n)
{
return x * n;
}
/* FP의 나눗셈(x/y) */
int div_fp(int x, int y)
{
return (int)((((int64_t)x) * F) / y);
}
/* FP와 int 나눗셈(x/n) */
int div_mixed(int x, int n)
{
return x / n;
}
recent_cpu 값 계산. (2 load_avg) / (2 load_avg + 1) * recent_cpu + nice
구현 전 힌트
void
mlfqs_recent_cpu(struct thread *t)
{
// 해당 스레드가 idle_thread가 아닌지 검사
// recent_cpu계산식 구현(fixed_point.h의 계산함수 이용)
if(t != idle_thread)
{
int load_avg_2 = mult_mixed(load_avg, 2); // load_avg의 2배 값 계산
int load_avg_2_1 = add_mixed(load_avg_2, 1); // load_avg의 2배에 1을 더한 값 계산
int frac = div_fp(load_avg_2, load_avg_2_1); // load_avg의 2배를 load_avg의 2배+1로 나눈값 계산
int tmp = mult_fp(frac, t->recent_cpu); // 위에서 구한 값을 현재 스레드의 recent_cpu 값과 곱한 값 계산
int result = add_mixed(tmp, t->nice); // 위에서 구한 값에 스레드의 nice 값을 더한 값 계산
// result 값이 음수가 되지 않도록 보정
if ((result >> 31) == (-1) >> 31)
{
result = 0;
}
// 계산된 값을 스레드의 recent_cpu 값으로 설정
t->recent_cpu = result;
}
}
load_avg 값 계산. (59/60) load_avg + (1/60) ready_threads
구현 전 힌트
// 평균 cpu 부하를 계산하여 'load_avg' 값을 업데이트('recent_cpu'와 'priority')
void
mlfqs_load_avg(void)
{
// load_avg계산식을 구현(fixed_point.h의 계산함수 이용)
// load_avg는 0보다 작아질 수 없다.
int a = div_fp(int_to_fp(59), int_to_fp(60)); // 59/60 계산
int b = div_fp(int_to_fp(1), int_to_fp(60)); // 1/60 계산
int load_avg2 = mult_fp(a, load_avg); // a * load_avg 계산
int ready_thread = (int)list_size(&ready_list); // read_thread 값 계산
ready_thread = (thread_current() == idle_thread) ? ready_thread : ready_thread + 1;
int ready_thread2 = mult_mixed(b, ready_thread); // b * ready_thread 계산
int result = add_fp(load_avg2, ready_thread2); // load_avg2 + ready_thread2 계산
// load_avg값을 result로 갱신
load_avg = result;
}
recent_cpu 값 1 증가.
구현 전 힌트
// recent_cpu 값 1증가
void
mlfqs_increment(void)
{
// 해당 스레드가 idle_thread가 아닌지 검사
// 현재 스레드 recent_cpu 값을 1증가 시킴
if(thread_current() != idle_thread)
{
int cur_recent_cpu = thread_current()->recent_cpu; // 현재 실행중인 스레드의 'recent_cpu' 값 가져오기
thread_current()->recent_cpu = add_mixed(cur_recent_cpu, 1); // 고정 수소점 값을 인자로 받아 정수값을 더하는 함수
}
}
모든 thread의 recent_cpu와 priority값 재계산
// 모든 스레드의 recent_cpu를 재계산
void
mlfqs_recalc_recent_cpu(void)
{
// 리스트 순회
for (struct list_elem *tmp = list_begin(&all_list); tmp != list_end(&all_list); tmp = list_next(tmp))
{
mlfqs_recent_cpu(list_entry(tmp, struct thread, all_elem));
}
}
// 모든 스레드의 priority를 재계산
void
mlfqs_recale_priority(void)
{
// 리스트 순회
for (struct list_elem *tmp = list_begin(&all_list); tmp != list_end(&all_list); tmp = list_next(tmp))
{
mlfqs_priority(list_entry(tmp, struct thread, all_elem));
}
}
// 모든 thread의 recent_cpu + priority값 재계산
void
mlfqs_recalc(void)
{
mlfqs_recalc_recent_cpu();
mlfqs_recale_priority();
}
mlfqs 스케줄러 일때 우선순위를 임의로 변경x
thread_set_priority (int new_priority)
{
// mlfqs 스케줄러 일때 우선순위를 임의로 변경할 수 없도록 한다.
if(thread_mlfqs) return;
// 1. 현재 실행 중인 스레드 가져오기
struct thread *curr = thread_current();
}
현재 thread의 nice값을 nice로 설정
구현 전 힌트
void
thread_set_nice (int nice UNUSED)
{
// 현재 스레드의 nice 값을 변경하는 함수 구현
// 해당 작업중에 인터럽트는 비활성화
// 현재 스레드의 nice 값 변경
// nice 값 변경 후에 현재 스레드의 우선순위를 재계산 > 우선순위에 의해 스케줄링
struct thread *t = thread_current();
// 2. 인터럽트 비활성화
enum intr_level old_level;
old_level = intr_disable();
// 3. 'nice'값 설정
t->nice = nice;
// 4. 우선순위 재계산 - 'nice' 값이 바뀌었기 때문에.
mlfqs_priority(t);
thread_preemption();
// 6. 인터럽트 복원
intr_set_level(old_level);
}
현재 thread의 nice 값 반환
구현 전 힌트
int
thread_get_nice (void)
{
// 현재 스레드의 nice 값을 반환
// 해당 작업중에 인터럽트는 비활성화.
struct thread *t = thread_current();
enum intr_level old_level;
old_level = intr_disable();
int nice_val = t->nice;
intr_set_level(old_level);
return nice_val;
}
load_avg에 100을 곱해서 반환
구현 전 힌트
recent_cpu에 100을 곱해서 반환
구현 전 힌트
int
thread_get_recent_cpu (void) {
// 해당 과정중에 인터럽트는 비활성화
enum intr_level old_level;
old_level = intr_disable();
int new_recent_cpu = fp_to_int(mult_mixed(thread_current()->recent_cpu, 100));
intr_set_level(old_level);
return new_recent_cpu;
}
1초마다 load_avg, 모든 스레드의 recent_cput, priority 재 계산. 4tick 마다 현재 스레드의 priority 재 계산
구현 전 힌트
// 매 tick마다 깨울 스레드가 있는지 확인.
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
ticks++;
thread_tick (); // 스레드의 우선순위를 관리, 다음 실행할 스레드를 선택하는 역할.
// mlfqs 수정 해야 할 것
/* mlfqs 스케줄러일 경우
timer_interrupt가 발생할때 마다 recuent_cpu 1증가,
1초마다 load_avg, recent_cpu, pririty 계산,
매 4tick마다 priority 계산*/
if(thread_mlfqs)
{
mlfqs_increment();
if (timer_ticks() % 4 == 0)
{
mlfqs_recale_priority();
}
if (timer_ticks() % 100 == 0)
{
mlfqs_load_avg();
mlfqs_recalc_recent_cpu();
}
}
thread_wakeup(ticks); // 일어날 시간이 된 스레드 > ready_list로 이동시키는 함수 호출
}
mlfqs 스케줄러 사용시 priority donation 사용금지
출처 : 카이스트, 한양대 핀토스