스케줄링
프로세스가 작업을 수행하려면 스케줄러로부터 cpu를 할당 받아야 한다.
할당을 받는 건 순서에 의해 받을 수 있고, 처리하게 되는 시간을 배정을 받는다.
할당 작업은 운영체제에서 구현이 되며 프로세스에게 효율적으로 자원을 할당하기 위한 정책이다.
목적
|
공정한 스케줄링 |
모든 프로세스에게 공정하게 할당을 해야함 |
|
응답시간 최소화 |
대화식 사용자에게는 최대한 응답시간(response time)을 빠르게 함 |
|
반환시간 최소화 |
프로세스를 제출한 시간부터 완료시까지 걸리는 반환시간(turn around time)을 최소화 한다. |
|
대기시간 최소화 |
프로세스 준비 상태 큐에서 대기하는 시간을 최소화 해야함 앞에서 처리가 늦어지면 뒤에서 부하가 생기기 때문에 빠르게 처리해야함. |
|
우선 순위 제도 |
먼저 처리해야 하는 것에 우선 순위를 부여해서 먼저 처리 함. |
|
처리량 극대화 |
단위시간당 할 수 있는 처리량을 최대화 한다. |
|
균형 있는 자원 사용 |
자원들이 유휴 상태에 놓이지 않도록 골고루 사용하게 함.
|
|
무한 연기 회피 |
자원을 사용하기 위해 무한정 연기하는 경우를 회피 |
스케줄링 기법
▶선점 스케줄링 (preemptive scheduling)
한 프로세스가 cpu를 할당받아서 실행하고 있을 때 다른 프로세스가 cpu를 사용하고 있는 프로세스를 중지시키고 cpu를 차지할 수 있는 스케줄링 기법을 선점 스케줄링 기법이라고 한다.
우선순위가 높은 프로세스를 먼저 수행할 때 유리하고 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용한다.
많은 오버헤드(overhead)를 초래함
A라는 프로세스가 cpu를 사용하고 있을 때 잠시 중지시키고 B를 시키는 상황에 사용됨.
예 ) round robin, SRT, 선점 우선 순위 등의 알고리즘이 있다.
▶비선점 스케줄링(non-preemptive scheduling)
이미 사용되는 cpu를 빼았지는 못하고 사용이 끝날 때 까지 기다리는 스케줄링 기법이다.
할당 받은 cpu는 끝날 때 까지 사용함.
응답 시간을 예측할 수 있고 일괄 처리 방식이 적합하다.
모든 프로세스에 요구에 대해 공정하다.
중요도가 높은 작업이 낮은 작업이 기다리는 경우가 발생할 수 있다.
예 ) FCFS(first come first service), SJF(shortest job first), 우선 순위, HRN(heighest response next)등이 있다.
-> 높은 우선순위가 먼저 실행되고 낮은 작업이 기다리게 된다.
프로세스(Process)가 구동하려면 다양한 시스템 자원이 필요하다. 대표적으로 CPU(중앙처리장치)와 입출력장치가 있는데, 최고의 성능을 내기 위해 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것을 CPU스케줄링이라고 한다. CPU스케줄링에 대해 알아보기 전에, 왜 필요한지 짚고 넘어갈 필요가 있다. (스케줄링 기법에 어떤 것들이 있는지 외우는 것보다 중요하다.)
프로세스의 생명주기
라면을 끓일 때, 물이 끓을 때까지 멍하니 기다리지는 않을 것이다. 라면 봉투를 미리 뜯어 놓기, 스프 미리넣기, 각종 재료를 미리 준비하기 등을 물이 끓는 것을 기다리면서 할 것이다. 여기서 CPU스케줄링을 착안하면 되겠다. 프로세스는 작업(Job)을 완료할 때까지 다양한 상태가 되는데, 우리가 주목해야할 것은 'Waiting'이다.
프로세스가 CPU를 점유하여 작업을 수행하는 도중 I/O 또는 Interrupt가 발생하면 일시적으로 프로세스는 CPU를 사용하지 않게 된다. 하지만 계속 점유하고 있다. 이러한 상황을 줄여, CPU를 최대한 활용하면 시스템의 성능 개선을 꾀할 수 있다. 결국, "어떻게 프로세스들이 CPU를 효율적으로 사용하게 할 것인가?" 라는 고민에서 CPU 스케줄링이 출발한다고 할 수 있다.
중앙처리장치는 컴퓨터의 두뇌와 같은 역할을 한다.
본격적으로 CPU 스케줄링에 대해 알아보겠다. CPU 스케줄링은 크게 두 가지로 분류되는데, 선점(Preemptive)스케줄링과 비선점(Non-Preemptive)스케줄링이다.
선점스케줄링
- CPU가 어떤 프로세스에 의해 점유 중일 때, 우선 순위가 높은 프로세스가 CPU를 차지할 수 있음
- 우선 순위가 높은 프로세스를 빠르게 처리해야할 경우 유용.
- 선점이 일어날 경우, 오버헤드가 발생하며 처리시간을 예측하기 힘듦.
선점 스케줄링의 경우 위와 같은 특징이 있으며, 비선점 스케줄링은 선점 스케줄링과 반대이다. 선점 스케줄링의 경우에는 I/O요청, I/O응답, Interrupt발생, 작업완료 등의 상황에서 스케줄링이 일어날 수 있다. 하지만 비선점 스케줄링의 경우 프로세스가 스스로 CPU를 놓아주는 시점(작업이 완료되는 시점)에만 스케줄링이 일어난다.
(비)선점 스케줄링에 각각 속하는 CPU 스케줄링 알고리즘 기법은 다양하다. 그 알고리즘에 대해 간략히 소개하도록 하겠다.
1. 선점 스케줄링
1-1. SRT(Shortest Remaining Time) 스케줄링: 짧은 시간 순서대로 프로세스를 수행한다. 남은 처리 시간이 더 짧은 프로세스가 Ready 큐에 들어오면 그 프로세스가 바로 선점됨. 아래에 소개할 SJF의 선점 버전이라고 할 수 있다.
1-2. 라운드로빈(Round-Robin)스케줄링: 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당시간이 너무 크면 선입선출과 다를 바가 없어지고, 너무 작으면 오버헤드가 너무 커진다.
1-3. 다단계 큐(Multi-level Queue) 스케줄링: Ready큐를 여러 개 사용하는 기법. 각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.
1-4. 다단계 피드백 큐 스케줄링: 다단계 큐와 비슷하나 프로세스들이 큐를 이동할 수 있다.
2. 비선점 스케줄링
1-1. HRN(Highest response ratio next) 스케줄링: 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법. 수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다.
1-2. SJF(Shortest Job First) 스케줄링: 큐 안에 있는 프로세스 중 수행시간이 짧은 것을 먼저 수행. 평균 대기 시간을 감소시킨다.
1-3. 우선순위(priority) 스케줄링: 프로세스에게 우선순위를 정적, 혹은 동적으로 부여하여 우선순위가 높은 순서대로 처리한다. 동적으로 부여할 경우, 구현이 복잡하고 오버헤드가 많다는 단점이 있으나, 시스템의 응답속도를 증가시킨다.
1-4. 기한부(Deadline) 스케줄링: 작업을 명시된 시간이나 기한 내에 완료하도록 계획.
1-5. FIFO 스케줄링: 프로세스들은 Ready큐에 도착한 순서대로 CPU를 할당 받는다. 작업 완료 시간을 예측하기 매우 용이하다. 하지만 덜 중요한 작업이 중요한 작업을 기다리게 할 수도 있다.
지금까지 CPU 스케줄링과 알고리즘에 대해 간략히 알아보았다. CPU 스케줄링은 운영체제가 사용자도 모르는 새 자동으로 진행하는 작업이다. 프로세스와 비슷한 성질을 띠는 스레드의 경우, 프로그램 개발자가 스케줄링 관련 코드를 삽입해야 한다.
CPU 스케줄링에 대한 기법은 선점과 비선점 스케줄링이 있으며, 각 기법에 따른 알고리즘은 FIFO, 우선 순위, RR, SJF, 다단계 피드백 큐 스케줄링 등이 있다.
(1) 스케줄링 기법
스케줄링 기법은 사용중인 프로세스에서 자원을 빼앗을 수 있는지의 여부에 따라 선점 스케줄링 기법과 비선점 스케줄링 기법이 있다.
ⓐ 선점(Preemptive) 기법 - RR, SRT, MFQ 등
하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 프로세서를 빼앗을 수 있는 방법을 선점 스케줄링이라고 한다. 선점 스케줄링 방식은 프로세스의 우선 순위가 높은 프로세스가 CPU를 먼저 차지하기가 용이하기 때문에 실시간 시분할 시스템에서 사용한다.
- 우선 순위가 높은 프로세스가 먼저 수행되어야 할 때 유용하다.
- 빠른 응답 시간을 요구하는 대화식 시분할 시스템이나 처리 시간이 제한되어 있는 실시간 시스템에 유용하다.
- 많은 오버헤드를 초래한다.
ⓑ 비선점(Non-preemptive) 기법 - SJF, FIFO, HRN 등
프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 그 프로세스의 사용이 끝난 후에 스케줄링을 하여야 하는 방법을 비선점 스케줄링이라고 한다.
- 모든 프로세스들에 대한 요구를 공정히 처리한다.
- 응답 시간의 예측이 용이하다.
- 짧은 작업이 긴 작업을 기다리는 경우가 종종 발생한다.
(2) 스케줄링 알고리즘의 종류
스케줄링 알고리즘의 종류에는 FIFO 스케줄링, 우선 순위 스케줄링, 기한부 스케줄링, RR 스케줄링 SJF 스케줄링, SRT 스케줄링, HRN 스케줄링, 다단계 피드백 스케줄링 등이 있다.
ⓐ FIFO(First In First Out) 스케줄링
가장 간단한 스케줄링 기법으로, 먼저 대기 큐에 들어온 작업에게 CPU를 먼저 할당하는 비선점 스케줄링 방식이다.
- 비선점 스케줄링 기법이다.
- 중요하지 않은 작업이 중요한 작업을 기다리게 할 수 있다.
- 대화식 시스템에 부적합하다.
- FCFS(First Come First Served) 스케줄링 기법이라고도 한다.
ⓑ 우선순위(Priority) 스케줄링
각 작업마다 우선순위가 주어지며, 우선 순위가 제일 높은 작업에 먼저 CPU가 할당되는 방법이다. 우선 순위가 낮은 작업은 Indefinite Bolcking 이나 Starvation에 빠질수 있고, 이에 대한 해결책으로 체류 시간에 따라 우선 순위가 높아지는 Aging 기법을 사용할 수 있다
ⓒ 기한부(Deadline) 스케줄링
작업이 주어진 제한 시간이나 Deadline 시간 안에 완료되도록 하는 기법이다.
ⓓ 라운드 로빈(RR; Round-Robin) 스케줄링
FIFO 스케줄링 기법을 Preemptive 기법으로 구현한 스케줄링 방법으로 프로세스는 FIFO 형태로 대기 큐에 적재되지만, 주어진 시간 할당량(Time Slice) 안에 작업을 마쳐야 하며, 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 다시 대기 큐의 맨 뒤로 되돌아간다.
- 선점 스케줄링 기법이다.
- 시스템이 사용자에게 적합한 응답시간을 제공해 주는 대화식 시분할 시스템에 적합하다.
ⓔ SJF(Shortest Job First) 스케줄링
SJF는 비선점 스케줄링 기법으로, 처리하여야 할 자업 시간이 가장 적은 프로세스에 CPU를 할당하는 기법이다. 평균 대기 시간이 최소인 최적의 알고리즘이지만, 각 프로세스의 CPu 요구 시간을 미리 알기 어렵다는 단점이 있다.
ⓕ SRT(Shortest Remaining Time) 스케줄링
SJF 스케줄링 기법의 선점 구현 기법으로, 새로 도착한 프로세스를 비롯하여 대기 큐에 남아 있는 프로세스의 작업이 완료되기까지의 남아있는 실행 시간 추정치가 가장 적은 프로세스에 먼저 CPU를 할당한다.
ⓖ HRN(Highest Response Ratio Next) 스케줄링
Brinch Hansen이 SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업의 지나친 불평등을 보완한 스케줄링 기법이다.
- 비선점 스케줄링 기법이다.
- 서비스 받을 시간이 분모에 있으므로 짧은 작업의 우선 순위가 높아진다.
- 대기 시간이 분자에 있으므로 긴 작업도 대기 시간이 큰 경우에는 우선 순위가 높아진다.
ⓗ 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
다양한 특성의 작업이 혼합된 경우 매우 유용한 스케줄링 방법으로, 새로운 프로세스는 그 특성에 따라 각각 대기 큐에 들어오게 되며, 그 실행 형태에 따라 다른 대기 큐로 이동한다. 예를 들어 연산 위주의 프로세스들은 처음에 RR 방식의 대기 큐에서 주어진 시간 할당량이 만료되면 다음 단계의 큐에 배치되고, 실행 시간이 길수록 점점 낮은 우선 순위를 지니게 되어 마지막 가장 낮은 우선 순위의 큐에 도달하면 작업이 끝날 대까지 RR 방식으로 스케줄된다.