[운영체제] #5 CPU Scheduling

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

프로그램이 실행되면 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
먼저 온 순서대로 처리

Process	Burst Time
P1	24
P2	3
P3	3

Process	Waiting Time
P1	0
P2	24
P3	27
Average	(0 + 24 + 27) / 3 = 17

• Convoy Effect : 먼저 도착한 프로세스가 너무 오래 걸려서 평균 대기 시간이 길어짐...

Process	Burst Time
P2	3
P3	3
P1	24

Process	Waiting Time
P1	0
P2	3
P3	6
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 보장

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

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

Process	Waiting Time
P1	0
P3	7 - 4 = 3
P2	7 - 2 + 1 = 6
P4	7 - 5 + 1 + 4 = 7
Average	(0 + 6 + 3 + 7) / 4 = 4

SRTF

Shortest Remaining Time First

Process	Waiting Time
P1	0 + 2 + 1 + 2 + 4 = 9
P2	0 + 1
P3	0
P4	0 + 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 를 저장했다가 바로 시작할 수 있는 환경에서 좋다.

Process	Burst Time
P1	53
P2	17
P3	68
P4	24

• 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 강의를 듣고 포스팅하고,
공룡책을 읽고 추가 정리합니다.

사진 출처는 강의 자료.