스케줄링 (컴퓨팅)

스케줄링(scheduling)은 다중 프로그래밍을 가능하게 하는 운영 체제의 동작 기법이다. 운영 체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

유형

• 장기 스케줄링
• 중기 스케줄링
• 단기 스케줄링

단계

• 1단계 스케줄링

작업 스케줄링(Job scheduling)이라고도 한다. 어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다. 작업들이 시스템에 들어오는 것을 승인하는 것이기 때문에 승인 스케줄링(Admission scheduling)이라고도 한다.

• 2단계 스케줄링

어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 그렇게 함으로써 시스템을 적절히 운영할 수 있다. 작업 승인(1단계)와 CPU 배당(3단계) 사이의 완충 작용을 한다.

• 3단계 스케줄링

CPU가 사용 가능한 경우 어느 프로세스에게 배당할지를 결정한다.

결정 시점

CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때이다.

1. 수행 → 대기
2. 수행 → 준비
3. 대기 → 준비
4. 수행 → 종료

비선점형과 선점형

스케줄링 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있다. 비선점형은 위의 결정 시점 중 1번과 4번의 상황에서만 수행되며, 선점형은 1번에서 4번까지 모든 상황에서 수행된다.

• 비선점형 스케줄링(Non-preemptive Scheduling) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다.^[1]

• 선점형 스케줄링(Preemptive Scheduling) : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다. '운영 체제가 프로세서 자원을 선점'하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.^[1]

정적 스케줄링과 동적 스케줄링

프로세스의 우선순위 변동 여부에 따라 정적 스케줄링과 동적 스케줄링으로 구분할 수 있다.

• 정적 스케줄링(Static Scheduling) : 프로세스에 부여된 우선순위가 바뀌지 않는다. 고정우선순위 스케줄링이라고도 한다.

• 동적 스케줄링(Dynamic Scheduling) : 스케줄링 과정에서 프로세스의 우선순위를 변동시킨다. 유동우선순위 스케줄링이라고도 한다.

스케줄링 알고리즘

스케줄링 알고리즘을 구현할 때 스케줄링의 여러 가지 목적 중 서로 상반되는 것이 있을 수 있다. 알고리즘 작성에는 일괄 처리인지와 대화형인지와, CPU, I/O의 사용 비율, 우선 순위 부여 여부와 부여할 경우 해당 프로세스의 선점 정도, 페이지 부재 정도가 고려된다.^[2]스케줄링 알고리즘에는 다음과 같은 종류가 있다.

• 비선점 프로세스 스케줄링

1. FCFS 스케줄링(First Come First Served Scheduling)
2. SJF 스케줄링(Shortest Job First Scheduling)
3. HRRN 스케줄링(Highest Response Ratio Next Scheduling)

• 선점 프로세스 스케줄링

1. RR 스케줄링(Round Robin Scheduling)
2. SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
3. 다단계 큐 스케줄링(Multilevel Queue Scheduling)
4. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
5. RM 스케줄링(Rate Monotonic Scheduling)
6. EDF 스케줄링(Earliest Deadline First Scheduling)

평가 기준

스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다.

• CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율.
• 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수.
• 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간.
• 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합.
• 반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.

같이 보기

• 비율 단조 스케줄링

각주

1. 이계영. 《운영 체제》. 정익사. 87쪽.
2. 이계영. 《운영 체제》. 정익사. 82~3쪽.