운영체제(3) - CPU 스케줄링

 

CPU 스케줄링 개요

 

운영체제가 프로세스들에게 공정하고 합리적으로 CPU를 배분하는 것을 CPU 스케줄링이라 한다.

 

프로세스 우선순위

 

프로세스들에게 CPU를 배분하는 방법으로 단순하게 차례로 돌아가며 이용하게 하는 방법이 있다. 요청을 한 순서대로 CPU를 이용하게 하는 것이다. 이는 그다지 좋은 방법이 아닌데, 프로세스마다 우선순위가 다르기 때문이다.

 

대표적인 우선순위가 높은 프로세스는 입출력 작업이 많은 프로세스가 있다. 왜 우선순위가 높은지 알려면 프로세스가 어떤 과정을 거쳐 실행되는지 생각해 봐야 한다. 프로세스들은 CPU와 입출력 장치를 모두 사용하며 실행된다. 즉, 실행 상태와 대기 상태를 반복하며 실행되는 것이다.

 

비디오 재생, 디스크 백업과 같은 작업을 담당하는 프로세스를 입출력 집중 프로세스라 하고, 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스를 CPU 집중 프로세스라 한다. 입출력 집중 프로세스는 실행 상태보다 대기 상태에 더 많이 머무르게 되기에 CPU 집중 프로세스와 동일한 빈도로 CPU를 사용하는 것은 비합리적이다.

 

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

 

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

 

스케줄링 큐

 

PCB에 우선순위가 적혀있어도 운영체제가 이를 일일이 확인하는 것은 비효율적이다. CPU를 원하는 프로세스는 여러 개고 언제든 생길 수 있기 때문이다.

 

이는 CPU뿐이 아닌 메모리, 특정 입출력 장치와 보조기억장치에도 해당된다. 그렇기에 운영체제는 프로세스들이 줄을 서서 기다릴 것을 요구하는데 이 줄을 스케줄링 큐로 구현하고 관리한다.

* 큐는 선입선출 자료 구조지만, 스케줄링에서는 반드시 선입선출일 필요 없다.

 

운영체제는 자원을 이용하고 싶은 프로세스들을 큐에 삽입하여 줄을 세운다. 이러한 큐에는 대표적으로 준비 큐와 대기 큐가 있다. 준비 큐는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다.

 

준비 상태에 있는 프로세스들의 PCB는 큐에 삽입된 순서대로 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위가 낮은 프로세스가 먼저라 해도 우선순위가 높은 프로세스들이 먼저 처리될 수 있다.

 

대기 상태에 있는 프로세스도 마찬가지다. 입출력이 완료되어 완료 인터럽트를 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 삭제한다. 해당 PCB는 준비 큐로 이동한다.

 

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

 

선점형 스케줄링은 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미한다. 어느 하나의 프로세스도 자원 사용을 독점할 수 없는 방식이다.

 

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

 

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

선점형 스케줄링은 더 급한 프로세스가 언제든 끼어들 수 있어 자원 독점을 막고 골 구로 배분할 수 있다는 장점이 있지만 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

비선점형 스케줄링은 문맥 교환의 횟수가 더 적기 때문에 오버헤드는 적지만 하나의 프로세스가 자원을 독점하기에 당장 자원을 사용해야 하는 상황에서도 무작정 기다릴 수밖에 없다.

 

CPU 스케줄링 알고리즘

 

CPU 스케줄링 알고리즘의 종류

 

• 선입 선처리 스케줄링

선입 선처리 스케줄링(FCFS 스케줄링 : First Come First Served Scheduling)은 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다. 가장 공정해 보이지만 때론 프로세스들이 기다리는 시간이 길어질 수 있다는 부작용이 있다.

 

예를 들어 17ms 이용하는 A, 5ms 이용하는 B, 2ms 이용하는 C가 순서대로 들어갔을 때 C는 고작 2ms를 이용하기 위해 22ms를 기다리게 된다. 이런 현상을 호위 효과(convoy effect)라 한다.

 

• 최단 작업 우선 스케줄링

호위 효과를 방지하려면 CPU 사용 시간이 긴 프로세스를 나중에 실행하면 해결된다. 이렇게 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간이 짧은 프로세스부터 실행하는 것을 최단 작업 우선 스케줄링(SJF 스케줄링 : Shortest Jop First Scheduling)이라 한다. 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만 선점형으로도 구현할 수 있다. 선점형 최단 작업 우선 스케줄링을 최소 잔여 시간 우선 스케줄링이라 한다.

 

• 라운드 로빈 스케줄링

라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다. 정해진 시간을 모두 사용하였음에도 아직 완료되지 않았다면 다시 큐의 맨 뒤로 삽입되며 문맥 교환이 발생한다.

 

• 최소 잔여 시간 우선 스케줄링

최소 잔여 시간 우선 스케줄링(SRT 스케줄링 : Shortest Remaining Time Shceduling)은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 방식이다. 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

 

• 우선순위 스케줄링

우선순위 스케줄링은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위부터 실행하는 방식이다. 하지만 우선순위가 낮은 프로세스는 먼저 삽입되었음에도 계속해서 연기될 수 있다. 이를 기아 현상이라고 한다. 이를 방지하기 위한 방법으로 에이징이 있다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

 

• 다단계 큐 스케줄링

다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태이다. 우선순위별로 준비 큐를 여러 개 사용하는 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 그다음 우선순위 큐에 프로세스들을 처리한다. 이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. 또한 큐 별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.

 

• 다단계 피드백 큐 스케줄링

앞서 설명한 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없다. 그러나 이는 기아 현상으로 이어질 수 있는데 이를 보완한 것이 다단계 피드백 큐 스케줄링이다. 위와 비슷하게 작동하지만 한 가지 다른 것은 프로세스들이 큐 사이를 이동할 수 있다는 것이다. 프로세스가 우선순위가 높은 큐에 삽입되고 일정 시간 동안 실행된 후 해당 프로세스가 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되는 방식이다. 결국 자연스레 CPU를 오래 사용하는 프로세스는 우선순위가 낮아지고 입출력 집중 프로세스의 우선순위는 높아진다. 프로세스가 큐 사이를 이동할 수 있기에 낮은 우선순위에 너무 오래 머무르면 에이징 기법을 적용하여 기아 현상을 예방할 수 있다. 다단계 피드백 큐 스케줄링은 구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘이다.