운영체제 핵심 기능 학습노트: CPU Scheduling·Virtual Memory·Storage

2023년 3월 26일에 정리한 운영체제 학습 메모를 다시 읽으며, CPU scheduling·virtual memory·storage를 자원을 공유하고 지연을 통제하는 운영체제의 세 가지 문제로 묶어 보강했다. 당시의 요약은 남기되, 특정 알고리즘을 항상 우수하다고 단정한 부분과 HDD 중심 설명은 현재 기준에 맞게 고쳤다.

운영체제가 맡는 일

운영체제는 application이 hardware를 안전하고 효율적으로 공유하도록 경계를 만든다.

• process와 thread의 생성·실행·종료
• CPU time 배분과 scheduling
• virtual address space와 physical memory 관리
• file system과 persistent storage 관리
• device·interrupt·I/O 처리
• protection, access control, isolation
• network stack과 resource accounting·observability

이 기능들은 따로 떨어져 있지 않다. page fault로 storage I/O가 발생하면 thread가 기다리고, scheduler는 그동안 다른 runnable task에 CPU를 줄 수 있다.

CPU Scheduling: 평균만 보지 않기

FCFS

FCFS(First-Come, First-Served)는 먼저 들어온 작업을 먼저 처리한다. 이해와 구현은 단순하지만 긴 CPU burst 뒤에 짧은 작업이 몰리면 convoy effect가 생길 수 있다. 그렇다고 FCFS가 모든 workload에서 항상 나쁘다는 뜻은 아니다. 순서의 예측 가능성과 구현 비용도 정책 선택 요소다.

SJF와 SRTF

SJF(Shortest Job First)는 다음 CPU burst가 가장 짧은 작업을 우선한다. burst 길이를 정확히 안다는 이상적 조건에서는 평균 waiting time을 줄일 수 있지만, 실제 시스템은 미래 burst를 미리 알 수 없어 history를 바탕으로 추정해야 한다.

SRTF(Shortest Remaining Time First)는 SJF의 preemptive variant다. 새로 온 짧은 작업이 현재 task보다 먼저 실행될 수 있다. 짧은 작업에 유리한 대신 긴 작업의 starvation 가능성이 있어 aging 같은 보완이 필요하다.

Round Robin

RR(Round Robin)은 runnable task에 time quantum을 돌아가며 준다. quantum이 지나면 timer interrupt 등을 계기로 preemption할 수 있다.

• quantum이 너무 크면 FCFS에 가까워져 interactive response가 나빠질 수 있다.
• 너무 작으면 context switch와 cache disruption 비중이 커질 수 있다.
• waiting time이 단순히 CPU 사용시간에 비례한다고 보장되지는 않는다.

FCFS·SJF·RR은 scheduling 원리를 배우는 좋은 모델이지만 현대 Linux의 일반 task scheduler를 단순 RR이라고 설명할 수는 없다. Linux kernel 문서는 6.6부터 CFS를 대체하는 방향으로 EEVDF 전환을 설명한다. production scheduler에는 fairness, latency, priority, topology 같은 조건이 함께 들어간다.

Virtual Memory: 큰 메모리처럼 보이는 것 이상

각 process는 독립된 virtual address space를 본다. CPU의 MMU와 operating system이 page table을 통해 virtual page를 physical frame에 mapping한다.

virtual memory가 제공하는 핵심은 다음과 같다.

• process 사이 address isolation
• page 단위 protection
• shared library와 shared memory mapping
• demand paging을 통한 필요한 page의 지연 loading
• physical memory보다 큰 working set을 다루기 위한 reclaim과 swap 가능성

“가상 메모리는 각 process의 독자적인 공간이고 swap은 RAM의 연장”이라는 요약만으로는 부족하다. file-backed page는 원본 file에서 다시 읽을 수 있지만, 수정된 anonymous page는 reclaim하려면 swap 같은 backing store가 필요할 수 있다. swap data가 전원 종료 때 의미 없이 자동 삭제된다고 일반화할 수도 없다. persistence와 encryption은 system 구성에 따라 다르다.

page fault도 모두 오류는 아니다. 아직 physical frame에 올라오지 않은 valid mapping에 처음 접근할 때 minor·major fault가 일어날 수 있다. invalid address 접근처럼 처리할 수 없는 fault는 process에 signal로 전달될 수 있다.

커널·system call·address space가 연결되는 흐름은 커널 내부 동작, CPU와 memory의 역할은 CPU와 메모리 기본 개념에서 이어서 볼 수 있다.

Page Replacement: LRU도 현실에서는 근사한다

memory pressure가 생겼을 때 운영체제는 어떤 page를 유지하고 reclaim할지 판단한다.

• LRU는 가장 오래 사용되지 않은 page를 내보낸다는 모델이다.
• LFU는 사용 횟수가 적은 page를 우선한다는 모델이다.
• working set은 일정 구간에 활발히 쓰인 page 집합에 주목한다.

정확한 LRU를 모든 memory access마다 유지하는 비용은 크다. 실제 operating system은 access bit, list, generation 같은 정보를 이용해 recency와 reclaim cost를 근사한다. dirty page, file-backed 여부, active working set, I/O 비용도 함께 고려한다.

Storage Scheduling: HDD와 SSD를 나눠 보기

HDD에서는 access time을 대략 seek time, rotational latency, transfer time으로 나눌 수 있다. 그래서 request 순서를 바꿔 head 이동을 줄이는 scheduling이 의미가 있었다.

• FCFS: 도착 순서대로 처리
• SSTF: 현재 head에서 가까운 request 우선, 먼 request starvation 가능
• SCAN: elevator처럼 한 방향으로 처리한 뒤 방향 전환

SSD와 NVMe에는 움직이는 head와 rotational latency가 없다. 대신 flash page·erase block, controller queue, parallel channel, garbage collection, wear leveling, write amplification을 봐야 한다. OS block layer도 multi-queue hardware를 활용해 여러 CPU와 device queue 사이 contention을 줄인다.

TRIM/discard는 file system이 더 이상 쓰지 않는 logical block 정보를 SSD에 전달할 수 있게 한다. 이것은 backup이나 replication 기능이 아니다. data durability는 storage medium, filesystem, controller, power-loss protection과 backup policy를 따로 확인해야 한다.

Caching과 저장장치 계층

register, CPU cache, DRAM, SSD, HDD처럼 가까운 계층은 일반적으로 빠르고 byte당 비용이 높으며 용량이 작다. 다만 “빠르면 항상 volatile, 느리면 항상 non-volatile”처럼 하나의 축으로만 외우면 새로운 persistent memory나 device 특성을 설명하기 어렵다.

caching은 빠른 계층에 재사용 가능성이 큰 data copy를 두는 전략이다. 확인할 질문은 네 가지다.

1. cache hit와 miss 비용은 얼마인가
2. 원본이 바뀌면 cached copy를 어떻게 무효화하는가
3. write-through와 write-back 중 무엇을 쓰는가
4. 장애 시 dirty data의 durability를 어디까지 보장하는가

다시 정리한 핵심

• scheduler는 throughput뿐 아니라 response time, fairness, starvation을 함께 다룬다.
• virtual memory의 중심은 address translation, isolation, protection, demand paging이다.
• page replacement algorithm은 실제 kernel에서 대개 근사와 여러 reclaim cost를 함께 사용한다.
• HDD scheduling 설명을 SSD·NVMe에 그대로 옮기지 않는다.
• storage 성능과 durability, backup은 서로 다른 문제다.

2023년의 메모는 용어를 나열하는 데 가까웠다. 이번 정리에서는 각 개념이 해결하는 문제와 적용 범위를 연결하는 데 초점을 맞췄다.

참고 자료

• Linux Kernel: EEVDF Scheduler
• Linux Kernel: Memory Management Concepts
• Linux Kernel: Multi-Queue Block IO Queueing Mechanism
• Operating Systems: Three Easy Pieces