[TIL / WIL] [Project 1] MLFQS + Advanced Scheduler in PintOS

이해에 도움이 되었던 참고 페이지

https://web.stanford.edu/class/cs140/projects/pintos/pintos_7.html#SEC131

MLFQS

목표

반환 시간의 최적화 | 짧은 시간을 먼저 실행시키자! 그런데 실행 시간의 정보를 어떻게 알 수 있지?

응답 시간의 최적화 

 

이 목표를 이루려면 프로세스에 대한 정보가 필요하다. 따라서 실행 중인 작업의 특성을 알아내고 스케쥴링에 사용하자.

 

특징

• 우선순위(priority level)이 다른 여러 개의 큐로 구성되고, 높은 우선순위를 가진 큐에 존재하는 작업이 선택될 가능성이 높다. 
• 각각의 큐엔 둘 이상의 작업이 존재할 수 있고, Round Robin 스케쥴링 알고리즘이 사용되어 작어이 처리된다. 
• 우선순위를 작업의 특성에 따라 동적으로 부여한다. 

규칙

1. 우선순위가 높은 작업이 먼저 실행된다.
2. 우선순위가 같을 때 RR 로 실행된다.
3. 작업이 시스템에 진입할 때 가장 높은 우선순위(맨 위의 queue)에 삽입된다. 
   • 작업의 길이를 알 수 없기 때문에 일단 짧은 작업이라고 가정하고 높은 우선순위를 부여한다.
   • 정말 적다면 빠르게 실행되고 곧바로 종료된다.
   • 아니라면 점점 아래의 큐로 이동한다.
4. 작업을 마치면(=타임 슬라이스를 모두 사용한다면) 우선순위가 낮아지고, .타임 슬라이스를 소진하기 전에 CPU를 양도한다면 우선순위를 유지한다. -> [개선] 타임 슬라이스의 시간을 모두 소진하면 CPU의 양도 여부에 상관 없이 아래 단계의 큐로 낮아진다(우선순위가 낮아진다.)
   • 대화형 작업(키보드 입출력 같은 것들)시에는 타임 슬라이스를 전부 소진하기 전에 CPU를 양도한다(입출력은 짧으니까!). 따라서 대화형 작업은 높은 우선순위를 유지하여, 응답 시간을 최소화할 수 있다. 
5. 일정 시간이 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다.
   • 그런데 이 경우에는 일정 시간의 길이를 정하는 것이 관건이다. 너무 크면 긴 실행 시간을 가진 작업은 기아 현상에 시달리고, 너무 적으면 대화형 작업(입출력 등)이 적절한 양의 CPU를 사용하지 못한다.

예상되는 문제점 (1-5번 규칙만 있을 때)

기아 상태(starvation)

입출력 작업이 매우 많다면, 그렇지 않은 작업들을 처리할 수 업게 된다. (계속해서 양보하고, 계속해서 높은 우선 순위를 유지할 것이니까.)

CPU 독점 가능성

인위적으로 타임 슬라이스를 양도하도록 입출력 요청을 한다면 특정 파일이 CPU를 거의 독접하게 될 수 있다. 

 

스케쥴러 [기타]

일부 스케쥴러는 OS 작업을 가장 높은 우선순위로 예약해둔다.

일반적인 유저 프로그램은 시스템 내에서 높은 우선순위를 얻지 못한다.

그러나 nice 와 같은 도구로 작업의 우선순위를 조정할 수 있다.

FreeBSD 

pintOS에서 구현하는 4.4BSD와 유사한 스케쥴러의 이전 버전은 작업의 현재 우선순위를 계산하기 위해 수학 공식을 사용한다. 프로세스가 사용한 CPU시간을 계산하고, CPU를 사용한 이후의 시간이 지난 만큼 감쇠하여 우선순위 상향에 사용한다.  

 

 

MLFQS | Advanced Scheduler in PintOS

https://casys-kaist.github.io/pintos-kaist/project1/advanced_scheduler.html

Implement a multilevel feedback queue scheduler similar to the 4.4BSD scheduler to reduce the average response time for running jobs on your system.

 

이 스케쥴러는 우선 순위를 기부하지 않는다! 따라서 이전 까지 구현했던 것과 다른, mlfq 방식으로 작동하는 코드를 분리하여 만들어야 한다. pintOS는 일반적인 mlfq와 다른 4.4BSD 스케쥴러를 구현한다.

일반적인 mlfq와 다르게 구현한 부분들

• 큐(리스트)를 여러 개 만들지 않고, priority 를 0에서 63까지 범위로 사용하여 멀티 레벨과 유사하게(?) 구현한다.(그런데 다른 호실의 다른 팀들은 정말로 64개의 큐 리스트를 만들어서 한 팀이 있다고 들었다!)
• 4.4BSD의 decay 개념을 사용하여 동적으로 프로세스의 우선 순위를 조정했다. 

Decaying threads in sleep list

blocked된(sleep중인) thread의 감쇠(decay)

thread의 균형잡힌 스케쥴링을 위해서, pintOS의 advanced schedule 섹션에서는 4.4BSD scheduler를 사용한다.

 

I/O 을 담당하는 threads는 input과 output을 위해서는 빠른 반응을 요구하지만 cpu를 점유하는 시간 자체는 짧으면 된다. 그러나 compute-bound thread는 많은 CPU시간을 요구하지만 빠른 반응 시간을 요구하지 않는다. 그 사이에 있는 다른 스레드들은 요구하는 시간들이 제각각이다.

 

이런 thread의 요구조건을 scheduler가 미리 알 순 없으므로 thread의 사용량으로 이것을 예측하는 공식을 세운다. 그 인자로는 system-wide한 load_avg와 각각의 threads마다 가진 recent_cpu, 그리고 얼마나 잘 양보하는 속성을 가졌는지의 지표인 nice를 세팅해 사용한다.

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
//아직 load_avg는 보이지 않는데, load_avg는 recent_cpu 내부에서 계산된다.

recent_cpu

recent_cpu = decay * recent_cpu + nice

• 특정 thread가 cpu를 점유한 시간동안 증가하며, 스케쥴러가 이 thread의 사용 경향을 계산하는 지표.
• 각각의 프로세스가 "최근에" 사용한 CPU 시간이 얼마나 되는지에 따라 결정되는데, 어떤 스레드가 더 많이 CPU를 사용할수록 recent_cpu의 가중치가 무거워진다. 왜냐하면 timer interrupt가 하나 발생할 때마다 1씩 recent_cpu를 올려 가중시키기 때문이다. 또한 decay를 통해 매초마다 recent_cpu를 감소하며, nice를 통해 조정한다.

nice

얼마나 잘 양보하는 속성을 가졌는지의 지표. 양수와 음수 값을 가지는데, 높을 수록 우선순위를 빠르게 낮춘다.

decay(감쇠) 와 load_avg

load_avg = (59/60)*load_avg + (1/60)*ready_threads
decay = (2 * load_average) / (2 * load_average + 1)

• load_avg: 최근 1분 동안 수행이 준비된 작업의 평균치로 Exponentially Weighted Moving Average(지수 가중 평균, EWMA) 방식으로 계산되었다. 이 방식은 기하급수적으로 가중치가 부여되며 최근 관측치가 이전 관측치보다 더 연관성이 높을 때 사용한다.(EWMA analyze data points over a specific time period, with more recent data points receiving greater weight.)
• 시간의 흐름에 따라 오래된 데이터가 미치는 영향을 지수적으로 감소(decay)
• 대기하는 스레드가 많을수록 load_avg의 값이 증가하고, 대기하는 스레드가 없다면 줄어든다.대기하는 스레드가 많다는 건 현재 시스템에 더 많은 부하가 걸린 상태라고 볼 수 있다.
• ready thread의 개수에 영향을 받지만((1/60)*ready_threads) 기존 값을 유지((59/60)*load_avg)하는 쪽에 가깝다.
• 무거운 부하가 걸릴수록 decay의 값은 1에 가까워지고 recent_cpu의 값이 커져 현재 스레드의 priority가 낮아져 thread교환이 이루어질 가능성이 커진다. 결과적으로 최근에 CPU 시간을 받은 스레드가 우선순위를 낮게 부여되게 되고, 최근 CPU 시간을 받지 않은 스레드의 최근 CPU는 0이 됨,

각 요소는 갱신 되는 시간이 다르다.

 

언제 무엇을?	load_avg	recent_cpu	priority
증가 increase		1 tick (실행중일 때)	4 tick
재계산 recalc	1 sec	1 sec	4 tick

sleep 중인 스레드의 recent_cpu도 계산 해야 하는가?

blocked되거나 sleep하게 되어 sleep list로 따로 관리되고 있는 thread의 recent_cpu와 우선순위도 갱신해 주어야 한다. 개인적으로는 '스레드가 잠들어 있다면 변화가 없을 것이다' 라고 생각 했는데, 오류가 떠서 생각을 해보니...

1. load_avg가 특정 스레드에만 적용되는 것이 아니고 전역변수로서 선언되는 system-wide한 요소이자 시스템 전체의 부하를 측정하는 변인이며,
2. 이것이 적용되는 decay는 시간의 흐름에 따라 오래된 과거의 데이터가 미치는 영향을 감소시키는 요소로 사용되었으니

sleep list에 있다 하더라도 잠든 스레드의 우선순위에도 영향을 미칠 것 같다' 는 생각이 들었다.

그 외, 이번 주에 겪은 문제와 해결

멀쩡했던 priority donate lower의 상태가..?

thread_mlfqs로 if문 분기 처리 시 중복하여 priority를 갱신하는 이슈 : 어떤 기능을 추가하여 특정 변수를 트리거로 if문을 추가할 때 중복 처리될 수 있음을 교훈으로 얻음

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {

	struct thread* curr = thread_current ();
	// [ project1-B : Donation ]
	if(! thread_mlfqs) {
		if (curr->priority == curr->original_priority) {
		curr->priority = new_priority;
		curr->original_priority = new_priority;

		} else {
			curr->original_priority = new_priority;
		}

	}

	///////////////////////////////////////////////////
	// if(thread_mlfqs){
	// 	curr->priority = new_priority;
	// }
	curr->priority = new_priority;  //if문을 나오고 다시 한번 더 갱신하여 오류 발생
	thread_switch();
	///////////////////////////////////////////////////
}

실수(fixed point)와 정수 연산

#define F (1 << 14)     //fixed point 1
int int_to_fp(int n) {
    return n * F;
}

int fp_to_int_round(int x) {
    if (x >= 0) return (x + F / 2) / F;
    else return (x - F / 2) / F;
}

int fp_to_int(int x) {
    return x / F;
}
int add_fp(int x, int y) {
    return x + y;
}
int sub_fp(int x, int y) {
    return x - y;
}
int add_mixed(int x, int n) {
    return x + n * F;
}
int sub_mixed(int x, int n) {
    return x - n * F;
}
int mult_fp(int x, int y) {
    return ((int64_t) x) * y / F;
}
int mult_mixed(int x, int n) {
    return x * n;
}
int div_fp(int x, int y) {
    return ((int64_t) x) * F / y;
}
int div_mixed(int x, int n) {
    return x / n;
}

pintOS에서 실수 값을 표현하기 위해 사용한 fixed point는 실수 값을 가정한 정수이고, 따라서 연산에 주의해야 한다. 특히 실수(정수로 표현됨)과 정수의 연산 시 정수를 실수화(fixed point로 변환)를 하지 않는 경우 굉장히 작은 값으로 처리가 된다. 이것을 이해하는 게 중요했다.

//example

int a = (59/60)*load_avg // 0
int b = div_fp(int_to_fp(59), int_to_fp(60))*load_avg // 16110

// 59*(1<<14) or 60*(1<<14) 의 차이.

여담으로 가끔 꽤 큰 마이너스 값이 나오는데, fp의 최상위 비트가 계산 중 오염되어서 sign bit가 0이어야 되는게 1이 되는 것이 아닌가 하는 추측을 한 친구가 있었다.

fixed pointreal airthmetic

이번 프로젝트에서 pintOS는 recent_cpu와 load_avg의 real number를 표현하기 위해 fixed pointreal airthmetic을 사용한다. 즉, Kernel 에서 floating-point arithmetic을 지원하지 않는다.왜냐하면 부동소수점 연산은 무한에 가까운 실수를 표현하기 위해 많은 메모리와 시간을 소모하여, 커널을 더 복잡하고 느리게 만들기 때문이다. 즉 일정 부분의 정확도를 포기하여 빠른 연산과 오버헤드가 발생하지 않는 안정성을 획득하기 위해서 부동소수점(fixed point) 연산을 사용한다.

여기서 오버헤드가 발생한다는 것이 무슨 뜻일까? 공룡 책(Operationg System concept)에서 찾아보니 스케쥴러가 context switching을 할 때 이전 프로세스의 레지스터의 정보들을 저장한다고 한다. 그런데 부동 소수점 레지스터는 별도로 관리되고 저장되는데 이것이 오버헤드를 발생시킨 것 같다.

OSR community의 한 게시글에서는 부동소수점을 사용한 연산 시 사용하는 FPU라는 프로세서의 상태를 저장하는 것이 엄청난 비용이 드는 작업이라고 한다. 그래서 과거에 이 비용을 포기하고 부동소수점 연산을 하지 않는 방향으로 커널을 설계했고, 지금까지도 그렇게 쓰고 있다는 듯 하다. 심지어 80387/80386(?) 까지는 부동소수점을 계산할 수 있는 산술 보조 프로세서가 따로 분리되어 나왔던 모양이다.

	부동소수점 연산	고정소수점 연산
특징	정확함	일정 부분 정확도를 희생
	시간과 메모리를 많이 차지함	연산이 빠르고 메모리를 덜 차지함
		제한된 정밀도지만 빠르고 간단한 하드웨어로 구현 가능
사용처		커널 수준 프로그래밍, 임베디드...

정확도와 크기 / 시간과 메모리의 오버헤드... 두 연산 방식 간에 tread off가 있다

 

• 요약하자면 pintOS에서는 커널 수준에서 recent_cpu와 load_avg가 다루는 실수(real number)연산을 정확도를 어느정도 포기하고 빠른 속도와 안정성을 챙기는 부동소수점 연산을 통해 처리한다. 
• 부동소수점 연산은 이 연산을 처리할 때, 실제 소숫점 자리 등을 표기할 수 없으므로 shift 연산을 통해 거대한 정수(1이 2의 14승이다, 이 경우에서는)로 소수점 자리까지 어느정도 보장하여 표현한다.
• 이러다 보니 정수 연산을 할 때 이 정수를 부동소수점화(化) 하여 처리하지 않는다면 오류가 발생한다. 가령 59/60을 (정수)59/(정수)60을 한 뒤, int 타입 처리를 한다면(int로 처리해야 계산이 가능하기 때문) 0이 되어 제대료 표현할 수 없고, 이것이 priority에게까지 영향을 끼쳐 제대로 된 스케쥴링이 불가능하다.

so what?

이럴 때 해결책으로는 여러가지 방법이 있을 수 있다.

• 연산은 무조건 fixed point로 처리하는 원칙 세우기
• 변수명 등을 지을 때 int/fp로 구분하여 읽기 쉽게 만들기
• typedef로 fixed point관련 타입을 정의하여 다루기

Operationg System concept

A range of extra hardware support was included in this release. Although still restricted to the Intel PC platform, hardware support had grown to include floppy-disk and CD-ROM devices, as well as sound cards, a range of mice, and international keyboards. Floating-point emulation was provided in the kernel for 80386 users who had no 80387 math coprocessor. System V UNIX-style interprocess communication (IPC), including shared memory, semaphores, and message queues, was implemented. (p777)

이 릴리스에는 추가적인 하드웨어 지원이 포함되었습니다. 여전히 인텔 PC 플랫폼에만 제한되어 있지만 하드웨어 지원은 플로피 디스크와 CD-ROM 디바이스, 사운드 카드, 다양한 마우스, 국제 키보드를 포함하도록 성장했습니다. 80387 수학 보조 프로세서가 없는 80386 사용자를 위해 커널에서 부동 소수점 에뮬레이션이 제공되었습니다. 공유 메모리, 세마포어, 메시지 큐를 포함한 시스템 V 유닉스 스타일 프로세스 간 통신(IPC)이 구현되었습니다. (p777)

 

Scheduling context: The most important part of the process context is its scheduling context — the information that the scheduler needs to suspend and restart the process. This information includes saved copies of all the process’s registers. Floating-point registers are stored separately and are restored only when needed. Thus, processes that do not use floating-point arithmetic do not incur the overhead of saving that state. The scheduling context also includes information about scheduling priority and about any outstanding signals waiting to be delivered to the process. A key part of the scheduling context is the process’s kernel stack, a separate area of kernel memory reserved for use by kernel-mode code. Both system calls and interrupts that occur while the process is executing will use this stack. (p788)

스케줄링 컨텍스트: 프로세스 컨텍스트에서 가장 중요한 부분은 스케줄러가 프로세스를 일시 중단 및 재시작하기 위해 필요한 정보인 프로세스의 스케줄링 컨텍스트입니다. 이 정보에는 모든 프로세스 레지스터의 저장된 복사본이 포함됩니다. 부동 소수점 레지스터는 별도로 저장되며 필요할 때만 복원됩니다. 따라서 부동 소수점 산술을 사용하지 않는 프로세스는 해당 상태를 저장하는 오버헤드가 발생하지 않습니다. 스케줄링 컨텍스트에는 스케줄링 우선순위에 관한 정보 및 프로세스에 전달되기를 대기 중인 미결 신호에 관한 정보도 포함됩니다. 스케줄링 컨텍스트의 핵심적인 부분은 프로세스의 커널 스택인데, 이는 커널 모드 코드에 의해 사용되도록 예약된 커널 메모리의 별도 영역입니다. 프로세스가 실행되는 동안 발생하는 시스템 호출 및 인터럽트 모두 이 스택을 사용할 것입니다. (p788)

OSR Developer Community

https://community.osr.com/discussion/268074/floating-point-operations-in-kernel

Why floating point operations are not permitted at kernel level? Is it because when a kernel-kernel context switch happens the state of FP registers is not saved, while it is saved in a user-kernel transition (feel free to correct if wrong)?

커널 레벨에서 부동 소수점 연산이 허용되지 않는 이유는 커널-커널 컨텍스트 스위치가 발생할 때 FP 레지스터의 상태가 저장되지 않고 사용자-커널 전환(잘못된 경우 자유롭게 수정)되기 때문입니까?

Correct. In the early days of the NT kernel, when we were using 80387 co-processors, saving the FPU state was an extremely expensive operation -- many thousands of CPU cycles. The design decision was made at that point to skip it for kernel transitions. Once made, such a decision cannot be easily rescinded.

맞습니다. NT 커널 초기에 우리가 80387 공동 프로세서를 사용할 때, FPU 상태를 저장하는 것은 CPU 사이클 수천 번을 반복하는 엄청난 비용이 드는 작업이었습니다. 그 시점에서 설계 결정은 커널 전환을 위해 생략하기 위해 내려졌습니다. 한번 결정되면 그러한 결정은 쉽게 취소될 수 없습니다.

int64_t 과 int

https://www.quora.com/What-is-the-difference-between-int-and-int32_t

https://stackoverflow.com/questions/14515874/difference-between-int32-int-int32-t-int8-and-int8-t

int, int32_t, int64_t는 왜 구분해야 하는 걸까?

 

• int : size >= 16bits 면 그 어떤 사이즈도 int타입이 될 수 있다.
• int32_t, int64_t... 는 <stdint.h>헤더에서 typedef로 선언된 타입이며 각각 특정한 사이즈를(32bits, 64bits) 보장받는다. 즉 보장받은 사이즈만큼의 bits로 연산의 정밀도를 보장받을 수 있다고 볼 수 있다.

 

pintOS의 경우 원래 32비트로 구현되었던 거라고 하고, 64비트로 구현하려면 세심하게 캐스팅해주어야 한다고 하는 듯 하다. (핀토스 외에도 다른 머신들, 특히 64비트로 처음부터 시작하지 않은 경우라면, 특히 C로 다룰 때 모두 샌경 써야 한다. 자바 같은 언어는 조금 덜 신경 써도 된다고 한다.) int64_t로 캐스팅을 하지 않으면 오버플로우가 일어날 수 있음.

• interrupt on/off 와 if문을 함께 사용할 때 먼저 if문을 사용해 끝낼 시 off/on 하고 보내는 것을 잊지 말 것. 다른 언어에서는 try catch로 사용이 가능하다.

// inerrupt off 하는 코드 
if (!a ) { 
  // interrupt on 코드 작성 필수 
    return }