[운영체제] 스케줄링 기법 정리

0. CPU 스케줄링

CPU 스케줄러는 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.

최신 운영체제에서는 실질적으로 프로세스가 아니라 커널 수준 스레드를 스케줄 한다.

 

1. 기본 개념 (Basic Concepts)

다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다. 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.

즉, CPU 이용률을 최대화 하는 것은 다중 프로세서 운영체제 설계의 핵심이 된다.

 

1.1 CPU - I/O 버스트 사이클 (CPU - I/O Burst Cycle)

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

프로세스의 실행은 CPU Burst로 시작된다. 뒤이어 I/O Burst가 발생하고, 그 뒤를 이어 또 다른 CPU Burst가 발생하며, 이어 또 다른 I/O Burst 등등으로 진행된다. 결국 아래의 그림처럼 마지막 CPU Burst는 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

CPU Burst들의 지속시간을 광범위하게 측정한 그래프는 CPU 스케줄링 알고리즘을 구현할 때 매우 중요하다.

 

1.2 CPU 스케줄러(CPU Scheduler)

CPU가 유휴 상태가 될 때마다, 운영체제는 Ready Queue에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러(CPU Scheduler)에 의해 수행된다.

CPU 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

Ready Queue는 반드시 FIFO 방식의 큐가 아니어도 되고, 우선순위 큐, 트리 등으로 구현될 수 있다. 일반적으로 큐에 있는 레코드들은 프로세스의 프로세스 제어 블록(PCB)들 이다.

 

1.3 선점 및 비선점 스케줄링 (Preemptive and Nonpreemptive Scheduling)

CPU 스케줄링의 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
4. 프로세스가 종료할 때

비선점 스케줄링(nonpreemptive)하에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. (1, 4번)

선점 스케줄링(preemptive)은 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료시에 더 높은 우선 순위 프로세스가 발생 되었음을 알았을 때, 현 실행 프로세스로부터 강제로 CPU를 회수하는 것을 말한다. (2, 3번)

• 데이터가 다수의 프로세스에 의해 공유될 때 racing condition이 발생될 수 있다.
• mutex lock, monitor 등의 기법을 사용해서 racing condition을 피한다.

race condition (경쟁 상태)

경쟁 상태(race condition)란 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다. 입력 변화의 타이밍이나 순서가 예상과 다르게 작동하면 정상적인 결과가 나오지 않게 될 위험이 있는데 이를 경쟁 위험이라고 한다.

인터럽트는 어느 시점에서건 일어날 수 있고, 커널에 의해서 항상 무시될 수는 없기 때문에, 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.

 

1.4 디스패처 (Dispatcher)

디스패처(Dispatcher)는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 진행한다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump) 하는 일

디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연(dispatch latency)라고 하고 아래의 그림과 같이 일어난다.

문맥 교환은 자발적 문맥 교환과 비자발적 문맥 교환으로 나뉜다.

• 자발적 문맥 교환: 현재 사용 불가능한 자원을 요청했을 때 프로세스가 CPU 제어를 포기한 경우 발생
• 비자발적 문맥 교환: 타임 슬라이스가 만료되었거나 우선순위가 더 높은 프로세스에 의해 선점되는 경우와 같이 CPU를 빼앗겼을 때 발생

 

 

2. 스케줄링 기준 (Scheduling Criteria)

여러 CPU 스케줄링 알고리즘 사이에서 하나를 선택하기 위한 CPU 스케줄링 비교 기준은 다음과 같다.

• CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률을 말한다. (실제 시스템에서는 40%~90%까지 가진다.
• 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수로써 나타낼 수 있다.
• 총처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 한다.
• 대기 시간(Waiting Time): 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.
• 응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간이다.

CPU Utilization, Throughput을 최대화하고 Turaround Time, Waiting Time, Response Time을 최소화 하는 알고리즘의 선택이 바람직한 선택이다.

하지만 대부분의 알고리즘의 경우는 Trade-Off 임으로 본인의 Context에 맞춰서 선택하는 것이 가장 좋은 방법이다.

 

 

 

3 스케줄링 알고리즘 (Scheduling Algorithms)

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다.

대부분의 최신 CPU 아키텍처에는 여러 개의 처리 코어가 있지만 이러한 스케줄링 알고리즘을 처리 코어가 하나뿐이라고 가정하고 설명한다. 즉, 한 개의 처리 코어를 가진 CPU가 한 개인 시스템이므로 한 번에 하나의 프로세스만 실행할 수 있다.

 

3.1 선입 선처리 알고리즘 (First Come First Served Scheduling, FCFS)

선입 선처리(FCFS) 스케줄링 알고리즘은 가장 간단한 CPU 스케줄링 알고리즘이다. 

이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.

프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다. CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당된다. 이 실행 상태의 프로세스는 이어 준비 큐에서 제거된다.

FCFS의 부정적인 측면으로는 선입 선처리 정책하에서 평균대기 시간은 종종 대단히 길 수 있다는 점을 갖고 있다. (대화형 시스템에 적절하지 않다.)

 

선입 선처리 스케줄링 알고리즘은 비선점형 알고리즘이다. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하는지 또는 I/O 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유한다.

  대기시간  : P1 = 0, P2 = 24, P3 = 27

 

3.2 최단 작업 우선 스케줄링 (Shortest Job First Schduling)

최단 작업 우선(Shortest Job First, SJF) 알고리즘은 CPU 버스트 길이가 가장 작은 프로세스부터 순서적으로 CPU 코어를 할당한다.

최단 작업 우선(SJF) 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적임을 증명할 수 있다. 하지만 각 프로세스의 CPU 버스트 길이는 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현하기가 어렵다. 따라서 우리는 프로세스별 CPU 버스트의 길이를 예측해서 스케줄링 해야만 한다.

SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 비선점형일 경우 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다.

 대기시간 - P1 = 3, P2 = 16, P3 = 9, P4 = 0

3.3 라운드 로빈 스케줄링 (Round Robin Scheduling, RR)

라운드 로빈(RR) 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 

시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다. CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

 

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면, RR 정책은 FCFS와 같다. 반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥 교환을 야기한다.

시간 할당량의 크기는 알고리즘의 성능과 Trade Off 관계임으로 문맥에 적절한 시간 할당량의 크기를 설정하자.

 

대기시간 - P1 = 10-4 = 6, P2 = 4, P3 = 7

 

3.4 우선순위 스케줄링 (Priority Scheduling)

우선순위가 각 프로세스들에 연관되어 있으며, CPU 코어는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄 된다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다.

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이다.

• 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄 된 것으로 간주할 수 있다. (Blocking)
• 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 도 있다. (Starvation)

우선순위 스케줄링의 문제점을 해결할 수 있는 방법에는 우선순위 스케줄링과 라운드 로빈 스케줄링을 결합하는 방법이있다.

 

3.5 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

다단계 큐 스케줄링 방법은 우선순위 스케줄링이 라운드 로빈과 결합한 스케줄링 알고리즘이다. 이 방식의 가장 일반적인 형태에서 우선순위가 각 프로세스에 정적으로 할당되며 프로세스는 실행시간 동안 동일한 큐에 남아 있다.

아래의 그림과 같이 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 사용할 수도 있다.

각 큐에는 자체 스케줄링 알고리즘을 구현할 수 있다.

우선순위를 가진 큐 별로 CPU를 선점할 수도 있고, 큐들 사이에 CPU의 시간을 나누어서 사용할 수도 있으니, 본인이 사용하는 문맥에 따라서 알고리즘을 적절히 활용하자.

 

3.6 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 이와 반대로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

다단계 피드백 큐 스케줄링 알고리즘은 Aging과 Starvation을 예방한다.

이 알고리즘은 특정 시스템에 부합하도록 구성이 가능함으로 현대 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다.

하지만, 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수 값들을 선정하는 특정 방법이 필요하기 떄문에 가장 복잡한 알고리즘이기도하다.

 

참조 링크 : https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html