WIL - PintOS:Project1 / Advanced Scheduler

박상우·2024년 5월 28일
TILWILpintos
0

📝 TIL

목록 보기
35/45
post-thumbnail

⚽️ Main Goal

❗ 큐가 없는 스케줄러처럼 4.4 BSD 스케줄러 MLFQ를 구현 ❗


📈 구현하기

⚙️ 관련 지표의 연산 함수 만들기

구현 단계에서 가장 먼저 해야할 것들이 MLFQ와 관련있는 여러 지표들에 대한 파악과 연산을 구현해야한다.

  • priority 스케줄러가 사용하는 스레드를 먼저 처리할지 확인하는 지표.

    • 0 (PRI_MIN) ~ 63 (PRI_MAX), 31 (Default)

    • 큰 수일수록 빨리 처리되며 작은 수일 수록 늦게 처리됨.

      공식

      priority = PRI_MAX - ( recent_cpu / 4 ) - ( nice * 2 ) // 계산 값을 반올림한 정수를 사용한다.

      Code

      void calc_priority (struct thread* t) {
	int nice = t -> nice;
	int recent_cpu = t -> recent_cpu;

	t -> priority = CONV_TO_INT_NEAREST(PRI_MAX - DIVIDE_X_N( recent_cpu, 4 )) - ( nice * 2 );
}

  • nice

    nice 값이 높을 수록 CPU 시간을 양보하고, nice 값이 낮을수록 다른 스레드의 CPU 시간을 뺏아서 사용한다.

    • 0 : Default Value. 우선순위에 영향을 주지 않는다.

    • -20 : 높은 우선순위를 가진다.

    • 20 : 낮은 우선순위를 가진다.

      Code

      int thread_get_nice (void) {
	enum intr_level old_level;
	old_level = intr_disable (); // 인터럽트 OFF

	int cur_nice = thread_current() -> nice;
	
	intr_set_level (old_level); // 인터럽트 ON

	return cur_nice;
}

void thread_set_nice (int nice UNUSED) {
	enum intr_level old_level;
	old_level = intr_disable (); // 인터럽트 OFF

	struct thread* cur = thread_current();
	cur -> nice = nice;

	calc_priority(cur);
	check_preemption();
	
	intr_set_level (old_level); // 인터럽트 ON

}

  • recent_cpu

    CPU의 각 프로세스들이 ‘최근’에 얼마나 CPU를 받았는지를 측정한 값.

    공식

    recent_cpu = ( 2 * load_average ) / ( 2 * load_average + 1 ) * recent_cpu + nice

    Code

    int thread_get_recent_cpu (void) {
	enum intr_level old_level;
	int cur_recent_cpu;

	old_level = intr_disable (); // 인터럽트 OFF

	cur_recent_cpu = CONV_TO_INT_NEAREST(thread_current() -> recent_cpu * 100);

	intr_set_level (old_level); // 인터럽트 ON

	return cur_recent_cpu;
}

void calc_recent_cpu (struct thread* t) {
	int nice = t -> nice;
	int recent_cpu = t -> recent_cpu;

	t -> recent_cpu = ADD_X_N(MULTIPLY(DIVIDE( 2 * load_avg , ADD_X_N( 2 * load_avg, 1 )), recent_cpu), nice);
}

void increase_recent_cpu (void) {
	if ( thread_current() != idle_thread )
		thread_current() -> recent_cpu = ADD_X_N( thread_current() -> recent_cpu, 1); // 매 tick 마다 recent_cpu 크기 추가
}

  • load_average

    load average는 지난 1분 동안 실행할 준비가 된 평균 스레드 수를 추정한다.

    초기에 OS가 부팅되었을 때, 0값을 가진다.

    공식

    load_avg = (59/60) * load_avg + (1 / 60) * ready_threads

    Code

    void calc_load_average (void) {
	int ready_list_size = list_size(&ready_list);

	// 현재 스레드가 idle_thread 인 경우
	if ( thread_current() != idle_thread) {
		ready_list_size += 1;
	}

	load_avg = MULTIPLY(DIVIDE_X_N( CONV_TO_FIXED(59), 60 ), load_avg)
						+ MULTIPLY_X_N(DIVIDE_X_N( CONV_TO_FIXED(1), 60 ), ready_list_size);
}

int thread_get_load_avg (void) {
	enum intr_level old_level;
	int cur_load_avg;

	old_level = intr_disable (); // 인터럽트 OFF
	
	cur_load_avg = CONV_TO_INT_NEAREST(load_avg * 100);

	intr_set_level (old_level); // 인터럽트 ON

	return cur_load_avg;
}

pintOS 내부에서 recent_cpu와 load_avg는 실수 값을 가진다. 일반적인 실수 연산에서는 대부분 IEEE 표준에 따라 부동 소수점 표현에 따라 실수 연산이 수행된다.
하지만 PintOS 내부에서는 부동 소수점을 처리할 수 있는 물리적인 수준의 지원이나 커널 부분에서의 성능이 제한되기 때문에 실수 연산을 하는 부분에 있어서 고정 소수점을 활용해야한다.
그래서 실수 및 정수 연산에 대해서 사용할 수 있는 매크로를 선언하여 연산에 편의를 더할 수 있다.

/* 고정 소수점을 통한 실수 연산 매크로  */
#define F (1 << 14) // define fixed-point scale factor 2^14
#define CONV_TO_FIXED(n) ((n) * F)
#define CONV_TO_INT_ZERO(x) ((x) / F) // x를 정수로 변환 (0 방향으로 반올림)
#define CONV_TO_INT_NEAREST(x) ((x) >= 0 ? ((x) + F / 2) / F : ((x) - F / 2) / F) // x를 정수로 변환 (가장 가까운 정수로 반올림)
#define ADD(x, y) ((x) + (y)) // x와 y를 더하기
#define SUBTRACT(x, y) ((x) - (y)) // y를 x에서 빼기
#define ADD_X_N(x, n) ((x) + (n) * F) // x에 n을 더하기 (n은 정수)
#define SUBTRACT_X_N(x, n) ((x) - (n) * F) // x에서 n을 빼기 (n은 정수)
#define MULTIPLY(x, y) ((int64_t)(x) * (y) / F) // x와 y를 곱하기
#define MULTIPLY_X_N(x, n) ((x) * (n)) // x에 n을 곱하기 (n은 정수)
#define DIVIDE(x, y) (((int64_t)(x) * F) / (y)) // x를 y로 나누기
#define DIVIDE_X_N(x, n) ((x) / (n)) // x를 n으로 나누기 (n은 정수)

위에서 만들어 놓은 연산들은 OS의 일정 규칙에 따라 주기적으로 연산되어야 한다.

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	if ( thread_mlfqs ) {

		increase_recent_cpu();

		if ( timer_ticks () % TIMER_FREQ == 0 ) { // 1초 (100tick) 마다 priority / recent cpu / load_average 재계산
			recalc_all();
		}

		if ( timer_ticks () % 4 == 0 ) { // 4 tick 마다 우선순위 재계산
			recalc_priority();
		}
	} 

	if ( get_global_ticks() <= ticks ) {
			thread_awake(ticks); //  global tick과 sleep_list의 스레드를 비교, 깨울 스레드는 깨움
		}

}

우선 1초마다 recent_cpu, load_average, prority 를 모두 갱신해준다. 이때 1초는 OS에서 지정해놓은 Tick 수에 따라 결정된다. 여기서는 1초에 100tick으로 지정되어있다.

그리고 4tick 마다 우선순위를 계산해주는 코드도 함께 추가해주어야 한다.


⚙️ all_list 만들기

위의 주기적인 계산은 현재 OS를 구동하면서 생성된 idle thread를 제외한 모든 스레드에 대해서 연산을 수행해야한다. 의미상 ready list, sleep list 내부의 스레드와, OS를 구동하는 main thread, 현재 실행중인 running thread에 대해서 연산을 해주면 되지만 편의상 스레드가 생성될 때마다 생성되는 스레드를 저장하는 all_list를 두어 연산에 활용한다.

그리고 스레드들을 all_list에 사용하기 위해서 새로운 list에 대한 elem 을 선언해주어야한다. 기존의 elem을 사용한다면 원래 사용중인 링크드 리스트에 대해서 삽입/삭제가 중복으로 적용되기 때문에 기존 구현되어있는 실행 과정에 영향을 줄 수 있다.

// thread.c
static struct list all_list; // 모든 생성된 스레드를 저장

...

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

// thread.h
struct thread {
	...
	struct list_elem all_elem;
	...
}

선언된 all_list에 스레드를 삽입할 때도 주의해야한다.

스레드를 선언, 초기화 하는 다양한 함수들이 있는데, 이중에서 테스트에만 사용되거나, OS를 가동시킬 때만 사용하는 함수 등, 특정 상황에서만 구동되는 함수가 있기 때문에 적절한 함수 내부에서 all_list 내부에 삽입할 수 있도록 코드를 짜야한다.

나는 init_thread 내부에서 thread와 관련된 속성들이 모두 초기화 되었을 때, all_list에 push하였다.

static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = priority;
	t->original_priority = priority; // 원래 우선순위를 할당
	t->magic = THREAD_MAGIC;
	t->wait_on_lock = NULL; // LOCK 관련 데이터 초기화
	list_init(&t -> donations);

	/* Put thread in all_list */
	list_push_front(&all_list, &t -> all_elem);
}

반대로 삭제하는 경우에도 적절한 위치에서 삭제해주어야한다.

나는 do_schedule 내부에서 동적 메모리 할당해주었던 스레드에 대해서 할당 해제를 하기 전에, 먼저 all_list에서 제거하고, 메모리 해제가 일어날 수 있도록 코드를 작성해주었다.

static void
do_schedule(int status) {
	ASSERT (intr_get_level () == INTR_OFF); // 인터럽트를 끈다.
	ASSERT (thread_current()->status == THREAD_RUNNING); // 스레드 상태를 스레드 실행 상태로 갱신한다.
	while (!list_empty (&destruction_req)) { // destruction req(삭제 요청) 리스트의 크기를 체크
		struct thread *victim = // 한명씩 꺼내서
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
			list_remove(&victim-> all_elem);
		palloc_free_page(victim); // 메모리 할당 해제 ( 모가지 날림 )
	}
	thread_current ()->status = status; // 현재 스레드 상태 갱신
	schedule (); // 새로운 스케줄 생성
}

위의 방식대로 선언, 초기화, 삽입, 삭제되는 all_list를 대상으로 순회하면서 스레드별 우선순위 함수를 적용해준다.

void recalc_priority (void) {
	for (struct list_elem *e = list_begin(&all_list); e != list_end (&all_list); e = list_next(e)) {
		struct thread *nt = list_entry (e, struct thread, all_elem);
		
		calc_priority(nt); // 우선순위 계산
	}

}

void recalc_all (void) {
		calc_load_average(); // load_average 사용량 계산

	for (struct list_elem *e = list_begin(&all_list); e != list_end (&all_list); e = list_next(e)) {
		struct thread *nt = list_entry (e, struct thread, all_elem);
		
		calc_recent_cpu(nt); // CPU 사용량 계산
		calc_priority(nt); // 우선순위 계산
	}
}

⚙️ 우선순위 적용 조건 추가

MLFQ의 경우 기존 우선순위 스케줄링에서 사용하는 Donation을 고려하지 않는다. 그래서 커멘드 옵션을 통해 전달 받은 thread_mlfqs 인자를 통해서 mlfq를 사용하는 경우 우선순위 donation과 관련된 코드( timer_interrupt, lock_acquire, lock_release, thread_set_priority )를 조건부 실행하도록 한다.

static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	if ( thread_mlfqs ) {

		increase_recent_cpu();

		if ( timer_ticks () % TIMER_FREQ == 0 ) { // 1초 (100tick) 마다 priority / recent cpu / load_average 재계산
			recalc_all();
		}

		if ( timer_ticks () % 4 == 0 ) { // 4 tick 마다 우선순위 재계산
			recalc_priority();
		}
	} 

	if ( get_global_ticks() <= ticks ) {
			thread_awake(ticks); //  global tick과 sleep_list의 스레드를 비교, 깨울 스레드는 깨움
		}

}
void
lock_acquire (struct lock *lock) {
	...
	
	if ( lock -> holder == NULL ) { // 현재 Lock이 없다면 
		lock -> holder = t; //  해당 락의 홀더에 스레드 할당
	}
	else {
		holder = lock -> holder;
		t -> wait_on_lock = lock; // 대기할 Lock을 할당

		if ( !thread_mlfqs ) {
			list_insert_ordered( &(holder -> donations), &t -> d_elem, compare_priority, NULL ); // 스레드와 연관있는 doantions을 우선순위 순으로 정렬
			holder -> priority = get_donation_priority(holder); // lock의 Holder가 가장 높은 우선순위를 양도 받아 스레드에 저장
			donate_nested_priority (holder);
		}
	}

	if ( !thread_mlfqs ) {
		t -> priority = get_donation_priority(t); // 현재 스레드의 우선순위 갱신
		donate_nested_priority (t);
	}

	...
}
void
lock_release (struct lock *lock) {
	...

	if ( !thread_mlfqs ) {

		struct thread *t = lock -> holder;
		
		for (struct list_elem *e = list_begin (&(t -> donations)); e != list_end (&(t -> donations)); e = list_next(e)) {
			
			struct thread *nt = list_entry (e, struct thread, d_elem);
			
			if ( nt -> wait_on_lock == lock ) {
				list_remove(e); // lock과 관련된 donation thread를 donation list에서 제거
			}
		}

		list_sort(&(t->donations), compare_priority, NULL);

		t -> priority = get_donation_priority(t); // 기존 Lock Holder에게 새로운 우선 순위 양도
		donate_nested_priority (t);

	}
	...
}
void
thread_set_priority (int new_priority) {
	if ( thread_mlfqs ) return;
	
	struct thread *t = thread_current();

	t -> original_priority = new_priority; // 스레드의 원래 우선순위를 갱신
	t -> priority = get_donation_priority(t); // 우선순위 양도를 고려한 우선 순위 갱신
	donate_nested_priority (t);

	check_preemption();
}

🎉 결과


profile
박상우
나도 잘하고 싶다..!
이전 포스트

WIL - PintOS:Project1 / Priority Scheduling

다음 포스트

WIL - PintOS:Project 2 / Argument Pass

0개의 댓글

관련 채용 정보