Skip to main content

3. 스케줄링 알고리즘

1. 스케줄링 평가 기준​

스케줄링 알고리즘의 성능은 보통 평균 대기시간과 평균 반환시간으로 평가한다.

  • 평균 대기시간: 프로세스가 실행되기 전까지 준비 큐에서 머무른 시간의 평균
  • 평균 반환시간: 프로세스가 생성된 시점부터 종료될 때까지 걸린 전체 시간의 평균

2. FCFS (First-Come First-Served)​

비선점 방식으로, 도착한 순서대로 실행된다. 구조는 단순하지만 짧은 작업이 긴 작업을 기다리는 문제가 발생해 대화형 환경에는 적합하지 않다.

3. SJF (Shortest Job First)​

비선점 방식으로, 준비 큐에서 예상 실행시간이 가장 짧은 작업을 우선 실행한다. 평균 대기시간이 짧아 효율은 좋지만 실행시간 예측이 어렵고, 긴 작업이 계속 후순위로 밀릴 위험이 있다.

4. SRT (Shortest Remaining Time)​

선점 방식이며, 현재 실행 중인 작업을 포함해 남은 실행시간이 가장 짧은 프로세스를 우선으로 한다. 대기·반환시간 측면에서는 SJF보다 효율적이지만, 잦은 선점으로 문맥교환 비용이 커질 수 있다.

5. RR (Round Robin)​

선점 방식이며, 일정한 시간 할당량(time quantum) 동안만 실행한 뒤 준비 큐 맨 뒤로 이동한다.

  • 시간 할당량이 너무 길면 FCFS처럼 동작하고
  • 너무 짧으면 문맥교환이 과도하게 증가한다.

대화형 시스템에서 공정성을 높이는 데 자주 사용된다.

6. HRN (High Response Ratio Next)​

비선점 방식이며, 다음의 응답비율(Response Ratio) 이 가장 높은 프로세스를 실행한다.

응답비율(Response Ratio) = (대기시간 + 서비스시간) / 서비스시간

서비스시간(예상 실행시간)이 짧을수록, 대기시간이 길수록 우선순위가 증가한다.
SJF의 불공정성 문제(긴 작업의 starvation)를 개선한 방식이다.

7. 다단계 피드백 큐 (Multi-level Feedback Queue)​

선점 방식이며, 프로세스의 특성에 따라 여러 우선순위 큐로 단계별 배치가 이뤄진다.

  • 입출력 중심 프로세스: 짧은 시간할당량을 가진 상위 큐
  • CPU 연산 중심 프로세스: 더 긴 시간할당량을 가진 하위 큐

실행 과정에서 우선순위가 동적으로 변하며, 대화형 시스템 대응 능력이 높다.
(정확한 정책은 OS마다 다르게 정의됨.)

이 시리즈의 모든 포스팅은 직접 수업과 교재를 통해 학습한 내용을 토대로
손으로 정리한 후, AI를 이용해 구조 정리와 맞춤법만 다듬은 자료입니다.