Completely Fair Scheduler

Completely Fair Scheduler, CFS.

1 개요[편집]

Completely Fair Scheduler는 리눅스의 기본 프로세스 스케줄러이다. 리눅스 커널 버전 2.6.23에 도입되었다. 이름처럼 완전히 공정한 스케줄러로서, 같은 우선순위를 가진 프로세스들이 정확히 같은 시간동안 CPU를 사용하는 것을 목표로 스케줄링한다.

내부적으로 레드-블랙 트리를 사용하여, N개의 태스크가 존재하는 상황에서 새로운 태스크를 넣을 때 O(logN)의 연산이 수행된다.

2 가상 실행시간[편집]

가상 실행시간(Virtual runtime; vruntime)은 우선순위를 반영하여 계산한 각 태스크들의 수행시간으로, [math]\displaystyle{ \mbox{(수행시간)} \times \frac{1024}{\mbox{(가중치)}} }[/math]로 계산된다. 우선순위가 높은 태스크는 같은 시간동안 CPU를 이용하였어도 더 낮은 가상 실행시간으로 계산된다.

스케줄러는 항상 가상 실행시간이 가장 작은 태스크를 다음에 실행시킬 태스크로 선정한다.