운영체제 심화: 스케줄링과 가상 메모리

컴퓨터 기초 트랙의 운영체제 강의를 한 층 더 파고들어요. 리눅스가 nice 값마다 가중치를 두고 가상 실행 시간이 가장 적은 작업에 CPU를 주는 공정 스케줄링을 흉내 내서 75 대 25의 몫을 확인하고, 시간 조각이 너무 짧으면 문맥 교환에 시간을 빼앗기는 이유를 계산해요. 48비트 주소를 네 단계로 나누는 페이지 테이블이 한 장짜리 512GB 표 대신 32KB로 끝나는 원리, TLB와 큰 페이지, 메모리가 한 칸 모자랄 때 페이지 부재가 1%에서 100%로 뛰는 스래싱 절벽, 시스템 호출을 모아 써야 빠른 이유까지 다뤄요.

고급강의 2 / 6약 12분

컴퓨터 기초 트랙의 운영체제 강의에서 CPU를 돌아가며 나눠 주는 스케줄링과, 메모리가 모자랄 때 페이지를 내보내는 FIFO와 LRU를 시뮬레이션해 봤어요. 이번 강의는 그 위에서 한 층 더 들어가요. 실제 리눅스는 CPU를 어떤 기준으로 나누는지, 가상 주소는 정확히 어떻게 실제 주소로 바뀌는지, 메모리가 조금 모자랄 때 왜 컴퓨터가 갑자기 멈춘 듯 느려지는지, 프로그램이 운영체제에 일을 부탁하는 비용은 얼마나 되는지를 숫자로 따져 봐요.

공정하게 나누기: 가중치와 가상 실행 시간

선착순과 돌아가며 나누기는 모든 작업을 똑같이 대했어요. 하지만 실제로는 "이 백업은 천천히 해도 돼" 같은 차이가 있어요. 리눅스는 작업마다 nice 값(-20에서 19까지, 클수록 남에게 잘 양보하는 착한 작업)을 두고, 값마다 가중치를 정해요. 그리고 작업마다 가상 실행 시간을 쌓아요. 실제로 CPU를 쓴 시간을 가중치에 맞게 줄이거나 늘려 더하는데, 가중치가 큰 작업일수록 가상 시간이 천천히 흘러요. 스케줄러는 늘 가상 실행 시간이 가장 적은 작업에게 CPU를 줘요. 2007년부터 쓰인 CFS가 이 방식이고, 2023년 리눅스 6.6부터 쓰는 EEVDF도 가중치와 가상 시간이라는 바탕은 같아요.

WEIGHT = {0: 1024, 5: 335, -5: 3121}                 # 리눅스가 nice 값마다 쓰는 가중치(일부)

def fair_share(tasks, ticks=10_000):                 # 늘 '가상 실행 시간'이 가장 적은 작업에 1틱을 줘요
    vruntime = {name: 0.0 for name in tasks}
    ran = {name: 0 for name in tasks}
    for _ in range(ticks):
        name = min(vruntime, key=vruntime.get)
        ran[name] += 1
        vruntime[name] += 1024 / WEIGHT[tasks[name]]  # 가중치가 클수록 가상 시간이 천천히 흘러요
    return {name: f"{ran[name] / ticks:.1%}" for name in tasks}

print("둘 다 nice 0:", fair_share({"압축": 0, "인코딩": 0}))
print("nice 0과 nice 5:", fair_share({"압축": 0, "인코딩": 5}))
print("nice -5와 nice 0:", fair_share({"압축": -5, "인코딩": 0}))
둘 다 nice 0: {'압축': '50.0%', '인코딩': '50.0%'}
nice 0과 nice 5: {'압축': '75.3%', '인코딩': '24.6%'}
nice -5와 nice 0: {'압축': '75.3%', '인코딩': '24.7%'}

가중치가 같으면 정확히 반반이에요. nice 0(가중치 1024)과 nice 5(가중치 335)는 약 3배 차이라 75 대 25로 나뉘어요. nice -5와 0도 같은 비율이에요. 리눅스는 nice가 1 차이 날 때마다 CPU 몫이 10%쯤 달라지도록 가중치를 대략 1.25배씩 잡아서, 몇 단계 차이인지만으로 비율이 정해져요. 터미널에서 nice -n 10을 앞에 붙여 무거운 명령을 실행하면 화면이 덜 버벅이는 이유예요.

이 방식은 오래 쉬다 깨어난 작업에도 자연스럽게 유리해요. 키보드 입력을 기다리며 대부분 잠들어 있는 편집기는 가상 실행 시간이 적게 쌓여서, 깨어나는 순간 곧바로 CPU를 받아요. 그래서 무거운 작업이 돌아도 입력에 반응이 빨라요. 실제로는 깨어난 작업이 너무 앞서 나가지 않도록 가상 시간을 조정해 줘요.

너무 자주 바꾸면 손해: 문맥 교환 비용

작업을 바꿀 때마다 운영체제는 지금 작업의 레지스터와 상태를 저장하고 다음 작업의 것을 불러와요. 이게 문맥 교환이에요. 교환 자체는 수 마이크로초면 끝나지만, 진짜 비용은 그다음이에요. 새 작업은 캐시에 자기 데이터가 없어서 한동안 느리게 달려요(컴퓨터 구조 강의). 한 번에 주는 시간 조각이 짧을수록 반응은 빨라지지만, 교환에 쓰는 비율이 커져요.

switch_us = 5                                        # 문맥 교환 한 번에 5마이크로초가 든다고 치면
for slice_us in (10, 100, 1_000, 10_000):
    overhead = switch_us / (slice_us + switch_us)
    print(f"한 번에 {slice_us:>6,}마이크로초씩 주면: 교환에 쓰는 시간 {overhead:.2%}")
한 번에     10마이크로초씩 주면: 교환에 쓰는 시간 33.33%
한 번에    100마이크로초씩 주면: 교환에 쓰는 시간 4.76%
한 번에  1,000마이크로초씩 주면: 교환에 쓰는 시간 0.50%
한 번에 10,000마이크로초씩 주면: 교환에 쓰는 시간 0.05%

10마이크로초씩 잘라 주면 시간의 3분의 1을 교환에 써요. 1밀리초씩이면 0.5%예요. 그래서 운영체제는 반응 속도와 처리량 사이에서 밀리초 단위의 조각을 골라요. 같은 이유로 스레드를 수천 개 만들어 놓고 서로 바꿔 가며 돌리는 설계는 생각보다 느려요. 동시성 강의에서 비동기 방식이 나오는 배경이에요.

가상 주소를 실제 주소로: 4단계 페이지 테이블

가상 메모리는 가상 주소를 4KB 페이지 단위로 실제 메모리에 대응시켜요. 주소의 아래 12비트(2의 12제곱은 4,096)는 페이지 안의 위치이고, 나머지가 페이지 번호예요. 64비트 CPU도 실제로는 주소를 48비트만 쓰는 경우가 많아서 페이지 번호는 36비트예요. x86-64는 이 36비트를 9비트씩 네 조각으로 나눠 표를 네 단계로 둬요. 첫 조각으로 1단계 표에서 2단계 표의 위치를 찾고, 둘째 조각으로 2단계 표에서 3단계 표를 찾는 식이에요. 표 한 장은 항목 512개(2의 9제곱) × 8바이트 = 4KB, 딱 한 페이지예요.

def split(vaddr):                                    # x86-64: 48비트 주소 = 9 + 9 + 9 + 9비트 번호 + 12비트 위치
    offset = vaddr & 0xFFF
    idx = [(vaddr >> shift) & 0x1FF for shift in (39, 30, 21, 12)]
    return idx, offset

vaddr = 0x7F3A_1C2B_5E17
idx, offset = split(vaddr)
print(f"가상 주소 {vaddr:#x} → 단계별 번호 {idx}, 페이지 안 위치 {offset:#x}")

flat = 2**36 * 8                                     # 한 장짜리 표라면: 페이지 2의 36제곱 개 × 항목 8바이트
print(f"한 장짜리 페이지 표: {flat / 2**30:,.0f}GB (프로세스마다!)")

used_pages = [0x0040_0000, 0x0040_1000, 0x0060_0000, 0x7FFF_F000_0000, 0x7FFF_F000_1000]
tables = set()
for page in used_pages:                              # 실제로 쓰는 페이지에 필요한 표만 만들어요
    i = split(page)[0]
    tables |= {("1단계",), ("2단계", i[0]), ("3단계", i[0], i[1]), ("4단계", i[0], i[1], i[2])}
print(f"페이지 {len(used_pages)}개를 쓰는 프로세스: 표 {len(tables)}장 × 4KB = {len(tables) * 4}KB")
가상 주소 0x7f3a1c2b5e17 → 단계별 번호 [254, 232, 225, 181], 페이지 안 위치 0xe17
한 장짜리 페이지 표: 512GB (프로세스마다!)
페이지 5개를 쓰는 프로세스: 표 8장 × 4KB = 32KB

페이지마다 한 줄씩 적는 한 장짜리 표라면 프로세스마다 512GB가 필요해요. 하지만 실제 프로세스는 넓은 주소 공간의 아주 일부만 써요. 코드와 데이터는 아래쪽에, 스택은 위쪽 끝에 몰려 있고 그 사이는 텅 비어 있어요. 네 단계로 나누면 쓰는 부분의 표만 만들면 되니, 페이지 5개를 쓰는 프로세스는 표 8장, 32KB로 끝나요. 알고리즘 트랙의 트리가 빈 곳을 통째로 건너뛰게 해 주는 거예요.

  • TLB: 주소를 바꿀 때마다 표를 네 번 읽으면 메모리 읽기가 다섯 배로 늘어요. 그래서 CPU는 최근에 바꾼 결과를 TLB라는 작은 캐시에 둬요. 프로그램이 자주 쓰는 페이지가 TLB에 다 들어가면 바꾸는 비용은 거의 없어요.
  • 큰 페이지: 메모리를 아주 많이 쓰는 데이터베이스나 가상 머신은 2MB짜리 큰 페이지를 쓰기도 해요. 페이지가 512배 넓으니 TLB 한 칸이 맡는 범위도 512배 넓어져요.
  • 요구 페이징: 프로그램이 메모리를 달라고 하면 운영체제는 표에 "빌려줬다"고만 적고, 실제 메모리는 처음 쓰는 순간에 붙여 줘요. 아직 붙지 않은 페이지를 건드리면 페이지 부재가 나고 운영체제가 끼어들어 처리해요.
  • 쓰기 시 복사: 리눅스에서 프로세스를 복제하는 fork는 메모리를 바로 복사하지 않고, 부모와 자식이 같은 페이지를 함께 보다가 누군가 쓰려는 순간에만 그 페이지를 복사해요. 큰 프로그램도 fork가 순식간인 이유예요.

한 칸 차이의 절벽: 스래싱

메모리가 조금 모자라면 조금만 느려질까요? 페이지 10개를 차례로 계속 도는 프로그램을 LRU로 관리해 볼게요.

from collections import OrderedDict

def fault_rate(refs, frames):                        # LRU로 페이지를 관리할 때 페이지 부재 비율
    memory, faults = OrderedDict(), 0
    for page in refs:
        if page in memory:
            memory.move_to_end(page)
        else:
            faults += 1
            memory[page] = True
            if len(memory) > frames:
                memory.popitem(last=False)
    return faults / len(refs)

refs = list(range(10)) * 100                         # 페이지 10개를 차례로 계속 도는 프로그램
for frames in (8, 9, 10, 11):
    print(f"메모리 {frames}칸: 페이지 부재 {fault_rate(refs, frames):.1%}")
메모리 8칸: 페이지 부재 100.0%
메모리 9칸: 페이지 부재 100.0%
메모리 10칸: 페이지 부재 1.0%
메모리 11칸: 페이지 부재 1.0%

메모리가 10칸이면 처음 10번만 부재가 나고 끝이에요(1%). 그런데 한 칸만 모자라도 100%가 돼요. LRU는 가장 오래 안 쓴 페이지를 내보내는데, 차례로 도는 패턴에서는 그게 바로 다음에 쓸 페이지거든요. 컴퓨터 구조 강의에서 열을 따라 읽을 때 캐시 적중률이 0%가 된 것과 같은 모양이에요.

프로그램이 자주 쓰는 페이지들을 작업 집합이라고 해요. 작업 집합이 메모리에 다 들어가지 않으면, 컴퓨터는 계산보다 디스크와 페이지를 주고받는 데 시간을 다 써요. 이걸 스래싱이라고 해요. 메모리가 꽉 찬 컴퓨터가 마우스조차 버벅이며 멈춘 듯 느려지는 현상이에요. 대처는 이래요.

  • 작업 집합을 줄여요. 데이터를 한꺼번에 다 올리지 말고 나눠서 처리해요.
  • 동시에 도는 프로그램 수를 줄여요.
  • 리눅스는 메모리가 정말 바닥나면 OOM 킬러가 메모리를 많이 쓰는 프로세스를 골라 강제로 끝내요. 서버에서 프로세스가 이유 없이 사라졌다면 dmesg로 OOM 기록부터 확인해요.

운영체제에 부탁하는 비용: 시스템 호출

파일 쓰기, 네트워크로 보내기, 메모리 받기처럼 하드웨어를 건드리는 일은 프로그램이 직접 하지 못하고 시스템 호출로 운영체제에 부탁해요(컴퓨터 기초 트랙). 이때 CPU는 사용자 모드에서 커널 모드로 넘어갔다가 돌아오는데, 이 왕복은 일반 함수 호출보다 훨씬 비싸요. 로그 10만 줄을 줄마다 직접 쓰는 것과 모아서 쓰는 것을 비교해 볼게요.

import os
import tempfile
import time

def write_lines(path, buffering):
    start = time.perf_counter()
    with open(path, "wb", buffering=buffering) as f:
        for i in range(100_000):
            f.write(b"log line\n")                    # buffering=0이면 줄마다 운영체제에 직접 부탁해요
    return time.perf_counter() - start

with tempfile.TemporaryDirectory() as tmp:
    path = os.path.join(tmp, "log.txt")
    direct = write_lines(path, buffering=0)
    buffered = write_lines(path, buffering=-1)       # 기본값: 모아 두었다가 한꺼번에 써요
    print("모아서 쓰는 쪽이 5배 넘게 빠른가요?", direct / buffered > 5)
모아서 쓰는 쪽이 5배 넘게 빠른가요? True

buffering=0이면 줄마다 시스템 호출을 해서 커널을 10만 번 오가요. 기본값은 메모리의 버퍼에 모아 두었다가 차면 한 번에 써서 호출 횟수가 크게 줄어요. 이 컴퓨터에서는 20배 넘게 차이 났어요. 데이터베이스가 쓰기를 모아서 처리하고, 네트워크 프로그램이 작은 조각을 묶어 보내는 것도 같은 이유예요. 대신 모아 둔 동안 프로그램이 죽으면 그 부분은 사라질 수 있어요. 꼭 남아야 하는 기록은 flush()로 운영체제에 넘기고, os.fsync()로 디스크까지 내려보내요.

실습

  1. fair_share에 세 작업(nice 0, 0, 10)을 넣어 몫을 구해 보세요. nice 10의 가중치는 110이에요.
  2. fair_share에 "10틱 중 1틱만 일하고 나머지는 잠드는" 작업을 더해 보세요. 이 작업은 깨어났을 때 얼마나 빨리 CPU를 받나요?
  3. 캐시를 다시 채우는 시간까지 쳐서 문맥 교환 한 번에 50마이크로초가 든다면, 교환에 쓰는 비율이 1% 아래가 되려면 시간 조각이 얼마 이상이어야 할까요?
  4. split으로 주소 0x0000_7FFF_FFFF_F000의 단계별 번호를 구해 보고, 2MB 큰 페이지라면 주소를 어떻게 나눠야 할지 생각해 보세요.
  5. fault_rate에서 페이지 10개를 차례로 도는 대신 무작위로 고르게 하면, 9칸일 때 부재율이 어떻게 달라지나요? 왜 그럴까요?

자주 하는 오해

  • nice 값을 낮추면 프로그램이 빨라진다. 다른 작업과 CPU를 다툴 때 몫이 커질 뿐, CPU가 놀고 있으면 차이가 없어요.
  • 메모리가 조금 모자라면 조금 느려진다. 작업 집합이 들어가지 않는 순간 절벽처럼 느려질 수 있어요.
  • 스왑이 있으면 메모리가 늘어난 것과 같다. 디스크는 메모리보다 수천 배 느려서, 잠깐 버티는 용도예요.
  • 스레드를 많이 만들수록 빠르다. 문맥 교환과 캐시 비용 때문에 코어 수를 크게 넘으면 오히려 느려져요.
  • write를 부르면 바로 디스크에 저장된다. 프로그램의 버퍼와 운영체제의 캐시를 거쳐요. 꼭 남겨야 하면 flush와 fsync를 써요.

점검 문제

  1. 리눅스의 공정 스케줄러는 다음에 실행할 작업을 어떻게 고르나요?
  2. nice 0과 nice 5 작업이 CPU를 75 대 25로 나누는 이유는?
  3. 시간 조각을 아주 짧게 하면 생기는 문제는?
  4. 48비트 주소 공간에서 한 장짜리 페이지 표가 비현실적인 이유와, 4단계 표가 이를 해결하는 방법은?
  5. TLB는 무엇이고, 큰 페이지가 TLB에 도움이 되는 이유는?
  6. 요구 페이징과 쓰기 시 복사는 각각 무엇인가요?
  7. 메모리가 한 칸만 모자라도 페이지 부재가 100%가 될 수 있는 이유는?
  8. 로그를 줄마다 직접 쓰면 느린 이유와, 모아서 쓸 때 조심할 점은?

정답

  1. 작업마다 실제 실행 시간을 가중치에 맞게 줄이거나 늘린 가상 실행 시간을 쌓고, 늘 그 값이 가장 적은 작업에게 CPU를 줘요.
  2. nice 0의 가중치는 1024, nice 5는 335라서 약 3배 차이가 나요. 가중치가 큰 쪽의 가상 시간이 3배 천천히 흐르니 CPU를 3배 더 받아요.
  3. 작업을 바꿀 때마다 상태를 저장하고 불러오는 비용과 캐시가 식는 비용이 드는데, 조각이 짧을수록 이 비용이 차지하는 비율이 커져서 처리량이 떨어져요.
  4. 페이지 번호가 36비트라 한 줄씩 적으면 프로세스마다 512GB의 표가 필요해요. 네 단계로 나누면 실제로 쓰는 부분의 표만 만들면 되니, 대부분 비어 있는 주소 공간을 아주 작은 표로 나타낼 수 있어요.
  5. 최근에 바꾼 가상 주소와 실제 주소의 대응을 담아 두는 CPU 안의 작은 캐시예요. 큰 페이지는 한 칸이 맡는 범위가 넓어서, 같은 TLB로 훨씬 넓은 메모리를 바로 바꿀 수 있어요.
  6. 요구 페이징은 메모리를 달라고 할 때가 아니라 처음 쓰는 순간에 실제 메모리를 붙여 주는 방식이에요. 쓰기 시 복사는 복제한 프로세스들이 같은 페이지를 함께 보다가, 누군가 쓰려고 할 때만 그 페이지를 복사하는 방식이에요.
  7. 차례로 도는 패턴에서는 LRU가 내보내는 "가장 오래 안 쓴 페이지"가 바로 다음에 쓸 페이지라서, 작업 집합보다 한 칸만 작아도 매번 부재가 나요.
  8. 줄마다 시스템 호출을 해서 사용자 모드와 커널 모드를 계속 오가기 때문이에요. 모아서 쓰면 빠르지만, 모아 둔 동안 프로그램이 죽으면 그 부분이 사라질 수 있으니 중요한 기록은 flush와 fsync로 내려보내요.

다음 강의

운영체제가 프로그램을 실행시켜 준다면, 그 프로그램은 어디서 왔을까요? 다음 강의에서는 사람이 쓴 코드를 기계가 실행할 수 있는 형태로 바꾸는 컴파일러와 인터프리터를 다뤄요. 이론 트랙의 파서에 이어, 파이썬 코드가 바이트코드로 바뀌어 실행되는 과정을 들여다보고 작은 컴파일러를 직접 만들어 봐요.