4.CPU Scheduling

http://www.kocw.net/home/search/kemView.do?kemId=1046323

운영체제

---

CPU 스케쥴링

: ready queue 에 들어와있는 프로세스 중 어떤 프로세스에 cpu 를 할당해 줄 것인지( CPU Burst )

1. 누구한테 줄건지

2. 언제까지 줄건지

- cpu burst 굉장히 긴 job 에 계속 주면, 잠깐 쓰고 나갈 i/o bound job 도 계속 기다려야 하는 상황 발생

 

[ Scheduling Criteria ] 

( 시스템 입장에서 )

CPU utilization : CPU 가 놀지 않고 사용된 비율 - 높을 수록 좋음

throughput(처리량) : 주어진 시간동안 몇 개의 작업을 완료했는지 - 많이 처리할 수록 좋음 

 

( 프로세스 입장에서 )

1. turnaround time(소요시간) : cpu 쓰러 들어와서 다 쓰고 나갈때까지 걸린 시간 

= 기다린 시간, cpu 사용한 시간 ... 다 합쳐서 나갈 때까지 걸린 총 시간 

2. response time(응답시간) : ready queue 들어와서 처음으로 cpu 쓸 때까지 기다린 시간 

3. wating time : ready queue 에서 기다린 시간 

-> 선점형 스케쥴링에서, 중간에 뺏기면서 기다리는 시간 여러 번 발생, 다 합친 게 wating time

 

+ non-preemptive / preemptive 스케쥴링

---

1. FCFS 

- 비선점형 

- 제일 긴 게 가장 먼저 도착하면 비효율 발생 

 

2. SJF

- 시간 제일 짧은 job 가장 먼저 수행시키기

- non-preemptive 이므로, 지금 수행중인 것보다 더 짧은 프로세스 들어와도 기다려야 함

- 처음에 가장 긴 것만 들어오면 뺏을 수 없기 때문에 기다려야 함

- 프로세스가 작업 끝내고 나갈 때 스케쥴링 수행

 

3. preemptive SJF == SRF(Shortest Remain time First)

- 남은 시간 적은 프로세스 먼저

- 평균 대기시간을 최소화 하기에 적합

- 새로운 프로세스 도착할 때마다 스케쥴링 수행 

-> (1) starvation 발생 가능 : 사용시간이 긴 프로세스는 영원히 대기

-> (2) cpu 사용시간을 미리 알 수 없다는 것

: 실제로는 얼마나 쓰고 나갈 것인지 알 수 없다? - 추정치로 사용 / 과거에 얼마나 썼는지

~> exponential averaging :

(n+1)번째 cpu 사용 예측 시간 = a*(n 번째)실제 cpu 사용 시간 + (1-a)*(n 번째)사용 예측 시간

( a : 0과 1 사이 일정 비율, 더 과거일 수록 조금 반영 )

 

Priority Scehduling

~ 비선점 / 선점 방식 존재 

~ 프로세스 마다 우선순위 부여 , 일반적으로 작은 수가 높은 우선순위 

..SJF 는 CPU Burst time 을 우선순위로 사용하는 스케쥴링 방법

-> 기아 현상 발생 => 해결방안 : Aging : 우선순위 아무리 낮더라도 높여서 cpu 얻을 수 있도록

 

4. Round Robin

: Time sharing System 에 기반한 방식 + Preemptive ( timer 끝나면 timer interrupt 발생 )

: Context Switching 제공 - 기존에 진행된 정도 저장

- 응답시간이 빨라진다..cpu 최초로 얻을 수 있는 시간 적게 소요된다

- 실행 시간과 대기 시간 길이 비례

-> cpu 사용시간이 크고 작은 것들 같이 있을 때 사용하기 좋다

-> ( 모두 동일한 시간이라면 다 쪼개서 수행하니까 다같이 오래걸려서 나가기 때문에 비효율, 오버헤드만 발생 )

 

- 시간 할당량이 커지면 FCFS 랑 같아지고

- FCFS 가 작아지면 Context Switching 자주 발생 - 오버헤드, 시스템 전체 성능 하락 

 

-> SJF 보다, turnaround-time 이나 waiting-time 은 길어질 수 있지만, response-time 은 훨씬 짧아짐

---

Multilevel Queue : ready queue  를 여러개로 분할 

- foreground / background

- 각 큐마다 독립적인 스케쥴링 알고리즘을 가짐

: 큐 마다 우선순위 존재

: 큐에 대한 스케쥴링 필요

ex) 높은 우선순위에 있는 프로세스 처리 , 비어있다면 낮은 우선순위 큐의 프로세스 수행

ex) 각 큐에 time slice 할당-80%는 우선순위 높은 큐에, 20%는 우선순위 낮은 큐에 할당

 

Multilevel Feedback Queue

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

-> 큐의 개수 / 각 큐의 스케줄링 알고리즘 

-> 프로세스를 상위 큐로 보내는 기준 / 프로세스를 하위 큐로 보내는 기준

-> 프로세스가 어느 큐로 들어갈 지에 대한 기준

ex) 새로운 job - time slice 가장 작은 큐에 할당 

-> 정해진 시간 내에 수행 완료 못할 경우 더 낮은 우선순위의 큐로 내려감

-> 또 완료 못 하면, 더 낮은 FCFS 큐로 내려감

...높은 우선순위에 시간 적게 할당, 낮은 우선순위 FCFS 

---

* Multi-Processor Scheduling

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

- Symmetric MultiProgramming(SMP) : 각 프로세서가 각자 알아서 스케쥴링 결정

- Asymmetric Multiprogramming : cpu 여러 개 중 하나가 전체적인 제어 관리 - 데이터 접근이나 공유를 책임지고 나머지 프로세서가 거기에 따르는 방식 

 

* Real-Time Scheduling 

- Hard Real-time : real-time job 은 deadline 안에 작업이 완료되는 걸 보장되도록 스케줄링

- Soft Real-time : 일반 프로세스에 비해 높은 우선순위 가지는 정도, deadline을 꼭 보장은 x

 

* Thread Scheduling

- Local Scheduling  : user level 쓰레드의 경우, 사용자 수준의 쓰레드 라이브러리에 의해 어떤 쓰레드 스케쥴할 지 결정

-> os 가 모르고, 프로세스가 어느 쓰레드에 스케쥴링 할 지 결정하는 수준

 

- Global Scheduling : kernel level 쓰레드의 경우, os 가 알고있기 때문에 어떤 쓰레드 스케쥴할 지 결정