[6주차 토의 주제] <article review> CFS Linux

CFS와 관련된 첨부의 article을 읽고 중요한 내용을 요약하여 발표하시오.

 

https://opensource.com/article/19/2/fair-scheduling-linux

CFS: Completely fair process scheduling in Linux

 

CFS: Completely fair process scheduling in Linux 

CFS gives every task a fair share of processor resources in a low-fuss but highly efficient way.

Intro

리눅스는 프로세스 유형에 따라(Real-time proecess, Normal process) 서로 다른 스케줄링 알고리즘을 사용하여 스케줄링 에 대한 모듈식 접근 방식을 취한다.

CFS의 특징은 preemptive(중단시키는,선점적인) 방법과는 다르게 프로세스에게 CPU를 공정하게 할당하는 fairness한 알고리즘 이라는 것이다. 

 

Some core concepts

프로세스는 명령과 데이터를 저장하는 메모리, 명령을 실행하는 최소 하나의 프로세서, 외부 세계와 상호 작용하는 I/O 장치 등 공유 시스템 리소스를 위해 다른 프로세스와 경쟁해야 한다.

프로세스 스케줄링은 운영 체제(OS)가 프로세서에 작업(예: 일부 숫자 처리, 파일 복사)을 할당하는 방법이다. 

그런 다음 실행 중인 프로세스가 작업을 수행합니다.
프로세스에는 기계 수준 명령의 시퀀스인 하나 이상의 실행 스레드가 있다.
프로세스를 스케줄링하는 것은 프로세서에서 스레드 중 하나를 선택하게 하는 것이다. 

 

Linux는 스케줄링된 프로세스를 단일 스레드로 처리한다.

따라서 프로세스가 N개의 스레드로 다중 스레드된 경우 스레드를 처리하려면 N개의 스케줄링 작업이 필요하다.

프로세스 내의 다중 스레드는 메모리 주소 공간과 같은 리소스를 공유하게 된다. 따라서 리눅스는 light weight processes로 설명되기도 한다. 

 

다양한 프로세스 상태 중 스케줄링에서 중요한 상태는 두 가지이다. 

• A blocked process: I/O event가 끝난 후 실행을 재개할 수 있는 프로세스
• A runnable process: 실행할 수 있는 프로세스

 

CPU burst(명령어 집합을 수행하는 구간)이 대부분의 프로세서를 차지하는 경우, processor-bound(computer-bound, CPU-bound) 라 하고

반대로 I/O burst(I/O가 끝나기를 기다리는 구간)이 긴 경우를 I/O-bound 라고 한다. 

따라서 process-bound  프로세스는 대부분 runnable한 상태인 반면 I/O-bound process는 대부분 blocked 상태이다.

ex) 숫자 처리 - CPU bound, 파일 액세스 작업 - I/O bound

사용자와 Interactvie하게 동작하는 프로그램은 대부분 I/O bound process,  non-interactive한 작업은 CPU-bound process

 

Preemptive scheduling vs CFS

<Preemptive sheduling>

Unix는 초기에 preemptive scheduling 알고리즘을 채택하였다. 

이는 특정 고정된 time slice (ex. 50ms)가 있어 정해진 시간동안 프로세스 작업이 끝날 때까지 다른 프로세스가 CPU를 선점하지 못하도록 막는 방식이다. 

프로세스 우선 순위당 여러 개의 scheduling queues가 포함되고 우선 순위가 높은 queue의 프로세스는 우선 순위가 낮은 queue의 프로세스보다 먼저 sheduling 된다.

 

<CFS>

Fairness하다.

고정된 time slice 및 우선순위가 없다.

프로세서의 주어진 작업에 대한 시간(process time)은 context switch가 변경됨에 따라 동적으로 계산된다. 

-> 강의자료 p.24 설명에 대한 내용이 맞는지 질문하기!

같은 priority queue 내에서 context switch 횟수가 0이라면 time quantum의 시간은 길어지게 되고, context switch 횟수가 많아질수록 time quantum의 시간은 짧아지게 된다.

 

예를 들어, multitasking이 가능한 processor P가 있다고 하자

작업 T1과 T2는 P에서 동시에 실행될 수 있으며 각각 P의 수행 능력의 50%를 받게 된다.

따라서 CFS는 CPU의 자원을 균등하게 나눠주는 완벽한 multitasking에 근접하도록 설계되었다.

 

CFS 스케줄러에는 실행 가능한 모든 작업이 프로세서를 한 번 이상 켜는 데 필요한 최소 시간인 target latency time이 있다.

target latency time
CFS가 설정한 가장 작은 스케줄 단위 또는 response time(ready queue에 있는 시간)의 최대치 (wait후 기다리는 시간) 

최소한의 target latency time(=response time) 기본 값은 20ms으로 실행 가능한 각 작업은 대기 시간의 1/N 을 얻게된다.(N = task 수)

ex) target latency time이 20ms, task 4개 있는 경우 각 작업은 5ms의 time slice(= time quantum, =waiting time)를 갖게 됨

 

따라서 CFS는 각 task에 대해 fairness 하다고 할 수 있다.

1/N time slice는 고정된 것이 아닌 context switch 횟수에 따라 달라지게 된다.

운영체제는 context switch, 한 프로세스가 다른 프로세스를 선점할 때 마다 오버헤드를 발생시키는데 이 오버헤드가 과도하게 커지지 않도록 하기 위해 프로세스가 선점되기 전에 실행 되어야하는 최소한의 시간(1ms~4ms)가 있다. 이를 minimum granularity(최소 세분성, process에 부과된 최소 time slice)이라고 한다. 만약 minimum granularity가 1/N time slice보다 크다면 시스템에 overhead가 걸리게 될 것이다. 

 

그렇다면 preemptive는 언제 발생할까?
CFS는 주어진 오버헤드를 고려하여 컨텍스트 전환을 최소화하려고 한다.

컨텍스트 전환에 소요된 시간은 다른 작업에 사용할 수 없는 시간이다. 
따라서 작업이 프로세서를 받으면 다른 작업을 위해 선점되기 전에 전체 가중 1/N 슬라이스에 대해 실행된다. 
작업 T1이 가중치 1/N에 대해 실행되었다고 가정하자
실행 가능한 작업 T2는 같은 프로세스 내의 작업 중에서 가상 런타임(vruntime)이 가장 낮다. 
이 경우 T1이 중단되고 T2가 CPU를 선점하게 된다. 

Linux에서의 스케줄러는 모든 작업에 대한 vruntime을 추적한다. 
vruntime이 낮을수록 CFS는 낮은 vruntime의 작업을 스케줄링 라인의 앞쪽으로 이동시킨다. 
하지만 이때 스케줄링 순서는 line이 아닌 트리로 구현된다. 

 

CFS scheduler는 얼마나 자주 reschdule하는가?

target latency(TL)가 20ms이고 minimum granularity(MG)가 4ms라고 가정하자

 

TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

 

이 경우 5개 이하의 작업의 수가 target latency time 동안 프로세서를 동작 시킬 수 있다. 

만약 5개 이상이라면 target latency time은 20초보다 더 증가시켜야 할 것이다.

 

예를 들어 작업이 5개라면 각 작업은 4ms의 1/N time quantum, minimum granularity를 가진다.

작업의 개수가 3개면 각 작업은 거의 7ms의 1/N time quantum을 얻는다. 
두 경우 모두 스케줄러는 target latency time인 20ms 단위로 reschdule을 하게 된다.

 

작업의 개수가 5개 이상이라면 target latency time은 20ms 보다 더 증가될 것이다. 

만약 작업의 수가 10개이고 MG 가 4라면 schduler는 40ms 이후에 reschdule을 하게 된다.

 

(number of tasks) * MG = (10 * 4) = 40ms  ## period = 40ms

 

 

Special features

1. SMP

CFS는 모든 프로세스(커널 또는 사용자)가 모든 프로세서에서 실행될 수 있는 SMP(symmetric multiprocessing)를 지원한다.

여러 프로세서가 동일한 스케줄링 정책을 공유하는 경우 이들 간의 로드 밸런싱이 이루어진다. 

특정 프로세서가 다른 프로세서와 다른 스케줄링 정책을 가지고 있는 경우 이 프로세서는 스케줄링과 관련하여 다른 프로세서와 분리된다.

 

2. Configurable scheduling groups

여러 프로세서가 동일한 스케줄링 정책을 공유하는 경우 이들 간의 로드 밸런싱이 이루어진다.

특정 프로세서가 다른 프로세서와 다른 스케줄링 정책을 가지고 있는 경우 이 프로세서는 스케줄링과 관련하여 다른 프로세서와 분리된다.

Nginx 웹 서버에 마스터 프로세스와 HTTP 요청 처리기 역할을 하는 4개의 작업자 프로세스가 있다고 해보자
모든 HTTP 요청의 경우 요청을 처리하는 특정 작업자는 관련이 없다. 요청이 적시에 처리되는 것만 중요하므로
4명의 Nginx 작업자를 스케줄링 목적으로 개인이 아닌 그룹으로 취급하는 것이 공정하다. 
즉, CFS 는 4개의 Nginx 작업자에게 개별 vruntime이 아닌 단일 vruntime을 갖도록 구성할 수 있다.
이는 Linux 방식의 파일을 통해 수행되는데,  vruntime-sharing의 경우 셸 명령을 통해 세부 정보가 제공되는 cpu.shares라는 파일이 생성된다. 

 

3. Scheduling class

Linux는 구현 알고리즘과 함께 서로 다른 스케줄링 정책이 동일한 플랫폼에서 공존할 수 있도록 스케줄링 클래스를 지원한다. 

스케줄링 클래스는 C에서 코드 모듈로 구현되는데, 

지금까지 설명한 스케줄링 클래스인 CFS는 SCHED_NORMAL이다. 
Real-time 작업을 위한 스케줄링 클래스에는 SCHED_FIFO(first in first out) 및 SCHED_RR(Round robin)이 있다. 

 

SCHED_FIFO에서 작업이 완료될 때까지 실행됩니다. SCHED_RR에서 태스크는 고정된 타임슬라이스를 소진하고 선점될 때까지 실행된다. 

CFS implementation

run queue 

schedule된 작업의 타임라인을 나타내는 데이터 구조

 

red-black tree

CFS는 run queue를 red-black tree로 구현한다. 

이는 O(log N) (N= 트리 노드 수)의 시간에 실행되는 효율적인 insert 및 remove 작업이 가능한 self-balancing binary search tree이다.

트리는 vruntime을 기반으로 엔터티를 계층 구조로 구성한다. 

트리의 내부 노드는 schedule되는 작업을 나타내고 vruntime이 가장 낮고 프로세서가 가장 많이 필요한 작업은 왼쪽 하위 트리 , vruntimes가 상대적으로 높은 작업은 오른쪽 하위 트리로 인덱싱 된다. 

 

CFS 스케줄러에는 schdule할 작업에 대한 정보를 담은 C task_struct 인스턴스가 있다. 

여기에는 sched_entity 구조를 포함하며,스케줄링 관련 정보인 작업 또는 작업 그룹당 vruntime이 포함된다. 

 

struct task_struct { /** info on a task **/
...
struct sched_entity se; /** vruntime, etc. **/
...
};

 

 

 

cfs_rq 인스턴스는 red-black 트리의 루트를 가리키는 tasks_timeline 이라는 rb_root 필드를 포함한다.
트리의 각 내부 노드에는 부모 노드와 두 자식 노드에 대한 포인터가 있습니다. 리프 노드는 값은 nil이다.

(이 부분 이해가 잘 안된다 ㅠ)

 

 

CFS에 관한article 을 영어 원문으로 처음 접하게 됐는데, 생각보다 너무 어렵다..

끝까지 다 읽어보고 해석하는데 거의 3시간 넘게 걸린 것 같다.

수업 내용으로 다 이해한 것 같았는데  response time, waiting time 등 CPU 성능 척도에 대해 다시 공부해야할 것 같다. 

이번 article 읽기 주제로 수업시간에 배운 내용을 다시 복기할 수 있었고 부족한 부분을 알게 되어 오래 기억에 남길 수 있을 것 같다