스케줄링 (컴퓨팅)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
스케줄링은 운영 체제가 시스템의 목적과 환경에 따라 다양한 수준으로 수행하는 작업 관리 기법이다. 스케줄러는 장기, 중기, 단기 스케줄러로 나뉘며, 각기 다른 시점에서 실행할 프로세스를 선택한다. 스케줄링 알고리즘은 CPU 사용률, 처리량, 응답 시간 등을 기준으로 평가되며, 비선점형과 선점형으로 구분된다. 대표적인 알고리즘으로는 FCFS, SJF, RR 등이 있으며, 운영 체제에 따라 다단계 피드백 큐, CFS 등 다양한 스케줄링 방식을 사용한다.
운영체제는 시스템의 목적과 환경에 따라 다양한 수준의 스케줄링을 수행한다. 스케줄러는 시스템에 다음에 허용될 작업과 다음에 실행할 프로세스를 선택하는 운영 체제 모듈이다. 운영 체제는 장기 스케줄러, 중기 스케줄러, 단기 스케줄러의 세 가지 유형을 가질 수 있다. 이러한 이름은 해당 기능이 수행되는 상대적 빈도를 나타낸다.
스케줄링 알고리즘은 시스템의 목적과 환경에 따라 적합한 알고리즘을 선택해야 하며, 다양한 기준을 통해 평가된다. 스케줄링 알고리즘은 크게 비선점형과 선점형으로 나눌 수 있다.
2. 스케줄링의 유형
스케줄러는 다음 목표 중 하나 이상을 가질 수 있다.
하지만 이러한 목표들은 상충되는 경우가 많다. (예: 처리량 대 지연 시간) 따라서 스케줄러는 사용자의 요구와 목표에 따라 적절한 타협점을 찾아 구현하며, 위에 언급된 문제 중 하나를 기준으로 선호도를 측정한다.
실시간 컴퓨팅 환경(예: 산업의 자동 제어(예: 로봇 공학)을 위한 임베디드 시스템)에서 스케줄러는 프로세스가 데드라인을 충족하도록 보장해야 한다. 이는 시스템의 안정성을 유지하는 데 매우 중요하다.
스케줄러는 크게 세 가지 유형으로 분류할 수 있다.
최근에는 소비 전력을 고려한 저전력 스케줄링 연구도 활발히 진행되고 있다.
2. 1. 장기 스케줄링 (Long-term Scheduling)
장기 스케줄러는 작업 스케줄링(Job scheduling)이라고도 하며, 어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다. 작업들이 시스템에 들어오는 것을 승인하기 때문에 승인 스케줄링(Admission scheduling)이라고도 한다.[1]
장기 스케줄러는 준비 큐(주 기억 장치)에 어떤 작업 또는 프로세스를 수용할지 결정한다. 즉, 프로그램 실행을 시도할 때 현재 실행 중인 프로세스 집합에 대한 수용이 장기 스케줄러에 의해 승인되거나 지연된다. 따라서 이 스케줄러는 시스템에서 어떤 프로세스가 실행될지, 어느 시점에서 지원될 동시성의 정도(많은 프로세스를 동시에 실행할지, 소수의 프로세스를 실행할지), 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 시간을 확보하도록 하기 위해 이 조합이 사용된다.
장기 스케줄링은 배치 처리 시스템, 컴퓨터 클러스터, 슈퍼컴퓨터, 렌더 팜과 같은 대규모 시스템에서도 중요하다. 이러한 경우, 전용 작업 관리 시스템이 장기 스케줄러의 역할을 한다.
일부 운영 체제는 모든 실시간 마감일을 여전히 충족할 수 있는지 확인하는 경우에만 새 작업을 추가하도록 허용한다. 운영 체제가 새 작업을 수락하거나 거부하는 데 사용하는 특정 휴리스틱 알고리즘을 ''수용 제어 메커니즘''이라고 한다.
일반적인 개인용 컴퓨터 등에서는 장기 스케줄러가 존재하지 않고, 프로세스가 생성되면 자동으로 실행 가능 상태가 된다. 그러나, 실시간 운영 체제(RTOS)와 같은 실시간 시스템에서는 장기 스케줄러가 중요하며, 응답 시간의 보장을 위해 동시적으로 실행하는 프로세스 수를 제한하는 등의 기능으로 보다 확실한 제어가 이루어진다.
2. 2. 중기 스케줄링 (Medium-term Scheduling)
중기 스케줄러는 프로세스를 주 기억 장치에서 보조 기억 장치(예: 하드 디스크 드라이브)로 임시로 제거하거나 그 반대로 이동시키는 역할을 한다. 이러한 동작을 각각 스왑 아웃(swap-out) 또는 스왑 인(swap-in)이라고 부른다. (잘못된 표현으로는 '페이징 아웃' 또는 '페이징 인'이라고도 한다.)[25]
중기 스케줄러는 다음과 같은 프로세스를 스왑 아웃할 수 있다.
이후에 더 많은 메모리가 사용 가능해지거나 프로세스가 차단 해제되어 더 이상 자원을 기다리지 않을 때, 중기 스케줄러는 해당 프로세스를 다시 스왑 인한다.
오늘날 많은 시스템(가상 주소 공간을 스왑 파일이 아닌 보조 저장 장치에 매핑하는 것을 지원하는 시스템)에서 중기 스케줄러는 장기 스케줄러의 역할을 수행하기도 한다. 바이너리를 실행 시 '스왑 아웃된 프로세스'로 취급하여, 바이너리 세그먼트가 필요할 때 스왑 인하거나 '지연 로드'하는 방식(요구 페이징이라고도 한다)을 사용한다.
2. 3. 단기 스케줄링 (Short-term Scheduling)
CPU 스케줄러라고도 하는 단기 스케줄러는 현재 준비 상태(Ready state)에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정한다.[26] 스케줄링 결정은 클럭 인터럽트, I/O 인터럽트, 운영체제 호출 등 다양한 이벤트에 의해 발생한다.[26] 장기, 중기 스케줄러에 비해 훨씬 자주 호출되며, 매우 짧은 시간 간격으로 실행된다.[26]
단기 스케줄러는 선점형 스케줄링과 비선점형 스케줄링으로 나눌 수 있다.[26] 선점형 스케줄러는 다른 프로세스에 CPU를 할당하기로 결정했을 때 CPU에서 프로세스를 강제로 제거할 수 있지만, 비선점형 스케줄러는 CPU에서 프로세스를 강제로 제거할 수 없다.[26]
CPU 스케줄링 기능과 관련된 또 다른 구성 요소는 디스패처이다. 디스패처는 단기 스케줄러가 선택한 프로세스에 CPU 제어 권한을 부여하는 모듈이다. 디스패처의 기능은 다음과 같다.
디스패처는 프로세스를 전환할 때마다 반드시 실행되므로, 성능이 중요하다. 디스패처가 특정 프로세스를 일시 중단하고 다른 프로세스의 실행을 재개하는 데 걸리는 시간을 "디스패치 지연 시간"이라고 부른다.[7]
3. 스케줄링 알고리즘
스케줄링 알고리즘의 평가 기준은 다음과 같다.
스케줄러는 다음 목표를 가질 수 있다.
이러한 목표는 상충되는 경우가 많으므로(예: 처리량 대 지연 시간) 스케줄러는 적절한 타협점을 구현한다.
실시간 컴퓨팅 환경에서는 스케줄러가 프로세스가 데드라인을 충족할 수 있도록 해야 한다.
스케줄링 알고리즘의 종류는 다음과 같다.
| 스케줄링 알고리즘 | CPU 오버헤드 | 처리량 | 턴어라운드 시간 | 응답 시간 |
|---|---|---|---|---|
| FCFS 스케줄링 | 낮음 | 낮음 | 높음 | 낮음 |
| SJF 스케줄링 | 중간 | 높음 | 중간 | 중간 |
| 우선순위 스케줄링 | 중간 | 낮음 | 높음 | 높음 |
| 라운드 로빈 스케줄링 | 높음 | 중간 | 중간 | 높음 |
| 다단계 피드백 큐 스케줄링 | 높음 | 높음 | 중간 | 중간 |
3. 1. 비선점형 스케줄링 (Non-preemptive Scheduling)
비선점형 스케줄링(Non-preemptive Scheduling)은 어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장하는 방식이다.[39]- 장점
- 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있다.
- 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적다.
- 일괄 처리 시스템에 적합하다.
- 단점
- CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다.[39]
비선점형 스케줄링에는 다음과 같은 종류가 있다.
- FCFS 스케줄링 (First Come First Served Scheduling)
- SJF 스케줄링 (Shortest Job First Scheduling)
- HRRN 스케줄링 (Highest Response Ratio Next Scheduling)
3. 1. 1. FCFS 스케줄링 (First Come First Served Scheduling)
'''FCFS 스케줄링'''(First Come First Served Scheduling)은 '''선입 선출'''(FIFO) 방식의 스케줄링 알고리즘으로, 가장 간단한 스케줄링 방식이다. FCFS는 준비 큐에 도착하는 순서대로 프로세스를 큐에 넣고, 맨 앞에서부터 순서대로 실행한다.
- 장점
- 프로세스 종료 시에만 문맥 교환이 발생하고, 프로세스 큐 재구성이 필요하지 않아 스케줄링 오버헤드가 최소화된다.
- 모든 프로세스가 결국 완료되므로 기아 상태가 발생하지 않는다.
- 단점
- 긴 프로세스가 CPU를 점유하면 짧은 프로세스들이 오랫동안 대기하게 되어 처리량이 낮아질 수 있다. (호송 효과)
- 반환 시간, 대기 시간 및 응답 시간이 길어질 수 있다.
- 우선 순위가 없으므로 프로세스 마감 기한을 맞추기 어렵다.
3. 1. 2. SJF 스케줄링 (Shortest Job First Scheduling)
SJF 스케줄링(Shortest Job First Scheduling)은 CPU 사용 시간이 가장 짧은 프로세스를 먼저 실행하는 방식이다. 이 방식은 평균 대기 시간을 최소화할 수 있다는 장점이 있다. 하지만, CPU 사용 시간을 예측하기 어렵고, 긴 프로세스가 무한정 대기하는 기아 현상(Starvation)이 발생할 수 있다는 단점도 존재한다.[40]SJF 스케줄링은 최단 잔여 시간 우선(SRTF) 스케줄링과 유사하지만, SJF는 비선점형 방식이라는 차이점이 있다.
3. 1. 3. HRRN 스케줄링 (Highest Response Ratio Next Scheduling)
SJF 스케줄링의 기아 현상을 보완하기 위해 대기 시간과 CPU 사용 시간을 함께 고려하여 우선순위를 결정하는 방식이다.[40]3. 2. 선점형 스케줄링 (Preemptive Scheduling)
선점형 스케줄링은 CPU를 할당받은 프로세스가 실행 중이더라도 다른 프로세스가 이를 중단시키고 CPU를 강제로 점유할 수 있는 방식이다.[39] 모든 프로세스에 CPU 사용 시간을 동일하게 부여할 수 있어 빠른 응답시간을 요구하는 대화형 시분할 시스템에 적합하며, 긴급한 프로세서 제어가 가능하다. 운영 체제는 프로세서 자원을 선점하고 있다가 각 프로세스의 요청에 따라 특정 요건들을 기준으로 자원을 배분한다.[39]스케줄링 알고리즘 구현 시 고려되는 요소로는 일괄 처리 또는 대화형 여부, CPU와 입출력(I/O) 사용 비율, 우선 순위 부여 여부 및 선점 정도, 페이지 부재 정도 등이 있다.[40]
선점형 스케줄링 알고리즘에는 다음과 같은 종류가 있다:
- RR 스케줄링(Round Robin Scheduling)
- SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
- 다단계 큐 스케줄링(Multilevel Queue Scheduling)
- 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
- RM 스케줄링(Rate Monotonic Scheduling)
- EDF 스케줄링(Earliest Deadline First Scheduling)
3. 2. 1. RR 스케줄링 (Round Robin Scheduling)
RR 스케줄링은 각 프로세스에 동일한 시간 할당량(Time quantum)을 부여하고, 이 시간 할당량이 만료되면 다른 프로세스에 CPU를 넘기는 방식이다.[40] 각 프로세스에 공정하게 CPU 시간을 할당하고 응답 시간을 빠르게 하지만, 시간 할당량을 너무 작게 설정하면 잦은 문맥 교환(Context switching)으로 인한 오버헤드가 발생할 수 있다.스케줄러는 각 프로세스에 고정된 시간 단위를 할당하고 프로세스들을 순환한다. 프로세스가 해당 시간 안에 완료되면 종료되고, 그렇지 않으면 다른 모든 프로세스에 기회를 준 후에 다시 스케줄된다.
- RR 스케줄링은 특히 작은 시간 단위를 사용할 경우, 과도한 오버헤드를 발생시킨다.
- FCFS/FIFO와 SJF/SRTF 사이에서 균형 잡힌 처리량을 보이며, 짧은 작업은 FIFO보다 더 빠르게 완료되고 긴 프로세스는 SJF보다 더 빠르게 완료된다.
- 평균 응답 시간이 양호하며, 대기 시간은 프로세스 수에 따라 달라지며 평균 프로세스 길이에 의존하지 않는다.
- 대기 시간이 길기 때문에 순수한 RR 시스템에서는 마감일을 맞추기 어렵다.
- 우선 순위가 주어지지 않으므로 기아 현상은 절대 발생할 수 없다. 시간 단위 할당 순서는 FIFO와 유사하게 프로세스 도착 시간을 기준으로 한다.
- 시간 조각이 크면 FCFS/FIFO가 되고, 짧으면 SJF/SRTF가 된다.
3. 2. 2. SRTF 스케줄링 (Shortest Remaining-Time First Scheduling)
SJF 스케줄링(Shortest Job First Scheduling)을 선점형으로 확장한 방식으로, 남은 CPU 사용 시간이 가장 짧은 프로세스에 CPU를 할당한다.[40]3. 2. 3. 우선순위 스케줄링 (Priority Scheduling)
운영 체제는 모든 프로세스에 고정 우선순위 순위를 할당하고, 스케줄러는 준비 큐에 있는 프로세스를 우선순위 순으로 정렬한다. 낮은 우선순위 프로세스는 들어오는 높은 우선순위 프로세스에 의해 중단된다.[40]고정 우선순위 선점형 스케줄링(Fixed-priority pre-emptive scheduling, FPPS)은 모든 프로세스에 고정된 우선순위를 부여하고, 해당 우선순위에 따라 프로세스를 큐에 넣는다. 새롭게 높은 우선순위의 프로세스가 도착하면, 현재 실행 중이던 낮은 우선순위의 프로세스는 중단된다.
- 오버헤드는 최소도 아니고, 극단적으로 크지도 않다.
- 처리량 면에서는 FIFO 스케줄링과 큰 차이가 없다.
- 대기 시간과 응답 시간은 프로세스의 우선순위에 따라 달라진다. 높은 우선순위의 프로세스일수록 대기 시간과 응답 시간이 작아진다.
- 데드라인은 우선순위를 적절하게 설정함으로써 만족시킬 수 있다.
- 낮은 우선순위 프로세스에서는 기아 현상이 발생할 수 있다.
3. 2. 4. 다단계 큐 스케줄링 (Multilevel Queue Scheduling)
다단계 큐 스케줄링은 프로세스를 여러 그룹으로 쉽게 나눌 수 있는 상황에 사용된다. 예를 들어, 전면(대화형) 프로세스와 후면(일괄) 프로세스로 구분할 수 있다. 이 두 유형의 프로세스는 응답 시간 요구 사항이 다르므로, 다른 스케줄링 요구 사항을 가질 수 있다. 공유 메모리 문제에 매우 유용하다.[40]3. 2. 5. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
다단계 피드백 큐 스케줄링은 프로세스를 여러 그룹으로 쉽게 분류할 수 있는 경우에 사용된다. 예를 들어 포어그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스로 나누면, 각 그룹에 따라 응답 시간 요구 사항이 다르므로 스케줄링 요구 사항도 달라진다.[40]윈도우 NT/XP/Vista는 고정 우선순위 선점형 스케줄링과 라운드 로빈 스케줄링, FIFO를 결합한 다단계 피드백 큐를 채택하고 있다. 이 시스템에서는 프로세스가 지금까지 동작해 온 상황이나 기다려 온 상황에 따라 우선순위를 동적으로 조정한다. 우선순위별로 큐가 있으며, 고우선순위 큐에서는 라운드 로빈 스케줄링을, 저우선순위 큐에서는 FIFO를 채택하고 있다. 응답 시간은 대부분의 프로세스에서 짧아지고, 짧지만 중요한 프로세스는 특히 빠르게 완료된다. 고우선순위 큐는 라운드 로빈이므로 프로세스가 일정 시간 단위로만 동작하므로 기아 상태는 일어나기 어렵다.[40]
4. 운영체제별 스케줄링 알고리즘
운영 체제를 설계할 때, 프로그래머는 시스템에 가장 적합한 스케줄링 알고리즘을 고려해야 한다. 모든 경우에 적용되는 "최고"의 스케줄링 알고리즘은 없으며, 많은 운영 체제가 기존 알고리즘의 확장이나 조합을 사용한다.
대칭형 멀티프로세싱(SMP) 시스템에서는 프로세서 선호도를 고려하여 전체 성능을 향상시키려 하지만, 개별 프로세스의 속도는 느려질 수 있다. 이는 주로 캐시 스레싱을 줄여 성능을 개선하는 방식으로 이루어진다.
멀티프로세싱 환경에서는 각 프로세서를 균등하게 사용하도록 스케줄링하는 것이 일반적이다. 스케줄링은 프로세서 단위 또는 시스템 전체 단위로 수행될 수 있다. 프로세서 단위 방식은 각 프로세서마다 실행 가능한 프로세스 큐를 가지며, 시스템 전체 방식은 시스템에 유일한 실행 가능 프로세스 큐를 가진다. 시스템 전체 방식은 우선순위 역전 발생 가능성이 낮고, 프로세서 간 부하 균형을 맞추기 쉽다는 장점이 있다. 그러나 실행 효율성을 위해서는 프로세스가 동일한 프로세서에서 실행되는 것이 유리하다. (프로세서 선호도) 따라서 프로세서 단위 스케줄러를 사용하면서 부하 불균형이 심할 때만 조정하는 시스템도 있다. 시스템 전체를 단일 스케줄러로 제어하면 실행 가능 프로세스 큐 접근 시 충돌이 발생해 성능이 저하될 수 있다.
NUMA 환경에서는 SMP 시스템들이 상호 연결된다. SMP 시스템 간 프로세스 이동은 SMP 내부 이동보다 성능에 더 큰 영향을 미친다. 따라서 각 SMP 시스템에서 스케줄러를 실행하고, SMP 시스템 간 부하 균형은 별도로 조정하는 것이 일반적이다. 리눅스에서는 `exec()`를 통한 오버레이 시에 밸런스 조정을 수행하는데, 이는 `exec()`에서 프로세스의 주소 공간 내용이 변경되어 노드 간 이동에 적합한 시점이기 때문이다.
다음은 주요 운영체제별 스케줄링 알고리즘을 정리한 표이다.
| 운영 체제 | 선점 여부 | 알고리즘 |
|---|---|---|
| Amiga OS | 예 | 우선순위 라운드 로빈 스케줄링 |
| FreeBSD | 예 | 다단계 피드백 큐 |
| 리눅스 커널 2.6.0 이전 | 예 | 다단계 피드백 큐 |
| 리눅스 커널 2.6.0–2.6.23 | 예 | O(1) 스케줄러 |
| 리눅스 커널 2.6.23 이후 | 예 | 완전 공정 스케줄러 |
| 리눅스 커널 6.6 이상 | 예 | 가장 빠른 적격 가상 데드라인 우선 스케줄링 (EEVDF) |
| 클래식 Mac OS 9 이전 | 아니오 | 협력적 스케줄러 |
| Mac OS 9 | 일부 | MP 작업은 선점형, 프로세스 및 스레드는 협력적 스케줄러 |
| macOS | 예 | 다단계 피드백 큐 |
| NetBSD | 예 | 다단계 피드백 큐 |
| Solaris | 예 | 다단계 피드백 큐 |
| Windows 3.1x | 아니오 | 협력적 스케줄러 |
| Windows 95, 98, Me | 반(半) | 32비트 프로세스는 선점형, 16비트 프로세스는 협력적 스케줄러 |
| Windows NT (2000, XP, Vista, 7, 및 Server 포함) | 예 | 다단계 피드백 큐 |
다음 표는 각 운영체제별 우선순위 범위를 요약한 것이다.
| 운영체제 | 우선순위 범위 | 용도 |
|---|---|---|
| FreeBSD | 0-255 | 인터럽트, 커널, 실시간 사용자 스레드, 시분할 사용자 스레드, 유휴 사용자 스레드 |
| NetBSD | 0-223 | 시분할 스레드, 커널 공간 진입 사용자 스레드, 커널 스레드, 사용자 실시간 스레드, 소프트웨어 인터럽트 |
| 솔라리스 | 0-169 | 시분할 스레드, 시스템 스레드, 실시간 스레드, 낮은 우선순위 인터럽트 |
4. 1. Windows
초창기 MS-DOS 및 마이크로소프트 윈도우 시스템은 멀티태스킹을 지원하지 않았기 때문에 스케줄러가 없었다. Windows 3.1x는 비선점형 스케줄러를 사용했는데, 이는 프로그램들을 중단시키지 않았다는 의미이다. 윈도우는 프로그램이 종료되거나, 프로세서가 더 이상 필요 없다고 운영체제에 알려 다른 프로세스로 넘어갈 수 있도록 했다. 이것은 일반적으로 협력적 멀티태스킹이라고 불린다. Windows 95는 초보적인 선점형 스케줄러를 도입했지만, 이전 버전과의 호환성을 위해 16비트 응용 프로그램은 선점 없이 실행하도록 했다.[10]Windows NT 기반 운영 체제는 다단계 피드백 큐를 사용한다. 0부터 31까지 32개의 우선 순위 레벨이 정의되어 있다. 0에서 15까지는 '일반' 우선 순위이고, 16에서 31까지는 소프트 실시간 우선 순위이며, 할당하려면 권한이 필요하다. 0은 운영 체제를 위해 예약되어 있다. 사용자 인터페이스와 API는 프로세스의 우선 순위 클래스와 프로세스 내 스레드를 사용하며, 시스템은 이를 절대 우선 순위 레벨로 결합한다.
커널은 스레드의 I/O 및 CPU 사용량, 그리고 대화형인지 여부(예: 사람의 입력을 받아 응답하는지 여부)에 따라 스레드의 우선 순위 레벨을 변경할 수 있으며, 대화형 및 I/O 바운드 프로세스의 우선 순위를 높이고 CPU 바운드 프로세스의 우선 순위를 낮추어 대화형 응용 프로그램의 응답성을 높인다.[11] 스케줄러는 Windows Vista에서 수정되어, 간격 타이머 인터럽트 루틴을 사용하는 대신 현대 프로세서의 사이클 카운터 레지스터를 사용하여 스레드가 실제로 실행한 CPU 사이클 수를 정확하게 추적한다.[12] Vista는 또한 I/O 큐에 우선 순위 스케줄러를 사용하여 디스크 조각 모음 프로그램과 같은 프로그램이 전경 작업에 간섭하지 않도록 한다.[13]
4. 2. macOS
Mac OS 9는 여러 협동 스레드를 제어하는 하나의 프로세스를 사용하며, 멀티 프로세싱 작업에 대해 선점형 스케줄링을 제공한다.[33] 커널은 선점형 스케줄링 알고리즘을 사용하여 멀티 프로세싱 작업을 스케줄링한다. 모든 프로세스 관리자 프로세스는 '블루 태스크'라고 하는 특수한 멀티 프로세싱 태스크 내에서 실행된다. 이러한 프로세스는 라운드 로빈 스케줄링 알고리즘을 사용하여 협동적으로 스케줄링된다. 프로세스는 `WaitNextEvent`와 같은 블로킹 함수를 명시적으로 호출하여 다른 프로세스에 프로세서 제어를 양보한다. 각 프로세스는 해당 프로세스의 스레드를 협동적으로 스케줄링하는 자체 스레드 관리자 사본을 가지고 있다. 스레드는 `YieldToAnyThread` 또는 `YieldToThread`를 호출하여 다른 스레드에 프로세서 제어를 양보한다.macOS는 스레드에 대해 일반, 시스템 높은 우선순위, 커널 모드 전용, 실시간의 네 가지 우선순위 밴드를 가진 다단계 피드백 큐를 사용한다.[33] 스레드는 선점형으로 스케줄링된다. macOS는 또한 Carbon의 스레드 관리자 구현에서 협동적으로 스케줄링된 스레드를 지원한다.
4. 3. Linux
리눅스 2.4 버전에서는 0부터 140까지의 우선순위 레벨을 가진 멀티레벨 피드백 큐를 사용하는 O(n) 스케줄러가 사용되었다.[17] 0~99는 실시간 작업용, 100~140은 nice 작업 레벨로 간주되었다. 실시간 작업의 경우 프로세스 전환에 대한 시간 할당량은 약 200ms였고, nice 작업의 경우 약 10ms였다. 스케줄러는 준비된 모든 프로세스의 실행 큐를 순회하며, 가장 높은 우선순위의 프로세스가 먼저 실행되어 시간 조각을 실행하도록 한 다음 만료된 큐에 배치했다. 활성 큐가 비어 있으면 만료된 큐가 활성 큐가 되고 그 반대로도 작동했다.일부 기업용 리눅스 배포판인 SUSE Linux Enterprise Server는 앨런 콕스가 Linux 2.4-ac 커널 시리즈에서 유지 관리한 O(1) 스케줄러의 백포트를 리눅스 2.4 커널에 적용했다.
2.6.0부터 2.6.22 버전까지 커널은 리눅스 2.5 개발 과정에서 잉고 몰나르를 비롯한 여러 커널 개발자들이 개발한 O(1) 스케줄러를 사용했다. 이 기간 동안 콘 콜리바스는 스케줄러의 상호 작용성을 개선하거나 자신의 스케줄러로 대체하는 패치 세트를 개발했다.
콘 콜리바스의 작업, 특히 공정 스케줄링의 구현인 Rotating Staircase Deadline(RSDL)는 잉고 몰나르가 이전 O(1) 스케줄러를 대체하기 위해 완전 공정 스케줄러(CFS)를 개발하는 데 영감을 주었으며, 발표에서 Kolivas의 공로를 인정했다.[18] CFS는 범용 운영 체제에서 널리 사용되는 공정 대기열 프로세스 스케줄러의 첫 번째 구현이다.[19]
CFS는 원래 패킷 네트워크를 위해 발명된 공정 대기열이라는 잘 연구된 고전적인 스케줄링 알고리즘을 사용한다. 공정 대기열은 이전에 스트라이드 스케줄링이라는 이름으로 CPU 스케줄링에 적용되었다. CFS 스케줄러는 O(log N)의 스케줄링 복잡성을 가지며, 여기서 N은 runqueue에 있는 작업의 수이다. 작업을 선택하는 데는 상수 시간이 걸리지만, 실행 후 작업을 다시 삽입하려면 실행 큐가 레드-블랙 트리로 구현되어 있기 때문에 O(log N) 연산이 필요하다.
4. 4. 기타 운영체제
FreeBSD는 0~255 우선순위를 가진 다단계 피드백 큐를 사용한다. 각 우선순위 범위별 용도는 다음과 같다.- 0~63: 인터럽트
- 64~127: 커널 상위 절반
- 128~159: 실시간 사용자 스레드
- 160~223: 시분할 사용자 스레드
- 224~255: 유휴 사용자 스레드
리눅스와 마찬가지로 활성 큐 설정을 사용하지만, 유휴 큐도 가지고 있다.[23][37]
NetBSD는 0–223 범위의 우선순위를 가진 다단계 피드백 큐를 사용하며, 각 범위별 용도는 다음과 같다.
- 0–63: 시분할 스레드 (기본값, SCHED_OTHER 정책)
- 64–95: 커널 공간에 진입한 사용자 스레드
- 96–128: 커널 스레드
- 128–191: 사용자 실시간 스레드 (SCHED_FIFO 및 SCHED_RR 정책)
- 192–223: 소프트웨어 인터럽트
솔라리스는 0에서 169까지의 우선순위를 가진 다단계 피드백 큐를 사용한다. 각 우선순위 범위별 용도는 다음과 같다.
- 0–59: 시분할 스레드
- 60–99: 시스템 스레드
- 100–159: 실시간 스레드
- 160–169: 낮은 우선순위 인터럽트
리눅스와 달리,[23] 프로세스가 시간 할당량을 다 사용하면 새로운 우선순위가 부여되고 큐에 다시 배치된다. 솔라리스 9는 고정 우선순위 클래스와 공정 공유 클래스라는 두 개의 새로운 스케줄링 클래스를 도입했다. 고정 우선순위 스레드는 시분할 클래스와 동일한 우선순위 범위를 가지지만, 우선순위가 동적으로 조정되지 않는다. 공정 스케줄링 클래스는 CPU ''몫''을 사용하여 스케줄링 결정에 대한 스레드의 우선순위를 정한다. CPU 몫은 CPU 자원에 대한 권한을 나타낸다. 이는 프로젝트로 통칭되는 프로세스 집합에 할당된다.[7]
각 운영체제별 우선순위 범위는 다음과 같이 요약할 수 있다.
| 운영체제 | 우선순위 범위 | 용도 |
|---|---|---|
| FreeBSD | 0-255 | 인터럽트, 커널, 실시간 사용자 스레드, 시분할 사용자 스레드, 유휴 사용자 스레드 |
| NetBSD | 0-223 | 시분할 스레드, 커널 공간 진입 사용자 스레드, 커널 스레드, 사용자 실시간 스레드, 소프트웨어 인터럽트 |
| 솔라리스 | 0-169 | 시분할 스레드, 시스템 스레드, 실시간 스레드, 낮은 우선순위 인터럽트 |
참조
[1]
논문
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
ACM
1973-01
[2]
서적
Queueing Systems, Vol. 2: Computer Applications
https://archive.org/[...]
Wiley-Interscience
[3]
서적
Workload Modeling for Computer Systems Performance Evaluation
http://www.cs.huji.a[...]
Cambridge University Press
2015-10-17
[4]
서적
Operating System Concepts
Wiley Publishing
[5]
웹사이트
Process Scheduling: Who gets to run next?
https://www.cs.rutge[...]
2023-06-19
[6]
서적
An Operating Systems Vade Mecum
https://www.yumpu.co[...]
Prentice Hall
1988
[7]
서적
Operating System Concepts
John Wiley & Sons, Inc.
[8]
간행물
Admission Control for Independently-authored Realtime Applications
https://citeseerx.is[...]
UWSpace
2004
[9]
서적
Fundamentals of Mobile Data Networks
Cambridge University Press
[10]
웹사이트
Early Windows
https://web.archive.[...]
'*'
[11]
웹사이트
A Tale of Two Schedulers Windows NT and Windows CE
http://sriramk.com/s[...]
[12]
웹사이트
Windows Administration: Inside the Windows Vista Kernel: Part 1
https://technet.micr[...]
2016-12-09
[13]
웹사이트
Archived copy
http://blog.gabefros[...]
2022-01-15
[14]
웹사이트
Technical Note TN2028: Threading Architectures
https://developer.ap[...]
2019-01-15
[15]
웹사이트
Mach Scheduling and Thread Interfaces
https://developer.ap[...]
2019-01-15
[16]
웹사이트
http://www.ibm.com/d[...]
[17]
웹사이트
Inside the Linux 2.6 Completely Fair Scheduler
https://developer.ib[...]
2024-02-07
[18]
간행물
"[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]"
https://lwn.net/Arti[...]
2007-04-13
[19]
웹사이트
Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin
http://happyli.org/t[...]
2016-12-09
[20]
웹사이트
EEVDF Scheduler May Be Ready For Landing With Linux 6.6
https://www.phoronix[...]
2023-08-31
[21]
웹사이트
EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced
https://www.phoronix[...]
2024-02-07
[22]
웹사이트
An EEVDF CPU scheduler for Linux [LWN.net]
https://lwn.net/Arti[...]
2023-08-31
[23]
웹사이트
Comparison of Solaris, Linux, and FreeBSD Kernels
http://cn.opensolari[...]
[24]
문서
Stallings
[25]
문서
Stallings
[26]
문서
Stallings
[27]
웹사이트
block: remove legacy IO schedulers
https://git.kernel.o[...]
2018-10-12
[28]
웹사이트
BFQ (Budget Fair Queueing)
https://www.kernel.o[...]
[29]
웹사이트
Deadline IO scheduler tunables
https://www.kernel.o[...]
[30]
웹사이트
Early Windows
https://web.archive.[...]
[31]
웹사이트
A Tale of Two Schedulers Windows NT and Windows CE
http://sriramk.com/s[...]
[32]
문서
Inside the Windows Vista Kernel: Part 1
http://technet.micro[...]
Microsoft Technet
[33]
웹사이트
Mach Scheduling and Thread Interfaces
http://developer.app[...]
[34]
웹사이트
CPU monitoring and tuning
http://www.ibm.com/d[...]
[35]
간행물
"[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]"
http://lwn.net/Artic[...]
2007-04-13
[36]
논문
Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin
http://happyli.org/t[...]
[37]
웹사이트
Comparison of Solaris, Linux, and FreeBSD Kernels
http://cn.opensolari[...]
2012-07-19
[38]
웹사이트
Real-Time Scheduler Scheduling Classes
https://docs.oracle.[...]
Oracle
2019-04
[39]
서적
운영 체제
정익사
[40]
서적
운영 체제
정익사
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com