# 04. CPU 스케줄링

1. CPU 스케줄링이란

 

정의

• 작업을 처리하기 위해서 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 것이다.
• 어떤 프로세스에 CPU를 배정할지 결정하고, 이 작업은 컴퓨터 시스템의 효율에 직결되는 중요한 일이다.

 

목적

• 공평성, 효율성, 안정성, 반응시간 보장, 무한 연기 방지

 

 

 

 

  2. 선점형 vs 비선점형 스케줄링

 

선점형 스케줄링

• 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식
• CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하다.
• 하지만 잦은 문맥 교환으로 오버헤드가 많이 발생한다.

 

 

비선점형 스케줄링

• 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식
• 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다.

 

 

 

  3.  스케줄링 알고리즘

 

FCFS

• 선입선출. 비선점형. 한업이 기다려서 비효율적.

 

 

 

SJF (shortest job first)

• 실행시간이 짧은 것부터. 비선점형. 단 더 짧아도 cpu 사용중인걸 뺏지는 못함. 기아현상.

 

 

 

HRN (highest response ratio next)

• SJF + Aging. 비선점형. 
• Aging : 나이를 먹는다는 의미 그대로 starvation을 해결하기 위해 대기 시간이 길어지면 우선순위를 높여주는 방법이다.

 

 

 

SRTF (shortest remaining time first)

• SJF 의 선점형 방식. 먼저 온 프로세스가 CPU를 할당받고 있더라도 남은 처리 시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗긴다.
• 평균 대기 시간이 가장 짧음. 
• 잦은 문맥 교환과 기아현상이 심각하게 발생.
• 실제로 사용 어려움.

 

 

 

Priority 스케줄링

• 프로세스의 중요도에 따라 매긴 우선순위를 반영. 
• 기아 현상, 공평성 문제

 

 

 

RR (round robin)

• 프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 한다. 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘긴다. 빼앗긴 프로세스는 준비 큐의 맨 뒤로 간다. 따라서 선점형 방식이다.
• 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다.
• 타임 슬라이스가 큰 경우 처리 시간이 긴 프로세스에 의해 CPU의 효율성이 떨어질 수 있다. 비디오 플레이어와 워드 프로세서를 동시에 실행했을 때 타임 슬라이스가 크다면 비디오가 약간 씩 끊겨서 재생될 것이다. 그리고 만약 타임 슬라이스가 무한대로 설정되면 FCFS 스케줄링과 다를 바 없어진다.
• 타임 슬라이스가 작은 경우 여러 프로그램이 동시에 실행되는 효과를 볼 수 있다. 하지만 너무 작으면 잦은 문맥 교환이 일어나 오버헤드가 상당히 커진다.

 

 

 

Multilevel queue 스케줄링

• 우선순위 스케줄링과 라운드로빈(RR) 스케줄링을 결합한 알고리즘이다.
• 여러 종류의 작업을 처리해야 하는 경우 적합한 방식으로, 작업의 중요도, 작업의 특성에 따라 분류하여 CPU를 할당하며 그룹마다 다른 스케줄링을 적용하기도 한다.

 

 

 

Multilevel Feedback quqe 스케줄링

• 프로세스가 큐들 사이를 이동하는 것을 허용하는 알고리즘으로 선점형에 해당한다.
• 현재 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다.