반효경 운영체제 - 4. CPU Scheduling

CPU Scheduling은 무엇인가?

---

프로그램 실행은 CPU burst와 I/O burst의 연속이다.

• CPU burst : CPU만 실행하는 단계
• I/O burst : I/O만 실행하는 단계
• 프로그램의 종류에 따라 CPU burst와 I/O burst의 빈도가 다르다.
  • 사용자가 사용하는 프로그램(Interactive)은 보통 상호작용이 있기에 I/O burst의 빈도가 다르다.
  • 1000*1000 행렬 계산 프로그램 등은 CPU burst의 비중이 높다.

• 위 그림의 경우 I/O bound job의 빈도는 굉장히 높고, CPU bound job의 빈도는 굉장히 낮았음을 보여준다.
  • I/O가 중간에 끼어들어 CPU를 짧게 쓰는 경우의 job을 I/O bound job이라고 한다.
  • CPU만 오랫동안 쓰는 경우를 CPU bound job이라고 한다.
• 여러 종류의 job(=process)가 섞여 있기 때문에 CPU 스케줄링이 필요하다.
  • Interactive job에게 적절한 response 제공 요망
    • Interactive job이 오래기다리지 않도록 하는 것이 중요하다.(사람이 오래 기다리게 되므로)
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
  • 언제 뺏을 것인가? 등이 CPU 스케줄링의 주요 이슈

---

프로세스의 특성 분류

• I/O bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • many short CPU bursts
• CPU-bound process
  • 계산위주의 job
  • long CPU bursts

---

CPU Scheduler & Dispatcher

• CPU Scheduler
  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
  • 운영체제 내에서 scheduling하는 프로그램을 scheduler라고 부른다.
• Dispatcher
  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
    • 실제 넘겨주는 과정을 관리하는 코드
  • 이 과정을 context switch(문맥 교환)라고 한다.
• CPU 스케줄링이 필요한 경우
  1. Running → Blocked (예 : I/O 요청하는 시스템 콜)
  2. Running → Ready (예 : 할당시간만료로 timer interrupt)
  3. Blocked → Ready (예 : I/O 완료 후 인터럽트)
     • 스케쥴 우선순위에 따라 실행 중 프로세스가 시간이 남아있어도 I/O 완료된 process를 바로 실행할 수도 있다.
  4. Terminate

**1,4에서 스케줄링은 non-preemptive(자진 반납), 나머지는 preemptive(강제 환수)

---

스케쥴링 알고리즘이란?

---

스케쥴링 알고리즘의 분류

• Non-pre-emptive Scheduling : 비선점형 스케쥴링
  • 강제로 뺏지 않는 스케쥴링
• Pre-emptive scheduling : 선점형 스케쥴링
  • 언제든지 권한을 뺏어올수 있는 스케쥴링

---

스케쥴링 알고리즘의 성능 척도(Performance Index)

1. 시스템 입장의 성능 척도

• CPU utilization(이용률)
  • 전체 시간 대비 CPU가 놀지 않고 일하는 시간의 비율
• Throughput(처리량)
  • 주어진 시간에 얼마나 많은 프로세스를 완료했는지?

2. 프로세스 입장의 성능 척도

 

CPU 입장에서의 Process 성능 척도이므로, 프로세스의 전체(I/O 포함)가 아닌 단일 CPU Burst(I/O 이전까지)의 time을 이야기한다.

• Turnaround time(소요시간, 반환시간)
  • Queue에서 서서 실행하고 나갈 때까지의 CPU Burst 시간
• Waiting time(대기 시간)
  • CPU를 쓰기 위해 Ready Queue에서 기다리는 시간
  • 선점형 스케쥴링 동안 발생하는 대기 시간의 총합
• Response time(응답 시간)
  • 선점형 스케쥴링이더라도 최초의 CPU를 얻기까지에 기다리는 시간

---

Scheduling Algorithms

---

FCFS (First-Come First-Served)

비선점형 스케쥴링으로, CPU를 짧게쓰는 프로세스가 도착해도 오래 기다려야한다는 단점이 있다. 이를 Convoy Effect라고 하는데, 긴 프로세스가 선점하였을 때, 뒤의 짧은 프로세스가 오래 기다려야하는 상황을 뜻한다.

 

---

 

SJF (Shortest-Job-First)

각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용하는 방식으로, CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴한다. 전체적인 Queue의 길이가 짧아지는 효과가 있고 또한 주어진 프로세스에 대해 minimum average waiting time을 보장된다는 특징이 있다.

• Two Schemes
  • Non-preemptive : CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
    • 한 프로세스가 CPU를 다쓰고 나가는 순간에 스케쥴링 발생
  • Preemptive : 수행중 process의 남은 CPU burst time보다 짧은 CPU burst time을 가진 프로세스가 도착하면 CPU를 빼앗김
    • 프로세스가 도착할 때마다 스케쥴링이 이루어진다.
    • Shortest-Remaining-Time-First(SRTF)라고도 부른다.

• SJF의 문제점
  • Starvation(기아 현상) : CPU 사용 시간이 긴 프로세스는 영원히 점유를 못할 수도 있다.(형평성)
  • 실제로는 분기, 제어 등에 의해 런타임에서 CPU 사용 시간이 결정되므로, CPU 사용시간을 미리 알 수 없다. 그러나 어느정도 추정은 가능하다.

• Exponential Averaging
  • alpha의 값을 통해서 현재의 가중치와 과거의 가중치 사이에서 조절할 수 있다. 다음 CPU Burst Time의 예측이 가능하다.

exponential averaging을 통한 CPU burst time 예측

Non-Preemptive SJF의 example

Preemptive SJF의 example

---

Priority Scheduling

우선순위가 가장 높은 프로세스에게 CPU 할당하는 방식이다. 우선순위는 어느 것이든 정할 수 있다.

• Preemptive : 우선순위가 더 높은 프로세스가 오면 CPU 권한을 빼앗음
• Non-preemptive : 한번 권한을 받으면 끝날때까지 사용
• 우선순위의 표현 : smallest integer = highest priority
• SJF는 일종의 priority scheduling이다.
  • Priority = predicted next CPU burst time
• Problem
  • Starvation : 우선순위가 낮은 프로세스가 할당 받지 못하는 것(형평성)
• Solution
  • Aging : 시간이 지나면서 프로세스의 우선순위가 높여주는 것

---

Round Robin (RR)

각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가진다. 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에 가서 대기한다. 일반적으로 SJF보다 average turnaround time이 길지만 response time이 더 짧다. CPU의 사용시간과 대기시간이 비례한다는 특징이 있다.

• 장점 : 전체적인 응답 시간이 빨라진다. 예측이 필요없다.
• 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 오버헤드가 커진다.
• CPU 사용시간이 모두 동일하다면, 효율이 떨어진다.
  • ex) 100초짜리 CPU burst 프로세스 10개인 경우, 1000초가 될때 모든 프로세스가 거의 동시에 끝난다. - turnaround time이 굉장히 길어진다.
• CPU 사용시간이 다양하고 예측할 수 없을 때, 효율이 좋다.
  • 전체적인 response가 빠르면서, 짧은 프로세스는 turnaround가 빨리 일어날 수 있다.

---

Multi-level Queue

• Ready queue를 여러개로 서는 것
  • Foreground(interactive) : Round Robin
  • background(batch - no human interaction) : FCFS, context switch overhead를 줄임
• 각 Queue는 독립적인 스케줄링 알고리즘을 가짐
• Queue에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • 무조건 foreground를 먼저 처리
    • starvation 가능성
  • Time Slice
    • 각 큐에 CPU time을 비율로 할당
    • ex. 80% to foreground in RR, 20% to background in FCFS

---

Multi-Level Feedback Queue

• 줄을 왔다갔다 할 수 있는 스케줄링
• Three queues
  • Q0 : (처음 들어오는 프로세스)RR방식 8 milliseconds
  • Q1 : RR방식 16miliseconds
  • Q2 : FCFS
• Queue간의 우선순위가 있어 반응 시간이 빠르며, CPU 사용량이 높은 프로세스는 순위가 낮아짐
• RR보다 사용 시간이 짧은 프로세스에게 더 우선순위를 주는 방식

---

Multiple-Processor Scheduling

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

---

Real-Time Scheduling

• Hard real-time Systems
  • hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함.
  • 보통 특수한 시스템 : 오프라인으로 미리 스케줄링, 반드시 periodic으로 할당해야하는 경우 등
• Soft real-time computing
  • soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함.
  • 영화관 등? deadline을 꼭 보장하지는 않아도 되는 경우.

---

Thread Scheduling

• Local Scheduling
  • User Level Thread
    • 사용자 프로세서가 쓰레드를 관리하고 운영체제는 쓰레드 존재를 모르는 경우
    • 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • Global Scheduling
    • 운영체제가 쓰레드의 존재를 알고있는 경우
    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

---

Algorithm Evaluation

• Queueing models (이론적인 모델)
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값 계산
• Implementation (구현) & Measurement (성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(work load)에 대해서 성능을 측정 비교
  • ex) Linux 시스템 내부 알고리즘을 수정, 로딩해서 다른 알고리즘의 리눅스 시스템들과 비교
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램으로 작성하여 성능을 시뮬레이션 하는 모델
  • 실제 시스템 사용 패턴(trace)에 근거한 시뮬레이션이 신빙성이 높다.

---

 

•