퀴즈 회고

핀토스에 영혼을 갈았더니 정작 중요한 개념 공부를 소흘히 해서 퀴즈에서 헷갈리는 게 많았음. 아래에서 정리해봅시다.

멀티프로세싱 vs 멀티쓰레딩

• 프로세스는 독립된 메모리 공간을 사용하므로 전역 변수 등 자원이 공유되지 않는다. 반면 멀티쓰레딩은 한 프로세스 내에서 여러 쓰레드가 실행되므로, 전역변수 등 자원을 공유할 수 있다. 작업 단위 간 자원 공유가 중요하다면 멀티쓰레딩을, 자원 간섭을 차단하고 독립적으로 처리하기 위해선 멀티프로세싱을 선택하는 것이 유리하다.
• 쓰레드는 프로세스에 비해 맥락 전환 시 저장 및 복원해야 하는 상태 정보가 더 적어, 전환 속도가 보다 빠르다. 작업 단위 간 전환이 빈번한 경우 멀티쓰레딩이 더 효율적이다.
• 한 프로세스에선 오류가 발생해도 다른 프로세스에 영향이 없지만, 한 쓰레드가 크래시하면 전체 프로세스가 크래시될 수 있다. 즉 프로그램의 안정성 유지에는 멀티프로세싱이 유리하다.

세마포어 vs 뮤텍스

• 공통점: 세마포어와 뮤텍스는 동기화에 사용되는 전역 변수로, 공유 자원에 동시에 접근하는 작업 단위(쓰레드, 프로세스 등) 사이에서 발생할 수 있는 동시성 문제를 방지하기 위해 사용된다. 한 번에 공유 자원이 존재하는, 임계 구역에 접근할 수 있는 작업 단위의 수를 제한하는 방식으로 동작한다.
• 차이점: 뮤텍스는 공유 자원에 한 번에 한 작업 단위만 접근할 수 있도록 하며, 임계 구역에 진입한 작업 단위만이 락을 해제할 수 있다. 세마포어는 동시에 접근 가능한 작업 단위 수를 설정할 수 있으며, 임계 구역 외부의 작업 단위도 세마포어를 해제할 수 있다.

데드락 (교착 상태)

• 두 개 이상의 작업 단위(쓰레드, 프로세스)가 서로 자원이 해제되기를 기다리면서 영원히 실행되지 않는 상태.
• 예를 들어, 락 L1을 가지고 있는 쓰레드 1이 락 L2를 기다리는 상황에서, 락 L2를 가지고 있는 쓰레드 2가 또 다른 락 L1을 기다리는 경우, 교착 상태가 발생해 두 쓰레드가 모두 실행되지 않는다.

MLFQS (멀티레밸 피드백 큐 스케줄러)

• -mlfqs 들어가면 thread_mlfqs = true 처리되는건 이미 코드상 있음.

  • thread_mlfqs를 가지고 조건문 처리 할 일이 많음.

• 원래는 priority가 0부터 63까지 존재하므로 64개의 큐를 준비해서 구현하는 게 정석이지만

  • 하나의 큐를 이용하고, 우선순위 할당 방식만 MLFQS 식으로 바꿔줘도 테스트 케이스는 모두 통과할 수 있음
  • 깃북 FAQ를 보니까 동작만 동일하면 큐를 1개 쓰든, 여러 개 쓰든 문제 없다고 언급했고...

• 그래서 일단 한개의 큐 (현재의 ready_list)로 먼저 만들어 보고, 시간 남으면 여러 큐를 만들어 보기로 함.

해야 됐던 일들

• [구현 4-0] load_avg 전역변수 추가

• [구현 4-1] struct thread에 구조체 멤버 추가

  • int nice, int recent_cpu
  • thread initialisation 할 때 초기값 설정 필요 (init_thread)

• [구현 4-2] mlfqs 사용 시 thread_set_priority 비활성화

  • if (thread_mlfqs) return; 으로 바로 반환하게 하면 됨

• [구현 4-3] mlfqs 사용 시 lock_acquire, lock_release의 priority donation 비활성화

  • if (!thread_mlfqs)일 때만 priority donation이 실행되도록 코드를 수정하면 됐음

• [★★구현 4-4★★] priority 계산을 위한 함수 만들기

  • 이 부분이 복잡했음. 핀토스에는 부동소수점을 저장할 수 있는 방법이 없어, 조금 특이한 방식으로 정수를 부동소수점 형태로 변환한 뒤 int에 저장해야 했음... 매크로 함수로 미리 필요한 부분을 정의하니까 조금 더 수월했음.

• 정수형과 정수형 간 계산은 기존처럼 해도 됨

  • 예외적으로 정수형과 정수형의 나눗셈 연산은, 둘 다 부동소수점으로 바꿔준 뒤 위 표와 같이 계산

• 하지만 정수형/부동소수점 or 부동소수점 간 계산은 아래와 같은 특이한 형태로 진행해야 함

  • 위 사진에서 x, y는 부동소수점, n은 정수형

• 정수형이든 부동소수점이든 int에 저장함에 유의

  • 대신 테스트 케이스에서 부동소수점으로 저장된 경우, 1 << 14로 나누어 정수 형태로 바꾸어주어야 했음
  • 설명하기 뭐하다... 아래 코드 보고 따라오십쇼.

• 암튼 만들어야 하는 건

  • recent_cpu를 1 증가시키는 함수. (매 틱)
  • load_avg를 재계산하는 함수. (매 초)
  • load_avg = (59 / 60) * load_avg + (1 / 60) * ready_threads
  • recent_cpu를 재계산하는 함수. (매 초)
    • recent_cpu = (2 * load_avg)/(2 * load_avg + 1) * recent_cpu + nice
  • priority를 재계산하는 함수. (매 타임슬라이스)
    • priority = PRI_MAX - (recent_cpu / 4) - (nice) * 2 후 인접정수로 내림.\
  • 혹시 모를 일을 방지하기 위해 thread_mlfqs가 참일 때만 실행.

#define CALC_F (1 << 14)
#define FLOAT(n) ((n) * (CALC_F))   // 정수 n -> 부동소수점 반환
#define INT(x) ((x) / (CALC_F))     // 부동소수점 x -> 정수 반환
#define MUL_FLOATS(x, y) (((int64_t)(x)) * (y) / CALC_F)  // 부동소수점 간 곱셈
#define DIV_FLOATS(x, y) (((int64_t)(x)) * CALC_F / (y))  // 부동소수점 간 나눗셈

void recent_cpu_up_one(void){
	// `recent_cpu`를 1 증가시키는 함수.
	// recent_cpu는 fixed-point.
	if(thread_mlfqs){
		(thread_current() -> recent_cpu) += 1 * (CALC_F);
	}
}

void calc_load_avg(void){
	// `load_avg`를 재계산하는 함수.
	// load_avg는 fixed point, ready_threads는 integer
	if(thread_mlfqs){
		int ready_threads = list_size(&ready_list);
		if (thread_current() != idle_thread){
			ready_threads += 1;
		}
		//printf("ready_threads %d, load_avg %d\n", ready_threads, load_avg);
		load_avg = (MUL_FLOATS(DIV_FLOATS(FLOAT(59), FLOAT(60)), load_avg) + DIV_FLOATS(FLOAT(1), FLOAT(60)) * ready_threads);

	}
}

void calc_recent_cpu(struct thread *t){
	// `recent_cpu`를 재계산하는 함수
	if(thread_mlfqs){
	// load_avg, recent_cpu, decay도 fixed point. nice는 integer.
	int decay = DIV_FLOATS(2 * load_avg, 2 * load_avg + CALC_F);
	int result = MUL_FLOATS(decay, t -> recent_cpu) + FLOAT(t -> nice);
	t -> recent_cpu = result;
	}
}

void calc_priority(struct thread *t){
	// `priority`를 재계산하는 함수
	if(thread_mlfqs){
	// priority, nice는 integer. recent_cpu는 fixed point.
	t -> priority = INT(FLOAT(PRI_MAX) - (t -> recent_cpu / 4) - FLOAT(t -> nice * 2));
	}
}

• [구현 4-4A] running, ready, blocked 상관없이 모든 쓰레드 대상으로 값을 갱신하는 함수 만들기

  • 모든 쓰레드의 priority 재계산하는 함수.
    • running, ready, blocked 모두. -> blocked는 어떻게 해??
  • 모든 쓰레드의 recent_cpu 재계산하는 함수.
    • running, ready, blocked 모두. -> blocked는 어떻게 해??
  • blocked까지 모든 쓰레드를 계산할 수 있게 하기 위해, 모든 쓰레드를 포함하는 리스트 all_list를 만들어 사용
    • 넣을 struct list_elem으로는, donation 안 하면서 남아도는 d_elem을 그대로 사용함.
    • thread_init 함수에서 main 쓰레드를 만든 뒤, all_list에 삽입
    • 이후 thread_create에서 새로운 쓰레드가 만들어지면 삽입
    • thread_exit에서 쓰레드를 없애는 경우 삭제
  • 이후 all_list를 순회하면서 recent_cpu, priority를 갱신하자.

• [구현 4-5] set, get 함수 몇 개 만들기

  • void thread_set_nice(int nice UNUSED): 현재 쓰레드의 nice 설정
    • nice value를 바꾸고, priority를 재계산. 여기서도 현재 쓰레드의 priority가 낮아지면 yield해야 함.
  • int thread_get_nice(void): 현재 쓰레드의 nice 반환
  • int thread_get_load_avg(void): load_avg * 100 반환. 이때 1 << 14로 나누어 정수형으로 변환해야 해야 테스트 케이스에서 잘 채점됨.
  • int thread_get_recent_cpu(void): recent_cpu * 100 반환. 이때 1 << 14로 나누어 정수형으로 변환해야 해야 테스트 케이스에서 잘 채점됨.

int thread_get_load_avg (void) {
	return INT(load_avg * 100);
}

int
thread_get_recent_cpu (void) {
	return INT(thread_current() -> recent_cpu * 100);
}

• [구현 4-6] timer_interrupt 함수에서 멤버를 갱신하게끔 설정
  • 실행되는 쓰레드의 recent_cpu: 매 틱마다 1씩 더함.
  • 모든 쓰레드의 load_avg, recent_cpu: timer_ticks () % TIMER_FREQ == 0 (매 초) 일 때 재계산
  • 모든 쓰레드의 priority 재계산: timer_ticks () % 4 == 0 (매 4 * 틱)일 때 재계산
  • 앞서 만든 함수들을 쓰자!

/* [구현] Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;


	// [구현 4-7] timer_interrupt마다 갱신할 멤버들 생신
	//enum intr_level old_level;
	//old_level = intr_disable();
	if(timer_ticks() % 4 == 0){
		// 모든 쓰레드의priority 재계산
		calc_all_priority();
	}
	recent_cpu_up_one();
	if(timer_ticks() % TIMER_FREQ == 0){
		calc_load_avg();
		calc_all_recent_cpu();
	}


	thread_tick ();


	// 깨울 쓰레드 찾고, 실제로 깨우기
	wake_up(ticks);
}