[운영체제] CPU Scheduling 기법 종류

CPU 스케줄링

: 여러 프로세스들이 번갈아 사용해야 하는 CPU(자원)이 있을 경우, 주어진 시점에서 어떤 프로세스가 CPU를 사용할 수 있도록 해 줄 것인가를 결정하는 것

 

스케줄링 기법들은 크게 비선점 / 선점 방식으로 분류된다.

 

 

비선점(Nonpreemptive) 스케줄링

: 한 프로세스가 CPU를 할당받았을 때 CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방법

 

1. FCFS(First Come First Service) 스케줄링

• 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해주며, CPU를 할당받은 프로세스는 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용한다.
• 뒤에 있는 프로세스들은 오래 기다려야 하므로 대화식 시스템에 적합하지 않으며, 평균 응답 시간이 길어지는 단점이 있다.
• 도착 순서만이 실행 순서를 결정짓는다는 관점에서 공평하다고 할 수 있다.

 

2. SPN(Shortest Process Next) 스케줄링

• 준비 큐에서 기다리고 있는 프로세스 중에서 가장 CPU 요구량이 적은 것을 먼저 실행시켜 주는 방식
• 평균 응답 시간을 최소화할 수 있으나, 실행 시간이 긴 프로세스가 CPU를 할당받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있다.

 

3. HRRN(Highest Response Ratio Next) 스케줄링

• 준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio)이 가장 높은 프로세스에게 높은 우선순위를 주는 방식
• 응답률 = (대기시간 + CPU 요구량) / CPU 요구량
• SPN과 SRT 방식의 약점인 수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법

 

 

 

선점(Preemptive) 스케줄링

: CPU를 할당받아 실행 중인 프로세스로부터 CPU를 선점하여 다른 프로세스에 할당할 수 있는 방식

 

1. SRT(Shortest Remaining Time) 스케줄링

• 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식
• 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우, 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당한다.
• SPN 방식과 같이 무한 대기 현상 발생 가능성 문제가 있다.
• 완료까지 남은 실행 시간의 계산, 실행 시간이 짧은 프로세스가 자주 도착할 경우 잦은 선점으로 인한 문맥교환의 부담이 있다.

 

2. 라운드 로빈(Round-Robin) 스케줄링

• FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기(시간 할당량)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 방식
• CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU를 할당받게 된다.
• 시간 할당량이 클수록 FCFS 스케줄링 방식과 같아지게 된다.
• 시간 할당량이 작을수록 문맥교환이 자주 발생하므로 문맥교환의 오버헤드가 커진다.

 

3. 다단계 큐(Multi-level Queue) 스케줄링

• 프로세스들의 우선순위 개수만큼의 큐가 필요하다
• 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏긴다.