요구 페이징과 페이지 교체 2

요구 페이징과 페이지 교체에서 본 교체 알고리즘을 실제로 쓸 때 부딪히는 문제를 이어서 다룬다. 메모리에 없는 페이지(page)에 접근하면 페이지 폴트(page fault)가 나고, 빈 페이지 프레임(page frame)이 없으면 페이지 하나를 골라 내보내야 한다. 가장 먼저 들어온 것을 내보내는 FIFO(First In First Out, 선입선출), 가장 오래 안 쓴 것을 내보내는 LRU(Least Recently Used, 최근 최소 사용), 앞으로 가장 오래 안 쓸 것을 내보내는 최적(OPT, optimal) 교체가 대표적이다. OPT는 미래의 참조를 미리 알아야 하므로 실제로는 구현할 수 없고, 다른 알고리즘이 얼마나 좋은지 재는 기준으로만 쓴다. 여기서는 FIFO에만 있는 역설, LRU를 싸게 흉내 내는 방법, 메모리가 너무 모자랄 때 시스템 전체가 느려지는 현상을 본다.

벨레이디의 모순

상식적으로는 프레임을 늘리면 폴트가 줄어야 한다. 그런데 FIFO에서는 프레임을 늘렸는데 폴트가 오히려 늘어나는 경우가 있고, 이를 벨레이디의 모순(Belady's anomaly)이라고 한다. 참조열(reference string) 1 2 3 4 1 2 5 1 2 3 4 5를 FIFO로 돌리면 프레임 3개일 때 폴트가 9번, 4개일 때 10번이다. LRU와 OPT에서는 같은 시점을 비교하면, 프레임이 n+1개일 때 메모리에 있는 페이지가 n개일 때의 페이지를 항상 모두 포함한다. 그래서 프레임이 적을 때 히트였던 참조는 프레임을 늘려도 계속 히트이고, 폴트가 늘어날 수 없다.

LRU의 비용과 클럭 알고리즘

진짜 LRU를 하려면 메모리 접근이 일어날 때마다 "언제 썼는지"를 갱신해야 한다. 접근은 명령어마다 일어나므로 소프트웨어로 매번 기록하기에는 너무 비싸다. 그래서 운영체제는 하드웨어가 공짜로 켜 주는 참조 비트(reference bit)만 보고 LRU를 흉내 낸다.

클럭 알고리즘(clock algorithm)은 프레임들을 시계 문자판처럼 둥글게 놓고, 시계 바늘이 가리키는 프레임부터 살핀다. 참조 비트가 1이면 최근에 쓴 페이지이므로 비트를 0으로 지우고 한 번 더 기회를 준 뒤 바늘을 옮긴다. 참조 비트가 0인 페이지를 만나면 그 페이지를 내보낸다. 한 번 봐준다는 뜻에서 두 번째 기회(second-chance) 알고리즘이라고도 부른다. 여기에 수정 비트(dirty bit)까지 봐서 디스크에 다시 쓸 필요가 없는 깨끗한 페이지를 먼저 내보내는 변형도 흔하다.

같은 고민은 운영체제 밖에도 있다. 데이터베이스는 디스크에서 읽은 페이지를 메모리에 캐시(cache)로 담아 두는 자기만의 버퍼 풀(buffer pool)을 두고, 여기서도 어떤 페이지를 남길지 고른다(버퍼 풀과 로그).

스래싱과 작업 집합

프로세스(process)를 너무 많이 올리면 각자 받는 프레임이 줄어든다. 자주 쓰는 페이지조차 메모리에 다 못 담으면, 내보낸 페이지를 곧바로 다시 부르는 폴트가 끝없이 이어진다. 이렇게 실제 계산보다 페이지를 넣고 빼는 데 시간을 대부분 쓰는 상태를 스래싱(thrashing)이라고 한다. 모든 프로세스가 디스크를 기다리므로 CPU 이용률이 뚝 떨어진다. 이때 운영체제가 "CPU가 논다"고 보고 프로세스를 더 올리면 상황은 더 나빠진다.

다이어그램 로딩…

처음에는 프로세스를 늘릴수록 한쪽이 입출력을 기다리는 동안 다른 쪽이 CPU를 써서 이용률이 오른다. 그러다 각자 받는 프레임이 자주 쓰는 페이지 수보다 작아지는 지점을 넘으면 폴트가 폭증해 이용률이 급락한다.

해결책은 프로세스마다 꼭 필요한 만큼의 프레임을 보장하는 것이다.

• 작업 집합(working set)은 최근 일정 구간 동안 프로세스가 실제로 참조한 페이지들의 모음이다. 모든 프로세스의 작업 집합을 합친 크기가 전체 프레임 수를 넘으면, 일부 프로세스를 통째로 멈추고 메모리에서 내보내 나머지가 작업 집합을 온전히 갖게 한다.
• 페이지 폴트 빈도(PFF, Page Fault Frequency) 방식은 폴트 비율을 직접 잰다. 비율이 상한을 넘으면 그 프로세스에 프레임을 더 주고, 하한 밑으로 내려가면 프레임을 거둬 다른 프로세스에 준다.

스와핑

스와핑(swapping)은 메모리가 모자랄 때 프로세스의 메모리를 디스크의 스왑 영역(swap space)으로 내보냈다가, 다시 필요할 때 들여오는 일이다. 원래는 프로세스 전체를 통째로 내보내는 것을 뜻했다. 요즘은 페이지 단위로 스왑 영역에 내보내는 것까지 흔히 스왑이라고 부른다. 서버에서 스왑 사용량이 계속 늘고 응답이 급격히 느려진다면 스래싱을 의심할 신호다.

면접 포인트

• "벨레이디의 모순은?" → FIFO에서 프레임을 늘렸는데 폴트가 늘어나는 현상. LRU·OPT에는 없다.
• "LRU를 왜 그대로 구현하지 않나요?" → 접근마다 순서를 갱신하는 비용이 너무 커서. 참조 비트를 쓰는 클럭 알고리즘으로 근사한다.
• "스래싱의 원인과 대책은?" → 작업 집합보다 적은 프레임 → 폴트 폭증·CPU 이용률 저하. 작업 집합·PFF로 프레임 보장, 동시에 올리는 프로세스 수 줄이기.
• "서버에서 스왑 사용량이 계속 늘고 응답이 느려지면?" → 스래싱을 의심한다. 스래싱 때 "CPU가 논다"고 프로세스를 더 올리면 악화된다.