3:56

1. CPU 스케줄링의 개요

 CPU 스케줄링은 특정 프로세스에 편중되지 않게 자원을 배분하기 위해 사용한다. 

 1) CPU 스케줄링의 단계

 2)  CPU 스케줄링의 구분

 선점형 스케줄링의 경우 프로세스가 CPU를 독점할 수 없어 시분할시스템에 적합하나, 문맥 교환의 오버헤드가 많다. 반면 비선점형 스케줄링의 경우 CPU 스케줄러의 작업량이 적고 문맥교환도 적기 때문에 오버헤드가 적지만 기다리는 프로세스가 많아 처리율이 떨어진다.

 2)  CPU 스케줄링 시 프로세스의 우선순위 결정

 일반적으로 프로세스의 우선순위는 다음과 같다.

① 커널 프로세스 > 일반 프로세스

② 입출력 집중 프로세스 > CPU 집중 프로세스

③ 전면 프로세스 > 후면 프로세스

④ 대화형 프로세스 > 일괄 처리 프로세스

 프로세스의 우선순위를 결정하는 방식으로는 다음과 같은 종류가 있다.

 고정 우선순위 방식은 구현은 쉽지만 작업 효율이 떨어지고, 변동 우선순위 방식은 구현은 어려우나 작업 효율이 고정 우선순위 방식보다 상대적으로 높다.

2. CPU 스케줄링의 종류

1) 선입선출 스케줄링 (FCFS, FIFO)

 선입선출 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당한다. 비선점형 방식으로, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 계속해서 대기해야 하므로 효율성이 낮은 편이다.

2) 최단 시간 우선 스케줄링 (SJF)

 최단 시간 우선 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하며, 비선점형 방식이다. 선입선출 스케줄링보다 효율성은 높으나, 작업 시간이 길다는 이유로 계속해서 뒷순위로 밀리는 프로세스가 생길 수 있다. 이러한 현상을 아사(Starvation) 현상이라고 부른다. 아사현상 완화를 위해서는 프로세스가 자신의 순서를 양보할 때마다 나이를 먹고 나이를 먹을 수록 우선순위를 높이는 에이징(aging) 기법을 사용할 수 있다.

3) 최고 응답률 우선 스케줄링 (HRN)

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

 최고 응답률 우선 스케줄링은 최단 시간 우선 스케줄링에서 발생하는 아사 현상을 해결하기 위해 만들어졌으며, 비선점형 방식이다. 최단 시간 우선 스케줄링과 같은 방식으로 작동하나, 최단 작업이 아닌 위와 같은 방법으로 우선 순위를 결정하고 우선 순위가 높은 프로세스를 우선적으로 처리한다.

4) 라운드 로빈 스케줄링 (RR)

라운드 로빈 스케줄링은 선입 선출 스케줄링과 유사하게 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하면 완료 상태로, 그렇지 못하면 다시 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 스케줄링 기법이며, 선점형 방식이다. 타임 슬라이스가 지나치게 크면 선입 선출 스케줄링과 다를 바가 없어지고 타임슬라이스가 지나치게 작으면 문맥 교환이 너무 자주 일어나 효율성이 떨어지므로 적절한 타임 슬라이스를 정해주는 것이 중요하다.

5) 최소 잔여시간 우선 스케줄링 (SRT)

 최소 잔여시간 우선 스케줄링은 최단 시간 우선 스케줄링을 선점 형태로 변형한 기법이다. 준비 큐 중 가장 빨리 작업을 끝낼 수 있는 프로세스에게 CPU를 먼저 할당하고, 중간에 들어온 새로운 프로세스가 더 빠른 시간 내에 작업을 마칠 수 있다면 실행 중이던 프로세스를 타임아웃 시키고 새로운 프로세스에 CPU를 할당한다.

 최소 잔여시간 우선 스케줄링은 프로세스의 종료 시간을 예측하기 어렵고, 최단 시간 우선 스케줄링와 마찬가지로 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

 6) 다단계 큐 스케줄링 (MLQ)

 다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러개 사용하는 스케줄링 방식이다. 프로세스는 운영체제로부터 부여 받은 우선순위에 따라 해당 우선순위의 큐에 삽입되며, 상위 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다. 각 단계에서는  주로 라운드 로빈 스케줄링의 방식을 사용한다. 그러나 이러한 방식은 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 계속해서 연기되는 문제가 발생할 수 있다.

 6) 다단계 피드백 큐 스케줄링 (MLFQ)

다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스의 작업이 계속해서 지연되는 다단계 큐 스케줄링의 문제점을 보안하기 위해 고안되었다. 기본적인 매커니즘은 다단계 큐 스케줄링과 유사하나, 다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다는 차이점이 있다. 즉 CPU를 사용하고 난 프로세스는 원래의 큐가 아니라 우선순위가 하나 낮은 큐의 끝으로 들어간다. 물론 우선순위가 낮아진다고 하더라도 커널 프로세스의 우선순위가 일반 프로세스의 큐로 들어가는 일은 없다. 또한, 일반적으로 다단계 피드백 큐 스케줄링은 우선순위가 낮아질수록 실행 기회를 더 많이 주기 위해 타임 슬라이스를 크게 배정한다. (가장 낮은 우선순위의 경우 선입선출 스케줄링과 같은 방식으로 작동한다.)