[OS] 스케줄링 종류

목차

• 비선점 스케줄링
• FCFS
• SJF
• HRN
• 우선순위
• 선점 스케줄링
• SRTF
• 선점 우선순위 스케줄링
• 라운드로빈 스케줄링

---

비선점스케줄링

• 이미 할당된 CPU를 다른 프로세스가 강제로 뺏을 수 없는 정책
• 프로세스가 자원 할당 받으면, 스스로 반납할 때 까지 사용을 허용한다.

특징

• 일괄 처리 방식의 스케줄링
• 응답 시간 예측이 용이
• 공정한 자원의 할당

단점

• 중요한 작업을 먼저 수행할 수 없다.

FCFS (선입 선처리 스케줄링)

• First Come First Service
• 큐에 도착한 순서에 따라 CPU를 할당한다.
• 호위 효과(convoy effect): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것

---

SJF (최단 작업 우선 스케줄링)

• Shortest Job First
• 버스트 시간( 실행 시간 ) 이 짧은 프로세스부터 CPU 할당
• 버스트 시간이 짧을수록 우선순위가 높다고 볼 수 있음
• 버스트 시간 같으면 FCFS( 선입 선출 ) 스케줄링
• 선점형 SJF 알고리즘은 최소 잔여시간 우선 스케줄링 ( SRTF, Shortest Remaining Time First Scheduling ) 라고 한다.

---

HRN

• Highest Response Ratio Next
• 짧은 작업에 유리한 SJF의 단점을 개선하여 우선순위로 서비스한다.
• 우선순위 계산 결과 값이 높은 것부터 수행한다.
• 대기 시간이 길수록 우선순위가 점점 높아진다. (aging)
• 우선순위 : ( 대기시간 + 서비스시간 ) / 서비스시간

---

우선순위 (Priority)

• 우선 순위가 높은 작업이 먼저 CPU를 사용한다.
• 시간 제한, 메모리 요구량, 열린 파일의 수, 프로세스의 중요성, 자원사용 비용 등 으로 우선순위 정의된다.
• 우선순위 알고리즘은 선점형, 비선점형 둘다 가능
  • 문제점
    • 기아 ( Starvation ) : 우선순위가 낮은 프로세스가 계속 뒤로 밀리면서 무기한 대기를 하는 것
  • 해결방법
    • 노화 ( Aging ) : 기아(Starvation) 현상을 방지하기 위해 일정시간 마다 우선순위를 높여서 노화 시키는것

---

선점 ( Preemptive ) 스케줄링

• 우선순위가 높은 다른 프로세스가 실행 중인 프로세스의 CPU 뺏을 수 있다.
• 빠른 응답을 요구하는 대화식 시분할 시스템에 사용됨
• 선점한 프로세스에게 일정 시간을 배당하기 위한 인터럽트 타이머가 필요
• 많은 오버헤드 초래할 수 있음

SRTF

• Shortest Remaining Time First
• 선점형 SJF 스케줄링
• 진행 중인 프로세스가 있어도 Sleep시키고 최단잔여시간 프로세스에 우선권 부여

---

선점 우선순위 스케줄링

• 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점

---

라운드 로빈 스케줄링 (RR)

• 시분할 시스템을 위해 설계되었다.
• 준비완료 큐는 원형 큐로 동작
• 대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다.
• CPU를 사용할 수 있는시간( Time Slice or Time Quantum ) 동안 CPU를 사용한 후에 다시 대기 큐에 배치하여 대기한다.
• 할당되는 시간이 작을수록 문맥 교환 및 오버헤드가 자주 발생된다.