출처
개인의 견해 및 추가 정리 내용이 포함되어 있습니다.
목차
CPU 스케줄링
- 실행 중인 프로세스 간 처리 순서를 정하는 행위
- 즉, 레디 큐에서 대기하는 프로세스 간에 CPU 자원을 분배하는 방법론 및 구현
- 스케줄링 평가 지표 :
프로세스 관점 - 대기 시간, 처리 시간, (최초) 응답 시간
CPU 관점 - 단위 시간 당 처리량(Throughput), CPU 이용률, 컨텍스트 스위칭으로 인한 오버헤드
CPU 스케줄링의 구분 - 선점 여부에 따라
비선점 (Non-Preemptive) 스케줄링
- 한 프로세스가 점유 중인 CPU를 다른 프로세스가 가로채어 할당할 수 없는 스케줄링 기법
e.g. FCFS, SJF, 우선 순위, HRN, 기한부
선점 (Preemptive) 스케줄링
- 한 프로세스가 점유 중인 CPU를 다른 프로세스가 가로채어 할당할 수 있는 스케줄링 기법 (특히, 우선순위에 의해)
e.g. RR, SRT, MQ, MFQ
비선점 스케줄링의 종류
1. FCFS (First Come First Served) 스케줄링
- 비선점 스케줄링
- 프로세스가 레디 큐에 도착한 순서대로 CPU 할당
- 단순하고 공평한 방법 : 프로세스간 우선순위와 순서 변동이 없음
- 비효율적이나, 프로세스의 처리 시간을 파악하는 것은 어려우므로 현대에선 응용 기법 사용
- 콘보이 효과를 일으킴
콘보이 효과 (Convoy Effect)
- CPU를 오래 점유하는 프로세스에 의해 다른 CPU들의 대기 시간이 커지는 현상
2. SJF (Shortest Job First) 스케줄링
- 비선점 스케줄링
- 레디 큐에 있는 프로세스 중, 처리 시간이 짧은 순서대로 우선 순위 부여
- 평균 대기 시간이 짧은 방식 중 하나 (콘보이 효과 완화)
- 기아 상태을 일으킴
기아(Starvation) 상태
- 우선 순위가 높은 프로세스가 계속 처리되며, 특정 프로세스가 무한정 대기하는 상태
3. HRN (Highest Response ratio Next) 스케줄링
- 비선점 스케줄링 (선점으로 구현 시 컨텍스트 스위칭이 잦기 때문)
- SJF의 기아 상태를 해결하기 위해 노화 기법 결합
- 우선순위 산정방식에 처리 시간과 대기 시간 고려
노화(Aging) 기법
- 기아 상태를 해결하기 위해 고안, 대기 시간에 따라 우선순위를 높혀 언젠가는 CPU를 할당받게 하는 기법
4. 우선순위 (Priority) 스케줄링
- 비선점/선점 여부는 구현자 몫
- 둘다 가능하기에, 분류상 비선점/선점에 공통 포함 : 최종 분류는 구현에 따름
- 우선순위에 따라 처리, 우선순위 책정은 구현자 몫
e.g. 처리 시간, 프로세스 중요도, 작업 유형 등 고려
- 일반적으로 우선순위가 같을 시 FCFS 적용
선점 스케줄링의 종류
1. 우선순위 (Priority) 스케줄링
- 위와 같음
2. SRT (Shortest Remaining Time) 스케줄링
- SJF를 선점 방식으로 변경한 기법
- 일반적으로 우선순위 큐 사용
- 처리 시간 기반 선점 : 레디 큐 상단의 프로세스가 CPU 점유 프로세스보다 짧을시 스위칭
- 평균 대기 시간이 짧은 방식 중 하나 : SJF와 같은 매커니즘, 선점 방식 적용에 따라 더 짧을 수 있음
- 기아 상태가 SJF보다 심해질 수 있음
3. RR (Round-Robin) 스케줄링
- FCFS에 선점 및 타임 퀀텀(혹은 슬라이스) 개념 추가
- 각 프로세스에게 동일한 타임 퀀텀(CPU 점유 가능 시간 단위)을 부여
- 타임 퀀텀이 지나면 프로세스가 CPU 자원 반납, 이후 레디 큐 맨 뒤로 이동
- 기아 상태 및 콘보이 효과 완화
- 적당한 타임 퀀텀 설정이 필요 (보통 10-100ms)
- 작다면, 잦은 컨텍스트 스위칭으로 오버헤드 발생
- 크다면, FCFS와 비슷해져 콘보이 효과 발생
4. MQ (다단계 큐, Multi-Level Queue) 스케줄링
- 프로세스를 그룹화하고 그룹마다 레디 큐를 두는 기법
- 큐의 스케줄링 기법 이기에, 큐안의 프로세스 스케줄링은 구현자 몫
- 큐마다 다른 스케줄링 방식 적용 가능
- 큐에 고정된 우선순위를 부여한다면 기아 현상이 발생할 수 있음
- 이를 위해, 큐마다 타임 퀀텀을 부여할 수 있음
5. MFQ (다단계 피드백 큐, Multi-Level Feedback Queue) 스케줄링
- MQ에 노화 기법을 추가
마치며
스케줄링 기법마다 장단점이 있기에, OS는 이를 조합하여 최적의 스케줄링한다. (상세 구현은 OS마다 상이)
예를 들어,
포워드 프로세스(혹은 작업)을 담는 포워드 큐와, 백그라운드 프로세스를 담는 백그라운드 큐로 구분한다면
포워드 프로세스는, 사용자와 상호작용하며 응답속도가 중요하기에 RR을 적용하고
백그라운드 프로세스는, 응답 시간이 중요하지 않기에(그래서 Batch를 적용하곤 한다) FCFS를 적용할 수 있다.
이 밖에,
I/O 프로세스나 대화형 프로세스(혹은 이를 담는 큐)에 높은 우선순위와 짧은 타임 퀀텀을 주는 경우 등이 있다.