[운영체제 3] CPU 스케줄링(CPU Scheduling)

2024-04-03 3 분 소요

누구부터 CPU를 쓰게할 것인가

앞선 포스팅에서 각 프로세스는 준비(ready) 상태에 놓여있다가 CPU의 허가를 받아 디스패치(dispatch)되어 실행(running) 상태로 넘어간다는 것을 보았다. 그런데 어느 프로세스든 먼저 CPU를 사용하고 싶어할 것이다.

따라서 각 프로세스들에게 합리적으로 CPU 자원을 배분해야할 필요가 있는데, 이 과정을 CPU 스케줄링이라고 부른다.

단순무식하게 먼저 손 든 프로세스부터 선착순으로 CPU를 할당해도 되겠지만, 모든 일에는 우선순위(priority)가 있는 법. 선택과 집중이 필요하다. 보통 입출력 작업이 많은 프로세스를 우선순위가 높게 책정한다.

한 작업을 실행하는 데 걸리는 시간을 버스트(burst: 한차례, 한바탕)라 부르는데, 보통 CPU 버스트(CPU burst)보다는 입출력 버스트(I/O burst)가 더 크기 때문이다. CPU 버스트가 더 많은 프로세스를 CPU 집중 프로세스(CPU bound process), 입출력 버스트가 더 많은 프로세스를 입출력 집중 프로세스(I/O bound process)라 한다.

이 입출력 집중 프로세스는 실행 상태보단 입출력을 위한 대기 상태에 더 많이 머무르기에, CPU를 사용하는 시간이 적어 얼른 먼저 처리해버리자는 아이디어. 쇠뿔도 단 김에 빼자?

우선순위는 입출력 집중 프로세스 외에도 실시간 프로세스, 일부 백그라운드 프로세스 등이 높다.

스케줄링 큐(Scheduling Queue)

이렇게 프로세스를 줄을 세우는 개념을 ‘스케줄링 큐(scheduling queue)’라고 부른다. 자료구조의 큐(Queue)와는 관계 없는(항상 선입선출인 것은 아니기 때문) 개념이다.

OS는 이 스케줄링 큐를 여러개로 나누어 자원을 할당하는데, CPU를 이용하려는 프로세스들은 준비 큐(ready queue)에, 입출력 장치를 이용하려는 프로세스들은 대기 큐(waiting queue)에 삽입된다.

큐인 만큼 순서대로 프로세스를 하나씩 꺼내어 실행하지만, 우선순위가 높은 프로세스를 먼저 실행한다는 원칙도 갖고 있다. 자세한 운영 방식은 후술.

준비 큐에서 CPU를 할당받은 프로세스는 해당 PCB(프로세스 제어 블록)에서 프로세스 상태가 변경되고, 큐에서 제거(dequeue)된다.

만약 입출력 요청을 받았다면 해당 프로세스는 준비 큐를 떠나 다시 대기 큐에 삽입(enqueue)되어 대기 상태에 있다가 입출력 장치를 사용할 수 있게 되는 것이다.

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

자 우선순위도 있고 선착순도 있고 뭐 다 좋다. 그런데 이번엔 화장실이 급한 녀석이 등장했다. 누가 먼저 화장실을 써야할까?

규정대로 먼저 온 사람부터 화장실을 쓸 수도 있고, 불쌍하니 이번 한 번만 앞으로 양보해줄 수도 있다.

후자처럼 앞서 CPU 자원을 사용 중인 프로세스가 있더라도, OS가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링을 선점형 스케줄링(preemptive scheduling)이라 하고, 전자처럼 앞의 프로세스가 자원을 사용하고 있다면 종료(terminated)되거나 대기(waiting)상태로 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링을 비선점형 스케줄링(non-preemptive scheduling)이라고 한다.

대부분의 OS는 선점형 스케줄링 방식을 채택했지만 각자 일장일단이 있다. 선점형은 각 프로세스의 자원 독점을 막고 골고루 배분할 수 있지만, 문맥 교환 과정이 잦아 오버헤드가 발생할 수 있다.

반면 비선점형은 오버헤드는 덜 발생하지만, 하나의 프로세스가 너무 길게 사용하면 뒤 프로세스들은 무작정 기다려야 한다는 단점이 존재한다.

CPU 스케줄링 알고리즘

그래서 결론이 뭐냐? 어떻게 CPU 스케줄링을 해야하냐?에 대한 모범 답안은 없다. 각 OS별로 다른 방식을 채택하고 있기 때문.

일단 여러 종류부터 맛을 보고 결정을 내려보자.

알고리즘	설명	추가 내용
선입 선처리 스케줄링 (FCFS Scheduling; First Come First Served)	큐에 삽입된 순서대로만 프로세스를 처리하는 방식. CPU를 너무 오래 사용하는 프로세스가 먼저 도착하면, 다른 프로세스는 무기한 기다리게 되는 부작용(호위 효과; convoy effect) 발생	비선점형
최단 작업 우선 스케줄링 (SJF Scheduling; Shortest Job First)	CPU 이용 시간의 길이가 가장 짧은 프로세스부터 우선 실행하는 방식. 평균 대기 시간이 획기적으로 짧아진다	기본적으로 비선점형. 선점형일 경우 SRT 스케줄링이 됨
라운드 로빈 스케줄링 (RR Scheduling; Round Robin)	FCFS에 각 프로세스별로 정해진 시간(타임 슬라이스)을 두어, 정해진 시간안에 처리가 안 될 경우 큐에서 삭제되어 다시 큐의 맨 뒤에 삽입됨	선점형. 원형 큐로 구현. 타임 슬라이스의 크기가 매우 중요
최소 잔여 시간 우선 스케줄링 (SRT Scheduling; Shortest Remaining Time)	선점형 SJF. 매 시각마다 잔여 작업 시간이 가장 적은 프로세스를 선점해서 우선 실행	책에는 SJF+RR이라고 소개하며 타임 슬라이스가 있다고 하는데, 블로그들에서는 타임 슬라이스가 없다고 설명한다. 뭐가 맞는거야?
우선순위 스케줄링 (Priority Scheduling)	우선순위가 높은 것부터 실행하는 알고리즘. 우선순위가 낮은 프로세스들은 실행이 계속해서 연기될 수 있는데(기아 현상; Starvation), 솔루션으로는 오래 대기한 프로세스의 우선순위를 점차 높이는 에이징(aging) 기법이 있다.	SJF, SRT도 광의의 우선순위 스케줄링이다.
다단계 큐 스케줄링 (MQ Scheduling; Multilevel Queue)	큐를 여러 개로 만들어 큐 자체에도 우선순위를 부여하는 방식	큐별로 타임 슬라이스를 여러 개 지정할 수도, 큐마다 다른 스케줄링을 사용할 수도 있음
다단계 피드백 큐 스케줄링 (MFQ Scheduling; Multilevel Feedback Queue)	MQ에서 각 프로세스는 큐 사이를 오갈 수 없어, 또 다시 기아 현상이 발생한다. 해결책으로 타임 슬라이스 내에 완료가 안 된 프로세스는 우선순위를 낮추고, 오래 낮은 큐에 머무른 프로세스는 우선순위를 높이는(=aging) 방식을 적용한다.	구현이 복잡하지만, 가장 범용적인 CPU 스케줄링 알고리즘이다!