스케줄러 알고리즘

※ 스케줄링 대상은 Ready Queue에 있는 프로세스 들이다.

 

 

FCFS ( First Come First Served )

---

 

• 먼저 온 순서대로 처리.
• 비선점형 스케줄링 (Non Preemptive)
• 일단 CPU를 잡으면 CPU Burst 가 완료 될 때까지 CPU를 반환하지 않는다.
• CPU를 모두 사용한 후 반환되면 스케줄링이 이루어진다

 

문제점

• Convoy Effect
  • Burst Time 이 긴 프로세스가 들어와 실행시간이 전부 늦쳐지는 현상.

 

SJF

---

• 프로세스 처리시간이 짧은 것을 먼저 처리하는 방식.( 다른 프로세스가 먼저 도착해도 처리시간이 짧은 것 먼저)
• 비선점형 스케줄링
  • 일단 CPU를 잡으면 CPU Burst가 완료될 때까지 CPU를 반환하지 않는다.
  • CPU를 반환될 때만 스케줄링이 이루어진다.

 

 

문제점

• Starvation
  • 특정 프로세스들이 지나치게 차별 받으면 그에 따른 영향이 있다.
  • SJF 극단적으로 짧은 처리시간을 갖는 JOB을 선호한다.
  • 사용시간이 긴 프로세스는 영원히 CPU를 할당받을 수 없게 되는 현상이 기아 현상이다.

 

SRTF ( Shortest Remaining Time First )

---

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 스케줄링(Preemptive)
  • 현재 수행중인 프로세스의 남은 Burst time 보다 더 짧은 CPU Burst time을 가지는 새로운 프로세스가 도착하면 CPU 점유를 뺏긴다.

 

문제점

• Starvation
  • 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU Burst time(CPU 사용시간)을 측정할 수가 없다. 

 

Priority Scheduling

---

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다.
• 선점형 스케줄링 방식
  • 우선순위가 높은 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.
• 비선점형 스케줄링 방식
  • 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.

문제점

• starvation
• indefinite Blocking ( 무기한 봉쇄 )
  • 실행 준비는 되었으나 우선순위가 높은 프로세스들이 오게 되면서 CPU를 사용못하는 프로세스들이 무기한 대기하는 상태.

 

문제 해결 방법

• Aging
  • 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다.

 

Round Robin

---

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간(time quantum) 을 갖는다.
• 할당시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우 효율적이다.
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

 

장점

• ResponseTime이 빨라진다.
  • n개의 프로세스가 ready Queue에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q단위로 CPU시간의 1/n을 얻는다. 즉 어떤 프로세스라도 (n-1)q time 단위 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.
  • 공정한 스케줄링이다.

 

※ 주의점

설정한 time Quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상정이지만 잦은 Context Swithching으로 overhead가 발생한다. 그러므로 적당한 time quantum을 설정하는 것이 중요하다.