CPU 스케줄링과 알고리즘

저번에 PCB에 CPU 스케줄링 정보가 저장된다고 했는데 CPU 스케줄링이 뭔지 CPU 스케줄링에 대해서 알아보자.

 

https://seungjjun.tistory.com/226

프로세스란? (PCB, Context Switching)

 

CPU 스케줄링이란?

우선 저번 포스팅에서 모든 프로세스는 실행을 위해 CPU가 필요하기 때문에 운영체제로 부터 CPU 자원을 할당받아야 한다고 배웠었다. 

모든 프로세스들은 자신이 먼저 자원을 할당받아 먼저 실행되기를 원할텐데 어떻게 각각 프로세스에게 CPU를 공평하게 할당을 해야 할까??

 

이에 대한 해결방법으로 프로세스들에게 공평하게 CPU 자원을 할당하는 것을 CPU 스케줄링이라고 한다.

 

CPU 스케줄링에는 선점형 스케줄링과 비선점형 스케줄링이 있다.

 

선점형 스케줄링

선점형 스케줄링은 프로세스가 CPU 자원을 할당받아 실행 중에 있어도 운영체제가 프로세스로부터 자원을 빼앗아서 다른 프로세스에게 자원을 할당해 프로세스의 실행 순서를 변경하는 방법을 의미한다.

 

프로세스마다 CPU의 자원을 사용할 수 있는 정해진 시간이 있는데, 이 시간이 지나면 다른 프로세스에게 할당하는 방식도 선점형 스케줄링이다.

 

장점

우선순위가 높은 프로세스부터 빠르게 처리하고, 특정 프로세스가 자원을 독점하는 막을 수 있다.

 

단점

우선순위가 높은 프로세스가 많아 자원을 자주 교체(context switching)하면 오버헤드가 발생한다.

 

프로세스에는 우선순위가 있는데 운영체제는 우선순위가 높은 프로세스부터 자원을 할당하고 처리한다.

 

비선점형 스케줄링

비선점형 스케줄링은 선점형 스케줄링과 다르게 자원을 한번 할당받으면 해당 프로세스가 종료되거나 대기 상태가 되기 전까지는 다른 프로세스가 자원을 이용할 수 없는 방법을 의미한다.

 

장점

선점형 스케줄링에 비해 context switching의 횟수가 적어 오버헤드가 발생할 확률이 낮다.

 

단점

작업이 긴 프로세스가 짧은 프로세스보다 먼저 자원을 할당받을 경우 긴 시간을 기다려야 하므로 자원을 효율적으로 이용할 수 없다.

 

스케줄링 알고리즘

운영체제가 사용하는 스케줄링 알고리즘의 종류는 여러 개가 있는데 대표적인 몇 가지만 알아보자.

우선 스케줄링의 대상은 준비 큐(Ready Queue)에 있는 프로세스들이라는 것을 알고자 가자.

 

FCFS(First Come First Served) 스케줄링

선입 선처리 스케줄링이라고도 불리는 FCFS 스케줄링 알고리즘은 먼저 준비 큐에 들어온 프로세스부터 CPU를 할당하는 간단한 방식이다. (비선점형)

 

해당 스케줄링 방식은 프로세스들이 기다리는 시간이 길어질 수 도 있다는 단점이 존재한다. (CPU를 이용하는 시간이 짧은 것보다 긴 프로세스가 먼저 들어온 경우) -> 호위 효과

 

https://hyuntaekhong.github.io/blog/OperatingSystem03/

 

SJF(Shortest - Job - First) 스케줄링

최단 작업 우선 스케줄링이라고도 불리는 SJF 스케줄링은 FCFS 스케줄링의 단점인 호위 효과를 방지하는 알고리즘이다. 

무슨 말이냐면 준비 큐에 있는 프로세스들 중에서 CPU 사용시간이 가장 짧은 프로세스부터 실행하는 방식이다. (비선점형)

 

언뜻 보기에는 소요시간이 짧은 프로세스부터 처리하니 효율적으로 보이지만 사용 시간이 긴 프로세스는 영원히 CPU의 할당을 못 받을 수도 있다는 문제점이 있다. -> 기아 현상 (starvation)

 

SRT(Shortest Remaining Time) 스케줄링

최소 잔여 시간 우선 스케줄링이라고도 불리는 SRT 스케줄링은 SJF 스케줄링을 선점형 방식으로 구현한 알고리즘이라고 생각하면 된다.

우선 작업 시간이 가장 짧은 프로세스부터 처리를 하는데 각 프로세스마다 CPU를 사용할 수 있는 시간(타임 슬라이스)이 지나면 준비 큐의 맨 뒤로 이동하고 다음으로 작업 시간이 짧은 프로세스를 실행하는 방식이다. (선점형)

 

Round Robin 스케줄링

라운드 로빈 스케줄링은 위에서 언급한 타임 슬라이스를 이용한 선점형 스케줄링이다.

각 프로세스는 CPU를 사용할 수 있는 정해진 할당 시간을 갖게 되는데 해당 시간이 지나면 준비 큐의 맨뒤로 가게 된다. (context switching)

 

이러한 라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 아주 중요하다. 너무 짧으면 context switching이 너무 자주 일어나게 돼서 오버헤드가 발생할 수 있고, 또 너무 크면 FCFS 스케줄링 방식과 동일해져 호위 효과가 발생할 수 있다.

 

 

우선순위 스케줄링 

우선순위 스케줄링은 말 그대로 우선순위가 가장 높은 프로세스부터 처리하는 스케줄링이다. (우선순위가 같다면 FCFS 스케줄링으로 처리)

 

우선순위 스케줄링의 문제점으로도 기아 현상이 발생할 수 있다는 문제점이 있다. 우선순위가 낮은 프로세스가 준비 큐에 먼저 들어와도 우선순위가 높은 프로세스들이 계속 들어오면 실행이 연기될 수 있기 때문이다.

 

기아 현상을 방지하기 위한 대표적인 방법으로 에이징이 존재한다.

에이징이란?

에이징은 준비 큐에 오랫동안 기다린 프로세스의 우선순위를 점점 높여서 기아 현상을 방지하는 방법을 말한다.

 

다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링

다단계 피드백 큐 스케줄링은 준비 큐가 하나가 아니라 여러 개를 사용하는 방식이다. 준비 큐 별로 우선순위를 정해 우선순위가 높은 큐에 있는 프로세스들을 먼저 처리한다.

그리고 여기서도 타임 슬라이스가 존재하는데 프로세스가 첫 번째 큐에서 실행이 끝나지 않으면 다음 준비 큐에 삽입이 된다. 이렇게 실행시간이 긴 프로세스는 우선순위가 점차 낮아지는 방식이다. 

 

이렇게 점점 낮은 우선순위 큐로 이동을 하면 실행시간이 긴 프로세스는 점점 뒤로 밀려 실행 시간이 연기되는 기아 현상이 발생할 수 있기 때문에 에이징 기법을 적용해서 기아 현상을 방지할 수 있다.

 

다단계 피드백 큐 스케줄링은 가장 일반적인 CPU 스케줄링 알고리즘이다.