CPU 스케줄링
1.
스케줄링의 목적
2.
스케줄링 시 고려 사항
3.
스케줄링 알고리즘
1) 스케줄링의 목적
CPU 스케줄링의 목적은 모든 프로세스가 공평하게 작업하도록 하는 것이다. 특정 프로세스가 시스템 자원을 독점하거나 파괴하는 것을 막기 위해 중요도에 따라 우선순위를 배정한다. 또한 시스템 자원을 효율적으로 배분하여 전체적인 시스템의 성능도 높여야 한다.
•
공평성: 모든 프로세스가 자원을 공평하게 배정받으며, 특정 프로세스가 배제되어서는 안 된다.
•
효율성: 시스템 자원이 유휴 시간 없이 사용되도록 한다.
•
안정성: 우선순위가 높은 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호한다.
•
확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
•
반응 시간 보장: 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
•
무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
2) 스케줄링 시 고려 사항
어떤 프로세스에 우선적으로 CPU를 할당할지 결정할 때 고려해야 할 사항이다.
a.
선점형 스케줄링과 비선점형 스케줄링
선점형 스케줄링
어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다. 문맥 교환(Context Switching) 같은 부가적인 작업으로 인해 낭비가 생기는 것이 단점이다. 그러나 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
비선점형 스케줄링
어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다. 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 실행된다. 선점형 스케줄링보다 작업량이 적고 문맥 교환에 의한 낭비도 적지만, CPU 사용 시간이 긴 프로세스가 있을 경우 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다. 과거의 일괄 작업 시스템에서 사용하던 방식이다.
b.
CPU 집중 프로세스와 입출력 집중 프로세스
CPU 집중 프로세스
수학 연산과 같이 CPU를 많이 사용하는 프로세스를 말한다. 즉 CPU 버스트(=CPU를 할당받아 실행하는 작업)가 많은 프로세스이다.
입출력 집중 프로세스
저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스를 말한다. 즉 입출력 버스트(=입출력 작업)가 많은 프로세스이다.
입출력 집중 프로세스는 잠깐 CPU를 사용한 후 대기 상태로 이동하기 때문에 다른 프로세스(CPU 집중 프로세스)가 CPU를 사용할 수 있다. 따라서 스케줄링을 할 때 입출력 집중 프로세스의 우선순위를 높이면 시스템의 효율이 향상된다.
c.
전면 프로세스와 후면 프로세스
전면 프로세스
GUI를 사요하는 운영체제 에서 화면의 맨 앞에 놓인 프로세스를 말한다. 현재 입출력을 사용하는 프로세스이므로 사용자와 상호작용이 가능하다.
후면 프로세스
사용자와 상호작용이 없는 프로세스로 사용자의 입력 없이도 작동하는 압축 프로그램을 예로 들 수 있다.
전면 프로세스는 사용자의 요구에 즉각 반응해야 하기 때문에 후면 프로세스보다 우선순위가 높다. 그만큼 후면 프로세스는 CPU를 할당받을 확률이 적다.
우선순위 높음 | 우선순위 낮음 |
대화형 프로세스 | 일괄 처리 프로세스 |
입출력 집중 프로세스 | CPU 집중 프로세스 |
전면 프로세스 | 후면 프로세스 |
3) 스케줄링 알고리즘
어떤 스케줄링 알고리즘이 효율적인지 파악하기 위한 평가 기준은 다음과 같다.
•
CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정한다.
•
처리량: 시스템이 정상적으로 작동한다면 일정 시간 후 작업이 끝난다. 처리량은 단위 시간당 작업을 마친 프로세스의 수를 나타낸다.
•
대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간이다.
•
응답 시간: 프로세스 시작 후 첫 번째 출력/반응이 나올 때까지 걸리는 시간이다.
•
반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간이다.
a.
FCFS 스케줄링
FCFS(First Come First Out) 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다. 초기의 일괄 작업 시스템에서 사용된 FCFS 스케줄링은 프로세스가 큐에 도착한 순서대로 실행되며, 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행시킬 수 있다. 큐가 하나이므로 모든 프로세스는 우선순위가 동일하다.
FCFS 알고리즘은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 계속 기다려 시스템의 효율성이 떨어지는 문제가 있는데 이를 콘보이 효과(=호위 효과)라고 한다. 또한 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않기 때문에 작업 효율이 떨어진다는 단점이 있다. (시분할 시스템에서는 입출력을 요청한 프로세스를 대기 상태로 보내어 처리할 수 있다.)
b.
SJF 스케줄링
SJF(Shortest Job First) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다. SJF 스케줄링은 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 순서를 바꾸어 CPU를 배정한다. FCFS 스케줄링의 콘보이 효과를 완화하여 시스템의 효율성을 높인다.
SJF 스케줄링은 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다는 단점이 있다. 또한 작업 시간이 길다는 이유만으로 계속 밀린다면 공평성이 현저히 떨어진다.
c.
HRN 스케줄링
HRN(Highest Response Ratio Next) 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 한다. HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식이다. 프로세스의 우선순위를 결정하는 기준은 다음과 같다.
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용시간
이처럼 대기 시간이 긴 프로세스의 우선순위를 높임으로써 아사 현상을 완화한다. 즉 스케줄링 방식에 에이징을 구현한 셈이다. 그러나 여전히 공평성이 위배되어 사용되지 않는다.
위의 세 가지는 비선점형 알고리즘에 해당한다. 선점형 알고리즘에 해당하는 스케줄링 알고리즘에는 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링 등이 있다.
[참고]
쉽게 배우는 운영체제 (2022)
