CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘 목표

• CPU Utilization - 시단당 프로세서 이용률, 한 마디로 CPU를 idle 타임 두지 않을 수록 높다.
• Throughput - 시간당 처리한 작업의 비율, 짧은 작업을 먼저 처리하거나 중간에 인터럽트가 안 걸리면 높다.
• Response Time - 프로세스가 요청되고서 처음 CPU를 할당 받기까지의 대기 시간.
• Running Time - CPU를 사용한 시간.
• Waitting Time - Ready Queue에서 대기한 시간들의 총합. ( Response Time 을 포함한다. )
• Turnarount Time - 실행시간과 반환시간의 총합으로, 프로세스 요청 후 부터 작업의 완료 후 반환까지의 총 시간.
• 시스템 입장에서는 CPU 이용률, 처리율을 높이는 것이 좋고, 사용자 입장에서는 응답시간, 대기시간, 반환시간을 줄이는 것이 좋다.
• CPU 스케줄링 알고리즘은 이러한 목표를 달성하기 위해 단기 스케줄러가 비선점형, 선점형 방식으로 프로세스에게 CPU를 할당한다.

Nonpreemptive Algorithm ( 비선점형 - FCFS, SJF, Priority, HRN )

• 비선점형 방식은 CPU를 프로세스에게 할당되면 작업을 완료할 때까지 독점하는 방식이다.
  ( I/O 인터럽트 발생과 같은 자발적인 양보도 가능 하다. )
• 장점 - Context Switching 이 잘 안일어난다. 일의 순서에 따라 처리율을 높일 수 있다.
            비교적 공정하게 CPU를 프로세스들이 이용할 수 있고, 응답과 반환시간 예측이 용이하다.
• 단점 - Convoy Effect( 짧은 작업이 뒤에 있으면 평균 반환시간이 비효율적이다 )
            Starvation ( 작업 완료 전까지 CPU 독점이기 때문에 우선순위가 낮다면 기아현상이 발생한다 )
            Dead Lock ( CPU 할당을 받은 프로세스가 특정 조건하에 교착상태에 빠지면 자원의 낭비이다 )
• 종류
  • FCFS ( first come first served - FIFO )
    • 일의 중요도, 작업 시간과 관계없이 요청받은 순서대로 처리한다.
    • 평균 응답시간, 반환시간이 길며 Convoy Effect 가 발생할 수 있다 ( 처리율이 낮다 ).
  • SJF ( Shortest Job First - 짧은 작업시간을 지닌 프로세스 우선)
    • 일종의 우선순위 기법으로 작업시간이 짧은 프로세스가 먼저 CPU 를 할당 받는다.
    • CPU Throughtput 을 높일 수 있다.
    • 최소 평균 대기 시간을 보장하지만, Starvation 문제가 발생할 수 있다.
  • HRN, aging (Highest Response ratio Next)
    • 우선순위 기법(SJF)의 기아 현상의 불공평한 상황을 해결하기 위한 기법이다.
    • HRN은 ( Waitting Time + 작업시간 ) / 작업시간 의 값이 높은 프로세스가 CPU를 차지한다.
    • 오래 기다릴수록 aging을 주는 개념이다.

Preemptive Algorthm ( 선점형, SRT, Priority, RR )

 

• 선점형 방식은 특정 조건하에 이미 사용중인 CPU를 빼앗아 선점할 수 있는 방식이다.
• 장점 - 시분할 시스템, deadline 처리에 적합하다. 응답시간이 비교적 빠르다.
• 단점 - 특정 조건하에 잦게 Context Switch가 발생하여 오버헤드가 크다.
            응답, 반환시간 예측이 어렵다.
• 종류
  • RR ( Round Robin )
    • 선점형 스케줄링 방식의 기본적인 개념.
    • Quantum 이라는 작업 시간 단위를 정하고,
      이 단위 시간 만큼 CPU를 프로세스에게 할당하고 후에 여러 조건에 따라 CPU를 재할당 한다.
    • RR방식은 FCFS + Quantum 이다.
    • 응답시간이 빠르고, 비교적 공정한 방식이다.
    • Quantum을 잘 정해야한다. 너무 길면 FCFS 방식과 유사하고, 너무 짧으면 오버헤드가 발생한다.
  • SRT ( Shortest Reamaining Time - 짧은 잔여 작업시간을 지닌 프로세스 우선)
    • 프로세스가 대기큐에 들어올 때마다 이미 CPU를 할당중이라도 잔여 작업시간을 비교하여
      제일 짧은 잔여 작업시간을 지닌 프로세스가 CPU를 차지한다.
      ( SRT도 RR 처럼 시간 단위만큼 처리 후 잔여 작업시간 비교하는 설명도 있다... )
    • Starvation 문제가 발생할 수 있으며 CPU 사용 시간을 정확히 예측하기 어렵다.
  • Priority
    
    • 작업 큐에 우선순위와 함께 프로세스를 넣고, CPU 사용중인 프로세스 보다 높은 우선순위가
      들어오면 선점한다.
    • 기아현상이 발생할 수 있지만 aging 기법으로 해결 가능하다!