프로세스 스케줄링

스케줄링은 CPU 작업과 입출력 작업을 병행하는 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법이다. 자원을 할당할 프로세스를

선택하는 과정이라고 할 수 있다. 자원 관리는 하나의 자원을 번갈아 가며 사용하는 방식과 하나의 자원을 분할하여 동시에 사용하는

방식으로 구분할 수 있다. 예를 들어, 프로세서 사용시간을 프로세스들에게 분배하는 것은 전자에 속하며 시간 분할(Time Sharing)

이라 부른다. 프로세스 스케줄링이 여기에 속한다. 반면, 메모리 공간을 분할하여 동시에 사용하는 것은 후자에 속하며 공간 분할

(Space Sharing)이라 한다.

 

스케줄링의 목적

스케줄링의 목적은 시스템의 성능 향상이다. 대표적인 성능 지표는 응답 시간(작업 요청으로부터 응답을 받을 때까지의 시간),

작업 처리량(단위 시간 동안 완료된 작업의 수), 자원 활용도(주어진 시간 동안 자원이 활용된 시간) 등이 있으며 목적에 맞는 지표를

고려하여 스케줄링 기법을 선택해야 한다. 

스케줄링의 기준

스케줄링 시 프로세스의 특성(I/O Bounded or Computed Bounded), 시스템 특성(Batch System, Interactive System),

프로세스의 긴급성, 프로세스 우선순위, 프로그램 총 실행 시간 등을 고려할 수 있다. 그중 Burst Time은 스케줄링의 중요한 기준 중

하나이다. 프로세스 수행은 CPU 사용 시간과 I/O 대기 시간으로 이루어지는데, CPU 사용시간을 CPU Burst, I/O 대기시간을

I/O Burst라고 한다.

 

스케줄링의 단계

발생하는 빈도 및 할당 자원에 따른 구분으로 Long-Term(Job Scheduling), Mid-Term(Memory Allocation), Short-Term(Process Scheduling)으로 나눈다. Job Scheduling은 커널에 등록할 작업을 결정하는 것으로 시스템 내의 프로세스 수를 조절한다. 

이때, I/O Bounded(I/O Burst가 CPU Burst에 비해 큰 프로세스)와 Compute Bounded(CPU Burst가 I/O Burst에 비해 큰 프로세스)

프로세스들을 잘 섞어서 선택해야 한다. Process Scheduling의 경우 프로세서를 할당할 프로세스를 결정하는 것으로 가장 빈번하게

발생하며 매우 빨라야 한다.

 

Job Scheduling(왼쪽), Memory Allocation(가운데), Process Scheduling(오른쪽)

스케줄링 정책

스케줄링 정책은 선점(Preemptive)-비선점(Non-Preemptive) 정책, 우선순위(Priority) 정책 등이 있다. 선점-비선점 정책에서 

비선점의 의미는 할당받은 자원을 스스로 반납할 때까지 사용한다는 것을 의미한다. Context Switching에 의한 부하가 적다. 

그러나 평균 응답 시간이 증가할 수 있고, 우선순위가 높은 일을 먼저 처리 못하는 우선순위 역전이 발생할 수 있다. 선점이란 타의에

의해 자원을 빼앗길 수 있음을 의미한다. 예를 들어, 할당 시간이 종료되었거나 우선순위가 높은 프로세스가 등장할 경우 자원을 

빼앗길 수 있다. 따라서 Context Switching 부하가 크다. 우선순위는 프로세스의 중요도를 의미한다. 이는 다시 정적 우선순위와

동적 우선순위로 구분할 수 있는데, 정적 우선순위는 프로세스 생성 시 결정된 우선순위가 유지되는 것을 의미한다. 구현이 쉽고

부하가 적다는 장점이 있으나 시스템 환경 변화에 대한 대응이 어렵다. 반면 동적 우선순위는 프로세스 상태 변화에 따라 우선순위를

변경하는 것을 의미한다. 구현이 복잡하고 우선순위 재계산의 부하가 크다. 하지만 시스템 환경 변화에 유연한 대응이 가능하다.

 

스케줄링 알고리즘

FCFS(First Come Fist Serve)

먼저 도착한 프로세스를 먼저 처리하는 비선점 스케줄링 알고리즘이다. Batch 시스템에 적합하고 Interactive 시스템에 부적합하다.

수행 시간이 긴 하나의 프로세서에 의해 다른 프로세스들이 오랜 대기 시간을 갖게 되는 Convoy Effect(대기 시간 > 실행시간)가

발생할 수 있다. 또한 평균 응답 시간이 길다는 단점이 있다.

 

RR(Round Robin)

먼저 도착한 프로세스를 먼저 처리하는 선점 스케줄링 알고리즘이다. FCFS와 다른 점은 자원 사용 제한 시간이 있어서 프로세스는

할당된 시간이 지나면 자원을 반납해야 한다. 이를 통해 특정 프로세스의 자원 독점을 방지한다. 대화형, 시분할 시스템에 적합하나

Context Switching 부하가 크다는 단점이 있다. 자원 사용 제한 시간(Time Quantum)이 시스템 성능을 결정하는 핵심 요소이며

해당 시간을 무한히 크게 설정하면 FCFS와 같아진다. 

 

FCFS(왼쪽), RR(오른쪽)

SPN(Shortest Process Next)

실행 시간을 기준으로 Burst Time이 가장 작은 프로세스를 먼저 처리하는 비선점 스케줄링 알고리즘이다. 평균 대기 시간을 최소화

하여 빠른 응답 시간을 제공할 수 있다. 또한, 시스템 내 프로세스 수를 최소화하여 스케줄링 부하를 감소하고 메모리를 절약함으로써

시스템 효율을 향상할 수 있다. 그러나 Burst Time이 긴 프로세스의 경우 자원을 할당받지 못하고 무한히 대기해야 하는

Starvation 현상이 발생할 수 있다. 그리고 정확한 실행 시간을 알 수 없어 이를 예측하는 기법 역시 필요하다.

 

SRTN(Shortest Remaining Time Next)

SPN의 변형으로 선점 스케줄링 알고리즘이다. 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점된다. SPN의 장점을 

극대화한 알고리즘이지만 프로세스 생성 시 총 실행 시간 예측이 필요하고, 잔여 실행을 계속 추적해야 해서 부하가 높다. Context

Switching의 부하도 존재한다. 사실상 구현 및 사용이 비현실적이다.

 

HRRN(High Response Ratio Next)

SPM의 변형으로 비선점 스케줄링 알고리즘이다. 스케줄링의 기준은 프로세스의 대기 시간(Aging Concepts)을 고려하여 

Response Ratio((WT + BT) / BT)가 높은 프로세스가 우선한다. SPN의 장점을 가지며 Starvation 역시 방지할 수 있다.

다만, 실행 시간 예측 기법이 필요하다.

 

MLQ(Multi Level Queue)

작업(or 우선순위) 별 별도의 ready queue를 가진다. 최초 배정된 queue를 벗어나지 못하며, 각각의 queue는 자신만의 스케줄링

기법을 사용한다. queue 사이에는 우선순위 기반의 스케줄링을 사용한다. 여러 개의 queue 관리를 위한 스케줄링 부하가 발생한다.

우선순위가 낮은 queue는 Starvation이 발생할 가능성이 있다.

 

MFQ(Multi Level Feedback Queue)

작업(or 우선순위) 별 별도의 ready queue를 가지며 queue 간 이동이 허용된다. Feedback을 통해 우선 순위를 조정한다. 

이때, 현재까지의 프로세서 사용 정보(패턴)을 활용한다. 설계 및 구현이 복잡하고 스케줄링 부하가 크다. Starvation이 발생할

가능성이 있다. 이를 개선하기 위해 각 ready queue 마다 시간 할당량을 다르게 배정하거나 대기 시간이 지정된 시간을 초과한

프로세스들을 상위 큐로 이동시키는 등의 변형을 취할 수 있으며, 입출력 위주의 프로세스들을 상위 단계의 큐로 이동하여 

우선순위를 높이는 방법 역시 가능하다.

 

스케줄링 알고리즘 요약

FCFS, RR은 공평성에 초점, SPN, SRTN, HRRN은 효율성 및 성능에 초점을 둔 알고리즘이다. 다만, SPN, SRTN, HRRN의 경우,

실행시간 예측 부하가 발생한다. MLQ, MFG는 추가적인 queue를 이용하여 이를 개선하기 위한 알고리즘이다.