스케줄링(컴퓨팅)

Scheduling (computing)
이 기사는 전반적인 스케줄링에 관한 것이다.네트워크는 네트워크 스케줄러를 참조하십시오.기타 용도는 스케줄링(동음이의)을 참조하십시오.

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

스케줄링 활동은 스케줄러라는 프로세스에 의해 수행된다.스케줄러는 (부하 분산과 마찬가지로) 모든 컴퓨터 자원을 사용 중이거나, 여러 사용자가 효과적으로 시스템 자원을 공유하거나, 목표 서비스 품질을 달성할 수 있도록 설계되는 경우가 많다.

스케줄링은 계산 그 자체와 컴퓨터 시스템의 실행 모델의 본질적인 부분이다; 스케줄링의 개념은 컴퓨터가 하나의 중앙 처리 장치(CPU)로 멀티태스킹하는 것을 가능하게 한다.

목표들

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

  • 처리량 최대화(시간 단위당 완료되는 총 작업량)
  • 대기 시간 최소화(작업 준비 시간부터 실행 시작 시점까지)
  • 지연 시간 또는 응답 시간 최소화([4]배치 활동의 경우 작업이 완료될 때까지 [1][2][3]또는 시스템이 응답하여 상호 작용의 경우 사용자에게 첫 번째 출력을 제공할 때까지의 작업 시간)
  • 공정성 극대화(각 프로세스와 동일한 CPU 시간 또는 각 프로세스의 우선 순위 및 워크로드에 따라 보다 일반적으로 적절한 시간).

실제로 이러한 목표는 종종 충돌하므로(예: 처리량 대 지연 시간) 스케줄러는 적절한 절충안을 구현할 것이다.선호도는 사용자의 요구와 목표에 따라 위에서 언급한 우려 중 하나에 의해 측정된다.

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

운영 체제 스케줄러 유형

참고 항목:네트워크 스케줄러, I/O 스케줄링 및 작업 스케줄러

스케줄러는 시스템에 허용할 다음 작업과 실행할 다음 프로세스를 선택하는 운영 체제 모듈이다.운영체제는 최대 세 가지 구분된 스케줄러 유형을 특징으로 할 수 있다: 장기 스케줄러(입장 스케줄러 또는 하이 레벨 스케줄러라고도 함), 중기 스케줄러 및 단기 스케줄러.그 이름들은 그들의 기능이 수행되는 상대적인 빈도를 암시한다.

프로세스 스케줄러

프로세스 스케줄러는 특정 시점에 실행될 프로세스를 결정하는 운영 체제의 일부다.보통 실행 중인 프로세스를 일시 중지하고 실행 중인 대기열의 뒤로 이동한 후 새로운 프로세스를 시작하는 기능을 가지고 있다. 이러한 스케줄러는 선제적 스케줄러로 알려져 있고 그렇지 않으면 협력 스케줄러로 알려져 있다.[5]

의사결정이 얼마나 자주 이루어져야 하는가에 따라 「장기 스케줄링」, 「중기 스케줄링」, 「단기 스케줄링」을 구분한다.[6]

장기스케줄링

장기 스케줄러 또는 승인 스케줄러는 준비 대기열(메인 메모리)에 허용할 작업 또는 프로세스를 결정한다. 즉, 프로그램을 실행하려고 시도할 때 현재 실행 중인 프로세스 세트에 대한 승인 또는 지연이 장기 스케줄러에 의해 승인된다.따라서 이 스케줄러는 시스템에서 실행할 프로세스와 동시성의 정도, 즉 다수의 프로세스를 동시에 실행할지 또는 소수의 프로세스를 동시에 실행할지 여부와 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 시간을 확보할 수 있도록 하기 위해 이 기능을 사용한다.[7]

일괄 처리 시스템, 컴퓨터 클러스터, 슈퍼컴퓨터, 렌더 팜 등 대규모 시스템에서도 장기 스케줄링이 중요하다.예를 들어, 동시 시스템에서는 상호 작용하는 프로세스의 공동 스케줄링이 서로 기다림으로 인해 차단되는 것을 방지해야 하는 경우가 많다.이러한 경우, 운영 체제에서 기본 승인 스케줄링 지원 외에 이러한 기능을 지원하기 위해 특수 목적 작업 스케줄러 소프트웨어가 일반적으로 사용된다.

일부 운영 체제는 모든 실시간 마감일이 여전히 충족될 수 있다고 확신하는 경우에만 새로운 작업이 추가될 수 있도록 허용한다.운영체제가 새로운 업무를 수용하거나 거부하기 위해 사용하는 특정한 경험적 경험적 알고리즘은 승인 제어 메커니즘이다.[8]

중기 스케줄링

중기 스케줄러는 주 메모리에서 일시적으로 프로세스를 제거하고 이를 보조 메모리(하드 디스크 드라이브 등)에 배치하거나, 반대로 일반적으로 "스왑 아웃" 또는 "스왑 인"("pauting out" 또는 "painting in"이라고도 잘못 표기함)이라고 한다.중기 스케줄러는 한동안 활성화되지 않은 프로세스, 우선순위가 낮은 프로세스 또는 페이지 결함을 자주 일으키는 프로세스 또는 다른 프로세스의 메인 메모리를 확보하기 위해 많은 양의 메모리를 차지하는 프로세스를 스왑 아웃하기로 결정할 수 있으며, 메모리가 많을 때 프로세스를 다시 스왑할 수 있다.사용 가능한 경우 또는 프로세스가 차단 해제되어 더 이상 리소스를 기다리지 않는 경우[스털링, 396] [스털링, 370]

오늘날의 많은 시스템(스왑 파일 이외의 2차 스토리지에 가상 주소 공간을 매핑하는 것을 지원하는 시스템)에서 중기 스케줄러는 실행 시 바이너리를 "스왑 아웃 프로세스"로 처리함으로써 실제로 장기 스케줄러의 역할을 수행할 수 있다.이러한 방식으로, 이진의 세그먼트가 필요할 때, 그것은 요청 시 교환될 수 있으며, 또는 "지속 로딩", [Stallings, 394] 또한 요구 페이징이라고 불린다.

단기 스케줄링

단기 스케줄러(CPU 스케줄러라고도 함)는 클럭 인터럽트, I/O 인터럽트, 운영 체제 호출 또는 다른 형태의 신호 후에 실행할 준비 상태의 메모리 내 프로세스(CPU 할당)를 결정한다.따라서 단기 스케줄러는 장기 스케줄러 또는 중간 스케줄러보다 스케줄링 결정을 훨씬 더 자주 내린다. 스케줄링 결정은 최소한 매 슬라이스 후에 이루어져야 하며, 이는 매우 짧다.이 스케줄러는 CPU가 CPU를 다른 프로세스에 할당하기로 결정할 때 CPU에서 프로세스를 강제로 제거할 수 있으며, 이 경우 스케줄러가 CPU에서 프로세스를 "강제"할 수 없는 비선제적("voluntary" 또는 "co-operative"라고도 함)을 의미한다.

선제적 스케줄러는 커널 모드에서 실행되는 인터럽트 핸들러를 호출하고 스케줄링 기능을 구현하는 프로그램 가능한 인터럽트 타이머에 의존한다.

디스패처

CPU 스케줄링 기능에 관여하는 또 다른 구성요소는 단기 스케줄러가 선택한 프로세스에 CPU를 제어하는 모듈인 디스패처다.인터럽트나 시스템 호출의 결과로 커널 모드에서 제어권을 수신한다.발송인의 기능은 다음과 같다.

  • 전송자가 이전에 실행된 프로세스 또는 스레드의 상태(일명 컨텍스트)를 저장한 컨텍스트 스위치. 그런 다음 전송자는 새 프로세스의 초기 또는 이전에 저장된 상태를 로드한다.
  • 사용자 모드로 전환 중.
  • 사용자 프로그램의 적절한 위치로 이동하여 새 상태로 표시된 프로그램을 다시 시작하십시오.

모든 프로세스 스위치 중에 호출되므로, 발송인은 가능한 한 빨리 실행되어야 한다.컨텍스트 스위치 중에는 프로세서가 사실상 단시간 동안 유휴 상태가 되므로 불필요한 컨텍스트 스위치는 피해야 한다.발송자가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 걸리는 시간을 발송 지연 시간이라고 한다.[7]: 155

스케줄링 분야

스케줄링 분야(스케줄링 정책 또는 스케줄링 알고리즘이라고도 함)는 자원을 동시에 비동기적으로 요청하는 당사자 간에 자원을 분배하는 데 사용되는 알고리즘이다.스케줄링 원칙은 운영 체제뿐만 아니라 라우터(패킷 트래픽 처리), 운영 체제(스레드 및 프로세스 간 CPU 시간 공유), 디스크 드라이브(I/O 스케줄링), 프린터(프린트 스풀러), 대부분의 내장 시스템 등에서 사용된다.

알고리즘 스케줄링의 주요 목적은 자원 기아를 최소화하고 자원을 이용하는 당사자 사이의 공정성을 보장하는 것이다.스케줄링은 미결된 요청 중 어떤 것이 자원 할당 대상인지 결정하는 문제를 다룬다.스케줄링 알고리즘에는 여러 가지가 있다.이 섹션에서는 몇 가지를 소개한다.

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

가장 단순한 베스트 에포트 스케줄링 알고리즘은 라운드 로빈, 페어 큐(최대 공정 스케줄링 알고리즘), 비례 공정 스케줄링 및 최대 처리량이다.최상의 통신과 달리 차별화된 서비스 품질 또는 보장된 서비스가 제공될 경우 가중 공정 대기열을 활용할 수 있다.

HSDPA(High-Speed Downlink Packet Access) 3.5G 셀룰러 시스템과 같은 고급 패킷 무선 네트워크에서는 채널 상태 정보를 이용하기 위해 채널 의존적 스케줄링을 사용할 수 있다.채널 조건이 유리한 경우 처리량과 시스템 스펙트럼 효율이 증가할 수 있다.LTE와 같은 훨씬 더 진보된 시스템에서는, 스케줄링이 채널 의존적인 패킷 별 동적 채널 할당이나, OFDMA 멀티캐리어 또는 다른 주파수 영역 균등화 컴포넌트를 가장 잘 활용할 수 있는 사용자에게 할당함으로써 결합된다.[9]

먼저 온 사람에게 우선권이 주어진다.

주요기사: FIFO(컴퓨팅 및 전자제품)
대기 중인 작업의 대기열(FIFO)과 완료된 작업의 대기열(노란색)이 있는 샘플 스레드 풀(녹색 상자)

퍼스트 인 퍼스트 아웃(FIFO, first come, first coming, first served, FCFS)은 가장 간단한 스케줄링 알고리즘이다.FIFO는 단지 그들이 준비된 대기열에 도착하는 순서대로 프로세스를 대기열에 넣는다.이것은 예를 들어 이 절에서 설명한 것처럼 작업 대기열에 일반적으로 사용된다.

  • 컨텍스트 스위치는 프로세스 종료 시에만 발생하며 프로세스 대기열의 재구성이 필요하지 않기 때문에 스케줄링 오버헤드는 미미하다.
  • 처리량이 낮을 수 있는데, 이는 긴 공정이 CPU를 지탱할 수 있기 때문에 짧은 공정이 오랫동안 대기할 수 있기 때문이다(운반 효과로 알려져 있음).
  • 기아는 없다. 왜냐하면 각각의 과정은 정해진 시간 후에 실행될 기회를 얻기 때문이다.
  • 전환 시간, 대기 시간 및 응답 시간은 도착 순서에 따라 다르며 위의 동일한 이유로 인해 높을 수 있다.
  • 우선순위 지정이 발생하지 않으므로 이 시스템은 프로세스 마감일을 준수하는 데 어려움을 겪는다.
  • 우선순위가 없다는 것은 결국 모든 과정이 완성되는 한 굶는 일이 없다는 뜻이다.일부 과정이 완료되지 않을 수 있는 환경에서는 기아 문제가 발생할 수 있다.
  • 그것은 큐를 기반으로 한다.

우선 순위 스케줄링

주요 기사: 가장 빠른 마감 첫 번째 예약
참고 항목:마감일 단조 스케줄링

가장 빠른 마감일 우선(EDF) 또는 최소 이동 시간은 실시간 운영 체제에서 우선 순위 대기열에 프로세스를 배치하기 위해 사용되는 동적 스케줄링 알고리즘이다.스케줄링 이벤트가 발생할 때마다(태스크가 종료되고, 새 태스크가 릴리스되는 등) 대기열에서 마감에 가장 가까운 프로세스를 검색하며, 이는 실행 스케줄이 다음으로 될 것이다.

최단 잔여 시간 먼저

주요 기사:최단잔속시간

최단 작업 우선(SJF)과 유사함.이 전략을 사용하여 스케줄러는 대기열에서 처리 시간이 가장 적게 남은 프로세스를 정렬한다.이를 위해서는 공정이 완료되는 데 필요한 시간에 대한 고급 지식이나 추정치가 필요하다.

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

고정 우선 순위 사전 허용 스케줄링

주요 기사:고정 우선 순위 사전 허용 스케줄링

운영체제는 모든 프로세스에 고정 우선순위 순위를 할당하고, 스케줄러는 그 우선순위에 따라 프로세스를 준비 대기열에 정렬한다.우선순위가 낮은 프로세스는 우선순위가 높은 프로세스가 들어오는 것에 의해 중단된다.

  • 오버헤드는 미미하지도 않고, 의미도 없다.
  • FPPS는 FIFO 스케줄링에 비해 처리량 면에서 특별한 이점이 없다.
  • 랭킹 개수가 제한될 경우 우선순위별 1개씩 FIFO 대기열의 집합으로 특징지을 수 있다.우선순위가 낮은 대기열의 프로세스는 우선순위가 높은 대기열이 모두 비어 있는 경우에만 선택된다.
  • 대기 시간과 응답 시간은 프로세스의 우선순위에 따라 달라진다.우선순위가 높은 프로세스는 대기 및 응답 시간이 적다.
  • 마감일은 마감일이 있는 공정에 더 높은 우선순위를 부여함으로써 충족될 수 있다.
  • 우선순위가 낮은 프로세스는 CPU 시간 동안 많은 수의 높은 우선순위 프로세스가 대기하면서 기아가 가능하다.

라운드 로빈 스케줄링

주요 기사: 라운드 로빈 스케줄링

스케줄러는 프로세스당 고정 시간 단위를 할당하고 이를 순환한다.공정이 해당 시간 경과 내에 완료되면 종료되며 그렇지 않으면 다른 모든 공정에 기회를 준 후 일정이 변경된다.

  • RR 스케줄링에는 특히 작은 시간 단위를 포함한 광범위한 오버헤드가 수반된다.
  • FCFS/FIFO와 SJF/SRTF 사이의 균형 잡힌 처리량, 짧은 작업은 FIFO에서보다 더 빨리 완료되고 긴 프로세스는 SJF에서보다 더 빨리 완료된다.
  • 양호한 평균 응답 시간, 대기 시간은 프로세스 수에 따라 달라지지만 평균 프로세스 길이가 아니다.
  • 대기 시간이 길기 때문에 순수한 RR 시스템에서는 마감일이 거의 충족되지 않는다.
  • 기아는 절대 일어날 수 없다. 우선권이 주어지지 않기 때문이다.시간 단위 할당 순서는 FIFO와 유사한 프로세스 도착 시간을 기준으로 한다.
  • Time-Slice가 크면 FCFS/FIFO가 되고, 짧으면 SJF/SRTF가 된다.

다단계 대기열 스케줄링

주요 기사:다단계 대기열

이것은 프로세스가 다른 그룹으로 쉽게 분할되는 상황에 사용된다.예를 들어, 포그라운드(상호작용) 프로세스와 백그라운드(배치) 프로세스 사이에 공통적인 구분이 이루어진다.이 두 가지 유형의 프로세스는 응답 시간 요구사항이 다르므로 스케줄링 요구사항이 다를 수 있다.그것은 공유 메모리 문제에 매우 유용하다.

작업 보존 스케줄러

주요 기사:작업 보존 스케줄러

작업 보존 스케줄러는 제출되는 작업이 예약 준비 상태인 경우 예약된 리소스를 항상 사용 가능한 상태로 유지하려고 하는 스케줄러입니다.이와는 대조적으로, 비작업 보존 스케줄러는 스케줄러로서, 어떤 경우에는 스케줄링할 준비가 되어 있는 작업에도 불구하고 스케줄러로 스케줄링된 리소스를 유휴 상태로 둘 수 있다.

최적화 문제 스케줄링

어떤 일이 언제 어느 역에 가는지 결정하는 것이 목표인 몇 가지 스케줄링 문제가 있는데, 이를 통해 전체 작업 공간을 최소화할 수 있다.

  • Job Shop 스케줄링 – N개의 직장과 동일한 역이 있다.각각의 작업은 하나의 기계에서 실행되어야 한다.이것은 보통 온라인상의 문제로 간주된다.
  • 오픈 숍 스케줄링 – 직장이 n개 있고 역이 다르다.각 직장은 각 역에서 자유 순서로 시간을 보내야 한다.
  • 플로우 숍 스케줄링 – 직장이 n개 있고 다른 스테이션이 있다.각 직장은 미리 정해진 순서대로 각 역에서 시간을 보내야 한다.

수동 스케줄링

임베디드 시스템에서 매우 일반적인 방법은 작업을 수동으로 예약하는 것이다.예를 들어 이것은 시간 다중화 방식으로 행해질 수 있다.때때로 커널은 수동 스케줄링, 사전 스케줄링 및 인터럽트 레벨의 세 개 이상의 부분으로 나뉜다.정확한 작업 스케줄링 방법은 종종 독점적이다.

  • 리소스 부족 문제 없음
  • 매우 높은 예측 가능성, 하드 실시간 시스템 구현 가능
  • 거의 오버헤드 없음
  • 모든 애플리케이션에 최적이지는 않을 수 있음
  • 효과성은 구현에 따라 완전히 달라진다.

스케줄링 알고리즘 선택

운영 체제를 설계할 때 프로그래머는 시스템이 볼 수 있는 사용에 가장 적합한 스케줄링 알고리즘을 고려해야 한다.보편적인 "최상의" 스케줄링 알고리즘은 없으며, 많은 운영체제가 위의 스케줄링 알고리즘의 확장 또는 조합을 사용한다.

예를 들어 Windows NT/XP/Vista는 고정 우선순위 선제 스케줄링, 라운드 로빈 및 퍼스트 아웃 알고리즘의 조합인 다단계 피드백 대기열을 사용한다.이 시스템에서 스레드는 이미 서비스를 받았는지, 아니면 광범위하게 대기하고 있었는지에 따라 우선순위를 동적으로 증가시키거나 감소시킬 수 있다.모든 우선순위 수준은 높은 우선순위 스레드 중 라운드 로빈 스케줄링, 낮은 우선순위 중 FIFO를 가진 자체 대기열로 표현된다.이런 의미에서 대부분의 스레드에 대한 응답 시간은 짧고 짧지만 중요한 시스템 스레드는 매우 빨리 완성된다.스레드는 가장 높은 우선순위 대기열에서 라운드 로빈의 1회 단위만 사용할 수 있기 때문에 더 긴 우선순위 스레드의 경우 기아 문제가 될 수 있다.

운영 체제 프로세스 스케줄러 구현

사용되는 알고리즘은 사이클링 리스트에서 각 공정에 동일한 시간(예: 1ms, 보통 1ms와 100ms 사이)이 주어지는 라운드 로빈처럼 단순할 수 있다.따라서 프로세스 A는 1ms 동안 실행한 다음 프로세스 B, 프로세스 C, 프로세스 A로 다시 실행한다.

보다 고급 알고리즘은 프로세스 우선 순위, 즉 프로세스의 중요성을 고려한다.이를 통해 일부 프로세스가 다른 프로세스보다 더 많은 시간을 사용할 수 있다.커널은 항상 시스템의 적절한 기능을 보장하기 위해 필요한 모든 자원을 사용하며, 따라서 무한한 우선순위를 가지고 있다고 말할 수 있다.SMP 시스템에서 프로세서 친화력은 프로세스 자체를 더 느리게 실행하게 할 수 있더라도 전체 시스템 성능을 증가시키는 것으로 간주된다.이것은 일반적으로 캐시 스레싱을 줄임으로써 성능을 향상시킨다.

OS/360 및 후속 제품

IBM OS/360은 세 개의 다른 스케줄러와 함께 사용할 수 있었다.차이점은 세 가지 다른 운영 체제로 간주되는 경우가 많았다.

  • PCP(Primary Control Program)라고도 하는 Single Sequential Scheduler 옵션은 단일 작업 스트림의 순차 실행을 제공했다.
  • MFT(Multiprogramming with 고정된 작업 수)로 알려진 다중 시퀀셜 스케줄러 옵션은 여러 동시 작업을 실행하도록 했다.실행은 각 스트림에 대해 기본값이 있거나 각 작업에 대해 별도로 요청할 수 있는 우선 순위에 의해 관리되었다.MFT 버전 II에는 상위 작업에 기반한 우선 순위로 실행된 하위 작업(스레드)이 추가되었다.각 작업 스트림은 해당 스트림의 모든 작업에서 사용할 수 있는 최대 메모리 양을 정의했다.
  • 다중 우선순위 스케줄러 옵션(MVT(Multiple Priority Scheduler) 또는 다중 프로그래밍(Multiprogramming with Variable Number of Tasks)은 처음부터 하위 작업을 수행했으며, 각 작업은 실행 전에 필요한 우선 순위 및 메모리를 요청했다.

이후 MVS의 가상 스토리지 버전은 스케줄러에 Workload Manager 기능을 추가했는데, 이 기능은 설치에 의해 정의된 정교한 계획에 따라 프로세서 리소스를 예약한다.

창문들

초기의 MS-DOS와 Microsoft Windows 시스템은 비 멀티태스킹이었고, 따라서 스케줄러가 특징이지 않았다.윈도 3.1x는 비선제적 스케줄러를 사용했는데, 이는 그것이 프로그램을 중단시키지 않았다는 것을 의미한다.프로그램을 종료하거나 OS에 프로세서가 필요 없다고 말해 다른 프로세스로 넘어갈 수 있도록 했다.이것은 보통 협동 멀티태스킹이라고 불린다.윈도 95는 초보적인 선제적 스케줄러를 도입했지만, 레거시 지원을 위해 16비트 애플리케이션을 선점 없이 실행하도록 선택했다.[10]

Windows NT 기반 운영 체제는 다단계 피드백 대기열을 사용한다.32개의 우선순위 레벨이 정의되며, 우선순위 0 ~ 15는 "정상" 우선순위, 우선순위 16 ~ 31은 소프트 실시간 우선순위로서 특권을 부여해야 한다.0은 운영 체제에 예약되어 있다.사용자 인터페이스와 API는 프로세스에 대한 우선 순위 클래스와 프로세스 내의 스레드를 사용하여 작동하며, 이 클래스는 시스템에 의해 절대 우선 순위 레벨로 결합된다.

커널은 I/O 및 CPU 사용량 및 인터랙티브인지 여부에 따라 스레드의 우선 순위 수준을 변경할 수 있으며(즉, 인간의 입력을 수용하고 응답) 인터랙티브 및 I/O 바운드 프로세스의 우선 순위를 높이고 CPU 바인딩 프로세스의 우선 순위를 낮추어 인터랙티브 애플리케이션의 응답성을 높일 수 있다.[11]Windows Vista에서 스케줄러는 단순히 인터럽트 타임 인터럽트 루틴을 사용하는 것이 아니라 스레드가 실행한 CPU 사이클 수를 정확히 추적하기 위해 현대 프로세서의 사이클 카운터 레지스터를 사용하도록 수정되었다.[12]또한 Vista는 디스크 조각 모음 및 기타 프로그램이 전경 작업을 방해하지 않도록 I/O 대기열에 우선 순위 스케줄러를 사용한다.[13]

클래식 Mac OS 및 MacOS

Mac OS 9는 한 프로세스가 여러 개의 공동 스레드를 제어하고 다중 처리 작업을 위한 사전 예약 기능을 제공하는 스레드에 대해 공동 스케줄링을 사용한다.커널은 사전 예약 알고리즘을 사용하여 다중 처리 태스크를 예약한다.모든 프로세스 관리자 프로세스는 "파란색 태스크"라는 특수 다중 처리 태스크 내에서 실행된다.이러한 프로세스는 라운드 로빈 스케줄링 알고리즘을 사용하여 협력적으로 스케줄링된다. 프로세스는 다음과 같은 차단 기능을 명시적으로 호출하여 프로세서를 다른 프로세스로 제어한다.WaitNextEvent. 각 프로세스에는 프로세스의 스레드를 공동 스케줄링하는 자체적인 스레드 관리자 복사본이 있으며, 스레드는 호출하여 프로세서를 다른 스레드로 제어한다.YieldToAnyThread또는YieldToThread.[14]

MacOS는 멀티레벨 피드백 대기열을 사용하며, 스레드에 대해 네 가지 우선 순위 대역(일반, 시스템 높음 우선 순위, 커널 모드 전용, 실시간)을 사용한다.[15]스레드는 사전에 계획되어 있으며, MacOS는 또한 Carbon의 스레드 매니저 구현 시 협력적으로 스케줄링된 스레드를 지원한다.[14]

AIX

AIX 버전 4에서는 스레드 스케줄링 정책에 대해 가능한 세 가지 값이 있다.

  • 우선 인, 퍼스트 아웃: 일단 이 정책이 있는 스레드가 예정되어 있으면 차단되지 않는 한, 자발적으로 CPU에 대한 제어권을 부여하거나, 우선 순위가 높은 스레드가 디스패치 가능한 상태가 되지 않는 한, 완료되기까지 실행된다.고정 우선 순위 스레드만 FIFO 스케줄링 정책을 가질 수 있다.
  • 라운드 로빈:이는 10ms 시간 슬라이스를 기반으로 한 AIX 버전 3 스케줄러 라운드 로빈 방식과 유사하다.RR 스레드가 시간 슬라이스의 끝에 제어권을 가지면, RR 스레드는 우선 순위의 디스패치 가능한 스레드의 대기열 꼬리로 이동한다.고정 우선 순위 스레드만 라운드 로빈 스케줄링 정책을 가질 수 있다.
  • 기타: 이 정책은 POSIX1003.4a에 의해 구현 정의된다.AIX 버전 4에서 이 정책은 고정되지 않은 우선 순위가 있는 스레드에 적용되는 것을 제외하고 RR와 동등한 것으로 정의된다.각 클럭 인터럽트에서 실행 중인 스레드의 우선 순위 값을 재계산한다는 것은 스레드의 우선 순위 값이 다른 디스패치 가능한 스레드의 우선 순위 값보다 높아졌기 때문에 스레드가 제어력을 상실할 수 있다는 것을 의미한다.AIX Version 3 동작이다.

스레드는 현재 몇 개의 비동기 프로세스로 구성된 애플리케이션에 주로 관심이 있다.이러한 애플리케이션은 다중 스레드 구조로 변환될 경우 시스템에 더 적은 부하를 가할 수 있다.

AIX 5는 FIFO, 라운드 로빈 및 페어 라운드 로빈과 같은 스케줄링 정책을 시행한다.FIFO 정책은 FIFO, FIFO2, FIFO3의 세 가지 다른 구현을 가지고 있다.라운드 로빈 정책은 AIX에서 SCED_RR, 페어 라운드 로빈은 SCED_OTER라고 불린다.[16]

리눅스

프로세스 스케줄러, I/O 스케줄러 및 패킷 스케줄러를 포함하는 매우 단순한 Linux 커널 구조

리눅스 2.4

Linux 2.4에서는 우선 순위 수준이 0 - 140인 다단계 피드백 대기열을 가진 O(n) 스케줄러가 사용되었으며, 0–99는 실시간 작업에 예약되어 있고 100–140은 좋은 작업 수준으로 간주된다.실시간 작업의 경우 프로세스 전환에 필요한 시간 퀀텀은 약 200ms, 좋은 작업의 경우 약 10ms였습니다.[citation needed]스케줄러는 모든 준비 프로세스의 실행 대기열을 통과하여 가장 높은 우선순위 프로세스를 먼저 실행하고 시간 조각을 차례로 실행한 후 만료된 대기열에 배치된다.활성 대기열이 비어 있으면 만료된 대기열이 활성 대기열이 되고 그 반대의 경우도 활성 대기열이 된다.

그러나 SUSE 리눅스 Enterprise Server와 같은 일부 엔터프라이즈 리눅스 배포판은 이 스케줄러를 O(1) 스케줄러(그의 Linux 2.4-ac 커널 시리즈에서 Alan Cox가 유지한 것)의 백포트로 대체하여 배포에서 사용하는 Linux 2.4 커널로 이동시켰다.

Linux 2.6.0에서 Linux 2.6.22로

버전 2.6.0 ~ 2.6.22에서, 커널은 Linux 2.5 개발 중에 Ingo Molnar와 많은 다른 커널 개발자들에 의해 개발된 O(1) 스케줄러를 사용했다.많은 커널을 위해 Con Kolivas는 이 스케줄러와의 상호작용을 개선하거나 심지어 자신의 스케줄러로 대체하는 패치 세트를 개발했다.

Linux 2.6.23 이후

콘 콜리바스의 업적은, 가장 두드러지게, "회전 계단 마감"이라는 이름을 붙인 "공정 스케줄링"의 이행으로, 인고 몰나르가 이전의 O(1) 스케줄러의 대체품으로 완전한 공정 스케줄러를 개발하도록 영감을 주어, 그의 발표에서 콜리바스를 신뢰하게 했다.[17]CFS는 범용 운영 체제에서 널리 사용되는 공정 대기열 프로세스 스케줄러를 최초로 구현한 것이다.[18]

완전 공정 스케줄러(CFS)는 패킷 네트워크를 위해 원래 고안된 공정 대기열이라는 잘 학습된 고전적인 스케줄링 알고리즘을 사용한다.공정한 대기열은 이전에 스트라이드 스케줄링이라는 이름으로 CPU 스케줄링에 적용되었었다.공정 대기열 CFS 스케줄러는 스케줄링 복잡도가 N) 이며 여기서 은 런큐의 작업 수입니다.작업을 선택하면 일정한 시간에 작업을 선택할 수 있지만 실행 대기열이 빨간색-검은색 트리로 구현되기 때문에 작업이 실행된 후 다시 삽입하려면 N) 작업이 필요하다.

콘 콜리바스가 만든 브레인 좆 스케줄러는 CFS의 대안이다.

자유BSD

FreeBSD는 0~255의 우선순위를 가진 다단계 피드백 대기열을 사용한다.0–63은 인터럽트용으로, 64–13은 커널의 상위 절반에, 128–13은 실시간 사용자 스레드에, 160–13은 시간 제한 사용자 스레드에, 224–13은 유휴 사용자 스레드에 대해 예약된다.또한 Linux와 마찬가지로 활성 대기열 설정을 사용하지만 유휴 대기열도 있다.[19]

넷BSD

NetBSD는 0–223 범위의 우선순위를 가진 다단계 피드백 대기열을 사용한다.0–63은 시간 공유 스레드(기본값, SCHED_OTER 정책), 커널 공간에 입력된 사용자 스레드의 경우 64–95, 커널 스레드의 경우 96-128, 사용자 실시간 스레드의 경우 128–191, 소프트웨어 인터럽트의 경우 192–223으로 예약되어 있다.

솔라리스

Solaris는 0과 169 사이의 우선순위를 가진 다단계 피드백 대기열을 사용한다.우선 순위 0~59는 시간 공유 스레드에, 60–99는 시스템 스레드에, 100–159는 실시간 스레드에, 160–169는 낮은 우선 순위 인터럽트에 예약되어 있다.타임 퀀텀을 이용해 공정을 진행하면 Linux와 달리 새로운 우선순위를 부여받아 다시 대기열에 넣는다.[19]Solaris 9는 두 가지 새로운 스케줄링 클래스, 즉 고정 우선 순위 클래스와 공정 공유 클래스를 도입했다.우선 순위가 고정된 스레드는 시간 공유 클래스의 우선 순위 범위와 동일하지만 우선 순위가 동적으로 조정되지 않는다.공정 스케줄링 클래스는 CPU 공유를 사용하여 스케줄링 결정을 위한 스레드의 우선순위를 정한다.CPU 공유는 CPU 리소스에 대한 사용 권한을 나타낸다.그것들은 집합적으로 프로젝트라고 알려진 일련의 과정에 할당된다.[7]

요약

운영 체제 선점 알고리즘.
아미가오스 네 우선 순위가 지정된 라운드 로빈 스케줄링
자유BSD 네 다단계 피드백 대기열
Linux 커널 2.6.0 이전 네 다단계 피드백 대기열
Linux 커널 2.6.0–2.6.23 네 O(1) 스케줄러
2.6.23 이후 Linux 커널 네 완전 공정 스케줄러
클래식 Mac OS Pre-9 없음 협동 스케줄러
맥 OS 9 일부 MP 작업을 위한 사전 예방적 스케줄러 및 프로세스와 스레드에 대한 협력
마코스 네 다단계 피드백 대기열
넷BSD 네 다단계 피드백 대기열
솔라리스 네 다단계 피드백 대기열
윈도 3.1x 없음 협동 스케줄러
윈도 95, 98, 미 절반 32비트 프로세스를 위한 사전 예방적 스케줄러 및 16비트 프로세스를 위한 공동 작업
Windows NT(2000, XP, Vista, 7 및 서버 포함) 네 다단계 피드백 대기열

참고 항목

메모들

  1. ^ C. L., Liu; James W., Layland (January 1973). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal of the ACM. ACM. 20 (1): 46–61. doi:10.1145/321738.321743. S2CID 207669821. We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.
  2. ^ Kleinrock, Leonard (1976). Queueing Systems, Vol. 2: Computer Applications (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.
  3. ^ Feitelson, Dror G. (2015). Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. if we denote the time that a job waits in the queue by tw, and the time it actually runs by tr, then the response time is r = tw + tr.
  4. ^ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Operating System Concepts (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.
  5. ^ Paul Krzyzanowski (2014-02-19). "Process Scheduling: Who gets to run next?". cs.rutgers.edu. Retrieved 2015-01-11.
  6. ^ 라파엘 핀켈."An Operating Systems Vade Mecum".프렌티스 홀, 1988년"2장: 시간 관리" 27쪽
  7. ^ a b c Abraham Silberschatz, Peter Baer Galvin and Greg Gagne (2013). Operating System Concepts. Vol. 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.{{cite book}}: CS1 maint: 작성자 매개변수 사용(링크)
  8. ^ 로버트 크뢰거(2004)"독립적으로 작성된 실시간 응용프로그램에 대한 승인 제어".UWSpace.http://hdl.handle.net/10012/1170. 섹션 "2.6 입장 통제" 페이지 33.
  9. ^ Guowang Miao; Jens Zander; Ki Won Sung; Ben Slimane (2016). Fundamentals of Mobile Data Networks. Cambridge University Press. ISBN 978-1107143210.
  10. ^ Wayback Machine의 초기 Windows(아카이브 인덱스)
  11. ^ Sriram Krishnan. "A Tale of Two Schedulers Windows NT and Windows CE". Archived from the original on July 22, 2012.
  12. ^ "Windows Administration: Inside the Windows Vista Kernel: Part 1". Technet.microsoft.com. 2016-11-14. Retrieved 2016-12-09.
  13. ^ "Archived copy". blog.gabefrost.com. Archived from the original on 19 February 2008. Retrieved 15 January 2022.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  14. ^ a b "Technical Note TN2028: Threading Architectures". developer.apple.com. Retrieved 2019-01-15.
  15. ^ "Mach Scheduling and Thread Interfaces". developer.apple.com. Retrieved 2019-01-15.
  16. ^ [1] 웨이백 머신에 보관된 2011-08-11
  17. ^ Molnár, Ingo (2007-04-13). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
  18. ^ Tong Li; Dan Baumberger; Scott Hahn. "Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin" (PDF). Happyli.org. Retrieved 2016-12-09.
  19. ^ a b "Comparison of Solaris, Linux, and FreeBSD Kernels" (PDF). Archived from the original (PDF) on August 7, 2008.

참조

추가 읽기