#5-2. CPU SCHEDULING

* 복습

cpu 스케줄링의 매커니즘 : ready 큐에 있는 프로세스중 누구한테 cpu를 줄지 정하는 것.
(크게 두가지 이슈가 있다)

1. cpu burst에 들어온 수많은 프로세스들중 누구한테 줄까?
2. cpu를 프로그램한테 줬으면 I/O를 하러 나갈때까지 계속 줄꺼냐? 아니면 중간에 뺏을꺼냐?

 

즉, 누구한테 줄것인가? 일단 줬으면 중간에 뺏어 오게 할 수 있게 할 것인가.
(공평도 필요하지만 효율적으로 하기위한 매커니즘)

* CPU 스케줄링 알고리즘

 

 

# 알고리즘들을 크게 두가지로 나누어 본다면,

 1) NONPreemtive 한 스케줄링 : 강제로 cpu를 빼앗지 않는 방법 (일단 cpu한번 주면 자진반납할때 까지 cpu보장해주는 방법- 비선점형)

 2) Preemtive 한 스케줄링 : 언제든지 뺏어올 수 있는 방법 (선점형, 요즘은 이걸 많이씀)

 

 

* CPU 스케줄링 성능 척도

 

 

 

# 성능척도를 크게 두가지로 생각해 볼수 있다.
 1) 시스템 입장에서의 성능 척도
  : CPU 하나를 가지고 최대한 일을 많이 시키면 좋은것(파란색 2개)
 2) 프로그램 입장에서의 성능 척도
  : 내가(프로세스) CPU를 빨리 얻어서 빨리 끈나면 좋은것, 그래서 시간과 관련이 있는 3가지를 고려(빨간색 3개)

# 척도 소개

 (처음 2개는 사장 입장)
 - CPU utilization : 전체 시간중에서 cpu가 놀지 않고 일한 시간.
 - Througput : 주어진 시간 동안에 몇개의 작업을 처리 하였느냐

 

 (밑에 3개는 고객입장(빨리 서비스 받고 싶다.))
 - Turnaround time : cpu를 쓰러 들어와서 다쓰고 나갈때 까지의 시간. (waiting time + cpu이용시간)
 - Waiting time : cpu를 쓰고자 ready큐에서 기다리는 시간
 - Response time : ready큐에 들어와서 cpu쓰겠다고 들어와서 처음으로 cpu를 얻기까지 걸린 시간.

 

cf> waiting time과 response time의 차이를 구분해보자면, preemtive(선점형)인 경우, cpu를 계속해서 돌려쓰게 되는데
1) waiting time : 기다리는거 모두 합한 값.
2) response time : 제일 처음 기다린 시간.
3) turnaround time : waiting time + 실행 시간

 

???) 시간을 왜 굳이 3개씩이나 나누지?
: 응답시간을 둔 이유는 time sharing 환경에서는 처음으로 cpu를 얻는 시간이 사용자 응답과 관련해서 굉장히 중요한 시간의 개념이다. 그래서 반환시간도 있고 대기시간도 있지만 응답시간을 별도로 둬서 이야기 하는 이유이다!

* FCFS
 : 먼저오면 먼저 처리 (NoonPreemtive)

 

 

 

# NoonPreemtive한 스케줄링이다. 중간에 시간이 많이 걸리는게 있다면 비효율적이다.

 

 

 

# 앞에 경우와 비교해보면 평균 waiting time이 짧아진것을 볼 수 있다.

# Convoy effect : 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 많은 시간을 기다리는 효과를 의미. (부정적 효과)

 

 

* SJF
 : 수행시간이 짧은게 먼저 처리

 

 

 

# Average waiting time이 최소화 되는 방법.

 

# SJF 알고리즘도 두가지 방법으로 나누어서 생각해 볼수 있다.

1) NoonPreemtive 한 방법
2) Preemtive한 방법 : cpu를 줬다 하더라고 남은 수행시간이 더 짧은 애가 오면 cpu를 빼앗긴다.(SRTF 라고도 부른다)

 

 

# 두가지 예를 봐보자

 

1) NoonPreemtive version.

 

 

2) Preemtive version.

 

 

 

# Preemtive 버전이 더 짧다는것을 알수 있다. (더 좋다.)

 

 

???) 그러나 두가지 문제점이 있다.

 

1) starvation(기아현상) : SJF는 수행시간이 짧은거를 선호 하기 때문에, 수행시간이 긴 프로세스는 영원히 서비스를 못 받을 수도 있다.

2) 매번 cpu사용 시간을 미리 알수 없다는게 문제이다. 그럼 SJF는 실제로 적용 못하나요? => 정확히는 알수 없지만, 과거의 사례(과거의 CPU burst time)을 통해서 추정한다

 

 

 

# 다음 cpu burst time 예측

 : 점화식을 해석해 보면 과거일수록 반영하는 가중치가 줄어든다.

 

 

 

 

 

 

 

 

 

* Priority Scheduling 
 : 우선순위가 높은 프로세스한테 cpu할당

 

 

 

# Priority Scheduling 알고리즘도 두가지 방법으로 나누어서 생각해 볼수 있다.

1) NoonPreemtive 한 방법
2) Preemtive한 방법 : cpu를 줬다 하더라고 남은 수행시간이 더 짧은 애가 오면 cpu를 빼앗긴다.(SRTF 라고도 부른다)

cf> 작은 숫자가 우선순위가 높다.

 

# Aging : 아무리 우선순위가 낮더라 하더라도, 시간이 지나게 되면서 우선순위를 조금씩 높여주자(starvation의 해결책!)

 

* Round Robin
: 가장 현대적인 스케줄링 알고리즘, 여태 우리가 배웠던 시스템이 RR이다.

 

 

 

# RR의 장점 : cpu 응답시간이 빨라진다. (누구든지 조금만 기다리면 cpu를 맛볼수 있다.)
(n-1)q 만 기다리면 내 차례가 돌아온다. (q라는 퀀텀을 짧게 잡아줄수록 내 차례가 빨리 다가온다.)

 

#
1) q를 너무 크게 잡으면 : FCFS
2) q를 너무 짧게 잡으면 : context switch 오버헤드가 커진다.(시스템 전체 성능이 나빠질수 있다.)
 => 즉, 너무 크거나 짧게 q를 잡으면 성능이 나빠진다.

 

 

# 할당 시간(q)이 20 인경우의 예제

 

 

 

# RR의 장점 : Response time이 줄어든다!!