CPU 스케줄링

CPU 스케줄링의 기본 개념

---

다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행중인 프로세스를 가지게 하는데 있습니다. 어떤 프로세스가 대기해야할 경우 운영체제는 CPU를 해당 프로세스로부터 회수하여 다른 프로세스에게 할당합니다. 이렇게 CPU 이용률을 최대화하는 것이 다중 프로세서 운영체제의 핵심입니다.

 

💡 CPU-I/O 버스트 사이클이란?

 

• 프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성됩니다. 프로세스들은 이 두 상태 사이를 교대로 왔다 갔다 합니다.
• 프로세스 실행은 CPU 버스트로 시작됩니다. 뒤이어 I/O 버스트가 발생하고, 그 뒤를 이어 또 다른 CPU 버스트가 발생하며, 이어 또 다른 I/O 버스트 등으로 진행됩니다. 결국 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신 실행을 종료하기 위한 시스템 요청과 함께 끝나게 됩니다.
• 조금 더 쉽게 설명을 하면 CPU를 사용하다가 I/O 요청으로 인해 대기하다가, 다시 작업하고, 다시 쉬고를 반복하는 것입니다. 프로세스가 CPU를 사용할 때 CPU 버스트라 하고, I/O 작업을 기다릴 때 I/O 버스트라 합니다.

 

💡 CPU 스케줄러란?

 

• CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중 적절한 프로세스를 선택하여 실행합니다. 이때 선택 절차는 CPU 스케줄러에 의해 수행됩니다.
• 스케줄러는 실행 준비가 되어 있는 프로세스들 중 하나를 선택하여 CPU를 할당하게 됩니다.
• 준비 큐에 있는 모든 프로세스는 CPU에 의해 실행되길 기다리고 있으며, 준비 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB) 입니다.

 

💡 선점 및 비선점 스케줄링

 

• CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있습니다.

상황

 

1. 한 프로세스가 실행 상태에서 대기 상태로 전환된 경우(비밀번호 입력 요구 등)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환된 경우(인터럽트 발생)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환된 경우(비밀번호 입력 완료 이벤트)
4. 프로세스가 종료할 때

비선점 스케줄링이란?

 

• CPU가 한 프로세스에게 할당되면 해당 프로세스가 종료하든지, 대기 상태로 전환되어 CPU를 방출하든지 할 때까지 점유하게 됩니다.

선점 스케줄링이란?

 

• 한 프로세스가 CPU를 할당 받아서 실행하고 있을 때 다른 프로세스가 CPU를 사용하고 있는 프로세스를 중지한 뒤 CPU를 차지할 수 있는 기법입니다.
• Windows, macOs, Linux 및 Unix를 포함하여 거의 모든 최신 운영체제들은 선점 스케줄링 기법을 사용합니다.
• 선점 스케줄링 기법은 데이터가 다수의 프로세스들에 의해 공유될 때 race-condition이 발생할 수 있습니다. 그렇기 때문에 이를 방지하기 위해 mutex 락과 같은 기법이 필요합니다. 

 

💡 디스패처란?

 

• CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처입니다.
• 디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에게 주는 모듈입니다.
• 디스패처는 모든 프로세스의 context-switch 시 호출되므로, 가능한 빨리 수행되어야 합니다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연이라합니다. 

자발적 context-switch란?

 

• 프로세스가 비밀번호 입력 등 I/O 작업으로 인해 대기 상태가 되었을 때 발생합니다.
• 프로세스가 종료되었을 때 발생합니다.

비자발적 context-switch란?

 

• 타임 슬라이스가 만료되었거나, 우선 순위가 더 높은 프로세스에 의해 CPU를 빼앗겼을 때 발생합니다.

 

스케줄링 기준

---

💡 CPU 이용률

 

• 우리는 가능한 CPU를 최대한 바쁘게 유지하길 원합니다. 개념상으로는 0에서 100% 까지 있습니다. 
• Linux, macOs, Unix 시스템에서 top 명령어를 통해 CPU 이용율을 얻을 수 있습니다.

💡 처리량

 

• 단위 시간당 완료된 프로세스의 개수로, 처리량이라 합니다.

💡 총 처리 시간

 

• 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라 합니다.
• 총 처리 시간은 준비 큐에서 대기한 시간, CPU에서 실행한 시간, I/O 시간을 합한 시간입니다.

💡 대기 시간

 

• 대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합입니다.

💡 응답 시간

 

• 하나의 요청을 보낸 후 첫 번째 응답이 나올 때까지의 시간입니다.
• 응답 시간이라고 하는 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는데 걸리는 시간이 아닙니다.
• 응답 시간 = 총 처리 시간 - 결과가 나오는 시간 으로 구할 수 있습니다.

 

스케줄링 알고리즘

---

💡 선입 선처리 스케줄링

 

• 선입 선처리 스케줄링은 CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받는 것입니다.
• 선입선출 큐로 쉽게 관리할 수 있습니다. 프로세스가 준비 큐에 진입하면 해당 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결합니다. 그리고 CPU가 가용 상태가 되면 준비 큐의 앞 부분에 있는 프로세스에 할당됩니다. 그리고 프로세스가 실행되면 준비 큐에서 제거됩니다.

위와 같은 프로세스가 있을 경우 평균 대기 시간은 어떻게 될까?

(0 + 10 + 28 + 6 + 4 + 14) / 5 = 12초 입니다.

 

장점

 

• 스케줄링 이해와 구현이 단순합니다.
• 준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 없는 공정한 정책입니다.

단점

 

• 비선점 방식이므로 대화식 프로세스에는 부적합 합니다.
• 장기 실행 프로세스가 있다면 뒤에 있는 프로세스를 대기시켜야 하므로, 평균 대기 시간이 길어지게 됩니다.
• CPU 사용 시간이 긴 프로세스에 의해 사용 시간이 짧은 프로세스들이 오래 기다리는 현상으로 호위 효과가 발생할 수 있습니다.

 

💡 최단 작업 우선 스케줄링

 

• 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킵니다. CPU가 가용 상태가 되면 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당합니다. 만약 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가진다면 우선 순위를 정하기 위해 선입 선처리 스케줄링을 적용합니다. 
• 이 스케줄링은 프로세스의 전체 길이가 아닌 다음 CPU 버스트의 길이에 의해 스케줄링 되기 때문에 최단 다음 CPU 버스트라고도 합니다.

위와 같은 프로세스가 있을 경우 평균 대기 시간은 어떻게 될까?

(0 + 34 + 14 + 10 + 20) / 5 = 15.6초 입니다.

 

장점

 

• 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기 시간이 짧습니다.

단점

 

• 긴 CPU 버스트를 가진 프로세스들은 짧은 CPU 버스트를 가진 프로세스들이 종료되어야 실행될 수 있으므로 기아상태가 발생하게 됩니다.
• 기본적으로 짧은 CPU 버스트를 가진 프로세스들이 우선적으로 실행되므로 불공정합니다.
• 실행 시간을 예측하기 어려워 실용적이지 못합니다.

 

💡 라운드 로빈 스케줄링

 

• 라운드 로빈 스케줄링이란 시분할 시스템을 위해 설계된 선점형 스케줄링입니다. 프로세스들 사이에 우선 순위를 두지 않고, 순서대로 시간 단위로 CPU를 할당하는 방식입니다.
• CPU 자원을 사용할 수 있는 기회를 프로세스에게 공평하게 제공하기 위한 방법으로 각 프로세스에게 일정시간을 할당하고, 프로세스의 CPU 버스트가 시간 할당량보다 작은 경우에는 CPU를 자발적으로 방출합니다. 하지만 프로세스의 CPU 버스트가 시간 할당량보다 큰 경우 그 프로세스는 context-switch에 의해 다시 준비 큐의 마지막에 넣어집니다. 그리고 CPU 스케줄러는 다음 프로세스에게 기회를 부여하게 됩니다.
• RR은 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당 받는 프로세스는 없습니다.

장점

 

• CPU를 독점적으로 사용하지 않고 공평하게 사용합니다.
• 대화식 프로세스에 적합합니다.

단점

 

• 시간 할당량이 너무 작으면 context-switch에 따른 오버헤드가 크게 증가합니다.
• 시간 할당량이 너무 크면 선입 선출 스케줄링과 같아집니다.

 

💡 우선순위 스케줄링

 

• 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당되게 됩니다. 만약 우선순위가 같다면 선입 선처리 스케줄링에 의해 처리 됩니다.
• 0이 높은 우선순위인가 낮은 우선순위인가에 대해서 일반적인 합의는 없습니다. 시스템 마다 다릅니다.

 

우선순위 결정 방법

 

• 우선순위는 내부적, 외부적으로 결정될 수 있습니다.
• 내부적 우선순위는 제한 시간, 메모리 요구, 열린 파일의 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율이 계산에 사용됩니다.
• 외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형, 작업을 지원하는 부서, 정치적인 요인에 의해 결정됩니다.

선점과 비선점

 

• 우선순위 스케줄링은 선점형이거나 비선점형이 될 수 있습니다.
• 선점형 우선순위는 프로세스가 준비 큐에 도착하면 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교하여, 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점합니다.
• 비선점형 우선순위는 단순히 준비 큐에 새로운 프로세스를 삽입하게 됩니다.

 

장점

 

• 프로세스마다 상대적 중요성을 정의할 수 있습니다.

단점

 

• 무한 봉쇄 또는 기아 상태가 발생할 수 있습니다. 만약 계속하여 높은 우선순위를 가진 프로세스가 들어오게 된다면 그보다 낮은 프로세스는 무한정 기다리게 됩니다.
• 낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대해 해결방법은 노화입니다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킵니다.

 

💡 다단계 큐 스케줄링

 

• 우선순위마다 준비 큐를 형성해 놓는 방식입니다.
• 각 큐는 별도의 스케줄링 알고리즘을 가지고 있으며, 큐 사이에도 스케줄링이 존재합니다.
• 각 큐는 절대적인 우선순위를 가지며, 우선순위가 높은 큐에 존재하는 프로세스부터 실행되며, 우선 순위가 높은 큐들이 모두 비어있지 않으면 다음 우선순위의 준비 큐를 실행할 수 없습니다.
• 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당하게 됩니다. 그리고 해당 프로세스들은 한 큐에서 다른 큐로 이동하지 않습니다. 이렇게 큐들 간의 프로세스 이동이 불가능하기 때문에 오버헤드가 적지만 유연성이 떨어지게 됩니다.
• 우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수 있습니다.

우선순위 마다 별도 큐 유지

💡 다단계 피드백 큐 스케줄링

 

• 다단계 큐 스케줄링과 마찬가지로 여러개의 준비 큐를 사용합니다.
• 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 삽입됩니다. 해당 프로세스는 선입 선출 순서로 CPU를 할당받아 실행됩니다. 그리고 해당 큐의 CPU 시간 할당량이 끝나면 한 단계 아래 큐로 삽입됩니다.
• 단계가 내려갈수록 시간 할당량이 증가합니다.
• 프로세스는 큐 사이에 이동이 가능하며, 어떤 프로세스가 CPU 시간을 많이 소비하면 낮은 우선순위 큐로 이동하고, I/O 중심의 프로세스는 높은 우선순위 큐로 이동하게 됩니다.
• 가장 아래의 큐에 담긴 프로세스들은 기아 상태를 방지하기 위해 점차 높은 우선순위를 가지는 큐로 이동할 수 있습니다.

 

스레드 스케줄링

---

대부분의 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아닌 커널 수준 스레드입니다. 사용자 수준 스레드는 사용자 모드에서 스레드 라이브러리에 의해 생성 및 관리되고 커널은 사용자 수준 스레드의 존재를 모릅니다. 

사용자 수준의 스레드가 CPU 상에서 실행되기 위해 경량 프로세스를 통해 간접적인 방식이라도 커널 수준 스레드에 매칭되어야 합니다.

 

💡 프로세스 경쟁 범위(Process Contention Scope)

 

• 다대일, 다대다 모델을 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 이용 가능한 LWP에 스케줄링합니다.
• 프로세스 경쟁 범위는 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위라 합니다.

 

💡 시스템 경쟁 범위(System Contention Scope)

 

• 스레드 라이브러리가 사용자 수준 스레드를 이용 가능한 LWP에 스케줄링 한다고 할 때, 스레드가 실제로 CPU 상태에서 실행 중이라는 것을 의미하지 않습니다. 이때 실제로 CPU 상에서 실행되기 위해서는 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 합니다.
• CPU 상에서 어느 커널 스레드를 스케줄 할 것인지 정하기 위해 커널은 시스템 경쟁 범위를 사용합니다.
• 시스템 경쟁 범위는 시스템상의 모든 스레드 사이에서 일어납니다. Windows, Linuxd와 같은 일대일 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케줄합니다.

 

다중 처리기 스케줄링

---

다중 처리기 스케줄링이란 여러 개의 CPU가 있는 다중 처리기 시스템입니다.

 

💡 비대칭 다중 처리

 

• 비대칭 다중 처리는 마스터 서버의 역할을 수행하는 하나의 처리리가 모든 스케줄링과 관련된 결정, 입출력 처리, 여타 활동을 취급합니다. 다른 처리기들은 사용자 코드만 수행합니다.
• 마스터 서버의 역할을 수행하는 하나의 처리리가 시스템 자료구조에 접근하기 때문에 다른 처리기 간의 커널 내 자료를 공유할 필요가 없습니다.
• 비대칭 다중 처리의 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 발생할 수 있습니다.

💡 대칭 다중 처리

 

• 대칭 다중 처리는 각 프로세서에서는 스스로 스케줄링할 수 있습니다.
• 각 프로세서의 스케줄러가 준비 큐를 검사하고, 실행할 스레드를 선택하여 스케줄링이 진행됩니다.
• 모든 프로세스가 공동의 준비 큐에 있기도 하지만, 각 처리기마다 가지고 있는 프라이빗 준비 큐도 있습니다.
• 공유 준비 큐에 race-condition이 발생할 수 있으므로 두 개의 다른 프로세서가 동일한 스레드를 스케줄하지 않도록 그리고 큐에서 스레드가 없어지지 않도록 보장해야 합니다.
• 프라이빗 큐에서는 각 프로세서가 자신만의 실행 큐에서 스레드를 스케줄할 수 있도록 허용하므로 공유 준비 큐에서 발생하는 문제점이 발생하지 않습니다. 또한 자신만의 큐가 있으므로 캐시 메모리를 보다 효율적으로 사용할 수 있습니다.

💡 다중 코어 프로세서

 

다중 코어란

 

• 하나의 프로세서 칩에 여러개의 코어를 장착합니다. 각 코어는 구조적인 상태를 유지하고 있어 운영체제 입장에서는 개별적인 논리적 CPU 처럼 보이게 됩니다.
• CPU 각각이 프로세서 칩을 하나씩 가지는 시스템보다 속도도 빠리고 적은 전력을 소모합니다.

메모리 멈춤(Memory Stall)이란

 

• 캐시 미스등의 원인으로 인해 프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 발생하는 대기 시간입니다.

하드웨어 스레드란

 

• 메모리 멈춤 문제를 해결하기 위해 하나의 코어에 2개 이상의 스레드를 할당하는 것입니다.
• 한 스레드가 메모리 멈춤에 의해 메모리를 기다리면서 멈추면, 코어는 다른 스레드로 전환이 가능합니다. 그렇기 때문에 메모리 멈춤 현상이 발생하면 코어는 작업 스레드를 다른 스레드로 전환하여 작업을 진행합니다. 이러한 스레드는 하드웨어적으로 구현됩니다. 

거친 다중 스레딩이란

 

• 거친 다중 스레딩에서 스레드가 메모리 멈춤과 같은 긴 지연시간을 발생시킬 때까지 한 처리기에서 수행됩니다. 그러다가 메모리 멈춤이 발생하면 다른 스레드로 전환됩니다. 이때 다른 스레드로 전환될 때 기존 스레드의 명령어 파이프 라인이 완전히 정리되어야 하므로 스레드 간 교환 비용이 많이 듭니다. 

세밀한 다중 스레딩이란

 

• 세밀한 다중 스레딩은 보통 명렁어 주기의 경계에서 스레드 교환이 일어납니다. 스레드 교환을 위한 회로적 지원이 필요히자만 교환 비용은 감소합니다.

부하 균등화란

 

• 부하 균등화란 처리기 사이에 부하가 균등하게 배분되도록 하는 것입니다. pull migration과 push migration 접근법이 있습니다.
• 부하 균등화는 각 처리기가 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능입니다. 공통 준비 큐가 있는 시스템에서는 한 처리기가 쉬게 되면 곧바로 공통 준비 큐에서 새로운 프로세스를 선택하여 실행하기때문에 부하 균등화가 필요하지 않습니다.
• push migration
  
  • 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 상대적으로 덜 바쁜 처리기로 스레드를 이동시킴으로써 부하를 배분합니다.
• pull migration
  • 쉬고 있는 처리리가 바쁜 처리기의 처리를 기다리고 있는 프로세스를 가져옵니다. 즉 pull 합니다.

처리기 선호도란

 

• 예를들어 부하 균등화로 인해 스레드가 다른 처리기로 이주한다면 어떤일이 발생할까? 그에 대한 답은 기존에 머물러 있던 처리기의 캐시 내용은 필요가 없어지므로 무효화해야 합니다. 그리고 이주하고자 하는 처리기에 다시 채시를 채워야 합니다. 캐시 무효화 및 다시 채우는 비용은 많이 들기 때문에 대부분의 운영체제에서는 스레드를 한 처리기에서 다른 처리기로 이주시키지 않고 대신 같은 처리기에서 계속 실행시키면서 warm cache를 이용하려고 합니다.
• 공통 준비 큐를 사용하면 스레드는 어느 처리기에서건 실행될 수 있습니다. 따라서 스레드가 새 프로세서에 스케줄되면 해당 프로세서의 캐시를 무효화 및 다시 채우는 비용이 듭니다. 하지만 자신만의 큐를 사용하게 된다면 스레드는 항상 동일한 프로세서에 스케줄 되므로 warm cache의 내용을 사용할 수 있습니다.

 

실시간 CPU 스케줄링

---

프로세스의 deadLine을 고려하여 스케줄링하는 알고리즘입니다. 여기에는 연성 실시간 시스템과 경성 실시간 시스템이 있습니다.

 

연성 실시간 시스템이란

 

• deadLine을 만족하는 것을 보장하지 않습니다.
• 중요한 프로세스가 그렇지 않은 프로세스들에 비해 우선권만 가지고 있습니다.

경성 실시간 시스템이란

 

• deadLine을 100% 만족하는 것을 보장합니다.
• deadLine을 못 맞추는 것은 치명적이여서 못 맞출바에는 차라리 스케줄링을 안하는게 더 나은 시스템입니다.

 

💡 지연시간 최소화

 

• 실시간 시스템의 이벤트 중심의 특성을 보면 시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다립니다. 이벤트가 발생하면 시스템은 가능한 빨리 응답을 하고 그에 맞는 동작을 수행해야 합니다.

지연시간

 

• 지연시간이란 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 말합니다. 여기에는 인터럽트 지연시간과 디스패치 지연시간으로 나누어 집니다.

 

인터럽트 지연시간

 

• 인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말합니다.
• 인터럽트가 발생하면 운영체제는 우선 수행중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정합니다.
• 인터럽트 서비스 루틴을 사용하여 해당 인터럽트를 처리하기 전에 현재 수행중인 프로세스의 상태를 저장합니다.
• 실시간 태스크가 즉시 수행될 수 있도록 인터럽트 지연시간을 최소화하는게 실시간 운영체제에서 중요합니다.

 

디스패치 지연시간

 

• 디스패치 지연시간은 스케줄링 디스패치가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간입니다.
• 디스패치 지연시간을 최소화하는 가장 효과적인 방법은 선점형 커널입니다.
• 디스패치 단계는 우선순위가 높은 프로세스를 사용 가능한 CPU에 스케줄합니다.
• 충돌 단계
  • 커널에서 동작하는 프로세스에 대한 선점
  • 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출

💡 우선순위 기반 스케줄링

 

• 우선순위 기반의 스케줄링 알고리즘은 각각의 프로세스의 중요성에 따라 그 우선순위를 부여합니다.
• 스케줄러가 선점 기법을 제공하면 현재 CPU를 이용하고 있는 프로세스가 더 높은 우선순위를 갖는 프로세스에 선점될 수 있습니다.

 

💡 Rate Monotonic 스케줄링

 

• Rate Monotonic 스케줄링은 주기에 따라 우선순위가 정해집니다.
• 주기가 짧을수록 우선순위가 높아지고, 주기가 길면 낮은 우선순위를 가집니다. 즉 CPU를 더 자주 필요로하는 태스크에게 더 높은 우선순위를 할당합니다.
• 선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄합니다. 낮은 우선순위의 프로세스가 실행중이고 높은 우선순위의 프로세스가 실행 준비가 되면, 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 선점합니다.

 

💡 Eariest-Deadline-First 스케줄링

 

• 마감시간에 따라서 우선순위를 동적으로 부여합니다. 
• 마감시간이 빠를수록 우선순위는 높아지고, 낮을수록 낮아집니다.
• 프로세스가 실행가능하게 되면 자신의 마감시간을 시스템에게 알려줘야 합니다. 시스템은 실행 가능하게 된 프로세스의 마감시간에 맞춰 다시 조정됩니다.

 

💡 일정 비율의 몫 스케줄링

 

• 스케줄러는 모든 응용들에게 T개의 시간 몫을 할당하여 동작합니다.
• 한 개의 응용이 N개의 시간 몫을 할당받으면 그 응용은 모든 프로세스 시간 중 T/N 시간을 할당받습니다.
• 일정 비율의 몫 스케줄러는 응용이 시간 몫을 할당받는 것을 보장하는 승인 제어 정책과 함께 동작해야 합니다.
• 승인 제어 정책은 사용 가능한 충분한 몫이 존재할 때, 그 범위 내의 몫을 요구하는 클라이언트에게만 실행을 허락합니다.
• 예를들어 A: 50, B: 15, C: 20 총 85개의 몫이 할당되어 있는 상태에서 새로운 프로세스 D가 30 몫을 요구한다면 승인 컨트롤러는 D의 진입을 거부합니다.

 

 

 

참고자료

• https://jwprogramming.tistory.com/17