[컴퓨터 공학] 스케줄링 알고리즘

1. Scheduling Algorithm

- 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업

 

 

2. Non-Preemptive

SJF (Shortest Job First)

- 최단 작업 우선 스케줄링은 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당
- 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘
- 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보되어 기아 상태가 발생할 수 있음 
- 대기 상태에 있는 프로세스의 요구시간에 대한 정확한 자료를 얻기 어려움.
- 단기 스케줄링 보다는 장기 스케줄링에 유리

 

 

FCFS (First Come First Serve)

- 선입 선처리 스케줄링은 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해 주는 방식
- CPU 스케줄링, 디스크 스케줄링 등에서 사용

 

 

 

HRRN (Highest Response Ratio Next)

- 최상 응답 비율 순서 스케줄링은 프로세스 처리의 우선 순위를 CPU 처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정
- SJF 스케줄링의 문제점을 보완해 개발된 스케줄링

HRRN 공식

 

 

3. Preemptive

PS (Priority Scheduling)

- 각 프로세스에 우선순위 번호를 부여하고 CPU는 우선순위가 높은 프로세스를 실행

 

 

RR (Round Robin)

- 시분할 시스템을 위해 설계된 선점형 스케줄링
- 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당
- 보통 시간 단위는 10 ms ~ 100 ms 정도이며 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려남
- 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리

 

 

MFQ (MultiLevel Feedback Queue Scheduling)

- 다단계 큐 스케줄링은 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여
- 각각의 큐에 대해 다른 스케줄링 알고리즘을 적용하기도 함
- 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있음
- 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용

 

 

MLQ (MultiLevel Queue Scheduling)

- 항목은 삽입 시 특정 레벨에 할당되므로(미리 정의된 알고리즘을 사용하여) 다른 레벨로 이동할 수 없음

- 항목은 레벨에서 모든 항목을 제거한 다음 다음 레벨로 이동하여 큐에서 제거

- 항목이 위의 레벨에 추가되면 fetching이 거기에서 다시 시작됨
- 큐의 각 레벨은 자체 스케줄링을 자유롭게 사용할 수 있으므로 단순히 큐에 여러 레벨을 갖는 것보다 더 큰 유연성을 추가함