CPU 스케줄링 개요
운영체제가 프로세스들에게 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 합니다. CPU 스케줄링은 컴퓨터 성능과도 직결되는 대단히 중요한 문제입니다. 이번장에서는 이런 프로세스들의 처리순서를 관리하는 CPU 스케줄링에 대해 알아보겠습니다.
프로세스 우선순위
cpu가 처리해야 할 프로세스들의 순서는 어떻게 정하는것이 좋을까요? 단순히 프로세스들을 차례대로 처리하면 될거라 생각이 들지만 좋은 방법은 아닙니다. 그 이유는 프로세스마다 우선순위가 다르기 때문입니다.
우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있습니다. 대부분의 프로세스들은 cpu와 입출력장치를 모두 사용하며 실행됩니다. 달리 말하면 프로세스는 실행 상태와 대기 상태를 반복하며 실행됩니다.
그런데 프로세스마다 입출력장치를 이용하는 시간과 cpu를 이용하는 시간에 차이가 있습니다. 비디오 재생이나 디스크 백업같이 입출력 작업이 많은 프로세스를 입출력 집중 프로세스라고 하고, 복잡한 수학연산이나 컴파일처리를 하는 프로세스를 cpu 집중 프로세스라고 합니다. 입출력 집중 프로세스는 실행 상태보다 대기 상태에 더 많이 머무르게 되고, 반대의 경우엔 실행 상태에 더 많이 머무르게 됩니다.
cpu 집중 프로세스와 입출력 집중 프로세스를 동시에 cpu 자원을 요구했다고 가정해 봅시다. 이런 경우 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 대기상태로 전환시키고, 그 다음 cpu 집중 프로세스를 실행 상태로 전환하는 것이 더 효율적입니다.
이처럼 cpu를 차례대로 사용하는 것보다 각각 상황에 맞게 cpu를 배분하는 것이 더 효율적입니다.
이처럼 프로세스의 중요도에 맞게 cpu를 운영할 수 있도록 운영체제는 프로세스에 우선순위를 부여합니다. 운영체제는 각 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정합니다.
스케줄링 큐
PCB에 우선순위가 적혀 있다고는 하지만, CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 PCB를 뒤적거리는 것은 비효율적입니다.
그래서 운영체제는 프로세스들에 '줄을 서서 기다릴 것'을 요구합니다. CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들을 줄세우는 것이죠. 그리고 운영체제는 이 줄을 스케줄링 큐로 구현합니다.
운영체제가 관리하는 대부분의 자원은 큐로 관리됩니다. 운영체제에는 다양한 큐가 존재하는데, 대표적으로 준비 큐와 대기 큐가 있습니다. 준비 큐는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미합니다.
준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다립니다. 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행합니다.
대기 상태에 있는 프로세스들은 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다립니다. 예를 들어 하드 디스크 사용을 요구한 프로세스는 하드 디스크 대기 큐에서 입출력 작업이 완료되기를 기다리고, 프린터 사용을 요구한 프로세스는 프린터 대기 큐에서 입출력 작업이 완료되기를 기다리는 것이지요.
선점형과 비선점형 스케줄링
만일 cpu에서 실행중인 프로세스가 있는데 갑자기 급한 프로세스가 cpu를 사용해야 할 경우 어떻게 될까요?
이 경우 지금 사용중인 프로세스를 중단시키고 급한 프로세스를 처리하거나, 현재 사용중인 프로세스가 끝날때까지 기다린 후 프로세스를 처리할 수 있습니다. 전자를 선점형 스케줄링이라 하고, 후자를 비선점형 스케줄링이라 합니다.
CPU 스케줄링 알고리즘
cpu 스케줄링 알고리즘의 종류는 다양합니다. 여기서 중요한건 스케줄링 알고리즘에 사용된 '아이디어'지 '용어'가 아님을 알아야 합니다. 그러므로 이번장에서 스케줄링 알고리즘의 작동 방식과 장단점을 이해하는데 집중하길 바랍니다.
스케줄링 알고리즘 종류
선입 선처리 스케줄링
선입 선처리 스케줄링은 FCFS 스케줄링이라고도 부릅니다. 이는 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식입니다. 선입 선처리 스케줄링은 가장 공정해 보이는 스케줄링이지만 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있는 부작용이 있는 스케줄링 입니다.
최단 작업 우선 스케줄링
프로세스들이 대기상태로 오래 있는 것을 호위 효과라고 합니다. 이런 호위 효과를 방지하려면 어떻게 해야 할까요? 단순히 생각해보면 사용 시간이 긴 프로세스를 나중에 실행하고, 짧은 프로세스를 먼저 실행하면 됩니다.
이렇게 실행시간이 짧은 프로세스부터 실행하는 방식을 최단 작업 우선 스케줄링 혹은 SJF 스케줄링 이라고 합니다.
라운드 로빈 스케줄링
라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식입니다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 시간을 정해놓은 것을 의미합니다. 즉, 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 cpu를 이용하는 선점형 스케줄링입니다.
라운드 로빈 스케줄링에서는 타임 슬라이스 크기가 매우 중요합니다. 타임 슬라이스가 매우 크면 호위 효과가 생길수 있고, 매우 작으면 문맥 교환에 발생하는 비용이 커집니다.
최소 잔여 시간 우선 스케줄링
최소 잔여 시간 우선 스케줄링 혹은 SRT 스케줄링은 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식입니다.
우선순위 스케줄링
우선순위 스케줄링은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 입니다.
우선순위 스케줄링은 근본적인 문제를 내포하고 있습니다. 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 계속 연기될 수 있습니다. 이를 기아 현상이라고 합니다.
이를 방지하기 위한 방법으론 에이징이 있습니다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식입니다.
다단계 큐 스케줄링
다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태로, 우선순위 별로 준비 큐를 여러 개 사용하는 방식입니다.
다단계 큐 스케쥴링에서 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리합니다.
이렇게 큐를 여러 개 두면 유형별로 우선순위를 구분하여 실행하는 것이 편리해집니다. 또한 큐 별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할수도 있습니다.
다단계 피드백 큐 스케줄링
다단계 큐 스케줄링의 발전된 형태입니다. 앞서 설명한 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없습니다. 그럼 앞에서 설명한 기아 현상이 발생할 수 있는데, 다단계 피드백 큐 스케줄링은 큐 사이를 프로세스들이 이동할 수 있도록 해서 이런 문제를 해결합니다.
