운영체제 - CPU schedulering

• CPU Scheduler
  : 다중 프로그래밍의 목적은 항상 실행할 수 있는 프로세스가 있도록 하여 CPU 사용 효율을 극대화하는데 있다.
  : CPU 스케줄러는 CPU가 유휴 상태가 되면 Ready queue에 있는 프로세스를 하나 선택해서 실행
  
  - CPU-I/O 버스트 주기
   : 프로세스는 실행되는 동안 CPU 실행과 입출력 대기 두 주기를 반복한다.
   : 계산 중심 프로세스는 적은 수의 매우 긴 CPU 버스트를 가지며, 입출력 중심 프로세스는 많은 수의 짧은 CPU 버스트를 가진다.
   
  

  
  
  - 비선점(Nonpreemptive) vs 선점(Preemptive)
  

    ■ 선점형 스케줄링
     : 어떤 조건이 만족되면 현재 실행중인 프로세스의 의사와 상관없이 그것의 실행을 중단하고 다른 프로세스를 CPU에 할당
      1. 프로세스가 실행중 상태에서 대기중 상태로 전환 (ex. 입출력 요청)
      2. 프로세스가 실행중 상태에서 준비 완료 상태로 전환 (ex. 인터럽트 발생)
      3. 프로세스가 대기중 상태에서 준비 완료 상태로 전환 (ex. 입출력 완료)
      4. 프로세스가 종료 
  

    ■ 비선점형 스케줄링
     : 프로세스가 CPU에 할당되면 그 프로세스가 종료되거나 대기중 상태로 전환될 때까지 CPU를 점유. 1, 4에서 스케줄링이 일어나면 비선점.
  
  - Dispatcher
   : 스케줄러가 선택한 프로세스를 CPU에 할당해주는 요소를 디스패처(Dispatcher)
   : 문맥 전환, 모드 전환
   : 디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연(dispatch latency)
  
  - 스케줄링 기준
   : CPU 사용 효율, 처리율, 반환시간, 대기시간, 응답시간
  
  - 스케줄링 알고리즘
   ■ FCFS(First-Come First_Serverd)
     : 먼저 요청한 프로세스 순으로 스케줄링, FIFO 큐를 이용하여 쉽게 구현
     : 비선점 방식
     : Convoy effect 발생 (하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상)
  
   ■ SJF(Shortest-Job-First) = SRTF
     : CPU 버스트 시간이 가장 짧은 프로세스 순으로 스케줄링
  
   ■ Priority Scheduling
     : 우선순위가 높은 프로세스에게 먼저 CPU를 할당
     : SJF도 우선순위 스케줄링 중 하나
     : indefinite blocking, starvation 현상 발생, 우선순위가 낮은 프로세스는 평생 실행 안되는 현상 -> aging 기법으로 해결
  
   ■ RR(Round-Robin)
     : 시분할 시스템에서 사용하는 알고리즘
     : time slice 단위로 시간이 경과될 때마다 현재 프로세스를 중단하고 다음 프로세스를 실행
     : Ready queue를 순환버퍼로 만들어 구현
     : 선점 방식
     : time slice 단위가 너무 크면 FCFS, 너무 작으면 Context switching 오버헤드가 큼
  
   ■ Multilevel Queue
    : 다중레벨 큐 스케줄링에서는 준비완료 큐를 여러 개의 큐로 나누어 사용한다.
    : 각 큐는 독자적인 스케줄링 알고리즘을 사용
    : 큐 간에는 별도 스케줄링 알고리즘을 사용