2단계와 이 편의 역할 구분

FCFS·SJF·SRTF·우선순위·라운드 로빈(RR)·HRRN 여섯 알고리즘의 정의와 간트 차트·평균 대기·반환 시간 계산은 2단계 운영체제 07편과 08편에서 같은 프로세스 집합으로 이미 전 과정을 검산했다. 이 편에서는 그 계산을 반복하지 않는다.

4단계 통합컴퓨터시스템의 출제기준은 여기서 한 걸음 더 나가 단일 큐 하나로는 표현할 수 없는 상황, 즉 우선순위가 여러 단계로 나뉘어 있고 프로세스가 그 단계를 오가는 상황(다단계 피드백 큐), CPU가 여러 개인 상황(멀티프로세서 스케줄링), 그리고 “몇 시까지 반드시 끝나야 한다”는 마감시한이 있는 상황(실시간 스케줄링)까지 요구한다.

쉽게 말하면: 2단계가 “손님 한 줄을 어떤 순서로 처리할까”를 배웠다면, 이 편은 “줄을 여러 개로 나누고, 계산대도 여러 개이고, 어떤 손님은 반드시 정해진 시각까지 나가야 하는” 더 복잡한 상황을 다룬다.

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

프로세스를 성격에 따라 여러 개의 준비 큐로 미리 나누고(예: 시스템 프로세스, 대화형 프로세스, 일괄 처리 프로세스), 큐마다 다른 스케줄링 알고리즘을 적용한다. 큐 사이에는 보통 고정된 우선순위를 두거나(상위 큐가 완전히 비어야 하위 큐 실행), 시간을 비율로 나눠 배분한다(예: 시스템 큐 50퍼센트, 대화형 큐 30퍼센트, 일괄 큐 20퍼센트).

한계: 한 번 배정된 큐를 프로세스가 스스로 옮길 수 없다. 대화형 프로세스로 분류되었다가 실제로는 CPU를 오래 쓰는 계산 위주 작업으로 판명나도, 계속 대화형 큐에 남아 다른 대화형 프로세스의 응답성을 해칠 수 있다. 이 한계를 보완한 것이 다단계 피드백 큐다.

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

MLFQ는 프로세스가 큐 사이를 이동할 수 있게 허용한다. 핵심 규칙은 다음과 같다(구체적인 할당량·조건은 시스템마다 다르며, 시험에서는 문제 지문에 규칙이 제시된다).

1. 새 프로세스는 가장 높은 우선순위 큐(가장 짧은 시간 할당량)에서 시작한다.
2. 할당된 시간 할당량을 다 쓰고도 끝나지 않으면 CPU를 많이 요구하는 프로세스로 간주해 한 단계 아래(낮은 우선순위, 더 긴 할당량) 큐로 강등한다.
3. 할당량을 다 쓰기 전에 스스로 입출력 등을 위해 대기 상태로 넘어가면 대화형 작업으로 간주해 같은 큐 또는 더 높은 큐에 남긴다(시스템 정책에 따라 다르다).
4. 낮은 큐에서 너무 오래 기다린 프로세스는 에이징을 적용해 상위 큐로 승격시켜 기아를 막는다(2단계 운영체제 08편에서 다룬 기아·에이징 개념을 그대로 재사용한다).

예제로 큐 이동 추적하기

3단계 큐(Q0: 할당량 4, Q1: 할당량 8, Q2: FCFS)를 가정하고, 실행 시간 20인 프로세스 P가 큐를 어떻게 이동하는지 추적한다. P는 계속 CPU만 쓰는 계산 위주 작업이라고 가정한다(중간에 스스로 대기 상태로 가지 않음).

결과 해석: 총 4+8+8=20으로 실행 시간과 일치한다(검산 완료). 이 프로세스는 짧게 끝나지 않는 “CPU를 많이 쓰는 작업”으로 판명되어 점점 낮은 우선순위, 대신 더 긴 시간 할당량을 받는 큐로 내려갔다. 이렇게 하면 정말 짧게 끝나는 대화형 작업은 Q0에서 빠르게 처리되고, 계산 위주 작업은 Q2에서 방해받지 않고 긴 시간을 배정받는 두 마리 토끼를 잡을 수 있다.

자주 틀리는 점: MLFQ를 “우선순위가 고정된 다단계 큐”와 혼동하면 안 된다. 다단계 큐(MLQ)는 큐 간 이동이 없고, MLFQ는 프로세스의 실행 양상을 관찰해 큐를 동적으로 재배정한다는 점이 결정적 차이다.

멀티프로세서 스케줄링

CPU(프로세서 코어)가 여러 개인 시스템에서는 “어떤 프로세스를 어떤 코어에 배정할 것인가”라는 문제가 추가된다.

대칭형 대 비대칭형

• 비대칭 멀티프로세싱(AMP, Asymmetric Multiprocessing): 하나의 마스터 프로세서만 스케줄링·입출력 결정을 내리고 나머지는 그 지시를 따른다. 구조는 단순하지만 마스터가 병목이 될 수 있다.
• 대칭형 멀티프로세싱(SMP, Symmetric Multiprocessing): 모든 프로세서가 대등하게 스케줄링 결정에 참여하고, 준비 큐를 공유하거나 각자의 큐를 갖는다. 현대 다중 코어 시스템 대부분이 이 방식이다.

프로세서 친화성 (Processor Affinity)

프로세스가 이전에 실행되던 코어에는 그 프로세스의 데이터가 캐시에 이미 적재되어 있다. 다른 코어로 옮기면 그 캐시가 무효화되고 새 코어의 캐시를 다시 채워야 하므로(캐시 미스가 늘어남) 성능이 떨어진다. 이 때문에 스케줄러는 가능하면 같은 프로세스를 같은 코어에 계속 배정하려 하는데, 이를 프로세서 친화성이라 한다.

• 연성 친화성(soft affinity): 가능하면 같은 코어에 배정하려고 노력하지만 보장하지는 않는다.
• 경성 친화성(hard affinity): 특정 프로세스를 특정 코어(들)에만 실행하도록 강제한다.

이 개념은 9~10편에서 배운 캐시 적중률과 바로 연결된다. 코어를 자주 옮기는 프로세스는 그때마다 캐시 적중률이 떨어지는 효과를 낸다 — 통합형 문항에서 “친화성이 낮으면 어떤 성능 지표가 나빠지는가”를 물을 때 캐시 적중률 저하를 답으로 연결할 수 있어야 한다.

부하 분산 (Load Balancing)

코어마다 준비 큐를 따로 두는 SMP 시스템에서는 한 코어에 작업이 몰리고 다른 코어는 놀 수 있다. 이를 막는 두 가지 방식이 있다.

• 푸시 마이그레이션(push migration): 별도의 감시 작업이 주기적으로 코어별 부하를 확인해, 부하가 높은 코어의 작업을 낮은 코어로 밀어낸다.
• 풀 마이그레이션(pull migration): 작업이 없어 놀고 있는 코어가 직접 다른 코어의 큐에서 작업을 끌어온다.

자주 틀리는 점: 부하 분산과 프로세서 친화성은 서로 목표가 충돌한다. 부하 분산은 작업을 다른 코어로 옮겨서라도 균형을 맞추려 하고, 친화성은 가능하면 옮기지 않으려 한다. 실제 스케줄러는 두 목표 사이에서 절충한다는 점이 통합형 서술 문제의 핵심 포인트다.

실시간 스케줄링: RM과 EDF

실시간 시스템은 결과가 논리적으로 맞는 것만으로는 부족하고, 정해진 시각(마감시한, deadline)까지 나와야 의미가 있다. 독학사 4단계에서는 대표적인 두 알고리즘의 가능성 검사(schedulability test) 를 계산할 수 있어야 한다.

주기적 태스크(periodic task) $i$ 마다 실행 시간(execution time) $C_i$와 주기(period) $T_i$가 주어진다. 각 태스크의 이용률(utilization)은 다음과 같이 정의한다.

• $C_i$: 태스크 $i$가 한 번 실행되는 데 필요한 CPU 시간
• $T_i$: 태스크 $i$가 반복되는 주기(= 보통 이 주기 안에 실행을 끝내야 하는 마감시한과 같다고 가정)

전체 이용률은 각 태스크 이용률의 합이다.

RM(Rate Monotonic, 최소 주기 우선)

정의: 주기가 짧은 태스크일수록 높은 우선순위를 정적으로(고정) 부여하는 선점형 알고리즘이다. 리우와 레이런드(Liu & Layland)가 증명한 충분 조건은 다음과 같다.

• $n$: 태스크 개수
• $2^{1/n}-1$: 태스크 개수가 늘어날수록 이 값은 점점 작아져 $n \to \infty$일 때 약 $\ln 2 \approx 0.693$에 수렴한다.

예제: 태스크가 3개이고 각각 $(C_1,T_1)=(1,4)$, $(C_2,T_2)=(2,6)$, $(C_3,T_3)=(2,12)$라고 하자.

$n=3$이므로 RM 충분 조건의 경계값을 계산한다.

$U=0.75 \leq 0.78$이므로 이 조건을 만족한다 — RM으로 스케줄링 가능하다고 판정한다.

자주 틀리는 점: 이 조건은 충분 조건이지 필요조건이 아니다. 즉 $U$가 경계값을 넘어도 실제로는 스케줄링이 가능한 경우가 있을 수 있다(다만 그 경우는 별도로 정밀 검사를 해야 한다). “$U$가 경계값을 넘으면 무조건 스케줄링 불가능하다”고 단정하면 틀린다 — 정확히는 “경계값 이하이면 반드시 가능하다고 보장되고, 초과하면 판정을 보류하고 별도 검사가 필요하다.”

EDF(Earliest Deadline First, 최소 마감시한 우선)

정의: 정적으로 우선순위를 고정하지 않고, 그 순간 마감시한이 가장 임박한 태스크에게 동적으로 최고 우선순위를 주는 선점형 알고리즘이다. 가능성 검사는 RM보다 훨씬 단순하고 정확하다(필요충분조건).

즉 전체 CPU 이용률이 100퍼센트를 넘지 않으면 EDF는 반드시 모든 태스크의 마감시한을 지킬 수 있다.

같은 예제(U=0.75)에 EDF를 적용하면 $0.75 \leq 1$이므로 역시 스케줄링 가능하다. 이번에는 RM으로는 불가능하지만 EDF로는 가능한 경계 사례를 보자. 태스크가 $(C_1,T_1)=(3,5)$, $(C_2,T_2)=(2,4)$ 두 개라면,

$U=1.1 > 1$이므로 EDF로도 스케줄링이 불가능하다(EDF 조건은 필요충분이므로 이 경우는 어떤 알고리즘으로도 마감시한을 모두 지킬 수 없다). RM의 충분 조건은 이보다 훨씬 낮은 경계값이므로 애초에 검사할 필요도 없이 불가능 판정이 나온다.

RM vs EDF 비교

쉽게 말하면: RM은 “항상 똑같은 순서”로 처리해 구현은 쉽지만 CPU를 약 70퍼센트까지만 안전하게 쓸 수 있고, EDF는 “매번 마감이 급한 것부터” 다시 계산해 CPU를 100퍼센트까지 알뜰하게 쓸 수 있지만 그만큼 계산 비용이 더 든다.

핵심 정리

• 다단계 큐(MLQ)는 큐 간 이동이 없고, 다단계 피드백 큐(MLFQ)는 시간 할당량 소진 여부에 따라 프로세스를 다른 큐로 강등·승격시켜 CPU 위주 작업과 대화형 작업을 자동으로 분리한다.
• 멀티프로세서 스케줄링에서는 프로세서 친화성(캐시 재사용을 위해 같은 코어에 두려는 경향)과 부하 분산(균형을 위해 다른 코어로 옮기려는 경향)이 서로 충돌하며, 이 절충이 SMP 스케줄러 설계의 핵심이다.
• RM은 주기가 짧을수록 높은 우선순위를 정적으로 부여하며, 가능성 검사는 $U \le n(2^{1/n}-1)$ 이라는 충분 조건이다.
• EDF는 마감시한이 임박한 순서로 동적으로 우선순위를 정하며, 가능성 검사는 $U \le 1$ 이라는 필요충분조건이라 이론적으로 CPU를 가장 알뜰하게 쓸 수 있다.

마무리 복습

참고 자료

• Silberschatz et al., Operating System Concepts 강의노트 정리 
• 대학 운영체제 강의노트 – CPU 스케줄링 & 데드락