CPU 스케쥴링 알고리즘

목표

1.스케쥴링의 배경에 대해 이해한다.

2.스케쥴링이 일어나는 시점에 대해 이해한다.

3.스케쥴링 알고리즘의 평가기준에 대해서 이해한다.

4.스케쥴링 알고리즘의 종류와 장,단점을 예시와 함께 이해한다.

스케쥴링이란?

프로세스와 쓰레드 포스팅에서 배운거처럼, 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 한다. 따라서 OS는 실행 대기중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있다.

정책에 따라서 

1.CPU이용률을 최대화,

2.오버헤드를 최소화,

3.모든 프로세스가 공평하게 분배하는 방식이 있다.

선점 스케쥴링(Preemptive Scheduling)

OS가 나서서 CPU사용권을 '선점'하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다. 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있다. 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다. 

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

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있으며 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적다. 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있다. 

CPU , I/O Burst Cycle

<CPU I/O Burst Cycle>

스케쥴링에 본격적으로 들어가기 전에 스케쥴링의 단위에 대해서 짚고 넘어가자.

프로세스 실행은 CPU실행과 입/출력 대기의 싸이클로 구성된다. 프로세스는 이 둘 상태를 왔다갔다 하는 것이다. 

여기서 CPU Burst란 프로세스의 사용중에 연속적으로 CPU를 사용하는 단절된 구간이다. 즉, 스케쥴링의 단위이다.

I/O Burst란 프로세스의 실행 중에 I/O작업이 끝날때까지 Block되는 구간이다.

스케쥴링이 일어나는 시점

스케쥴링은 다음과 같은 프로세스의 상태변화가 일어날 때 발생된다.

1.수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때

2.수행 -> 준비 (Running->Ready) : 인터럽트가 발생했을때

3.대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을때 

4.수행 -> 종료 (Running -> Terminate)

여기서 1,4은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링이 발생되고 2,3은 강제로 할당해야 하므로 선점 스케쥴링 방식이다.

스케쥴링 알고리즘 평가기준

-CPU이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율

-처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수

-총 처리 시간 : 프로세스가 시작해서 끝날때 까지 걸린 시간

-대기시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총 합

-응답시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

스케쥴링의 종류

1. FCFS (First Come , First Serve)

먼저 도착한 프로세스를 먼저 처리하는 스케쥴링 알고리즘이다. 비 선점형이며 FIFO큐를 이용하여 간단하게 구현한다.

다만 Convoy Effect(호위효과)가 발생하는데, 긴 처리시간의 프로세스가 선점되어버리면 나머지 프로세스들은 끝날때 까지 대기해야 한다.

따라서 먼저 도착한 프로세스의 버스트 타임에 따라서 평균 대기시간의 편차가 크다. 

2. SJF(Shorted Job First)

최단작업우선 스케쥴링 알고리즘이다. 여기서 최단작업이란 CPU버스트 타임이 가장 짦은 프로세스를 말한다. 따라서 가장 적은 평균 대기 시간을 달성할 수 있다. 만약 CPU버스트 시간이 동일하다면 FCFS방식을 따른다. 다만 선점형인 경우에는 위와같이 진행이 되지만 비 선점형일 경우엔 최소잔여시간우선 법칙을 따른다. 

현재 CPU에 할당된 프로세스의 남은 잔여시간과, 새로 들어온 프로세스의 CPU버스트 타임을 비교하여 더 적은 프로세스에게 할당하게끔 한다.

최적이긴 하지만 다음 프로세스의 버스트시간을 계산하기 어렵다는 단점이 있어서 '비슷할것이다'라고 추측을 통해 진행하기도 한다.

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

미리 주어진 프로세스의 우선순위에 따라서 스케쥴링하는 방식이다. 2번에서 다룬 SJF도 Priority Scheduling의 일종이다.(최소 버스트 시간 기준) 그러나 우선순위가 낮은 프로세스는 할당되지 않기도 하는데, 이를 기아(Starvation)이라고 부른다. 이를 방지하기 위한 해결법으로는 노화(Aging)이 있는데 기다리는 시간에 따라 우선순위를 증가시켜주는 방식이다. 마찬가지로 우선순위가 같으면 FCFS를 적용한다. 

선점형과 비선점형이 있다. 

4.Round Robin(라운드로빈)

정해진 시간 할당량만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환 큐)의 가장 마지막에 가서 재할당을 기다린다.

시간 할당량이 중요한데, 너무 작으면 빈번한 Context Switching이 발생하고, 너무 길면 FCFS와 다를 바 없어진다. 통산 10~100ms사이이다.

선점형 알고리즘이다.

5.Multilevel-Queue(다단계 큐)

준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식. 메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당된다. 따라서 큐와 큐 사이에도 스케쥴링이 필요하다. 우선순위 방식 혹은 시분할 방식으로 한다.

우선순위 방식

고정 우선순위의 선점형 방식으로 구현되며, 따라서 우선순위에 따른 큐의 스케쥴링은 절대적이다. 예를 들어, 

우선순위가 높은 Forground Queue

-대화형 프로세스를 위한 큐

-Round Robin

우선순위가 낮은 Background Queue

-연산작업을 처리하는 프로세스 큐

-FCFS

여기서 Forground큐가 비어있지 않는 한 Background큐는 먼저 실행될 수 없으며, Background큐가 먼저 실행중이더라도 Forground큐에 프로세스가 들어오면 선점된다.

6.Multilevel-Feedback-Queue(다단계-피드백 큐)

기존 다단계 큐 방식은 특정 프로세스가 큐에 고정되는 방식이었다. 반면 다단계 피드백 큐에서는 큐와 큐 사이에 프로세스가 이동하는걸 허용한다. 큐를 구분하는 기준은 CPU버스트이며 입출력 중심의 프로세스와 대화형 중심의 프로세스를 높은 우선순위의 큐에 넣는다. 기아상태를 예방하기 위한 노화정책도 진행된다.

다단계 큐와 비교했을때 프로세스를 버스트타임이나 기타 우선순위에 따라서 큐에서 내리거나 올리는 등 설계나 구현이 복잡하다는 단점이 있다.

참고

https://oaksong.github.io/2018/02/12/cpu-scheduling/

https://jiwondh.github.io/2017/11/02/process-scheduling/#%EF%B8%8F-srt-%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%A7%81-%EC%B5%9C%EB%8B%A8-%EC%9E%94%EC%97%AC%EC%8B%9C%EA%B0%84

https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85)