3. CPU 스케줄링

앞서 운영 체제의 기능을 배우면서 CPU와 메모리 보조기억장치 와의 관계를 보았으며 이들 사이에 시스템 호출, 메모리 할당등을 하면서 CPU 스케줄링 관리, 메모리 관리, 파일 및 입출력 관리가 필요하다는 것을 알게 됐다.

그렇다면 CPU 스케줄링이 무엇일까?

CPU 스케줄링

메모리에 있는 준비(Ready)상태의 프로세스 중 하나를 선택 해 CPU의 자원을 할당하는 방법이다.

 

CPU 스케줄링이 일어나는 시점

CPU자원을 가지고 있다가 뺴앗길 수 있는 상황은 다음과 같다.

1. 실행(Running)상태에서 대기(Waiting)상태로 전환될 때 (예, 입출력 요청) - 비선점

2. 실행(Running)상태에서 준비(Ready)상태로 전환될 때 (예, 인터럽트가 발생할 때) - 선점

3. 대기(Waiting)상태에서 준비(Ready)상태로 전환될 때 (예, 입출력이 종료될 때) - 선점

4. 종료(Terminated)될 때 - 비선점

 

선점과 비선점의 차이는 기존에 CPU를 사용하던 프로세스가 계속 프로세스를 사용할 수 있는데도 불구하고 자원을 빼앗는지에 대한 여부이다. 대기상태로 전환되거나 종료된 경우에는 CPU사용을 멈춘 상태이므로 다른 CPU자원이 다른 프로세스에 항당 되는 것이 당연하다. 하지만 준비 상태일 떄는 CPU 사용이 가능한 상태이고 이때 CPU자원이 다른 프로세스로 이동하는 것은 CPU 자원을 빼앗긴 것이다.  그래서 대기 상태로 전환되거나 종료될 때, 준비상태로 전환이 될 때 프로세스에 CPU 자원 할당이 이루어 지고 이때 어떤 프로세스에 자원을 할당할지 결정하는 알고리즘이 CPU 스케줄링이라고 할 수 있다.

 

선점(Preemptive) 스케줄링

한 프로세스가 CPU를 차지하고 있을 때, 다른 프로세스가 현재의 프로세스를 중지시키고, CPU를 차지할 수 있도록 하는 방법이다. 긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용하다.

 

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

일단 CPU가 한 프로세스에 할당되면, 프로세스가 종료하던가, 또는 대기상태로 전환해 CPU를 해제할 때까지 CPU를 점유하는 방법이다. 모든 프로세스에 대해서 공정한 처리가 가능하지만 긴급 응답을 요하는 작업에는 좋지 못하다. 짧은 작업이 긴 작업이 끝날때까지 기다리는 문제점(Convoy Effect)이 생길 수 있다

 

*Convoy Effect: 하나의 큰 프로세스가 자원을 오랫동안 독점 하는 동안 작은 프로세스들이 자원을 할당받지 못하는 현상. 같은 중요도라고 가정했을 때 작은 프로세스들이 먼저 자용하고 그 다음 큰 프로세스가 사용하는 것이 성능상 유리하다.

 

반응형

CPU 스케줄링 종류

FCFS(First-Come, First-Served) 스케줄링

Ready Queue에 들어온 순서대로 CPU를 할당한다. 먼저 들어온 프로세스가 CPU 자원을 모두 사용한 뒤 다음 프로세스에 할당하므로 비선점형 스케줄링에 해당된다.

 

장점: 구현이 가장 간단하고 처리 순서가 명확하다.

단점: Convoy Effect가 생길 수 있다.

 

 

SJF (Shortest Job First) 스케줄링 (최소작업 우선)

Ready Queue에 있는 작업 중 작은 프로세스(처리 시간이 짧은 프로세스)부터 자원을 할당받는다. 선점형과 비선점형으로 나뉜다.

비선점형은 할당받을 당시에 Ready Queue에 있는 프로세스 중 처리시간(Burst)이 가장 작은 프로세스가 자원을 할당 받고 이 프로세스가 모두 끝난 후에 다른 프로세스에게 자원을 할당한다.

선점형은 할당받을 당시엔 Burst가 가장 작은 프로세스가 자원을 할당 받았지만, 작업중에 Ready Queue에 들어온 프로세스가 남은 Burst보다 더 작은 Burst를 가진다면 자원을 빼앗아 짧은 작업부터 처리하는 방식이다. Average waiting time이 줄언든다.

비선점형은 Non Preemptive SJF라고도 불리나 SRF(Shortest Remaining Time First) 스케줄링이라고 다른 이름을 사용하기도 한다.

 

장점: 최소의 Average Waiting Time을 실현할 수 있다.

단점: *Starvation이 생길 수 있다.

해결법: *Aging

현실적 문제점: 처리 시간은 실제로 프로세스를 돌려봐야 정확히 알 수 있다.

 

*Starvation: 우선순위가 가장 작거나 처리시간이 긴 프로세스가 자원을 계속 할당받지 못하는 문제로써 SJF, SRF에선 처리시간이 짧은 프로세스가 먼저 자원을 할당 받으므로 처리시간이 작은 프로세스가 계속 Ready Queue에 들어올 경우 처리시간이 긴 프로세스는 오랫동안 대기 했음에도 불구하고 계속 자원을 할당받지 못하는 문제가 생긴다.

 

*Aging: Ready Queue에 있는 프로세스에 나이를 부여하는 방법이다. 얼마나 오래 기다렸는가를 고려하여 처리시간이 긴 프로세스임에도 기다린 시간이 길다면 자원을 할당해 준다.

 

 

Priority 스케줄링 (우선순위 스케줄링)

Ready Queue에 들어온 프로세스 중 우선순위가 높은 프로세스가 먼저 CPU 자원을 할당받는 방법이다. 우선순위가 높은 실행중인 프로세스가 작업을 마치고 나면 Ready Queue에서 다음으로 우선순위가 높은 프로세스가 CPU자원을 할당받게 된다. 이 방법은 선점형과 비선점형 방법 모두 적용할 수 있다. 또한 계속해서 우선순위가 높은 프로세스가 자원을 할당 받을 수 있어 Starvaion이 생길 수 있다.

Round Robin 스케줄링

라운드 로빈 스케줄링은 프로세스가 자원을 할당받고 동작할 시간을 할당받는 방식이다.  이떄 라운드 로빈의 Ready Queue는 원형 큐로 설계되어 있어서 프로세스가 시간을 다 쓰면 OS가 인터럽트를 걸어 현재 PCB가 큐의 가장 뒤로 가는 방식이다.

 

장점:

모든 프로세스가 공정하게 시간을 할당받기 때문에 Starvaion이 발생하지 않는다. 

프로세스의 최악의 응답시간을 아는 데에 용이하다.

 

단점:

하드웨어 타이머가 필요하다.

작업 시간 할당을 너무 짧게 하면 Context Switching이 자주 일어나 오버헤드가 일어난다.

 

MLQ (Multi Level Queue) 스케줄링

작업들의 여러 종류의 Ready Queue로 구분하여 스케줄링하는 기법으로 각 Ready Queue마다 독자적인 스케줄링 알고리즘을 사용하여 CPU를 할당한다. 모든 프로세스가 단순히 작업시간이나 대기시간만으로 우선순위를 정할 만큼 동일한 중요도를 가지는 것은 아니다. MLQ 알고리즘은 작업시간과 대기시간만을 고려한 단순한 우선순위 할당보다 작업 자체의 우선순위를 고려하는, 좀 더 고도화된 스케줄링 기법이다.

MFQ (Multilevel Feedback Queue) 스케줄링

MLQ 스케줄링 보다 좀 더 고도화된 알고리즘으로, 정확한 개념은 아니지만 쉽게 설명하자면, MLQ에서 생길 수 있는 Starvation을 보완한 스케줄링 기법이다. MLQ처럼 중요 작업을 무조건 높은 우선순위로 분류할 경우 덜 중요한 작업들은 작업 시간이 짧든 길든 CPU자원을 오랫동안 할당받지 못하는 문제가 생길 수 있다. SJF에서 작업시간이 긴 프로세스가 자원을 할당받지 못하는 문제와 같은 맥락이다.

 

이를 해결하기 위해 중요도 별로 여러 Ready Queue를 두되 각 Ready Queue마다 할당 시간을 부여하여 Ready Queue를 비선점형으로 운용하는 알고리즘이다. MLQ와 Round Robin 기능이 결합된 스케줄링이라고 할 수 있다.