CPU Scheduling Algorithms

- 각 알고리즘 성능 척도(하나의 CPU brust 동안)

1) 시스템 입장에서의 성능 척도

- CPU 하나 가지고 최대한 많은 일을 시킬수 있으면 성능이 좋음

1. CPU utilization(이용률)

- 전체 시간 중 CPU가 놀지 않고 일한 시간 비율

- 가능한 CPU를 바쁘게

2. Throughput(처리량)

- 주어진 시간 동안 몇개의 작업을 완료 했나

 

2) 프로그램 입장에서의 성능 척도

- 프로그램이 최대한 빨리 끝날 수 있으면 성능이 좋음

1. Turnaround time(소요시간, 변환시간)

- CPU를 쓰러 와서 다 쓰고 나갈때까지의 시간(CPU brust time)

- wating time + CPU 사용 시간

2. Waiting time(대기 시간)

- ready 상태에서 CPU를 기다리는 시간

- 매 CPU brust 기간동안 타이머 등의 이유로 여러번 CPU를 사용하고 반납할텐데 그때마다 기다리는 모든 시간을 합친 시간

3. Response time(응답 시간)

- CPU brust에서 처음 CPU를 사용하기까지 기다린 시간

 

 

CPU 스케줄링 알고리즘

1) FCFS(First-Come First-Served)

- 비선점형, nonpreemptive 알고리즘

- 먼저 온 고객을 먼저 서비스해준다

- CPU를 길게 쓰는 job이 하나 실행되면, CPU를 아주 짧게만 쓰고 나가는 job들이 앞서 작업이 끝날때까지 무작정 기다리기만 해야됨

- p1은 24초, p2는 3초, p3는 3초가 소요됨

- 0초에 간발의 차로 p1,p2,p3이 도착

- waiting time: p1 = 0, p2 = 24, p3 = 27

- 평균 waiting time: (0+24+27)/3 = 17초

- Convoy effect: short process가 긴 시간을 기다려야 할수도 있음

- 하지만 반대로 p2,p3,p1 순서대로 실행되면 평균 3초밖에 안걸림, 맨 처음 어떤 프로스세가 실행되느냐가 중요해짐

 

2) SJF(Shortest-Job-First)

- 온 순서대로 CPU를 주는 것이 아닌 CPU brust가 일찍 끝나는 프로세스 먼저 CPU를 준다

- 짧게 쓰는 프로세스들이 빨리 쓰고 나가므로 ready queue가 항상 짧음

- 주어진 프로세스들의 평균 대기 시간이 가장 짧음, minimum average waiting time을 보장

1. nonpreemptive일때

- 일단 가장 짧은 프로세스한테 CPU를 줬으면, 곧바로 더 짧은 프로세스가 오더라도 일단 실행되고 있던것이 계속 실행

2. preemptive일때

- 이미 CPU를 가지고있더라도 더 짧은 시간의 프로세스가 도착하면 다시 CPU를 뺴앗고 더 짧은 프로세스에게 CPU를 줌

- ready queue에 추가된 프로세스의 CPU brust time과 이미 CPU를 가지고 있는 프로세스의 남은 CPU brust time을 비교함

- 항상 제일 짧은 프로세스가 실행되기 때문에 Shortest-Remaing-Time-First(SRTF)라고도 부름

 

- nonpreemptive일때

- 0초에는 p1밖에 없으므로 p1에게 먼저 할당

- p1이 끝난 시점에는 p2,p3,p4 모두 기다리고 있음

- 그 중 가장 짧은 p3에게 먼저 할당

- 그리고 나머지도 짧은 순서대로 할당

 

- preemptive일때

- 2초일때 p1은 7초 중 2초를 사용해서 5초가 더 남았고, p2는 2초에 도착해서 4초를 사용하면됨

- p2가 실행시간이 더 짧으므로 p1껄 뺏어서 p2에게 먼저 줌

- 이렇게 매 프로세스가 ready queue에 도착할때마다 CPU brust time을 비교함(CPU 스케줄링이 자주 필요함)

- nonpreemptive보다 평균 대기시간이 더 짧음(어떠한 알고리즘보다 짧음)

 

SJF 문제점:

1. CPU brust time이 긴 프로세스는 영원히 차례가 안올수 있음(Starvation, 기아현상)

- 1초짜리 프로세스가 계속해서 들어온다면 100초짜리 프로세스는 영원히 차례를 못받음

2. CPU brust time을 정확히 알수 없음

- SJF 알고리즘은 CPU brust time을 비교해서 CPU 스케줄링을 하는데, 사실은 해당 프로세스의 CPU brust time을 정확하게 알수는 없음

- 이번의 CPU brust time을 알수는 없지만 추정은 할수 있음, 과거 해당 프로세스의 CPU brust time으로 예측하면 됨

 

- exponential averaging: 예측할수 있는 식

1번: 실제 CPU 사용 시간

2번: CPU 사용을 예측한 시간(ͳ: 타우)

- t(n)은 n번째 실제 CPU사용 시간, 1~n까지 CPU 사용 시간은 알고 있음

- 여기서 ͳ(n+1)은 다음번 CPU 사용 예측 시간

3번: 일정 비율씩 곱할때 사용하는 값, 0~1사이, 4번의 a와 1-a를 합하면 1이됨, 일정 비율씩 반영한다는 의미

4번: ͳ(n+1) = at(n) + (1-a)ͳ(n)

- 위 식에 n자리에 n-1을 집어넣고, 모든 ͳ를 같은 식으로 대입해서 한쪽에 ͳ를 ͳ(0)만 남기면 식을 풀수 있음

- 이때 a는 뒤로 갈수록 점점 작아지니 최신 CPU 사용시간은 가중치를 높게 반영하고 오래된 CPU 사용시간은 가중치를 좀더 낮게 반영한다는 뜻

- a가 0이나 1인경우는 조금 극단적인 예

 

 

3) Priority Scheduling

- 우선순위 스케줄링

- 우선순위가 높은 프로세스에게 먼저 CPU를 준다

- preemptive: 우선순위가 더 높은 프로세스가 오면 기존 CPU 사용하고 있던 프로세스에게서 뺏어온다

- nonpreemptive: 우선순위가 더 높은 프로세스가 오더라도 기존걸 뻇진 않는다

- 프로세스마다 하나의 정수값으로(int) 우선순위를 가지고 있고, 값이 작을수록 우선순위가 큼

- SJF와 비슷, 단지 시간보다는 우선순위를 보고 정함

- SJF와 똑같이 우선순위가 낮은 프로세스는 영원히 못받을수도 있음(기아현상)

- 기아현상을 해결하기 위해 Aging 기법을 사용함, 오래기다리면 기다릴수록 우선순위를 높여줌, 그러면 우선순위가 낮더라도 오래 기다리면 우선순위가 점점 높아져서 언젠가는 사용을 할수있게 됨

 

 

4) Round Robin(RR)

- 현대 CPU 스케줄링의 기반

- 타이머를 주고 일정시간이 지나면 CPU를 뻇는다

- 이전 강의에 설명했던 CPU 동작방법들이 RR을 기반으로 설명이 되어있음

- RR의 가장큰 장점은 "응답시간"이 가장 짧음 모든 프로세스가 짧게씩만 쓰고 넘겨주기 때문에 오래 기디리지 않고 CPU를 받을 수 있음

- CPU brust time이 적은 프로세스는 한번의 타이머만에 자기 일을 끝마치고 갈수도 있음

- 반면 오래 사용하는 프로세스는 그만큼 짧게 여러번 기다려야됨

- 타이머를 길게 해놓으면 FCFS 방법이 됨

- 타이머를 짧게 해놓으면 문맥교환시 발생하는 오버해드가 커지게됨

- 짧게 쓰는 프로세스는 짧게만 쓰고 나가고 나머지는 계속 반복해서 사용함

- 만약 100초짜리 프로세스가 4개 있으면 10초씩 번갈아가면서 쓰다가 400초가 되면 그떄 동시에 다 빠져나가게 됨

- 그래서 비슷한 프로세스끼리는 마지막에 비슷하게 끝나기 때문에 average turnaround time이 김

- 비슷하다면 차라리 타이머를 길게 잡는게 효율이 좋음

- CPU 기다리는 시간이 본인이 CPU를 사용하려는 시간과 어느정도 비례함

- 프로세스가 1~4까지 있을때

- 각 타이머(time quanturn) 시간마다 average turnaround time을 구한 값

 

 

Multilevel Queue

- queue를 하나가 아닌 여러 줄을 둔 상태, 위에 있을수록 우선순위가 높다

- 한번 배정받은 queue가 정해지면 그 queue에서만 기다려야됨

- 큐를 배정하기 위해 프로세스의 사용 시간을 예측해야됨

 

- ready queue를 2개로 분리한 예시

- interactive가 많은 job은 foreground에 no human interaction한 job은 background에 기다리게함

 

- 각 줄마다 다른 스케줄링을 사용

- foreground에서는 사람과 interacive 하기 때문에 RR을 사용하여 응답시간을 짧게 함

- background에서는 CPU만 오래동안 사용하는 프로세스기 때문에 괜한 문맥교환 오버헤드를 줄이기 위해 FCFS를 사용

 

- 무조건 foreground 다 사용하고 나중에 background에게 주는 방식일 경우 starvation 현상이 나타날수 있음

- 그래서 각 큐에 적절한 비율로 할당하는 방식을 많이 사용

 

 

Multilevel Feedback Queue

- 일이 진행됨에 따라 배정받은 queue가 변할수도 있는 형태

- 맨 위에는 타이머를 짧게 줘서 빠른 일처리가 가능하게 하고, 중간에는 조금 길게 줘서 어느 정도는 일이 진행되도록 하고 맨 밑에는 FCFS방식을 사용하여 긴 프로세스들이 처리가 가능하도록 함

- 맨 처음 들어온 프로세스는 제일 위 큐에 할당됨, 그리고 한 타이머 내에 일을 못끝내면 한칸 밑에 큐로 들어감

- 그래서 밑으로 내려갈수록 오래 기다리지만 시간은 좀더 할당받는 형태가 됨 

- 들어오자 마자 맨 위 큐로 가기 때문에 실행시간을 예측할필요가 없어짐

 

 

Real-Time Scheduling

- 데드라인 있는 프로세스의 경우 먼저 CPU 스케줄링을 해서 데드라인을 지킬수 있도록 한다

1. Hard real time scheduling

-  정해진 데드라인 내에 반드신 끝나야 하는 job

2. soft real time scheduling

- 일반 프로세스에 비해 높은 우선순위(priority)를 갖는 job

 

Thread Scheduling

1. Local Scheduling

- user level thread의 경우 OS가 스레드의 존재를 모르기 때문에 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정

2. global scheduling

- kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

 

 

알고리즘 평가(Algorithm Evaluation)

1. Queueing models: arrival rate(도착률), service rate(처리률)등을 수학적으로 계산해서 각 알고리즘 성능 측정

2. 구현, 성능측정: 실제 시스템을 돌려봐서 알고리즘 성능 측정

3. 모의실험: 실제 OS를 수정해서 성능 테스트 하기엔 시간이 많이 소요되므로 모의 프로그램으로 작성후 테스트