[PintOS] 1-3 Advanced Scheduler

GIT

 

[thread.c, thread.h, timer.c, synch.c, fixed_point.c, fixed_point.h, targets.mk]

 

영상 출처 : https://youtu.be/4-OjMqyygss

 

 

---

 

---

🔥 Main Goal

1. MLFQ 특성을 갖는 4.4 BSD scheduler 구성하기 (queue 제외하고)

    - Give priority to the processes with interactive nature
    - Priority based scheduler

    ⇒ 우선순위 계산할 때 equation 사용

 

Why Advanced Scheduler ?

- priority scheduler는 thread의 실행을 판단하는 요소가 prioirty 하나 뿐이다

1. 우선순위에 따라 CPU를 점유한 thread가 실행 도중인 상태에서, 우선순위 동적 변화가 없다
  - prioirty가 낮은 thread는 CPU를 점유하기 힘든 상황이 지속될 수 있다 (Starvation Problem)
  - pintOS의 테스트 코드에서는, starvation 상황을 고려하지 않아서 문제가 생기지 않은 것
  - starvation 문제가 발생하면, 전체 시스템의 응답성과 성능을 저하시킬 수 있다
	
2. 어떤 동작을 하는 thread인지에 대한 구분이 없다
  - I/O동작 처리 thread : CPU는 조금만 점유해도 되는데, 응답이 빨라야 함
  - compute-bound thread : 응답이 빠를 필요는 없는데, CPU를 많이 점유해야 함
  - compute-bound thread가 CPU를 점유하다가도, I/O 동작 처리 thread 요청이 들어온다면 switching이 가능해야 한다는 의미

 

---

important concept in BSD scheduler : nice

NICE

- Int형 자료
- thread의 nice가 높아질수록 priority 감소
- thread의 nice가 낮아질수록 priority 증가

- pintOS에서는 -20 ~ 20의 nice를 가진다

- 관련된 Function : thread_get_nice() / thread_set_nice(int new_nice)

 

Priority equation

1. nicer thread일 경우, priority를 낮춘다
2. 최근에 많은 CPU를 사용한 thread일 경우, priority를 낮춘다
3. 모든 thread는 4틱마다 priority를 재계산한다
4. 계산 결과는 가장 근접한 정수로 판정된다
   -> recent_cpu/4는 정수가 아니라 부동 소수점 숫자

 

recent_cpu : thread의 최근 CPU 사용량 추적하는 값
             thread가 얼마나 많은 CPU cycle을 사용했는지 나타냄
             timer_interrupt 발생할때마다 1씩 증가

decay : 시간이 지남에 따라 recent_cpu 값에 대한 과거 CPU 사용량을 줄이는 데 사용
        decay는 1보다 작은 값을 가짐
        1초마다 recent_cpu에 decay를 곱해주면서, 가중치를 낮춘다

* 왜 recent_cpu를 감소시켜줘야 하나 ?
	
	1. 시간의 경과에 따른 가중치 조정
       recent_cpu는 thread의 최근 CPU 사용량을 나타내는 값
       decay로 감소시키지 않는다면, 예전부터 실행중인 프로세스의 recent_cpu는 부당하게 높아질 것
	
	2. 장기 실행 프로세스의 불공정성 완화
       recent_cpu가 부당하게 높아진 프로세스는 우선순위가 낮아짐에 따라 실행되지 못할 것
		 
	3. 시스템 안정성 유지
       recent_cpu가 무한정 증가하면, 오버플로우나 자원 고갈 등의 문제 야기 가능

nice : 1초마다 recent_cpu에 nice를 더해주면서, 프로세스의 우선순위를 조정한다
       양수일 경우 recent_cpu 증가 -> priority 감소
       음수일 경우 recent_cpu 감소 -> priority 증가
			 
			 

==> 매 초마다 recent_cpu = decay * recent_cpu + nice

 

 

decay를 고정적으로 사용하지 않을거임

쓰레드의 경우에 따라, decay를 조정할 거임

-> decay = (2*load_average) / (2*load_average + 1)

 

load_avg : 시스템이 얼마나 바쁜지 나타내는 값

부팅 시 load_avg는 0으로 초기화
load_avg = (59/60)*load_avg + (1/60)*ready_threads 

(59/60), (1/60) -> 이 value들은 스케줄링 알고리즘에 중요한 파트

 

- 4틱마다, 모든 thread에 대한 우선순위를 재계산

- 1틱마다, running thread의 recent_cpu 1씩 증가

- 1초마다, running thread, load_avg를 업데이트 (nice, decay 고려하여)

 

- 커널에서는, 오직 정수 연산만 가능함
- context switching이 일어날 때, 부동 소수점을 저장할 수 없다

- 따라서, 정수 연산으로 고정 소수점 연산을 구현해야 함

[priority, nice, ready_threads] : 정수 값
[recent_cpu, load_avg] : 실수 값

 

0 ~ 13 : decimal (소수 부분)
13 ~ 30 : integer part (정수 부분)
30 ~ 31 : sign bit (부호 비트)

x, y = 실수
n = 정수
f = 2^14

 

- structure thread에, 새로운 필드 추가해야 함 [nice, recent_cpu]

- 새로운 Function 추가해야 함
	
	recent_cpu, nice를 사용해서 priority 계산하는 공식
	recent_cpu 계산하는 공식
	load_avg 계산하는 공식
	1틱마다 recent_cpu 1씩 증가하는 공식
	4틱마다 모든 thread의 priority 재계산하는 공식
	1초마다 recent_cpu, load_avg 재계산하는 공식
	
- 공식을 모두 구현해서 사용하게 되면, MLFQS 사용하지 않아도 됨
=> 4.4 BSD scheduler, MLFQS 모두 동일한 목표를 달성하기 때문

 

# Need to Modify

1. static void init_thread(struct thread *t, const char *name, int priority)

	 nice, recent_cpu 초기화하는 동작 추가해야 함
	 
2. void thread_set_priority(int new_priority)
	 
	 advanced scheduler를 사용할 때는, priority setting을 비활성화 해야함
	 	 
3. static void timer_interrupt(struct intr frame *args UNUSED)

	 1초마다 recent_cpu, load_avg 계산해서 업데이트 하는 동작 추가해야 함
	 4틱마다 모든 thread의 우선순위를 계산해서 업데이트 하는 동작 추가해야 함

4. void lock_acquire(struct lock *lock)
	 
	 advanced scheduler를 사용할 때는, prioirty donation 금지 !
	 
5. void lock_release(struct lock *lock)

	 advanced scheduler를 사용할 때는, prioirty donation 금지 !
	 
6. void thread_set_nice(int nice UNUSED)

	 current thread의 nice 값을 설정하는 동작
	 
7. int thread_get_nice(void)
	
	 current thread의 nice 값을 반환하는 동작
	 
8. int thread_get_load_avg(void)

	 load_avg에 100을 곱한 값을 반환하는 동작
	 
9. int thread_get_recent_cpu(void)

	 recent_cpu에 100을 곱한 값을 반환하는 동작

---

# summary

4.4 BSD scheduler를 구현하며 쓰는 recent_cpu, load_avg, nice, decay 개념
=> 기존 priority scheduler의 한계를 해결하기 위해 고안된 메커니즘
=> 쓰레드의 특성과 시스템의 상태를 고려하여 priority를 동적으로 조정하는 데 사용
=> 위 개념들을 활용하여 문제들을 간접적으로 해결할 수 있음 (직접적 : mlfqs)

1. I/O 동작 쓰레드의 우선 실행 문제

- recent_cpu, decay : CPU 사용량이 적은 I/O 동작 쓰레드의 우선순위를 높게 유지하는 데 도움
- I/O 동작 쓰레드가 CPU를 할당받을 기회가 더 많아진다.

2. Starvation 문제

- nice : 사용자가 쓰레드의 우선순위를 조정할 수 있는 수단 제공 
         (CPU 연산 중심 동작 쓰레드는 nice가 높게 책정되어 양보할 가능성이 증가하니까)
         이를 통해 priority가 낮아도 (I/O 동작 쓰레드) CPU 할당 가능
				 
- load_avg : 시스템 전체의 부하를 나타내는 지표
             쓰레드의 우선순위를 조정함으로써 과부하 상황에서의 공평성 향상
						 
- decay : 시간이 경과함에 따라 과거 CPU 사용량의 영향을 감소시킴
          (CPU 점유 쓰레드에게 과도한 불공평을 제공하지 않겠다는 의미)

 

---

마주한 문제

 

0. 실행

전체 실행 : make check -> make -mlfqs check
개별 실행 : pintos -v -k -T 480 -m 20 -- -q -mlfqs run {테스트 파일 이름}
		  pintos -v -k -T 480 -m 20 -- -q -mlfqs run mlfqs-load-1


1. 고정소수점 연산

연산하는 함수를 따로 만들어서 추가해줌
[fixed_point.c] (threads 폴더)
[fixed_point.h] (include -> threads 폴더)
이후 threads 폴더의 targets.mk 파일의 마지막 줄에 threads_SRC += threads/fixed_point.c 추가

2. calculate, recalculate 함수 추가

각종 변수들을 계산하고, 설정하고, 가져오는 동작을 추가해야 함
int, float type을 신경쓰며 작성해야 하기에 조금 힘듬

3. load_60 테스트 시 120초에 kernel panic 발생

어디가 문제인지 판단하기 힘든 문제였다
1) load_avg 변수가 제대로 업데이트가 되지 않는다
1-1) load_avg 변수에 영향을 끼치는 다른 변수 (ready_thread) 카운트 방식이 틀렸다
2) load_avg 변수는 제대로 업데이트가 되지만, 다른 영역에서 문제가 발생한다

아무리 살펴봐도 뭐가 문제인지 해결을 못하고 있었는데, load_avg 테스트 파일 위에 주석을 보라는 조언을 받음
-> timer interrupt handler가 너무 많은 일을 하면 오류가 발생한다는 문구가 있다
--> all_list를 순회할 때, state == dying인 thread까지 검색을 하는 동작을 제거해야 함
---> thread_exit 함수에서 list_remove 함수를 사용하여 all_list에서 해당 상태인 thread 제거

4. recent-1 테스트 시 recent_cpu 변수가 감소하지 않는 문제

1) recent_cpu 변수가 제대로 업데이트 되지 않는다
1-1) recent_cpu = decay * recent_cpu + nice인데, decay가 문제가 있을 확률이 크다
1-2) decay에 관여하는 변수는 load_avg인데, load 테스트는 통과했다 ?
-> load 테스트는 통과할 정도의 오차는 발생하지만, 그 오차가 recent 테스트에서는 허용되지 않는다
-> 그렇다면 기존의 load_avg 계산 동작에 문제가 있을 확률이 있다

이런 생각의 흐름으로 load_avg 계산 공식을 지웠다가 다시 쓰는 걸 반복해도 문제가 해결되지는 않았다
답은 [initial thread 생성 시 all_list에 삽입하는 동작]이 결여되어서 발생한 문제였다

recent-1 테스트에서는 initial thread 생성 이후 recent_cpu가 감소하는 지 확인하는데, 기존 코드에서는
initial thread가 all_list에 추가되지 않아 decay가 증가하지 않았다

initial thread를 all_list에 넣어주니까, 바로 문제 해결