개발/💻 CS 지식

[ 운영체제 ] CPU Scheduling

정소은 2025. 4. 13. 01:11

 

 

 

CPU Burst & I/O Burst

 

 

프로그램은 CPU burst와 I/O burst를 번갈아가며 수행된다

-  CPU burst : CPU가 주도권을 잡고 기계어를 수행하는 구간

-  I/O burst : I/O가 수행되는 구간, process는 blocked 상태

 

 

Process의 특성 분류

 

I/O bound process 

:  CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 프로그램

:  사람과 interaction을 많이 하는 프로그램

:  many short CPU bursts

CPU bound process

:  CPU를 길게 사용하는 계산 위주의 프로그램

:  few very long CPU bursts

 

Process 종류에 따른 CPU burst Time 분포

여러 종류의 process가 섞여 있기 때문에 CPU 스케줄링 필수적

 

I/O bound process  vs  CPU bound process

=>  I/O bound process에 CPU 먼저 줌

 

 

 

CPU Scheduler & Dispatcher

 

CPU Scheduler

:  Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스 선정 (Ready -> Running)

 

Dispatcher

:  CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김

:  이 과정을 Context Switch(문맥 교환)이라고 함

 

CPU Scheduling이 필요한 경우

-  Running -> Blocked   ex ) I/O 요청하는 시스템 콜

-  Running -> Ready  ex ) 할당 만료로 timer interrupt

-  Blocked -> Ready  ex ) I/O 완료 후 interrupt

-  Terminate

이때 1, 4에서의 Scheduling은 nonpreemptive(자발적)

2, 3에서의 Scheduling은 preemptive(강제적)

 

 

 

CPU Scheduling

 

Scheduling Criteria

  • CPU utilization : CPU 이용률
  • Throughput : CPU 처리량
  • Turnaround time : 어떤 프로세스가 CPU를 쓰러 들어와서 프로세스가 끝날 때까지 걸린 시간
  • Waiting time : 어떤 프로세스가 CPU를 쓰러 들어와서 프로세스가 CPU를 기다린 총 시간
    • Waiting Time = Turnaround Time - CPU Burst Time
  • Response time : 어떤 프로세스가 CPU를 쓰러 들어와서 최초로 CPU를 얻을 때까지 기다린 시간
    • Response Time = 첫 CPU 시작 시간 - 프로세스가 시스템에 도착한 시간

 

 

Scheduling Algorithms

 

FCFS(First Come First Service)

:  프로세스가 도착한 순서대로 실행시키기

 

ex 1 ) 

Waiting Time Average : ( 0 + 3 + 6 ) / 3 = 3

 

ex 2 )

Waiting Time Average : ( 0 + 24 + 27 ) / 3 = 17

  • Convoy Effect : Long Process가 먼저 수행돼서 Short Process가 오래 기다리게 됨

 

 

SJF(Shortest Job First)

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

 

SJF의 종류

  • Nonpreemptive
    : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
  • Preemptive
    : 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU 뺏김 
    • 이 방법을 Shortest Remaining Time First(SRTF)라고도 부름
  • 주어진 프로세스들에 대해 최소 평균 대기 시간을 보장

 

ex 1 ) Preemptive SJF

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

Waiting Time Average : ((0+9) + 1 + 0 + 2) / 4 = 3

  • Starvation : Long Term Process가 수행될 기회가 X

 

SJF의 다음 CPU burst time 예측

SJF는 CPU burst time이 짧은 순으로 수행시키는데 다음 CPU burst time을 어떻게 예측하는가?

:  추정만 가능함

:  과거의 CPU burst time을 이용해서 추청(exponential averaging)

 

Exponential Averaging

-  해당 프로세스의 과거의 CPU burst time의 평균값으로 추정

-  가중치를 이용해 최근일수록 예측값에 더 많이 반영, 과거일수록 가중치가 작아져 더 적게 반영

 

 

Priority Scheduling

 

Priority Number는 모든 프로세스에게 할당되어 있음

(Priority Number가 작을수록 더 우선되어야 하는 프로세스)

 

SJF도 일종의 Priority Scheduling -> Priority Number : 예측된 다음 CPU burst time

문제 : Starvation (Long term Job은 수행될 기회X)

해결 : Aging (기다린 시간이 길수록 더 높은 우선순위를 갖도록)

 

 

Round Robin(RR)

:  모든 프로세스가 할당된 시간만큼만 수행되고 다음 프로세스한테 CPU 빼앗김

:  할당 시간이 지나면 프로세스는 ready queue 맨뒤에 가서 다시 줄 섬

:  n개의 프로세스가 q time unit을 할당

=> 각 프로세스는 CPU의 시간의 1/n을 얻음

=> 어떤 프로세스의 Waiting time도 (n-1)q time unit을 넘지 않음

 

-  q가 너무 거대하면 결국 FCFS와 같아짐

-  q가 너무 작으면 context switch 오버헤드가 커진다

-  일반적으로 SJF보다 average turnaround time이 길지만, response time은 더 짧다

 

 

 

Multilevel Queue

 

Multilevel Queue

:  Ready Queue를 여러 개로 분할

  • foreground(interactive) : I/O bound job
  • background(batch - no human interaction) : CPU bound job

-  각 큐는 독립적인 스케줄링 알고리즘을 가짐

  • ex ) foreground - RR, background - FCFS (대부분 상위 큐로 갈수록 RR , 하위 큐로 갈수록 FCFS 알고리즘 사용)

-  큐 스케줄링 방법

  • Fixed Priority Scheduling
    • 높은 레벨의 큐부터 순차적으로 수행하는 것
    • 높은 레벨의 큐에 프로세스가 아예 존재하지 않을 때 다음 레벨로 넘어가도록
    • Starvation 문제가 발생할 가능성 있음
  • Time Slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • ex ) high level queue - 80%, low level queue - 20%

 

Multilevel Feedback Queue

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

:  Aging을 이와 같은 방식으로 구현 가능 - 대기 시간이 긴 프로세스들 높은 레벨의 큐로 이동시키기

 

Multilevel-Feedback-Queue Scheduler를 정의하는 파라미터

  • Queue의 수
  • 각 Queue의 Scheduling Algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫓는 기준
  • Process가 CPU 서비스를 받으러 할 때 들어갈 큐를 결정하는 기준

 

ex )

Q1 : 각 프로세스에게 9 milliseconds의 수행할 시간을 부여함

Q2 : 각 프로세스에게 19 millliseconds의 수행할 시간을 부여함

Q3 : FCFS

->  CPU burst time이 짧은 프로세스를 더 우대하는 방식

 

 

 

Multiple-Processor-Scheduling

:  CPU가 여러 개일 때의 Scheduling

 

Homogeneous Processor인 경우

-  Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록

-  반드시 특정 프로세서에서 수행되어야 하는 Process가 있다면 더 복잡해짐

 

Load Sharing

-  일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

-  별개의 큐를 두는 방법 / 공동 큐를 사용하는 방법

 

Symmetric Multiprocessing

-  각 프로세서가 각자 알아서 스케줄링 결정(CPU가 서로 대등함)

Asymmetric Multiprocessing

-  하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름(CPU 대장이 존재)

 

 

 

Real-Time-Scheduling

 

Hard real-time systems

:  정해진 시간 내에 반드시 끝내도록 스케줄링

Soft real-time systems

:  정해진 시간 내에 끝내야 하는 프로세스가 있다면 높은 우선순위를 갖도록 함

 

 

Thread Scheduling

 

Local Scheduling

:  User level Thread의 경우 사용자 수준의 thread library 사용해서 thread scheduling (OS는 thread 존재 모름)

Global Scheduling

:  Kernel level Thread의 경우 커널의 단기 스케줄러가 thread scheduling

 

 

 

Algorithm Evaluation

 

Queueing Models

:  확률 분포로 주어지는 arrival rate와 service rate를 통해 계산 -> 처리량, 소요시간

Implementation & Measurement

:  실제 작업에 알고리즘 적용해서 성능 측정

Simulation

:  시뮬레이션으로 알고리즘 적용해 결과 비교

저작자표시 비영리 변경금지