가상 메모리 — 요구 페이징, 페이지 교체, 스래싱

1. 일부만 올려도 된다

앞 글은 페이지 몇 개씩만 옮기는 이야기로 끝났습니다. 필요한 페이지만 메모리에 두어도 프로세스가 돈다는 생각이었습니다. 정말 그럴까요. 프로그램 안을 들여다보면 거의 안 쓰는 부분이 많습니다. 오류가 났을 때만 도는 코드가 있습니다. 넉넉하게 잡아 두고 절반도 안 채우는 배열도 있습니다. 한 번 부를까 말까 한 함수도 있습니다. 이런 것까지 전부 메모리에 올려 둘 이유는 없습니다.

프로그램의 일부만 메모리에 두고 실행할 수 있다면 좋은 일이 셋 생깁니다.

1. 프로그램 크기가 물리 메모리 크기에 묶이지 않습니다.
2. 같은 메모리에 더 많은 프로그램을 올릴 수 있습니다.
3. 올리고 내리는 입출력도 줄어듭니다.

이것을 가능하게 하는 것이 가상 메모리입니다. 프로세스가 보는 메모리와 실제 물리 메모리를 떼어 놓는 방식입니다. 프로세스는 0번지에서 시작해 끝까지 이어진 넓은 주소 공간을 봅니다. 이것을 가상 주소 공간이라고 합니다. 실제로는 그중 일부 페이지만 물리 프레임에 흩어져 있고, 나머지는 디스크에 있습니다. 둘을 잇는 일은 메모리 관리 장치가 맡습니다. 그래서 가상 주소 공간은 물리 메모리보다 훨씬 커도 됩니다. 프로그래머는 메모리가 얼마 남았는지 신경 쓰지 않고 코드를 짤 수 있습니다. 주소 공간 가운데가 비어 있어도 괜찮습니다. 힙과 스택이 자라면서 그 빈 곳을 채우고, 그때 필요한 페이지만 새로 받습니다.

2. 요구 페이징과 페이지 부재

가상 메모리를 만드는 대표적인 방법이 요구 페이징입니다. 페이지를 미리 올리지 않고, 실행 중에 그 페이지를 실제로 쓰려는 순간에야 올리는 방식입니다. 그러려면 하드웨어가 어떤 페이지가 메모리에 있고 어떤 페이지가 디스크에 있는지 알아야 합니다. 여기에 앞 글에서 본 유효 비트를 씁니다. 앞 글에서는 주소 공간에 속하지 않는 페이지를 무효로 표시했습니다. 이제는 주소 공간에 속하지만 아직 메모리에 올라오지 않은 페이지도 무효로 표시합니다. 유효 페이지에 접근하면 평소처럼 진행합니다. 무효 페이지에 접근하면 하드웨어가 트랩을 일으킵니다. 이 트랩을 페이지 부재라고 합니다. 영어로는 페이지 폴트라고 부릅니다.

처리 순서

1. 운영체제가 따로 들고 있는 표를 봅니다. 그 주소가 애초에 이 프로세스 것이 아니면 프로세스를 끝냅니다. 주소는 맞는데 페이지가 아직 안 올라온 경우라면 올려 줍니다.
2. 빈 프레임을 하나 찾습니다.
3. 디스크에서 그 페이지를 읽어 빈 프레임에 넣습니다.
4. 페이지 테이블의 그 항목에 프레임 번호를 적고 유효로 바꿉니다.
5. 트랩을 일으킨 그 명령을 처음부터 다시 실행합니다. 이번에는 페이지가 메모리에 있으니 그대로 진행됩니다.

프로세스 입장에서는 명령 하나가 조금 오래 걸렸을 뿐입니다.

처음에는 아무것도 없이

극단적으로는 페이지를 하나도 올리지 않고 프로세스를 시작할 수도 있습니다. 첫 명령부터 페이지 부재가 나고, 이후 새 페이지를 처음 만질 때마다 부재가 납니다. 이것을 순수 요구 페이징이라고 합니다. 명령 하나가 페이지 여러 개를 건드리면 부재도 여러 번 날 수 있습니다. 메모리의 두 값을 더해 다시 메모리에 쓰는 명령이 그렇습니다. 명령 자체, 읽을 값 둘, 쓸 자리가 서로 다른 페이지일 수 있습니다. 그래도 실제로는 견딜 만합니다. 1편에서 본 지역성 덕분에 한번 올린 페이지를 한동안 계속 쓰기 때문입니다.

처리 순서에서 빈 프레임을 하나 찾는다고 했습니다. 그래서 운영체제는 빈 프레임 목록을 늘 들고 있습니다. 프레임을 내줄 때는 먼저 내용을 0으로 지웁니다. 앞서 쓰던 프로세스의 데이터가 새 프로세스에 보이면 안 되기 때문입니다.

3. 부재 한 번의 값

요구 페이징은 얼마나 느려질까요. 앞 글에서 유효 접근 시간을 TLB 적중률로 셈했습니다. 이번에는 페이지 부재가 날 확률로 셈합니다. 이 확률을 부재율이라고 하고 p로 씁니다.

부재가 안 나면 메모리 접근 한 번입니다. 여기서는 200나노초라고 합니다. 부재가 나면 디스크를 다녀와야 합니다. 트랩 처리와 재시작에 몇 마이크로초가 들고, 디스크에서 페이지를 읽는 데 8밀리초쯤 걸립니다. 8밀리초는 800만 나노초입니다. 유효 접근 시간은 두 경우의 시간에 각각의 확률을 곱해 더한 값입니다.

유효 접근 시간 = (1 − p) × 200 + p × 8,000,000  (나노초)

부재율이 천 번에 한 번이면 약 8200나노초, 곧 8.2마이크로초입니다. 부재가 없을 때보다 약 40배 느립니다. 부재가 아주 드물어도 한 번의 값이 워낙 커서 평균을 끌어올립니다.

4. 연습문제 1 — 부재율 10만 분의 1

조건은 방금과 같습니다. 메모리 접근은 200나노초, 부재 한 번을 처리하는 데는 8밀리초가 걸립니다. 부재율이 10만 번에 한 번으로 줄었다고 합시다. 유효 접근 시간은 몇 나노초입니까. 그리고 부재가 없을 때보다 몇 퍼센트 느립니까.

풀이

p는 10만 분의 1입니다. 부재가 안 나는 쪽부터 봅니다. 1 빼기 p에 200을 곱하면 200에서 0.002를 뺀 값이라 거의 200입니다. 부재가 나는 쪽은 800만을 10만으로 나눈 값, 80입니다. 더하면 약 280나노초입니다. 200나노초보다 80나노초가 늘었으니 40% 느립니다.

천 번에 한 번일 때 40배였던 것이 40%로 줄었습니다. 그래도 느린 편입니다. 느려지는 정도를 10% 안으로 묶으려면 늘어나는 몫이 20나노초를 넘지 않아야 합니다. 거꾸로 셈하면 부재율이 약 40만 번에 한 번보다 드물어야 합니다. 요구 페이징에서는 부재율을 낮게 유지하는 것이 성능을 거의 결정합니다.

5. 쓰기 시 복사

가상 메모리는 프로세스를 만드는 일도 빠르게 합니다. 3편에서 본 fork는 부모를 통째로 복사해 자식을 만듭니다. 그런데 자식은 대개 곧바로 다른 프로그램을 실행하니, 애써 복사한 페이지가 금방 버려집니다.

그래서 fork 직후에는 페이지를 복사하지 않습니다. 부모와 자식의 페이지 테이블이 같은 프레임을 가리키게 하고, 그 페이지들을 쓰기 금지로 표시해 둡니다. 둘 중 하나가 어떤 페이지에 쓰려고 할 때에야 그 페이지 하나만 복사합니다. 이것을 쓰기 시 복사라고 합니다. 영어 약자로 COW라고 씁니다. 예를 들어 P1과 자식이 페이지 A, B, C를 함께 가리키고 있습니다. P1이 C를 고치려 하면 C만 새 프레임에 복사되고, P1의 페이지 테이블이 그 복사본을 가리킵니다. A와 B는 계속 함께 씁니다.

6. 빈 프레임이 없으면 — FIFO 교체

프로세스가 늘어나면 언젠가 빈 프레임이 바닥납니다. 그때는 이미 메모리에 있는 페이지 하나를 골라 내보내고 그 자리를 씁니다. 이것을 페이지 교체라고 하고, 내보낼 페이지가 들어 있는 프레임을 희생 프레임이라고 합니다. 이렇게 되면 부재 한 번에 디스크를 두 번 다녀올 수 있습니다. 희생 프레임의 페이지를 디스크에 쓰고, 원하는 페이지를 읽어 와야 하기 때문입니다. 그래서 페이지마다 변경 비트를 둡니다. 더티 비트라고도 합니다. 메모리에 올라온 뒤 한 번이라도 고친 페이지면 1이 됩니다. 변경 비트가 0이면 디스크에 있는 것과 같으니 다시 쓸 필요 없이 그냥 덮어씁니다.

어느 페이지를 내보낼지 정하는 규칙을 페이지 교체 알고리즘이라고 합니다. 좋은 알고리즘은 부재를 적게 냅니다. 알고리즘을 비교할 때는 프로세스가 차례로 접근하는 페이지 번호를 나열해 씁니다. 이것을 참조열이라고 합니다.

첫 번째 알고리즘은 가장 먼저 들어온 페이지를 내보내는 방식입니다. 선입선출이라고 하고, 영어 약자로 FIFO라고 씁니다. 스무 개짜리 참조열을 봅니다. 앞부분은 7, 0, 1, 2, 0, 3, 0, 4이고 프레임은 셋입니다. 7, 0, 1이 들어와 세 칸이 찹니다. 2가 오면 가장 먼저 들어온 7을 내보냅니다. 다음 0은 이미 있으니 그냥 지나갑니다. 3이 오면 그다음으로 오래된 0을 내보냅니다. 그런데 바로 다음 참조가 0이라서 곧장 또 부재가 납니다. 이렇게 스무 번 참조하는 동안 부재가 15번 납니다. 구현은 쉽지만, 오래 있었다는 것과 앞으로 안 쓴다는 것은 별개입니다.

7. 연습문제 2 — FIFO 부재 세기

참조열은 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5입니다. 모두 열두 번 참조합니다. 프레임은 셋이고 처음에는 모두 비어 있습니다. FIFO로 교체하면 페이지 부재는 몇 번 납니까. 빈 프레임을 처음 채우는 것도 부재로 셉니다. 매번 프레임 세 칸에 무엇이 있는지 적어 가며 세 보십시오.

풀이

1, 2, 3이 들어오며 부재가 세 번입니다. 4가 오면 가장 오래된 1을 내보냅니다. 네 번째 부재입니다. 다음 1이 오면 이번엔 2를 내보내고, 다음 2가 오면 3을 내보냅니다. 여기까지 부재가 여섯 번입니다. 5가 오면 4를 내보내고 일곱 번째입니다. 이제 프레임에는 1, 2, 5가 있습니다. 이어지는 1과 2는 이미 있으니 부재가 없습니다. 3이 오면 가장 오래된 1을 내보내 여덟 번째, 4가 오면 2를 내보내 아홉 번째입니다. 마지막 5는 그대로 남아 있습니다. 답은 9번입니다.

1과 2를 내보내자마자 다시 부르는 모습이 보입니다. 가장 오래 있었던 페이지가 가장 많이 쓰이는 페이지일 수도 있습니다.

프레임을 늘렸는데 부재가 늘어난다

같은 참조열에 프레임을 넷으로 늘려 봅니다. 보통은 프레임이 많을수록 부재가 줄어든다고 기대합니다. 그런데 FIFO로 세어 보면 부재가 10번입니다. 프레임 셋일 때의 9번보다 오히려 많습니다. 프레임 수를 하나부터 늘려 가며 그래프를 그리면, 셋에서 넷으로 가는 구간에서만 선이 올라갑니다. 이렇게 프레임을 늘렸는데 부재가 늘어나는 현상을 벨레이디 이상이라고 합니다. 발견한 사람의 이름을 딴 것입니다. 메모리를 더 줬는데 더 느려질 수 있다는 뜻이니 곤란한 성질입니다. FIFO는 페이지가 얼마나 쓰이는지를 전혀 보지 않고 들어온 순서만 보기 때문에 이런 일이 생깁니다.

8. 최적 교체와 LRU

가장 좋은 답 — 최적 교체

부재가 가장 적은 규칙은 앞으로 가장 오랫동안 쓰이지 않을 페이지를 내보내는 것입니다. 이것을 최적 교체라고 합니다. 다시 스무 개짜리 참조열, 프레임 셋입니다. 7, 0, 1이 찬 뒤 2가 옵니다. 앞을 내다보면 0은 바로 다음에 쓰이고, 1은 한참 뒤에, 7은 가장 늦게 쓰입니다. 그래서 7을 내보냅니다. 이렇게 끝까지 가면 부재가 9번입니다. FIFO의 15번보다 훨씬 적고, 어떤 알고리즘도 이보다 적게 낼 수 없습니다. 문제는 앞으로의 참조를 미리 알아야 한다는 점입니다. 실제 운영체제는 미래를 모릅니다. 그래서 최적 교체는 직접 쓰지 않고, 다른 알고리즘이 얼마나 좋은지 재는 기준으로 씁니다.

과거로 미래를 짐작하기 — LRU

미래를 모르면 과거를 봅니다. 지역성 덕분에 최근에 참조한 페이지는 곧 다시 참조할 가능성이 큽니다. 그래서 가장 오랫동안 쓰이지 않은 페이지를 내보냅니다. 이것을 최근 최소 사용 교체라고 하고, 영어 약자로 LRU라고 씁니다. 같은 참조열에서 LRU는 부재가 12번입니다.

구현은 두 가지입니다. 페이지 테이블 항목마다 마지막으로 참조한 시각을 적어 두고 가장 오래된 것을 찾는 방법이 있습니다. 또는 페이지 번호를 쌓아 두고, 참조한 페이지를 맨 위로 옮기는 방법도 있습니다. 그러면 맨 아래가 곧 내보낼 페이지입니다.

LRU에는 벨레이디 이상이 생기지 않습니다. 프레임이 셋일 때 메모리에 있는 페이지는 프레임이 넷일 때에도 언제나 메모리에 있습니다. 프레임을 늘리면 들고 있는 페이지가 늘기만 할 뿐 빠지지 않으니 부재가 늘 수 없습니다. 프레임 수와 상관없이 이 성질을 가진 알고리즘을 스택 알고리즘이라고 합니다.

9. LRU를 흉내 내기 — 두 번째 기회

LRU는 좋지만 참조할 때마다 시각을 적거나 순서를 옮겨야 합니다. 이것을 제대로 지원하는 하드웨어는 드뭅니다. 대신 많은 하드웨어가 페이지마다 참조 비트를 줍니다. 처음에는 0이고, 페이지를 읽거나 쓰면 하드웨어가 1로 바꿉니다. 참조 비트로는 최근에 쓰였는지는 알지만 쓰인 순서는 모릅니다.

이것으로 LRU를 흉내 내는 대표적인 방법이 두 번째 기회 알고리즘입니다. 페이지들을 시계처럼 둥글게 놓고 바늘이 돌며 후보를 봅니다. 참조 비트가 0이면 그 페이지를 내보냅니다. 1이면 비트를 0으로 바꾸고 한 번 봐준 뒤 다음 페이지로 넘어갑니다. 한 바퀴 도는 동안 다시 쓰이지 않은 페이지가 결국 나갑니다. 여기에 변경 비트까지 함께 보면 더 낫습니다. 참조도 변경도 안 된 페이지를 먼저 내보내면 디스크에 쓰는 일까지 아낄 수 있습니다.

10. 프레임을 몇 개씩 줄 것인가

너무 적게 주면 부재가 잦아집니다. 적어도 명령 하나가 건드릴 수 있는 페이지를 모두 담을 만큼은 줘야 합니다. 그래야 그 명령이 끝까지 실행됩니다. 나누는 방법은 둘입니다. 균등 할당은 모두에게 똑같이 줍니다. 비례 할당은 프로세스 크기에 비례해 줍니다. 프레임이 62개이고, P1은 10페이지, P2는 127페이지라고 합시다. 둘을 합하면 137페이지입니다. 비례 할당이면 P1은 약 4개, P2는 약 57개를 받습니다.

교체할 때 어디서 희생 프레임을 고르는지도 둘로 나뉩니다. 전역 교체는 다른 프로세스의 프레임까지 후보로 삼습니다. 지역 교체는 자기 프레임 안에서만 고릅니다. 전역 교체가 메모리를 더 알뜰하게 써서 더 흔히 쓰입니다.

11. 스래싱과 작업 집합

프레임이 너무 모자라면 페이지를 올리려고 다른 페이지를 내보냈는데, 내보낸 페이지가 금방 다시 필요해집니다. 그걸 올리려고 또 하나를 내보냅니다. 프로세스가 실제 일은 못 하고 페이지를 넣고 빼는 데만 시간을 씁니다. 이 상태를 스래싱이라고 합니다.

여기서 악순환이 생깁니다. 모두가 디스크를 기다리니 프로세서가 놉니다. 이용률이 떨어집니다. 운영체제는 이용률이 낮으니 멀티프로그래밍을 더 하려고 메모리에 프로세스를 더 올립니다. 새 프로세스는 남의 프레임을 빼앗고, 부재는 더 늘고, 이용률은 더 떨어집니다. 막으려면 각 프로세스에 필요한 만큼 프레임을 줘야 합니다.

필요한 만큼은 얼마인가

답은 다시 지역성에 있습니다. 지역성을 페이지 단위로 보면 이렇습니다. 프로그램은 어느 한 시기에 몇몇 페이지를 집중해서 함께 씁니다. 함수 하나를 도는 동안에는 그 함수의 코드와 변수가 든 페이지들을 씁니다. 이렇게 함께 쓰이는 페이지 묶음을 지역이라고 하고, 실행하면서 지역이 옮겨 간다고 보는 것을 지역성 모델이라고 합니다.

지금의 지역을 재는 방법이 작업 집합입니다. 가장 최근 참조 몇 개 안에 나온 페이지들의 집합입니다. 몇 개를 볼지를 작업 집합 창이라고 합니다. 창을 참조 10개로 잡은 예에서, 첫 시점에는 1, 2, 5, 6, 7 다섯 페이지가 작업 집합이고, 뒤 시점에는 3과 4, 두 페이지뿐입니다.

프로세스는 작업 집합 크기만큼 프레임이 있으면 됩니다. 모든 프로세스의 작업 집합 크기를 더한 값이 전체 프레임보다 크면 스래싱이 납니다. 그때는 프로세스 하나를 통째로 내보내 나머지를 살립니다. 더 간단히 부재율만 볼 수도 있습니다. 이것을 페이지 부재 빈도 방식이라고 합니다. 부재율이 너무 높은 프로세스에는 프레임을 더 주고, 너무 낮은 프로세스에서는 하나 거둡니다.

정리

가상 메모리는 프로세스가 보는 주소 공간과 물리 메모리를 떼어 놓습니다. 요구 페이징은 쓰려는 순간에 페이지를 올리고, 없는 페이지를 건드리면 페이지 부재가 납니다. 부재 한 번은 메모리 접근보다 수만 배 느리니 부재율을 낮게 지켜야 합니다. 쓰기 시 복사는 고치는 페이지만 나중에 복사합니다. 프레임이 모자라면 페이지를 교체합니다. FIFO는 쉽지만 벨레이디 이상이 있습니다. 최적 교체는 기준이 되고, 실제로는 LRU와 그 근사를 씁니다. 프레임이 작업 집합보다 모자라면 스래싱이 납니다.

부재가 날 때마다 페이지를 디스크에서 읽어 왔습니다. 디스크에는 페이지 말고도 우리가 매일 쓰는 파일이 있습니다. 다음 글에서는 그 파일을 운영체제가 어떻게 이름 붙이고 보관하는지, 파일 시스템을 봅니다.