[운영체제] CPU Scheduling

CPU Scheduling이란

어떤 프로세스에게 얼마만큼 CPU를 줄지 결정하는 것입니다. 만약 CPU를 엄청 오래 쓰는 프로세스에게 CPU를 주고 다 끝날 때까지 기다린다면, 다른 프로세스들은 사용하기 위해 오래 가디려야하기 때문에 비효율적입니다. 따라서, 적절히 CPU를 할당하고 다시 뺏는 스케줄링이 필요합니다.

• CPU Scheduler: Ready 상태의 프로세스 중에서 어떤 프로세스에 CPU를 줄지 결정합니다.
• Dispatcher: CPU 제어권을 선택된 프로세스에게 넘깁니다. 이 과정을 Context Switch라고 합니다.

Preemptive VS Non-Preemptive

CPU를 다 쓸 떄까지 기다리는 것을 Non-Preemptive(비선점형), 강제로 뺴앗은 것을 Preemptive(선점형)이라고 합니다.

스케줄링 성능척도

• CPU utilization
  • 전체 시간 중 일하는 시간 비율
• Throughput
  • 주어진 시간에 완료한 프로세스의 수
• Turnaround time
  • CPU를 쓰러 들어와서, 다 쓰고 나갈 때까지 걸린 시간
  • 프로세스가 CPU 쓰러와서 IO하러 나갈 떄까지의 시간, 즉 하나의 CPU burst시간
• Waiting time
  • 한 프로세스가 큐에서 기다리는 시간
  • 선점형인 경우, 계속 CPU를 얻었다 뺏겻다를 반복. 그 사이사이에 기다린 시간을 합친 것
• Response time
  • ready queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간.

Scheduling 알고리즘

FCFS (First-Come First-Servced)

말 그대로 선입선출 방식입니다. CPU를 오래 쓰는 프로세스가 먼저 들어오면, 뒤의 프로세스들이 오래 기다리게 되는 비효율이 있습니다.

SJF (Shortest-Job-First)

CPU Burst가 가장 짧은 프로세스에게 먼저 CPU를 할당합니다. 이 방식은 다시 Preemptive와 Non-Preemptive방식으로 나뉘어집니다. Non-Preemptive 방식은 어떤 프로세스가 수행하고 있는 도중에 더 짧은 CPU Burst를 가진 프로세스가 Ready Queue에 들어오더라도, 우선 수행 중인 프로세스가 끝날 때까지 기다립니다. 반면 Preemptive방식은 중간에 더 짧은 CPU Burst를 가진 프로세스가 들어온 경우, 중간에 CPU를 뺴앗깁니다.
예를 들어, Burst Time이 6인 프로세스가 CPU에서 3동안 실행된 후 Burst Time이 4인 프로세스가 들어올 경우, 기존 프로세스의 잔여 Burst Time은 6-3=3으로 새로 들어온 프로세스의 시간(4)보다 짧음으로 CPU를 빼앗기지 않습니다. 다시 1 단위시간이 지난 후 Burst Time이 1인 프로세스가 들어오면, 잔여 시간이 더 짧음으로 뺴앗깁니다.

SJF의 문제

• Starvation: CPU Burst가 긴 프로세스는 영원히 CPU 제어권을 할당받지 못할 수도 있습니다.
• 부정확한 CPU Burst: 미리 CPU Burst를 알 수는 없고, 과거의 데이터를 토대로 추정(Exponential Averaging)합니다.

Priority Sheduling

우선 순위가 높은 프로세스에게 CPU 제어권을 줍니다. SJF도 Priority Scheduling의 일종입니다.

문제점

• Starvation해결: Aging오래 기다린 프로세스의 우선순위를 높여주는 방법으로 해결할 수 있습니다.

Round Robin (RR)

• 모든 프로세스가 일정한 시간만큼씩 CPU를 쓴 후, 주어진 시간(q)이 끝나면 다시 Ready Queue에서 기다립니다.
• 모든 프로세스는 정해진 시간(q)을 초과해서 기다리지 않습니다.
• q가 너무 크게되면 FCFS와 같게 되고, q가 너무 작으면 Context Switch가 너무 많이 발생해서 오버헤드가 커집니다.

Multilevel Queue

• Ready Queue를 우선순위가 다른 여러 개로 나눕니다.
  • foreground 사람과 상호작용이 잦은 것(높은 우선순위)
  • background 사람과 상호작용이 없는 것
• 각 큐 마다 다른 스케줄링 알고리즘을 적용할 수 있습니다.
  • foreground: RR
  • background: FCFS (이 방법을 통해 context switch 비용을 최소화합니다.)
• 큐에 대한 스케줄링이 필요합니다.
  • 높은 우선순위부터 실행하는 방법 (이 방법은 Startvation의 가능성이 있습니다.)
  • 각 큐에 적절한 비율로 CPU를 나눠서 사용

Multilevel Feedback Queue

• 우선 모든 프로세스가 첫번째 큐로 들어갑니다.
• 일정 시간동안 끝내지 못한 프로세는 다음 큐로 이동합니다.
• 이러한 방식으로 Aging을 구현할 수 있습니다.

Multiple-Processor Scheduling

• CPU가 어려 개일 경우입니다.
• CPU가 어려 개이더라도, 모두 같은 성질의 프로세서라면(즉 모든 프로세스는 어떤 프로세서에서 실행되어도 결과가 같음), 그렇다면, 큐에 한 줄로 세워놓고, 각 CPU가 하나씩 꺼내가서 수행하도록 하면 됩니다.
• Load Sharing
  • 한 프로세스에 일이 몰리지 않도록 적절히 분산시켜야합니다.
• Symmetric Multiprocessing
  • 각 프로세스가 알아서 스케줄링 합ㄴ다.
• Asymmetric Multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지는 그것에 따릅니다.

Real-Time Scheduling

• Hard real-time systems
  • 정해진 시간에 일을 끝마치도록 보장
• Soft real-time systems
  • 다른 프로세서에 비해 높은 우선순위를 갖도록 함.(예. 영상 재생)

Thread Scheduling

• Local Scheduling
  • User Level Thread인 경우 사용자 수준의 Thread Library에 의해 스케줄링합니다.
  • JVM은 Priority Scheduling합니다.
• Global Scheduling
  • 커널 수준의 Thread는 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 담당합니다.

알고리즘 평가

• Queueing Models
  • 확률 분포로 주어지는 arrival rate와 service rate를 통해 각종 수치들을 계산
• Implementation & Measurement
  • 실제 시스템를 구현하고 적용하여 성능을 측정
• Simulation
  • 알고리즘을 모의 프로그램으로 작성하여 결과를 비교합니다.