[운영체제] 3. 스케줄링 알고리즘

1. 스케줄링 평가 기준

일반적으로 스케줄링 알고리즘의 성능을 평가하는 데에는 평균 대기시간과 평균 반환시간이 사용된다.

• 평균 대기시간: 프로세스의 수행이 완료될 때 까지 준비 큐에서 기다리는 시간의 평균
• 평균 반환시간: 프로세스가 생성된 시점부터 반환되는 시점까지 걸린 시간의 평균

2. FCFS (First-Come First-Served)

비선점 알고리즘이며, 먼저 온 프로세스가 먼저 실행되는 알고리즘이다. 짧은 작업이 긴 작업을 기다리거나 중요한 프로세스가 나중에 실행될 수도 있다는 점에서 대화형 시스템에는 적합하지 않다.

3. SJF (Shortest Job First)

비선점 알고리즘이며, 준비 큐에서 기다리는 프로세스 중 예상 실행시간이 가장 짧은 것이 먼저 실행된다. 예상 실행시간을 예측하는 것이 쉽지 않고 예상 실행시간이 긴 프로세스는 무한정 대기에 들어갈 수 있는 등 공정성 면에서 문제가 있다.

4. SRT (Shortest Remaining Time)

선점 알고리즘이며, 새로 들어오는 프로세스를 포함하여 남은 실행 시간 추정치가 가장 짧은 프로세스를 디스패치 하여 실행하는 방식이다. 단순 반환시간과 대기시간을 계산하면 SJF 보다 높은 효율성을 보여주지만, 실행상태에 있는 프로세스 교체가 잦다면 잦은 문맥교환이 자주 발생하므로 오버헤드의 위험이 있다.

5. RR (Round Robin)

선점 알고리즘이며, 프로세스가 도착한 순서대로 디스패치 하지만 정해진 시간 할당량에 의해 실행을 제한하고 할당된 시간을 모두 사용한 프로세스는 완료되지 않았더라도 준비 큐의 맨 뒤로 가서 실행을 기다리게 되는 알고리즘이다. 시간간격을 너무 길게 설정하면 FCFS 알고리즘 처럼 성능이 저하되고, 시간 간격을 너무 짧게 설정하면 문맥교환이 너무 빈번하게 발생하여 오버헤드의 위험이 커진다는 문제가 있다.

6. HRN (High Response Ratio Next)

비선점 알고리즘이며, 응답비율이 가장 높은 프로세스를 우선으로 실행하는 비선점 알고리즘이다. 여기서 응답비율이란 예상 실행시간이 짧을수록, 대기한 시간이 길수록 커지는 값이다. 따라서 예상 실행시간이 짧으면 무조건 선순위로 실행되던 SJF 알고리즘의 단점을 개선한 알고리즘이라고 볼 수 있다. 예상 실행시간이 긴 프로세스라도, 너무 오랫동안 대기하게 된다면 응답비율이 높아져 다른 예상 실행시간이 짧은 프로세스보다 우선적으로 처리될 수 있게 된다.

7. 다단계 피드백 큐

선점 알고리즘이며, 입출력 중심인 프로세스와 GPU 중심인 프로세스에 따라 서로 다른 시간 할당량을 부여한다. 연산 위주의 프로세스는 큰 단계에 배치되고, 입출력 위주의 프로세스는 낮은 단계에 위치하게 된다.