6. 훑어보는 CPU 스케줄링

CPU 스케줄링

일반적으로 컴퓨터 시스템에서 프로세서(Processor)라 함은 주기억 장치에서 저장된 프로그램(기계 명령어) 읽어가면서 처리하는 CPU를 일컫는다.

운영체제의 프로세서 관리는 다수의 프로세스가 준비 상태에 있을 때, CPU가 어느 프로세스를 먼저 처리하도록 할 것인가를 결정하기 위한 제반 사항을 총칭하고, CPU 스케줄링(CPU Scheduling)이라 부르기도 한다.

1. 단계별 처리 스케줄링

컴퓨터는 여러 개의 프로세스가 동시에 존재하므로 각각의 프로세스를 식별하거나 관리하기 위해서는 아래와 같은 여러 가지 단계들이 필요하다.

1. 장기 스케줄링(Long-term Scheduling)

장기 스케줄링 단계에서는 어느 프로그램을 주기억 장치에 먼저 적재할 것인가를 결정한다. 현대 운영체제의 장기 스케줄링에서는 운영체제에 등록된 프로세스 수의 적정성 여부에 따라 프로그램의 적재를 허용하거나 거부한다. 이런 이유로 장기 스케줄링을 잡 스케줄링(Job Scheduling)이라고도 한다.

2. 중기 스케줄링(Midium-term Scheduling)

중기 스케줄링 단계에서는 컴퓨터 자원의 고갈 등의 이유로, 적재된 프로세스 중 일부에 대하여 상당 기간 동안 처리를 보류시켜야 할 때, 여러 가지 요인을 고려하여 보류 대상 프로세스(들)를 선정한다.

운영체제는 처리가 보류된 프로세스들을 처리 재개가 가능할 때까지 주기억장치에서 하드 디스크로 옮기는데, 이 과정을 스왑 아웃(Swap out)이라고 부르고, 반대를 스왑 인(Swap In)이라 한다.

3. 단기 스케줄링(Short-term Scheduling)

단기 스케줄링은 운영체제가 다수의 준비 상태 프로세스 중에서 CPU를 점프 시켜 실행시킬 프로세스를 선택하는 과정을 말한다. 보통 CPU 스케줄링이라고 하면 바로 이 단계를 말한다.

CPU 스케줄링은 그 전략에 따라 다르겠지만, 1초에 수십 ~ 수백 번 이루어질 수도 있다. CPU 스케줄러는 결국 프로세스들에 CPU를 배분하는 역할을 담당하므로 이를 디스패처(Dispatcher)라 부르기도 한다.

2. CPU 스케줄링 전략의 목표 및 기준

운영체제에서 구현되는 CPU 스케줄러의 기본 목표 중 하나는 사용자 프로세스들의 기다리는 시간을 줄여, 가능한 한 신속하게 처리될 수 있도록 하는 것이다.

이 외에도, 목표 설정의 기준은 크게 사용자 관점과 시스템 관점으로 분류할 수 있다.

• 사용자 관점에서의 CPU 스케줄링 목표 지표:
  • 응답 시간(Response Time): 사용자 데이터 입력 후, 출력이 이루어질 때까지의 소요 시간
  • 반환 시간(Turnaround Time): 프로그램 제출(혹은 시작) 후, 끝날 때까지 소요되는 총 시간
  • 대기 시간(Waiting Time): 프로세스들이 준비 상태로 대기열에서 기다린 시간의 총합
• 시스템 관점에서의 CPU 스케줄링 목표 지표:
  • CPU 이용률(CPU Utilization): 총 경과 시간 대비 CPU가 순수하게 사용자 프로세스를 수행한 시간의 비
  • 처리량(Throughput): 단위 시간당 처리된 프로세스의 개수

사용자 관점과 시스템 관점에서의 CPU 스케줄링 목표 지표들 사이에는 상호 배타적인 관계가 존재한다. 예를 들어, 사용자에게 짧은 응답 시간을 제공하기 위해서는 시간을 작게 나누어서 프로세스들에게 CPU를 가급적 자주 골고루 할당해주어야 하는데, 이럴 경우 운영체제의 스케줄링이 빈번하게 실행하게 되어 결국은 CPU 이용률과 처리율이 낮아진다.

따라서 CPU 스케줄링에는 다양한 주변 여건을 고려하여 적절한 전략이 적용되어야 한다.

3. CPU 스케줄링이 이루어지는 시기

- 프로세스가 입/출력을 요구할 때

CPU가 할당되어 실행 중인 주기를 CPU 버스트(CPU Burst), 입/출력이 이루어지는 주기를 I/O 버스트(I/O Burst)라 부른다. 예를 들어 accept(), connect(), send(), recv(), open(), close(), fgets(), printf() 등은 모두 운영체제의 입/출력 시스템 콜이어서, 입/출력이 완료될 때까지 그 프로세스는 CPU 할당을 받지 못하는 I/O 버스트고, 그 외 부분은 CPU 버스트다.

I/O 버스트가 시작되면 운영체제는 CPU를 다른 프로세스에게 할당해주어야 하는데, 이 경우가 가장 대표적인 CPU 스케줄링 시기다.

- 프로세스가 종료를 요구할 때

사용자가 작성한 프로그램을 컴파일하고 링크하면 목적 코드(실행 파일)에는 프로그램의 끝부분에 운영체제에게 종료를 요구하는 코드가 자동으로 링크된다.

_start() {
  r = main(...);
  exit(r); // 종료 시스템 콜
}

이처럼 프로세스가 종료를 요구하면 운영체제는 CPU를 보내줄 새로운 프로세스를 찾기 위해 CPU 스케줄링이 일어난다.

- 높은 우선순위의 프로세스가 나타났을 때

입/출력 상태에 있던 프로세스는 입/출력이 완료되면 준비 상태가 되어 CPU 할당 대상에 새롭게 추가된다. 즉, 입/출력 완료 인터럽트가 발생하면 CPU는 실행 중이던 프로세스에서 잠시 떠나 운영체제의 인터럽트 핸들러로 이동하여 준비 상태의 새로운 프로세스가 나타났음을 인식하고, 만약 이 새로운 프로세스의 우선순위가 이전에 떠나왔던 프로세스보다 높다면 CPU 스케줄링 방법에 따라 CPU 할당을 즉시 교체할 수 있다.

- 주어진 CPU 실행 시간을 초과했을 때

대부분의 사용자 프로그램은 CPU 버스트와 I/O 버스터가 번갈아 섞여 있어서, 다수의 프로세스 사이에서 CPU가 자연스럽게 고루 할당된다.

그러나 어떤 프로그램은 입/출력이 극히 적고 계산식으로만 이루어져 있어서 CPU의 고른 분배가 어려워질 수 있다. 이를 해결하기 위해 어느 한 프로세스가 연속해서 사용할 수 있는 최대 시간을 설정하고, 시간이 초과한 경우 CPU를 다른 프로세스에게 할당할 수 있다.

이때 지정된 최대 시간을 타임 퀸텀(Time Quantum) 또는 타임 슬라이스(Time Slice)라 부른다.

4. CPU 스케줄링 전략의 분류

• 프로세스 스스로의 요구에 의해 이루어지는 자율적 CPU 반납: 입/출력, 종료

• 외부 상황에 따라 CPU를 강제로 회수당하는 타율적 CPU 반납: 높은 우선순위 출현, 타임 퀀텀 초과

CPU 반납 방식의 자율성 및 타율성 여부에 따라 CPU 스케줄링 전략은 크게 비선점형과 선점형으로 분류된다.

- 비선점(Non-preemption)형

비선점형 CPU 스케줄링은 실행 중인 프로세스가 자율적으로 CPU를 반납할 때까지 CPU를 계속 점유하여 실행하는 운영체제 환경이다.

입/출력이 적은 계산 위주(CPU Bounds) 프로세스가 다수 적재되어 있다면 다른 프로세스들의 응답 시간은 매우 저조할 것이다. 반대로 프로세스들이 입/출력 위주(I/O Bounds)라면 CPU를 어느 정도 규칙적으로 번갈아 할당받을 수 있으므로 응답 시간이 크게 나쁘지 않을 것이다.

- 선점(Preemption)형

자율적 CPU 반납은 물론 타율적 CPU 반납까지 이루어지는 운영체제 환경이다.

선형 운영체제 환경에서는 어떤 프로세스도 일정 시간(타임 퀀텀) 이상 동안 연속해서 CPU를 점유할 수 없으므로 계산 위주 프로세스가 많이 적재되어 있다 하더라도, 모든 프로세스의 반응 시간 성능을 평균 이상으로 유지할 수 있다.

5. CPU 스케줄링 전략들

1. 선입 선처리(FCFS: First-Come First-Served) 스케줄링

가장 간단하면서도 알기 쉽다. 프로세스들이 준비 대기열에 도착하는 순서에 따라 CPU를 할당하는 방법이다.

| 프로세스 | CPU 버스트 시간 | | -------- | --------------- | | P1 | 30 | | P2 | 3 | | P3 | 6 |

P1 -> P2 -> P3:
평균 대기 시간 = (0 + 30 + 33) / 3 = 21
평균 응답 시간 = (30 + 33 + 39) / 3 = 34

FCFS 전략에서 CPU 버스트가 긴 계산 위주 프로세스가 먼저 도착했다면, 이후의 CPU 버스트가 짧은 입/출력 위주 프로세스들은 간발의 차로 늦게 도착했다는 이유로 억울하게 그만큼 많이 기다려야 한다. 이럴 경우 입/출력 장치에 대한 활용도는 물론, 준비 대기열이 대부분 입/출력 위주 프로세스들로 구성된다면 CPU 이용률도 저하될 수 있다.

위와 같은 현상을 호위 효과(Convoy Effect)라 부르며, 근본적으로 FCFS가 비선점형 CPU 스케줄링이기 때문에 일어난다.

2. 최단 작업 우선(SJF: Shortest Job First) 스케줄링

CPU 버스트가 가장 짧은 프로세스를 CPU에 먼저 할당하는 전략이다.

P2 -> P3 -> P1:
평균 대기 시간 = (0 + 3 + 9) / 3 = 4
평균 응답 시간 = (3 + 9 + 39) / 3 = 17

평균 대기 시간과 평균 응답 시간이 FCFS에 비해 개선되었으나, SJF는 비선점형이므로 계산 위주의 긴 프로세스에 CPU가 할당된 상태에서 다수의 입/출력 위주 짧은 프로세스들이 도착한다면 마찬가지로 호위 효과가 일어날 수 있다.

또한, 짧은 프로세스들이 지속적으로 도착한다면, 상대적으로 긴 프로세스는 계속해서 지연되는 단점이 있다. 이처럼 계속해서 지연되는 상황을 보통 기아 상태(Starvation State)라고 부른다.

3. 최단 잔여 시간 우선(SRTF: Shortesst Remaining Time First) 스케줄링

비선점형인 SJF 스케줄링인 단점을 보완하기 위해서 준비 대기열에 새로운 프로세스가 도착하면, 현재 진행 중인 프로세스의 잔여 실행 시간과 새로운 프로세스의 CPU 버스트 시간을 비교하여 새 프로세스의 실행 시간이 더 짧으면 CPU를 강제 회수하여 새로운 프로세스에 할당하는 선점형 스케줄링 전략이다.

| 프로세스 | 도착 시간 | CPU 버스트 시간 | | -------- | --------- | --------------- | | P1 | 0 | 30 | | P2 | 1 | 15 | | P3 | 2 | 10 |

P1 -> P3 -> P2:
SJF 평균 대기 시간 = (0 + 39 + 28) / 3 = 22.3

P1 -> P2 -> P3 -> P2 -> P1
SRTF 평균 대기 시간 = (25 + 10 + 0) / 3 = 11.7

SRTF는 평균 대기 시간과 평균 응답 시간을 더욱 개선하면서 CPU나 입/출력 장치의 이용률 저하 현상 발생을 억제할 수 있으나, 기아 상태 발생 가능성이 더 커질 수 있다.

4. 최고 응답률 우선(HRRF: Highest Response Ratio First) 스케줄링

각 프로세스의 응답률을 계산하여 응답률이 가장 큰 프로세스를 먼저 처리하는 스케줄링 전략이다.

응답률 = (준비 큐 대기 시간 + CPU 버스트 시간) / (CPU 버스트 시간) = 1 + ((준비 큐 대기 시간) / (CPU 버스트 시간))

위 식은 CPU 버스트 시간에 대한 준비 대기열 대기 시간이 상대적으로 클수록 응답률이 높아져 CPU 스케줄링 우선순위가 높아진다. 만약 대기 시간이 같다면 CPU 버스트 시간이 짧을수록 응답률이 높아져 SJF나 SRTF와 같다. CPU 버스트 시간이 아무리 크더라도 언젠가는 준비 대기열 시간도 커질 것이므로 무한정 지연되는 기아 현상이 예방된다.

HRRF 스케줄링은 선점형이나 비선점형 중 어느 형태로도 운영이 가능한데, 선점형으로 구현할 경우 새로운 프로세스가 준비 큐에 도착하면 현재 실행 중인 프로세스와 새 프로세스의 응답률 계산 결과를 활용하면 된다.

5. 라운드 로빈(RR: Round Robin) 스케줄링

RR은 전형적인 선점형 스케줄링 전략으로, 모든 프로세스에 동일한 최대 CPU 점유 시간(타임 퀀텀)을 설정하고, 처리 중인 프로세스의 CPU 실행 시간이 타임 퀀텀을 초과하면 CPU를 강제로 회수하여 다음 프로세스에 할당하는 방식이다. 이렇게 하여 모든 프로세스들에게 CPU가 할당될 기회가 동일하게 주어지므로 대화식 시스템 환경에 적합하다.

RR 스케줄링 전략에서는 적절한 타임 퀀텀 설정이 매우 중요하다. 만약 타임 퀀텀이 아주 작다면 CPU 할당이 교체될 때마다 일어나는 컨텍스트 스위칭 횟수가 증가하여 시스템 부담을 증가시키므로 전체적인 처리율이 감소한다. 반대로 아주 크게 설정한다면 RR은 FCFS 스케줄링 전략과 거의 유사한 방식으로 후퇴할 것이다.

6. 다단계 큐(MQ: Multi-level Queue) 스케줄링

RR의 단점은 최적의 타임 퀀텀 찾기와 설정된 타임 퀀텀으로 인해 프로세스 특성을 고려할 수 없다는 것이다. 이를 해결하기 위한 방안으로 프로세스 특성별로 준비 큐를 여러 개 두어 우선순위를 부여하고, 높은 우선순위 큐들이 모두 비었을 때만 다음 단계의 낮은 우선순위의 큐 프로세스들에게 CPU를 할당하는 MQ 스케줄링 전략을 도입했다.

• 시스템 프로세스 준비 큐 (우선순위 가장 높음)
• 대화형(입/출력 위주) 프로세스 준비 큐
• 계산 위주 프로세스 준비 큐
• 후면처리 프로세스 준비 큐 (우선순위 가장 낮음)

각 준비 큐에는 해당 프로세스의 특성을 반영하는 타임 퀀텀을 설정한다. 예를 들어 대화형 프로세스들은 CPU 버스트 시간이 짧으므로 긴 타임 퀀텀이 필요 없고, 계산 위주 프로세스들은 타임 퀀텀이 길면 콘텍스트 스위칭 빈도가 줄어 시스템 부담을 줄일 수 있다. 또한, 같은 준비 큐 프로세스들 간에는 FCFS, SJF, RR 등 다른 스케줄링 전략등을 적용할 수 있다.

7. 다단계 피드백 큐(MFQ: Multi-level Feedback Queue) 스케줄링

응용 프로그램은 대부분 계산 위주 단계와 입/출력 위주 단계를 반복하므로 프로세스 진행 과정에서 그 특성이 변하면 이를 인지하여 해당 프로세스를 적절한 준비 큐로 이동시켜주는 전략이 MFQ 스케줄링이다.

• 실행 중인 프로세스가 해당 큐의 타임 퀀텀을 소진하지 못하고 입출력 등으로 CPU를 자진 반납하면, 이 프로세스는 입/출력 성향이 강해진 것으로 인식하여 입/출력 쪽으로 한 단계 높은 준비 큐로 이동시킨다.
• 반대로, 실행 중인 프로세스가 주어진 타임 퀀텀을 모두 소진한 후 CPU를 강제로 회수당하면, 이 프로세스는 계산 성향이 강해진 것으로 인식하여 이 프로세스를 입/출력 성향 기준 한 단계 낮은 준비 큐로 이동시킨다.

---