[OS] Scheduling에 대하여

CPU가 프로세스를 실행하는 순서를 나타내는 스케쥴링과 알고리즘 종류를 알아보자.

Apr 12, 2024

Contents

✅ 스케쥴링 개요 ✅ 가정하기 ✅ 스케쥴링 평가 항목 ✅ 스케쥴링 알고리즘 ✅ 입출력 연산의 고려

✅ 스케쥴링 개요

우리는 프로세스를 실행시키기 위한 문맥 교환, 시스템 콜 등의 저수준 기법에 대해서는 이제 분명하게 이해하고 있을 것이다. 추가적으로 운영체제 스케쥴러의 고수준 정책에 관해서 이해가 필요하다.

❓

스케쥴링은 어떻게 개발하는가? 1. 스케쥴링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가? 2. 핵심 가정은 무엇인가? 3. 어떤 평가 기준이 중요한가? 4. 컴퓨터 시스템 초창기에 사용되었던 기본 접근법은 무엇인가?

✅ 가정하기

가장 먼저 프로세스에 대하여 몇 가지 가정을 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드라고 부르기로 한다. 우리가 지금 설명에서 사용할 워크로드에 대한 가정은 비현실적이다. 하지만, 당장 논의하는 데는 아무 문제 없다. 앞으로 논의가 진행됨에 따라 가정을 완화시킬 것이고 최종적으로 제대로 동작하는 스케쥴링 정책을 만들게 될 것이다.

모든 작업은 같은 시간 동안 실행된다.

모든 작업은 동시에 도착한다.

각 작업은 시작되면 완료될 때까지 실행된다.

모든 작업은 CPU만 사용한다. (즉, 입출력을 수행하지 않는다.)

각 작업의 실행 시간은 사전에 알고 있다.

✅ 스케쥴링 평가 항목

워크로드에 대한 가정 이외에 스케쥴링 정책 비교를 위해 스케쥴링 평가 항목을 결정해야 한다. 평가 항목은 다양하다. 여기서는 크게 두 가지로 나뉜다.

1. 반환 시간

→ 작업이 완료된 시각에서 작업이 시스템에 도착한 시각을 뺀 시간

(끝난 시각 - 도착 시각)

2. 응답 시간

→ 작업이 도착할 때부터 처음 스케쥴 될 때까지의 시간

(처음 시작한 시각 - 도착 시각)

✅ 스케쥴링 알고리즘

스케쥴링 알고리즘은 크게 4가지로 구성된다.

1. 선입 선출 (FIFO - First In First Out)

→ 가장 먼저 도착한 작업부터 실행한다.

만약 3가지 작업이 도착했고 처음 도착한 작업이 길면, 반환시간과 응답 시간 측면에서 모두 나쁜 성능을 보인다. 슈퍼에서 계산을 기다릴 때 앞사람이 카트에 물건을 가득 싣고 있는 경우와 비슷하다.

2. 최단 작업 우선 (SJF - Shortest Job First)

→ 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

모든 작업이 동시에 도착한다면 SJF가 최적의 스케쥴링 알고리즘이다!! 하지만 모든 작업이 동시에 도착한다는 보장이 없다.

B와 C가 늦게 도착하면 A의 실행이 끝날 때까지 기다려야 한다.. 이 경우에도 반환 시간에 문제가 발생한다.

3. 최소 잔여시간 우선 (STCF - Shortest Time-to-Completion First)

→ 이 문제를 해결하기 위해 가정 3을 완화해야 한다. (가정 3: 각 작업은 한 번 시작하면 완료될 때까지 실행된다) SJF에 선점 기능을 추가하여 만든 스케쥴러가 바로 STCF이다. 언제든 새로운 작업이 시스템에 들어오면, 이 스케쥴러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케쥴한다.