CPU 스케줄링 알고리즘

1. CPU 스케줄링

• 정의 : 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업
• 종류

장기 스케줄링	어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정해 준비상태 큐로 보내는작업
중기 스케줄링	어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업
단기 스케줄링	프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업

• 목적: 공정성, 처리율 증가, CPU 이용률 증가, 우선순위 제도 , 오버헤드 최소화, 응답시간 최소화, 반환시간 최소화, 대기시간 최소화, 균형있는 자원의 사용, 무한 연기 회피 등

2. CPU 스케줄링 알고리즘 : 어떤 프로그램에 CPU 소유권을 줄 것인지 결정. CPU 이용률은 높게, 시간당 많은 일을 수행하고, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로한다. 크게 비선점, 선점형 두가지 방식으로 나뉜다.

 

3. 비선점형 방식 : 프로세스가 스스로 CPU 소유권을 포기하는 방식. 강제로 프로세스를 중지하지 않는다. 컨텍스트 스위칭으로 인한 부하가 적다.

FCFS	가장 먼저 온것을 가장먼저 처리하는 알고리즘. 선입선출. 수행 시간이 긴 프로세스 때문에 준비큐에서 오래기다리는 현상(convoy effect)이 발생한다.
SJF	실행시간이 가장 짧은 프로세스를 가장 먼저 실행. 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧다.
HRN(Highest Response-ratio Next, 우선순위)	대기 시간과 서비스시간을 이용해 우선순위를 산정하고 높은 순으로 실행. -> 오래된 작업일 수록 우선순위가 높아진다.((대기시간 + 서비스시간) / 서비스시간)

4. 선점형 방식 : 현대 운영체제가 쓰는 방식으로 프로세스를 강제 중단시킨 후 다른 프로세스에게 CPU 소유권을 할당하는 방식. 많은 오버헤드를 발생시킨다.

라운드 로빈	우선순위 스케줄링의 일종으로 각 프로세스에게 동일한 할당 시간을 주고 그 시간안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘. 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.
SRF	SJF와 비슷한 방식이나 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 강제로 해당 프로세스로 수행하는 알고리즘
다단계 큐	우선순위에 따른 준비큐를 여러개 사용하고, 큐마다 다른 알고리즘을 적용한것. 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어진다.