[운영체제 OS] CPU 스케줄링 알고리즘

 

이전에 운영체제의 역할 중 하나가  CPU 스케줄링과 프로세스 관리 인 것과

프로세스, 스레드 그리고 멀티 프로세스, 멀티 스레싱 등 학습했다.

 

그럼 CPU(자원)이 하나일 때 여러 프로세스가 해당 자원을 필요로 할때 운영체제가 어떻게 관리를 할까?

 

CPU 스케줄러

CPU 스케줄러: CPU 스케줄링 알고리즘에 따라 프로세스에서 해야하는 일을 스레드 단위로 CPU에 할당시켜주는 것

 

즉, CPU 스케줄러를 통해 여러 개 중 어떤 프로세스에 CPU를 배정할지 결정한다.

이것은 컴퓨터 시스템의 효율에 직결되는 중요한 일이다.

 

CPU 스케줄링 알고리즘

프로그램이 실행될 때 CPU 스케줄링 알고리즘을 통해 어떤 프로그램에게 CPU 소유권을 줄 것인지 결정된다.

 

이 알고리즘은 다음과 같은 목표로 CPU 스케줄러를 사용한다.

 

1. CPU 이용률 - 높게

2. 처리량(Throughput) -주어진 시간에 많은 일을 하도록

3. 대기시간(Waiting time) - 준비 큐(Ready Queue)에 있는 프로세스가 적게

4. 반환 시간과 응답 시간은 짧게

 

 

CPU 스케줄링 알고리즘은 크게 2가지가 있다.

 

1. 비선점형 스케줄링

2. 선점형 스케줄링

 

말그대로 선점(Preemption), 선수 칠 수 있는 스케줄링과 그렇지 않은 스케줄링이다.

 

비선점형 스케줄링

비선점형 방식은 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식이다.

프로세스가 정해진 순서대로 CPU 소유권이 할당된다.

프로세스 순서가 변하지 않아 강제로 프로세스를 중지하지 않고

그로 인해 컨텍스트 스위칭으로 인한 부하가 적다.

 

종류는 다음과 같은 알고리즘이 있다.

 

1. FCFS(First Come, First Served)

2. SJF(Shortest Job First)

3. 우선순위(HRN, Hightest Response-ratio Next)

 

FCFS (First Come, First Served)

말 그대로 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

 

장점 - 간편함, 단순하고 공평함

단점 - 순서대로 수행 중에 길게 수행되는 프로세스 때문에 Conve Effect(준비 큐에서 오래 기다리는 현상)이 발생

SJF (Shortest Job First)

실행  시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

 

장점 - 평균 대기 시간이 가장 짧음

단점 - 긴 시간을 가진 프로세스가 실행되지 않는 기아 현상(starvation)이 일어남. 실제 실행 시간을 알 수 없기 때문에 과거의 실행 했던 시간을 토대로 추측 해서 사용함.

 

우선순위

기존 SJF 스케줄링에서 가장 긴 시간을 가진 프로세스가 실행되지 않는 점을 보완하기 위해 Aging 기법을 사용한 알고리즘. 

FCFS + SJF의 혼합형이라고 생각하면 된다.

 

아래와 같은 우선순위로 스케줄링 알고리즘 순서가 정해진다.

 

우선 순위 = (대기시간 + 실행시간) / (실행시간)

 

선점형 스케줄링

선점형 방식은 프로세스가 CPU를 할당 받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식이다.현대 운영체제가 쓰는 방식이며 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단 시키고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식이다.

 

1. 라운드 로빈(RR, Round Robin)

2. SRF(Shortest Remaining Time First)

3. 다단계 큐

 

라운드 로빈 (RR, Round Robin)

각 프로세스에 동일한 할당 시간을 주고 그 시간안에 끝나지 않으면 다시 준비 큐(Ready Queue)의 뒤로 가는 알고리즘.

 

예를들어 N개의 프로세스가 운영되고 각 프로세스에 q만큼의 할당 시간이 부여될 때 (N - 1) *q시간이 지나면 다시 자기 차례가 오게 된다.

할당시간이 크면 단순한 FCFS가 되고, 할당시간이 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 비용이 커진다.

 

일반적으로 전체 작업시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.

 

이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.

 

SRF (Shortest Remaining Time First)

SJF와 달리 중간에 실행시간이 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수애하는 알고리즘

 

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용하는 것.

 

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.