[OS] - CPU 스케줄링

프로세스?

- 프로세스를 구동하기 위해서는 다양한 자원이 필요하다.

- 이에 대한 효율적인 배분을 위해서 상황에 맞는 자원을 각각의 프로세스에게 분배할 필요가 있다.

- 그러면 이러한 효율적인 배분이 왜 필요한 것일까?

프로세스의 생명주기

- 효율적인 배분이 필요한 이유는 프로세스의 Waiting 상태가 존재하기 때문이다.

- Waiting 상태의 프로세스에게 자원을 배분하면, 낭비가 이루어지기 때문에 이를 효율적으로 관리하기 위해 스케줄링을 하는 것이다!

- 결국, "어떻게 프로세스들이 CPU를 효율적으로 사용할 것인가? " 에 대한 답을 끌어내기 위해서다

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

º Running 상태에서 Waiting 상태로 전환 되었을 때 

º Running 상태에서 Ready 상태로 전환 되었을 때

º Waiting 상태에서 Ready 상태로 전환 되었을 때

º Terminated 상태로 들어 왔을 때

> 단, Running상태에서 스케줄링이 일어나지는 않는다.

- CPU 스케줄러가 dispatcher에게 명령을 내려서 PCB에 대한 정보를 Context Switch 한다!!

스케줄링 기법

- 선점(preemptive) 스케줄링 : 다른 프로세스가 선점하고 있는 자원을 빼았아서 가져오는 방식

- 비선점(Non-Preemptive) 스케줄링 :  어떤 프로세스가 자원을 선점하고 있다면, 빼았지 못하게 하는 방식

- FCFS(First Come First Served) 스케줄링 : Ready Queue에 들어온 순서대로 프로세스에게 자원을 할당한다.

    * 장점 : 구현이 간단하고, 처리과정이 명확하다.

    * 단점 : Convoy Effect가 발생할 수 있다.

> Convoy Effect ?

 - 하나의 큰 프로세스가 오랫동안 자원을 독점하여, 다른 프로세스가 자원을 할당받지 못하는 효과

- SJF(Shortest Job First) 스케줄링 : Ready Queue에 있는 작업 중에서 수행시간이 짧은 프로세스를 먼저 할당하는 방식

     * 선점형과 비선점형으로 나뉘어진다! But, 이 방식은 치명적인 단점이 존재한다.

     * Starvation(기아 현상) : 처리시간이 긴 프로세스는 영원히 자원을 받지 못한다.

      -> 해결방법 ? Aging 기법을 통해서 해결한다!

- HRN(Highest Response ratio Next) 스케줄링 : 처리시간 + 대기시간을 고려하여 우선순위를 정한다! 

     * 일반적으로 비선점형이다.

- MLQ(Multi Level Queue) 스케줄링 : 5개의 Ready Queue로 구성하여 선점형 배분방식으로 자원을 할당한다.

     * 각각의 작업에 대하여 우선순위를 결정하여 프로세스에게 자원을 할당한다.

- MFQ(MultiLevel Feedback Queue) 스케줄링 : MLQ에서 생기는 Starvation을 보완한 스케줄링 기법이다.

     * 일반적으로 비선점형 방식이다.  

 

참고

CPU 스케줄링 알고리즘