CPU 스케줄링 알고리즘
CPU 스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다.
스케줄링 알고리즘
프로그램이 실행될 때 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. 이 알고리즘은 다음과 같은 항목들을 목표로 한다.
- CPU 이용률: CPU를 얼마나 잘 활용했는지
- 처리량: 단위시간 당 완료된 프로세스의 개수가 몇 개인지
- 총 처리 시간: 어떤 프로세스를 실행하는데 걸리는 시간이 얼마나 짧은지
- 대기 시간: 레디 큐에서 대기한 시간이 얼마나 짧은지
- 응답 시간: 시스템에 요청이 들어온 시간부터 첫 번째 응답이 발생하기까지의 시간이 얼마나 짧은지
종류는 크게 두 가지로 나뉜다.
- 비선점형(Non-preemptive): 일단 CPU를 할당받으면 해당 프로세스가 끝날때까지 CPU를 빼앗기지 않는다.
- 선점형(Preemptive): 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다.
비선점형
- FCFS(First Come First Served)
FCFS는 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 구현은 간단하나, 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 ‘호위 효과(Convoy Effect)’가 발생한다는 단점이 있다.
- SJF(Shortest Job First)
SJF는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 최소 평균 대기 시간을 보장한다는 장점이 있으나, 긴 시간을 가진 프로세스가 실행되지 않는 ‘기아 현상(Starvation)’이 일어날 가능성이 있다는 단점이 있다.
- Priority Scheduling
가장 높은 우선순위를 가진 프로세스에게 CPU를 할당해주는 방법이다. 오랜 대기시간을 가지고 있는 작업의 우선순위를 높이는 방법(Aging)을 통해 기아 현상을 해결한다는 장점이 있다.
선점형
- SRTF (Shortest Remaining Time First)
SJF의 선점형 스케줄링 방식으로, 중간에 더 짧은 시간을 가진 작업이 들어오면 CPU를 내어주는 알고리즘이다. 처리량은 많아질 수 있으나, 역시 기아 현상이 일어난다.
- RR (Round Robin)
라운드 로빈은 현대 컴퓨터가 쓰는 우선순위 스케줄링의 일종으로, 각 프로세스에게 동일한 할당 시간을 주고 그 시간에 작업이 끝나지 않으면 준비 큐로 돌아가는 알고리즘이다. 모든 프로세스는 ‘실행중인 프로세스의 개수 * 할당 시간’ 이내에 응답을 받을 수 있어 평균 응답시간이 짧다는 장점이 있다. 하지만 할당 시간을 너무 길게 설정하면 FCFS와 같아져 비효율적이어지고, 너무 짧게 설정하면 컨텍스트 스위칭이 너무 자주 일어나 오버헤드가 증가한다는 딜레마가 있다.
- MLQ (MultiLevel Queue)
MLQ, 다단계 큐는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용한 것을 말한다. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담은 적지만, 유연성이 떨어지기 때문에 우선순위가 낮은 프로세스는 기아 현상을 겪을 수 있다는 단점이 있다.
</details>
- CPU 스케줄링이 무엇인가요?
답변
* 프로그램이 실행되어 프로세스로 등록되고 나서 어떤 프로세스에 CPU 소유권을 줄 것인지를 특정한 알고리즘에 따라 결정하는 것을 말합니다. * 그 알고리즘은 프로세스가 CPU를 한 번 점유하고 나서, 다른 프로세스에게 소유권을 넘겨주는지의 여부에 따라 선점형, 비선점형으로 나눌 수 있습니다. 1. 비선점형 알고리즘에는 FCFS, SJF, Priority 스케줄링 등이 있고, 2. 선점형 알고리즘에는 SRFT, 라운드 로빈, 다단계 큐 등이 있습니다.- 운영체제에서 기아란 무엇인가요?
답변
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말합니다.- 운영체제에서 에이징은 무엇인가요?