리눅스 스케줄러 구현 (CFS)

※ 리눅스 스케줄링 구현 

CFS의 4가지 구성요소

- 시간 기록

- 프로세스 선택

- 스케줄러 진입 위치

- 휴면 및 깨어남

 

시간 기록

1 모든 프로세스 스케줄러는 각 프로세스의 실행 기록을 기록

2 대부분 유닉스 시스템은 프로세스에 타임슬라이스를 할당하면서 기록

3. CPU 클럭 한틱이 지날때마다 그틱에 해당하는 시간만큼 타임슬라이스가 줄어든다

 

스케줄러 단위 단위 구조체

1 CFS에는 타임슬라이스 개념이 없지만 공정하게 할당된 몫만큼을 사용하기 때문에 프로세스의 실행시간을 기록해 두어야 한다.

2 <linux/sched.h>에 정의된 struct sched_entity라는 스케줄러 단위 구조체를 사용해서 정보를 저장

 

가상실행 시간

1. vruntime 변수에는 프로세스의 가상 실행시간이 저정되며 가상 실행시간은 실행 가능한 프로세스 개수에 따라 정규화한 실제 실행시간을 의미한다.

2. 가상실행시간을 이용해 CFS가 지행하는 '이상적인 멀티태스킹 프로세서'를 근사적으로 구현 가능

이상적인 프로세서에서는 우선순위가 같은 프로세스의 가상 실행시간은 3. 모두 같으며 CFS는 vruntime을 통해 프로세서가 얼마나 오랫동안 실행 됬는지 앞으로 얼마나 더 실행되어야 하는지를 기록

4. 이작업은 kernel/sched_fair.c에 정의된 update_curr()에서 수행

 

프로세스 선택

1. 다음 실행할 프로세스를 선택할 때 CFS는 vruntime이 가장 작은 프로세스를 선택

2. CFS는 이를 효율적으로 하기 위해 레드블랙트리를 사용한다 (rbtree)

3. 레드블랙트리는 어떤 데이터를 노드에 저장하는 자료구조로, 특정키로 각 노드를 식별할 수 있으며, 키값이 주어졌을 때 그 키값을 가진 데이터를 효율적으로 탐색할 수 있는 자료구조

 

다음 작업 선택

1. 시스템의 실행가능한 모든 프로세스에 대해 각 프로세스별로 가상 실행시간을 키값으로 하는 노드를 만들어 레드블랙를 구성했을 때,

2. 주어진 트리에서 vruntime값이 가장 작은 CFS가 다음에 실행하고자 하는 프로세스는 트리의 가장 왼쪽에 있는 노드에 해당하는 프로세스

3. 트리의 루트노드에서부터 말단 노드에 이를 때 까지 계속 왼쪽 노드를 다라 가면 vruntime 값이 가장 작은 프로세스를 찾을 수 있다.

4. 따라서, CFS의 프로세스 선택 알고리즘은 "레드블랙트리의 가장 왼쪽노드에 해당하는 프로세스를 실행한다"로 요약

( kernel/sched_fair.c __pick_next_entity() 가 수행)

 

스케줄러 진입 위치

1. 프로세스 스케줄링 작업을 시작하는 곳은 kernel/sched.c 파일의 schedule()함수에 정의

2. 커널의 다른 부분에서 이 함수를 통해 프로세스 스케줄러를 호출함으로서 다음에 실행할 프로세스를 선택하고 실행

3. schedule()함수는 더 일반적인 형태의 스케줄러 클래스이고 이 함수는 가장 우선순위가 높은 실행 가능한 프로세스를 가진 스케줄러 클래스를 찾고 다음에 실행할 프로세스를 해당 스케줄러에게 물어본다.

4. kernel/sched.c 파일의 pick_next_task()함수는 가장 높은 우선순위의 스케줄러 클래스부터 돌아가면서 우선순위가 가장 높은 클래스의 우선순위가 가장 높은 프로세스를 찾아낸다.