[운영체제 기초] CPU 스케줄링

본 포스팅은 인프런의 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제를 참조하여 작성한 글입니다.

CPU 스케줄링 개요

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 한다. CPU 스케줄링은 컴퓨터 성능과도 직결되는 대단히 중요한 문제이다. 프로세스들에게 현명하게 CPU를 배분하지 못하면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있기 때문이다.

프로세스 우선순위

그러면 가장 공정한 CPU 스케줄링 방법은 무엇이 있을까? CPU를 사용하고 싶어하는 프로세스들이 차례대로 돌아가면서 하는 방법이 공정할까? 아니다! 빨리 처리해야 하는 프로세스가 있기 때문이다. 즉, 프로세스마다 우선순위가 다르기 때문에 들어온 순서대로 처리하는 것이 불공정할 수 있다.

보통은 입출력 작업이 많은 프로세스(= 입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스(= CPU 집중 프로세스)의 우선순위보다 높다. 왜 그럴까? CPU 집중 프로세스는 CPU를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스인데 CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것이 비합리적이다.

CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정해보자. 이러한 경우 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다. 입출력장치가 입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에 입출력 집중 프로세스를 얼른 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문이다. 이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

상황에 맞게, 그리고 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위를 부여한다. 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고 PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다. 그렇게 자연스럽게 우선순위가 높은 프로세스는 더 빨리 더 자주 실행된다.

스케줄링 큐

PCB에 우선순위가 적혀 있다고 하지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적이다. CPU를 원하는 프로세스들은 1~2개가 아니고 CPU를 요구하는 새로운 프로세스는 언제든 생길 수 있기 때문이다.

이는 비단 CPU 자원에만 국한된 상황이 아니다. 메모리에 적재되고 싶어하는 프로세스도 얼마든지 있을 수 있고 특정 입출력장치와 보조기억장치를 사용하길 원하는 프로세스도 여러개 있을 수 있기 때문이다. 운영체제가 매번 일일이 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거롭다.

그래서 운영체제는 프로세스들에게 줄을 서라고 명령한다. CPU를 사용하고 싶은 프로세스들, 메모리를 사용하고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세우는 것이다. 그리고 운영체제는 이 줄을 스케줄링 큐 로 구현하고 관리한다.

이렇게 운영체제가 관리하는 줄, 즉 스케줄링 큐에는 다양한 종류가 존재한다. 대표적인 큐로 준비 큐와 대기 큐가 있다. 준비 큐는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다. 또한 대기 큐에는 여러 종류의 큐들이 존재하는데 쉽게 생각해서 입출려장치 별로 큐가 존재한다고 보면 좋을 것 같다. 입출력장치 큐에서 작업이 완료되면 준비 큐로 보낸다.

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

운영체제가 CPU 자원이 제한적이니 스케줄링 큐를 활용하여 관리한다. 또한 스케줄링 종류에도 다양한 경우가 존재한다. 현재 CPU를 사용 중인 프로세스부터 CPU 자원을 빼앗아 다른 프로세스에게 할당하는 선점형 방식과 현재 CPU를 사용중인 프로세스의 작업이 끝날 때까지 프로세스를 기다리는 비선점형 방식이 존재한다. 선점형 스케줄링은 어느 한 프로세스의 자원독점을 막고 프로세스들에 골고루 자원을 분배한다. 대신 그 만큼 컨텍스트 스위칭 과정에서 오버헤드가 발생한다. 반면 비선점형 스케줄링은 선점형 스케줄링에 비해 컨텍스트 스위칭에서 발생하는 오버헤드가 적다. 대신 모든 프로세스가 골고루 자원 이용이 불가능하다.

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케줄링 알고리즘을 사용하고 있다. 이것은 전부 암기하는 것보다 알고리즘의 아이디어(작동 방식, 장단점)에 주목해서 학습하면 좋을 것 같다.

스케줄링 알고리즘의 종류

스케줄링 알고리즘의 종류는 매우 다양하다. 하나씩 알아보자.

선입 선처리 스케줄링(FCFS)는 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링이다. 먼저 CPU를 요청한 프로세스부터 CPU를 할당한다. 하지만 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 존재하는데 이런 부작용을 호위 효과 라고 한다.

최단 작업 우선 스케줄링(SJF)는 호위 효과를 방지하기 위해 나온 스케줄링으로 CPU 사용이 긴 프로세스는 나중에 실행하고 CPU 사용시간이 짧은 프로세스는 먼저 실행한다. 즉, CPU 사용 시간이 짧은 프로세스부터 처리하는 방식이다.

라운드 로빈 스케줄링(RR)은 FCFS에 타임 슬라이스를 넣은 스케줄링 기법이다.

타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 말한다.

라운드 로빈은 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다. 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼 이용을 한다. 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다.(컨텍스트 스위칭) 라운드 로빈 스케줄링에서 타임 슬라이스 크기는 매우 중요하다. 타임 슬라이스가 지나치게 크면 사실상 FCFS와 다를 바가 없어지며 타임 슬라이스가 지나치게 작으면 컨텍스트 스위칭에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는 데에 온 힘을 쓸 것이다.

최소 잔여시간 우선순위 스케줄링(SRT)은 SJF + RR을 합친 방식이다. SJF는 작업시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘이고 RR은 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘이다. 이 둘을 합친 SRT는 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업시간이 가장 적은 프로세스가 되는 방식이다.

우선순위 스케줄링은 프로세스들에 우선순위를 부여하고 우선순위 높은 프로세스부터 실행을 하는 방식이다. 우선순위가 같은 프로세스들 같은 경우 FCFS 방식으로 처리한다. SRT나 SJF도 크게 보면 해당 우선순위 스케줄링 방식에 속한다. 하지만 우선순위 스케줄링의 근본적인 문제로 기아 현상이 발생한다. 우선순위 높은 프로세스들만 쭉 실해하면 우선순위가 낮은 프로세스(준비 큐에 먼저 삽입이 되었음에도 불구하고)는 계속 실행이 연기된다. 이를 방지하기 위해 에이징 기법이 나왔다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로 대기중인 프로세스의 우선순위를 마치 나이를 먹듯이 점차 증가 시킨다. 이러면 우선순위가 낮아도 우선순위는 언젠가 높아질 것이다.

다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태이다. 우선순위 별로 준비 큐를 여러개 사용하는 스케줄링 방식으로 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리한다.

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태이다. 큐 간의 이동이 가능한 다단계 큐 스케줄링이다. 다단계 큐 스케줄링에서는 기본적으로 큐간의 이동이 불가능했다. 그래서 우선순위 낮은 프로세스는 계속해서 실행이 연기되고 기아현상이 발생했다. 하지만 다단계 피드백 큐 스케줄링을 이용하면 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아직 입출력 집중 프로세스의 우선순위는 상대적으로 높아진다. 즉, 다단계 큐 스케줄링에 에이징 기법을 이용한 방식이다. 다단계 피드백 큐는 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 걸리면 우선순위가 높아진다.