CPU 스케줄링이란?

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 한다. 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링CPU schedulling이라고 한다.

프로세스 우선순위

상황과 중요도에 따라 프로세스가 CPU를 이용할 수 있도록 운영체제는 프로세스마다 우선순위priority를 부여한다. 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.

운영체제가 자원 배문을 위해 일일히 모든 프로세스의 PCB를 검사하는 것은 비효율적이며 오랜 시간이 걸리는 일이다. 그래서 운영체제는 프로세스들을 스케줄링 큐scheduling queue로 구현하고 관리한다.

큐는 자료 구조 관점에서 봤을 때 먼저 삽입된 데이터가 먼저 나가는 선입선출 자료구조지만, 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없다.

선점형 스케줄링(preemptive scheduling)은 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼았아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 말한다.

비선점형 스케줄링(non-preemptive scheduling)은 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미한다.

대부분의 운영체재는 선점형 스케줄링 방식을 차용하고 있지만 각기 장단점을 가지고 있다.

선점형 스케줄링

비선점형 스케줄링

장점 : 문맥 교환의 횟수가 선점형보다 적기 때문에 오버헤드가 상대적으로 덜 일어난다.
단점 : 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에사도 무작정 기다려야 하므로 모든 프로세스가 골고루 자워늘 사용할 수 없다.

*프로세스 A(17ms 동안 CPU 이용), 프로세스B(5ms 동안 CPU 이용), 프로세스B(2ms 동안 CPU 이용) 차례로 준비 큐에 삽입된다면 프로세스 C는 2ms를 실행하기 위해 22ms(17ms + 5ms)라는 시간을 기다려야 한다(호위 효과).

큐에 삽입된 프로세스들은 삽입된 순서대로 정해진 시간만큼 CPU를 이용하고, 정해진 시간을 모두 사용하고도 프로세스가 완료되지 않으면 다시 큐의 맨 뒤에 삽입된다. 이 때 문맥 교환이 발생한다.

타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링과 같아 호위 효과가 생길 수 있고, 지나치게 작으면 문맥 교환에 발생하는 비용이 커질 수 있다.

프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 사진 프로세스부터 실행(우선순위가 같은 프로세스들은 선입 선처리로 스케줄링)
넓은 의미에서 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링은 우선순위 스케줄링의 일종
준비 큐에 먼저 삽입되었어도 우선순위가 높은 프로세스들에 의해 실행이 연기될 수 있다(기아starvation현상). 이를 방지하기 위해 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 에이징 기법이 있다.