CPU 스케줄링

본 글은 KOCW 이화여대 반효경 교수님의 운영체제 강의를 듣고 정리한 내용입니다.
http://www.kocw.net/home/m/search/kemView.do?kemId=1226304

1. CPU 스케줄링과 디스패처가 필요한 이유와 개념에 대해 알아본다
2. CPU 스케줄링의 여러가지 알고리즘에 대해 알아본다
3. CPU 스케줄링의 여러가지 알고리즘 중 멀티레빌 큐와 멀티레벨 피드백 큐에 대해 알아본다
4. 특수한 CPU 스케줄링에 대해 알아본다

🔹 프로세스의 일생

• 사람하고 interaction 하는 것 : CPU, I/O 를 번갈아 많이씀
  
  • CPU 를 길게 쓰는 작업 : CPU bound job (CPU bound process)
  • CPU 를 짧게 쓰는 작업 : I/O bound job (interactive job에게 적절한)

🔹 프로세스의 특성 분류

• 프로세스는 그 특성에 따라 두가지로 나눔
  • I/O bound process
    • CPU 를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
    • many short CPU bursts
  • CPU-bound process
    • 계산 위주의 job
    • few very long CPU burst

🔹 CPU Scheduler & Dispatcher

• CPU Scheduler

  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

• Dispatcher

  • 결정된 프로세스를 실제로 넘겨주는 운영체제의 일부
  • CPU의 제어권을 CPU scheduler 에 의해 선택된 프로세스에게 넘김
  • 이 과정을 context switch (문맥교환) 이라고한다

• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태변화가 있는 경우

  1. Running → Blocked (ex. I/O 에 요청하는 시스템 콜)
  2. Running → Ready (ex. 할당시간 만료로 timer interrupt)
  3. Blocked → Ready (ex. I/O 완료 후 인터럽트)
  4. Terminate

  *1~4 에서의 스케줄링은 nonpreemptive (=강제로 빼앗지않고 자진 반납)
  ** 다른 모든 스케줄링은 preemptive (=강제로 빼앗음)

🔹 Scheduling Algorithms

• FCFS (First-Come First-Served)

  • 프로세스의 도착순서대로 처리
    
    
  • 단점 ; convoy effect
    
    

• SJF (Shortest-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

  • CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄
    

  • Two schemes:

    • Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될때까지 CPU를 선점당하지않음
    • Preemptive
      • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김 ▶ SRTF(Shortest-Remaining-Time-First) 라고 부름

  • SJF is optimal

    • 주어진 프로세스들에 대해 minimum average waiting time 보장
      
      
  
  

• SRTF (Shortest-Remaining-Time-First)

• Priority Scheduling

  • A priority number is associated with each process
  • highest priority 를 가진 프로세스에게 CPU할당 (smallest integer = highest priority)
    • preemptive
    • nonpreemptive
  • SJF는 일종의 priority scheduling
    • priority = predicted next CPU burst time
  • Provlem
    • Starvation : low priority processes may never execute
  • Solution
    • Aging : as time progresses increase the priority of the process
      
      

• RR (Round Robin)

  • 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가짐 (일반적으로 10-100ms)

  • 할당시간이 지나면 프로세스는 선점(preempted)당하고 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

  • 여러줄로 줄 서기

  • starvation 발생가능

  • 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
    
    

• Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동가능
  • 에이징(aging)을 이와 같은 방식으로 구현 가능
    • starvation 효과 감소
  • Multilevel-feedback-queue scheduler 를 정의하는 파라미터들
    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process 를 상위 큐로 보내는 기준
    • Process 를 하위 큐로 내쫓는 기준
    • 프로세스가 CPU 서비스를 받을때 들어갈 큐를 결정하는 기준
  • Example
    

🔹 Scheduling Criteria

Performance Index (=Performance Measure, 성능척도)

• CPU utilization (이용률)
  • Keep the CPU as busy as possible
• Throughput (처리량)
  • #Of processes that complete their execution per time unit
• Turnaround time (소요시간, 반환시간)
  • amount of time to execute a particular process
• Waiting time (대기시간)
  • amount of time a process 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 produced, not output (for time-sharing environment)

🔹 Multiple-Processor Scheduling

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

🔹 Real-time scheduling

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

🔹 Threaad scheduling

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