[OS] 프로세스 스케줄링 알고리즘

지난 포스팅에서 프로세스 스케줄링의 개념에 대해 알아보았는데요.

이번 포스팅에서는 프로세스 스케줄링의 알고리즘에 대하여 알아보겠습니다.

 

스케줄링 알고리즘 

스케줄링 알고리즘의 종류는 아래와 같습니다.

• FCFS
• SJF
• SRT
• RR
• HRN
• 다단계피드백큐

크게 선점과 비선점으로 구분해 보겠습니다.

선점알고리즘 

• RR
• 다단계피드백큐
• SRT

비선점알고리즘

• FCFS
• SJF
• HRN

각각의 알고리즘의 개념과 장단점에 대해 알아보겠습니다.

 

FCFS(First Come First Served)

이름과 같이 준비 큐에 도착한 순서에 따라 디스패치하는 비선점 알고리즘입니다.

장점

가장 간단한 스케줄링 기법입니다.

단점

긴 프로세스가 먼저 들어온 경우 짧은 프로세스가 긴 프로세스의 종료를 기다려야 하는 경우가 발생할 수 있습니다.

또 중요한 프로세스가 나중에 수행되거나 도착순서에 따라 평균 반환 시간이 크게 변화될 수 있어 예측이 어려워 시분할 운영체제나 실시간 운영체제에서는 부적합한 방식입니다.

 

SJF(Shortest Job First)

이름 그대로 가장 짧은 작업을 먼저 수행하는 비선점 알고리즘입니다.

준비큐에 대기하는 프로세스 중 실행시간이 가장 짧을 것으로 예상되는 작업을 먼저 디스패치합니다.

장점

일괄처리 환경에서 구현하기 쉽습니다.

단점

긴 프로세스가 먼저 들어오고 짧은 프로세스가 계속해서 추가된다면 긴 프로세스는 실행이 밀려 계속 대기만 하는 상황이 발생할 수 있습니다.

위와 같은 경우에 중요한 프로세스가 나중에 수행될 수 있어 시분할이나 실시간 운영체제에는 부적합한 방식입니다.

또한 예상 실행시간이 짧은 것을 먼저 디스패치 하지만 실제로는 프로세스의 CPU 시간을 예측하는 것이 불가능하기 때문에 실현되기 어렵습니다.

 

SRT(Shortest Remaining Time)

준비큐에 대기 중인 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 프로세스를 먼저 디스패치합니다.

장점

SJF 알고리즘을 선점방식으로 구현한 것으로 SJF보다 평균대기시간/평균반환시간에서 효율적입니다.

단점

SJF와 마찬가지로 실행예상시간을 알 수 없기 때문에 잔여 실행 예상 시간을 알기 어렵습니다.

또한 SJF보다 오버헤드가 크다는 단점을 가지고 있는데요.

각 프로세스의 실행시간 추적이 필요하고 선점을 위한 문맥교환이 발생하기 때문입니다.

 

RR(Round Robin)

선점 방식 알고리즘입니다.

준비큐에 도착한 순서대로 디스패치 하지만 미리 정해둔 시간 할당량에 의해 실행을 제한하는데요.

시간 할당량 안에 작업을 완료하지 못하면 CPU를 빼앗기게 되고 준비큐의 마지막에 배치됩니다.

 

장점

CPU 독점 없이 공평하게 이용이 가능합니다.

해서 시분할 시스템에 가장 적합합니다.

단점

시간 할당량이 너무 크면 FCFS 스케줄링과 동일하게 작동합니다.

반대로 시간할당량이 너무 작으면 너무 많은 문맥 교환발생해 오버헤드 커지게 되니 적절한 시간 할당량을 정해주는 것이 중요합니다.

 

HRN(Higtest Response Ratio Next)

비선점 방식의 알고리즘입니다.

준비큐에서 대기 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치 하는데요.

응답비율을 구하는 공식은 아래와 같습니다.

결과적으로 오른쪽과 같은 식으로 구할 수 있는데요.

분자값이 클수록, 분모값이 작을수록 전체 값이 커지므로 예상실행시간이 짧을수록, 대기시간이 길수록 응답비율은 커지게되겠죠.

결과적으로 예상시간 짧은 것 먼저 처리함과 동시에 오래 기다린 프로세스들 또한 우선순위를 높여주게 됩니다.

 

 

장점

SJF  스케줄링의 단점을 보완했습니다.

너무 긴 프로세스가 미리 기다리다 보면 짧은 애들이 계속 들어와 밀리는 단점을 보완한 것으로 예상 실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치가 가능합니다.

단점

실제로는 프로세스의 CPU 시간을 예상할 수 없어 실제 적용은 어렵습니다.

 

다단계 피드백 큐 

선점 알고리즘으로 라운드 로빈의 확대 버전입니다.

입출력 프로세스와 연산 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여하는데요.

단계 1부터 n까지 각각의 단 게마다 별도의 준비 큐가 존재합니다.

 

단계별로 시간 할당량도 다른데요.

단계가 커질수록 시간 할당량도 커지게 됩니다.

앞쪽에서는 CPU를 빨리 쓰고 빨리 반환하고 뒤쪽으로 갈수록 CPU를 오래 사용합니다.

 

시간 할당량이 끝나면 같은 단계의 뒤로 가는 것 아니라 다음 단계의 뒤로 가서 붙게 됩니다.

시간 할당량이 끝나도 종료되지 못하면 단계가 점점 높아지게 되겠죠?

한 가지 특징은 실행하려는 단계의 앞단계의 준비큐가 모두 비어있어야 다음 단계 준비큐 내의 프로세스를 디스패치합니다.

 

중요한 점은 입출력 위주 프로세스는 높은 우선권을 유지한다는 점인데요.

입출력 위주는 짧게 쓰고 반환하기 때문에 다음 단계 큐로 넘어가지 않고 같은 단계 큐의 뒤로 붙도록 높은 우선권 유지시켜줍니다.

반대로 연산위주의 프로세스는 우선권은 낮지만 긴 시간 할당량을 가지게 됩니다.

 

알고리즘의 평가 

지난 포스팅에서 프로세스 스케줄링 알고리즘의 평가는 평균대기시간과 평균반환시간을 이용한다고 말씀드렸습니다.

이해를 돕기 위해 FCFS 스케줄링의 평균 반환시간과 대기시간 계산을 해보았는데요.

위의 결과를 바탕으로 대기시간과 반환시간의 평균을 구하면 아래와 같은 결과가 나오게 됩니다.

• 평균대기시간 0+5+9+12 / 4 = 6.5
• 평균반환시간 5+9+12+14 / 4 = 10

위의 그림과 수식을 참고하시어 여러분도 직접 다른 알고리즘의 반환시간과 대기시간을 계산해 보시길 바랍니다.