CPU 스케쥴링

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

프로세스 우선순위

CPU 할당을 기다리는 프로세스 순서대로 CPU를 사용하는 것은 합리적인 것처럼 보이지만, 합리적인 방법이 아니다. 프로세스마다 우선순위가 다르고, 우선순위가 높은 프로세스는 빠르게 처리해야 하는 프로세스를 의미한다. 우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스이다. 그리고 입출력 작업이 많은 프로세스를 먼저 실행시키는 것이 효율적인 이유는 아래 예시를 통해 알 수 있다. 

 

먼저, 일반적인 프로세스가 어떤 과정을 거치며 실행되는지를 봐야한다. 대부분의 프로세스들은 다음과 같이 CPU와 입출력장치를 모두 사용하며 실행된다. 

위의 그림과 같이 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다. 하지만 프로세스 종류마다 입출력장치를 이용하는시간과 CPU를 이용하는 시간의 양에는 차이가 있다. 

• 입출력 집중 프로세스 I/O bound process
  • 비디오 재생이나 디스크 백업 작업 등과 같이 입출력 작업이 많은 프로세스
  • 실행 상태보다는 입출력을 위한 대기 사태에 더 많이 머무르게 된다.
• CPU 집중 프로세스 CPU bound process
  • 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스 등과 같이 CPU 작업이 많은 프로세스
  • 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.

위와 같이 CPU 집중 프로세스는 CPU를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스이다. 따라서, CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이다. 동시에 작업을 요구하였을 떄, 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 합리적이다. 

이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 각각에 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.  그래서 운영체제는 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 프로세스마다 우선순위를 부여한다. 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.

프로세스 우선순위 예시

스케쥴링 큐

PCB에 프로세스 우선순위가 적혀 있지만, 운영체제가 매번 일일이 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거롭고 오랜 시간이 걸릴 수 있다. 

운영체제는 메모리에 적재되거나 생성하고 싶은 프로세스들을 큐에 삽입하여 줄을 세우고, 마찬가지로 CPU를 이용하고 싶은 프로세스들, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다. 그리고 이 줄을 스케쥴링 큐(scheduling queue)로 구현하고 관리한다.

운영체제가 관리하는 큐에는 다양한 종류가 있다. 그 중 대표적인 큐로 준비 큐(ready queue)와 대기 큐(waiting queue)가 있다. 

• 준비 큐
  • CPU가 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐
  • 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄 

준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다. 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 우선순위가 높은 프로세스를 먼저 실행한다.

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

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

• 선점형 스케쥴링(preemptive scheduling)
  • 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식을 의미한다. 
  • 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케쥴링 방식
  • 더 급한 프로세스가 언제든 끼어들어 사용할 수 있는 방식으로, 어느 한 프로세스의 독점을 막고 프로세스에 골고루 자원을 배분할 수 있다.
  • 문맥 교환과정에서 오버헤드가 발생할 수 있다.
• 비선점형 스케쥴링 (non-preemptive scheduling)
  • 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는스케쥴링 방식
  • 하나의 프로세스가 자원 사용을 독점할 수 있는 스케쥴링 방식이다. 
  • 문맥 교환에서 발생하는 오버헤드는 선점형 스케쥴링보다 적다.
  • 모든 프로세스가 골고루 자원을 사용할 수 없다.