CPU Scheduling

CPU Scheduling

• Preemptible Resource
  - 한 Process가 점유한 상태에서 다른 Process에게 양보할 수 있는 자원
      (ex)CPU, Memory
  
  

• Non-Preemptible Resource
  - 한 Process가 점유하면 사용을 마칠때 까지 다른 Process에게 양보할 수 없는 자원
      (ex)Printer
  
  

• CPU Brust
  - 프로그램의 수행중에 연속적으로 CPU를 사용하는 단절구간
  

  
  

• I/O Brust
  - 프로그램의 수행중에 I/O의 완료를 기다리며 블록 되는 구간
  
  

• Scheduling Policies
  - 다음에 어떤 Process에게 CPU자원을 할당 할지
  - 얼마만큼에 시간동안 자원 할당 할지
  
  
• Scheduling Policies 설계 목표
  - Resource의 실질적인 작업시간 계산
  - 오버헤드의 최소화
  - Scheduling 최소화 ( Context Switching 최소화)
  - CPU Time을 여러 Process에게 골고루 할당
  
  
• Aging
  - Task가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 기법
  
  
• Process의 특징
  - CPU Bound Process : 대부분의 시간을 CPU연산에 사용
      성능적 요구 : 높은 CPU Utilization과 Throughput을 요구
  - I/O Bound Process : 대부분의 시간을 I/O를 보내고 wait에 사용하고 CPU연산을 짧게 한다.
     성능적 요구 : 짧은 Response Time을 요구한다.
  
  
• Scheduling의 종류
  1. First in First out ( FIFO )
      - 먼저 들어온 job을 먼저 처리한다.
      - CPU Brust기준으로 실행한다
      장점 : 단순하고 직관적
      단점 : 하나의 job이 무한Loop를 통해 CPU를 계속해서 점유하고 있을 수 있다. -> 이 경우 OS가 Timer를 통해 관리
      - CPU Brust가 짧은 순서대로 실행시키는게 효율적
          -> 문제점 : 운영체제가 Task의 남은 CPU Brust size를 예측할 수 없음
  
  2. Round Robin ( RR )
      - 기본적으로 FIFO 구조로 설계
      - Timeout 시간을 정해 일정시간 동안만 Job을 실행시키고 시간이 초과 하면 Ready Queue의 맨뒤로 간다.
      - 문제점
          (1) *<Timeout 시간>을 얼마나 잡을 것 인가?
              *Timeout 시간 : Time Slice 또는 TimeQuantum 
                  -> Task에게 CPU가 할당된 후 다음 스케쥴링을 위한 Timer Interrupt가 발생할 때 까지의 시간
          (2) 평균적으로 FIFO보다 좋은 성능을 보이지만 몇몇 상황에선 FIFO보다 안좋은 성능을 보인다.
          (3) CPU Brust의 차이가 미미하다면 FIFO가 효율적이다.
          (4) CPU Brust의 차이가 클수록 Round Robin이 효율적이다.
  
  3. Adeptive Scheduling
      - workload의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케쥴링 기법
      - Multi Level Feedback Queue가 대표적 (MLFQ)
  
      
  
  4. Priority-based Scheduling
      - Process들에게 선호도를 매기고, 선호도가 높은 Process를 먼저 수행하는 스케쥴링 기법
      - 문제점 : Stavation -> 수행할 준비를 마치고 CPU를 할당 받기를 기다리는 Process가 선호도가 낮아 무기한 연기되는 현상 발생
  
  5. Fair Share Scheduling(Bandwidth Scheduling, Proportional Share Scheduling)
      - 대기중인 Process들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케쥴링 기법
  
  
• Evolution of Scheduling Policies