리눅스 스케줄링 알고리즘
스케줄러 클래스
1. 리눅스 스케줄러는 모듈화돼어 있으며 여러유형의 프로세스를 각기 다른 알고리즘을 통해 스캐줄링이 가능하며 모듈화된 형태를 스케줄러 클래스라고 한다.
2. 스케줄러 클래스를 이용해 교체 가능한 여러 알고리즘을 동시에 사용하면서 클래스별로 독자적인 방식으로 프로세스를 스케줄링이 가능
3. kernel/sched.c 에 정의된 기본 스케줄러 코드는 각 스케줄러 클래스를 우선순위에 따라 차례대로 실행
4. 실행가능한 프로세스가 있는 가장 우선순위가 높은 스케줄러가 다음에 실행할 프로세스를 선택
5. 완전 공정 스케줄러(CFS)는 SCHED_NORMAL로 정의된 리눅스의 일반 프로세스용 스케줄러 클래스
유닉스 시스템의 프로세스 스케줄링
증요한 2가지의 개념 : 프로세스 우선순위와 타임슬라이스
타임 슬라이스는 프로세스가 얼마나 오랫동안 실행되는가이고 높은 우선순위 프로세스는 더 자주 실행되고 더 긴 타임슬라이스 값을 할당 받는다.
→ 이 시스템의 방법론적인 문제발생
1. 작업전환의 최적화 문제 발생
2. 우선순위(나이스 값)가 타임슬라이스와 묶이는 것과 나이스 값의 상대적인 차이 발생
3. 나이스값에 따라 타임슬라이스를 할당 하려면 타임슬라이스의 절대값을 할댕해야 됨
4. 우선순위 기반 스케줄러가 대화형작업을 최적화 하고자 할 경우 프로세스 깨우기 처리와 관련된 문제 발생
공정 스케줄링 (CFS)
CFS는 이상적이고 완벽한 프로세서를 가지고 있는 시스템의 프로세스 스케줄링을 추구
1. CFS는 각 프로세스를 순차적으로 일정시간동안 실행하고 가장 실행이 될 된 프로세스를 다음에 실행할 프로세스를 선택
2. 실행가능한 전체 프로세스 개수와 관련된 함수를 이용해 프로세스를 얼마동안 실행해야 하는지 계산
3. 프로세스에 할당할 프로세서 시간 비율의 가중치로 나이스값을 활용
4. CFS는 실제 타임슬라이스 값을 계산하기 위해 완전 멀티태스킹의 '무한히 작은' 스케줄링 단위를 근사 할 수 있는 목표치를 정해 놓고 이를 목표 응답시간이라고 한다.
리눅스 스케줄링 구현
CFS의 4가즈 구성요소
- 시간 기록
- 프로세스 선택
- 스케줄러 진입 위치
- 휴면 및 깨어남
시간 기록
1 모든 프로세스 스케줄러는 각 프로세스의 실행 기록을 기록
2 대부분 유닉스 시스템은 프로세스에 타임슬라이스를 할당하면서 기록
3. 시트메 클럭 한틱이 지날때마다 그틱에 해당하는 시간만큼 타임슬라이스가 줄어든다
스케줄러 단위 단위 구조체
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()함수는 가장 높은 우선순위의 스케줄러 클래스부터 돌아가면서 우선순위가 가장 높은 클래스의 우선순위가 가장 높은 프로세스를 찾아낸다.