CPU 스케줄링

CPU 스케줄링에 대해 알아보자.

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

선점형 스케줄링
하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법이다.

FCFS(First Come First Served)
먼저 온 순서대로 서비스 처리
convoy effect - 소요 시간이 긴 프로세스가 먼저 도달해 평균 대기 시간이 길어지게 되어 효율성을 낮추는 현상 발생
비선점형 스케줄링

SJF(Shortest-Job-First)
다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선 할당
starvation - 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태가 발생
비선점형 스케줄링

SRTF(Shortest Remaining Time First)
새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이뤄진다.
starvation
선점형 스케줄링

priority Scheduling 
우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
선점형 스케줄링 - 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점
비선점형 스케줄링 - 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.
starvation
indefinite blocking(무기한 봉쇄) - 실행 준비는 되었으나 CPU를 사용 못하는 프로세스를 CPU가 무기한 대기하는 상태 발생
해결책으로는 aging이 있다. 아무리 우선 순위가 낮은 프로세스라도 오래 기다리면 우선 순위를 높이는 것이다.

Round Robin
현대적인 CPU 스케줄링
각 프로세스는 동일한 크기의 할당 시간을 가짐
할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤로 가 대기 
CPU 사용 시간이 랜덤한 프로세스들이 섞여 있을 때 효율적
프로세스의 context를 저장할 수 있기에 가능
할당시간(time quantum)이 너무 커지면 FCFS와 같아진다. 반대로 너무 작아지면 잦은 context switch로 overhead가 발생한다. 따라서 적절한 time quantum을 설정하는 것이 중요하다. 

 

여기서 context switchingd이란 작업의 주체가 현재 context를 잠시 중단하고 다른 context를 실행하는 것이다. 
이것이 가능한 이유는 프로세스나 스레드 레지스터에 context를 저장할 수 있기 때문이다. 이 context switching에 의해 Dispatcher에 발생하게 되는 부담을 context switching overhead라고 한다. 

 

아래 깃허브 게시글을 학습한 내용입니다.

Interview_Question_for_Beginner/OS at main · JaeYeopHan/Interview_Question_for_Beginner (github.com)