블로그 이미지
Young-il Yoon blog 프로그래밍하는 피카츄

카테고리

Young-il Blog (60)
Android (4)
Real-time System. (0)
Multi-core (2)
Virtualization (2)
Linux Kernel (12)
LEON4_ITX Porting (4)
xen 소스분석 (5)
inline Assembly (1)
Debug Skill (3)
SPARC Architecture (1)
실습자료.. (5)
논문 정리 (1)
Book (2)
music (2)
Drama Review (1)
My Diary (0)
TED.. (1)
ETC... (12)
Total69,658
Today11
Yesterday23

달력

« » 2021.4
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  

공지사항

태그목록


Linux 스케줄러는 여러 가지 면에서 흥미로운 연구 분야이다. 흥미로운 점 중 하나는 Linux가 적용된 사용 모델이다. 원래는 데스크탑 운영 체제용으로 개발된 Linux였지만 지금은 서버, 소형 임베디드 장치, 메인프레임 및 수퍼컴퓨터에서도 사용되고 있다. 물론 이러한 도메인에 대한 스케줄링 로드는 각기 다르다. 또 하나 흥미로운 점은 아키텍처(멀티프로세싱, 대칭 멀티스레딩, NUMA(Non-Uniform Memory Access))와 가상화를 포함한 플랫폼 영역의 기술 발전이다. 여기에는 상호 운용성(사용자 응답성)과 전체적인 공평성 사이의 밸런스도 포함되어 있다. 이러한 관점에서 보면 Linux에서의 스케줄링 문제가 매우 어려운 문제라는 것을 쉽게 알 수 있다.

Linux 스케줄러의 약사

초기 Linux 스케줄러에서는 최소한의 설계를 사용하며 다수의 프로세서나 하이퍼스레딩이 포함된 대형 아키텍처를 전혀 고려하지 않는다. 1.2 Linux 스케줄러에서는 라운드 로빈 스케줄링 정책에 따라 작동하는 순환형 큐를 사용하여 실행 가능한 작업을 관리한다. 이 스케줄러는 프로세스를 추가 및 제거하는 데 효율적이며 잠금 기능을 사용하여 구조를 보호한다. 간단히 말해서 이 스케줄러는 복잡하지 않고 단순하며 빠르다.

Linux 버전 2.2에서는 스케줄링 클래스라는 개념이 채택되면서 실시간 작업, 우선 순위가 없는 작업 및 비실시간 작업에 대한 스케줄링 정책을 사용할 수 있다. 2.2 스케줄러에는 SMP(Symmetric Multiprocessing)에 대한 지원도 포함되어 있다.

2.4 커널에는 스케줄링 이벤트 동안 모든 작업을 반복하여 O(N) 시간 이내에 작동되는 비교적 단순한 스케줄러가 있다. 2.4 스케줄러에서는 시간을 에포크(Epoch) 단위로 나누며 모든 작업은 해당 시간 조각 동안 실행할 수 있다. 작업이 해당 시간 조각의 일부를 사용하지 못한 경우에는 다음 에포크에서 더 길게 실행할 수 있도록 나머지 시간의 절반이 새 시간 조각에 추가된다. 이 스케줄러는 단순히 goodness 함수(메트릭)를 적용하여 다음 실행 작업을 결정하는 방식으로 전체 작업을 반복한다. 이 방법은 상대적으로 단순하기는 하지만 상대적으로 비효율적이고, 확장성이 없으며 실시간 시스템에 취약하다. 게다가 멀티코어 프로세서와 같은 새로운 하드웨어 아키텍처도 사용할 수 없다.

초기 2.6 스케줄러인 O(1) 스케줄러는 2.4 스케줄러의 여러 가지 문제점을 해결하기 위해 설계되었다. 즉, 이 스케줄러는 전체 작업 목록을 반복하지 않고도 스케줄링할 다음 작업을 식별할 수 있다. O(1)이라는 이름에서 알 수 있듯이 이 스케줄러는 훨씬 더 효율적이고 확장성이 높았다. O(1) 스케줄러는 실행 가능한 작업을 하나의 실행 큐로 추적한다. (실제로는 우선 순위 레벨별로 두 개의 실행 큐를 사용한다. 하나는 활성 작업을 위한 큐이며, 다른 하나는 만료된 작업을 위한 큐이다.) 다시 말해서 다음 실행 작업을 식별하기 위해 이 스케줄러는 각 우선 순위에 해당하는 특정 활성 실행 큐에서 다음 작업을 가져오기만 하면 된다. O(1) 스케줄러는 확장성이 훨씬 더 높아졌으며 상호 작용 메트릭과 여러 가지 추론 방법을 통합하여 I/O 또는 프로세서 관련 작업인지 여부를 결정한다. 하지만 O(1) 스케줄러는 커널에서 다루기가 쉽지 않았다. 추론 방법을 계산하는 데 필요한 코드의 양이 매우 많았기 때문에 근본적으로 관리하기가 어려웠을 뿐만 아니라 순수주의자의 입장에서 보면 알고리즘의 실체가 없었다.

프로세스와 스레드 비교

Linux에서는 프로세스와 스레드를 동일한 것으로 간주하여 프로세스 및 스레드 스케줄링을 통합적으로 처리한다. 하나의 프로세스는 단일 스레드일 수도 있지만 여러 리소스(코드 및/또는 데이터)를 공유하는 여러 스레드를 포함할 수도 있다.

O(1) 스케줄러가 직면하고 있는 문제와 기타 외부 요인으로 인해 몇 가지 변경이 필요했다. 이 변경은 Con Kolivas의 Staircase scheduler에 포함되어 있던 RDSL(Rotating Staircase Deadline Scheduler)을 이용한 커널 패치를 통해 이루어졌다. 이 작업의 결과로 공평성과 한정 지연 특성이 통합되어 있는 단순하게 설계된 스케줄러가 제공되었다. Kolivas의 스케줄러는 많은 부분에 영향을 주었으며(최신 2.6.21 주류 커널에 통합하는 호출 사용) 그 이후 이 방향에 따라 스케줄러의 변경이 이루어졌다. O(1) 스케줄러의 작성자인 Ingo Molnar는 그 이후 Kolivas의 작업에서 얻은 몇 가지 아이디어를 바탕으로 CFS를 개발했다. 이제 상위 레벨에서 CFS가 작동하는 방법을 자세히 살펴보자.

CFS 개요

CFS의 기본 개념은 작업에 프로세서 시간을 제공할 때 밸런스(공평성)를 유지하는 것이다. 즉, 프로세스에 공평한 양의 프로세서가 제공되어야 한다. 작업 시간의 밸런스가 무너진 경우에는(다른 작업에 비해 하나 이상의 작업에 공평한 양의 시간이 주어지지 않은 경우) 작업 시간이 적게 지정된 작업에 실행 시간이 주어져야 한다.

CFS에서는 밸런스를 결정하기 위해 가상 런타임이라는 지정된 작업에 제공된 시간의 양을 관리한다. 작업의 가상 런타임이 작을수록 즉, 프로세서에 액세스할 수 있도록 허용된 시간이 작은 작업일수록 더 많은 프로세서 시간이 필요하다. 또한 CFS에는 대기자 공평성이라는 개념도 포함되어 있다. 이 개념은 현재 실행할 수 없는 작업(예를 들어, I/O를 대기 중인 작업)이 나중에 프로세서가 필요할 때 대기했던 시간에 상응하는 프로세서 시간을 받을 수 있도록 보장한다.

하지만 CFS는 이전 Linux 스케줄러와는 달리 실행 큐에서 작업을 관리하지 않고 시간순으로 정렬된 red-black 트리(그림 1 참조)를 유지한다. Red-black 트리에는 흥미롭고 유용한 두 가지 특성이 있다. 첫 번째는 스스로 밸런스를 조절한다는 것이다. 즉, 이 트리의 모든 경로는 다른 경로보다 두 배 이상 길어지지 않는다. 두 번째는 트리에 대한 작업이 O(log n) 시간(여기서 n는 트리의 노드 수임) 내에 발생한다는 것이다. 따라서 작업을 빠르고 효율적으로 삽입하거나 삭제할 수 있다.


그림 1. Red-black 트리의 예
Red-black 트리의 예

시간순으로 정렬된 red-black 트리에 저장되어 있는 작업(sched_entity 오브젝트로 표시됨)을 보여 주는 위 그림을 보면 프로세서에 대한 요구가 높은(가상 런타임이 낮은) 작업부터 차례대로 트리의 왼쪽에 저장되며 프로세서에 대한 요구가 가장 낮은(가상 런타임이 가장 높은) 작업이 트리의 맨 오른쪽에 저장된다. 그런 다음 스케줄러는 공평성을 유지하기 위해 red-black 트리의 맨 왼쪽 노드를 다음에 실행할 노드로 선택한다. 작업은 해당 실행 시간을 가상 런타임에 추가하여 CPU 사용 시간을 계산한 다음 실행 가능한 경우 트리로 다시 삽입된다. 이 방법에 따라 트리의 왼쪽에 있는 작업에 실행 시간이 지정되며 트리의 컨텐츠가 오른쪽에서 왼쪽으로 이동하면서 공평성이 유지된다. @@@따라서 실행 가능한 작업 세트 전체의 실행 밸런스를 유지하기 위해 실행 가능한 각 작업은 다른 작업을 따라서 이동한다.@@@

CFS 내부

Linux 내의 모든 작업은 task_struct라는 작업 구조체로 표시된다. 이 구조체는(연결된 다른 구조체와 함께) 작업을 완전히 설명하며 작업의 현재 상태, 해당 스택, 프로세스 플래그, 우선 순위(정적 및 동적) 등을 포함한다. ./linux/include/linux/sched.h에서 이 구조체와 기타 여러 관련 구조체를 볼 수 있다. 하지만 모든 작업이 실행 가능하지는 않기 때문에 task_struct에는 CFS 관련 필드가 없다. 대신 스케줄링 정보를 추적하기 위해 sched_entity라는 새 구조체가 작성되었다(그림 2 참조).


그림 2. 작업의 구조체 계층과 red-black 트리
작업의 구조체 계층과 red-black 트리

그림 2에서는 다양한 구조체의 관계를 보여 준다. 트리의 루트는 ./kernel/sched.c에 있는 cfs_rq 구조체의 rb_root 요소를 통해 참조된다. Red-black 트리의 리프에는 아무 정보도 없지만 내부 노드는 실행 가능한 하나 이상의 작업을 나타낸다. Red-black 트리의 각 노드는 rb_node로 표시되며 하위 참조와 상위 노드의 색만 포함한다. rb_nodesched_entity 구조체 내에 포함되며 이 구조체에는 rb_node 참조, 로드 중량 및 다양한 통계 데이터가 포함되어 있다. 무엇보다도 sched_entity에는 작업이 실행되면서 red-black 트리의 인덱스로 작동한 시간을 나타내는 vruntime(64비트 필드)이 포함되어 있다. 마지막으로 작업을 설명하고 sched_entity 구조체를 포함하는 task_struct가 맨 위에 있다.

CFS 부분과 관련된 스케줄링 함수는 매우 간단하다. @@@./kernel/sched.c를 보면 yield()를 통해 그 자체를 선취하지 않는 한 현재 실행 중인 작업을 선취하는 일반 schedule() 함수가 있다.@@@ CFS에는 선취에 대한 실제 시간 조각 개념이 없다. 이는 선취 시간이 가변적이기 때문이다. 현재 실행 중인 작업(선취된 작업)이 put_prev_task(스케줄링 클래스를 통해)에 대한 호출을 통해 red-black 트리로 리턴된다. 스케줄링할 다음 작업을 식별할 때가 되면 schedule 함수가 pick_next_task 함수를 호출한다. 이 함수도 ./kernel/sched.c에 있는 일반 함수이지만 스케줄러 클래스를 통해 CFS 스케줄러를 호출한다. CFS의 pick_next_task 함수는 ./kernel/sched_fair.c(pick_next_task_fair()라고 함)에 있다. 이 함수는 단순히 red-black 트리에서 가장 왼쪽에 있는 작업을 선택하여 연관된 sched_entity를 리턴한다. 간단한 task_of() 호출에서 이 참조를 사용하여 리턴된 task_struct 참조를 식별한다. 마지막으로 일반 스케줄러가 이 작업에 프로세서를 제공한다.

우선 순위와 CFS

CFS에서는 우선 순위를 직접 사용하지 않는 대신 작업에 허용된 실행 시간에 대한 지연 인수로 사용한다. 우선 순위가 낮을수록 지연 인수가 높은 작업이며, 우선 순위가 높을수록 지연 인수가 낮은 작업이다. 이는 우선 순위가 높은 작업보다 우선 순위가 낮은 작업에서 작업에 허용된 실행 시간이 더 빨리 소진된다는 것을 의미한다. 이 방법은 우선 순위별로 실행 큐를 관리하지 않아도 되는 효과적인 방법이다.

CFS 그룹 스케줄링

CFS의 또 하나 흥미로운 특징은 2.6.24 커널에서 도입된 그룹 스케줄링 개념이다. 그룹 스케줄링은 스케줄링의 공평성을 높일 수 있는 또 다른 방법으로, 특히 그 안에서 다른 많은 작업이 발생하는 작업의 경우 효과가 높다. HTTP 서버의 전형적인 아키텍처와 같이 들어오는 연결을 병렬 처리하기 위해 많은 작업이 발생하는 서버를 가정해 보자. CFS에서는 모든 작업을 균등하게 처리하는 대신 이 동작을 처리하기 위해 그룹을 사용한다. 작업이 발생하는 서버 프로세스는 계층 구조로 되어 있는 전체 그룹에 대한 가상 런타임을 공유하는 반면 단일 작업은 고유한 독립 가상 런타임을 관리한다. 이 방법에서는 단일 작업이 그룹과 거의 비슷한 스케줄링 시간을 받는다. /proc 인터페이스는 프로세스 계층 구조를 관리하는 데 사용되며, 그룹을 형성하는 방법에 대한 전체 제어를 제공한다. 이 구성을 사용하면 사용자, 프로세스 또는 각 변형 전체에 대한 스케줄을 공평하게 할당할 수 있다.

스케줄링 클래스 및 도메인

CFS에서는 스케줄링 클래스(그림 2 참조)라는 개념도 도입되었다. 각 작업은 스케줄링 클래스에 속하며, 이 스케줄링 클래스에 따라 작업의 스케줄링 방법이 결정된다. 스케줄링 클래스는 sched_class를 통해 스케줄러의 동작을 정의하는 공통 함수 세트를 정의한다. @@@예를 들어, 각 스케줄러는 스케줄링할 작업을 추가하고, 실행할 다음 작업을 가져오고, 스케줄러에게 양도하는 등의 작업을 수행할 수 있는 방법을 제공한다.@@@ 각 스케줄러 클래스는 단일 연결 목록을 통해 다른 하나의 스케줄러와 연결되어 있으므로 이 연결을 따라 클래스를 반복할 수 있다(예를 들어, 지정된 프로세서의 비활성화를 활성화하기 위해). 그림 3에서는 일반적인 구조체를 보여 준다. 이 그림에서 enqueue_task 및 dequeue_task 함수는 특정 스케줄링 구조체에 작업을 추가하거나 제거하는 단순한 작업을 수행한다. pick_next_task 함수는 스케줄링 클래스의 특정 정책에 따라 실행할 다음 작업을 선택한다.


그림 3. 스케줄링 클래스의 그래픽 보기
스케줄링 클래스의 그래픽 보기

하지만 스케줄링 클래스도 작업 구조체의 일부이기 때문에(그림 2 참조) 해당 스케줄링 클래스와 상관 없이 작업에서 수행할 연산이 단순해진다. 예를 들어, 다음 함수는 새 작업을 사용하여 현재 실행 중인 작업을 ./kernel/sched.c로부터 선취한다. (여기서 curr은 현재 실행 중인 작업을 정의하고, rq는 CFS에 대한 red-black 트리를 나타내며 p는 스케줄링할 다음 작업이다.)

static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
  rq->curr->sched_class->check_preempt_curr( rq, p );
}

이 작업이 공평한 스케줄링 클래스를 사용하고 있다면 check_preempt_curr()check_preempt_wakeup()으로 해석된다. ./kernel/sched_rt.c, ./kernel/sched_fair.c 및 ./kernel/sched_idle.c에서 이러한 관계를 볼 수 있다.

스케줄링 클래스는 여전히 스케줄링 변경의 흥미로운 특징으로 남아 있지만 스케줄링 도메인의 추가로 그 기능이 확장되었다. 이러한 도메인을 사용하면 로드 밸런싱 및 분리를 위해 하나 이상의 프로세서를 그룹화할 수 있다. 하나 이상의 프로세서가 스케줄링 정책(및 로드 밸런스)을 공유하거나 독립 스케줄링 정책을 구현하여 작업을 의도적으로 분리할 수 있다.

출처 : http://www.ibm.com/developerworks/kr/library/l-completely-fair-scheduler/

'Linux Kernel' 카테고리의 다른 글

Spin lock 이란?  (1) 2012.02.12
Ctags 사용법  (0) 2012.02.10
Linux CFS 스케줄링 알고리즘 정리  (0) 2012.02.10
Linux 의 Directory구조 ¶  (1) 2012.02.10
리눅스 부팅 프로세스 연구  (0) 2012.02.05
모노리딕 커널과 마이크로 커널의 차이..  (0) 2012.02.04
Posted by Embedded LAB 프로그래밍하는 피카츄

댓글을 달아 주세요

최근에 달린 댓글

글 보관함