개념

스케줄링은 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정이다. 프로세서의 효율성을 높이고 시스템의 작업 처리 능력을 향상시키며, 작업의 응답 시간을 최소화하는 것이 목적이다.

다중 프로그래밍

다중 프로그래밍은 운영체제에서 가장 중요한 개념으로, 여러 작업을 동시에 처리한다. 여러 프로그램을 메인 메모리에 적재하고 프로세서를 분할해 시스템 효율성을 높이며, 이를 통해 프로세서 이용률과 처리율을 함께 끌어올릴 수 있다.

실행 과정

프로세스 A와 B가 각각 1초씩 실행하고 1초씩 기다리는 과정을 60회 반복한다고 하자. A를 모두 처리한 뒤 B를 처리하면 작업 전체에 4분이 걸린다. 이 중 컴퓨터가 실제로 작업을 처리하는 시간은 2분이고, 나머지 2분은 쉬는 시간이다. 반면 A를 먼저 실행하고 1초 뒤에 B를 실행하는 식으로 겹쳐서 처리하면, 쉬는 시간을 줄여 전체 작업 시간을 단축할 수 있다.

기본 요소

프로세스의 실행은 실행(프로세서 버스트)과 입출력 대기가 반복되는 순환으로 이루어진다. 컴퓨터 시스템에서 발생하는 다양한 프로세스는 스케줄링이 필요한 것과 그렇지 않은 것으로 나뉜다. 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 같은 사전 처리는 스케줄링 없이 실행되고, 사용자 프로세스와 시스템 프로세스는 스케줄링이 필요하다.

다중 작업(Multi Tasking)

다중 작업은 다중 프로그래밍 여부와 상관없이 여러 프로세스가 동시에 실행되는 것을 말한다. 스풀링 같은 시스템 프로세스 덕분에, 단일 사용자 시스템에서도 여러 프로세스가 동시에 실행될 수 있다.

프로세스 버스트

프로세서 버스트의 지속 시간을 측정하면, 전체 발생 시간이 빈도 곡선으로 나타난다.

스케줄링의 세 단계

프로세스들을 언제, 어느 프로세서에 할당할지는 세 단계를 거쳐 결정된다.

  1. 작업 스케줄링(작업 선택): 승인 스케줄링이라고도 하며, 시스템 자원을 실제로 사용할 작업을 결정하는 단계다. 수행 빈도가 낮아 장기 스케줄링이라 부르며, 새로운 프로세스가 생성되어 작업 스케줄링이 수행되면 작업은 여러 프로세스로 나뉜다.
  2. 작업 승인과 프로세서 할당: 어느 프로세스에 프로세서 사용 권한을 줄지, 시스템 부하가 바뀜에 따라 어느 프로세스를 잠정적으로 연기할지를 결정한다. 작업 승인과 프로세서 배당 사이에서 완충 역할을 하며, 수행 빈도로 보면 중기 스케줄링에 해당해 교체 가능성의 일부로 이해할 수 있다.
  3. 준비 상태 프로세서에 프로세스 할당(디스패치): 디스패치를 통해 준비 상태에 있는 프로세스 중 어느 것에 프로세서를 할당할지 결정한다.

성능 평가 기준

스케줄링의 성능은 다섯 가지 기준으로 평가한다. 사용률은 프로세서를 항상 실행 상태로 유지해 유휴 상태가 되지 않도록 하는 정도이고, **처리율(Throughput)**은 단위 시간당 시스템이 처리하는 작업량으로 높을수록 더 많은 작업을 빠르게 처리한다는 뜻이다. 반환 시간은 작업이 시스템에 맡겨져 메인 메모리에 들어가기까지, 즉 준비 큐에 머무는 시간을 말하고, 대기 시간은 작업의 실행 시간이나 입출력 시간에는 영향을 주지 못하므로 준비 큐에서 기다리는 시간을 최소화하도록 사용자 수를 제한해 관리한다. 반응 시간은 요청한 시점부터 반응이 시작되는 시점까지의 간격으로, 대화형 시스템에서 특히 중요해 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업의 요구가 없을 때 처리한다.

스케줄링 알고리즘

대부분의 스케줄링 알고리즘은 대화식 사용자 환경과 빠른 응답 시간을 구현하는 데 초점을 맞춰 발전했다. 프로세스 스케줄러는 이 알고리즘에 따라 프로세서를 할당해 작업을 완료한다. 여기서는 단일 프로세서로 구성된 시스템의 대표적인 스케줄링 알고리즘을 살펴본다.

선점 스케줄링

선점 스케줄링은 현재 실행 중인 프로세스를 인터럽트하거나 준비 상태로 되돌릴 수 있는 방식으로, 하나의 프로세스가 프로세서를 오래 독점하는 것을 막고 우선순위가 높은 프로세스가 긴급히 처리를 요청할 때 유용하다. 다만 효과적으로 선점하려면 메인 메모리에 많은 프로세스가 저장되어 있어야 해 오버헤드가 크고, 설계할 때 우선순위 개념을 반드시 고려해 의미 있게 배당해야 한다.

비선점 스케줄링

비선점 스케줄링은 한 프로세스가 자원을 선택하면 다른 프로세스에 할당된 자원을 빼앗을 수 없는 방식이다. 모든 프로세스를 공정하게 관리하지만, 그 때문에 실행 시간이 짧은 작업들이 오래 기다리게 되는 경우도 있다. 대신 우선순위가 높은 작업이 중간에 들어와도 대기 중인 작업들은 영향을 받지 않으므로 응답 시간을 예측하기 쉽다.

FCFS(First-Come, First-Served) 스케줄링

FCFS는 프로세스들이 도착한 순서대로 CPU를 할당받는 비선점형 스케줄링이다. 먼저 도착한 프로세스가 끝날 때까지 다음 프로세스는 대기하며, FIFO(First-In, First-Out) 큐로 구현한다. 일괄 처리 시스템에서는 효율적이지만, 대화식 시스템에서 요구하는 빠른 응답에는 적합하지 않다. 새로운 작업이 들어오면 프로세서의 PCB를 준비 큐 맨 끝에 연결하고, 차례가 되면 준비 큐 맨 앞의 프로세스가 프로세서를 할당받고 큐에서 빠진다. 평균 대기 시간이 길어지는 콘보이 효과(Convoy Effect) 때문에 성능이 좋지 않은 경우가 많다.

SJF(Shortest Job First) 스케줄링

SJF는 프로세서 버스트 시간이 가장 짧은 작업에 프로세서를 먼저 할당한다. 선점형과 비선점형 두 방식이 있으며, 선점형은 SRTF(Shortest Remaining Time First)라 부른다.

Priority 스케줄링

Priority 스케줄링은 준비 큐에 도착한 프로세스와 현재 실행 중인 프로세스의 우선순위를 비교한다. 우선순위가 낮은 프로세스는 계속 밀려 무한히 대기하는 기아(Starvation) 현상이 생길 수 있고, 우선순위가 같은 프로세스는 도착한 순서대로 스케줄링된다.

RR(Round Robin) 스케줄링

RR은 시분할 시스템을 위해 특별히 설계된 방식으로, 규정 시간량(Time Quantum, 시간 할당량)만큼 CPU를 할당받고 시간이 끝나면 다음 프로세스로 넘어간다. 준비 큐는 FIFO 큐이며, 스케줄러는 큐 맨 앞의 프로세스에 프로세서를 디스패치한다. 타임 퀀텀이 너무 작으면 문맥 전환이 잦아지고, 너무 크면 FCFS처럼 동작하게 된다.

Multilevel Queue 스케줄링

Multilevel Queue 스케줄링은 작업들을 서로 다른 묶음으로 분류할 수 있을 때 쓴다. 프로세스들이 우선순위에 따라 여러 큐로 나뉘어 관리되며, 각 큐는 서로 다른 스케줄링 알고리즘을 쓸 수 있다.

Multilevel Feedback Queue 스케줄링

이 방식은 다단계 큐 스케줄링을 개선한 것으로, 작업이 한 큐에 고정되지 않고 실행 중에 다른 큐로 이동할 수 있다. CPU 사용 패턴에 따라 상위 큐나 하위 큐로 옮겨간다.

Multiprocessor 스케줄링

CPU나 코어가 여러 개 있는 시스템에서, 각 CPU에 어떤 프로세스를 어떻게 할당할지 결정하는 방식이다.

HRN(Highest Response-Rate Next) 스케줄링

한슨이 개발한 HRN은 SJF 기법의 약점이었던 긴 작업과 짧은 작업 사이의 지나친 불평등을 어느 정도 보완한다. 비선점 스케줄링 기법으로, 각 작업의 우선순위를 서비스받을 시간뿐 아니라 서비스를 기다린 시간까지 함께 고려하는 함수로 나타낸다. 한 작업이 프로세서를 차지하면 그 작업이 끝날 때까지 계속 실행된다.