[운영체제] #5 CPU Scheduling

또상·2022년 7월 15일
0

Operating System

목록 보기
6/13
post-thumbnail

프로그램의 실행 단계 (배경)

프로그램이 실행되면 CPU burst job 과 I/O burst job 이 반복적으로 실행된다.
프로그램 별로 I/O 의 빈도가 다름

  • interactive : I/O 빈도 높음

  • I/O bound job : I/O 를 많이 하기 때문에 CPU 를 짧게 씀.
    • interactive 한 I/O bound job 에 CPU 를 우선적으로 주기 위해서 CPU Scheduling 을 한다.
  • CPU bound job : 계산 위주의 작업. CPU 를 길게 씀.
  • 그래서 어떤 job 에 CPU 를 어떻게 분배해야 공정하고 효율적인가??
    -> CPU Scheduler 가 결정.

CPU Scheduler & Dispatcher

-> CPU SCHEDULER 는 OS 안에 있는 특정 코드이다.

  • CPU Scheduler
    • Ready 상태의 프로세스 중에서 CPU 를 줄 프로세스를 고른다.
    • CPU 를 누구에게 줄 지, 프로세스에게 준 CPU 를 언제 빼앗을지 결정
  • Dispatcher
    • CPU 제어권을 CPU Scheduler 가 선택한 프로세스에게 넘긴다.
    • 해당 과정이 바로 context switch

CPU 스케줄링이 필요한 경우

  1. Running -> Reading (ex. I/O 요청하는 시스템 콜) CPU를 자진적으로 내놓음
  2. Running -> Ready (ex. timer interrupt / 우선순위) 강제로 빼앗김.
  3. Blocked -> Ready (ex. I/O 완료 후 인터럽트 - 우선순위에 따라 Blocked -> Running 으로 가기도...)
  4. Terminate
  • nonpreemptive (= CPU 자진 반납) 1, 4
  • preemptive (= 강제로 빼앗김) 2



Performance Criteria 성능 척도

  • System 측면 : CPU 하나로 일을 많이 시키면 좋은 것.
    • CPU utilization(이용률) : CPU가 일을 한 시간 / 전체 시간
    • Throughput(처리량) : 주어진 시간에 몇 개의 일(process)을 처리했는지
  • Program 측면 : CPU 를 얻어서 빨리 끝나면 좋은 것.
    • Turnaround time : CPU를 쓰러 와서 CPU 를 다 쓰고 나갈 때 까지 걸린 시간 (기다림 + running)
      • ready queue에 들어와서 한번 running 할 때 까지 걸린 시간.
      • 프로세스가 시작해서 끝날때까지가 아님! I/O 시간은 제외
    • Waiting time : CPU를 쓰기 위해 기다린 시간 - CPU 얻었다 뺏겼다 할 때 ready queue 에서 기다린 모든 시간 (in preemtive)
    • Response time : 최초로 CPU를 얻기까지 걸린 시간
      • 사용자 반응에 있어서 최초 반응이 중요하니까!



Scheduling Algorithm

FCFS

First Come First Service
먼저 온 순서대로 처리

ProcessBurst Time
P124
P23
P33

ProcessWaiting Time
P10
P224
P327
Average(0 + 24 + 27) / 3 = 17
  • Convoy Effect : 먼저 도착한 프로세스가 너무 오래 걸려서 평균 대기 시간이 길어짐...

ProcessBurst Time
P23
P33
P124

ProcessWaiting Time
P10
P23
P36
Average(0 + 3 + 6) / 3 = 3

SFJ

Shortest Job First
다음번 CPU burst time 이 가장 짧은 것에 먼저 CPU를 준다.

  • Nonpreemptive
    • CPU 를 잡으면 CPU burst가 완료될 때 까지 CPU를 뺏기지 않음.
  • Preemptive
    • 수행중인 프로세스의 남은 brust time 보다 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏김. -> SRTF
    • minumim average waiting time 보장

ProcessArrival TimeBurst Time
P107
P224
P341
P454

P1 이 끝나는 시점에 P2, P3, P4 가 모두 도착해있으므로 그 중 제일 짧은 P3 먼저 실행.

ProcessWaiting Time
P10
P37 - 4 = 3
P27 - 2 + 1 = 6
P47 - 5 + 1 + 4 = 7
Average(0 + 6 + 3 + 7) / 4 = 4

SRTF

Shortest Remaining Time First

ProcessWaiting Time
P10 + 2 + 1 + 2 + 4 = 9
P20 + 1
P30
P40 + 2
Average(9 + 1 + 0 + 2) / 4 = 3
  • 어떤 알고리즘을 써도 preemptive SJF == SRTF 가 가장 짧은 waiting time.

SJF 의 문제점

1. starvation

CPU 사용 시간이 긴 녀석이 하나 있고 짧은 것이 계속 들어오면 긴 녀석은 영원히 실행이 되지 않을수도 있다...

2. 다음 CPU Burst Time 을 어떻게 알지...

  • 과거의 CPU Burst Time 을 통해 추정한다.
  • exponentional averaging 식 이용.

    • 과거 실행 시간보다 최근 실행 시간의 가중치를 크게 두어서 예측

Priority Scheduling

  • 우선순위가 높은 프로세스에게 먼저 CPU 할당.
  • Nonpreemptive
  • Preemptive : 실행중인 프로세스보다 우선순위가 더 높은 프로세스가 오면 CPU 뺏김
  • SJF 는 CPU burst time 이 짧은 것에 우선순위로 두는 priority scehduling
  • 문제점 : Starvation
  • goruf : Aging - 오래 기다리면 프로세스의 우선순위가 높아지게 처리.

RR

Round Robin
현대적인 컴퓨터 시스템의 CPU 는 RR 기반.

  • 각 프로세스는 동일한 할당 시간 (time quantum) 을 가진다. (10~100ms)
  • 할당 시간이 지나면 CPU 를 빼앗기고, ready queue 맨 뒤에 줄 선다.
  • 프로세스가 한 타임에 기다리는 시간의 최대치가 정해져 있음.
    • n : ready queue 에 있는 프로세스 수
    • q : 할당 시간
    • 어떤 프로세스도 (n-1)*q time unit 이상 기다리지 않음.
    • q 를 너무 크게 잡으면 FCFS
    • q 가 너무 작으면 context switch 오버헤드가 커져서 성능이 떨어진다.
  • context 를 저장했다가 바로 시작할 수 있는 환경에서 좋다.

ProcessBurst Time
P153
P217
P368
P424

  • SJF 보다 평균 turnaround time 이 길지만 : running 이 한번 CPU 잡으면 끝나는게 아니니까
  • response time 은 짧음 : 최초로 잡는 시간은 최대 (n-1)*q time unit

Multilevel Queue

여러줄 서기.
우선순위가 높은 큐부터 처리.

  • Ready Queue 를 여러개로 분할한다
    • foreground : interactive
    • background : batch
  • 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
    • foreground : RR
    • background : FCFS
  • 큐에 대한 스케쥴링 필요
    • Fixed priority scehduling
      • ex) foreground 먼저
      • starvation 가능성 있음
    • Time slice
      • 각 큐에 CPU Time 을 적정 비율로 할당.
      • 80% foreground in RR, 20% background in FCFS

Multilevel Feedback Queue

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

  • aging 을 이런 방식으로 구현 가능.

  • 고려사항

    • Queue 의 수
    • 각 큐의 schedhuling algorithm
    • Process 를 상위 큐로 보내는 기준
    • Process 를 하위 큐로 쫓아내는 기준
    • 프로세스가 CPU 서비스를 받으려고 할 때 들어갈 큐를 결정하는 기준

  • 새로운 job 은 우선순위가 높은 Q0 으로 보내고,

  • CPU 를 잡아서 할당 시간 8ms 동안 실행

  • 8ms 동안 끝이 안나면 Q1 로 내려감

  • Q1 에서 기다렸다가 16ms 실행

  • 또 실행하지 못하면 Q2 로..

    • CPU burst time 이 짧은 job 에 우선순위를 높게 준다.
    • 근데 예측도 안해도 됨.
  • 우선순위가 높은 큐가 비어있으면 우선순위가 낮은 큐를 실행.



Multi-Processor Scheduling

CPU가 여러개인 경우의 스케쥴링

  • Homogeneous processor
    • 한 줄로 세워서 각 프로세서가 꺼내가게 한다.
    • But 특정 프로세서에서 수행되어야 하는 프로세스가 있다면..? 복잡...
  • Load sharing
    • 일부 프로세서에 job 이 몰리지 않도록 부하를 적절히 공유해야함.
    • 별개의 큐 vs 공동 큐 ...
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링
  • Asymmetric Multiprocessing
    • 하나의 프로세서가 시스템 데이터 접근, 공유를 책임지고 나머지 프로세스는 거기에 따름



Real-Time Scheduling

deadline 에 보장되도록 job 을 배치한다.

  • Hard real-time system : Hard real-time task 가 정해진 시간 안에 무조건 끝내야함.
  • Soft real-time system : Soft real-time task 가 일반 task 보다 높은 우선 순위를 가져야함.



Thread Scheduling

  • Local Scheduling
    • User level thread : 사용자 thread library 에 의해 어떤 쓰레드를 스케줄할지 결정
    • OS 는 스레드의 존재를 모름. 해당 process 에게 CPU 를 줄지 안줄지 결정함.
  • Global Scheduling
    • Kernel level thread : OS 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정



Algorithm Evaluation

알고리즘 성능평가

  • Queueing models
    • arrival rate, service rate 같은 확률 분포를 가지고 performance index 값을 게산.
  • Implementation & Measurement
    • 실제 시스템에 구현해서 실제 작업에 대한 성능을 측정 비교
  • Simulation
    • 모의 프로그램을 만들어서 trace 를 입력으로 해서 결과 비교

최근에는 실 시스템에서 돌리는 것을 더 많이 사용한다.



출처 / 참고

반효경 교수님의 2014 운영체제 5. CPU Scheduling, 2 강의를 듣고 포스팅하고,
공룡책을 읽고 추가 정리합니다.

사진 출처는 강의 자료.

profile
0년차 iOS 개발자입니다.

0개의 댓글