cpu 스케쥴링이란?
Cpu 스케쥴링은 ready queue에 있는 프로세스 중 cpu를 할당할 프로세스를 결정하는 것이다.
cpu 스케쥴러의 두가지 종류
선점형(preemptive)
이미 작업 중인 프로세스에 대해서 우선 순위가 더 높은 프로세스가 등장한다면 context switching이 일어난다.
빠른 응답이 가능해 실시간 시스템이나 시분할 시스템에 적합니다. 하지만, context switching이 잦아 오버헤드가 발생한다.
context switching이란?
비선점형(non-preemptive)
이미 작업 중인 프로세스에 대해서 우선 순위가 더 높은 프로세스가 등장하더라도 context switching이 발생하지 않는다.
모든 프로세스에 대해 공평하게 작업이 가능하지만 앞에 긴 작업이 진행 중인 경우, 짧은 작업은 대기 시간이 길어지고 평균 처리시간이 증가한다.
선점형 vs. 비선점형
- 선점형 : 프로세스의 cpu를 강제로 뺏어서 실행
- 비선점형 : cpu를 획득한 프로세스가 스스로 반납하기 전까지 cpu를 뺏기지 않는 방법
디스패처
디스패처란?
Cpu할당을 결정하면 이를 이양하는 작업이 필요한데, 선택된 프로세스가 cpu를 할당받고 작업을 수행할 수 있게 환경설정하는 코드를 말한다.
-
현재 수행 중인 문맥을 pcb에저장하고, 새로운 프로세스의 문맥을 pcb로부터 복원한 후 그 프로세스에게 cpu를 넘기는 과정을 수행한다.
-
디스패처가 프로세스를 정지시키고 다른 프로세스에게 cpu를 전달하기까지 걸리는 시간을 디스패치 지연시간이라고 한다.
디스패치 지연시간의 대부분은 context switching 오버헤드에 해당한다.
-> 선점형 cpu 스케쥴링에서 사용된다.
cpu 스케쥴링 알고리즘
Ready queue에 있는 프로세스를 대상으로 스케쥴링을 한다.
1) first come first served(fcfs)
- 먼저 온 순서대로 처리한다.
- 선점형 스케쥴링
- 소요시간이 긴 프로세스가 먼저 도착하면 짧은 프로세스들은 대기시간이 길어진다 (convoy effect)
프로세스마다 대기시간은 앞의 프로세스가 완료될 때까지의 시간이고, 평균 대기시간은 이를 프로세스 수로 나눈 시간이다.
2) round robin (rr)
- 프로세스가 ready queue를 순차적으로 돌며 cpu를 할당한다.
- 비선점형 스케쥴링
- 프로세스 작업의 시간 제한이 있다. 시간이 경과하면, ready queue의 끝에 추가되고 다음 프로세스가 cpu를 할당받는다.
할당시간을 time slice/time quantum 이라고 한다.
이 시간이 짧아질 수록 모든 프로세스가 동시에 작업하는 것처럼 보인다.
하지만, 그만큼 context switching이 많이 발생하여 오버헤드가 발생한다.
이 시간이 길어질수록 fcfs 방식과 유사해진다.
3) priority scheduling
- 우선순위가 가장 높은 프로세스에게 cpu를 할당하는 스케쥴링이다.
- 선점/비선점 둘다 가능
- 선점형 : 더 높은 우선순위를 가진 프로세스가 오면 실행 중인 프로세스를 중지하고 cpu를 반환한다.
- 비선점형 : 더 높은 우선순위를 가진 프로세스가 오면 ready queue의 head에 넣는다.
- 우선순위가 낮은 프로세스는 차례가 오지 않는 기아 상태(starvation)가 발생할 수 있다.
+ aging으로 시간이 지나면 우선순위를 높여 해결이 가능하다.aging : 기다리는 시간이 길어질 수록 우선순위를 조금씩 높임
4) shortest job first(sjf)
- cpu burst time이 짧은 프로세스에게 cpu를 할당한다.
- 비선점형으로 더 짧은 작업시간을 갖는 프로세스가 오면, ready queue에 넣는다.
- 시스템 프로세스 수를 최소회하고, 스케쥴링 부하가 감소한다.
- 메모리를 절약하여 시스템 효율이 향상된다.
- 작업시간이 길면 차례가 오지 않는 기아 상태(starvation)가 발생할 수 있다.
5) shortest remaining time first(srt)
- 잔여 실행시간이 짧은 프로세스에게 cpu를 할당한다.
- 선점형으로, 잔여 실행시간이 더 짧은 프로세스가 오면 cpu를 반납한다.
- 주어진 집합에 대해 최소 평균 대기시간을 제공한다.
- 잔여 실행 시간을 예측해야한다.
이 다섯개 이외에도,
Highest response ratio nest(hrrn), multi-level queue(mlq), multi-level feedback queue(mfq) 등이 있다.
Reference : https://jgrammer.tistory.com/entry/운영체제-CPU-스케쥴링 https://velog.io/@secho/OS-Cpu-스케쥴링
