5강) CPU 스케줄링 (CPU Scheduling)

** KOCW에서 반효경 교수님의 운영체제(2014년) 강의를 수강한 내용을 정리한 글입니다.

[운영체제

운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각

www.kocw.net](http://www.kocw.net/home/cview.do?cid=3646706b4347ef09)

프로그램은 CPU burst와 I/O burst가 번갈아서 진행된다.

Burst : 연속적으로 실행하고 있는 단계

• I/O bound job : I/O burst가 잦은 프로그램
  • 짧은 CPU burst가 많은 수로 존재
• CPU bound job : CPU burst 지속시간이 긴 프로그램
  • 긴 CPU burst가 적은 수로 존재
• 여러 종류의 Job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다
• Interactive job에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
• 공평하게보다는 효율적으로 CPU 자원을 분배할 필요성 (사람과의 상호작용 고려)

 

CPU Scheduler & Dispatcher

• CPU Scheduler
  • Ready 상태의 프로세스 중에서 CPU를 넘겨줄 프로세스를 고른다
  • 운영체제 안의 코드로 존재
• Dispatcher
  • CPU의 제어권을 넘기는 역할
    • 이 과정을 Context switch(문맥 교환)라고 한다.
  • 운영체제 안의 코드로 존재
• CPU 스케쥴링이 필요한 경우는 다음과 같은 상태 변화가 있는 경우이다.
  1. Running → Blocked(eg: I/O 요청하는 시스템 콜)
  2. Running → Ready(eg: 할당시간 만료로 Timer interrupt)
  3. Blocked → Ready(eg: I/O 완료 후 인터럽트)
  4. Terminate2, 3 등 그 외 모든 스케줄링 → Preemptive (강제로 빼앗음)
  5. 1, 4 → Nonpreemptive (자진 반납)

 

성능 척도 (Scheduling Criteria)

• CPU 입장에서
  • CPU utilization (이용률)
    • CPU가 가능한 바쁘게 유지하기
  • Throughput(처리량)
    • 단위 시간 당 완료하는 실행
• 프로세스 입장에서
  • Turnaround time (소요시간, 반환시간)
    • 특정 프로세스를 실행하는 데에 걸린 시간 (Ready queue에 들어와서 실행을 마치고 나가기까지)
  • Waiting time (대기 시간)
    • 순수하게 기다린 시간(in ready queue)
    • CPU burst 동안에 생기는 대기까지 모두 포함
  • Response time (응답 시간)
    • Ready queue에 들어와서 처음 CPU를 얻기까지 걸린 시간
• 위 얘기들은 프로세스가 실행되어 종료되기까지를 얘기하는 것이 아니라
• → 한 번의 CPU burst에 있어서를 얘기하는 것!

 

FCFS (First-Come First-Served)

• 프로세스 도착 순서대로 CPU 할당

• P1 = 0 / P2 = 24 / P3 = 27 (Waiting time)
• Average : 17

• P2 = 0 / P3 = 3 / P1 = 6 (Waiting time)
• Average : 3
• 앞에 도착한 프로세스의 사용시간이 긴 경우 → 평균 Waiting time이 길어짐 (Convoy effect라고 함)
• → 좋은 알고리즘이 아님

 

SJF (Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• Two schemes
  • Nonpreemptive : 일단 CPU를 잡으면, CPU burst 완료 시까지 CPU를 선점(preemption) 당하지 않음
  • Preemptive : 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스 도착 시 → CPU를 빼앗김 (SRTF : Shortest-Remaining-Time-First)
• SJF is optimal for Waiting time
  • 주어진 프로세스들에 대해 Minimum average waiting time을 보장 (SRTF)

 

Nonpreemptive SJF 예제

• P1 도착 후 바로 실행 → 나머지 모두 도착했으니, Burst가 짧은 P3 실행
• Average waiting time = (0 + 6 + 3 + 7(순서대로)) / 4 = 4

 

Preemptive SJF(SRTF) 예제

• 도착한 프로세스의 Burst time과 실행 중인 프로세스의 Remaining burst time을 비교
• Average waiting time = 3
  • P1 = 9
  • P2 = 3
  • P3 = 0
  • P4 = 2

 

SJF의 문제점

1. Starvation(기아 현상)
   
   1. → CPU burst time이 긴 프로세서는 너무 오래 실행되지 않을 가능성이 있음
2. CPU Burst time 예측이 불가능함
   1. branch, user input 등이 있기 때문 
   2. 추정만이 가능 → 과거의 CPU burst time을 이용해서 추청 (exponential averaging)

 

Priority Scheduling

• 각 프로세스에 우선 순위가 할당됨
  • 높은 우선 순위(작은 Integer)의 프로세스에게 CPU 할당
  • Preemptive와 Nonpreemptive
• SJF는 일종의 Priority scheduling이다.
  • 우선 순위 → 다음 CPU burst time의 예측값이 낮은 순
• 문제점 : Starvation(기아 현상) → Low priority 프로세스가 실행되지 않을 수 있다.
  • 해결 : Aging(노화) ㅍ 시간이 지남에 따라 Priority를 높인다.

 

Round Robin (RR)

• 현대 운영체제 스케줄링은 RR에 기반
• 각 프로세스는 동일한 크기의 할당 시간(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(First-Come First-Served)
  • q small → Context switch 오버헤드가 커진다

• 일반적으로 SJF보다 Average turnaround time이 길지만, response time은 더 짧다.

 

Multilevel Queue

• Ready queue를 여러 개로 분할
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • Foreground (interactive) : RR
  • Background (batch - no human interaction) : FCFS
• 큐에 대한 스케줄링이 필요
  1. Fixed priority scheduling
     • Foreground 먼저 제공하고 Background 제공
     • Starvation 가능성
  2. Time slice
     • 각 큐에 CPU time을 적절한 비율로 할당
     • Eg., 80% to foreground in RR, 20% to background in FCFS

 

Multilevel feedback queue

• 프로세스가 다른 큐로 이동 가능

 

Multiple-Processor Scheduling

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

 

Real-Time scheduling

• Hard real-time systems : Task를 정해진 시간 안에 반드시 끝내도록 스케줄링
• Soft real-time systems: 해당 Task의 Priority를 일반 프로세스에 비해 높게 설정

 

Thread Scheduling

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

 

Algorithm Evaluation