[OS] 스케줄링: 추첨 스케줄링(비례 배분)/ 보폭 스케줄링(공정 배분)/ 리눅스 CFS

◈  비례 배분 스케줄러

: 반환시간이나 응답시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장한다. 

ex) 추첨 스케줄링 (lottery scheduling)

: 다음 실행될 프로세스를 추첨을 통해 결정한다.

  더 자주 수행되어야 할 프로세스는 추첨권(티켓)을 많이 준다. 

---

◈ 추첨권 스케줄링

[장점] 

▶ 무작위성이다.

1. 무작위 방식은 관리해야 할 상태 정보가 거의 없다. (프로세스의 상태 정보만 필요하다. 예. 각 프로세스가 가진 추첨권의 개수)

그에 반해 전통적인 공정 배분 스케줄링 알고리즘에서는 각 프로세스가 사용한 CPU 양을 기록해야 한다. 이 정보는 각 프로세스를 실행시킬 때마다 갱신된다. 

2. 무작위 방식은 매우 빠르다. 난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 되고 따라서 속도가 요구되는 많은 경우에 사용될 수 있다.

 

▶ 구현이 단순하다.

- 추첨권 스케줄링은 난수 발생기와 프로세스들의 집합을 표현하는 자료구조, 추첨권의 전체 개수만 필요하다.

 

[단점] 

▶ 무작위성은 원하는 비율을 정확히 보장하지는 않는다. 

  짧은 기간만 실행되는 경우 정확한 비율을 더욱 보장할 수 없다. 

  하지만 두 작업이 장시간 실행될수록, 원하는 비율을 달성할 가능성이 높아진다.

---

추첨권 스케줄링의 문제점을 해결하기 위해  Waldspurger는 결정론적 공정 배분 스케줄러인 보폭 스케줄링(stride scheduling)을 고안하였다. 

◈ 보폭 스케줄링(stride scheduling)

- 보폭 : 자신이 가지고 있는 추첨권 수에 반비례하는 값 

• 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지를 추적한다. 
• 스케줄러는 보폭과 pass 값을 사용하여 어느 프로세스를 실행시킬지 결정한다.
• 가장 작은 pass 값을 가진 프로세스를 선택한다. 
• 프로세스를 실행시킬 때마다 pass 값을 보폭만큼씩 증가한다. 

---

 

[정리]

1.  추첨 스케줄링은 정해진 비율에 따라 확률적으로 CPU를 배분한다.

2. 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다. 

	추첨 스케줄링	보폭 스케줄링
장점	1. 프로세스 상태 정보가 필요 없다 2. 확장성이 좋다. (추첨권의 개수만 필요)	1. 공정성을 확보할 수 있다.
단점	1. 공정성이 보장되지 않는다.	1.  CPU 사용 현황, pass 값을 유지하고 갱신해야 한다.  2. 확장성이 나쁘다.( 새로운 작업에 pass 값이 0이라면 CPU 독점)

---

◈ 리눅스 CFS (Completely Fair Scheduler, 완전 공정 스케줄러)

CFS란 리눅스 운영체제가 구현한 "공정 배분 스케줄링"이다. 

기존과는 다른 방식이다. 

 

[장점]

▶ 효율성 (스케줄러의 효율성이 전체 시스템 성능에 매우 중요한 영향을 갖는다.)

▶ 확장성 

 

[CFS의 특징]

1. 고정된 길이의 타임 슬라이스를 사용하지 않는다.

2. vruntime이라는 간단한 counting 기반 테크닉을 사용한다. 가장 낮은 vruntime을 가진 프로세스를 다음에 실행할 프로세스로 선택한다.

cf) vruntime은 해당 프로세스의 "지금까지 실행된 시간"이라고 생각하면 된다. 실제 시간과 같은 속도로 증가한다.

3. 공정성(각 프로세스가 작은 시간 간격으로 CPU사용하면 공정해짐)과 성능(문맥교환 오버헤드 작게해야함 ) 

이 상충된 두 마리 토끼를 잡으려고 sched_latency 와 min_granularity 라는 변수를 이용한다.

4. 티켓이 아닌 nice 레벨(가중치와 대응)을 이용하여 타임슬라이스 길이를 계산한다.

5. Red-Black 트리를 활용하여 실행중이거나 또는 실행 가능한 프로세스들을 보관한다. (O(logn) 로그 함수 시간에 삽입과 삭제 연산이 가능하다.)

6. 작업이 sleep상태에서 깨어날 때 vruntime을 트리에서 가장 작은 값으로 재설정함으로써 기아 상태를 방지한다.