[혼자 공부하는 컴퓨터 구조 + 운영체제] 11강 CPU 스케줄링

CPU 스케줄링 개요

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

프로세스 우선순위

준비 상태의 프로세스가 서로 CPU를 사용하고 싶어할 때 어떻게 배분해야 프로세스들이 공정하게 CPU를 사용할 수 있을까?

단순한 아이디어로는 요청한 순서대로 CPU를 이용하는 방법이 있을 것이다. 하지만 이는 좋은 방법이 아니다. 그 이유는 프로세스마다 우선순위가 다르기 때문이다. 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스를 의미한다. 우선순위가 높은 프로세스로는 대표적으로 입출력 작업이 많은 프로세스가 있다. 왜 그럴까?

이를 이해하기 위해서 프로세스가 어떤 과정을 거치며 실행되는지 알아보자. 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행된다. 달리 말하면 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다.

예를들어 워드 프로세서는 다음과 같은 과정을 꾸준히 반복한다.

CPU를 통한 명령어 실행 → 사용자에게 입력받은 내용을 보조기억장치에 저장 → CPU를 통한 명령어 실행 → 사용자에게 입력받은 내용을 화면에 출력 → …

프로세스의 종류마다 입출력 장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있으며, 이러한 프로세스를 구분할 수 있다.

• 입출력 집중 프로세스(I/O bound process)
  • 비디오 재생이나 디스크 백업을 담당하는 프로세스처럼 입출력 작업이 많은 프로세스가 여기에 속한다.
• CPU 집중 프로세스(CPU bound process)
  • 복잡한 수학 연산이나, 컴파일, 그래픽 처리 작업을 담당하는 프로세스처럼 CPU 작업이 많은 프로세스가 여기에 속한다.

입출력 집중 프로세스는 실행 상태보다 대기 상태에 더 많이 머무르며, CPU 집중 프로세스는 대기 상태보다 실행 상태에 더 많이 머무르게 된다.

CPU를 이용하는 작업을 CPU버스트라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트라고 부른다. 프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행된다.

입출력 집중 프로세스는 CPU를 짧게 사용하기 때문에, 입출력 집중 프로세스를 먼저 실행시켜서 입출력장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다.

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

스케줄링 큐

PCB에 우선순위가 적혀있다고 하지만, 운영체제가 매번 일일이 모든 PCB를 검색해서 먼저 자원을 사용할 프로세스를 결정하는 것은 많은 연산을 필요로 한다. 그래서 운영체제는 자원 할당을 원하는 프로세스에게 ‘줄을 서서 기다릴것’을 요구한다. CPU를 사용하고 싶은 프로세스, 메모리에 적재되고 싶은 프로세스, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄세운다. 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리한다.

큐는 선입선출 형태의 자료구조이지만, 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요가 없다.

즉, 운영체제는 자원을 원하는 프로세스를 큐에 삽입하여 줄세워 관리한다.

운영체제는 자원을 큐로 관리하며, 운영체제가 관리하는 큐에는 다양한 종류가 있다. 대표적으로 준비 큐와 대기큐가 있다.

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

프로세스가 준비 상태가 되면 준비 큐에 PCB가 삽입된다. 마찬가지로 대기 상태가 된다면, 대기 큐에 PCB가 삽입된다. 운영체제는 PCB가 큐에 삽입된 순서대로 프로세스를 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다. 다시말해 우선순위가 낮은 프로세스는 먼저 큐에 삽입되어도 우선순위가 높은 프로세스가 먼서 처리될 수 있다.

대기 상태인 프로세스의 PCB는 대기중인 입출력장치의 큐에 삽입된다. 이때 입출력장치로부터 완되었다는 인터럽트가 발생하면, 운영체제는 작업이 완료된 PCB를 찾아 준비 상태로 변경한 뒤에 준비 큐로 이동시킨다.

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

프로세스A가 CPU를 사용하고 있을 때 매우 급한 프로세스인 프로세스B가 CPU 이용을 원한다면 어떻게 처리해야할까? 프로세스A의 작업을 중단시키고 프로세스B를 동작시킬 수도 있고, 프로세스B를 기다리게 할 수도 있다. 이를 각각 선점형 스케줄링과 비선점 스케줄링이라고 한다.

• 선점형 스케줄링(preemptive scheduling)
  • 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식이다. 즉, 어느 프로세스가 자원을 독점할 수 없는 스케줄링 방식이다.
  • 지금까지 설명한 스케줄링은 선점형 스케줄링이다. CPU를 정해진 시간만큼 사용하다가 종료하는 방식은 선점형 스케줄링의 일종이다.
  • 프로세스가 골고루 자원을 할당받을 수 있다는 장점이 있지만, 문맥 교환 과정에서 오버헤드가 발생할 수 있다는 단점이 있다.
• 비선점형 스케줄링(non-preemptive scheduling)
  • 하나의 프로세스가 자원을 사용하고 있다면, 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식이다.
  • 문맥 교환의 횟수가 상대적으로 적기 때문에 오버헤드가 적다는 장점이 있지만, 모든 프로세스가 골고루 자우너을 사용할 수 없다는 단점이 있다.

CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링
  • 선입 선처리 스케줄링은 FCFS 스케줄링(First Come First Served Scheduling)이라고도 불리며, 단순히 큐에 삽입된 순서대로 프로세스를 처리하는 방식이다.
  • 가장 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다. 가령 CPU를 짧게 사용해도 되는 프로세스 앞에 오랜 시간동안 CPU를 사용해야하는 프로세스가 있다면, 긴 시간을 기다려야한다. 이런 현상을 호위효과(convoy effect)라고 한다.
• 최단 작업 우선 스케줄링
  • 최단 작업 우선 스케줄링은 SJF 스케줄링(Shortest Job First Scheduling)이라고 하며, 호위효과를 방지하기 위해 사용기간이 짧은 프로세스 순서로 실행하는 스케줄링이다. 이 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다. 선점형 최단 작업 우선 스케줄링이 뒤에 언급할 최소 잔여 시간 우선 스케줄링이다.
• 라운드 로빈 스케줄링
  • 라운드 로빈 스케줄링(round robin scheduling)은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉, 정해진 타임 슬라이스만큼의 시간만큼 돌아가며 CPU를 사용하는 선점형 스케줄링이다.
  • 타임 슬라이스 크기를 적절히 나누는 것이 중요하다. 너무 크다면, 호위효과가 생길 여지가 있고, 너무 짧다면 문맥 교환이 자주 발생하여 오버헤드가 발생한다.
• 최소 잔여 시간 우선 스케줄링
  • 최소 잔여 시간 우선 스케줄링 혹은 SRT(Shortest Remaining Time) 스케줄링은 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 방식이다. 즉, 작업 시간이 짧은 프로세스부터 처리하며, 정해진 타임 슬라이스만큼 돌아가며 동작한다. 타임 슬라이스만큼 처리하며, 잔여시간이 더 짧은 프로세스를 우선으로 선택한다.
• 우선순위 스케줄링
  • 우선순위 스케줄링(priority scheduling)은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순의를 가진 프로세스부터 실행하는 알고리즘이다. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링된다.
  • 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 알고리즘은 넓은 의미에서 우선순위 스케줄링의 일종으로 볼 수 있다. 다만, 우선순위 스케줄링은 근본적인 문제가 있는데, 바로 우선순위가 낮은 프로세스는 실행이 계속해서 연기될 수 있다는 것이다. 이를 기아(starvation)현상이라고 하며, 이를 막기 위한 기법으로 에이징(aging)이 있다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방법이다.
• 다단계 큐 스케줄링
  • 다단계 큐 스케줄링(multilevel queue scheduling)은 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면, 그 다음 우선순위 큐에 있는 프로세스들을 처리한다.
  • 큐를 여러개 두면 유형별로 우선순위를 구분하여 실행하는 것이 편리하다. 큐별로 타임 슬라이스를 여러 개 지정할 수 있으며, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.
• 다단계 피드백 큐 스케줄링
  • 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)은 다단계 큐 스케줄링의 발전된 형태이다. 다단계 큐 스케줄링에서는 프로세스가 큐 사이를 이동할 수 없다. 따라서 기아 현상이 발생할 여지가 있는데, 프로세스가 큐 사이를 이동할 수 있도록 하여 이런 문제를 보완했다.
  • 새로 준비상태가 된 프로세스는 우선순위가 가장 높은 큐에 삽입된다. 만약 프로세스가 해당 큐에서 실행이 끝나지 않으면, 우선순위가 낮은 큐로 점차 이동한다. 즉, CPU를 오랫동안 사용할수록 우선순위가 낮아진다. 반대로 큐에서 너무 오래 대기하는 프로세스가 있다면, 우선순위를 높여 기아 현상을 예방한다. 구현이 가장 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져있다.