[OS] CPU Scheduling

CPU Scheduler & Dispatcher

CPU Scheduler

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

Dispatcher

CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
이 과정을 context switch라고 한다.

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

1. Running -> Blocked (예: I/O 요청하는 시스템 콜)
2. Running -> Ready (예: 할당시간 만료로 timer interrupt)
3. Blocked -> Ready (예: I/O 완료 후 interrupt)
4. Terminate

1, 4에서의 스케줄링은 Nonpreemptive (= 강제로 빼앗지 않고 자진 반납)
All other scheduling is preemptive (= 강제로 빼앗음)

Scheduling Criteria (성능 척도)

• CPU utilization (이용률)
  CPU가 놀지않고 일한 시간의 비율
• Throughput (처리량)
  단위 시간당 처리량
• Turnaround time (소요시간, 반환시간)
  queue에서 기다린 시간 + CPU 사용 시간
• Waiting time (대기 시간)
  CPU를 쓰러와서 기다린 전체시간 (기다린 시간의 합), CPU 사용하다가 뺏겨서 또 기다리고하는 시간의 합
• Response time (응답 시간)
  프로세스가 CPU를 최초로 얻기까지의 시간

Scheduling Algorithms

FCFS (First-Come First-Served)

먼저 도착한 프로세스를 먼처 처리

• 단점
  앞에 긴 친구가 들어오면 waiting 타임 전체가 길어지게 된다.
  Convoy effect: short process behind long process

SJF (Shortest-Job-First)

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄.
waiting 측면에서는 가장 optimal한 방법 (minimum average waiting time을 보장)

• Nonpreemptive
  일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
• Preemptive
  현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김.
  이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.
• SJF의 치명적인 약점 2가지
  • Starvation 발생
    짧은 프로세스만 우선적으로 하므로 long job은 영원히 CPU를 선점하지 못할 수 있음.
  • Starvation 해결책
    Aging: 기다린 시간이 길어지면 우선순위를 높여준다.
  • 다음번 CPU burst time을 어떻게 알 수 있는가?
    과거의 CPU burst time을 통해 예측한다.

Priority Scheduling

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

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• 성능
  • 할당 시간(time quantum) 클 경우 => FCFS
  • 할당 시간(time quantum) 작을 경우 => context switch 오버헤드가 커진다.
• 장점
  • Response time이 짧다. SJF보다 일반적으로 average turnaround time이 길지만 큐에 들어와서 첫번째 CPU를 얻기까지의 시간이 짧음.
• 단점
  • homogeneous한 시간을 가지는 job에서는 average turnaround time이 길어지는 단점이 있다.

Multilevel Queue

• Ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch-no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS (long job)
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    모든 foreground job 처리 후 background job 처리
    Starvation이 발생할 가능성이 있음.
  • Time slice
    각 큐에 CPU time을 적절한 비율로 할당
    80% to foregound in RR, 20% to background in FCFS

Multilevel Feedback Queue

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

Multiple-Processor Scheduling

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

Real-Time Scheduling

deadline을 지키는 것이 중요한 scheduling

• Hard real-time systems
  반드시 deadline을 지겨야하는 scheduling
• Soft real-time computing
  일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

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

Algorithm Evaluation

Queueing models

확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

Implemetation & Measurement

실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교

Simulation

알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교