System Designer

리눅스 스케줄링 알고리즘

스케줄러 클래스

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()함수는 가장 높은 우선순위의 스케줄러 클래스부터 돌아가면서 우선순위가 가장 높은 클래스의 우선순위가 가장 높은 프로세스를 찾아낸다.

멀티태스킹 :

하나 이상의 프로세스를 동시에 중첩형태로 실행할수 있는 운영체제

멀티태스킹 운영체제:

협동형 멀티태스킹 (Cooperative Multitasking) & 선접형 멀티태스킹프로세스 (Preemptive Multitasking)가

선점형 멀티태스킹 :

- 프로세스 실행을 언제 중단하고 다른 프로세스를 실행할지리를 스케줄러가 결정

- 실행중인 프로세스를 강제로 중지시키는 작업을 선점이라고 정의

- 프로세스가 선점되기 전까지 주어지는 시간은 보통 미리 정해져 있으며 이것을 Timeslice(타임슬라이스)라고 함

타임슬라이스 : 프로세스가 선점되기 전까지 프로세스에 주어지는 시간

- 스케줄러는 타임슬라이스를 관리하는 방식으로 전체적인 시스템 스케줄링을 결정

협동형 멀티태스킹 :

- 프로세스가 자발적으로 실행을 중단하지 않는 한 프로세스를 중지 불가

- 프로세스가 자주 양보함으로써 실행 중인 프로세스가 충분한 프로세서가 충분한 동작 시간을 확보할 있다

정책 : 스케줄러가 무엇을 언제 실행 할  것인지를 정하는 동작

- 스케줄러의 정책을 통해 프로세서 시간의 사용을 최적화하는 책임

입출력중심 / 프로세서중심 프로세스

입출력중신 프로세스 : 입출력 요청을 기다리는데 대부분의 시간을 사용하는 프로세스

-> 입출력을 기다리는 작업을 반복하게 되므로 실제 실행시간을 짧다

ex) GUI 어플리케이션, Word Application

프로세서 중심 프로세스 : 대부분의 시간을 코드를 실행하는 데 사용

-> 선점될때 까지 계속 실행 / 긴시간동안 덜 자주실행되는것이 중요

ex) ssh-keygen , MATLAB

프로세스 우선순위

1. 스케줄링 알고리즘의 일반적인 형태는 우선순위 기반의 스케줄링이다

2. 목표는 가치와 필요에 따라 프로세스의 순위를 매겨 프로세서 시간을 할당해야 한다.

리눅스 커널의 두가지 우선순위 단위

1. 나이스값 (-20 ~ +19, 기본값 : 0) : 클 수록 우선순위가 낮다.

2. 실시간 우선순위 (0 ~ 09) : 클수록 우선순위가 높다

-> 실시간 우선순위값은 나이스값과 별도의 값이다

타임슬라이스 : 선점되기 전까지 작업을 얼마나 더 실행할 수 있는지 나타내는 값이다

1. 너무 길게 잡으면 시스템의 대화형 성능이 떨어지고 실제 App이 시스템에서 실행되고 있다는 것을 느끼기 어렵다

2. 너무 짧게 잡으면 타임슬라이를 소진한 프로세스를 다음 프로세스로 전환하는데 빈번하게 시스템 시간을 사용하게 되므로 프로세스 전환에 프로세스 시간을 소비한다.

※ 리눅스의 CFS스케줄러는 타임슬라이스 값을 할당하지 않고 대신 프로세스별 프로세서 할당 비율을 지정하는 방법을 사용한다

→ 리눅스에서 프로세스에 할당되는 프로세스 시간은 시스템의 부하에 따른 함수로 결정되고 이는 나이스값의 영향을 받는다