개념정리
SMP (symmetric multiprocessing) ; 대칭형 다중처리
SMP는 운영체계와 메모리를 공유하는 여러 프로세서가 프로그램을 수행하는 것을 말한다. SMP에서는 프로세서가 메모리와 입출력 버스 및 데이터 path를 공유하며, 또한 하나의 운영체계가 모든 프로세서를 관리한다. 보통 2개부터 32개의 프로세서로 이루어지며, 어떤 시스템은 64개까지 프로세서를 공유한다.
SMP시스템은 보통 MPP시스템에 비하여 병렬 프로그래밍이 훨씬 쉽고, 프로세서간 작업 분산(workload balance)시키는 것은 훨씬 용이하지만, 확장성은 MPP에 비하여 취약하다. 또한 많은 사용자가 동시에 데이터베이스에 접근하여 일을 처리하는 OLTP 작업에서도 강점을 보인다
NUMA (non-uniform memory access)
NUMA[누마]는 멀티프로세싱 시스템에서 지역적으로는 메모리를 공유하며, 성능을 향상시키고, 시스템 확장성이 있도록 마이크로프로세서 클러스터를 구성하기 위한 방법이다. NUMA는 SMP 시스템에서 사용된다. SMP 시스템은 서로 밀접하게 결합되어, 모든 것을 공유하는 시스템으로서, 다중 프로세서들이 하나의 단일 운영체계 하에서 공통의 버스를 통해 각자의 메모리를 액세스한다. 보통, SMP의 한계는 마이크로프로세서가 추가됨에 따라, 공유 버스나 데이터 경로가 과중한 부하가 생기게 되어, 성능에 병목현상이 일어나는데 있다. NUMA는 몇 개의 마이크로프로세서들 간에 중간 단계의 공유메모리를 추가함으로써, 모든 데이터 액세스가 주버스 상에서 움직이지 않아도 되도록 한다.
NUMA는 하나의 상자 속에 있는 클러스터로 생각할 수 있다. 클러스터는 대체로 마더보드 상의 하나의 공유 메모리 (L3 캐시라고도 부른다)로 향하는 로컬버스에, 서로 연결된 네 개의 마이크로프로세서들로 구성된다. 이 유니트는 모든 클러스터들을 서로 연결하는 공용 버스 내에서 SMP를 구성하기 위하여 비슷한 유니트에 추가될 수 있다. 이러한 시스템은 대체로 16~256개의 마이크로프로세서를 가지고 있다. SMP 시스템에서 실행되는 응용프로그램에게는, 모든 개별 프로세서 메모리들이 하나의 단일 메모리인 것처럼 비쳐진다.
프로세서가 어떤 메모리 주소에 있는 데이터를 찾을 때, 그것은 마이크로프로세서 그 자체에 붙어 있는 L1 캐시를 먼저 찾은 다음, 근처에 있는 다소 큰 L2 캐시 칩을 찾는다. 그 다음에는 다른 마이크로프로세서 인근에 있는 원격 메모리의 데이터를 찾기 전에, NUMA 구성에 의해 제공되는 제3의 캐시를 찾는다. NUMA에게는, 이러한 클러스터들 각각이 서로 연결된 네트웍 내에 있는 하나의 노드들 처럼 비쳐진다. NUMA는 모든 노드들 상에 있는 데이터를 계층 체계로 유지한다.
NUMA SMP 시스템의 클러스터들 사이에 있는 버스에서는 SCI (scalable coherent interface) 기술을 사용하여 데이터가 움직인다. SCI는 다중 클러스터의 노드에 걸쳐 캐시 일관성이라고 불리는 것과 대등하다.
SMP와 NUMA 시스템은 대체로 공통의 데이터베이스 상에 집단적으로 작업하는 많은 수의 프로세서들에게, 작업 처리를 분담시킬 수 있는 데이터 마이닝과 의사결정 시스템 등과 같은 분야에 사용된다. 시퀀트, 데이터제너럴, NCR 등이 NUMA SMP 시스템을 생산하는 회사들이다.
Linux 2.6 Completely Fair Scheduler
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는 트리의 노드 수임) 내에 발생한다는 것이다. 따라서 작업을 빠르고 효율적으로 삽입하거나 삭제할 수 있다.
시간순으로 정렬된 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 트리
그림 2에서는 다양한 구조체의 관계를 보여 준다. 트리의 루트는 ./kernel/sched.c에 있는 cfs_rq 구조체의 rb_root 요소를 통해 참조된다. Red-black 트리의 리프에는 아무 정보도 없지만 내부 노드는 실행 가능한 하나 이상의 작업을 나타낸다. Red-black 트리의 각 노드는 rb_node로 표시되며 하위 참조와 상위 노드의 색만 포함한다. rb_node는 sched_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의 또 하나 흥미로운 특징은 2.6.24 커널에서 도입된 그룹 스케줄링 개념이다. 그룹 스케줄링은 스케줄링의 공평성을 높일 수 있는 또 다른 방법으로, 특히 그 안에서 다른 많은 작업이 발생하는 작업의 경우 효과가 높다. HTTP 서버의 전형적인 아키텍처와 같이 들어오는 연결을 병렬 처리하기 위해 많은 작업이 발생하는 서버를 가정해 보자. CFS에서는 모든 작업을 균등하게 처리하는 대신 이 동작을 처리하기 위해 그룹을 사용한다. 작업이 발생하는 서버 프로세스는 계층 구조로 되어 있는 전체 그룹에 대한 가상 런타임을 공유하는 반면 단일 작업은 고유한 독립 가상 런타임을 관리한다. 이 방법에서는 단일 작업이 그룹과 거의 비슷한 스케줄링 시간을 받는다. /proc 인터페이스는 프로세스 계층 구조를 관리하는 데 사용되며, 그룹을 형성하는 방법에 대한 전체 제어를 제공한다. 이 구성을 사용하면 사용자, 프로세스 또는 각 변형 전체에 대한 스케줄을 공평하게 할당할 수 있다.
CFS에서는 스케줄링 클래스(그림 2 참조)라는 개념도 도입되었다. 각 작업은 스케줄링 클래스에 속하며, 이 스케줄링 클래스에 따라 작업의 스케줄링 방법이 결정된다. 스케줄링 클래스는 sched_class를 통해 스케줄러의 동작을 정의하는 공통 함수 세트를 정의한다. @@@예를 들어, 각 스케줄러는 스케줄링할 작업을 추가하고, 실행할 다음 작업을 가져오고, 스케줄러에게 양도하는 등의 작업을 수행할 수 있는 방법을 제공한다.@@@ 각 스케줄러 클래스는 단일 연결 목록을 통해 다른 하나의 스케줄러와 연결되어 있으므로 이 연결을 따라 클래스를 반복할 수 있다(예를 들어, 지정된 프로세서의 비활성화를 활성화하기 위해). 그림 3에서는 일반적인 구조체를 보여 준다. 이 그림에서 enqueue_task 및 dequeue_task 함수는 특정 스케줄링 구조체에 작업을 추가하거나 제거하는 단순한 작업을 수행한다. pick_next_task 함수는 스케줄링 클래스의 특정 정책에 따라 실행할 다음 작업을 선택한다.
하지만 스케줄링 클래스도 작업 구조체의 일부이기 때문에(그림 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에서 이러한 관계를 볼 수 있다.
스케줄링 클래스는 여전히 스케줄링 변경의 흥미로운 특징으로 남아 있지만 스케줄링 도메인의 추가로 그 기능이 확장되었다. 이러한 도메인을 사용하면 로드 밸런싱 및 분리를 위해 하나 이상의 프로세서를 그룹화할 수 있다. 하나 이상의 프로세서가 스케줄링 정책(및 로드 밸런스)을 공유하거나 독립 스케줄링 정책을 구현하여 작업을 의도적으로 분리할 수 있다.
@@@스케줄링 작업을 계속하다 보면 성능 및 확장성이 향상된 개발 중인 스케줄러를 만날 수 있다. Con Kolivas는 자신의 Linux 경험에 안주하지 않고 BFS라는 도발적인 약어를 사용하는 또 다른 Linux용 스케줄러를 개발했다.@@@ 이 스케줄러는 NUMA 시스템과 모바일 장치에서 향상된 성능을 제공하는 것으로 보고되었으며 파생 Android 운영 체제에 도입되었다.
Linux에 항상 적용되는 한 가지 사실이 있다면 그것은 바로 변화가 필연적이라는 것이다. 현재는 CFS가 2.6 Linux 스케줄러이지만 미래에는 정적 또는 동적으로 호출할 수 있는 또 다른 새 스케줄러 또는 스케줄러 스위트일 수도 있을 것이다. CFS, RSDL 및 커널과 관련된 프로세스가 매우 복잡함에도 불구하고 Kolivas와 Molnar의 노력으로 2.6 작업 스케줄링에서 새로운 수준의 공평성을 유지할 수 있게 되었다.
SpinLock & Ticket SpinLock
이름이 뜻하는대로, 만약 다른 스레드가 lock을 소유하고 있다면 그 lock이 반환될 때까지 계속 확인하며 기다리는 것이다. 즉 mutiprocessor system에서 여러 processor가 동시에 critical section에 진입하지 못하도록 하는 synchronization 기법이다. 한 processor가 lock을 가지고 있으면 다른 processor들은 unlock될 때까지 busy-wait하다가 lock을 차지하기 위해 동시에 lock 변수에 접근(write)한다.
여기서 두 가지 문제가 발생할 수 있는데 첫 번째는 각 processor 간에 lock을 획득하는 순서를 보장할 수 없기 때문에 먼저 spin lock을 기다리던 processor가 더 나중에 lock을 얻을 수도 있다는 것이다. 때문에 spin lock은 공정하지 못하다.
또 하나의 문제는 성능에 관련된 것으로 cache coherency로 인해 한 processor가 lock 변수에 write를 하게되면 다른 모든 processor의 cache line이 invalidate된다. 따라서 contention이 심한 경우 lock을 얻은 processor에서도 반복적으로 cache miss가 발생하여 실행 성능이 매우 나빠질 수 있다. (보통 lock 변수와 데이터는 같은 line에 놓여있을 것이다.)
Spin Lock 은 다음과 같은 특성을 갖는다.
1. Lock을 얻을 수 없다면, 계속해서 Lock을 확인하며 얻을 때까지 기다린다. 이른바 바쁘게 기다리는 busy wating이다.
2. 바쁘게 기다린다는 것은 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는 것이다.
3. Lock이 곧 사용가능해질 경우 컨택스트 스위치를 줄여 CPU의 부담을 덜어준다. 하지만, 만약 어떤 스레드가 Lock을 오랫동안 유지한다면 오히려 CPU 시간을 많이 소모할 가능성이 있다.
4. 하나의 CPU나 하나의 코어만 있는 경우에는 유용하지 않다. 그 이유는 만약 다른 스레드가 Lock을 가지고 있고 그 스레드가 Lock을 풀어 주려면 싱글 CPU 시스템에서는 어차피 컨택스트 스위치가 일어나야하기 때문이다.
ticket spin lock은 이를 개선하기 위해 2.6.25 버전부터 도입된 것으로 lock을 기다리는 각 processor들은 자신 만의 ticket을 부여받고 자기 차례가 돌아오는 경우에만 write를 시도하므로 순서대로 lock을 얻을 수 있으며 전체적으로 cache miss 횟수를 줄일 수 있다.
CFS(Completely Fair Scheduler) : http://www.ibm.com/developerworks/kr/library/l-completely-fair-scheduler/
spinlock : http://dev.heartsavior.net/315
ticket spinlock : http://studyfoss.egloos.com/5144295 , http://lwn.net/Articles/267968/
tickless kernel : http://www.zdnet.co.kr/ArticleView.asp?artice_id=00000039158842