본문 바로가기
리눅스

(번역) Scheduling (computing)

by 다움위키 2024. 12. 26.

원문 보기: https://dawoum.duckdns.org/wiki/Scheduling_(computing)

 

Original article: w:Scheduling (computing)
This article is about scheduling of computing resources. For networks, see Network scheduler. For other uses, see Scheduling (disambiguation).

컴퓨팅에서, 스케줄링(scheduling)은 작업를 수행하기 위해 자원을 할당하는 동작입니다. 자원은 프로세서, 네트워크 링크, 또는 확장 카드일 수 있습니다. 작업는 쓰레드, 프로세스, 또는 데이터 흐름일 수 있습니다.

스케줄링 활동은 스케줄러라는 메커니즘에 의해 수행됩니다. 스케줄러는 종종 모든 컴퓨터 자원을 바쁘게 유지 (로드 밸런싱에서 처럼)하거나, 여러 사용자가 시스템 자원을 효과적으로 공유하거나, 목표 서비스-품질을 달성하도록 설계됩니다.

스케줄링은 계산 그 자체에 토대적이고, 컴퓨터 시스템의 실행 모델의 본질적 부분입니다; 스케줄링이라는 개념을 통해 단일 중앙 처리 장치 (CPU)를 갖는 컴퓨터 멀티태스킹을 가지는 것이 가능해집니다.

Goals

스케줄러는 다음과 같은 하나 이상의 목표를 목표로 할 수 있습니다:

  • 처리량 (시간 단위당 완료된 총 작업량) 극대화;
  • 대기 시간 (작업이 준비되는 순간부터 실행을 시작하는 첫 지점까지의 시간)을 최소화;
  • 지연 시간 또는 응답 시간 (일괄 작업의 경우에서 작업이 준비되는 시간부터 완료되는 시간, 대화형 작업의 경우에서 시스템이 응답하고 첫 번째 출력을 사용자에게 전달하는 시간)을 최소화;
  • 공정성 (각 프로세스에 같은 CPU 시간을 제공하거나, 더 일반적으로는 각 프로세스의 우선 순위와 작업 부하에 따라 적절한 시간을 제공) 최대화;

실제로, 이들 목표는 종종 충돌하고 (예를 들어, 처리량 대 지연 시간), 따라서 스케줄러는 적절한 타협안을 구현할 것입니다. 선호도는 사용자의 필요와 목표에 따라 위에서 언급한 관심 사항 중 하나로 측정됩니다.

산업 (예를 들어, 로봇공학)에서 자동 제어를 위한 임베디드 시스템과 같은 실시간 환경에서, 스케줄러는 프로세스가 마감일을 충족할 수 있도록 보장해야 합니다; 이것은 시스템을 안정적으로 유지하는 데 치명적니다. 예약된 작업는 네트워크를 통해 원격 장치에 분산되고 관리 백엔드를 통해 관리될 수도 있습니다.

Types of operating system schedulers

스케줄러는 시스템에 들어갈 다음 작업와 실행할 다음 프로세스를 선택하는 운영 시스템 모듈입니다. 운영 시스템에는 최대 3가지의 고유한 스케줄러 유형이 있습니다: 장기 스케줄러 (입장 스케줄러 또는 상위 레벨 스케줄러라고도 함), 중기 또는 중간기 스케줄러, 및 단기 스케줄러입니다. 그 이름은 해당 기능이 수행되는 상대적 빈도를 나타냅니다.

Process scheduler

프로세스 스케줄러는 특정 시점에 어떤 프로세스가 실행될지 결정하는 운영 시스템의 일부입니다. 그것은 보통 실행 중인 프로세스를 일시 중지하고 실행 큐의 맨 뒤로 이동하고 새 프로세스를 시작할 수 있는 기능이 있습니다; 그러한 스케줄러는 선점형 스케줄러(preemptive scheduler)로 알려져 있으며, 그렇지 않으면 협력형 스케줄러(cooperative scheduler)입니다.

우리는 결정을 얼마나 자주 내려야 하는지에 따라 장기 스케줄링, 중기 스케줄링, 및 단기 스케줄링을 구분합니다.

Long-term scheduling

장기 스케줄러, 또는 입장 스케줄러는 어떤 작업 또는 프로세스가 준비 대기열 (메인 메모리)에 입장될지 결정합니다; 즉, 프로그램을 실행하려고 할 때, 현재 실행 중인 프로세스 집합에 입장하는 것은 장기 스케줄러에 의해 승인되거나 지연됩니다. 따라서, 이 스케줄러는 시스템에서 어떤 프로세스를 실행할지, 한 번에 지원할 동시성 정도 (많은 프로세스가 동시에 실행될지 적은 프로세스가 실행될지 여부), 및 I/O 집약적 프로세스와 CPU 집약적 프로세스를 어떻게 분할할지를 지시합니다. 장기 스케줄러는 멀티프로그래밍 정도를 제어하는 ​​역할을 합니다.

일반적으로, 대부분의 프로세스는 I/O-바운드 또는 CPU-바운드로 설명될 수 있습니다. I/O-바운드 프로세스는 계산을 하는 것보다 I/O를 하는 데 더 많은 시간을 사용하는 프로세스입니다. 반면에, CPU-바운드 프로세스는 I/O 요청을 드물게 생성하여, 계산을 하는 데 더 많은 시간을 사용합니다. 장기 스케줄러가 I/O-바운드 및 CPU-바운드 프로세스의 적절한 프로세스 혼합을 선택하는 것이 중요합니다. 만약 모든 프로세스가 I/O-바운드이면 준비 대기열은 거의 항상 비어 있고 단기 스케줄러는 할 일이 거의 없습니다. 다른 한편, 만약 모든 프로세스가 CPU-바운드이면, I/O 대기 대기열은 거의 항상 비어 있고, 장치가 사용되지 않고, 다시 시스템이 불균형해집니다. 따라서 성능이 가장 좋은 시스템은 CPU-바운드 및 I/O-바운드 프로세스의 조합을 갖게 됩니다. 최신 운영 시스템에서, 이는 실시간 프로세스가 작업을 완료하는 데 충분한 CPU 시간을 확보하도록 하는 데 사용됩니다.

장기 스케줄링은 일괄 처리 시스템, 컴퓨터 클러스터, 슈퍼컴퓨터, 및 렌더 팜과 같은 대규모 시스템에서도 중요합니다. 예를 들어, 동시 시스템에서, 상호 작용하는 프로세스의 공동-스케줄링이 종종 필요하여 서로를 기다리면서 차단되는 것을 방지합니다. 이들 경우에서, 특수-목적 작업 스케줄러 소프트웨어가 전형적으로 이들 기능을 지원하는 데 사용되며, 운영 시스템의 기본 입장 스케줄링 지원 외에도 사용됩니다.

일부 운영 시스템은 모든 실시간 마감일을 여전히 충족할 수 있다고 확신하는 경우에만 새 작업을 추가할 수 있도록 허용합니다. 운영 시스템이 새 작업을 수락하거나 거부하는 데 사용하는 특정 휴리스틱 알고리즘은 입장 제어 메커니즘(admission control mechanism)입니다.

Medium-term scheduling

중기 스케줄러는 일시적으로 주요 메모리에서 프로세스를 제거하고 보조 메모리 (예를 들어, 하드 디스크 드라이브)에 넣거나 그 반대로 하며, 이를 공통적으로 스와핑 아웃 또는 스와핑 인 (역시 부정확하게 페이징 아웃 또는 페이징 인이라고 함)이라고 합니다. 중기 스케줄러는 한동안 활성화되지 않은 프로세스, 낮은 우선순위를 가지는 프로세스, 자주 페이지 폴트가 발생하는 프로세스, 또는 다른 프로세스를 위해 주요 메모리를 비우기 위해 많은 양의 메모리를 차지하는 프로세스를 스왑 아웃하여, 나중에 더 많은 메모리가 사용 가능해지거나 프로세스가 차단 해제되어 더 이상 자원을 기다리지 않을 때 프로세스를 다시 스와핑하기로 결정할 수 있습니다.

오늘날 많은 시스템 (스왑 파일이 아닌 보조 저장소에 가상 주소 공간을 매핑하는 것을 지원하는 시스템)에서, 중기 스케줄러는 바이너리를 실행 시 스왑-아웃된 프로세스로 처리함으로써, 장기 스케줄러의 역할을 실제로 수행할 수 있습니다. 이런 식으로, 바이너리의 세그먼트가 필요할 때 필요에 따라 스왑 인하거나 지연 로드할 수 있으며, 이를 요구 페이징(demand paging)이라고도 합니다.

Short-term scheduling

단기 스케줄러 (CPU 스케줄러라고도 함)는 클록 인터럽트, I/O 인터럽트, 운영 시스템 호출, 또는 다른 형태의 신호 후에 어떤 준비된 메모리-내 프로세스를 실행할지 (CPU에 할당할지) 결정합니다. 따라서 단기 스케줄러는 장기 또는 중기 스케줄러보다 훨씬 더 자주 스케줄링 결정을 내립니다 – 스케줄링 결정은 최소한 모든 각 시간 슬라이스 후에 내려야 하고, 이는 매우 짧습니다. 이 스케줄러는 선점형일 수 있는데, 즉 CPU를 또 다른 프로세스에 할당하기로 결정할 때 CPU에서 프로세스를 강제로 제거할 수 있거나, 비-선점형 (자발적 또는 협동적이라고도 함)일 수 있는데, 이 경우 스케줄러가 CPU에서 프로세스를 강제로 제거할 수 없습니다.

선점형 스케줄러는 커널 모드에서 실행되는 인터럽트 핸들러를 호출하고 스케줄링 기능을 구현하는 프로그래밍 가능한 구간 타이머를 사용합니다.

Dispatcher

CPU 스케줄링 기능에 관여하는 또 다른 구성 요소는 디스패처로, 단기 스케줄러가 선택한 프로세스에 CPU 제어권을 제공하는 모듈입니다. 그것은 인터럽트나 시스템 호출의 결과로 커널 모드에서 제어권을 받습니다. 디스패처의 기능에는 다음이 포함됩니다:

  • 컨텍스트 전환, 이것에서 디스패처는 이전에 실행 중이던 프로세스나 쓰레드의 상태 (컨텍스트라고도 함)를 저장합니다; 그런-다음 디스패처는 새 프로세스의 초기 상태나 이전에 저장된 상태를 로드합니다.
  • 사용자 모드로 전환.
  • 사용자 프로그램의 적절한 위치로 이동하여 새 상태가 나타내는 프로그램을 다시 시작.

디스패처는 모든 각 프로세스 전환 중에 호출되므로 가능한 한 빨라야 합니다. 컨텍스트 전환 중에, 프로세서는 일부 시간 동안 사실상 유휴 상태가 되고, 따라서 불필요한 컨텍스트 전환은 피해야 합니다. 디스패처가 한 프로세스를 중지하고 또 다른 프로세스를 시작하는 데 걸리는 시간을 디스패치 지연(dispatch latency)이라고 합니다.

Scheduling disciplines

스케줄링 규율 (스케줄링 정책 또는 스케줄링 알고리듬이라고도 함)은 동시에 그리고 비동기적으로 자원을 요청하는 당사자 사이에 자원을 분배하는 데 사용되는 알고리즘입니다. 스케줄링 규율은 라우터 (패킷 트래픽 처리)와 운영 시스템 (쓰레드와 프로세스 사이에 CPU 시간을 공유), 디스크 드라이브 (I/O 스케줄링), 프린터 (인쇄 스풀러), 대부분의 임베디드 시스템, 등에서 사용됩니다.

스케줄링 알고리즘의 주요 목적은 자원 기아를 최소화하고 자원을 활용하는 당사자 간의 공평성을 보장하는 것입니다. 스케줄링은 미처리 요청 중 어느 것을 자원에 할당할지 결정하는 문제를 다룹니다. 다양한 스케줄링 알고리즘이 있습니다. 이 섹션에서는 그 중 몇 가지를 소개합니다.

스케줄링 알고리즘의 주요 목적은 자원 기아를 최소화하고 자원을 활용하는 당사자 사이의 공평성을 보장하는 것입니다. 스케줄링은 미처리 요청 중 어느 것을 자원에 할당할지 결정하는 문제를 다룹니다. 다양한 스케줄링 알고리즘이 있습니다. 이 섹션에서는 그 중 몇 가지를 소개합니다.

패킷-교환 컴퓨터 네트워크와 기타 통계적 멀티플렉싱에서, 스케줄링 알고리즘의 개념은 데이터 패킷 선입선출 대기열의 대안으로 사용됩니다.

가장 간단한 최선의-노력 스케줄링 알고리즘은 라운드-로빈, 공정한 대기열 (최대-최소 공정한 스케줄링 알고리즘), 비례-공정한 스케줄링, 및 최대 처리량입니다. 최선의-노력 통신과 달리 차별화되거나 보장된 서비스 품질이 제공되면, 가중된 공정한 대기열을 활용할 수 있습니다.

HSDPA (High-Speed ​​Downlink Packet Access) 3.5G 셀룰러 시스템과 같은 고급 패킷 무선 네트워크에서, 채널-종속 스케줄링을 사용하여 채널 상태 정보를 활용할 수 있습니다. 만약 채널 조건이 유리한 경우면, 처리량과 시스템 스펙트럼 효율이 증가할 수 있습니다. LTE와 같은 훨씬 더 고급 시스템에서, 스케줄링은 채널-종속 패킷-별 동적 채널 할당에 의해 결합되거나, OFDMA 다중-캐리어 또는 기타 주파수-영역 등화 구성 요소를 가장 잘 활용할 수 있는 사용자에게 할당함으로써 결합됩니다.[9]

First come, first served

선입선출 (First in, first out, FIFO), first come, first served (FCFS)이라고도 알려진, 가장 간단한 스케줄링 알고리즘입니다. FIFO는 단순히 준비된 대기열에 도착한 순서대로 프로세스를 대기열에 넣습니다. 이것은 공통적으로 이 섹션에서 설명한 것처럼 작업 대기열(task queue)에 사용됩니다.

  • 컨텍스트 전환은 프로세스 종료 시에만 발생하고, 프로세스 대기열의 재구성은 필요가 없으므로, 스케줄링 오버헤드가 최소화됩니다.
  • 처리량이 낮을 수 있는데, 왜냐하면 긴 프로세스가 CPU를 점유하고 있어, 짧은 프로세스가 긴 시간 대기해야 하기 때문입니다 (컨베이 효과라고 알려져 있습니다).
  • 각 프로세스는 특정 시간 이후에 실행될 기회를 얻기 때문에 기아 현상이 발생하지 않습니다.
  • 소요 시간(Turnaround time), 대기 시간, 및 응답 시간은 도착 순서에 따라 달라지고 위에 언급한 것과 같은 이유로 길어질 수 있습니다.
  • 우선순위 지정이 이루어지지 않아, 이 시스템은 프로세스 마감을 맞추는 데 어려움을 겪습니다.
  • 우선순위가 없다는 것은 모든 프로세스가 결국 완료되는 한 기아가 없다는 것을 의미합니다. 일부 프로세스가 완료되지 않을 수 있는 환경에서, 기아가 발생할 수 있습니다.
  • 이는 대기열을 기반으로 합니다.

Priority scheduling

가장 빠른 마감 먼저 (EDF) 또는 가야할 가장 짧은 시간(least time to go)은 실시간 운영 시스템에서 프로세스를 우선순위 대기열에 배치하는 데 사용되는 동적 스케줄링 알고리즘입니다. 스케줄링 이벤트가 발생할 때마다 (작업이 완료되거나, 새 작업이 출시되는, 등), 대기열은 마감에 가장 가까운 프로세스를 검색하여 실행을 위해 그 다음으로 스케줄링됩니다.

Shortest remaining time first

가장 짧은 작업 우선 (SJF)과 유사합니다. 이 전략과 함꼐, 스케줄러는 추정 처리 시간이 가장 짧은 프로세스를 대기열의 다음 순서로 정렬합니다. 이를 위해서는 프로세스가 완료되는 데 필요한 시간에 대한 고급 지식이나 추정이 필요합니다.

  • 만약 또 다른 프로세스의 실행 중에 더 짧은 프로세스가 도착하면, 현재 실행 중인 프로세스가 중단되고 (선점이라고 함), 해당 프로세스가 두 개의 별도 컴퓨팅 블록으로 나뉩니다. 이것은 추가 컨텍스트 전환을 통해 과도한 오버헤드를 생성합니다. 스케줄러는 역시 들어오는 각 프로세스를 대기열의 특정 위치에 배치해야 하며, 따라서 추가 오버헤드가 생깁니다.
  • 이 알고리즘은 대부분의 시나리오에서 최대 처리량을 위해 설계되었습니다.
  • 대기 시간과 응답 시간은 프로세스의 계산 요구 사항이 증가함에 따라 증가합니다. 소요 시간은 대기 시간과 처리 시간을 더한 값이므로, 긴 프로세스는 이에 상당한 영향을 받습니다. 어쨌든 어떤 프로세스도 가장 긴 프로세스의 종료를 기다릴 필요가 없으므로, 전체 대기 시간은 FIFO보다 작습니다.
  • 마감에는 특별한 주의를 기울이지 않으며, 프로그래머는 마감이 있는 프로세스를 가능한 한 짧게 만들려고만 노력할 수 있습니다.
  • 특히 많은 작은 프로세스가 실행되는 바쁜 시스템에서는 기아 상태가 발생할 수 있습니다.
  • 이 정책을 사용하기 위해, 우선 순위가 다른 두 개 이상의 프로세스가 있어야 합니다.

Fixed-priority pre-emptive scheduling

운영 시스템은 모든 각 프로세스에 고정된 우선순위 순위를 할당하고, 스케줄러는 준비 대기열에 있는 프로세스를 우선순위 순서대로 정렬합니다. 우선순위가 낮은 프로세스는 들어오는 우선순위가 높은 프로세스에 의해 중단됩니다.

  • 오버헤드는 최소 수준도 아니고, 상당 수준도 아닙니다.
  • FPPS는 FIFO 스케줄링에 비해 처리량 측면에서 특별한 이점이 없습니다.
  • 만약 순위의 수가 제한되어 있다면, 우선순위 순위마다 하나씩 FIFO 대기열의 모음으로 특징지을 수 있습니다. 우선순위가 낮은 대기열의 프로세스는 우선순위가 높은 대기열이 모두 비어 있을 때만 선택됩니다.
  • 대기 시간과 응답 시간은 프로세스의 우선순위에 따라 달라집니다. 우선순위가 높은 프로세스는 대기 시간과 응답 시간이 더 짧습니다.
  • 마감이 있는 프로세스에 더 높은 우선순위를 부여하면 마감을 맞출 수 있습니다.
  • 다수의 높은 우선순위 프로세스가 CPU 시간을 차지하기 위해 대기하고 있으면, 낮은 우선순위의 프로세스가 부족해질 수 있습니다.

Round-robin scheduling

스케줄러는 프로세스당 고정된 시간 단위를 할당하고 그것들을 통해 순환합니다. 만약 프로세스가 해당 시간-슬라이스 내에 완료되면, 그것은 종료되고, 그렇지 않으면 다른 모든 프로세스에 기회를 준 후 다시 스케줄됩니다.

  • RR 스케줄링에는 많은 오버헤드가 수반되는데, 특히 시간 단위와 함께 더욱 그렇습니다.
  • FCFS/FIFO와 SJF/SRTF 사이에 처리량이 균형을 이루며, 짧은 작업은 FIFO보다 더 빨리 완료되고 긴 프로세스는 SJF보다 더 빨리 완료됩니다.
  • 평균 응답 시간이 좋으며, 대기 시간은 평균 프로세스 길이가 아닌 프로세스 수에 따라 달라집니다.
  • 대기 시간이 길기 때문에, 순수한 RR 시스템에서 마감-시간을 지키는 경우가 거의 없습니다.
  • 우선순위가 주어지지 않기 때문에 기아는 결코 발생할 수 없습니다. 시간 단위 할당 순서는 FIFO와 유사하게 프로세스 도착 시간을 기준으로 합니다.
  • 만약 시간-슬라이스가 크면, FCFS/FIFO가 되고, 짧으면 SJF/SRTF가 됩니다.

Multilevel queue scheduling

Main article: Multilevel queue

이것은 프로세스가 쉽게 여러 그룹으로 나뉘는 상황에서 사용됩니다. 예를 들어, 포그라운드 (대화형) 프로세스와 백그라운드 (배치) 프로세스 사이에 공통적인 구분이 이루어집니다. 이들 두 가지 유형의 프로세스는 응답-시간 요구 사항이 다르고 따라서 스케줄링 요구 사항이 다를 수 있습니다. 그것은 공유 메모리 문제에 매우 유용합니다.

Work-conserving schedulers

작업-보존 스케줄러는 스케줄링할 준비가 된 제출된 작업이 있으면 항상 스케줄링된 자원을 바쁘게 유지하려고 하는 스케줄러입니다. 반면, 비-작업 보존 스케줄러는 스케줄링할 준비가 된 작업이 있음에도 불구하고 어떤 경우에는 스케줄링된 자원을 유휴 상태로 둘 수 있는 스케줄러입니다.

Scheduling optimization problems

어떤 작업이 어떤 시간에 어떤 스테이션으로 가야 하는지 결정하여 전체 메이크스팬(makespan)을 최소화하는 것이 목표인 스케줄링 문제가 여러 가지 있습니다.

Manual scheduling

임베디드 시스템에서 매우 공통적인 방법은 작업을 수동으로 스케줄링하는 것입니다. 이것은 예를 들어 시간-다중화 방식으로 수행될 수 있습니다. 때때로 커널은 수동 스케줄링, 선점형 및 인터럽트 수준의 세 부분 이상으로 나뉩니다. 작업을 스케줄링하는 정확한 방법은 종종 독점적입니다.

  • 자원 기아 문제 없음
  • 매우 높은 예측 가능성; 하드 실-시간 시스템 구현 가능
  • 거의 오버헤드 없음
  • 모든 응용 프로그램에 최적이 아닐 수 있음
  • 효과는 구현에 전적으로 달려 있음

Choosing a scheduling algorithm

운영 시스템을 설계할 때, 프로그래머는 어떤 스케줄링 알고리즘이 시스템이 보려는 것의 용도에 가장 잘 맞는지 고려해야 합니다. 보편적으로 가장 좋은 스케줄링 알고리즘은 없고, 많은 운영 시스템은 위의 스케줄링 알고리즘을 확장하거나 조합하여 사용합니다.

예를 들어, Windows NT/XP/Vista는 고정-우선순위 선점 스케줄링, 라운- 로빈, 및 선입선출 알고리즘을 결합한 다중-수준 피드백 대기열을 사용합니다. 이 시스템에서, 쓰레드는 이미 서비스되었는지, 또는 광범위하게 대기했는지에 따라 우선순위를 동적으로 증가시키거나 감소시킬 수 있습니다. 모든 각 우선순위 수준은 자체 대기열로 표현되며, 높은-우선순위 쓰레드 사이에는 라운드-로빈 스케줄링이 적용되고 낮은-우선순위 쓰레드 사이에는 FIFO가 적용됩니다. 이런 의미에서, 대부분의 쓰레드에 대한 응답 시간이 짧고, 짧지만 중요한 시스템 쓰레드는 매우 빠르게 완료됩니다. 쓰레드는 가장 높은 우선순위 대기열에서 라운드-로빈의 시간 단위를 하나만 사용할 수 있으므로, 더 긴 높은-우선순위 쓰레드에 대한 기아 상태가 문제가 될 수 있습니다.

Operating system process scheduler implementations

사용된 알고리즘은 라운드-로빈처럼 간단할 수 있으며, 여기서 각 프로세스는 순환 목록에서 같은 시간 (예를 들어, 1ms, 보통 1ms~100ms)을 받습니다. 즉, 프로세스 A가 1ms 동안 실행되고, 그 다음 프로세스 B, 그 다음 프로세스 C가 실행되고, 다시 프로세스 A로 돌아갑니다.

더 진보된 알고리즘은 프로세스 우선순위, 또는 프로세스의 중요성을 고려합니다. 이를 통해 일부 프로세스는 다른 프로세스보다 더 많은 시간을 사용할 수 있습니다. 커널은 항상 시스템의 적절한 기능을 보장하기 위해 필요한 모든 자원을 사용하고, 따라서 무한한 우선순위를 가진다고 할 수 있습니다. SMP 시스템에서, 프로세서 친화성(processor affinity)은 프로세스 자체가 더 느리게 실행될 수 있더라도 전체 시스템 성능을 높이는 것으로 고려됩니다. 이는 일반적으로 캐시 쓰래싱(cache thrashing)을 ​​줄여 성능을 개선합니다.

OS/360 and successors

IBM OS/360은 세 가지 다른 스케줄러와 함께 제공되었습니다. 차이점은 변형이 종종 세 가지 다른 운영 시스템으로 고려될 정도였습니다:

  • 단일 순차 스케줄러(Single Sequential Scheduler) 옵션은, 역시 주요 제어 프로그램(Primary Control Program, PCP))으로도 알려져 있으며, 단일 작업 스트림의 순차적 실행을 제공했습니다.
  • 다중 순차 스케줄러(Multiple Sequential Scheduler) 옵션은, 고정된 수의 작업을 갖는 멀티프로그래밍 (Multiprogramming with a Fixed Number of Tasks, MFT)으로 알려져 있으며, 여러 동시 작업의 실행을 제공했습니다. 실행은 각 스트림에 대한 기본값이 있거나 각 작업에 대해 별도로 요청할 수 있는 우선순위에 의해 관리되었습니다. MFT 버전 II는 부모 작업의 우선순위를 기반으로 우선순위에서 실행되는 하위-작업 (쓰레드)을 추가했습니다. 각 작업 스트림은 해당 스트림에서 임의의 작업에 의해 사용될 수 있는 최대 메모리 양을 정의했습니다.
  • 다중 우선순위 스케줄러(Multiple Priority Schedulers) 옵션, 또는 가변 개수의 작업을 갖는 다중-프로그래밍 (Multiprogramming with a Variable Number of Tasks, MVT)은 시작부터 하위-작업을 특징으로 했습니다; 각 작업은 실행 전에 우선순위와 필요한 메모리를 요청했습니다.

MVS의 이후 가상 스토리지 버전에서는 스케줄러에 워크로드 관리자(Workload Manager) 기능이 추가되어 설치에 따라 정의된 정교한 계획에 따라 프로세서 자원을 스케줄링합니다.

Windows

매우 초기의 MS-DOS와 Microsoft Windows 시스템은 멀티태스킹이 아니었고, 이를테면 스케줄러가 없었습니다. Windows 3.1x는 비-선점형 스케줄러를 사용했으며, 그것은 프로그램을 중단하지 않았음을 의미합니다. 그것은 프로그램이 종료되거나 OS에 프로세서가 필요 없다고 알려서 또 다른 프로세스로 넘어갈 수 있다고 말하는 것에 의존했습니다. 이것은 보통 협력적 멀티태스킹이라고 말합니다. Windows 95는 기본적인 선점형 스케줄러를 도입했습니다; 어쨌든, 레거시 지원을 위해 16-비트 응용 프로그램이 선점 없이 실행되도록 선택했습니다.

Windows NT-기반 운영 시스템은 다중-수준 피드백 대기열을 사용합니다. 0에서 31까지 32개의 우선순위 수준이 정의되어 있으며, 우선순위 0에서 15는 정규(normal) 우선순위이고 우선순위 16에서 31은 소프트 실-시간 우선순위로, 할당하려면 권한이 필요합니다. 0은 운영 시스템에 대해 예약되어 있습니다. 사용자 인터페이스와 API는 프로세스와 프로세스에서 스레드에 대한 우선순위 클래스와 함께 작동하며, 이는 시스템에 의해 절대 우선순위 수준으로 결합됩니다.

커널은 쓰레드의 I/O 및 CPU 사용량과 대화형인지 (즉, 사람으로부터 입력을 수락하고 응답하는지)에 따라 쓰레드의 우선순위 수준을 변경하여, 대화형 및 I/O 제한 프로세스의 우선순위를 높이고 CPU 제한 프로세스의 우선 순위를 낮춰, 대화형 응용 프로그램의 응답성을 높일 수 있습니다. 스케줄러는 Windows Vista에서 수정되어 구간-타이머 인터럽트 루틴을 사용하는 대신 최신 프로세서의 사이클 카운터 레지스터(cycle counter register)를 사용하여 쓰레드가 실행한 정확한 CPU 사이클 수를 추적합니다. Vista는 역시 디스크 조각 모으기 프로그램과 이와 유사한 다른 프로그램이 포그라운드 작업을 방해하지 않도록 I/O 대기열에 대한 우선순위 스케줄러를 사용합니다.

Classic Mac OS and macOS

Mac OS 9는 쓰레드에 대해 협력 스케줄링을 사용하며, 여기서 하나의 프로세스는 여러 협력 쓰레드를 제어하고, 멀티프로세싱 작업에 대한 선점 스케줄링도 제공합니다. 커널은 선점 스케줄링 알고리즘을 사용하여 멀티프로세싱 작업을 스케줄링합니다. 모든 프로세스 관리자 프로세스는 블루 태스크(blue task)라고 하는 특수 멀티프로세싱 작업 내에서 실행됩니다. 그것들의 프로세스는 라운드-로빈 스케줄링 알고리즘을 사용하여 협력적으로 스케줄링됩니다; 프로세스는 WaitNextEvent와 같은 차단 함수를 명시적으로 호출함으로써 프로세서 제어권을 또 다른 프로세스에 넘깁니다. 각 프로세스는 해당 프로세스의 쓰레드를 협력적으로 스케줄링하는 쓰레드 관리자의 고유한 사본을 가지고 있습니다; 쓰레드는 YieldToAnyThread 또는 YieldToThread를 호출하여 프로세서 제어권을 또 다른 쓰레드에 넘깁니다.

macOS는 쓰레드에 대해 정규, 시스템 높은 우선순위, 커널 모드 전용, 및 실-시간의 4가지 우선순위 대역을 갖는 다중-수준 피드백 대기열을 사용합니다. 쓰레드는 선점적으로 예약됩니다; macOS는 Carbon에서 쓰레드 관리자 구현에서 협력적으로 스케줄된 쓰레드도 지원합니다.

AIX

AIX 버전 4에서, 쓰레드 스케줄링 정책에 대해 가능한 세 가지 값이 있습니다:

  • 선입선출: 일단 이 정책을 갖는 쓰레드가 예약되면, 그것이 차단되지 않는 한, 자발적으로 CPU 제어권을 넘기거나, 더 높은-우선순위 쓰레드가 디스패치 가능해지지 않는 한 완료될 때까지 실행됩니다. 고정 우선순위 쓰레드만 FIFO 스케줄링 정책을 가질 수 있습니다.
  • 라운드 로빈: 이것은 10ms 시간 슬라이스를 기반으로 하는 AIX 버전 3 스케줄러 라운드-로빈 방식과 유사합니다. RR 쓰레드가 시간 슬라이스의 끝에서 제어권을 가질 때, 우선순위의 디스패치 가능 쓰레드 대기열의 끝으로 이동합니다. 고정-우선순위 쓰레드만 라운드-로빈 스케줄링 정책을 가질 수 있습니다.
  • 기타: 이 정책은 POSIX1003.4a에서 구현-정의로 정의됩니다. AIX 버전 4에서, 이 정책은 고정되지 않은 우선순위를 갖는 스레드에 적용되는 것을 제외하고는 RR과 동등하게 정의됩니다. 각 클록 인터럽트에서 실행 중인 쓰레드의 우선순위 값을 다시 계산하면 쓰레드가 우선순위 값이 또 다른 디스패치 가능 쓰레드보다 높아져 제어를 잃을 수 있습니다. 이는 AIX 버전 3 행위입니다.

쓰레드는 현재 여러 비동기 프로세스로 구성된 응용 프로그램에 주로 관심이 있습니다. 이들 응용 프로그램은 멀티쓰레드 구조로 변환하면 시스템에 더 가벼운 부하를 가할 수 있습니다.

AIX 5는 다음 스케줄링 정책을 구현합니다: FIFO, 라운드 로빈, 및 공정한 라운드 로빈. FIFO 정책에는 FIFO, FIFO2, 및 FIFO3의 세 가지 다른 구현이 있습니다. 라운드 로빈 정책은 AIX에서 SCHED_RR이라고 이름-짓고, 공정한 라운드 로빈은 SCHED_OTHER라고 불렀습니다.

Linux

Linux 1.2

리눅스 1.2는 라운드-로빈 스케줄링 정책을 사용했습니다.

Linux 2.2

리눅스 2.2에서는 스케줄링 클래스와 대칭적 멀티프로세싱 (SMP) 지원이 추가되었습니다.

Linux 2.4

리눅스 2.4에서, 우선 순위 수준이 0~140을 갖는 다중-수준 피드백 대기열을 갖춘 O(n) 스케줄러가 사용되었습니다; 0~99는 실시간 작업을 위해 예약되어 있고 100~140은 nice 작업 수준으로 간주됩니다. 실-시간 작업에 대해, 프로세스를 전환하는 데 시간 양자는 약 200ms이고, nice 작업에 대해 약 10ms입니다. 스케줄러는 모든 준비된 프로세스의 실행 대기열을 통해 실행하여, 가장 높은 우선 순위 프로세스를 먼저 실행하도록 허용하고 해당 시간 슬라이스를 실행한 후, 그것들은 만료된 대기열에 배치될 것입니다. 활성 대기열이 비어 있을 때, 만료된 대기열이 활성 대기열이 되고 그 반대의 경우도 마찬가지입니다.

어쨌든, SUSE Linux Enterprise Server와 같은 일부 엔터프라이즈 리눅스 배포판은 이 스케줄러를 배포판에 의해 사용되는 리눅스 2.4 커널에 대한 O(1) 스케줄러 (Alan Cox에 의해 Linux 2.4-ac 커널 시리즈에서 유지 관리)의 백포트로 대체했습니다.

Linux 2.6.0 to Linux 2.6.22

버전 2.6.0에서 2.6.22까지 커널은 Linux 2.5 개발 중에 Ingo Molnar와 다른 많은 커널 개발자에 의해 개발된 O(1) 스케줄러를 사용했습니다. 시간 프레임에서 많은 커널을 위해, Con Kolivas는 이 스케줄러와의 상호 작용을 개선하거나 자신의 스케줄러로 대체하는 패치 집합을 개발했습니다.

Linux 2.6.23 to Linux 6.5

Con Kolivas의 작업, 특히 Rotating Staircase Deadline (RSDL)이라는 공정 스케줄링의 구현은 Ingo Molnár가 이전의 O(1) 스케줄러를 대체하기 위해 Completely Fair Scheduler (CFS)를 개발하도록 영감을 주었으며, 이는 그의 발표에서 Kolivas의 공로를 인정한 것입니다. CFS는 일반적인-목적 운영 시스템에서 널리 사용되는 공정 대기열 프로세스 스케줄러의 첫 번째 구현입니다.

CFS는 원래 패킷 네트워크를 위해 발명된 공정한 대기열이라는 잘-연구된 클래식 스케줄링 알고리즘을 사용합니다. 공정한 대기열은 이전에 스트라이드 스케줄링(stride scheduling)이라는 이름으로 CPU 스케줄링에 적용되어 왔습니다. 공정한 대기열 CFS 스케줄러는 \(O(\log N)\)의 스케줄링 복잡도를 가지고 있으며, 여기서 N은 실행-대기열에 있는 작업의 개수입니다. 작업을 선택하는 것은 상수 시간 내에 수행될 수 있지만, 실행된 후에 작업을 다시 삽입하는 것은 \(O(\log N)\) 연산이 필요한데, 왜냐하면 실행 대기열은 레드-블랙 트리로 구현되기 때문입니다.

역시 Con Kolivas에 의해 만들어진 Brain Fuck Scheduler는 CFS의 대안입니다.

Linux 6.6

2023년에, Peter Zijlstra는 CFS를 가장 빠른 적격 가상 마감-시간 우선 스케줄링(earliest eligible virtual deadline first scheduling, EEVDF) 프로세스 스케줄러로 교체할 것을 제안했습니다. 그 목적은 CFS 지연 나이스(latency nice) 패치의 필요성을 없애는 것이었습니다.

FreeBSD

FreeBSD는 우선순위가 0–255 범위를 갖는 다중-수준 피드백 대기열을 사용합니다. 0–63은 인터럽트에 대해, 64–127은 커널의 꼭대기 절반에 대해, 128–159는 실-시간 사용자 쓰레드에 대해, 160–223은 시간-공유 사용자 쓰레드에 대해, 그리고 224–255는 유휴 사용자 쓰레드에 대해 예약되어 있습니다. 역시, 리눅스와 마찬가지로, 활성 대기열 설정을 사용하지만, 유휴 대기열도 있습니다.

NetBSD

NetBSD는 우선순위가 0–223 범위를 갖는 다중-수준 피드백 대기열을 사용합니다. 0–63은 시간-공유 쓰레드 (기본값, SCHED_OTHER 정책)에 대해, 64–95는 커널 공간에 들어온 사용자 쓰레드에 대해, 96-128은 커널 쓰레드에 대해, 128–191은 사용자 실-시간 쓰레드 (SCHED_FIFO 및 SCHED_RR 정책)에 대해, 그리고 192–22은 소프트웨어 인터럽트에 대해 예약되어 있습니다.

Solaris

Solaris는 우선순위 0에서 169 사이 범위를 갖는 다중-수준 피드백 대기열을 사용합니다. 우선순위 0–59는 시간-공유 쓰레드에 대해, 60–99는 시스템 쓰레드에 대해, 100–159는 실-시간 쓰레드에 대해, 그리고 160–169는 낮은 우선순위 인터럽트에 대해 예약되어 있습니다. 리눅스와 달리, 프로세스가 시간 양자를 사용하여 완료될 때, 새 우선순위가 주어지고 대기열에 다시 배치됩니다. Solaris 9에서는 고정-우선순위 클래스와 공정 공유 클래스라는 두 가지 새로운 스케줄링 클래스가 도입되었습니다. 고정 우선순위를 갖는 쓰레드는 시간-공유 클래스의 그것과 같은 우선순위 범위를 가지지만, 우선순위는 동적으로 조정되지 않습니다. 공정 스케줄링 클래스는 CPU 공유를 사용하여 스케줄링 결정을 위한 쓰레드의 우선순위를 지정합니다. CPU 공유는 CPU 자원에 대한 자격을 나타냅니다. 그것들은 프로젝트라고 총칭되는 프로세스의 집합에 할당됩니다.

Summary

References

Further reading

 

 

 

관련글

티스토리툴바