PintOS: 메모리가 가득 찬 날

새 page를 올려야 하는데, 남은 frame이 없었다. Page는 프로그램이 쓰는 가상 메모리의 한 조각이고, frame은 그 조각이 실제 RAM에 머무는 자리다. 자리가 다 찼다면 누군가는 나가야 한다. 그렇게 지목되는 page가 victim이다.

문제는 단순해 보였지만, 두 개의 질문이 계속 따라붙었다. 어떤 page를 내보내야 손해가 가장 적은가. 그 하나를 찾자고 매번 전체 메모리를 뒤져야 하는가. 이번 설계는 이 두 질문에서 시작됐다.

한 자리를 비우는 일

내보내는 비용은 page마다 다르다. 파일에서 읽어 온 뒤 수정되지 않은 page는 그냥 버려도 된다. 원본이 그대로 있으니 다시 읽으면 그만이다. 수정된 file page는 버리기 전에 변경분을 파일에 되돌려 놓아야 한다. Stack이나 heap처럼 원본 파일 자체가 없는 anonymous page는 지금 내용을 통째로 swap disk에 보존해야 한다.

그러니 victim의 기준은 "가장 오래된 page"가 아니라 "지금 내보내고 나중에 되살리기 가장 싼 page"다. Page는 종류와 변경 여부에 따라 file clean, file dirty, anon, stack anon의 비용 등급으로 구분했다. Swap 공간이 얼마 남지 않았을 때는 anonymous page를 고르는 일에 한 번 더 신중해지도록 했다.

상태를 하나의 좌표에 놓다

Victim을 찾을 때마다 frame 구조체를 하나씩 열어 보는 방식은, 전체 메모리를 매번 다시 걷는 일이다. 한 자리를 비우는 값으로는 너무 비싸다. 그래서 모든 frame에 연속된 frame_id를 붙이고 배열에 앉혔다.

Page 주소 같은 상세 정보는 frame 구조체에 남는다. "사용 중인가", "고정되어 있는가", "file page인가"처럼 예와 아니오로 답이 끝나는 상태는 bitset에 따로 모았다. Frame 하나가 1bit, 그게 전부인 배열이다.

frame_table_by_id[17]  → 17번 frame의 상세 정보
occupied_bits[17]      → 현재 사용 중인가?
pinned_bits[17]        → 지금 이동시키면 안 되는가?
file_bits[17]          → file page를 담고 있는가?

배열에서든 bitset에서든, 같은 번호는 같은 frame이다. 구조체는 선택된 frame 하나를 깊이 읽고, bitset은 전체 frame에 같은 질문을 한꺼번에 던진다.

뜰채를 만들다

Bitset 한 장은 조건 하나다. 여러 장을 같은 위치에서 AND와 NOT으로 겹치면, 모든 조건을 통과한 frame만 1로 남는다.

  valid
& occupied
& ~pinned
& ~evicting
& ~shared
──────────────────
안전하게 선택할 수 있는 frame

pinned는 kernel이 작업 중이라 건드리면 안 되는 frame, evicting은 이미 다른 eviction이 처리 중인 frame이다. 여러 page가 함께 쓰는 frame도 일단 제외한다. 이 필수 조건을 지난 뒤에는 수정되지 않은 file page나 오래 접근되지 않은 page 쪽으로 그물을 좁힌다.

빠른 이유는 묶음에 있다. Frame 64개의 상태가 64bit word 하나로 묶여 논리 연산 한 번에 걸러진다. word cursor가 word들을 차례로 돌고, 각 word 안에서는 bit cursor가 지난번 멈춘 자리부터 후보를 찾는다. 선택이 한 구간에 몰리지 않도록 word마다 최대 2개까지만 걷어 올린다.

수집은 최대 32개에서 멈춘다. 다음 단계의 조회 비용을 묶어 두기 위한 상한이다. 32는 최적값이 아니라, 후보의 분산과 평가 비용 사이 어디쯤이 적당한지 관찰하려고 정해 둔 지금의 작업 예산이다.

마지막 순간에 다시 묻다

Bitset은 후보를 빠르게 좁혀 주지만, 어디까지나 힌트다. Page가 방금 접근되었는지, 내용이 바뀌었는지는 프로그램이 도는 동안 계속 달라진다. 그래서 이 판단만은 마지막까지 미뤄, 남은 후보에 대해서만 page table에서 직접 확인한다.

CPU는 page가 사용되면 page table의 accessed bit를, 내용이 바뀌면 dirty bit를 켠다. 확인 시점에 accessed가 켜져 있으면 그 page는 우선순위에서 뒤로 보내고 bit를 끈다. 다음 평가 때도 꺼져 있다면, 그제야 한동안 쓰이지 않았다고 믿을 근거가 생긴다.

Frame에는 평가된 횟수인 observation_count와, 접근 흔적 없이 지나간 연속 횟수인 cold_miss_count를 적어 둔다. 관찰이 쌓였고 "접근 없음"이 충분히 반복된 후보를 먼저 고르는 것이 strict 단계다. 그런 후보가 없고 당장 frame이 급하면, relaxed 단계가 접근 여부와 관찰 횟수, 저장 비용을 함께 놓고 기준을 내려놓는다.

선택 이후의 책임

Victim을 골랐다고 frame을 바로 덮어쓸 수는 없다. 표시, 보존, 차단, 분리를 거쳐야 재사용이다. 먼저 evicting bit를 켠다. Lock으로 직렬화된 eviction 경로 안에서, 이 표시가 같은 frame이 다시 후보로 잡히는 일을 막는다. 그다음 swap_out()이 page 종류에 맞는 보존을 맡는다. Anonymous page는 swap disk에 기록되고, 변경된 file page는 파일에 반영된다.

저장이 끝나면 pml4_clear_page()가 page table에서 기존 가상주소와 frame의 mapping을 지운다. 이제 그 주소로의 접근은 frame에 직접 닿지 못하고, page fault를 거쳐 kernel의 복구 경로로 돌아온다. 마지막으로 page와 frame 사이 참조를 끊으면, frame은 새 page의 자리가 된다.

이 과정은 trace log로 남겼다. 437번 후보가 어느 word에서 나왔는지, 접근 흔적은 없었는지, file clean 등급으로 victim이 되었는지. 정책이 의도대로 도는지는 코드가 아니라 이 기록으로 확인했다.

우아함의 유지비

Bitset 여러 장을 겹칠 때마다, 흩어져 있던 frame들이 하나의 후보 집합으로 모였다. 그 장면이 꽤 마음에 들었다. 문제는, 마음에 드는 설계일수록 유지비를 따져 봐야 한다는 것이다.

조밀한 상태 저장과 word 단위의 검사를 얻는 대가로, frame metadata 배열을 미리 확보해야 하고 구조체와 bitset이 어긋나지 않도록 상태가 바뀌는 모든 경로를 관리해야 한다. 힌트의 정확도와 전역 자료구조의 동기화도 이 설계가 떠안은 짐이다.

단순한 순차 탐색보다 정말 빠른지는 실제 workload와 benchmark 위에서만 답할 수 있다. 거르는 계산은 줄었지만, bitset을 갱신하는 비용과 걸러진 후보의 품질에 따라 결과는 얼마든지 뒤집힌다.

내가 얻은 것은 특정 자료구조가 언제나 우월하다는 결론이 아니었다. 문제를 반복되는 질문으로 바꾸고, 질문의 모양에 맞는 자료구조를 고르고, 그 선택이 데려온 효율과 복잡성을 같은 저울에 올려 보는 경험이었다. Bitset은 정답이 아니다. 반복해서 묻던 질문을, 코드의 모양으로 옮겨 적은 선택이었다.