[개발 한 스푼] CPU 스케줄링 알고리즘의 종류와 각각에 대해 아는대로 설명해주세요 (2023.01.08)

개발 한 스푼

본 글은 <개발 한 스푼>에 올라오는 "오늘의 질문"에 대한 학습 결과물을 정리한 내용입니다.

 

 

CPU 스케줄링?

메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할 지 일들의 순서를 정하는 것을 CPU 스케줄링이라고 한다.

다르게 말하면, Ready Queue에 있는 프로세스들의 실행 순서를 정하는 것이다.

효과적인 스케줄링은 다중 프로그래밍을 가능하게 하고 CPU 이용률을 극대화시킬 수 있다.

 

CPU 스케줄링 종류

CPU 스케줄링 알고리즘은 선점과 비선점으로 구분할 수 있다.

- 선점(preemptive) : 다른 프로세스가 현재 CPU를 할당받아 실행중인 프로세스를 중지시키고 CPU를 강제적으로 뺏을 수 있는 방식

- 비선점(non-preemptive) : 다른 프로세스들이 CPU를 할당받아 실행중인 프로세스에게 CPU 할당을 강제적으로 뺏을 수 없는 방식

 

1. FCFS(First-Come First-Served)

- 선입선출. 먼저 요청한 프로세스 순으로 할당하는 방식

- 비선점 방식

- 장점 : 구현이 단순. 기아 현상(starvation)이 발생하지 않음.

- 단점 : 평균 응답 시간이 길어짐(한 프로세스가 장시간 독점하는 경우 뺏을 수 없기 때문에 끝날 때까지 기다려야하기 때문)

 

2. SJF(Shortest-Job-First)

- CPU 작업 시간(CPU burst time)이 짧은 프로세스 순으로 할당하는 방식

- 비선점 방식

- 작업 시간이 모두 동일한 경우 FCFS 정책을 따름

- 장점: 평균 대기 시간 최소화

- 단점: 수행시간이 긴 작업은 우선순위가 계속 밀려 기아 현상 발생. 현실적으로 실행 시간을 예측할 수 없음.

 

3. SRTF(Shortest-Remaining-Time-First)

- SJT의 선점 방식

- 프로세스의 남은 작업 시간이 짧은 프로세스를 우선 할당하는 방식

- 프로세스의 남은 burst time보다 더 짧은 프로세스가 도착하면 CPU를 빼앗음

- 장점 : 평균 대기 시간 최소화

- 단점 : 기아 현상 발생할 수 있음. 잦은 선점으로 context switching 비용 증대. 정확한 burst time을 정확히 예측하기 어려움

 

4. RR(Round-Robin)

- 동일한 크기의 할당 시간(time slice)을 가지고 할당 시간이 지나면 프로세스를 교체하는 방식

- 선점 당한 프로세스는 Ready Queue의 맨 뒤로 가게 됨

- 시분할 시스템을 위한 설계

- 선점형 방식

- 장점 : 평균 대기 시간은 조금 길어질 수 있지만, 응답 시간은 짧아짐. 기아 현상 x

- 단점 : 할당 씨간이 커지면 FCFS와 같아짐. 할당 시간이 작으면 context switching 비용이 증대함.

 

5. 우선순위 스케줄링(Priority Scheduling)

- 우선 순위가 높은 프로세스에게 CPU를 할당

- 선점형 방식 : 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스보다 높으면 CPU 선점

- 비선점형 방식 : 더 높은 우선순위의 프로세스가 들어오면 Ready Queue의 head 부분에 넣는다.

- 단점 : 기아 현상 및 프로세스가 CPU를 사용할 준비가 되었지만 우선순위가 낮을 경우 무한 대기하는 문제 발생

-> [해결책] Aging 기법 - 큐에 남아있던 시간에 비례해 가중치 부여

 

6. 다단계 큐(Multilevel-Queue)

- Ready Queue를 여러 개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식

- 각 Queue 마다 독자적 스케줄링을 사용하여 프로세스 성격에 따라 우선순위 부여 가능

- Queue들 간의 프로세스 이동 불가. 유연성이 떨어짐

- 단점 : 기아 현상 발생

 

7. 다단계 피드백 큐(Multilevel-Feedback-Queue)

- 기존 다단계 큐 방식은 특정 프로세스가 큐에 고정되는 방식. 반면, 다단계 피드백 큐에서는 큐와 큐 사이에 프로세스가 이동하는 것을 허용하는 방식

- 낮은 우선 순위에 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동 할 수 있다.

 

 

[참고]

CPU 스케줄링