CPU 스케줄링

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 여기서 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 CPU 스케줄링 알고리즘이라 한다. 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는가가 관건이다. CPU 스케줄링은 크게 2가지로 구분되는데, Preemptive 스케줄링과 Non-Preemptive 스케줄링으로 구분된다.

Preemptive vs Non-Preemptive

1. Preemptive(선점)

프로세스가 CPU를 점유하는 동안 I/O나 인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다.
프로세스가 정상적으로 수행중인 다른 프로세스나 CPU를 강제로 점유하여 실행 가능하다.

2. Non-Preemptive(비선점)

한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 완전히 종료할 때까지 다른 프로세스가 CPU를 점유하지 못한다.

선점형 스케줄링(Preemptive Scheduling)

1. SRT(Shortest Remaining Time) 스케줄링

짧은 시간 순서대로 프로세스를 수행한다.
현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착하면 CPU는 선점된다. (실행 중인 프로세스가 있어도 최단 프로세스를 위해 sleep 시키고, 가장 시간 짧게 걸리는 프로세스부터 시행한다.)
계속해서 현재 실행중인 프로세스보다 짧은 시간의 프로세스가 들어오면 잦은 문맥교환이 일어난다는 단점이 존재한다.

2. Round Robin 스케줄링

시분할 시스템의 성질을 활용한 방법이다.
일정 시간을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다.
다음 프로세스 역시 같은 시간동안 수행 후 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 진행하고, 마지막 프로세스까지 진행했다면, 다시 처음 프로세스로 돌아와서 작업을 반복한다.
이러한 일정 시간을 Time Quantum(Time slice)라 부른다. 일반적으로 10msec~100msec 사이의 범위를 지닌다.
한 프로세스가 종료되기 전에 Time Quantum이 끝나면 다른 프로세스에 CPU 자원을 넘겨주므로 선점형 스케줄링의 대표적 예시

3. Multi-Level Queue 스케줄링

프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 두어, 각 큐마다 다른 규칙을 지정할 수 있다. 이를테면, 어떤 준비 큐는 우선순위를 기준으로, 어떤 큐는 CPU 시간 등을 기준으로 규칙을 정한다는 의미이다.
준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
프로세스들이 CPU를 기다리기 위해 한 줄이 아닌 여러 줄로 선다.
큐마다 우선순위를 지정해 줄 수 있다. 예를 들어, System process Queue, Interactive process Queue, Batch process Queue가 있을 때, System process, Interactive process, Batch process 순으로 우선순위가 높은 순서이다. Batch process Queue는 운영체제 개입이 적으므로 우선순위가 가장 낮다.

4. Multi-Level feedback Queue 스케줄링

기본 개념은 Multi-Level Queue와 동일하지만, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다.
모든 프로세스는 가장 위의 큐에서 CPU 점유를 대기한다. 이 상태로 있다가 이 큐에서 기다리는 시간이 오래 걸리면 아래의 큐로 프로세스를 옮긴다. 이러한 방식으로 대기시간을 조정한다.
우선순위 순으로 큐를 사용하는 와중에 우선순위가 낮은 아래의 큐에 있는 프로세스에서 starvation 상태가 발생하면 이를 우선순위가 높은 위의 큐로 옮길 수 있다.
대부분 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용한다. 프로세스 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.

비선점형 스케줄링(Non-preemptive Scheduling)

1. FCFS (First Come First Server)

준비 큐에 먼저 도착한 프로세스가 먼저 CPU를 점유한다.
CPU를 할당받으면 CPU Burst가 완료될 때까지 CPU를 반환하지 않으며, 할당되었던 CPU가 반환할 때만 스케줄링이 이루어진다.
위의 그림에서 프로세스가 들어온 순서가 C, B, A이면 평균 대기 시간은 아래와 같다.
두 경우에서 모든 프로세스가 끝난 시간은 30msec으로 같지만, 평균 대기 시간으로 말미암아 위의 예제는 17msec, 아래에서는 3msec로 차이가 난다. 들어온 순서대로 수행한다고 반드시 효율적인 것은 아니다.
위의 예제처럼 A, B, C 순서대로 들어온 경우를 Convoy Effect라 부른다. 이는 CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스는 그만큼 오래 기다리는 것을 의미한다.

2. SJF(Shortest-Job-First)

다른 프로세스가 먼저 도착했어도 CPU Burst가 짧은 프로세스에게 CPU를 먼저 할당
선점, 비선점 모두 가능하다
가장 효율적인 CPU 스케줄링 같지만, 매우 비현실적이다. 왜냐하면 컴퓨터 환경에서는 프로세스 CPU 점유 시간을 알 수 없기 때문이다. 여러 변수가 많기 때문에 실제로 수행해서 측정해야 한다. 실제 측정한 시간으로 예측하여 SJF 사용할 수 있지만 이는 오버헤드가 매우 크다

3. Priority

우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘
우선순위는 정수값으로 나타내며, 작은 값이 우선순위가 높다.
우선순위를 정하는 방법
- 내부적으로 정의: 프로세스의 우선순위를 계산하기 위해 어떤 측정가능한 변수들을 이용한다. 예를 들어 시간 제한, 메모리 요구량, 평균 I/O burst 비율부터 CPU 버스트 비율까지 모두 우선순위를 계산하는데 이용한다. 여기서 I/O 버스트는 I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지의 일련의 작업을 의미한다. 그리고 CPU 버스트는 프로그램이 I/O를 한 번 수행한 후 다음번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 일련의 작업을 의미한다.
- 외부적으로 정의: 운영체제가 스스로 정하는 것이 아닌 외부에 설정된 기준을 준수한다. 예를 들어, 정책적 요소, 프로세스 중요도, 들어가는 자원의 비용 등의 외부적 요인이 프로세스의 우선순위 계산하는데 이용된다.
단점으로 starvation 현상이 발생할 수 있다. starvation 현상이란 어떤 프로세스가 CPU의 점유를 오랜 시간 동안 하지 못하는 현상을 의미한다. 실제 컴퓨터 환경에서 새 프로세스가 계속 ready queue에 들어오는데, 이 프로세스들이 모두 우선순위가 높으면 이미 기다리고 있던 우선순위 낮은 프로세스는 계속 기다리는 상태로 남게 된다.
이를 해결하는 방법으로 aging이 있다. Ready queue에서 기다리는 동안 일정 시간이 지나면 우선 순위를 일정량 높이는 것이다. 그렇게 하면 우선순위 가장 낮은 프로세스라도 시간이 지나면 우선순위 역시 계속 높아지므로 수행될 가능성이 높아진다.