[OS] CPU 스케줄러

스케줄링 대상은 Ready Queue에 있는 프로세스

FCFS(First Come First Served)

특징

먼저 온 프로세스를 먼저 서비스 해주는 방식

비선점형(Non-Preemptive) 스케줄링

일단 CPU를 잡으면  CPU burst가 완료될 때까지  CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링

CPU burst: 프로그램 수행 중 연속적으로 CPU를 사용하는 구간, 스케줄링 단위

문제점

convoy effect: 소요시간이 긴 프로세스가 먼저 도착하면 효율성이 낮아지는 현상이 발생한다

 

 

SJF(Shortest - Job - First)

특징

다른 프로세스가 먼저 도착했어도 CPU burst 시간이 짧은 프로세스에 할당

비선점형(Non-preemptive) 스케줄링

문제점

Starvation

효율성을 추구하는게 중요시된 나머지 사용 시간이 긴 프로세스는 영원히 CPU를 할당받을 수 없다.

 

 

Priority Scheduling

특징

우선순위가 가장 높은 프로세스에게 CPU를 할당, 우선 순위는 정수로 표시하고 작을 수록 우선순위가 높다

선점형(Preemptive)방식: 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다

비선점형(Non-Preemptive)방식: 더 높은 우선순위으이 프로세스가 도착하면 Ready Queue의 Head에 넣는다

문제점

Starvation

무기한 봉쇄(Indefinite blocking)

실행 준비는 되어있으나, CPU를 사용못하는 프로세스를 CPU가 무기한 기다리는 상태

 

해결책

aging

아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다

 

 

Round Robin(RR) 가장 공정!!

특징

현대적인 CPU 스케줄링 방식

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다

할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다

RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다

RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다(PCB)

장점

Response Time이 빨라진다

n개의 프로세스가 ready queue에 있고 할당시간이 q인 경우 각 프로세스는 q 단위로 CPU시간의 1/n을 얻는다.

즉, 어떤 프로세스도 (n-1)q 시간 이상 기다리지 않는다

프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다

 

주의할 점

설정한 Time Quantum이 너무 커지면 FCFS와 같아진다. 너무 작으면 스케줄링 알고리즘의 목적에는 이상적이지만, 

context switch로 overhead가 발생한다

 

---

 

github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS

JaeYeopHan/Interview_Question_for_Beginner

jhann.tistory.com/24?category=907648

[OS] 프로세스와 스레드의 차이