[OS] CPU 스케줄링

CPU 스케줄링은 Ready 상태의 프로세스 중 다음에 실행할 프로세스를 결정하는 정책을 의미한다.

---

주요 개념

• Workload (작업 부하): 작업 설명의 집합. 예를 들어 도착 시간, 실행 시간 등이 포함된다.
• Scheduler (스케줄러): 언제 어떤 작업이 실행될지 결정하는 논리.
• Metric (평가 지표): 스케줄링 품질을 측정하는 기준.

 

평가 지표의 종류

1. Turnaround Time: $ T_\text{complete} - T_\text{arrival} $
2. Response Time: $ T_\text{firstrun} - T_\text{arrival} $
3. Waiting Time: Ready 상태에서 실행되기까지 기다리는 시간.
4. Throughput: 시간 단위당 완료되는 작업 수.
5. Resource Utilization: 비싼 장치들이 얼마나 바쁘게 유지되는지.
6. Overhead: 컨텍스트 스위치 횟수.
7. Fairness: 작업들이 공평하게 CPU를 점유하는지.

Turnaround Time과 Response Time이 주로 사용된다.

---

스케줄러의 초기 가정

1. 모든 작업은 동일한 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 한 번 시작되면, 각 작업은 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다. (입출력 없음)
5. 각 작업의 실행 시간은 고정되어 알려져 있다.

---

FIFO (First In, First Out)

• 작업은 도착한 순서대로 스케줄링 된다.
• 비선점형: 한 번 시작된 작업은 완료될 때까지 계속 실행된다.
• 모든 작업이 동등하게 취급되므로 기아 상태(Starvation)가 발생하지 않는다.

 

콘보이 효과 (Convoy Effect)

실행 시간이 짧은 작업이 실행 시간이 긴 작업 뒤에서 기다리면 평균 Turnaround Time이 커질 수 있다.

• 고속도로에서 느린 트럭 한 대가 전체 도로 흐름을 느리게 하는 상황에 비유 할 수 있다.

---

SJF (Shortest Job First)

• 가정 1 해제: 각 작업은 가변적인 실행 시간을 가진다.
• 가장 짧은 실행 시간을 가진 작업을 실행한다.
• 비선점형: 한 번 시작된 작업은 완료될 때까지 계속 실행된다.

 

FIFO vs SJF

 

기아 상태 (Starvation)

높은 우선순위의 작업이 계속 들어오면, 낮은 우선순위 작업은 실행되지 않고 무기한 대기 상태에 빠질 수 있다.

• SJF에서는 실행 시간이 긴 작업이 기아 상태에 빠질 가능성이 있다.

---

STCF (Shortest Time-to-Completion First)

• 가정 2 해제: 작업이 동시에 도착하지 않는다.
• 가정 3 해제: 새로운 작업이 도착했을 때, 그 작업의 실행 시간이 현재 작업의 남은 시간보다 짧으면 선점한다.
• 선점형 스케줄러이다.

 

선점형 · 비선점형 스케줄링

선점형 스케줄링

• 스케줄러가 작업을 중단하고 컨텍스트 스위치를 강제로 수행할 수 있다 .
  • 예: STCF.

비선점형 스케줄링

• 이전 작업이 CPU를 자발적으로 해제할 때만 새 작업이 스케줄링된다.
  
  • I/O 작업 수행
  • yield 호출
  • 작업 완료
• FIFO와 SJF는 비선점형 스케줄링이다.

 

SJF vs STCF

STCF는 선점형 스케줄러이기에 SJF보다 더 효율적이다.

---

RR (Round Robin)

• 실행 큐는 순환 FIFO 큐로 처리된다.
• 각 작업에 Time Slice가 배정된다.
  • 작업을 Time Slice 동안 실행한 다음, 실행 큐의 다음 작업으로 컨텍스트 스위치한다.
• 선점형 스케줄링이다.
• 기아 상태가 발생하지 않는다.

 

SJF vs RR

RR는 Response Time 지표를 SJF보다 크게 개선 시킬 수 있다.

그러나 일반적으로 SJF보다 저 높은 Turnaround Time을 가지기에, RR는 시간 분할 시스템에서 주로 사용된다.

---

정적 우선 순위 스케줄링

• 각 작업은 정적인 우선 순위를 갖는다.
• 다음 실행할 작업은 가장 높은 우선순위를 가진 작업이다.
  • 동일한 우선 순위 내에서는 RR 또는 FIFO를 사용한다.
• 선점형과 비선점형 모두 사용 가능하다.
• 기아 상태 발생 가능: 높은 우선순위 작업이 계속 공급되면, 낮은 우선순위 작업이 실행되지 않을 수 있다.

---

I/O 작업을 고려한 스케줄링

• 가정 4 해제: I/O 작업이 존재한다.
• I/O 장치가 특정 작업을 위한 입출력을 수행하는 동안 CPU는 다른 작업을 실행한다.
• 시스템의 자원을 보다 효율적으로 사용할 수 있다.

---

MLFQ (Multi-Level Feedback Queue)

• 각 우선순위 레벨에 대해 여러 개의 개별적인 큐가 존재한다.
• 큐 간에는 정적 우선순위 스케줄링이 이루어지며, 같은 큐 내에서는 Round Robin (RR) 방식이 적용된다.
• 가정 5 해제: 작업별 CPU 사용량과 시간에 대한 사전 지식이 필요하지 않다.

규칙 1: 만약 $Priority_A > Priority_B$라면, $A$가 실행되고 $B$는 실행되지 않는다.
규칙 2: 만약 $Priority_A = Priority_B$라면, $A$와 $B$가 RR 방식으로 실행된다.

 

일반적인 작업 부하

• Interactive jobs: 실행 시간이 짧고 빠른 반응 시간이 필요하다.
• CPU-intensive jobs: 많은 CPU 시간이 필요하며 반응 시간에는 크게 관심이 없다.

 

동적 우선 순위 변경

규칙 3: 작업이 시스템에 들어오면, 가장 높은 우선순위(상위 큐)에 배치된다.
규칙 4a: 작업이 실행 도중 Time Slice를 모두 사용하면, 우선순위가 감소(하위 큐로 이동)한다.
규칙 4b: 작업이 Time Slice가 끝나기 전에 CPU를 양보하면, 우선순위는 유지된다.

문제점

1. 작업 A와 같이 실행 시간이 긴 작업은 우선순위가 하락하면서 기아 상태에 빠질 수 있다.
2. 악의적인 응용 프로그램이 Time Slice가 끝나기 직전에 CPU를 양보하여 우선순위를 유지할 수 있다.
3. 프로그램은 시간이 지남에 따라 행동을 변경할 수 있다.

 

우선 순위 높임 (Priority Boost)

규칙 5: 일정 시간 $S$가 지나면, 시스템 내 모든 작업이 가장 상위 큐로 이동한다.

• 우선순위 높임이 없으면, 장시간 실행되는 작업이 계속 하위 큐로 내려가 최종적으로 CPU를 할당받지 못하게 된다.
• 우선순위 높임을 통해 장시간 실행되는 작업도 기아 상태 없이 정기적으로 CPU 시간을 할당받을 수 있다.

 

더 나은 우선 순위 하락 논리

규칙 4a/4b를 수정한다.

규칙 4: 작업이 할당된 시간을 모두 사용하면, CPU를 양보한 횟수와 관계없이 우선순위가 감소한다.

수정 전 문제점

• 상위 큐(Q2)의 작업 $B$가 Timer Interrupt 전에 CPU를 양보하면 우선순위가 감소하지 않아 계속 Q2에서 실행된다.
• 이로 인해 작업 $A$가 기아 상태에 빠질 수 있다.

규칙 수정 이후

• 작업 $B$가 Q2에서 할당된 시간을 모두 사용한 후, 우선순위가 하락해 Q1, Q0로 이동한다.
• 이후 작업 $A$와 번갈아가며 실행된다.

 

요약

규칙 1: 만약 $Priority_A > Priority_B$라면, $A$가 실행되고 $B$는 실행되지 않는다.
규칙 2: 만약 $Priority_A = Priority_B$라면, $A$와 $B$가 RR 방식으로 실행된다.

규칙 3: 작업이 시스템에 들어오면 가장 높은 우선순위에 배치된다.

규칙 4: 작업이 할당된 시간을 모두 사용하면, CPU를 양보한 횟수와 관계없이 우선순위가 감소한다.

규칙 5: 일정 시간 $S$가 지나면, 시스템 내 모든 작업이 가장 상위 큐로 이동한다.

---

비례 공유 스케줄링

각 작업은 가중치 값을 가지고, CPU는 작업의 가중치 값에 비례해서 할당 된다.

Lottery 스케줄링

• 각 작업 $τ_i$​는 $m_i$ 티켓을 가진다.
• 시스템 전체에는 총 $M$ 티켓이 존재한다.
• 확률적 알고리즘으로, 무작위 번호 생성기를 사용해 당첨 티켓을 선택한다.
• 작업 $τ_i$ 는 확률 $p=m_i/M$ 에 따라 자원을 할당받는다.

Stride 스케줄링

• 결정론적 알고리즘으로, stride는 티켓 수에 반비례한다.
• 최소 pass 값을 가진 Task가 선택되며, 선택된 Task의 pass 값은 stride만큼 증가한다.

동작 방식

1. 각 작업의 초기 pass 값은 stride 값으로 설정된다.
2. 각 단계에서 가장 작은 pass 값을 가진 작업이 CPU를 할당받는다.
3. CPU를 할당받은 작업의 pass 값은 stride만큼 증가한다.
4. 동일한 pass 값을 가진 작업이 여러 개라면, 무작위로 선택해 CPU를 할당한다.