CPU Scheduling

CPU-burst Time의 분포

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다

• Interactive job에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
  

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
  Dispatcher
• CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
• 이 과정을 context switch(문맥 교환)라고 한다
  

CPU 스케줄링이 필요한 경우
1. Running -> Blocked (예. I/O 요청하는 시스템 콜)
2. Running -> Ready (예. 할당시간 만료로 time interrupt)
3. Blocked -> Ready (예. I/O 완료 후 인터럽트)
4. Terminate

1,4에서의 스케줄링은 nonpreemptive, 나머지는 preemptive(강제적)

Scheduling Criteria

• CPU utilization: keep the CPU as busy as possible
• Throughput: # of process that complete their execution per time unit
• Turnaround time: amount of time to execute a particular process
• Waiting time: amount of time a process that has been waiting in the ready queue
• Response time: amount of time it takes from when a request was submitted until the first response is roduced. not output (for time-sharing environment)

Scheduling Algorithms

• FCFS (First-Come First-Service)
  - Convoy effect: short process behind long process

• SJF (Shorteds-Job-First)
  - Nonpreemptive: 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음

  • Preemptive: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김 (Shorteds-Remaining-Time-First)
  • 주어진 프로세스들에 대해 minimum average waiting time을 보장
  • 다음 CPU Burst Time의 예측
    $t_{n}$ = actual length of $n^{th}$ CPU burst
    $r_{n}$ = predicted value for the next CPU burst
    $0 <= a <= 1$
    $r_{n+1} = at_{n} + (1-a)r_{n}$

• Priority Scheduling
  - highest priority를 가진 프로세스에게 CPU 할당
  - SJF는 일종의 priority scheduling이다

  • Problem: Starvation (low priority process may never execute)
  • Solution: Aging (as time progress increase the priority of the process)

• RR (Round Robin)
  - 각 프로세스는 동일한 크기와 할당 시간을 가짐

  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue와 제일 뒤에 가서 다시 줄을 선다
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  • performance
    • q large => FCFS
      • q small => context switch 오버 헤드가 켜진다.
  • Multilevel Queue
    • Ready queue를 여러 개로 분할
      • foreground (interactive)
      • background (batch - no human interaction)
    • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
      • foreground - RR
      • background - FCFS
    • 큐에 대한 스케줄링이 필요함
      • Fixed priority scheduling
        • serve all from foreground then from background.
        • Possibility of starvation
      • Time slice
        • 각 큐에 CPU time을 적절한 비율로 할당
        • Eg. 80% to foreground in RR, 20% to background in FCFS

• Multiple-Processor Scheduling

  • CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  • Homogeneous processor인 경우
    • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    • 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링 결정
  • Asymmetric multiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

• Real-Time Scheduling

  • Hard real-time systems: 정해진 시간 안에 반드시 끝내도록 스케줄링
  • Soft real-time systems: 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

• Thread Scheduling

  • Local Scheduling: User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • Global Scheduling: Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

• Queuing models: 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
• Implementation & Measurement: 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
• Simulation: 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교