CPU 스케쥴링(CPU Scheduling)

안녕하세요 dely입니다:)

오늘은 CPU 스케쥴링에 대해 정리해보겠습니다.

 

CPU 스케쥴링은 다중 프로그램 운영체제에서 CPU를 어떻게 하면

더 효율적으로 사용할 수 있을지에 대한 고민에 의해 생겨난 개념입니다.

 

즉, 같은 시간 내에 많은 양의 작업을 처리하기 위해

적합한 프로세스에게 CPU를 할당하기 위한 방법론이라고 할 수 있습니다.

 

프로세스 실행은 다음과 같이 CPU 실행과 입출력 대기의 사이클로 구성됩니다.

CPU burst -> 입출력 burst -> CPU burst -> ... -> CPU burst -> 시스템 콜(실행 종료)

 

그런데 이때 CPU burst와 입출력 burst의 길이 차이가 생길 수 있습니다.

입출력 중심의 프로그램일 경우 CPU burst는 상대적으로 짧을 것이고,

CPU 지향 프로그램일 경우 CPU burst는 상대적으로 길 것이기 때문입니다.

CPU 스케쥴링은 이러한 상황에 맞춰 적절한 CPU 스케쥴링 알고리즘을 선택하는 것이 중요합니다.

 

CPU 스케쥴링은 여러가지 알고리즘이 있습니다.

1. 선입 선처리(First-Come First-Served) 스케쥴링

2. 최단 작업 우선(Shortest Job First) 스케쥴링

3. 우선 순위(Priority) 스케쥴링

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

5. 다단계 큐(Multilevel) 스케쥴링

6. 다단계 피드백 큐(Multilevel Feedback Queue) 스케쥴링

 

하나씩 정리해보겠습니다.

 

1. 선입 선처리(First-Come First-Served) 스케쥴링

선입 선처리 스케쥴링은 우리의 세상에서 당연하게 받아들이는 줄서기 알고리즘입니다.

CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받게 됩니다.

프로세스가 준비완료 큐에 진입하면 PCB를 큐의 끝에 연결하여 FIFO 큐 형태로 관리합니다.

 

뭔가 굉장히 효율적이라고 생각이 들지만,

만약 CPU burst 시간이 매우 긴 프로세스가 제일 처음 들어오게 된다면

이후 들어오는 프로세스들은 대기 시간이 길어지게 됩니다.

 

CPU burst 시간이 짧은 프로세스부터 들어오게 된다면

같은 시간 내에 여러 개의 프로세스에게 CPU를 할당할 수 있는데,

CPU burst 시간이 긴 프로세스부터 들어오게 된다면

1개의 프로세스에게만 CPU를 할당할 수 밖에 없다는 말입니다.

 

그래서 선입 선처리 스케쥴링은

이전에 CPU를 선점한 프로세스를 무조건 기다려야하는 비선점형 알고리즘입니다.

 

 

2. 최단 작업 우선(Shortest Job First) 스케쥴링

최단 작업 우선 스케쥴링은 선입 선처리 스케쥴링의 단점을 보완한 알고리즘입니다.

CPU burst 길이가 짧은 프로세스에게 CPU를 먼저 할당하는 것입니다.

만약 CPU burst 길이가 동일한 프로세스가 여러개 있다면 선입 선출 스케쥴링을 적용하게 됩니다.

 

그리고 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비완료 큐에 도착했을 때

새로운 프로세스의 CPU burst가 실행되고 있는 프로세스의 남은 시간보다 더 짧을 수도 있습니다.

이 때 두 가지의 선택상황이 발생하게 됩니다.

이는 새로운 프로세스가 CPU를 할당받는 선점형 알고리즘과

기존에 실행하고 있는 프로세스가 자신의 CPU burst를 끝내도록 허용하는 비선점형 알고리즘입니다.

 

최단 작업 우선(SJF) 스케쥴링은 장기 CPU 스케쥴링에서 자주 사용됩니다.

단기 CPU 스케쥴링에서는 다음 CPU 요청 길이를 파악하기가 어렵기 때문입니다. (지수 평균 공식을 사용하여 추측할 수는 있음)

 

 

3. 우선 순위(Priority) 스케쥴링

우선 순위 스케쥴링은 사실 바로 위의 SJF 알고리즘을 포함하고 있습니다.

우리가 흔히 리스트 정렬 방법을 오름차순, 내림차순 등으로 선택할 수 있듯

우선 순위 스케쥴링도 다양하게 정의될 수 있습니다.

시간 제한, 메모리 요구, 열린 파일의 수, 평균 입/출력 burst와 평균 CPU burst에 대한 비율 등이 될 수도 있고,

사용자가 결정할 수도 있습니다.

 

SJF에서 이미 언급한 선점형과 비선점형 두 가지 선택상황이 발생할 수 있는데,

사실 우선 순위 스케쥴링의 문제점은

무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)입니다.

기존에 준비완료 큐에 들어있던 프로세스보다 우선순위가 높은 프로세스들이 새로이 들어오게 되면

기존에 준비완료 큐에 들어있던 프로세스는 계속 뒤로 밀려나기 때문입니다.

 

그래서 그에 대한 해결방법으로 노화(aging)가 있습니다.

오랫동안 시스템에서 대기하는 프로세스들의 우선 순위를 점진적으로 증가시키는 기법입니다.

 

 

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

라운드 로빈 스케쥴링은 원형 큐로 설계된 준비완료 큐를 사용합니다.

그리고 타이머를 설정해서 시간 안에 완료 된 프로세스는 자발적 방출이 되고,

시간을 오버한 프로세스는 준비완료 큐의 꼬리에 넣어

새로운 프로세스가 자동으로 CPU를 할당받을 수 있는 시스템입니다.

 

그렇기 때문에 라운드 로빈 스케쥴링은 선점형 알고리즘인데,

시간 할당량의 크기에 성능이 매우 많은 영향을 받게 됩니다.

시간 할당량이 너무 크게 되면 선입선출과 다름없고,

시간 할당량이 너무 작게 되면 잦은 문맥 교환 발생으로 매우 느린 처리기가 됩니다.

따라서 시간 할당량이 문맥 교환 시간에 비해 더 커야한다는 결론이 나게 됩니다.

 

5. 다단계 큐(Multilevel) 스케쥴링

다단계 큐 스케쥴링은 포그라운드, 백그라운드로 프로세스들을 구분하여 처리하게 됩니다.

먼저 포그래운드 프로세스가 백그라운드 프로세스보다 높은 우선 순위를 가질 수 있습니다.

 

또한 준비완료 큐를 여러개의 별도의 큐로 나눌 수 있습니다.

메모리 크기, 프로세스의 타입, 프로세스의 우선 순위와 같은 프로세스의 특성에 기반하여

한 개의 큐에 영구적으로 할당하게 됩니다.

 

 

6. 다단계 피드백 큐(Multilevel Feedback Queue) 스케쥴링

다단계 피드백 큐 스케쥴링은 위의 다단계 큐 스케쥴링에서

한 개의 큐에 영구적으로 할당되는 적은 융통성을 해결하기 위한 방법입니다.

 

프로세스가 큐들 사이로 이동할 수 있다는 의미로,

어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선 순위의 큐로 이동됩니다.

이러한 aging은 기아 상태를 예방할 수 있습니다.