CPU 스케줄링 (CPU Scheduling)
스케줄링이란 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다. CPU 스케줄러(프로세스 스케줄러)는 프로세스가 생성된 후 종료될 때까지의 모든 상태 변화를 조정한다. CPU 스케줄러는 관리의 범주를 나누어 스케줄링을 진행하는데 규모에 따라 다음으로 분류된다.
- 고수준 스케줄링(High Level Scheduling): 시스템 내의 전체 작업 수를 조절하는 것으로, 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수를 결정한다. 또한 전체 시스템의 부하를 고려하여 작업의 시작 여부를 결정한다.
- 저수준 스케줄링(Low Level Scheduling): 활성화된 프로세스들의 실제 진행을 담당한다.
- 중간 수준 스케줄링(Middle Level Scheduling): 고수준 스케줄링에 의해 실행이 결정된 프로세스의 수를 조절하여 시스템의 과부하를 막는다.
CPU 스케줄링의 목적은 다음과 같다.
- 공평성: 모든 프로세스는 자원을 공평하게 배정받아야 하고, 특정 프로세스가 배제되어서는 안 된다
- 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 줘야 한다
- 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정하여 시스템 자원을 점유 또는 파괴하려는 프로세스로부터 자원을 보호해야 한다.
- 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 시스템 자원이 늘어나는 경우에도 혜택이 시스템에 반영되도록 해야 한다.
- 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 인식하기에 시스템은 적절한 시간 내에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
스케줄러 고려사항
CPU 스케줄러가 어떤 프로세스에 우선적으로 CPU를 할당할지 결정할 때 고려해야 할 사항들이 있다.
선점형 스케줄링 & 비선점형 스케줄링
- 선점형 스케줄링(Preemptive Scheduling): 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
- 비선점형 스케줄링(Non-Preemptive Scheduling): 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
선점형 스케줄링 방식은 운영체제가 실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있다. 하나의 프로세스가 CPU를 독점할 수 없기에 대화형 또는 시분할 시스템에 적합하다. 그러나 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생긴다.
비선점형 스케줄링 방식은 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기까지 계속 실행된다. 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적지만, CPU 사용 시간이 긴 프로세스로 인해 전체 시스템의 처리율이 떨어진다.
프로세스 우선순위
CPU 스케줄러는 우선순위를 사용한다. 이는 각각의 프로세스의 중요도가 다르다는 것을 의미한다. 우선순위가 높다는 것은 더 빠르게, 더 자주 실행된다는 것이다. CPU 스케줄러는 각 프로세스에 우선순위를 부여하는데 커널 프로세스의 우선순위가 일반 프로세스보다 더 높다.같은 커널 프로세스여도 더 중요한 커널 프로세스는 우선순위가 더 높고, 덜 중요한 프로세스는 우선순위가 낮다. 마찬가지로 일반 프로세스도 중요도가 각각 다르기에 우선순위가 서로 다르다.
프로세스의 우선순위를 배정하는 방식에는 고정 우선순위 방식과 변동 우선순위 방식이 있다.
- 고정 우선순위 방식(Static Priority): 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식
- 변동 우선순위 방식(Dynamic Priority): 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
CPU 집중 프로세스 & 입출력 집중 프로세스
프로세스의 상태 중, 실제 작업이 일어나는 상태는 CPU를 사용하여 작업하는 "실행 상태"와 입출력을 요청하여 완료되기까지 기다리는 "대기 상태"이다. 이때 CPU를 할당받아 실행하는 작업을 CPU 버스트(CPU Burst), 입출력 작업을 입출력 버스트(I/O Burst)라고 한다. 프로세스는 위의 작업 형태에 따라 CPU 집중 프로세스와 입출력 집중 프로세스로 분류된다.
- CPU 집중 프로세스(CPU Bound Process): CPU를 많이 사용하는 프로세스로, CPU 버스트가 많다.
- 입출력 집중 프로세스(I/O Bound Process): 입출력을 많이 사용하는 프로세스로, 입출력 버스트가 많다.
CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있으면 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. 입출력 집중 프로세스는 CPU를 잠시 사용한 후 대기 상태로 옮겨지기에 다른 프로세스가 CPU를 사용할 수 있게 된다. 이와 같이 입출력 집중 프로세스가 CPU 집중 프로세스보다 먼저 실행 상태에 들어가는 것을 "사이클 훔치기(Cycle Stealing)"이라고 한다.
전면 프로세스 & 후면 프로세스
전면 프로세스는 GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다. 현재 입력과 출력을 사용하는 프로세스이며 사용자와 상호작용이 가능하다. 후면 프로세스는 사용자와 상호작용이 없는 프로세스이다. 전면 프로세스는 사용자의 요구에 즉각 반응해야 하기에 우선순위고 높고, 후면 프로세스는 상호작용이 없기에 전면 프로세스보다 우선순위가 낮고 CPU를 할당받을 확률이 낮다.
스케줄링 알고리즘 (Scheduling Algorithm)
스케줄링 알고리즘 선택 기준
어떤 스케줄링 알고리즘이 더 좋은지 평가하려면 그에 따른 기준이 있어야 한다. 스케줄링 알고리즘의 성능을 평가하는 기준은 다음과 같다.
- CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
- 처리량: 단위 시간 당 작업을 마친 프로세스의 수를 측정하는 방법
- 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간을 측정하는 방법
- 응답 시간: 프로세스 시작 후 첫 번째 출력 또는 반응이 나타날 때까지 걸리는 시간을 측정하는 방법
- 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간을 측정하는 방법
CPU 스케줄링 알고리즘의 효율성을 평가할 때는 주로 대기 시간, 응답 시간, 반환 시간을 계한하며, 성능을 비교할 때는 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 "평균 대기 시간"을 본다.
FCFS 스케줄링 (First Come First Served)
FCFS 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다. 모든 프로세스의 우선순위가 동일하며 비선점형 방식이기에 한 번 실행되면 프로세스가 끝나야 다음 프로세스를 실행할 수 있다.
FCFS 스케줄링은 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 시스템의 효율성은 떨어진다(콘보이 효과) 또한 현재 작업 중인 프로세스가 입출력 작업을 요청하면 CPU가 작업하지 않고 쉬는 시간이 많아지기에 작업 효율이 떨어진다.
SJF 스케줄링 (Shortest Job First)
SJF 스케줄링은 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. 프로세스 CPU를 배정할 때 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있다면 순서를 바꿔서 실행하는 것이다. 이로써 FCFS 스케줄링의 콘보이 효과를 완화한다.
SJF 스케줄링은 작은 작업부터 먼저 실행하기에 시스템의 효율성은 좋아진다. 다만 운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵고, 공평성에 위배되기에 사용하기 어렵다.
특히 두 번째 이유인 공평성에 위배된다는 것은 특정 프로세스가 가장 나중에 실행되는데 그보다 간단한 작업이 계속 준비 큐에 들어오면 특정 프로세스의 작업이 계속 연기된다는 것을 말한다. 이를 아사 현상(Starvation) 또는 무한 봉쇄(Infinite Blocking)이라고 한다. 이는 프로세스가 양보하는 상한선을 정하는 에이징(Aging)으로 완화할 수 있지만 한계가 있다.
HRN 스케줄링 (Highest Response Ratio Next)
HRN 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로, 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식이다. 우선 순위를 결정하는 기준은 다음과 같다.
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간
HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화하지만 여전히 공평성이 위배되어 많이 사용되지 않는다.
라운드 로빈 스케줄링 (Round Robin : RR)
라운드 로빈 스케줄링은 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 선전형 알고리즘으로 프로세스들이 작업을 완료할 때까지 계속 순환하며 실행된다. 프로세스가 CPU를 일정 시간 동안 사용하고 다른 프로세스에 넘겨주어야 하기에 앞의 긴 작업을 무작정 기다리는 콘보이 효과가 줄어든다.
라운드 로빈 스케줄링과 같은 선점형 방식에는 문맥 교환 시간이 추가되기에 FCFS 스케줄링과 평균 대기 시간이 같다면 라운드 로빈 스케줄링이 조금 더 비효율적이 알고리즘이 된다.
SRT 스케줄링 (Shortest Remaining Time)
SRT 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당 받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택하는 알고리즘 방식이다.
실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간 더 적은 프로세스와 문맥 교환을 해야 하기에 SJF 스케줄링에는 없는 작업이 추가된다. 또한 SRT 스케줄링은 운영체제가 프로세스 종료 시간을 예측하기 어렵고 아사 현상이 일어나기에 잘 사용하지 않는다.
우선순위 스케줄링 (Priority)
우선순위 스케줄링은 우선순위를 반영한 스케줄링 알고리즘으로 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현 가능하다. 선점형 방식과 비선점형 방식 모두에 적용 가능하다.
- (비선점형 방식) SJF 스케줄링: 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
- (비선점형 방식) HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여한다.
- (선점형 방식) SRT 스케줄링: 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉜다.
- 고정 우선순위 알고리즘(Static Priority): 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정되는 방식
- 변동 우선순위 알고리즘(Dynamic Priority): 일정 시간마다 우선순위가 변하여 새로 계산하고 반영하는 방식
우선순위 스케줄링은 공평성을 위배하고 아사 현상을 일으킨다는 문제가 있다. 또한 프로세스의 우선순위를 매번 바꾸기에 오버헤드가 발생하여 시스템의 효율을 떨어뜨린다. 그럼에도 프로세스의 우선순위는 시스템의 효율성이 아닌 프로세스의 중요도를 기준으로 결정된다.
다단계 큐 스케줄링 (Multi-Level Queue)
다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 선점형 방식으로, 고정형 우선순위를 사용한다. 우선순위에 따라 다단계로 나뉘고 각각의 큐는 라운드 로빈 방식으로 운영된다. 프로세스는 운영체제에게 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입하고 상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
다단계 큐 스케줄링에서는 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업이 불가능하다. 따라서 우선순위가 높은 프로세스로 인해 우선순위가 낮은 프로세스의 작업이 연기된다.
다단계 피드백 큐 스케줄링 (Multi-Level Feedback Queue)
다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식으로, 다단계 큐 스케줄링과 기본 형태는 같기에 우선순위를 가진 여러 개의 큐를 사용한다. 우선순위에 따라 여러 개의 큐를 사용하고 한 번 CPU를 잡은 프로세스의 우선순위를 떨어뜨린다.
또한 다단계 피드백 큐 스케줄링은 각 큐의 타임 슬라이스 크기가 다른 변동 우선순위 알고리즘이다. 우선순위가 낮아질수록 큐의 타임 클라이스가 커진다. 다단계 큐 스케줄링에서 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻게 된다. 따라서 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작한다.
다단계 피드백 큐 스케줄링 방식은 오늘날 운영체제가 CPU 스케줄링을 할 때 일반적으로 사용하는 방식으로, 대표적인 변동 우선순위 알고리즘이다.
