메인 메모리와 페이징 — 주소 변환, 단편화, TLB

1. 메모리를 나눠 쓰기

앞 글까지는 프로세서를 여럿이 어떻게 나눠 쓰는지 봤습니다. 이제 또 하나의 큰 자원, 메모리입니다. 3편에서 프로세스마다 자기만의 주소 공간이 있는 것처럼 보인다고 했고, 그 착각은 나중에 운영체제가 만든다고 했습니다. 이 글이 그 나중입니다. 여러 프로세스가 메모리 하나를 나눠 쓰면서도 서로의 영역을 건드리지 못하게 하는 방법, 그리고 메모리를 빈틈없이 쓰는 방법을 봅니다.

프로세서가 직접 읽고 쓸 수 있는 저장소는 레지스터와 메인 메모리뿐입니다. 디스크의 프로그램은 먼저 메모리로 올라와야 실행됩니다. 메모리 쪽에서 보면 들어오는 것은 주소와 읽기 요청, 또는 주소와 데이터와 쓰기 요청의 흐름뿐입니다. 레지스터는 프로세서 한 박자 안에 읽히지만 메모리는 여러 박자가 걸립니다. 그래서 1편에서 본 캐시가 그 사이에 있습니다. 그리고 여러 프로세스가 함께 쓰니, 한 프로세스가 다른 프로세스나 운영체제의 영역을 건드리지 못하게 막는 장치가 반드시 필요합니다.

2. 기준과 한계로 영역 지키기

가장 단순한 보호 장치는 레지스터 두 개입니다. 기준 레지스터에는 그 프로세스 영역이 시작하는 주소를, 한계 레지스터에는 영역의 크기를 넣습니다. 하드웨어가 프로세스의 주소를 하나하나 이 둘과 견줍니다. 기준 이상이고 기준 더하기 한계보다 작으면 통과시키고, 벗어나면 트랩을 일으켜 운영체제에 넘깁니다. 이 두 레지스터의 값은 특권 명령으로만 바꿀 수 있습니다. 그래야 프로세스가 스스로 영역을 넓히지 못합니다.

3. 주소는 두 가지입니다

프로세서가 실행하면서 만들어 내는 주소를 논리 주소, 또는 가상 주소라고 합니다. 메모리가 실제로 받는 주소를 물리 주소라고 합니다. 둘 사이를 실행 중에 바꿔 주는 하드웨어가 메모리 관리 장치입니다. 영어 약자로 MMU라고 씁니다.

가장 단순한 방식은 앞에서 본 기준 레지스터를 그대로 쓰는 것입니다. 이렇게 쓸 때는 재배치 레지스터라고 부릅니다. 프로세스가 낸 주소에 이 레지스터 값을 더해서 메모리로 보냅니다. 재배치 레지스터가 14000이고 프로세스가 346번지를 읽으면 실제로는 14346번지를 읽습니다. 프로세스는 자기가 346번지를 읽었다고 알 뿐, 실제 물리 주소는 끝내 보지 못합니다.

필요할 때만 올리고 필요할 때 잇기

프로그램 전체가 메모리에 다 올라와야 한다면 프로세스 크기는 메모리 크기를 넘을 수 없습니다. 그래서 필요한 부분만 올리는 방법을 씁니다. 동적 적재는 함수를 처음 부를 때에야 그 함수를 메모리에 올립니다. 한 번도 안 부르는 함수는 끝까지 안 올라오니 메모리가 절약됩니다. 동적 연결은 라이브러리를 잇는 일도 실행할 때로 미룹니다. 프로그램에는 라이브러리 자리에 작은 대리 코드만 넣어 두고, 처음 부를 때 그 대리 코드가 실제 라이브러리를 찾아 연결합니다. 그러면 여러 프로세스가 라이브러리 한 벌을 함께 쓰고, 라이브러리를 고쳐도 프로그램을 다시 만들 필요가 없습니다.

4. 연속 할당 — 한 덩어리씩 나눠 주기

초기의 방법은 연속 할당입니다. 메모리를 운영체제 영역과 사용자 영역으로 나누고, 프로세스마다 이어진 한 덩어리를 줍니다. 프로세스는 크기가 제각각이라 덩어리 크기도 그때그때 정합니다. 이것을 가변 분할이라고 합니다. 프로세스들이 들어오고 나가다 보면 메모리 곳곳에 빈 틈이 생깁니다. 이 빈 틈을 구멍이라고 부릅니다. 새 프로세스가 오면 들어갈 만큼 큰 구멍을 찾아 줍니다. 프로세스가 끝나면 그 자리가 구멍이 되고, 이웃 구멍과 붙어 있으면 하나로 합칩니다.

어느 구멍을 줄 것인가

• 최초 적합 — 처음부터 훑다가 맞는 첫 구멍에 넣습니다.
• 최적 적합 — 맞는 구멍 중 가장 작은 것에 넣습니다. 남는 조각이 가장 작습니다.
• 최악 적합 — 가장 큰 구멍에 넣습니다. 남는 조각이 가장 커서 나중에 다른 프로세스가 쓸 수 있으리라는 생각입니다.

실제로 재 보면 최초 적합과 최적 적합이 최악 적합보다 속도와 공간 모두에서 낫습니다. 둘 사이에서는 공간은 비슷하고 최초 적합이 대개 더 빠릅니다.

5. 조각나는 문제

연속 할당은 조각 문제를 피할 수 없습니다. 빈 공간을 다 더하면 충분한데, 여기저기 흩어져 있어서 한 덩어리로는 모자란 경우가 생깁니다. 이것을 외부 단편화라고 합니다. 최초 적합을 분석해 보면 할당된 덩어리가 N개일 때 0.5N개만큼이 조각으로 버려져, 메모리의 3분의 1 정도를 못 쓸 수 있습니다. 반대로 요청보다 조금 크게 떼어 주는 바람에 덩어리 안쪽에 남는 낭비도 있습니다. 이것은 내부 단편화라고 합니다.

외부 단편화는 프로세스들을 한쪽으로 몰아 구멍을 하나로 모으는 압축으로 풀 수 있지만 비용이 큽니다. 더 근본적인 해결은 프로세스의 메모리가 꼭 이어져 있지 않아도 되게 하는 것입니다.

6. 페이징 — 잘게 잘라 흩어 두기

그 방법이 페이징입니다. 물리 메모리를 같은 크기의 칸으로 자르고 프레임이라고 부릅니다. 프로세스의 논리 주소 공간도 같은 크기로 자르고 페이지라고 부릅니다. 페이지 하나는 아무 빈 프레임에나 들어갈 수 있습니다. 이어져 있을 필요가 없으니 외부 단편화가 사라집니다. 어느 페이지가 어느 프레임에 있는지는 프로세스마다 가진 페이지 테이블에 적어 둡니다. 운영체제는 어느 프레임이 비었는지 따로 목록으로 들고 있다가, 프로세스가 오면 필요한 수만큼 빈 프레임을 떼어 줍니다.

주소를 둘로 쪼개기

페이징에서 논리 주소는 두 부분으로 쪼개집니다. 앞부분은 페이지 번호, 뒷부분은 페이지 안에서의 위치인 오프셋입니다. 페이지 크기가 2의 n제곱 바이트이면 주소의 아래쪽 n비트가 오프셋이 됩니다. 변환은 이렇습니다. 페이지 번호로 페이지 테이블을 찾아 프레임 번호를 얻고, 프레임 번호에 페이지 크기를 곱한 값에 오프셋을 더합니다.

예를 봅니다. 페이지가 4바이트이고 물리 메모리가 32바이트, 곧 프레임이 여덟입니다. 페이지 테이블은 다음과 같습니다.

논리 주소 4는 4로 나누면 몫 1, 나머지 0이니 1번 페이지의 첫 칸입니다. 1번 페이지는 6번 프레임에 있으니 6 곱하기 4 더하기 0, 물리 주소 24가 됩니다.

7. 연습문제 1 — 주소 변환

같은 페이지 테이블, 같은 4바이트 페이지입니다. 논리 주소 13은 물리 주소 몇 번지로 바뀝니까. 페이지 번호와 오프셋을 먼저 구하고 답해 보십시오.

풀이

13을 4로 나누면 몫이 3, 나머지가 1입니다. 페이지 번호 3, 오프셋 1입니다. 이진수로 보면 13은 1101이고, 아래 두 비트 01이 오프셋, 위 두 비트 11이 페이지 번호 3입니다. 페이지 테이블에서 3번 페이지를 찾으면 2번 프레임입니다. 2번 프레임의 시작은 2 곱하기 4, 곧 8번지입니다. 여기에 오프셋 1을 더하면 9입니다. 답은 물리 주소 9입니다.

논리 주소에서는 뒤쪽이던 13이 물리 메모리에서는 앞쪽 9에 있습니다. 페이지는 이렇게 순서와 상관없이 흩어져 있어도 됩니다.

페이징에도 낭비는 있습니다

페이징은 외부 단편화를 없애지만 내부 단편화는 남습니다. 프로세스 크기가 페이지 크기로 딱 나누어떨어지지 않으면 마지막 페이지가 덜 찹니다. 페이지가 2048바이트이고 프로세스가 72766바이트라고 해 봅니다. 페이지 35개를 꽉 채우고 1086바이트가 남습니다. 그래서 페이지가 모두 36개 필요하고, 마지막 페이지에는 962바이트가 비어 낭비됩니다. 버려지는 양은 가장 나쁠 때 프레임 하나에서 1바이트를 뺀 만큼이고, 평균은 프레임 절반입니다. 페이지를 작게 하면 이 낭비가 줄지만, 페이지 수가 늘어 페이지 테이블이 커지고 디스크 입출력도 비효율적이 됩니다. 그래서 요즘 페이지는 보통 4킬로바이트나 8킬로바이트입니다.

8. TLB와 유효 접근 시간

페이지 테이블은 메모리에 있습니다. 그 위치는 페이지 테이블 기준 레지스터가 가리킵니다. 그러면 데이터 하나를 읽으려면 먼저 메모리에서 페이지 테이블을 읽어 프레임 번호를 얻고, 다시 메모리에서 데이터를 읽어야 합니다. 메모리에 두 번 가는 것입니다.

이것을 줄이려고 변환 색인 버퍼라는 작고 빠른 하드웨어 캐시를 둡니다. 영어 약자로 TLB라고 씁니다. 최근에 쓴 페이지 번호와 프레임 번호의 짝을 몇십에서 천 개쯤 들고 있습니다. 페이지 번호가 TLB에 있으면 바로 프레임 번호를 얻고, 없으면 메모리의 페이지 테이블을 보고 그 짝을 TLB에 넣어 둡니다.

TLB에서 찾는 비율을 적중률이라고 합니다. 메모리 한 번 가는 데 10나노초가 걸린다고 해 봅니다. TLB에서 찾으면 데이터만 읽으면 되니 10나노초, 못 찾으면 페이지 테이블과 데이터 두 번이니 20나노초입니다. 적중률이 80%이면 평균은 0.8 곱하기 10 더하기 0.2 곱하기 20, 곧 12나노초입니다. 페이징이 없을 때의 10나노초보다 20% 느립니다. 이 평균을 유효 접근 시간이라고 합니다.

9. 연습문제 2 — 적중률 99%

메모리 한 번에 10나노초, TLB에서 찾으면 10나노초, 못 찾으면 20나노초라는 조건은 그대로입니다. 적중률이 99%로 올라가면 유효 접근 시간은 몇 나노초이고, 페이징이 없을 때보다 몇 퍼센트 느립니까.

풀이

찾는 경우가 0.99, 못 찾는 경우가 0.01입니다. 0.99 곱하기 10은 9.9, 0.01 곱하기 20은 0.2입니다. 더하면 10.1나노초입니다. 페이징이 없을 때 10나노초였으니 1% 느립니다. 적중률이 80%에서 99%로 오르자 느려지는 정도가 20%에서 1%로 줄었습니다.

TLB가 몇십 개에서 천 개 남짓한 작은 캐시인데도 효과가 큰 까닭은, 프로그램이 짧은 시간 동안 같은 페이지를 되풀이해 쓰기 때문입니다. 1편에서 본 지역성입니다.

10. 페이지 단위로 지키고 나누기

페이징에서는 보호도 페이지 단위로 합니다. 페이지 테이블의 각 항목에 보호 비트를 붙여 읽기만 되는지, 쓰기도 되는지, 실행이 되는지 적습니다. 읽기 전용 페이지에 쓰려 하면 하드웨어가 트랩을 일으킵니다. 또 항목마다 유효 비트가 있습니다. 이 페이지가 프로세스의 주소 공간에 실제로 속하면 유효, 아니면 무효입니다. 무효인 페이지에 접근하면 막습니다.

반대로 페이지를 일부러 함께 쓸 수도 있습니다. 편집기나 컴파일러처럼 여러 사용자가 동시에 돌리는 프로그램의 코드는 읽기만 하니, 물리 메모리에 한 벌만 두고 여러 프로세스의 페이지 테이블이 같은 프레임을 가리키게 합니다. 데이터 페이지는 프로세스마다 따로 둡니다.

11. 페이지 테이블이 너무 클 때

페이지 테이블 자체가 문제가 되기도 합니다. 32비트 주소에 4킬로바이트 페이지면 페이지가 백만 개가 넘고, 항목 하나가 4바이트면 프로세스마다 페이지 테이블만 4메가바이트입니다. 이것을 한 덩어리로 이어서 둘 수는 없습니다. 해결책은 셋입니다.

• 계층 페이징 — 페이지 테이블도 페이지로 잘라, 바깥 테이블이 안쪽 테이블 조각을 가리키게 합니다. 쓰지 않는 영역의 조각은 만들 필요가 없습니다.
• 해시 페이지 테이블 — 페이지 번호를 정해진 계산식에 넣어 칸 하나를 고르고, 그 칸에 달린 짧은 목록만 뒤집니다.
• 역 페이지 테이블 — 프로세스마다 표를 두지 않고, 물리 프레임마다 항목을 하나씩 두어 시스템 전체에 표를 하나만 둡니다. 항목에는 어느 프로세스의 몇 번 페이지인지를 적습니다.

스와핑

지금까지는 프로세스가 통째로 메모리 안에 있다고 했습니다. 메모리가 모자라면 프로세스를 잠시 디스크로 내보냈다가 다시 들여올 수 있습니다. 이것을 스와핑이라고 합니다. 그러면 프로세스들의 메모리를 다 더한 것이 물리 메모리보다 커도 됩니다. 대가는 시간입니다. 100메가바이트짜리 프로세스를 초당 50메가바이트로 옮기면 내보내는 데 2초, 들여오는 데 2초, 모두 4초가 걸립니다. 프로세스를 통째로 옮기는 원래의 스와핑은 이렇게 너무 느려서 요즘 운영체제는 거의 쓰지 않습니다. 대신 프로세스 전체가 아니라 페이지 몇 개씩만 내보내고 들여옵니다.

정리

프로세스는 논리 주소를 쓰고, 메모리 관리 장치가 그것을 물리 주소로 바꿉니다. 기준과 한계 레지스터가 영역을 지킵니다. 연속 할당은 구멍 사이에 조각이 생기는 외부 단편화를 피하지 못합니다. 페이징은 메모리를 같은 크기 프레임으로 잘라 페이지를 흩어 두고, 페이지 번호와 오프셋으로 주소를 바꿉니다. 메모리에 두 번 가는 비용은 TLB가 줄이고, 적중률이 높으면 거의 느려지지 않습니다.

그런데 스와핑에서 페이지 몇 개씩만 옮긴다고 했습니다. 동적 적재처럼, 필요한 페이지만 메모리에 두어도 프로세스는 돌 수 있다는 뜻입니다. 다음 글에서는 그 생각, 가상 메모리를 봅니다.