CPU scheduling

cpu scheduling algorithms

- nonpreemtive(강제로 빼앗지 않는 방법)-비선점형

- preemtive(강제로 빼앗는 방법)- 선점형

성능 척도- performance index, scheduling criteria

 

시스템 입장에서 성능 척도.

- cpu utilization(이용률) - 전체 시간 중에서 cpu가 놀지 않고 일한 시간 비율

- throughput(처리량) - 주어진 시간 동안 몇 개의 작업을 하느냐. 

 

프로그램 입장에서 성능 척도 - 시간이 빨리 처리되는 것이 중요하다. 

- turnaround time(소요시간. 반환 시간) - cpu를 사용한 시간. 즉 특정 프로세스 수행 시간( cpu를 쓰러 들어와서 i/o 작업을 하러 나가기 전까지의 시간)

- waiting time( 대기시간)- cpu를 기다리는 시간

- response time(응답 시간)- 처음으로 cpu를 얻기까지 걸린 시간

 

cpu 스케줄링 알고리즘

- FCFS(first come first served) : 먼저 온 순서대로 처리한다. - 비선점형 스케줄링. 앞선 프로세스가 cpu를 내놓지 않으면 뺏을 수 없다. 비효율적인 방법. 

스케줄 순서를 간트 차트로 나타낸다. 도착 순서에 따라서 평균 대기 시간이 달라질 수 있다. 

convoy effect : 짧은 프로세스들 앞에 긴 프로세스가 있어서 긴 프로세스 뒤에서 기다리는 것. 

 

- SJF(shortest job first) -  cpu 사용시간이 짧은 프로그램한테 cpu를 먼저 준다. 각 프로세스의 다음번 cpu burst time을 가지고 스케줄링에 활용, cpu burst time이 가장 짧은 프로세스를 제일 먼저 스케줄. 

주어진 프로세스들에 대해 평균 대기 시간의 최소를 보장함. minimum average waiting time. - preemptive 버전에 해당한다. 

nonpreemptive 타입에서는 일단 cpu를 잡으면 cpu burst가 완료될 때까지 cpu를 빼앗기지 않는다. 

preemptive : 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 cpu burst time을 가지는 새로운 프로세스가 도착하면 cpu를 빼앗김. 이 방법을 shortest-remaining-time-first(SRTF)라고 부른다. 

nonpreemptive버전은 cpu를 다 쓰고 나가는 시점에 스케줄링을 할지 안 할지 결정을 하고 preemptive는 새로운 프로세스가 도착을 하면 언제든지 스케줄링이 이루어질 수 있다. 

이 알고리즘은 2가지 문제점이 있다.

첫 번째 문제는 starvation이다.(기아 현상) sjf는 cpu 사용시간이 짧은 job을 선호해서 cpu 사용시간이 긴 프로세스는 영원히 cpu를 못 받을 수 있다. 

두 번째 문제점은 cpu 사용시간을 미리 알 수 없다. 하지만 추정은 할 수 있다. 과거의 cpu burst time을 이용해서 추정. 

 

- priority scheduling - 우선순위가 높은 것 순서대로. 여기에도 nonpreemptive버전과 preemptive 버전이 있다. 각 프로세스마다 우선순위 숫자가 주어진다. 우선순위가 높을수록 작은 숫자. sjf도 우선순위 스케줄링의 일종이다. 우선순위가 낮은 프로세스가 오래 기다려서 영원히 cpu 사용을 할 수 없을 수도 있다는 것이 문제점이다. starvation. 

이를 해결하기 위해 aging 기법을 도입하게 된다. 오래 기다리게 되면 우선순위를 조금씩 높여주자는 것이다. 

 

- round robin(RR) - 현대적인 컴퓨터 시스템들은 RR에 기반하고 있다. preemptive. 선점형 스케줄링이다. 동일한 크기의 할당 시간을 세팅해서 주고 timer interrupt로 ready queue의 제일 뒤에 가서 줄을 서게 된다. 

장점은 응답 시간(response time) cpu를 처음 얻는 시간이 짧아진다. 누구든 cpu를 얻을 수 있다. 

할당 시간이 q라면 어떤 프로세스든 (n-1) q time unit 이상 기다리지 않는다. 

대기 시간이 본인의 cpu 사용 시간에 비례하게 된다. cpu를 길게 쓰는 프로세스는 여러 번 반복해서 기다려야 하기 때문이다. 

q를 길게 잡으면 FCFS와 같은 스케줄링 알고리즘이 된다. 

q를 작게 잡으면 context switch 오버헤드가 커진다. 시스템 전체의 성능이 나빠질 수 있다. 적당한 규모의 time quantum(할당 시간)을 주는 것이 좋고 일반적으로 10ms~100ms으로 알려져 있다. 

일반적으로 SJF보다 average turnaround time이나 waiting time은 길어질 수 있지만 response time은 더 짧다. 

cpu 사용시간이 모두 동일한 프로세스가 여러 개라면 동시에 빠져나가게 된다. 따라서 waiting time이 길어지는 측면에선 별로일 수 있다. 따라서 cpu 사용 시간이 짧은 프로세스와 긴 프로세스가 섞여 있을 때 효과적이다.