프로세스 상태와 CPU 스케줄링

여러 프로세스가 하나의 CPU를 나눠 쓰려면 "지금 누구에게 CPU를 줄 것인가"를 정하는 규칙이 필요하다. 이것이 CPU 스케줄링이며, 프로세스의 상태 변화를 이해해야 스케줄링이 언제 일어나는지도 이해할 수 있다. 프로세스의 구조와 PCB, 스레드는 프로세스와 스레드에 따로 정리했다.

프로세스 상태

보류는 원래 어느 상태에서 내려갔느냐에 따라 둘로 나뉜다. 준비 상태에서 내려가면 보류 준비(suspended ready), 대기 상태에서 내려가면 보류 대기(suspended blocked) 다. 보류 대기 중에 기다리던 입출력이 끝나면 보류 준비로 바뀌고, 어느 쪽이든 재개(resume) 되어야 메모리로 돌아와 준비·대기 상태가 된다. 운영체제가 프로세스를 보류시키는 경우는 대개 셋이다.

• 메모리 부족 같은 장애가 생겨 회복될 때까지 일부를 내려 둔다.
• 동작이 의심스러운 프로세스를 멈춰 두고 확인한 뒤 재개하거나 끝낸다.
• 부하가 너무 커서 몇 개를 내려 두었다가 정상으로 돌아오면 다시 올린다. 이 판단이 중기 스케줄러의 일이다(아래 「스케줄링 큐와 스케줄러의 종류」).

상태 전이와 스케줄링 시점

생성 → 준비 → 실행 → 완료가 기본 흐름이다. 실행 중의 전이가 곧 CPU 스케줄링이 일어나는 시점이다.

비선점 스케줄링에는 Timeout(실행 → 준비) 전이도, 깨어난 프로세스가 실행 중인 것을 빼앗는 전이도 없다. 실행 중인 프로세스는 끝나거나 스스로 대기 상태로 갈 때만 CPU를 내놓는다.

교착 상태(deadlock)는 별도의 상태라기보다, 프로세스들이 서로가 가진 자원을 기다리며 영원히 대기하는 상황이다. 자세한 내용은 교착 상태 참고.

왜 CPU 스케줄링이 필요한가

모든 프로그램은 실행되는 동안 CPU burst(CPU로 명령을 실행하는 구간)와 I/O burst(I/O를 요청하고 기다리는 구간)를 번갈아 반복한다. 그 비율은 프로그램마다 다르다.

이런 작업들이 섞여 있으므로, 대화형(I/O-bound) 작업에 빠르게 응답하면서도 CPU를 놀리지 않도록 공평하면서 효율적으로 CPU를 나눠 주는 규칙이 필요하다.

그래서 "먼저 손 든 순서대로"가 가장 공정한 방식은 아니다. 보통 I/O-bound 프로세스에 CPU-bound 프로세스보다 높은 우선순위를 준다. I/O-bound 프로세스는 CPU를 잠깐 쓰고 곧 대기 상태로 들어가 한동안 CPU를 찾지 않는다. 먼저 처리해 대기로 보내 두면 그동안 CPU-bound 프로세스가 CPU를 길게 쓸 수 있고, 입출력 장치와 CPU가 동시에 바쁘게 돌아간다. 동영상 재생·디스크 백업은 I/O-bound, 컴파일·수학 연산·그래픽 계산은 CPU-bound에 가깝다.

CPU 스케줄러와 디스패처

• CPU 스케줄러: ready 상태의 프로세스 중 CPU를 줄 프로세스를 고르는 운영체제 코드
• 디스패처: 고른 프로세스에게 CPU 제어권을 넘기는 운영체제 코드. 이 과정이 문맥 교환이다. 문맥 교환(PCB 저장·복원) 동안은 실제 일을 하지 않으므로 OS 오버헤드의 주요 원인이다(프로세스와 스레드). 디스패처는 문맥 교환 → 사용자 모드로 전환 → 프로그램의 이어서 실행할 위치로 점프 순으로 일하고, 한 프로세스를 멈추고 다른 프로세스를 시작하기까지 걸리는 시간을 디스패치 지연(dispatch latency) 이라고 한다. 디스패처는 스케줄링 때마다 불리므로 이 지연이 짧아야 한다.

스케줄링 큐와 스케줄러의 종류

프로세스(정확히는 PCB)는 상태에 따라 커널 주소 공간의 data 영역에 있는 큐에 줄을 선다.

운영체제는 다음 프로세스를 고를 때마다 모든 PCB를 뒤지지 않고, 자원별로 줄(큐)을 세워 그 줄만 본다. 이름은 큐지만 반드시 선입선출은 아니다. 같은 줄 안에서도 우선순위가 높은 프로세스가 먼저 나간다.

대기(device) 큐는 보통 입출력 장치마다 따로 있어서, 같은 장치를 기다리는 프로세스끼리 한 줄에 선다. 입출력이 끝나 완료 인터럽트가 오면 운영체제는 그 장치의 대기 큐에서 작업이 끝난 PCB를 찾아 상태를 대기에서 준비로 바꾸고 준비 큐로 옮긴다.

이 큐 사이에서 프로세스를 옮기는 결정을 누가 내리느냐에 따라 스케줄러를 셋으로 나눈다.

현대 범용 OS(Linux, Windows, macOS)에는 장기 스케줄러가 따로 없다. 새 프로세스는 만들어지는 즉시 ready가 된다. 메모리가 부족할 때도 프로세스를 통째로 내보내는 중기 스케줄링 대신 페이지 단위의 교체와 스왑으로 버티고(가상 메모리), 그래도 모자라면 Linux는 OOM killer가 프로세스를 골라 끝낸다. 교재의 suspended 상태가 실제로는 「페이지 대부분이 스왑으로 나간 프로세스」로 나타나는 셈이다.

보통 "CPU 스케줄링"이라 하면 단기 스케줄링을 말하고, 이 노트의 나머지도 단기 스케줄러의 알고리즘을 다룬다. 스케줄링 대상인 프로세스의 문맥과 PCB는 프로세스와 스레드에 있다.

성능 척도

여기서 시간은 프로그램 전체의 시작~종료가 아니라 CPU burst 하나 단위로 잰다.

비선점 스케줄링 (Non-preemptive)

한 번 CPU를 받은 프로세스는 스스로 반납할 때까지 계속 사용한다. 응답 시간 예측이 쉽고 일괄 처리에 적합하지만, 덜 중요한 작업 때문에 중요한 작업이 기다릴 수 있다.

HRN의 우선순위는 (대기 시간 + 서비스 시간) / 서비스 시간이다. 오래 기다릴수록 값이 커져 결국 순서가 돌아온다.

호위 효과는 순서만 바꿔도 크게 줄어든다. CPU burst가 17, 5, 2인 프로세스 A, B, C가 이 순서로 준비 큐에 들어왔다고 하자.

SJF의 두 가지 방식과 한계

비선점형 SJF는 일단 CPU를 주면 빼앗지 않는다. 선점형 SJF인 SRTF(Shortest-Remaining-Time-First)는 새 프로세스의 burst가 현재 프로세스의 남은 burst보다 짧으면 CPU를 빼앗으며, 평균 대기 시간이 최소임이 보장된다.

SJF의 한계는 둘이다. 짧은 작업만 선호해 긴 작업이 기아(starvation)에 빠질 수 있고, CPU 사용 시간을 미리 알 수 없어 과거 burst를 지수 평균(exponential averaging)해 추정할 뿐이다. 그래서 SJF는 이론상 최적이지만 그대로 구현할 수는 없고, 정확한 이름은 「다음 CPU burst가 가장 짧은 작업 먼저」다.

τ(n+1) = α · t(n) + (1 − α) · τ(n)     (0 ≤ α ≤ 1)
 
t(n): 방금 끝난 n번째 burst의 실제 길이,  τ(n): n번째 burst의 예측값
α = 0 → 최근 실적을 무시하고 예측이 처음 값 그대로
α = 1 → 바로 직전 burst 길이를 그대로 다음 예측으로
보통 α = 0.5. τ(0)은 상수나 시스템 평균으로 둔다

식을 풀면 과거 burst일수록 가중치가 α(1 − α)ᵏ로 지수적으로 줄어든다. 최근 행동을 더 믿되 한 번 튄 값에 휘둘리지 않게 하는 이동 평균이다.

우선순위 스케줄링

우선순위가 가장 높은 프로세스에게 먼저 CPU를 준다. 우선순위가 같으면 FCFS로 처리한다. 선점형·비선점형 모두 가능하며, SJF도 "CPU burst가 짧을수록 우선순위가 높은" 우선순위 스케줄링의 일종이다. 마찬가지로 기아 문제가 생길 수 있는데, 오래 기다린 프로세스의 우선순위를 점점 높여 주는 에이징(aging) 으로 해결한다.

우선순위는 메모리 요구량·열린 파일 수·평균 burst 같은 내부 요인이나, 사용자·요금·작업의 중요도 같은 외부 요인으로 정한다. 기다리는 동안 낮은 우선순위 작업이 락을 쥐고 있으면 높은 우선순위 작업까지 늦어지는 우선순위 역전이 생길 수 있다(프로세스 동기화).

우선순위는 PCB에 기록되고, 일부는 사용자가 바꿀 수 있다. 리눅스·macOS에서는 ps -eo pid,ni,pri,comm으로 nice 값을 보고, nice -n 10 <명령>으로 낮은 우선순위로 실행하거나 renice로 실행 중인 프로세스의 값을 바꾼다. nice 값은 -20(가장 우선)부터 19(가장 양보)까지이고, 값을 낮추려면 관리자 권한이 필요하다. Windows에서는 작업 관리자나 Process Explorer에서 우선순위를 확인한다.

우선순위 스케줄러 구현

준비 큐를 우선순위 큐(힙) 로 두면 된다. 키를 (우선순위, 도착 시각)으로 잡아 우선순위가 같으면 먼저 온 것이 나가게(FCFS) 한다.

import heapq
 
ready = []                           # (priority, arrival, pid). 숫자가 작을수록 높은 우선순위
def arrive(pid, priority, t):
    heapq.heappush(ready, (priority, t, pid))
def dispatch():
    return heapq.heappop(ready)[2] if ready else None

우선순위 단계가 적고 정해져 있으면(예: Linux 실시간 클래스의 0~99) 힙 대신 단계마다 큐 하나 + 비어 있지 않은 큐를 표시한 비트맵을 두고, 비트맵에서 가장 높은 비트를 찾아 O(1)에 고른다. Linux 2.6 초기의 O(1) 스케줄러가 이 구조다. 힙은 힙과 우선순위 큐에 있다.

선점 스케줄링 (Preemptive)

우선순위가 더 높은 프로세스가 실행 중인 프로세스의 CPU를 빼앗을 수 있다. 빠른 응답이 필요한 대화형·시분할 시스템에 쓰이며, 타이머 인터럽트가 필요하고 문맥 교환 오버헤드가 크다.

Round Robin

현대 시스템이 쓰는 스케줄링의 기반이다.

• 각 프로세스는 같은 크기의 할당 시간(time quantum, 보통 10~100ms)을 받고, 다 쓰면 타이머 인터럽트로 CPU를 빼앗겨 ready 큐 맨 뒤로 간다.
• ready 큐에 n개의 프로세스가 있고 할당 시간이 q라면, 어떤 프로세스도 (n-1)q 이상 기다리지 않는다. 그래서 응답 시간이 빠르다.
• q가 너무 크면 FCFS와 같아지고, 너무 작으면 문맥 교환이 잦아져 오버헤드가 커진다. 경험칙은 CPU burst의 약 80%가 q보다 짧게 잡는 것이다. 그러면 대부분의 작업이 할당 시간 하나 안에 끝나고, 긴 작업만 잘린다. q는 문맥 교환 시간(수 μs)보다 훨씬 커야 한다.
• 대기 시간이 쓰려는 CPU 시간에 비례한다. SJF보다 평균 소요·대기 시간은 길지만 응답 시간은 짧아, 짧은 작업과 긴 작업이 섞여 있을 때 효과적이다.

다단계 큐 (Multilevel Queue)

ready 큐를 여러 줄로 나누고, 프로세스 종류에 따라 줄을 고정한다.

큐끼리는 고정 우선순위(foreground를 모두 처리한 뒤 background, 낮은 큐는 기아 위험)나 타임 슬라이스(예: foreground 80%, background 20%)로 나눈다.

다단계 피드백 큐 (Multilevel Feedback Queue)

다단계 큐의 "한 번 정해지면 못 바꾸는" 차별을 없애, 프로세스가 큐 사이를 이동할 수 있게 한다. 정의할 파라미터는 큐의 개수, 큐별 알고리즘, 승격·강등 기준, 처음 들어갈 큐다.

보편적으로 새 프로세스는 가장 높은 큐에 들어가고, 위쪽 큐일수록 RR 할당 시간이 짧으며(마지막 큐는 FCFS), 할당 시간을 다 쓰고도 끝나지 않으면 한 단계 아래로 강등된다.

결과적으로 CPU burst가 짧은 작업은 빨리 끝나고, 긴 작업은 점점 아래로 내려간다. 실행 시간을 미리 몰라도 SJF와 비슷한 효과를 낸다. I/O-bound 프로세스는 위쪽 큐에서 할당 시간을 다 쓰기 전에 대기로 가므로 높은 우선순위를 유지하고, CPU-bound 프로세스는 자연스럽게 아래로 밀린다. 아래쪽 큐에서 너무 오래 기다린 프로세스는 에이징으로 위 큐로 올려 기아를 막는다. 구현은 복잡하지만 범용 운영체제 스케줄러의 가장 일반적인 뼈대다.

같은 작업으로 비교하기

같은 작업 묶음을 각 알고리즘에 넣어 보면 차이가 숫자로 드러난다. 다섯 프로세스가 1ms 간격으로 도착한다. 우선순위는 숫자가 클수록 높다.

• 반환 시간 = 끝난 시각 − 도착 시각, 대기 시간 = 반환 시간 − 실행 시간이다.
• 처음에 긴 P2가 일찍 들어와 있으므로 FCFS는 호위 효과로 가장 나쁘다. 도착 순서만 바꿔 P3·P1·P4·P5·P2 순으로 들어오게 해도 FCFS의 평균 대기 시간은 13.2로 떨어진다.
• SJF·SRTF가 평균 대기 시간을 최소로 만든다는 것이 수치로 확인된다. 대신 긴 P2는 어느 쪽에서든 맨 마지막이다.
• RR은 평균값으로는 SJF 계열보다 못하지만, 짧은 P4가 19ms 만에 끝나는 것처럼 응답 시간이 고르다. RR의 장점은 평균이 아니라 대화형 응답에 있다.

MLFQ도 늘 이득은 아니다. 실행 시간이 30, 20, 10인 세 작업이 동시에 들어오면, 할당 시간 1인 RR의 평균 반환 시간은 46인데, 할당 시간을 1·2·4로 늘려 가는 3단계 MLFQ는 약 48로 조금 더 길다. 아래 큐로 갈수록 할당 시간이 길어져, 가장 짧은 작업(10)도 긴 작업들의 4ms 조각 뒤에서 기다리기 때문이다. MLFQ의 강점은 작업 길이를 미리 모르는 상황에서 짧은 대화형 작업을 우대하는 데 있다.

특수한 환경의 스케줄링

프로세서 친화도와 부하 분산

프로세스가 다른 CPU로 옮겨 가면 이전 CPU의 캐시에 데워 둔 데이터는 버려지고 새 CPU의 캐시를 다시 채워야 한다. 그래서 스케줄러는 프로세스를 가능하면 같은 CPU에서 계속 돌린다. 이것이 프로세서 친화도(processor affinity) 다.

반대로 CPU마다 준비 큐를 따로 두는 SMP에서는 어떤 CPU는 바쁘고 어떤 CPU는 노는 일이 생기므로 부하 분산(load balancing) 이 필요하다.

Linux는 둘을 함께 쓴다. 부하 분산은 프로세스를 옮기므로 친화도의 이득(데운 캐시)을 깎는다. 그래서 실제 스케줄러는 같은 코어의 하이퍼스레드 → 같은 칩 → 다른 NUMA 노드 순으로 가까운 곳부터 옮기고, 불균형이 일정 기준을 넘을 때만 이주한다.

실제 운영체제의 스케줄러

교과서 알고리즘은 실제 스케줄러의 재료다. 범용 OS는 여러 아이디어를 섞어 "대화형 작업은 빠르게 응답하고, CPU를 오래 쓰는 작업도 굶기지 않게" 만든다.

• I/O 중심 작업은 CPU를 짧게 쓰고 금방 대기 상태로 가므로, MLFQ·CFS 모두에서 자연스럽게 우대된다. 키 입력에 빨리 반응하는 이유다.
• 여러 작업을 번갈아 실행해 동시에 도는 것처럼 보이게 하는 것이 병행(concurrency), 코어 여러 개에서 실제로 같은 순간에 실행하는 것이 병렬(parallelism) 이다.

알고리즘 평가 방법

핵심 정리

• 준비 ↔ 실행 ↔ 대기 사이의 전이(dispatch, timeout, block, wake up)를 기억한다.
• 비선점: FCFS, SJF, LJF, HRN / 선점: RR, SRT, LRTF, MLQ, MLFQ.
• SJF(SRTF)는 평균 대기 시간 최소지만 기아와 burst 예측 문제가 있고, 에이징으로 기아를 완화한다.
• RR은 응답 시간이 짧고 (n-1)q 이상 기다리지 않는다. MLFQ는 실행 시간을 몰라도 짧은 작업을 우대한다.
• 문맥 교환은 피할 수 없는 오버헤드이므로, 스케줄링 정책은 응답성과 오버헤드 사이의 균형이다.