프로세스 스케줄링 알고리즘

스케줄링 방식

1. 비선점 스케줄링 : 프로세스가 (실행 > 대기),  (실행 > 종료) 로의 상태전이가 있을 때 적용됨

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법. 

선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적다. 

일괄처리 시스템에 적합하고, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점도 있다. 

 

2. 선점 스케줄링 : (실행 > 대기), (실행 > 준비), (대기 > 준비), (수행 > 종료) 모든 상태변화에서 적용됨 

하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법. 

모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있으며, 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다. 

 

 

비선점형 스케줄링 알고리즘 : FCFS SJF HRN

 

1. FCFS(First Come Fisrt Served) 스케줄링

: 프로세스들은 대기 큐에 도착한 순서에 따라 중앙처리장치를 할당받으며, 일단 프로세스가 중앙처리장치를 차지하면 완료될 때까지 CPU를 점유하며 수행된다. 

 

 

 

2. SJF(Shortest Job First) 스케줄링

: 기다리고 있는 프로세스 중에서 수행시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식이다.

문제점은 수행될 프로세스나 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보를 얻기가 어렵다는 점이다. 

 

3. HRN(High Response ratio Next) 스케줄링

: SJF의 약점, 특히 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법으로서 일단 한 작업이 중앙처리장치를 차지하면 그 작업은 완성될 때까지 실행하며, 대기시간이 고려되어 긴 작업과 짧은 작업 간의 불평등을 어느 정도 완화시킨다. 

 

선점형 스케줄링 알고리즘 : SRT RR MQ

 

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

: SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시분할 시스템에서 유용하다.

SJF에서는 한 번 작업의 처리가 시작되면 완료될 때까지 계속 실행되지만, SRT에서는 실행 중인 프로세스가 선점될 수 있다. 

 

2. RR(Round Robin)

: 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다.

 

(==) 같은말로, 컴퓨터 운영에서, 컴퓨터 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 한 방법으로서, 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이라 풀어 말할 수 있겠습니다.

 

보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. 

문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하고, 할당되는 시간이 클 경우 비선점 FCFS 기법과 같아지게 된다. 

 

3. 다단계 큐(Multilevel Queue) 스케줄링

: 작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법으로, 전면작업(foreground job : 대화식) 프로세스들과 후면작업(background job : 일괄처리) 프로세스들로 나눈다. 

우선순위 전면작업 > 후면작업