[OS]CPU 스케줄링 알고리즘

스케줄링 알고리즘 종류

• 비선점형 알고리즘 : FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
• 선점형 알고리즘 : 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
• 둘 다 가능 : 우선순위 스케줄링

 

스케줄링 알고리즘 평가 기준

• CPU 사용률 : 전체 시스템 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
• 처리량 : 단위 시간당 작업을 마친 프로세스의 수, 클수록 좋음
• 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간, 짧을 수록 좋음
• 응답 시간 : 프로세스 시작 후 첫 번째 출력/반응이 나올 때까지 걸리는 시간, 짧을 수록 좋음
• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데 걸리는 시간, 대기 시간 + 실행 시간
• 스케줄링 알고리즘 성능을 비교할 때는 주로 평균 대기 시간을 봄 : 모든 프로세스의 대기 시간 / 프로세스 수

 

---

[비선점형]

 

FCFS 스케줄링

• First Come First Served, 선입선출 스케줄링
• 준비 큐에 도착한 순서대로 CPU 할당
• 큐가 하나라 모든 프로세스는 우선순위가 동일
• 콘보이 효과(convoy effect), 호위 효과 : 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템 효율성 떨어지는 현상
• 현재 작업 중인 프로세스가 입출력 작업 요청하면, CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율 떨어짐

 

SJF 스케줄링

• Shortest Job First, 최단 작업 우선 스케줄링
• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU 할당
• FCFS 스케줄링의 콘보이 효과를 완화하여 시스템 효율성 높임
• 프로세스의 종료 시간 파악이 어렵고, 아사 현상(공평성 위배)이 일어나기 때문에 잘 사용하지 않음
  • 아사(starvation), 무한 봉쇄(infinite blocking) 현상 : 크기가 큰 작업이 계속 뒤로 밀리는 현상
  • 이를 해결하기 위한 방법 : 에이징(aging), 프로세스가 양보할 수 있는 상한선 정하는 방식
    프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정

 

HRN 스케줄링

• Highest Response Ratio Next, 최고 응답률 우선 스케줄링
• 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링
• 프로세스 우선순위 결정 기준 : 우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간
• 우선순위를 정할 때 대기 시간을 고려함으로써 아사 현상 완화
• 여전히 공평성 위배되어 많이 사용하지 않음

 

---

[선점형]

 

라운드 로빈 스케줄링

• Round Robin, 순환 순서 방식
• 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

 

- 타임 슬라이스의 크기와 문맥 교환

• 선점형 방식에서는 문맥 교환 시간이 추가됨
• 타임 슬라이스가 큰 경우
  • 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보임
  • 라운드 로빈 스케줄링에서 타임 슬라이스가 무한대이면 FCFS 스케줄링
• 타임 슬라이스가 작은 경우
  • 여러 프로그램이 동시에 실행되는 것처럼 느껴짐
  • 시스템의 전반적인 성능 저하
  • 문맥 교환이 너무 자주 일어나 문맥 교환으로 인한 시간이 낭비됨

 

SRT 우선 스케줄링

• Shortest Remaining Time, 최소 잔류 시간 우선 스케줄링
• SJF와 라운드 로빈을 혼합한 방식
• 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택
• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간이 더 적은 프로세스와 문맥 교환해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨
• SJF 스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고, 아사 현상이 일어나서 잘 사용하지 않음

 

다단계 큐 스케줄링

• multilevel queue
• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입됨
• 큐는 라운드 로빈 방식으로 운영되고 우선순위에 따라 다단계로 나뉘어 있음 → 프로세스가 큐에 삽입되는 것만으로 우선순위 결정 (고정형 우선순위)
• 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식
  • 우선순위가 높은 프로세스가 먼저 작동할 수 있음
  • 우선순위에 따라 타임 슬라이스 조절하여 작업 효율 높일 수 있음
• 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없음
  (우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스 작업이 연기됨)

 

다단계 피드백 큐 스케줄링

• multilevel feedback queue
• 우선순위를 가진 여러 개의 큐를 사용하지만, CPU를 사용하고 난 프로세스의 우선순위가 낮아짐
• CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어감
  → 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링 문제점 보완
  (프로세스의 우선순위가 낮아지더라도 커널 프로세스가 일반 프로세스 큐에 삽입되지는 않음)
• 우선순위에 따라 타임 슬라이스의 크기가 다름 (우선순위가 낮아질수록 타임 슬라이스 커짐)
  • 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻음
  • = 프로세스가 실행상태에 들어가면 CPU를 빼앗기지 않고 끝까지 작업을 마침
  • = FCFS방식으로 동작
• 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식, 변동 우선순쉬 알고리즘의 예

---

[둘 다 가능]

 

우선순위 스케줄링

• 프로세스는 중요도에 따라 우선순위를 갖는데, 이러한 우선순위를 반영한 스케줄링 알고리즘
• 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현 가능
• 공평성 위배, 아사 현상 문제
• 준비 큐의 프로세스 순서를 무시하고 프로세스 우선순위를 매번 바꾸며 오버헤드 발생
• 프로세스의 우선순위는 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정