스케쥴링 - 어떤 프로세스에게 CPU를 줄까요~?

스케줄링이란?

 

하나의 CPU를 여러 프로세스가 번갈아 사용할 때, 어떤 프로세스에게 CPU를 줄 지를 결정하는 것이다. 

ready 상태에 있는 프로세스 중 하나를 선택하는 과정이다. 

먼저 요청한 프로세스에게 줄 지, 우선 순위가 높은 프로세스에게 줄 지 다양한 스케줄링 기법이 존재한다! 

 

스케줄링은 언제 발생하나? 

 

1. running 중인 프로세스가 I/O 요청으로 waiting 상태로 전이될 때

2. running 중인 프로세스가 time out으로 ready 상태로 전이될 때

3. waiting하던 프로세스가 I/O Interrupt로 ready로 전이될 때 (우선순위가 높을 수 있으므로)

4. running 중인 프로세스가 종료되었을때

 

 

 

선점형 스케쥴링 vs 비선점형 스케쥴링 (Preemptive vs Nonpreemptive)

 

선점형 스케쥴링은 위의 그림에서 봤을 때 자발적으로 cpu를 내놓는 1,4 경우에만 스케쥴링을 하는 것

비선점형 스케쥴링은 1,2,3,4 경우 모든 언제든 필요한 때에 스케쥴링을 할 수 있는 것

 

 

스케쥴링 판단 기준 

 

CPU Utilization - CPU 이용률: CPU는 비싼 자원이기에 바쁘면 바쁠수록 좋음

Throughout - 처리율 : 단위시간당 수행을 완료한 프로세스의 수 

Turnaround Time - 반환 시간: 프로세스가 실행되는 시간 

Waiting Time - 대기 시간 : ready queue에 들어오고부터 CPU를 할당받기까지 기다리는 동안의 시간

Response Time - 응답 시간 : 프로세스가 제출된 시점부터 처음으로 응답이 돌아오는 시간

 

CPU 이용률, 처리율은 클수록 좋고, 

반환 시간 은 의미없고, 

대기 시간, 응답 시간은 짧을수록 좋다. 

 

 

스케쥴링 기법

 

• FCFS 
• SJF - 비선점
• SRTF - 선점 SJF
• Priority Scheduling
• Round Robin
• Multilevel Queue
• Multilevel Feedback Queue

 

FCFS:: 도착한 순서대로 CPU 할당

🙂 구현이 간단

😡 긴 작업이 짧은 작업을 기다려 좀비현상 발생

 

SJF - 비선점:: 실행시간이 가장 짧은 프로세스부터 CPU 할당

🙂 평균 waiting Time이 가장 짧음

😡 긴 작업이 무한히 대기하는 기아현상 발생

 

SRTF - 선점 SJF:: 현재 실행중인 프로세스 포함 가장 짧은 실행시간을 가진 프로세스에 CPU 할당

🙂 평균 waiting Time이 짧음

😡 문맥교환이 빈번하여 오버헤드 발생

 

Priority Scheduling:: 우선순위가 높은 프로세스부터 CPU 할당

🙂 중요하거나 긴급한 작업을 우선적으로 처리 가능

😡 우선순위가 낮은 작업의 기아 현상 발생

 

Round Robin:: 각 프로세스에 일정시간(q:Time Quantum)만큼 cpu 할당하고 시간이 지나면 다음 프로세스로 전환

🙂 CPU를 공정하게 나누어 사용할 수 있음

😡 타임 퀀텀이 너무 짧으면 오버헤드 발생 (문맥 교환)

 

Multilevel Queue:: 여러 개의 큐에 다른 스케쥴링 기법을 적용

🙂 작업에 맞는 다양한 스케쥴링 전략 사용 가능

😡 큐 간의 프로세스 이동이 제한적

 

Multilevel Feedback Queue:: 프로세스가 우선 순위와 실행 시간을 기준으로 여러 큐를 순회

🙂 동적 우선순위 조정으로 모든 프로세스가 공정하게 처리

😡 구현과 관리가 복잡