운영체제 및 시스템 아키텍처
2단계: 커널, 가상 메모리, 그리고 AI 가속기의 세계
이론적 기초 — 1단계에서 멈춰있던 질문들
1단계에서 우리는 프로세스와 스레드가 어떻게 CPU를 나눠 쓰는지를 배웠고, 캐시 계층이 메모리 접근 속도를 어떻게 좌우하는지를 다뤘다. 그런데 잠깐, 거기서 아주 자연스러운 질문 하나가 남는다. "프로세스가 CPU를 나눠 쓴다고 했는데, 그 '나눠주는 주체'는 누구야?" 그것이 바로 **운영체제의 핵심, 즉 커널(Kernel)**이다.
커널은 운영체제에서 가장 깊은 곳에 있는 코드다. 하드웨어와 소프트웨어 사이에서 중재자 역할을 하며, 모든 자원 할당의 최종 결정권자다. 그러나 우리가 1단계에서 배운 멀티스레드 프로그래밍은 사실 커널이 제공하는 추상화 위에서 돌아가는 것이었다. 이제 그 추상화의 뚜껑을 열어볼 차례다.
그리고 메모리에 대해서도 생각해보자. 1단계에서 "L1 캐시가 빠르고 RAM이 느리다"는 걸 배웠는데, 그렇다면 수십 개의 프로세스가 동시에 RAM을 점유하려 하면 어떻게 될까? RAM이 부족하면? 어떤 데이터를 디스크로 내보내고, 어떤 것을 남길까? 이 질문이 **가상 메모리(Virtual Memory)와 페이지 교체 정책(Page Replacement Policy)**의 출발점이다.
마지막으로, 현대 컴퓨팅에서 빼놓을 수 없는 존재가 있다. GPU와 NPU다. 인공지능 모델이 수십억 개의 파라미터를 수백 밀리초 안에 처리할 수 있는 이유는 CPU가 똑똑해서가 아니라, 아예 다른 철학으로 설계된 하드웨어가 그 연산을 맡고 있기 때문이다. 그 철학을 이해하는 것이 이번 단계의 세 번째 목표다.
자, 이 세 가지 질문을 순서대로, 그리고 연속적으로 풀어나가 보자.
커널 설계 — 운영체제의 심장을 해부하다
커널이 존재하는 이유: 보호와 추상화
컴퓨터에는 함부로 건드리면 시스템 전체가 망가지는 자원들이 있다. 메모리 주소를 직접 덮어쓰거나, 인터럽트 처리기를 멋대로 교체하거나, 다른 프로세스의 메모리를 읽거나. 만약 모든 프로그램이 이런 일을 할 수 있다면 컴퓨터는 단 1초도 안정적으로 작동하지 못한다.
그래서 현대 CPU는 하드웨어 수준에서 **특권 레벨(Privilege Level)**을 나눈다. Intel x86 기준으로는 Ring 0부터 Ring 3까지 있는데, Ring 0은 커널 모드(Kernel Mode)로 모든 명령어를 실행할 수 있는 최고 권한이고, Ring 3은 사용자 모드(User Mode)로 일반 애플리케이션이 돌아가는 제한된 영역이다. 우리가 Chrome이나 게임을 실행할 때 그 프로세스는 Ring 3에 있다. 파일을 읽고 싶다면? 커널에게 요청을 보내야 하고, 이것을 **시스템 콜(System Call)**이라고 부른다. 이 순간 CPU는 자동으로 Ring 3에서 Ring 0으로 전환되고(이를 컨텍스트 스위치의 일부라 볼 수 있다), 커널이 요청을 처리하고 결과를 돌려준다.
[노트 기록] 커널 모드 vs 사용자 모드: Ring 0(커널 모드) = 하드웨어 직접 접근 가능 / Ring 3(사용자 모드) = 시스템 콜을 통해서만 커널 기능 요청. 이 경계를 "커널-유저 공간 경계(Kernel-User Space Boundary)"라 함.
어떻게 설계할 것인가: 모놀리식 vs 마이크로커널
커널을 어떻게 구조화하느냐는 수십 년간 운영체제 연구자들이 싸워온 전쟁이다. 크게 두 진영이 있다.
**모놀리식 커널(Monolithic Kernel)**은 파일 시스템, 디바이스 드라이버, 스케줄러, 네트워킹 스택 등 모든 핵심 기능을 하나의 거대한 커널 공간에 집어넣는 설계다. Linux가 대표적인 예다. 장점은 성능이다. 컴포넌트 간 통신이 함수 호출로 이루어지므로 오버헤드가 극히 적다. 단점은 커널 내 버그 하나가 시스템 전체를 죽일 수 있다는 것이다(커널 패닉, Kernel Panic).
반면 **마이크로커널(Microkernel)**은 최소한의 기능만 커널에 남기고(주로 메모리 관리, IPC, 기본 스케줄링), 나머지는 사용자 공간의 서버 프로세스로 분리한다. QNX, MINIX, seL4가 여기에 속한다. 안정성과 보안이 뛰어나지만, 컴포넌트 간 통신이 **IPC(Inter-Process Communication)**를 통해 이루어지므로 성능 오버헤드가 크다. 재미있는 역사적 사실을 하나 추가하면, Linus Torvalds(Linux 창시자)와 Andrew Tanenbaum(MINIX 창시자) 사이에 1992년 인터넷에서 벌어진 모놀리식 vs 마이크로커널 논쟁은 운영체제 역사에서 유명한 사건이다(Torvalds-Tanenbaum debate). Windows NT와 macOS의 XNU는 두 방식을 혼합한 **하이브리드 커널(Hybrid Kernel)**이다.
[노트 기록] 커널 설계 트리오: 모놀리식(Linux) = 빠르지만 버그에 취약 / 마이크로커널(QNX, seL4) = 안정적이지만 느림 / 하이브리드(Windows NT, XNU) = 절충안. 이번 단계 프로젝트에서 구현할 RTOS는 마이크로커널에 가까운 설계를 따른다.
멀티코어 스케줄링 — 여러 CPU를 하나처럼 쓰기
1단계에서 우리는 단일 CPU가 컨텍스트 스위칭(Context Switching)을 통해 여러 프로세스를 동시에 실행하는 것처럼 보이게 만든다는 걸 배웠다. 이제 CPU가 1개가 아니라 16개, 128개라면? 문제는 더 복잡해지는 게 아니라 질적으로 달라진다.
**SMP(Symmetric Multiprocessing)**는 모든 코어가 동등하게 같은 메모리를 공유하는 구조다. 현재 대부분의 데스크톱, 서버 CPU가 여기에 해당한다. 이 구조에서 스케줄러는 각 코어에 어떤 스레드를 배정할지 결정해야 한다. 단순히 "놀고 있는 코어에 스레드를 던지면 되지 않나?" 하고 생각할 수 있지만, 여기서 1단계에서 배운 캐시 개념이 다시 등장한다. 스레드가 특정 코어에서 실행되다가 다른 코어로 이동하면 **캐시 미스(Cache Miss)**가 폭발적으로 발생한다. 이전 코어의 L1/L2 캐시에 쌓인 데이터가 쓸모없어지기 때문이다. 이것을 캐시 친화성(Cache Affinity) 문제라고 한다. 따라서 좋은 스케줄러는 가능하면 스레드를 같은 코어에 계속 배정하려 한다.
Linux의 현재 기본 스케줄러인 **CFS(Completely Fair Scheduler)**는 이 문제를 "가상 런타임(Virtual Runtime, vruntime)"이라는 개념으로 해결한다. 각 스레드가 실제로 CPU를 사용한 시간을 추적하고, 가장 적게 사용한 스레드에게 우선권을 준다. 자료구조로는 **레드-블랙 트리(Red-Black Tree)**를 사용해 O(log n) 시간에 다음 실행할 스레드를 찾는다. "공평하게"라는 개념이 단순한 라운드 로빈(Round Robin)과 다른 점은, 입출력이 잦아 CPU를 적게 쓰는 인터랙티브 프로세스(예: 마우스 커서)가 자연스럽게 높은 우선순위를 가지게 된다는 것이다.
그런데 멀티코어 환경에서는 더 심각한 문제가 있다. 코어 A가 메모리의 특정 위치를 수정하는 동안, 코어 B의 캐시에는 그 위치의 과거 데이터가 남아있을 수 있다. 이를 캐시 일관성(Cache Coherence) 문제라고 한다. 이를 해결하기 위해 CPU들은 **MESI 프로토콜(Modified-Exclusive-Shared-Invalid)**이라는 하드웨어 프로토콜을 사용한다. 각 캐시 라인(Cache Line)에 네 가지 상태 중 하나를 붙여 관리하는 방식인데, 이 프로토콜 덕분에 우리는 멀티코어 프로그래밍에서 데이터 일관성을 하드웨어가 어느 정도 보장해준다는 사실을 믿고 코드를 짤 수 있다. 단, 이 프로토콜은 "어느 정도"일 뿐이고, volatile 키워드나 메모리 펜스(Memory Fence)가 필요한 상황도 여전히 존재한다.
**NUMA(Non-Uniform Memory Access)**는 코어 수가 수십~수백 개가 되는 서버 CPU에서 등장하는 개념이다. 모든 코어가 하나의 메모리에 동등하게 접근하는 SMP와 달리, NUMA는 각 코어 그룹이 로컬 메모리를 가지고 있고 원격 메모리 접근은 더 느리다. AMD EPYC 프로세서가 대표적인 NUMA 아키텍처를 채용한다. NUMA를 모르고 짠 코드는 "왜 코어 수를 두 배 늘렸는데 성능이 오히려 떨어지지?"라는 기이한 현상을 맞이하게 된다.
[노트 기록] 멀티코어 스케줄링 핵심 개념: CFS(vruntime + 레드-블랙 트리) / 캐시 친화성(Cache Affinity) / MESI 캐시 일관성 프로토콜 / NUMA(로컬 vs 원격 메모리). CFS의 시간 복잡도는 O(log n)임을 기억.
가상 메모리 — 실제로 없는 메모리를 만들어내는 마법
왜 가상 메모리가 필요한가
지금 이 순간 당신의 컴퓨터에서 Chrome, Discord, IDE, 터미널이 동시에 열려있다고 하자. 각 프로그램은 자신이 마치 혼자 메모리를 전부 쓰고 있는 것처럼 행동한다. Chrome은 0x00400000 주소에 있는 데이터를 읽는다. Discord도 0x00400000 주소를 쓴다. 이 둘이 충돌하지 않는 이유는 뭘까?
답은 이 주소가 **가상 주소(Virtual Address)**이기 때문이다. 프로세스가 보는 주소와 실제 RAM에 존재하는 **물리 주소(Physical Address)**는 다르다. 운영체제는 각 프로세스에게 독립된 가상 주소 공간을 제공하고, 실제 접근 시에 **MMU(Memory Management Unit)**라는 하드웨어가 가상 주소를 물리 주소로 변환해준다.
이 변환 정보를 담은 자료구조가 **페이지 테이블(Page Table)**이다. 메모리는 보통 4KB 단위의 **페이지(Page)**로 나뉘고, 페이지 테이블은 가상 페이지 번호(VPN, Virtual Page Number)와 물리 프레임 번호(PFN, Physical Frame Number)의 매핑 테이블이다. 64비트 시스템에서는 이 테이블이 너무 커지기 때문에 **다단계 페이지 테이블(Multi-level Page Table)**을 사용한다. Linux는 4단계(PGD→PUD→PMD→PTE), 최신 시스템은 5단계를 사용한다. 그런데 페이지 테이블도 결국 메모리에 있다. 그렇다면 메모리 접근 시마다 페이지 테이블을 읽는 오버헤드가 생기지 않을까? 그래서 MMU 안에는 **TLB(Translation Lookaside Buffer)**라는 캐시가 있다. 최근에 변환한 VPN→PFN 매핑을 캐시에 보관해두고, TLB 히트(TLB Hit) 시에는 메모리를 추가로 참조하지 않아도 된다. TLB 크기는 보통 수십~수백 엔트리에 불과하지만, 프로그램의 지역성(Locality) 덕분에 히트율이 95% 이상이 되는 경우가 많다. 이 지역성은 1단계에서 캐시 최적화를 설명할 때도 등장했던 개념이다.
[노트 기록] 가상 메모리 핵심 구조: 가상 주소 → (MMU + TLB) → 물리 주소. TLB 미스 → 페이지 테이블 워크(Page Table Walk). 페이지 크기 = 보통 4KB. 64비트 리눅스는 4단계 페이지 테이블.
페이지 폴트와 디스크의 관계
가상 메모리의 진짜 마법은 여기서 시작된다. 페이지 테이블에는 각 페이지가 현재 물리 RAM에 있는지, 아니면 디스크에 있는지를 나타내는 **유효 비트(Valid Bit)**가 있다. 프로세스가 디스크에 있는 페이지에 접근하면 MMU가 **페이지 폴트(Page Fault)**라는 예외(Exception)를 발생시킨다. 그러면 커널이 제어권을 받아 해당 페이지를 디스크에서 RAM으로 불러오고, 페이지 테이블을 업데이트한 다음, 프로세스를 재시작시킨다. 이 과정을 **디맨드 페이징(Demand Paging)**이라고 한다.
그런데 RAM도 유한하다. RAM이 가득 찼는데 새 페이지를 불러와야 한다면? 기존 페이지 중 하나를 내보내야(Evict) 한다. 어떤 페이지를 내보낼 것인가를 결정하는 알고리즘이 바로 **페이지 교체 정책(Page Replacement Policy)**이다.
페이지 교체 알고리즘들
**OPT(Optimal, 또는 Belady's Algorithm)**는 미래를 알 수 있다면 어떻게 해야 최적인가를 보여주는 이론적 알고리즘이다. 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보낸다. 현실에서는 미래를 알 수 없으므로 구현이 불가능하지만, 다른 알고리즘의 성능을 평가하는 **기준선(Baseline)**으로 사용한다. "내 알고리즘이 OPT 대비 몇 % 효율이냐?"처럼.
**FIFO(First-In, First-Out)**는 가장 먼저 올라온 페이지를 내보낸다. 구현은 매우 쉽지만, Belady's Anomaly라는 황당한 현상이 발생한다. 프레임 수를 늘렸는데 오히려 페이지 폴트가 더 많이 발생하는 역설이다. 이것이 반직관적인 이유를 스스로 생각해보길 바란다.
**LRU(Least Recently Used)**는 가장 오랫동안 사용되지 않은 페이지를 내보낸다. OPT의 "미래 기반"과 반대로 "과거 기반"으로 근사한다. 지역성(Locality) 가정에서 오랫동안 안 쓴 페이지는 앞으로도 안 쓸 것이라는 논리다. 성능은 좋지만 완전한 LRU 구현은 모든 메모리 접근에 타임스탬프를 기록해야 해서 오버헤드가 크다. 그래서 현실에서는 LRU를 근사하는 알고리즘을 쓴다.
**Clock 알고리즘(또는 Second Chance Algorithm)**은 순환 큐(Circular Queue)와 참조 비트(Reference Bit)를 사용해 LRU를 근사한다. 포인터가 시계처럼 돌면서 참조 비트가 0인 페이지를 내보내되, 1인 경우 0으로 바꾸고 지나쳐 두 번째 기회를 준다. Linux의 실제 메모리 관리는 이 Clock 알고리즘의 변형인 Two-List LRU를 사용한다.
[노트 기록] 페이지 교체 알고리즘 비교: OPT(이상적, 미래 기반, 구현 불가) → LRU(최선 근사, 과거 기반) → Clock(LRU 근사, 실용적) → FIFO(단순, Belady's Anomaly 존재). 실제 Linux = Two-List LRU (Active/Inactive List).
**쓰래싱(Thrashing)**은 이 모든 메커니즘이 깨지는 상황이다. 너무 많은 프로세스가 동시에 실행되어 각 프로세스가 충분한 페이지를 RAM에 올리지 못하면, 계속 페이지 폴트가 발생하고 디스크 I/O에 CPU가 대부분의 시간을 쓰게 된다. CPU 사용률(CPU Utilization)이 갑자기 100%에서 10%로 떨어지면서 시스템이 사실상 멈춘 것처럼 느껴지는 현상이다. Denning(1968)의 **워킹셋 모델(Working Set Model)**은 각 프로세스가 실제로 자주 참조하는 페이지들의 집합(Working Set)을 RAM에 보장해줘야 쓰래싱을 막을 수 있다고 설명한다. 이 개념은 Peter Denning의 고전 논문 "The Working Set Model for Program Behavior"(1968, Communications of the ACM)에서 처음 제안되었다.
하드웨어 가속기 — CPU가 못 하는 일을 대신하는 존재들
CPU의 한계: 왜 GPU가 필요한가
자, 이제 발상의 전환이 필요하다. CPU는 범용 프로세서다. 복잡한 조건 분기, 순차적 의존성이 있는 연산, 운영체제 관리, I/O 처리 등 온갖 일을 잘 한다. 그러나 딥러닝 모델의 순전파(Forward Pass)를 생각해보자. 행렬 곱셈(Matrix Multiplication) 하나가 수십억 번의 곱셈-덧셈 연산이다. 이 연산들은 서로 **독립적(Independent)**이다. A행렬의 1번 행과 B행렬의 1번 열의 곱은 2번 행과 2번 열의 곱의 결과를 기다릴 필요가 없다.
CPU의 코어는 보통 8개에서 많아도 수십 개다. 각 코어는 강력하지만 독립적인 연산을 수십억 개 동시에 처리하기엔 수가 너무 적다. **GPU(Graphics Processing Unit)**는 이 문제를 완전히 다른 방식으로 해결한다. 수천 개의 단순한 코어를 가진다. NVIDIA H100 기준으로 CUDA 코어가 14,592개다. 각 코어는 CPU 코어보다 훨씬 단순하지만, 동일한 연산을 동시에 수천 개 처리할 수 있다.
GPU 아키텍처의 내부 구조
GPU의 계층 구조를 이해하는 것이 핵심이다. NVIDIA GPU 기준으로 설명하면, GPU 전체는 여러 개의 **SM(Streaming Multiprocessor, 스트리밍 멀티프로세서)**으로 구성된다. H100에는 132개의 SM이 있다. 각 SM은 독립적인 실행 단위로, 자체적인 레지스터 파일, L1 캐시, 공유 메모리(Shared Memory)를 가진다.
SM 내부에서는 스레드들이 **워프(Warp)**라는 단위로 실행된다. 워프는 32개의 스레드 묶음이다. 여기서 핵심적인 개념이 등장한다. **SIMT(Single Instruction, Multiple Threads)**다. 하나의 워프 안 32개 스레드는 동시에 동일한 명령어를 실행한다. 단, 각자 다른 데이터에 대해서. 이것이 1단계 때 CPU에서 배운 SIMD(Single Instruction, Multiple Data)와 유사하면서도 다른 점이다. SIMT는 스레드마다 독립적인 프로그램 카운터(PC)를 가지므로 분기(Branch)가 가능하지만, 같은 워프 안 스레드들이 서로 다른 분기를 따라가면 Warp Divergence가 발생해 직렬화(Serialize)된다. 즉, GPU 성능을 제대로 뽑으려면 같은 워프의 스레드들이 가능한 한 동일한 코드 경로를 따라가야 한다.
소프트웨어 관점에서 프로그래머는 CUDA(Compute Unified Device Architecture) API를 통해 커널(GPU에서 실행되는 함수를 커널이라고 부른다 — 운영체제의 커널과 같은 단어지만 완전히 다른 의미다)을 실행할 때 Grid → Block → Thread의 3단계 계층으로 스레드를 조직한다. Grid는 Block들의 배열, Block은 Thread들의 배열이다. Block 안의 스레드들은 같은 SM에서 실행되며 **공유 메모리(Shared Memory, 48KB228KB)**를 통해 빠르게 데이터를 주고받을 수 있다. 서로 다른 Block끼리는 **글로벌 메모리(Global Memory, 수십 GB VRAM)**를 통해 통신하는데, 이것은 수백 사이클의 레이턴시가 발생한다.
[노트 기록] GPU 계층 구조: Grid > Block > Warp(32 threads) > Thread. SM이 Warp를 실행. 메모리: 레지스터(fastest) > 공유 메모리(Shared, 수백 사이클) > 글로벌 메모리(VRAM, 수백천 사이클). SIMT = 워프 내 동일 명령어, 다른 데이터. Warp Divergence 발생 시 직렬화!
NPU 아키텍처 — AI에 특화된 더 극단적인 설계
GPU도 범용적이긴 하다. 렌더링도 하고, 연산도 하고, 비트코인 채굴도 한다. **NPU(Neural Processing Unit)**는 더 극단적이다. "오직 딥러닝 연산만 빠르게"를 목표로 설계된다. 애플 실리콘의 Neural Engine, 구글의 TPU(Tensor Processing Unit), 삼성의 Exynos NPU가 여기에 속한다.
NPU의 핵심 구조는 **시스톨릭 어레이(Systolic Array)**다. 이 개념은 1982년 H.T. Kung과 C.E. Leiserson의 논문에서 등장했다. 시스톨릭 어레이는 MAC 유닛(Multiply-Accumulate Unit) — 즉 곱하고 더하는 회로 — 이 격자 형태로 배열된 구조다. 데이터가 이 격자를 물처럼 흘러다니면서 자연스럽게 행렬 곱셈이 수행된다. 데이터 재로드 없이 연속적으로 연산이 이루어지므로 메모리 대역폭(Memory Bandwidth) 요구량이 GPU보다 훨씬 낮다.
구글의 TPU v3는 시스톨릭 어레이 기반으로 128×128 = 16,384개의 MAC 유닛을 가진다. 이것이 한 클럭에 동시에 실행된다는 것은, 이론적으로 클럭당 32,768번의 연산(각 MAC은 곱셈 한 번 + 덧셈 한 번)이 가능하다는 의미다.
그러나 NPU의 약점도 있다. 행렬 곱셈, Convolution처럼 규칙적인 연산은 폭발적으로 빠르지만, 불규칙한 연산, 복잡한 분기가 있는 연산은 GPU보다 오히려 느릴 수 있다. 이것이 "Task의 특성에 맞는 연산 유닛을 선택해야 한다"는 3단계 이기종 컴퓨팅(Heterogeneous Computing)의 핵심 철학으로 이어진다. 이 주제는 3단계에서 다시 만날 것이다.
[노트 기록] GPU vs NPU 비교: GPU = SIMT, 범용 병렬(수천 코어, Warp 기반) / NPU = 시스톨릭 어레이, AI 특화(MAC 유닛 격자, 규칙적 연산 최적). GPU는 유연성, NPU는 효율성. 실제 스마트폰 SoC(Apple A시리즈, Snapdragon)는 CPU+GPU+NPU를 동시에 탑재한 이기종 설계.
프로젝트 — 스스로 생각해볼 시간
아래 세 프로젝트는 이 단계에서 배운 내용을 실제로 손으로 구현하거나 분석하면서 체화하는 과정이다. 정답을 주지 않는다. 막히는 부분이 생기면 바로 "어떻게 해야 해요?"를 묻기보다 먼저 30분 정도 직접 부딪혀보고, 그다음에 힌트를 요청하길 권한다. 진짜 이해는 막혀서 고민한 흔적에서 나온다.
프로젝트 1: 우선순위 선점형 스케줄러 시뮬레이터
배경: RTOS(Real-Time Operating System)의 핵심은 정해진 데드라인(Deadline) 안에 태스크를 반드시 완료하는 것이다. 산업용 로봇 팔, ABS 브레이크, 드론 제어기가 모두 RTOS 위에서 돌아간다. 이들에서 데드라인 미스는 시스템 오작동으로 이어진다.
구현 목표: Python(또는 C)으로 선점형 스케줄러(Preemptive Scheduler)를 시뮬레이션하라.
문제: 다음 5개의 태스크가 있다. 각 태스크는 (태스크명, 도착 시간, 실행 시간, 우선순위, 데드라인)으로 정의된다.
T1: 도착=0, 실행=5, 우선순위=3, 데드라인=10
T2: 도착=1, 실행=3, 우선순위=1, 데드라인=5
T3: 도착=2, 실행=8, 우선순위=2, 데드라인=15
T4: 도착=4, 실행=2, 우선순위=1, 데드라인=8
T5: 도착=6, 실행=4, 우선순위=2, 데드라인=12
우선순위 숫자가 낮을수록 높은 우선순위다(1이 가장 높음).
먼저 EDF(Earliest Deadline First) 알고리즘으로 시뮬레이션하라. EDF는 현재 실행 가능한 태스크 중 데드라인이 가장 이른 것을 먼저 실행한다. 새 태스크가 도착할 때마다 현재 실행 중인 태스크가 선점(Preemption)될 수 있다.
다음으로 **고정 우선순위 선점 스케줄링(Fixed-Priority Preemptive Scheduling)**으로 같은 태스크 집합을 시뮬레이션하라.
두 알고리즘의 실행 타임라인(Gantt Chart 형식), 데드라인 미스 여부, 평균 대기 시간(Average Waiting Time), 평균 반환 시간(Average Turnaround Time)을 비교하라. 두 결과가 다르다면 왜 다른지, 어느 상황에서 어떤 알고리즘이 더 유리한지 분석하라. 또한 컨텍스트 스위치(Context Switch)가 발생하는 시점을 모두 표시하고, 만약 컨텍스트 스위치에 1 단위의 오버헤드가 있다면 결과가 어떻게 달라지는지도 계산하라.
심화 질문: 태스크 집합이 CPU를 100% 이상 요구하는 상황(Over-utilization)에서 EDF와 Fixed-Priority는 각각 어떻게 다르게 실패하는가? Liu & Layland(1973)의 스케줄러빌리티 테스트(Schedulability Test)를 찾아보고, 위 태스크 집합이 스케줄 가능한지(Schedulable) 판별하라.
프로젝트 2: 페이지 교체 정책 시뮬레이터 및 Belady's Anomaly 재현
배경: 운영체제의 메모리 관리 서브시스템(Memory Management Subsystem)은 페이지 교체 정책에 따라 같은 워크로드에서 수십 배 다른 성능을 낼 수 있다.
구현 목표: FIFO, LRU, Clock, OPT 네 가지 알고리즘을 구현하고 비교하라.
문제: 다음 페이지 참조 스트링(Page Reference String)이 주어진다.
참조 스트링 A: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
참조 스트링 B: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
각 알고리즘을 구현하되, 프레임 수(Frame Count)를 1부터 7까지 변화시키면서 각 경우의 **페이지 폴트 수(Number of Page Faults)**를 계산하라. 결과를 표와 그래프(프레임 수 vs 페이지 폴트 수)로 시각화하라.
FIFO 알고리즘에서 프레임 수를 늘렸을 때 페이지 폴트가 오히려 증가하는 Belady's Anomaly를 직접 재현하고, 어느 프레임 수 구간에서 이 현상이 발생하는지 명확히 표시하라. LRU에서는 이 현상이 발생하지 않는 이유를 수학적으로(스택 속성, Stack Property를 이용하여) 설명하라.
Clock 알고리즘의 경우 참조 비트(Reference Bit)가 어떻게 변화하는지를 타임스탬프와 함께 상세히 추적하라. 포인터의 위치와 각 페이지의 참조 비트 상태를 매 참조마다 출력하라.
심화 질문: 현실의 Linux 커널은 순수 LRU 대신 Active/Inactive 두 리스트를 사용하는 Two-List LRU를 채용한다. 순수 LRU 대신 이 방식을 선택하는 이유는 무엇인가? "파일 캐시(File Cache)"와 "익명 메모리(Anonymous Memory, 힙/스택)"를 다르게 처리해야 하는 이유와 연결하여 서술하라.
프로젝트 3: CUDA 커널 최적화 분석 — 행렬 곱셈
배경: 딥러닝의 핵심 연산인 행렬 곱셈(GEMM, General Matrix Multiply)을 GPU 위에서 어떻게 최적화하는지 이해하는 것은, GPU 아키텍처를 진정으로 이해하는 척도다.
구현 목표: 세 가지 버전의 행렬 곱셈 CUDA 커널을 작성하고 성능을 비교 분석하라. (CUDA 환경이 없다면 CUDA 코드를 작성하되 이론적 분석을 병행하라.)
문제: N×N 행렬 두 개를 곱하는 코드를 세 버전으로 구현하고, N = 256, 512, 1024, 2048에 대해 실행 시간을 측정하라.
버전 1 — Naive 구현: 각 출력 원소 C[i][j]를 한 스레드가 담당하며, 모든 데이터를 글로벌 메모리(Global Memory)에서 직접 읽는다. 이 구현에서 같은 데이터가 몇 번 글로벌 메모리에서 읽히는지 수식으로 계산하라.
버전 2 — Shared Memory 타일링(Tiling) 최적화: TILE_SIZE × TILE_SIZE 크기의 타일로 나눠 공유 메모리(Shared Memory)를 활용하라. TILE_SIZE = 16으로 시작하되, 32로 변경했을 때 성능 변화를 측정하라. Shared Memory를 사용함으로써 글로벌 메모리 접근 횟수가 이론적으로 얼마나 줄어드는지 계산하라.
버전 3 — 추가 최적화: 레지스터 재사용, 루프 언롤링(Loop Unrolling), 또는 뱅크 충돌(Bank Conflict) 방지 등 하나 이상의 추가 최적화를 스스로 선택하여 적용하라. 왜 그 최적화를 선택했는지, 이론적으로 어느 정도의 개선을 기대하는지 먼저 계산하고 실측과 비교하라.
각 버전에 대해 **산술 강도(Arithmetic Intensity, FLOP/Byte)**를 계산하라. 이것이 Roofline Model과 어떻게 연결되는지 설명하고, 당신의 구현이 메모리 대역폭 한계(Memory Bound)인지 연산 한계(Compute Bound)인지 분석하라.
심화 질문: NVIDIA cuBLAS 라이브러리의 GEMM 성능과 당신의 구현을 비교하면 얼마나 차이가 나는가? 그 차이의 원인을 Warp Occupancy, 메모리 접근 패턴, Tensor Core 활용 여부의 관점에서 설명하라.
마무리 — 세 가지 질문을 하나로 묶으면
이 단계에서 배운 세 가지 — 커널, 가상 메모리, 하드웨어 가속기 — 는 사실 하나의 공통된 주제를 다루고 있다. "제한된 자원을 어떻게 효율적으로 추상화하고 분배할 것인가." 커널은 CPU와 메모리를 추상화하고, 가상 메모리는 물리적 RAM의 한계를 추상화하며, GPU와 NPU는 수천 개의 단순 연산 유닛을 하나의 강력한 추상화로 감싼다. 3단계에서 배울 컨테이너, 하이퍼바이저, 이기종 컴퓨팅 오케스트레이션은 이 추상화들을 한 단계 더 쌓는 작업이다. 지금 배운 내용이 탄탄할수록 다음 단계가 쉬워진다. 프로젝트를 통해 실제로 숫자가 움직이는 모습을 확인하면서 이 개념들을 자기 것으로 만들길 바란다.