스케줄링 알고리즘

• 단기 스케줄링 평가 기준들
  • 사용자 중심 + 성능 중심
    • 턴어라운드 시간
      • 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간을 의미
      • 실제 실행 시간 + CPU 나 다른 자원들을 사용하기 위해 대기한 시간
    • 응답시간
      • 시스템에 요구를 한 뒤 시스템으로부터의 첫 응답이 올 때 까지의 시간
      • 사용자 입장에서 시스템의 반응 속도를 가늠하기 위해서는 텀어라운드 시간보다 응답 시간이 더 현실적
    • 완료 시한
      • 실시간 OS에서, 프로세스가 완료되어야 하는 시점에 deadline (기한)이 있다면 스케줄러는 다른 평가 척도가 희생되더라도 완료 기한을 만족시킬 수 있는 프로세스의 수를 최대화 하는 방향으로 설계되어야 한다.
  • 사용자 중심 + 기타
    • 예측 가능성
      • 같은 작업이라면 항상 같은 기간, 같은 비용으로 실행되어야 한다.
      • 실행할 때마다 응답 시간, 턴어라운드 시간에 차이가 많이 나면 사용자들은 시스템에 신뢰를 가지지 못하게 될 것
  • 시스템 중심 + 성능 중심
    • 처리량
      • 단위 시간 동안 처리되는 작업의 양 
      • 단위 시간 내에 완료될 수 있는 프로세스의 수를 최대화 하는 정책 사용
      • 처리해야하는 양에 관련된 척도로써 각 프로세스 실행 시간의 길고 짧음에 따라 크게 좌우됨
      • 스케줄링 정책에 따라 처리기 이용률이 많이 차이나므로 어떤 스케줄링 정책을 채택하느냐가 처리량에 큰 영향을 미침
    • 처리기 이용률
      • 전체 시간 중 처리기가 작업한 시간의 비
  • 시스템 중심 + 기타
    • 공정성
      • 모든 프로세스가 공평하게 처리되며 기아에 시달려서는 안된다.
    • 일관된 우선순위
      • 프로세스들에게 우선순위고 부여되면 높은 우선순위의 프로세스를 우대하는 정책을 취하여야 함
    • 균형 있는 우선순위
      • 스케줄러는 시스템 내의 자원들이 가능한 최대로 활용되도록 해야함

• 우선순위 기반 스케줄링
  • 우선순위가 가장 높은 프로세스를 다음 번 프로세스로 선택
  • 문제점
    • 기아(starvation) : 낮은 우선 순위의 프로세스가 계속 CPU를 할당받지 못해 굶어 죽을 가능성
    • 기아 상태가 발생하지 않도록 하기 위해서는 프로세스가 시스템 내에 머무른 시간, 과거 실행 경력 등을 감안하여 우선순위를 조정해야 함 
• 다양한 스케줄링 정책들
  • 선택 함수
    • 다음 번 실행을 위해 준비 큐에서 대기 중인 프로세스 중 하나를 고를 때 사용하는 알고리즘을 함수 형태로 표현한 것
  • 결정 모드
    • 선택 함수가 호출되는 시점이 언제인가 하는 것
    • non-preemptive
      • 프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때 까지 CPU를 빼앗기지 않음
    • preemptive
      • 현재 실행중인 프로세스라 할지라도 OS에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있음
      • 선점 시킬 수 있는 시점
        • 새로운 프로세스가 진입하는 순간
        • 하드웨어로부터의 인터럽트로 인해 선점된 프로세스가 다시 준비 큐로 들어오는 순간
        • 클록 인터럽트에 의해 주기적으로 스케줄러가 호출되는 시점
      • 장점
        • preemptive모드가 non preemptive 모드에 비해 문맥교환이 잦아 이로 인한 오버헤드가 큼
        • 하지만 프로세스가 처리기를 오랫동안 독점하는 현상을 방지할 수 있으므로 프로세스 전체에는 비선점 모드보다 나은 서비스를 제공

• FCFS (First Come First Serve)
  • non-preemptive
  • 온 순서대로 모든 작업을 마치고 종료

• RR (Round Robin)
  • preemptive
  • 큐에 들어온 순서대로 정해진 TQ동안 수행하고 준비큐로 진입한다.

• SPN (Shortest Process Next)
  • non preemptive
  • 현재 가장 짦은 프로세스를 끝날 때 까지 수행

• SRN (Shortest Remaining Time)
  • preemptive
  • 새 프로세스가 도착했을 때 현재 수행시간이 가장 적게 남아있는 프로세스를 우선 실행한다.

Process Id	Arrival time	Burst time
P0	0	3
P1	2	6
P2	4	4
P3	6	5
P4	8	2

• HRRN (Highest Response Rate Next)
  • non-preemptive
  • 현재 "(기다린 시간 + 서비스 시간) / 서비스 시간" 값이 가장 큰 프로세스를 먼저 수행

• Multi Level Feedback Queue (MLFQ)
  
  • preemptive
  • 프로세스를 들어온 순서대로 가장 높은 우선순위의 큐에 넣는다.
  • 상위 우선순위의 비어있지 않은 큐에서 프로세스를 빼서 정해진 시간동안 수행
  • TQ가 끝나면 방금 나온 큐 보다 한 단계 낮은 우선순위의 큐에 넣는다.
  • 현대 OS에서 가장 많이 쓰는 스케줄링 알고리즘