CPU 스케줄링

CPU 스케줄링이란 운영체제가 프로세스들에게 CPU 자원을 분배하는 것을 말한다.

CPU 스케줄링이 필요한 이유

각 프로세스 별로 입출력장치를 이용하는 시간과 CPU를 이용하는 시간에 차이가 있다.
입출력이나 디스크 백업을 자주 이용하는 프로세스(입출력 집중 프로세스) vs 복잡한 수학 연산, 그래픽 처리 작업 등을 자주 이용하는 프로세스(CPU 집중 프로세스)
위 예시에서 전자는 입출력을 위한 대기 상태에 더 많이 머무르게 되고, 후자는 실행 상태에 더 많이 머무르게 되는데, 이처럼 각 프로세스 별로 CPU사용에 대한 우선순위가 다르다.
위처럼 간단한 예시의 두 가지 프로세스가 동일하게 CPU를 할당 받는 것은 비합리적이기 때문에 CPU 스케줄링이 필요하다.

스케줄링 큐

운영체제는 프로세스들을 줄 세워 기다리게 한다. 이를 스케줄링 큐라고 한다.
이전에 포스팅 했던 프로세스 상태에 아래처럼 큐가 추가 된다.

준비 큐

- CPU를 이용하려는 프로세스가 서는 줄

대기 큐

- 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

 

그럼 큐는 선입선출이니 먼저 들어온 프로세스가 먼저 실행되나?

-> NO! 우선순위에 따라 먼저 처리될 수 있음(큐라고 이름지었지만 무조건 선입선출은 아님)

선점형 vs 비선점형 스케줄링

스케줄링은 크게 두 가지로 나뉘는데,
선점형 스케줄링은 한 프로세스가 사용하고 있는 자원을 운영체제가 강제로 뺏어 다른 프로세스에게 할당 가능한 방법이고,
비선점형 스케줄링은 한 프로세스가 자원을 사용 중이면, 스스로 해당 자원을 반납하기 전까지는 다른 프로세스가 자원을 넘겨받을 수 없는 방식이다.

---

CPU 스케줄링 알고리즘

선입 선처리 스케줄링(FCFS 스케줄링)

비선점형 스케줄링 방식으로, 말 그대로 먼저 들어온 프로세스부터 작업을 완료하고 다음 프로세스로 넘기는 방식

-> CPU를 오래 사용하는 프로세스가 먼저 들어오면, 다른 프로세스는 한참 기다려야 함(호위 효과).

최단 작업 우선 스케줄링(SJF 스케줄링)

CPU 사용 시간이 짧은 프로세스를 우선적으로 실행하는 방식

라운드 로빈 스케줄링

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식으로, 먼저 들어온 프로세스를 먼저 실행한, 정해진 시간 만큼 돌아가서 이용하도록 하는 선점형 스케줄링 방식이다.

우선순위 스케줄링

프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위 프로세스부터 실행(같은 우선순위일 경우 선입 선처리)

-> 기아현상이 발생할 수 있음(우선 순위가 낮은 프로세스가 계속해서 뒤로 밀려 실행되지 못하는 현상)

-> 에이징 기법으로 해결 가능(대기하고 있는 프로세스를 나이 먹듯이 점차 높이는 방식)

---

다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 방식이다.

위 그림처럼 큐를 여러 개두어 우선순위 별로 프로세스를 관리 및 실행하는 것이 편리해진다.

우선순위가 높은 큐에 프로세스를 먼저 실행하고 해당 큐가 비면 다음 우선순위의 큐를 실행하게 된다.

-> 이렇게 큐를 구분해놓으면, 큐마다 다른 스케줄링 알고리즘을 사용하거나 타임 슬라이스를 다르게 적용할 수도 있다.

하지만, 프로세스가 큐 사이를 이동할 수 없어서 기아 현상이 다시 발생할 수 있다. 이를 보완한 것이 밑의 알고리즘이다.

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링의 발전된 형태로, 위의 다단계 큐 스케줄링과 비슷하지만, 프로세스가 큐 사이를 이동할 수 있다.
구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘이다.

가장 높은 우선순위 큐의 프로세스가 CPU를 점유 후 정해진 타임 슬라이스만큼 실행-> 타임 슬라이스 안에 작업이 완료되지 않음-> 우선순위가 한단계 낮은 큐에 삽입

즉, CPU를 오래 사용해야 하는 CPU 집중 프로세스는 자연스럽게 우선순위가 낮아짐

+ 에이징 기법을 이용해 낮은 우선순위의 프로세스는 자연스레 우선순위가 높아짐