[운영체제 공룡책] 운영체제 별 프로세스 스케줄링
Posted: Updated:
운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.
운영체제 별 프로세스 스케줄링
Linux 스케줄링
버전 2.5 전까지는 UNIX 스케줄링 알고리즘의 변형을 사용하여 SMP 시스템을 염두하지 않아 성능이 저조했다.
버전 2.5에서 시스템에 존재하는 태스크 개수와 상관없이 항상 상수 시간에 실행되는 스케줄링 알고리즘이 포함되었다.
이 $O(1)$ 스케줄러는 SMP 시스템에서는 성능이 좋았지만, 대화형 프로세스에서 느린 응답 시간을 보여 2.6.23 커널부터 완전 공평 스케줄러(Completely Fair Scheduler, CFS)가 시스템 디폴트 스케줄링 알고리즘이 되었다.
각 클래스별로 특정 우선순위를 부여받는 스케줄링 클래스에 기반하여 동작한다.
표준 Linux 커널은 CFS 스케줄링 알고리즘을 사용하는 디폴트 스케줄링 클래스와 CFS보다 높은 우선 순위를 가진 실시간 스케줄링 클래스를 구현한다.
CFS는 상대 우선순위에 상응하는 시간 할당량을 정하지 않고, 각 태스크에 CPU 처리 시간 비율을 할당한다.
이 비율은 nice 값에 기반을 두고 계산된다.
Nice 값
-20부터 +19까지의 범위를 가지며, 낮을수록 우선순위가 높다.
낮은 nice 값을 가지면 높은 nice 값을 가진 태스크보다 많은 CPU 처리시간을 할당받는다.
목적 지연시간(targeted latency)
목적 지연시간이란 실행 가능한 모든 태스크가 최소 한 번은 실행될 수 있는 시간 간격이다.
CFS는 고정된 시간 할당량 대신 목적 지연시간을 사용한다.
CPU 시간 비율은 목적 지연시간의 값으로부터 할당되며, 시스템상에 활성 태스크의 개수가 일정 임계값보다 많아지면 증가할 수 있다.
가상 실행 시간(vruntime)
CFS에서는 직접적인 우선순위를 사용하지 않고, 각 태스크별로 vruntime이라는 변수에 태스크가 실행된 시간을 기록하여 우선순위를 판단한다.
태스크의 우선순위에 기반을 둔 감쇠 지수(decay factor)에 따라 우선순위가 높은 태스크는 vruntime이 천천히 증가하고, 낮은 우선순위는 빨리 증가한다.
두 태스크가 같은 nice 값을 가지고 하나는 I/O 중심, 다른 하나는 CPU 중심이라면 I/O 중심 태스크의 vruntime이 작게 증가하여 더 자주 CPU를 점유할 수 있다.
SCHED_FIFO, SCHED_RR 실시간 스케줄링
POSIX 표준을 사용하여 실시간 스케줄링을 구현한다.
실시간 태스크는 일반 태스크보다 높은 우선순위를 가지며, 실시간 태스크는 0부터 99사이의 정적 우선순위를 부여받으며 보통의 태스크는 100에서 139까지의 영역에서 부여받는다.
NUMA 인식 스케줄링
NUMA를 인식하고 스레드 이주를 최소화하는 정교한 기술을 사용하여 부하 균등화를 지원한다.
스레드의 우선순위와 평균 CPU 이용률의 조합으로 각 스레드의 부하를 정의한다.
스레드를 이주하면 캐시 내용을 무효화해야 하거나 NUMA 시스템에서 메모리 액세스 시간이 길어져 메모리 액세스 불이익이 발생할 수 있다.
이를 해결하기 위해 스케줄링 도메인의 계층적 시스템을 결정한다.
스케줄링 도메인
서로 부하를 공유하거나 캐시를 공유하는 CPU 코어의 집합이다.
각 스케줄링 도메인의 코어는 시스템 자원을 공유하는 방법에 따라 그룹화된다.
각 코어에 자기 자신만의 레벨 1(L1) 캐시가 있을 수 있고, 한 쌍의 코어는 레벨 2(L2) 캐시를 공유할 수 있다.
마찬가지로 두 도메인이 레벨 3(L3) 캐시를 공유할 수 있어 프로세서 수준 도메인(혹은 NUMA 노드)으로 구성된다.
따라서 CFS는 가장 낮은 도메인부터 시작해 도메인 내부의 부하 균형을 맞추려 하고, 처음에는 동일한 도메인의 코어 간에서만 이주가 이루어지다가 심각한 부하 뷸균형이 일어날 때만 다른 NUMA 노드로 스레드를 이동시킨다.
Windows 스케줄링
Windows는 우선순위 기반 선점 스케줄링 알고리즘을 사용한다.
항상 가장 높은 우선순위의 스레드가 실행되도록 보장되며, 커널 중 스케줄링을 담당하는 부분을 디스패처(dispatcher)라고 한다.
우선순위가 높은 스레드가 준비되면 실행 중인 낮은 우선순위 스레드는 선점된다.
스레드는 가변 클래스(Variable Class)와 실시간 클래스(Real-Time Class)로 나뉘며, 가변 클래스에 있는 스레드는 우선순위가 1부터 15이며 실시간 클래스는 우선순위 16부터 31까지의 스레드를 포함한다.
우선순위가 0인 스레드는 메모리 관리에 사용된다.
디스패처가 각 우선순위를 위해 큐를 사용하고, 큐를 높은 우선순위부터 낮은 우선순위까지 조사해 준비 상태의 스레드가 있는지 확인한다.
준비 상태의 스레드가 없으면 idle 스레드라고 불리는 특수한 스레드를 실행한다.
Windows API에서는 다음과 같은 6가지 우선순위 클래스를 제공한다.
- IDLE PRIORITY CLASS
- BELOW NORMAL PRIORITY CLASS
- NORMAL PRIORITY CLASS
- ABOVE NORMAL PRIORITY CLASS
- HIGH PRIORITY CLASS
- REALTIME PRIORITY CLASS
일반적으로 프로세스는 NORMAL_PRIORITY_CLASS에 속하고, 명시하지 않으면 기본값으로 사용된다.
REALTIME_PRIORITY_CLASS 를 제외한 모든 우선순위 클래스는 가변적으로, 클래스에 속한 스레드의 우선순위가 변할 수 있다.
각 스레드의 우선순위는 그 스레드가 속한 우선순위 클래스와 클래스 안에서의 상대적인 우선순위(relative priority)에 기반을 둔다.
그리고 각 스레드는 스레드가 속한 클래스의 우선순위 범위의 값을 기본 우선순위로 배정받는다.
스레드의 초기 우선순위는 스레드가 속한 프로세스의 기본 우선순위가 배정되지만, 변경할 수 있다.
시간 할당량이 만료되어 인터럽트 된 스레드가 가변 우선순위 클래스에 속한다면 우선순위가 낮아진다.
하지만 기본 우선순위보다는 낮아지지 않는다.
스레드의 우선순위가 낮차지면 계산 중심 스레드들이 CPU를 독점하는 것을 제한하게 된다.
가변 우선순위 스레드가 대기 연산에서 풀려나면 디스패처가 우선순위를 높여준다.
사용자와 상호작용이 필요할 경우 우선순위를 높게 받아 응답 시간이 향상된다.
대화형 프로그램의 프로세스는 좋은 성능이 필요하므로, 포그라운드 프로세스와 백그라운드 프로세스를 구분한다.
Windows에서는 포그라운드 프로세스가 되면 시간 할당량을 3배 정도 증가시키는 방법을 사용한다.
사용자 모드 스케줄링(User-Mode Scheduling, UMS)을 통해 응용 프로그램은 커널과 독립적으로 스레드를 직접 만들고 관리할 수 있다.
Windows 커널 스케줄러의 도움 없이 여러 스레드를 생성하고 스케줄할 수 있다.
스레드의 선호도, 최근에 실행된 프로세서의 유지 관리를 통해 해당하는 스레드에 가장 적합한 처리 코어에 스레드가 스케줄 되도록 한다.
논리 프로세서 집합(SMT 집합)을 통해 여러 논리 프로세서에 부하를 분배하기 위해 각 스레드에 스레드가 선호하는 프로세서를 나타내는 숫자인 이상적인 프로세서를 배정한다.
Solaris 스케줄링
Solaris는 우선순위 기반 스레드 스케줄링을 사용하며, 우선순위에 따라 다음 6개의 스케줄링 클래스를 정의한다.
- 시분할 (Time-Sharing, TS)
- 대화형 (Interactive, IA)
- 실시간 (Real Time, RT)
- 시스템 (System, SYS)
- 공평 공유 (Fair Share, FSS)
- 고정 우선순위 (Fixed Priority, FP)
디폴트 스케줄링 클래스는 시분할로, 다단계 피드백 큐를 사용해 동적으로 우선순위를 바꿔 서로 다른 길이의 타임 슬라이스를 할당한다.
또한, 우선순위와 타임 슬라이스 사이에 반비례 관계가 존재해 우선순위가 높을수록 타임 슬라이스가 더 작고, 우선순위가 낮을수록 타임 슬라이스가 더 크다.
대화형 프로세스는 높은 우선순위를 가지고, CPU 위주의 프로세스는 낮은 우선순위를 가진다.
소수의 실시간 프로세스는 가장 높은 우선순위가 주어지며, 제한된 주기 내에 시스템으로부터 응답을 보장받도록 한다.
커널 스레드를 실행하기 위해 시스템 클래스를 사용한다.
고정 우선순위 클래스의 스레드는 시분할 클래스의 스레드와 같은 우선순위를 갖지만, 동적으로 조정되지 않는다.
공평 공유 클래스는 스케줄링 결정을 위해 우선순위 대신 CPU 공유량(share)을 사용한다.
CPU 공유량은 가용한 CPU 자원에 대한 권리(entitlement)를 가리키며, 프로젝트(project)라고 불리는 프로세스의 집합에 할당된다.
댓글남기기