[Operating System] CPU Scheduling

CPU Scheduling

CPU는 여러 작업을 동시에 수행할 수 없지만, 처리해야할 작업(Process)은 다수이기 때문에, 적절한 스케쥴링을 통해서 작업을 수행한다.(멀티 코어 CPU인 경우 여러 작업을 동시에 처리할 수 있지만, 단일 코어로 가정한다)

 

아주 단순한 스케쥴링으로는 먼저 들어온 작업이 수행되는 것이다. 

하지만, 빨리 처리해야하는 작업이 오래 기다릴 수 있고 처리에 아주 짧은 시간이 소요되는 작업도 다른 작업에 밀려서 오래 기다려야하는 비효율이 발생할 수 있다.

 

따라서, CPU 스케쥴링은 다양한 알고리즘을 적용해서 합리적으로 작업을 수행한다.

 

비선점형 스케쥴링

어떤 프로세스가 다른 프로세스가 점유 중인 CPU를 사용할 수 없다.(가로챌 수 없다.)

즉. 먼저 작업 중이던 프로세스가 CPU를 놓아야만 다른 프로세스가 CPU를 점유할 수 있다.

 

FCFS

• 가장 먼저 요청한 프로세스를 가장 먼저 수행함(First Come First Served)
• 장점: 구현이 간단하며, 예측이 용이하다.
• 단점: 프로세스들의 평균 대기 시간이 길어질 수 있다. 사용 시간이 긴 작업이 처리 되고 있으면 다른 프로세스는 오래 대기해야한다.

SJF

• 예상 CPU 시간이 짧은 프로세스부터 먼저 수행함(Shortest Job First)
• 선점, 비선점 둘다 가능
• 장점: 프로세스들의 평균 대기 시간을 줄일 수 있다.
• 단점: CPU 점유 시간을 미리 알아야 하고, 긴 작업이 계속 배제되는 기아 현상이 발생할 수 있다.

Priority

• 프로세스에 대해서 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 수행함
• 선점, 비선점 둘다 가능
• 장점: 중요한 작업(프로세스)을 빠르게 처리할 수 있다.
• 단점: 우선순위가 낮은 작업이 계속 처리되지 않아 기아현상이 발생할 수 있다.

HRN

• 대기 시간과 예상 실행 시간을 종합해서 우선순위를 정해 작업을 처리하는 방식(Highest Response Ratio Next)
• 장점: SJF보다 기아 현상이 완화된다.
• 단점: 예상 실행 시간이 정확하지 않으면 성능 저하가 발생할 수 있다.

 

선점형 스케쥴링

RR

• 각 프로세스에 동일한 타임 슬라이스를 부여 받고, 일정 시간이 지나면 CPU를 다른 프로세스로 교체하는 방식(Round Robin)
• 장점: 공정성이 높고, 응답 시간이 중요한 시분할 시스템에 적합하다.
• 단점: 타임 슬라이스가 너무 짧으면 오버헤드가 증가하고, 너무 길면 응답성이 떨어진다.

SRTF

• SJF 알고리즘의 선점형. 실행 중 새로운 프로세스가 도착하면 가장 남은 실행시간이 짧은 프로세스에 CPU를 할당한다.(Shortest Remain Time First)
• 장점: 평균 대기 시간을 단축시킬 수 있다.
• 단점: 자주 컨텍스트 스위칭이 발생해 오버헤드가 높고, 기아 현상이 발생할 수 있다.

Multi-level & Multi Feedback Queue

• 여러 개의 준비 큐를 우선순위 별로 나누고 각 큐에 다른 스케쥴링 방식을 적용. 피드백 큐는 프로세스가 오랫동안 실행될수록 점차 우선순위가 낮아짐
• 장점: 다양한 유형의 프로세스를 유연하게 처리할 수 있다.
• 단점: 알고리즘 설계가 복잡하고 튜닝이 필요하다.