[OS] 선점형과 비선점형 스케줄링의 정의와 종류

1. CPU 스케줄링이란?

복수의 프로세스 중 어떤 프로세스가 CPU를 가장 먼저 사용하고 얼마나 오래 사용할지를 결정하는 방식을 의미한다.
이를 위해서 스케줄링 기법마다 다르게 프로세스들의 우선순위를 측정하고, CPU 사용시간을 산정한다.

(1) 좋은 CPU 스케줄링이란?

CPU란 단일 자원을 프로세스들에게 최대한 공평하게 배분하여 프로세스 처리율과 CPU 이용률을 높이고, 응답시간, CPU 과부화(오버 헤드), 프로세스들의 처리 대기시간을 줄이는 것이 좋은 스케줄링이다.

공평성🆙 ➜ ( 프로세스 처리율⬆️, CPU 이용률⬆️ ) | (응답 시간 ⬇️, CPU 과부하 ⬇️, 프로세스 처리 대리시간 ⬇️)

2. 선점형 스케줄링에 대하여

현재 CPU를 활용하고 있는 프로세스를 A라고 하자. 이때 준비큐에서 A보다 처리 우선순위가 높은 프로세스를 발견한다면 선점형 스케줄링은 다음과 같이 실행된다.

• 1️⃣ 현재 실행 중인 프로세스 A를 준비큐 꼬리로 보낸다.
• 2️⃣ A보다 우선순위가 높은 프로세스에게 CPU를 할당한다. (만약 그러한 프로세스가 복수라면 당연하게 그들 중 우선순위가 가장 높은 녀석이 준비큐의 머리에 존재하게 되고, 그것에게 CPU 할당)

우선순위가 높은 프로세스를 먼저 처리하는 성격 때문에 DeadLine이 존재하는 응답을 해줘야 하는 환경, 실시간으로 응답을 해줘야 하는 환경에 적절하다. (각각 우선순위를 DeadLine이 임박한 순, 먼저 입력한 순으로 두면되기 때문이다.)

그렇다면 이 우선순위의 기준을 어떻게 세울 것인가가 관건이다. 이 우선순위를 어떻게 세울 것인가의 기준에는 총 5개가 있다. 따라서 선점형 스케줄링의 종류에도 5개가 존재한다.

이제부터 "A : 현재 CPU를 할당받아 사용 중인 프로세스" 라고 가정하고 다음 종류들을 살펴보겠다.

(1) SRT

a. 정의

우선순위 기준: 프로세스의 남은 실행시간이 짧을 수록 우선순위가 높다.

만약 준비큐에 담겨 있는 값들 중 A보다 남은 실행시간이 짧은 프로세스가 있다면 해당 프로세스에게 CPU를 할당하고, A는 다시 준비큐에 넣는다.

b. 장단점

• 장점: 평균 대기 시간이 최소화 된다.
• 단점: 실행 시간이 긴 프로세스B가 준비 큐에 존재한다고 할 때, 그것보다 실행시간이 짧은 신입 프로세스가 계속 준비큐에 들어온다면, B는 영원히 CPU를 할당 받지 못하는 기아 상태가 발생한다.

c. 사용해야 할 상황

짧은 작업들이 많아 빠르게 처리해야하는 상황

(2) RR (Round Robin)

a. 정의

프로세스마다 자신에게 할당된 시간 (Time Quantum)이 존재.
해당 할당 시간을 초과하면 강제로 종료하고 준비 큐의 꼬리로 이동

b. 장단점

• 장점: 공평성(모든 프로세스가 자원을 공평하게 쓰는 것)이 가장 높다.

          평균적인 응답시간이 짧다.

• 단점:
  Time Quantum이 너무 짧으면 문맥 전환이 잦음 ➜ 오버 헤드가 증가
  Time Quantum이 너무 길면 FCFS(들어온 순으로 처리)가 되어서 선점형 스케줄링 쓰는 이유가 없음

c. 사용해야 할 상황

대화형 시스템 (채팅, 페이지 로딩, 명령어 실행)에서 유용

대화형 시스템은 사용자의 요청을 빠르게 처리하고 즉각적인 반응을 제공하는 것이 중요. 이것을 보장하기 위해서는 하나의 프로세스가 CPU를 독점하지 않고, 응답 시간이 되도록 짧아야 하는데, RR는 평균적인 응답 시간이 짧기 때문에 이에 적합하다.

(3) 우선순위 스케줄링

우선순위 기준: OS 설계자가 설정

a. 정의

각 프로세스에게 나름의 기준을 둔 우선순위를 제공, 우선순위가 높은 프로세스에게 CPU를 우선 할당하는 방식이다. 당연하게도, 현재 CPU를 할당 받아 사용 중인 프로세스보다 신입 프로세스의 우선순위가 높다면 현재 실행 중인 프로세스를 중단하고 해당 프로세스를 먼저 실행한다.

b. 장단점

• 장점: 아무래도 설계자의 CUSTOM이 가능하니, 설계자 혹은 사용자에게 의미상 중요한 작업들을 먼저 처리할 수 있다.
• 단점: 이 또한 특정 프로세스B보다 우선순위가 높은 프로세스만 계속 준비 큐에 들어온다면 B는 기아 상태에 빠질 수 있다.
• 보안: 단점을 보아하기 위해 Priority Aging 기법을 사용한다. Priority Aging 기법은 준비 큐에 존재하는 시간이 길수록 해당 프로세스의 우선순위를 높이는 것이다.

c. 사용 예시

사용자 기준 우선순위가 높은 것을 특정할 수 있고, 그 프로세스들부터 처리하고 싶을 때

3. 비선점형 스케줄링

한 프로세스A가 CPU를 할당 받으면 A가 작업 종료 혹은 I/O BLOCK 후 CPU를 반환할 때까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식이다.

(1) 특징

• 1️⃣ 우선순위가 높은 신입 프로세스가 들어왔다는 이유로 문맥교환이 불가하다.
• 2️⃣ 1번 특징 때문에 문맥 전환 횟수가 적다. ➜ CPU 과부하가 날 확률이 적고, CPU 안정성이 높다.
• 3️⃣ 실행 시간이 긴 프로세스가 CPU 독점할 가능성이 높다. ➜ 실시간 시스템, 대화형 시스템에서는 부적절하다.

여기서 헷갈리지 말아야 할 점은 비선점형 스케줄링 또한 프로세스간의 우선순위를 가지고 있다는 것이다. 다만 우선순위가 높은 신입이 들어왔다는 이유로 문맥교환은 하지 않는다. 다음은 그 종류 4가지에 대해서 알아보겠다.

(2) FCFS (First Come, First Served 선입 선출)

준비 큐 내의
우선순위 기준: 준비 큐 먼저 들어온 프로세스가 우선순위가 높다.

a. 정의

먼저 준비 큐에 들어온 놈 먼저 실행 (선배 대우)

b. 장단점

• 장점: 구현이 간단하다.
• 단점: 실행시간 긴 프로세스의 CPU 독점 가능성이 있음. Convoy 효과 (긴 작업이 앞 순위에 있으면 뒤의 짧은 작업들은 자신의 실행시간보다 대기 시간이 더 길어지는 효과)가 생김

c. 사용 예시

단순환 배치 처리 시스템 (일괄 작업)

(3) SJF

우선순위 기준: 실행시간이 짧은 프로세스가 우선순위가 높다.

a. 정의

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식

b. 장단점

• 장점: 짧은 작업이 먼저 끝나므로 평균 대기 시간이 줄어든다.
  비선점형 스케줄링 중에서는 가장 CPU의 효율적인 사용하는 기법
• 단점:
  준비 큐는 우선순위 큐이다 보니, 실행시간이 긴 프로세스는 언제나 후순위이다. (기아 상태)
  모든 프로세스의 실행 시간을 미리 알아야 효과적 (그런 상황이 잘 없음)

c. 사용 예시

실행 시간이 일정해서 예측 가능한 환경

(4) Priority 스케줄링

우선순위 기준: 설계자 마음

a. 정의

이것도 선점형의 Priority 스케줄링의 비선점형 버전

b. 장단점

장점:

• 중요한 작업을 빠르게 처리 가능.

단점:

• 우선순위가 낮은 프로세스가 실행되지 못할 가능성(기아 상태, Starvation).
• 우선순위 기준이 명확하지 않으면 비효율적.
• 해결 방법 → Priority Aging (오래 기다린 프로세스의 우선순위를 점차 증가시키는 방법).

c. 사용 예시

선점형의 Priority 스케줄링이랑 거의 유사

4 HRRN (Highest Response Ratio Next, 최대 응답 비율 우선)

우선순위 기준: 대기 시간이 길수록 우선순위가 높다.

a. 정의

응답 비율을 계산한다. $응답 비율 = \frac{대기시간 + 실행시간}{실행시간}$

이 응답 비율이 높을수록 우선순위가 올라간다.

b. 장단점

• 장점: 기아 상태(Starvation) 방지** → 오래 기다린 프로세스가 우선 실행될 가능성이 높음.
• 단점: 비교적 복잡한 연산이 필요함.

c. 사용예시

• 우선순위를 조절해야 하는 환