CPU 스케쥴링 알고리즘

어떤 프로세스에 CPU를 배정할지 결정하는 것.

CPU 스케쥴링이 필요한 이유

CPU 스케쥴링의 원래 목적은 모든 프로세스가 자원을 공평하게 배정받도록 하는 것이다. 특정 프로세스가 시스템 자원을 독점하는 것을 막기 위함이다. 효율성 또한 고려해야 한다. 프로세스가 CPU를 점유하여 작업을 수행하다 인터럽트가 발생하면 일시적으로 프로세스는 CPU를 사용하지 않지만 계속 점유하고 있는 상태가 된다. 이러한 상태를 줄이면 CPU를 최대한 효율적으로 사용하며 시스템 성능을 높일 수 있다.

스케쥴링 알고리즘 선택기준

효율성을 평가할 때 CPU 사용률과 처리량은 계산하기 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.

• 대기 시간: 프로세스가 생성된 후 ~ 실행되기 전까지 시간
• 실행 시간: 프로세스 작업 시작 후 ~ 종료되기까지 시간
• 반환 시간: 대기 시간 + 실행 시간

Non-Preemptive(비선점) 스케쥴링

어떤 프로세스가 CPU를 점유하면 운영체제가 CPU를 강제로 빼앗을 수 없는 방식이다. 선점 스케쥴링보다 Context Switching에 의한 낭비가 적으나 CPU 사용 시간이 긴 프로세스 때문에 보다 실행시간이 짧은 여러 프로세스가 기다리게 되어 전체 시스템의 처리율이 떨어진다.

FCFS 스케쥴링

레디 큐에 도착한 순서대로 CPU를 할당하는 방식. 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 계속 기다려 효율성이 떨어진다.(콘보이 효과)

• 예시 (위와 동일한 표)

평균 대기 시간: (0+(30-3)+(48-6))/3=23ms

SJF(Shortest Job First) 스케쥴링

레디 큐 안의 프로세스 중 수행시간이 가장 짧은 것을 먼저 수행한다. 평균 대기시간을 감소시키는 기법이다. FCFS의 콘보이 효과를 완화한다. 그러나 운영체제가 프로세스의 종료시간을 정확하게 예측하기 어렵고 공평하지 못하여 사용하기 힘들다.

• 예시 (위와 동일한 표)

SJF의 경우 P1을 수행하는 동안 도착한 P2와 P3중 작업시간이 더 짧은 P3을 P2보다 먼저 수행한다.
평균 대기 시간: (0+(30-6)+(39-3)/3)=20ms

HRN(Highest Response Ratio Next) 스케쥴링 종류

수행시간의 길이와 대기시간을 모두 고려해 우선순위를 정한다. SJF와 비교하면 대기 시간이 긴 프로세스의 우선순위를 높여 CPU 할당받을 확률을 높인다. 그러나 공평성에 위배되어 많이 사용되지 않는다.

• 우선순위 = (대기 시간+CPU 사용 시간)/CPU 사용 시간

• 예시 (위와 동일한 표)

P1를 실행하는 동안 레디 큐에 있는 P2와 P3의 우선순위를 계산한다. P2의 우선순위는 (27+18)/18 = 2.5, P3은 (24+9)/9 = 3.67로 더 큰 P3가 먼저 실행된 후 P2가 실행된다.
평균 대기 시간: (0+(30-6)+(39-3)/3)=20ms

Preemptive(선점) 스케쥴링 종류

어떤 프로세스가 CPU를 점유하여 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식이다. 우선 순위가 높은 프로세스를 빠르게 처리할 수 있다는 장점이 있지만, Context Switching의 오버헤드가 많다.

라운드 로빈(Round Robin) 스케쥴링

프로세스의 우선 순위 두지 않고, 타임 슬라이스 만큼 순서대로 돌아가며 CPU를 할당하는 방식이다. 타임슬라이스 동안만 작업할 수 있는데, 작업이 다 끝나지 않으면 레디 큐의 끝에 다시 삽입된다. Context Switching의 오버헤드가 큰 반면 응답시간이 짧아진다는 장점이 있다. 할당 시간이 너무 크면 FCFS 방식과 같아지고, 할당 시간이 너무 작으면 Context Switching을 위한 오버헤드가 많아진다.

• 예시 (위와 동일한 표)

타임 슬라이스가 10ms일 때, P1(10ms) -> P2(10ms) -> P3(9) -> P1(10ms) -> P2(8ms) -> P1(10ms) 순으로 실행된다.
총 대기 시간: 0(P1) + 7(P2) + 14(P3) + 19(P1) + 19(P2) + 8(P1) = 67ms
평균 대기 시간: 67/3 = 22.33ms

SRT(Shortest Remaining Time) 스케쥴링

SJF 스케쥴링과 RR 스케쥴링을 혼합한 방식이다. 기본적으로 RR 방식을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

• 예시 (위와 동일한 표)

타임 슬라이스가 10ms일 때, P1(10ms) -> P3(9) -> P2(10ms) -> P2(8ms) -> P1(10ms) -> P1(10ms) 순으로 실행된다.
총 대기 시간: 0(P1) + 4(P3) + 16(P2) + 27(P1) = 47ms
평균 대기 시간: 47/3 = 15.66ms

SJF 스케쥴링의 평균 대기시간 보다 빠르지만, 프로세스의 남은 작업시간을 계산하고 Context Switching이 일어나는 등 SJF에 없는 작업이 추가된다.

우선순위 스케쥴링

프로세스에게 우선순위를 부여하여 우선순위 높은 순으로 처리한다. 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.

• 예시 (FCFS스케쥴링에서 작업시간이 짧은 프로세스의 우선순위를 높게 설정)

평균 대기 시간: (0+(30-6)+(39-3)/3)=20ms
이 경우 총 대기 시간과 평균 대기 시간이 SJF 스케쥴링과 같다.

multilevel queue(다단계 큐) 스케쥴링

프로세스에 따라 여러 종류의 그룹으로 나누고 여러 레디 큐에 다양한 알고리즘을 사용하는 방식이다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 실행된다.

다단계 큐 스케쥴링은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. 이러한 문제를 해결하기 위해 다단계 피드백 큐 스케쥴링이 제안되었다.

multilevel feedback queue(다단계 피드백 큐) 스케쥴링

다단계 큐 스케쥴링과 같이 우선순위를 가진 여러 개의 큐를 사용한다. 다단계 큐의 경우 각 단계의 큐에 RR 방식을 사용하고 우선순위에 변화가 없는 반면, 다단계 피드백 큐의 경우 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. (우선순위가 하나 낮은 큐로 들어감) 우선순위에 따라 타임슬라이스의 크기가 다르다. 프로세스 우선순위 낮아질수록 해당 큐의 타임 슬라이스를 크게 하여 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 한다. (아래 사진의 맨 아래 큐는 타임 슬라이스가 무한대인 것을 FCFS로 표현한 것)

이 스케쥴링 방식이 오늘날 운영체제가 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다.