5. CPU Scheduling

CPU 스케쥴링은 다중 프로그램 운영 체제의 기본이다. CPU를 프로세스간 전환을 해서 운영 체제는 컴퓨터를 더 생산적으로 만들 수 있다. 현대 운영 체제에서 운영 체제에 의해 스케쥴링되는 것은 프로세스가 아니라 커널 레벨의 스레드이다. 이 장에서는 프로세스 스케쥴링과 스레드 스케쥴링을 구분해 사용하도록 한다. 이 장에서 CPU에서 가동된다는 것은 CPU의 코어에서 가동된다는 뜻이다.

5.1. Basic Concepts

단일 CPU 코어 시스템에서 한 번에 하나의 프로세스만 동작할 수 있다. 다른 프로세스는 CPU 코어가 놀 때까지 기다려야 한다. 멀티프로그래밍의 목적은 CPU 활용을 최대화하기 위해 항상 프로세스를 수행하도록 한다. 발상은 I/O 요청 등을 위해 대기가 걸리기까지 프로세스를 동작하고, 대기하는 동안 다른 프로세스로 CPU를 전환하고, 이를 반복하는 것이다. 다중 CPU 코어 시스템에서는 이것이 여러 CPU 코어에 대해 확장된다. CPU는 주된 컴퓨터 자원이므로 스케줄링은 운영 체제에 있어 핵심적이다.

5.1.1. CPU-I/O Burst Cycle

성공적인 CPU 스케쥴링은 관측되는 프로세스의 특성에 의존한다. 프로세스 실행은 CPU 버스트I/O 버스트사이클로 이루어져 실행 종료에 대한 시스템 요청으로 끝난다. CPU 버스트 시간을 측정했을 때에는 짧은 버스트 빈도가 높고 긴 버스트 빈도는 낮다. 이 분포는 CPU 스케쥴링 알고리즘을 설계할 때 중요하다.

5.1.2. CPU Scheduler

운영 체제는 CPU 스케쥴러를 통해 실행 대기 큐에 있는 프로세스 중 하나를 선택한다. 이 큐는 선입선출일 필요가 없다. 이 큐 내의 기록은 프로세스의 프로세스 제어 블록으로 이루어져 있다.

5.1.3. Preemptive and Nonpreemptive Scheduling

CPU 스케쥴링은 다음의 4가지 환경에서 이루어진다.

  • 프로세스가 동작 상태에서 대기 상태로 전환할 때
  • 프로세스가 동작 상태에서 준비 상태로 전환할 때
  • 프로세스가 대기 상태에서 준비 상태로 전환할 때
  • 프로세스가 종료될 때

1, 4번의 상황에서는 스케쥴링에 있어서는 새 프로세스를 선택하는 것 외에 선택지가 없다. 2, 3번의 상황에서는 선택지가 있다. 1, 4번 상황만 있는 경우를 비선점(협업적) 스케쥴링, 이외를 선점 스케쥴링이라 한다. 비선점 스케쥴링에서는 CPU가 프로세스에 할당된 뒤에는 대기 상태로 전환하거나 종료될 때까지 프로세스가 CPU를 점유한다. 대부분의 현대 운영 체제는 선점 스케쥴링을 쓴다. 선점 스케쥴링은 데이터가 여러 프로세스간 공유될 때 레이스 컨디션을 일으킬 수 있다. 또한, 운영 체제 커널의 설계에도 영향을 미친다. 시스템 호출 도중에 커널은 프로세스 실행을 통해서 중요한 커널 데이터를 변경 중일 수 있다. 이 때 이 변경 도중에 커널이 같은 구조체를 읽거나 수정할 필요가 있다면 어떻게 해야 할까? 비선점 커널은 프로세스를 종료시키는 시스템 호출을 기다리거나 프로세스를 컨텍스트 스위치 이전 I/O가 완료될 때까지 대기시킨다. 이는 커널 구조가 간단하도록 보장하는데, 커널 자료 구조의 상태가 비일관적인 경우 프로세스를 선점하지 않기 때문이다. 하지만 이 커널 실행 모델은 실시간 컴퓨팅을 지원하는 데는 적합하지 않다. 선점성 커널은 공유 커널 자료 구조에 접근할 때의 레이스 컨디션을 막기 위해서 뮤텍스 같은 메커니즘을 필요로 한다. 대부분의 현대적 운영 체제는 커널 모드를 실행할 때 완전히 선점적이다.

인터럽트는 언제나 발생할 수 있으며 커널에 의해 무시되면 안 되기 때문에, 인터럽트에 의해 영향받는 코드의 부분은 동시적인 사용에 대해 보호되어야 한다. 운영 체제는 인터럽트를 거의 항상 수용해야 하는데, 아니면 입력이 유실되거나 출력이 덮어씌워지기 때문이다. 그러므로 이 코드 섹션은 여러 프로세스에 의해 동시적으로 접근되면 안 되므로, 진입 시에 인터럽트를 비활성화시키고 빠져나올 때 인터럽트를 재활성화시킨다. 이런 상황은 흔하진 않으며 몇 명령어에 대해 제한되어 있다.

5.1.4. Dispatcher

CPU 스케쥴링 기능에 포함된 다른 컴포넌트는 디스패쳐이다. 이는 CPU 코어에 대한 제어권을 CPU 스케쥴러에 의해 선택된 프로세스에 주는 모듈이다. 이 기능은:

  • 한 프로세스에서 다른 프로세스로 컨텍스트를 전환
  • 사용자 모드로 전환
  • 사용자 프로그램의 적절한 부분으로 점프해 프로그램을 재개

디스패쳐는 컨텍스트 스위칭마다 실행되므로 최대한 빨라야 한다. 디스패쳐가 프로세스를 중지하고 다른 프로세스를 실행하기까지 걸리는 시간을 디스패치 지연 시간이라 한다. 컨텍스트 스위치는 얼마나 자주 일어나는가? Linux에서는 vmstat 등의 명령어로 알 수 있다. 또한 특정 프로세스에 대해서는 /proc 파일 시스템을 쓸 수도 있다. 컨텍스트 스위치는 자발적, 비자발적으로 나뉜다.

5.2. Scheduling Criteria

서로 다른 스케쥴링 알고리즘은 서로 다른 스케쥴링 기준을 가진다. 여러 기준들은 다음과 같다.

  • CPU 활용 : CPU 활용성을 최대화시키고자 할 때.
  • 처리량 : 시간당 완료되는 프로세스의 수, 즉 처리량을 최대화시키고자 할 때.
  • 턴어라운드 시간 : 프로세스를 실행하기까지의 시간을 최소화시키고자 할 때.
  • 대기 시간 : 대기 큐에서의 대기 시간을 최소화시키고자 할 때.
  • 응답 시간 : 요청에 대해 응답하기까지의 시간을 최소화시키고자 할 때.

대부분 이들 사이에서 균형을 맞춘다. 하지만 모든 사용자가 좋은 서비스를 받음을 보장시키고자 하는 상황 등에서는 최대 대기 시간을 최소화시키는 것이 좋을 것이다. 상호 작용적 시스템에서는 대기 시간의 분산을 최소화시키는 것이 더 낫지만, 이 방면으로 많은 연구가 이뤄지지는 않았다.

5.3. Scheduling Algorithms

CPU 스케쥴링은 준비 큐에 있는 프로세스 중 어떤 것이 CPU 코어에 할당되어야 할지를 결정한다. CPU 스케쥴링 알고리즘은 여러 가지가 있다. 이 장에서는 프로세싱 코어는 하나라고 가정한다.

5.3.1. First-Come, First-Served Scheduling

가장 간단한 CPU 스케쥴링 알고리즘은 선도착 선처리(FCFS) 스케쥴링 알고리즘이다. 이는 선입선출 큐를 통해 간단히 구현될 수 있다. 하지만 평균 대기 시간이 길다. 이는 간트 차트를 통해 알아볼 수 있다. 선도착 선처리 알고리즘에서는 모든 다른 프로세스가 하나의 큰 프로세스를 대기하는 호송 효과가 일어나기 쉽다. 이는 CPU 활용도를 낮춘다. 선도착 선처리 알고리즘은 비선점적이다.

5.3.2. Shortest-Job-First Scheduling

다른 접근법은 최단 작업 우선(SJF) 스케쥴링 알고리즘이다. 이는 CPU 버스트가 가장 짧은 프로세스를 대기 큐에서 선택한다. 이는 최단 평균 대기 시간을 최적화하는 데 있어서 최적이다. 하지만 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케쥴링 레벨에서 구현될 수는 없다. 그래서 이전 CPU 버스트들의 지수적 평균을 이용해 다음 CPU 버스트를 근사한다. 최단 작업 우선 알고리즘은 선점적일 수도 있고 비선점적일 수도 있다. 선점적 최단 작업 우선 알고리즘은 최단 잔여시간 우선 스케쥴링이라 한다.

5.3.3. Round-Robin Scheduling

순차-순환(RR) 스케쥴링은 선도착 선처리 스케쥴링과 비슷하지만 프로세스간 전환을 가능케 하기 위해 선점이 추가된다. 이 때 시간 퀀텀 또는 시간 슬라이스라는 작은 시간의 단위가 정의된다. 이는 대개 10-100ms이며 CPU 스케쥴러는 대기 큐를 순회하며 이 단위에 따라 각 프로세스를 할당한다. 이 때 대기 큐는 선입선출 순환 큐로 구현된다. 순차-순환 스케쥴링은 선점적이다. 이 알고리즘의 성능은 시간 퀀텀의 크기에 의존한다. 시간 퀀텀 크기가 크면 선도착 선처리 스케쥴링과 다를 바가 없다. 시간 퀀텀 크기가 작으면 컨텍스트 스위치가 너무 빈번해진다. 또한 턴어라운드 시간도 시간 퀀텀의 크기에 의존한다. 널리 통하는 법칙은 CPU 버스트의 80퍼센트는 시간 퀀텀보다 짧아야 한다는 것이다.

5.3.4. Priority Scheduling

최단 작업 우선 알고리즘은 일반적인 우선도 스케쥴링 알고리즘의 특수한 경우이다. 프로세스 각각에 우선도가 매겨지고 CPU는 이 우선도를 기반으로 스케쥴링한다. 같은 우선도를 가진 프로세스는 선도착 선처리 알고리즘으로 할당된다. 우선도는 다양한 방법으로 계산된다. 우선도 스케쥴링은 선점적일 수도 있고 비선점적일 수도 있다. 선점적일 경우 새로 도착한 프로세스의 우선도가 현재 수행 중인 프로세스보다 우선도가 높다면 CPU를 선점한다. 비선점적일 경우 새 프로세스를 대기 큐의 맨 앞에 넣는다.

우선도 스케쥴링 알고리즘의 주된 문제는 무기한 차단 또는 기아 이다. 이는 우선도가 낮은 프로세스들이 기약 없이 기다리게 된다는 점이다. 이에 대한 해결책으로는 에이징으로, 프로세스가 대기한 시간에 따라 우선도를 높이는 것이다. 또는 순차 순환 스케쥴링을 조합하는 방법도 있다.

5.3.5. Multilevel Queue Scheduling

서로 다른 우선도를 가진 큐들을 서로 다른 큐에 분리해 저장하는 다층 큐는 우선도 기반 스케쥴링과 순차 순환 스케쥴링이 결합되었을 때 유용하다. 또한 이는 프로세스 유형에 따라 별도의 큐에 저장할 수도 있다. 전경 프로세스는 순차 순환으로, 배경 프로세스는 선도착 선처리로 스케쥴링될 수 있다. 이 때 큐들간의 스케쥴링도 존재해야 한다. 예를 들자면, 리얼타임 프로세스 – 시스템 프로세스 – 인터랙티브 프로세스 – 배치 프로세스의 우선도 순서를 갖는다. 큐들 간 타임 슬라이스를 할 수도 있다.

5.3.6. Multilevel Feedback Queue Scheduling

다층 피드백 큐에서는 프로세스의 큐들간 이동을 허용하여 유연성을 준다. 이는 다음의 인자들에 의해 정의된다.

  • 큐의 숫자
  • 각 큐의 스케쥴링 알고리즘
  • 프로세스를 우선도 높은 큐로 이동시킬지의 방법
  • 프로세스를 우선도 낮은 큐로 이동시킬지의 방법
  • 프로세스가 어떤 우선도의 큐로 들어갈지의 방법

5.4. Thread Scheduling

이 장에서는 사용자 레벨 스레드와 커널 레벨 스레드의 스케쥴링을 다룬다.

5.4.1. Contention Scope

프로세스 경합 범위(PCS) 에서는 사용자 레벨 스레드가 경량 프로세스에 스케쥴링된다. 시스템 경합 범위(SCS)에서는 경량 프로세스가 코어에 스케쥴링된다. 프로세스 경합 범위에서는 대개 현재 동작 중인 스레드가 더 높은 우선도의 스레드에 의해 선점된다. 하지만, 같은 우선도의 스레드간에는 타임 슬라이싱의 보장이 없다.

5.4.2. Pthread Scheduling

POSIX Pthread에서는 다음의 API를 제공한다:

  • PTHREAD_SCOPE_PROCESS, 프로세스 경합 범위
  • PTHREAD_SCOPE_SYSTEM, 시스템 경합 범위
  • pthread_attr_setscope, 경합 범위를 설정
  • pthread_attr_getscope, 설정된 경합 범위를 가져옴

5.5. Multi-Processor Scheduling

여러 CPU가 가용 가능하면 부하 공유 이슈가 생긴다. 멀티프로세서는 다음의 하나를 가리킨다.

  • 멀티코어 CPU
  • 멀티스레드 코어
  • 비균일 메모리 접근 시스템
  • 불균질 멀티프로세싱

5.5.1. Approaches to Multiple-Processor Scheduling

비대칭 멀티프로세싱에서는 하나의 코어, 마스터 서버가 스케쥴링 결정을 전담한다. 구현하기 간단하지만, 마스터 서버가 병목이 된다. 그래서 표준적인 접근법은 각 코어가 자신을 스케쥴링하는 대칭 멀티프로세싱이다. 이 때 모든 스레드가 공용 대기 큐를 쓸 수도 있고 각자의 대기 큐를 쓸 수도 있다. 후자가 더 일반적이다. 거의 모든 현대적 운영 체제는 대칭 멀티프로세싱을 제공한다.

5.5.2. Multicore Processors

대부분의 현대적 하드웨어는 단일 칩에 여러 컴퓨팅 코어를 두는 멀티코어 프로세서이다. 프로세서가 메모리에 접근할 때 데이터가 사용가능해지기까지 대기하는 메모리 대기를 겪기 때문에, 많은 최근의 하드웨어는 각 코어에 복수의 하드웨어 스레드를 두는 칩 멀티스레딩 방식을 택한다. 인텔 프로세서에서는 이를 하이퍼스레딩(동시 멀티스레딩)이라 한다.

프로세싱 코어에서의 멀티스레드는 두 가지 방법이 있다. 조립질 멀티스레딩과 세립질 멀티스레딩이다. 조립질 멀티스레딩에서는 스레드가 메모리 대기 같은 지연 시간이 긴 이벤트가 발생할 때까지 코어에서 작동한다. 스레드 스위치가 일어날 때 명령어 파이프라인이 비워져야 하기 때문에 스레드 스위치의 비용이 크다. 반대로 세립질 멀티스레딩에서는 스레드간 스위칭이 명령어 사이클의 경계에서 일어난다. 이는 스레드 스위칭이 잦지만 스레드 스위칭의 비용이 싸다.

물리적 코어의 자원은 하드웨어 스레드간 공유되어야 하므로, 프로세싱 코어는 한 번에 하나의 하드웨어 스레드밖에 실행할 수 없다. 그래서 멀티스레드 멀티코어 프로세서는 두 개의 다른 층위의 스케쥴링을 필요로 한다. 첫 번째 층위에서는 어떤 소프트웨어 스레드가 어떤 하드웨어 스레드에서 작동할지를 결정하는 것이고 두 번째 층위에서는 어떤 코어가 어떤 하드웨어 스레드를 작동시킬지를 결정하는 것이다. 이 두 개의 층위는 상호 배타적이지 않으며 대개 같이 구현된다.

5.5.3. Load Balancing

부하 분산은 스레드간의 부하를 균형을 맞춰 CPU의 활용도를 높인다. 두 가지 유형이 있는데, 하나는 푸시 이동으로 특정 작업이 각 프로세서의 부하를 체크해 불균형이 발생할 경우 스레드를 이동시켜 부하를 맞춘다. 하는 풀 이동으로 유휴 프로세서가 대기 중인 작업을 바쁜 프로세서로부터 가져와 부하를 맞춘다. 푸시 이동과 풀 이동 또한 상호 배타적이지 않으며 대개 같이 구현된다. 부하 균형은 여러 의미를 내포할 수 있다.

5.5.4. Processor Affinity

스레드가 다른 프로세서로 이동하면 캐시를 무효화시킨 뒤 재설정해야 하므로, 스레드를 이동시킬 때는 같은 프로세서 내 이동시키는 것이 좋다. 이를 프로세서 친화라 한다. 스레드 이동 시의 같은 프로세서 내의 이동을 선호하는 약한 친화와 스레드가 동작할 수 있는 프로세서의 범위를 강제하는 강한 친화가 있다. 많은 운영체제는 이 둘을 모두 제공한다. 시스템의 메인 메모리 아키텍쳐 또한 프로세서 친화 문제에 영향을 줄 수 있다. 부하 분산은 프로세서간 스레드를 이동시키므로 프로세서 친화를 깬다. 그래서 이 둘간에는 트레이드오프가 존재하며, 이 균형을 맞추고자 하는 일이 스케쥴링 작업을 더 복잡하게 만든다.

5.5.5. Heterogenous Multiprocessing

여러 코어간 클락 속도와 전력 소모 등이 다른 불균질 멀티프로세싱이 존재한다. 이는 비대칭 멀티프로세싱이랑은 다른 것이다. ARM 프로세서에서는 전력 소모가 큰 코어와 전력 효율이 좋은 코어를 붙이는 big.LITTLE 접근법을 사용한다.

5.6. Real-Time CPU Scheduling

리얼 타임 시스템에는 두 종류가 있는데, 리얼 타임 프로세스의 실행 기한에 엄격한 제한을 두지 않는 소프트 리얼 타임 시스템과 프로세스의 실행 기한에 엄격한 제한을 두는 하드 리얼 타임 시스템이 있다.

5.6.1. Minimizing Latency

리얼 타임에 있어 지연 시간을 줄이는 것은 필수적이다. 이벤트 지연 시간은 이벤트가 발생한 후 서비스되기까지의 시간을 말한다. 다른 이벤트는 다른 지연 시간 조건을 갖는다. 리얼 타임 시스템에 영향을 주는 지연 시간의 유형은 2가지인데, 인터럽트가 발생한 뒤 CPU에 의해 처리되기까지의 인터럽트 지연 시간과 프로세스가 중단된 뒤 다른 프로세스가 실행되기까지의 디스패치 지연 시간이다. 디스패치 지연 시간에는 충돌 기간이 존재하는데 이는 커널에서 실행 중인 프로세스를 선점하고 프로세스가 더 높은 우선도의 프로세스를 위해 자원을 해제해주는 과정이다.

5.6.2. Priority-Based Scheduling

리얼 타임 운영 체제의 중요한 특성은 리얼 타임 프로세스가 CPU를 필요로 한다면 최대한 빨리 그 프로세스에 응답하는 것이다. 그래서 스케쥴러는 선점성 우선도 기반 알고리즘을 제공해야 한다. 이는 소프트 리얼 타임 시스템의 조건만을 충족시키기 때문에, 하드 리얼타임 시스템에서는 추가적인 스케쥴링 특성을 필요로 한다.

주기적인 프로세스에서는 CPU 프로세싱 시간과 처리 기한이 고정되어 있고 이것이 주기적으로 나타난다. 이 프로세스의 비율은 주기의 역수로 정해진다. 프로세스는 진입 제어 알고리즘을 통해 처리 기한을 스케쥴러에 통지한다. 이 통지를 받은 스케쥴러는 프로세스를 수용하거나 기각한다.

5.6.3. Rate-Monotonic Scheduling

비율 단조 스케쥴링에서는 주기적 작업을 고정된 우선도 정책에 따라 선점적으로 스케쥴링한다. 이 때 우선도는 주기에 반비례해 정함으로써 CPU를 자주 필요로 하는 작업에 높은 우선도를 준다. 이는 정적 우선도 정책 알고리즘 중에서는 최적이지만, CPU 활용도에 한계가 존재한다는 단점이 있다. N 프로세스를 스케쥴링할 때의 최악의 경우 CPU 활용도는 N(2^{\frac{1}{N}} - 1)이다.

5.6.4. Earliest-Deadline-First Scheduling

최단 만기 우선(EDF) 스케쥴링은 만기를 가장 먼저 앞둔 프로세스에 가장 높은 우선도를 주는 동적 스케쥴링이다. 이는 프로세스가 주기적임을 요구하지 않는다. 필요한 조건은 프로세스가 스케쥴러에 만기 시점을 통지해야 한다는 것뿐이다. 이는 이론적으로는 최적이지만 프로세스와 인터럽트 핸들링 간 컨텍스트 스위치 때문에 실제로 CPU 활용도를 100% 얻기는 불가능하다.

5.6.5. Proportional Share Scheduling

비례 공유 스케쥴러는 모든 애플리케이션간 T개의 프로세스 공유를 할당한다. 이는 반드시 진입 제어 알고리즘과 같이 활용되어 애플리케이션이 할당된 공유를 받음을 보장해야 한다.

5.6.6. POSIX Real-Time Scheduling

POSIX 표준은 리얼 타임 컴퓨팅을 위한 확장을 제공한다. 이는 두 가지의 스케쥴링 클래스를 제공한다.

  • SCHED_FIFO, 선도착 선처리 스케쥴. 같은 우선도 프로세스간 타임 슬라이싱이 존재하지 않는다.
  • SCHED_RR, 순차 순환 스케쥴.
  • SCHED_OTHER, 표준상의 구현이 정의되어 있지 않다.

그리고 두 가지의 API를 제공한다.

  • pthread_attr_getschedpolicy, 스케쥴링 방법을 얻어옴
  • pthread_attr_setschedpolicy, 스케쥴링 방법을 세팅함

5.7. Operating-System Examples

여러 운영 체제에서의 예제를 알아보자.

5.7.1. Example: Linux Scheduling

리눅스 스케쥴링 알고리즘에서는 2.6.23부터 완전 공정 스케쥴러(CFS)가 기본이 되었다. 이는 스케쥴링 클래스를 기반으로 한다. 각 클래스는 특정한 우선도를 배정받는다. 표준 리눅스 커널은 CFS 스케쥴링을 사용하는 기본 스케쥴링 클래스와 리얼 타임 스케쥴링 클래스의 2가지를 구현한다. CFS 스케쥴링은 각 작업에 -20부터 +19까지의 좋은 값들을 할당한다. CFS는 이산적인 타임 슬라이스 값을 쓰는 대신 목표 지연 시간을 특정한다. 이 값으로부터 CPU 시간의 비율이 할당된다. CFS 스케쥴러는 우선도를 직접적으로 설정하지 않는다. 그 대신 프로세스의 동작 시간을 가상 런타임으로 기록한다. 이는 실제 런타임과 우선도에 따라 결정된다.

리눅스는 POSIX 표준에 따라 리얼 타임 스케쥴링을 구현한다. CFS 스케쥴러는 부하 분산도 제공하는데, 이 때 프로세서 친화를 위해 스케쥴링 영역의 계층 시스템을 제공한다. 스케쥴링 영역은 상호간 균형을 맞출 수 있는 CPU 코어의 집합이다. 이 영역간에는 L3 캐시(비균일 메모리 접근 노드)를 공유할 수 있다. CFS는 심각한 부하 불균형이 생기지 않는 한 별개의 NUMA 노드간에는 스레드 이동을 하지 않는다.

5.7.2. Example: Windows Scheduling

스케쥴링을 전담하는 윈도우 커널의 부분은 디스패쳐라 한다. 이는 32단계의 우선도를 통해 스레드 실행 순서를 정한다. 1-15까지의 가변 클래스와 16-31까지의 리얼 타임 클래스이다. 실행시킬 스레드가 없을 경우 디스패쳐는 유휴 스레드를 실행한다. 우선도 클래스는 6가지이다.

  • IDLE_PRIORITY_CLASS
  • BELOW_NORMAL_PRIORITY_CLASS
  • NORMAL_PRIORITY_CLASS
  • ABOVE_NORMAL_PRIORITY_CLASS
  • HIGH_PRIORITY_CLASS
  • REALTIME_PRIORITY_CLASS

같은 우선도 클래스 내에서도 IDLE, LOWEST, BELOW_NORMAL, NORMAL, ABOVE_NORMAL, HIGHEST, TIME_CRITICAL로 상대 우선도가 나뉜다. 스레드 시간 퀀텀이 끝나면 그 스레드는 인터럽트된다. 가변 우선도 클래스에 속한 경우 우선도가 낮춰진다. 스레드가 대기 동작으로부터 해제될 경우 우선도가 높아진다. NORMAL_PRIORITY_CLASS 내에서 윈도우는 전경 프로세스(현재 선택된 프로세스)와 그 외의 배경 프로세스를 구분한다. 윈도우 7에서는 사용자 모드 스케쥴링(UMS)으로 애플리케이션이 스레드의 생성과 관리를 커널과 독립적으로 할 수 있게 한다. 초기 버전의 윈도우는 파이버라는 특성으로 이런 특성을 제공하였다. 사용자 모드 스케쥴링은 프로그래머가 직접 쓸 수는 없다. 그 대신에 C++ 프레임워크인 동시성 런타임(ConcRT)을 제공한다.

윈도우는 멀티프로세서의 스케쥴링을 대칭 멀티스레딩 셋이라는 논리적 프로세서의 집합을 구성함으로써 수행한다. 같은 CPU 코어에서의 하드웨어 스레드는 같은 SMT 셋에 속하게 된다. 부하 분산을 위해, 각 스레드는 이상적 프로세서를 할당받으며, 이는 부하 상황에 따라 변화한다.

5.7.3. Example: Solaris Scheduling

솔라리스는 우선도 기반 스레드 스케쥴링을 한다. 각 스레드는 6개 중 하나의 클래스에 속한다.

  • 시간 공유(TS)
  • 인터랙티브(IA)
  • 리얼타임(RT)
  • 시스템(SYS)
  • 공정 공유(FSS)
  • 고정 우선도(FP)

각 클래스는 서로 다른 우선도를 갖고 서로 다른 스케쥴링 알고리즘을 갖는다. 기본 스케쥴링 클래스는 시간 공유이다. 인터랙티브 프로세스는 대개 높은 우선도를, CPU 바운드 프로세스는 낮은 우선도를 갖는다. 스케쥴링에 쓰는 디스패치 테이블의 구성 요소는 다음과 같다.

  • 우선도.
  • 시간 퀀텀.
  • 지난 시간 퀀텀.
  • 수면으로부터의 복귀.

리얼 타임 클래스의 스레드는 높은 우선도를 갖는다. 공정 공유 클래스는 우선도 대신 CPU 공유라는 값을 통해 스케쥴링을 한다. 이는 가용가능한 CPU 자원으로서 프로세스의 집합, 프로젝트에 할당된다.

5.8. Algorihm Evaluation

특정 시스템의 CPU 스케쥴링 알고리즘을 어떻게 선택할 것인가? 첫째로는 알고리즘 선택 기준을 정해야 한다. 이는 CPU 활용, 반응 이산, 처리량일 수도 있다.

5.8.1. Deterministic Modeling

하나의 평가 방법은 분석적 평가이다. 이는 특정 작업 부하에 대한 알고리즘에 대해 공식으로 그 성능을 평가한다. 그 중 하나로 결정론적 모델링이 있다. 이는 특정 작업 부하를 정해 그 작업 부하에 대한 알고리즘의 성능을 평가한다. 하지만 이로 구한 해는 그 경우에만 들어맞는다는 단점이 있다.

5.8.2. Queueing Models

실행 환경은 매일 바뀌기 때문에 좋은 결정론적 모델링은 실제로는 어렵다. 그래서 현재 CPU 내의 대기 큐 내의 데이터를 활용하는 큐 네트워크 분석을 활용한다. 이 중 하나는 리틀 공식n = \lambda W로 n은 평균적인 장기간 큐 길이, W는 큐의 평균 대기 시간, \lambda는 큐에서의 새 프로세스의 도착율이다. 이는 모든 스케쥴링 알고리즘과 도착 분포에 대해 성립하기 때문에 유용하다.

큐 네트워크 분석은 다룰 수 있는 알고리즘과 분포의 범위가 제한되어 있다는 단점이 있어서 근사 이상으로 쓰이기는 힘들다.

5.8.3. Simulations

위의 문제를 보정하기 위해 난수에 의해 가상의 프로세스 열을 생성하는 시뮬레이션 기법을 사용하기도 한다. 이 가상의 작업 부하가 실제에 보다 들어맞게 하기 위해, 실제 시스템을 모니터링하는 추적 파일을 이용해 이를 보정한다. 시뮬레이션은 비용이 크고, 설계/코딩/디버깅이 어렵다.

5.8.4. Implementation

스케쥴링 알고리즘의 유일한 제대로 된 평가 방법은 코딩 후 운영 체제에 구현하고 그 동작을 실제로 보는 것이다. 이 알고리즘이 성능을 더 나쁘게 하지 않았음을 증명하는 회귀 테스팅이 쓰인다. 이에는 또다른 난점이 있는데 알고리즘이 실행 환경을 어떻게 바꿀지 알 수 없다는 것이다. 그래서 일반적으로는 스케쥴링 알고리즘은 유연하게 구현한다. 또한, 스레드나 프로세스의 우선도를 동적으로 수정할 수 있는 API를 두기도 한다.

5.9. Summary

  • CPU 스케쥴링은 대기 큐에서 대기 프로세스를 선택해 CPU를 할당하는 것이다. 선택된 프로세스는 디스패쳐에 의해 CPU가 할당된다.
  • 스케쥴링 알고리즘은 선점적(프로세스로부터 CPU가 뺏겨지는) 또는 비선점적(프로세스가 직접 CPU를 포기해야 하는)일 수 있다. 거의 모든 현대 운영 체제는 선점적이다.
  • 스케쥴링 알고리즘은 다음 5가지 기준으로 평가된다. CPU 활용, 처리량, 턴어라운드 시간, 대기 시간, 반응 시간.
  • 선도착 선처리 스케쥴링은 가장 간단하지만, 짧은 프로세스들이 긴 프로세스를 오래 기다리게 된다.
  • 최단 작업 우선 스케쥴링은 평균 대기 시간을 최소화시키지만, 다음 CPU 버스트의 시간을 예측하기 힘들기 때문에 구현하기 힘들다.
  • 순차 순환 스케쥴링은 각 프로세스에 CPU를 시간 퀀텀만큼 할당한다. 프로세스는 시간 퀀텀이 지난 이후에 CPU를 다른 프로세스에 의해 선점당한다.
  • 우선도 스케쥴링은 각 프로세스에 우선도를 할당하고, CPU를 최고 우선도 프로세스에 할당한다. 같은 우선도간 프로세스는 선도착 선처리 또는 순차 순환으로 스케쥴링된다.
  • 다층 큐 스케쥴링은 프로세스를 우선도에 따른 여러 분리된 큐로 분할하고 스케쥴러는 가장 높은 우선도의 큐로부터 프로세스를 실행한다. 큐마다 스케쥴링 알고리즘은 다를 수 있다.
  • 다층 피드백 큐는 다층 큐와 비슷하지만 프로세스가 서로 다른 큐간 이동하는 것을 허용한다.
  • 멀티코어 프로세서는 같은 물리적 칩에 하나 이상의 CPU를 두며, 각 CPU는 복수의 하드웨어 스레드를 갖는다. 운영 체제의 관점에서 각 하드웨어 스레드는 논리적 CPU가 된다.
  • 멀티코어 시스템에서의 부하 분산은 CPU 코어간 부하를 균형을 맞추지만, 캐시를 무효화시켜 메모리 접근 시간을 늘릴 수 있다.
  • 소프트 리얼타임 스케쥴링은 리얼타임 작업에 우선도를 높이 준다. 하드 리얼타임 스케쥴링은 리얼타임 작업에 만기 조건을 보장한다.
  • 비율 단조 리얼타임 스케쥴링은 주기적 작업을 선점적으로 정적 우선도 방식에 따라 스케쥴링한다.
  • 최단 만기 우선 스케쥴링은 만기가 빠를수록 높은 우선도를 둔다.
  • 비율 공유 스케쥴링은 모든 애플리케이션간 T 단위의 공유를 둔다. 애플리케이션이 N개의 시간 공유를 할당받으면 N/T만큼의 전체 프로세서 시간을 갖는다.
  • 리눅스는 완전 공정 스케쥴러(CFS)를 쓴다. 이는 각 작업에 CPU 프로세싱 시간의 비율을 할당하는데, 이는 각 작업에 배정된 가상 런타임(vruntime)에 기반한다.
  • 윈도우 스케쥴링은 선점적이며, 32단계 우선도를 통해 스레드 스케쥴링의 순서를 판별한다.
  • 솔라리스는 6개의 고유한 스케쥴링 클래스를 두어 전역 우선도에 매핑되도록 한다. CPU 바운드 스레드는 낮은 우선도(높은 시간 퀀텀)을, I/O 바운드 스레드는 높은 우선도(낮은 시간 퀀텀)을 갖는다.
  • CPU 스케쥴링 알고리즘을 평가할 때 모델링과 시뮬레이션이 쓰인다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중