[OS] 물리적 메모리 관리 - 연속 할당, 페이징(Paging) 기법
메모리 공간과 주소 바인딩
32비트 컴퓨터의 메모리 크기는 4GB
우리가 흔히 사용하는 컴퓨터는 32비트 또는 64비트 주소 체계를 사용하고 있다. 32비트 주소 체계를 사용한다는 의미는 메모리의 고유 위치를 나타내기 위해 위해 32비트(4바이트)가 사용되며, 총 2³²개의 고유한 주소를 가질 수 있다는 의미다. 또한, 32비트 컴퓨터의 CPU가 한 번에 처리할 수 있는 데이터 크기이며, 레지스터의 크기이기도 하다.
컴퓨터는 바이트 단위로 메모리 주소를 부여하기 때문에 32비트 주소 체계를 사용하게 된다면 최대 약 4GB의 메모리 크기를 가지게 된다. 여기서 직접 비트를 바이트로 환산하는 계산을 해보고 왜 4GB인 지 헷갈릴 수 있다.
- 2³² bit = 4,294,967,296 bit = 536,870,912 byte = 536MB(약 512MB)
따라서 512MB가 메모리 크기가 아닌가 하는 의문이 들 수 있다. 실제로 위 식은 맞는 계산이다. 다만, 유의해야 할 점이 있다. 32비트 주소 체계를 사용한다는 의미는 메모리 공간 하나가 32비트로 이루어져 있다는 말이 아니다. 메모리 공간 하나의 크기는 1바이트이고, 이 1바이트를 나타내기 위한 주소 크기가 32비트인 것이다.
메모리 공간과 주소 바인딩
32비트 컴퓨터의 메모리 크기는 4GB
우리가 흔히 사용하는 컴퓨터는 32비트 또는 64비트 주소 체계를 사용하고 있다. 32비트 주소 체계를 사용한다는 의미는 메모리의 고유 위치를 나타내기 위해 위해 32비트(4바이트)가 사용되며, 총 2³²개의 고유한 주소를 가질 수 있다는 의미다. 또한, 32비트 컴퓨터의 CPU가 한 번에 처리할 수 있는 데이터 크기이며, 레지스터의 크기이기도 하다.
컴퓨터는 바이트 단위로 메모리 주소를 부여하기 때문에 32비트 주소 체계를 사용하게 된다면 최대 약 4GB의 메모리 크기를 가지게 된다. 여기서 직접 비트를 바이트로 환산하는 계산을 해보고 왜 4GB인 지 헷갈릴 수 있다.
- 2³² bit = 4,294,967,296 bit = 536,870,912 byte = 536MB(약 512MB)
따라서 512MB가 메모리 크기가 아닌가 하는 의문이 들 수 있다. 실제로 위 식은 맞는 계산이다. 다만, 유의해야 할 점이 있다. 32비트 주소 체계를 사용한다는 의미는 메모리 공간 하나가 32비트로 이루어져 있다는 말이 아니다. 메모리 공간 하나의 크기는 1바이트이고, 이 1바이트를 나타내기 위한 주소 크기가 32비트인 것이다.
위 그림에서 Addr. 은 32비트 주소를 4바이트로 표현한 것이고, 오른쪽의 Bytes 는 주소 공간의 크기인 1바이트를 나타낸 것이다. 그림을 보고 왜 32비트 컴퓨터의 메모리 크기는 4GB인 지 다시 한 번 생각해 보면 이제 이해가 될 것이다.
주소 바인딩을 위한 MMU(Memory Management Unit)
여러 프로그램들이 동시에, 실시간으로 실행되는 환경에서 CPU 만큼이나 메모리 공간은 비싼 자원이다. 위에서 알아본 것처럼 생각보다 메모리 공간의 크기는 크지 않다. 그리고 프로세스는 다양한 이유에 의해 메모리에 올라갔다 내려갔다 하기도 한다. 때문에 프로그램이 실행을 위해 메모리에 적재되면 실제 메모리 주소가 아닌, 그 프로세스를 위한 독자적인 주소 공간이 생성된다. 이 주소가 논리적 주소(logical address) 또는 가상 주소(virtual address)다. 논리적 주소는 각 프로세스마다 독립적으로 할당되며 0번지부터 시작된다. 프로세스가 10개 있으면 논리적 주소도 10개가 생성되는 것이다.
반면, 물리적 주소(physical address)는 물리적 메모리(RAM)에 실제로 올라가는 위치를 말한다. 프로세스가 CPU에 의해 실행되기 위해서는 해당 프로그램이 물리적 메모리에 올라가 있어야 한다. 하지만 프로세스는 고유한 논리적 주소를 가지고 있기 때문에 CPU가 그 주소를 그대로 읽어 수행하면 예상한 명령어가 수행되지 않는다.
예를 들어 프로세스의 논리적 주소 100번지가 실제 메모리에는 500번지에 위치할 수도, 4,000,123번지에 위치할 수도 있으며, 실행 후 메모리 위치가 바뀔 수도 있다. 만약 CPU가 논리적 주소 100번지를 참조한다고 했을 때, 현재 CPU에서 수행되고 있는 프로세스가 무엇인지에 따라 이 100번지가 가리키는 내용은 상이해진다.
때문에 프로세스의 논리적 주소가 실제 물리적 메모리의 어느 위치에 올라가 있는지 알 필요가 있는데, 이를 주소 바인딩(address binding)이라고 한다. 주소 바인딩은 보통 실행시간 바인딩(rin time binding) 방식으로 이루어 지며, 논리적 주소를 물리적 주소로 매핑해주는 MMU(Memory Management Unit) 하드웨어 장치가 주 역할군이 된다. 이 MMU는 기준 레지스터와 한계 레지스터를 포함하고 있다.
- 기준 레지스터(base register) 또는 재배치 레지스터(relocation register): 프로세스의 물리적 메모리 시작 주소를 가지고 있음
- 한계 레지스터(limit register) : 프로세스가 자신의 주소 공간을 넘어서는 메모리 참조를 하려고 하는지 판단하기 위해 프로세스의 크기를 가지고 있음
CPU가 특정 프로세스의 논리적 주소를 참조하려고 할 때, 그 주소값에 기준 레지스터의 값을 더해 물리적 주소값을 얻어낼 수 있다.
- 논리적 주소 + 기준 레지스터 = 물리적 주소
그림을 보면, 346의 논리적 주소에 14000의 재배치 레지스터(기준 레지스터) 값을 더해 14346이라는 물리적 주소값으로 변환한다. 프로그램의 주소 공간이 물리적 메모리에 연속적으로 적재된다면, 물리적 메모리상의 시작 주소만 알면 주소 변환은 간단하다. 논리적 주소가 오프셋(offset) 개념처럼 동작하는 것이다. 이 원리로 인해 사용자 프로그램이나 CPU는 논리적 주소만 알아도 된다. 물리적 주소는 알 지도 못하고, 알 필요도 없다.
이때, 물리적 메모리 안에는 여러 개의 프로세스가 동시에 올라가 있기 때문에 다른 프로세스의 주소 공간을 침범할 가능성이 있다. 이런 상황을 방지하기 위해 한계 레지스터로 메모리 보안을 유지한다.
먼저 CPU가 요청한 논리적 주소값이 한계 레지스터 내의 저장된 프로세스의 크기보다 작은지 확인한다. 작다면 정상적으로 물리적 메모리 값을 구하겠지만, 만약 크다면 트랩을 발생시켜 해당 프로세스를 강제 종료시킨다.
물리적 메모리의 할당 방식
연속 할당(contiguous allocation) 기법
연속 할당 방식은 각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식이다. 이때 물리적 메모리를 고정된 크기로 미리 나누어 놓는지 그렇지 않은지에 따라 고정 분할 방식과 가변 분할 반식으로 나뉜다.
고정 분할
고정 분할 방식은 물리적 메모리를 주어진 개수 만큼의 영구적인 분할(partition)로 미리 나누어 두고, 각 분할에 하나의 프로세스를 적재한다. 이때 분할의 크기는 모두 같을 수도, 다를 수도 있지만, 하나의 분할에 하나의 프로그램만 적재할 수 있다. 따라서 동시에 메모리에 올릴 수 있는 프로그램 수가 고정되게 된다.
또한, 상황에 따라 단편화(fragmentation)가 발생한다.
- 외부 단편화(external fragmentation) : 프로그램의 크기보다 분할의 크기가 작은 경우, 해당 분할이 비어 있는데도 불구하고 프로그램을 적재하지 못하는 부분
- 내부 단편화(internal fragmentation) : 프로그램의 크기보다 분할의 크기가 큰 경우, 해당 분할에 프로그램을 적재하고 남은 메모리 공간
가변 분할
고정 분할 방식과 달리 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식이다. 분할의 크기가 프로그램의 크기보다 크지 않기 때문에 내부 단편화가 생기지 않는다.
가변 분할에서는 프로세스를 메모리에 올릴 때, 물리적 메모리 내 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제가 중요하다. 이를 동적 메모리 할당 문제(dynamic storage-allocation problem)라고 한다. 다양한 크기의 가용 공간들이 여러 곳에 흩어져 있기 때문에 이를 효율적으로 관리할 필요가 있다.
- 최초 적합(first-fit) : 프로그램의 크기보다 큰 가용 공간이 최초로 발견되면, 그 공간에 프로그램을 올림
- 최적 적합(best-fit) : 프로그램의 크기보다 큰 가용 공간 중, 가장 작은 공간에 프로그램을 올림
- 최악 적합(worst-fit) : 가용 공간 중, 가장 크기가 큰 곳에 프로그램을 올림
가변 분할 방식에서는 내부 단편화가 생기지 않는 반면, 이미 메모리에 존재하는 프로그램이 종료된 다음 생긴 빈 공간에 의해 외부 단편화가 발생할 가능성은 있다. 이를 해결하기 위한 방법으로 컴팩션(compaction)이라는 것이 있다. 컴팩션은 가용 공간들을 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법으로, 예전에 windows의 조각 모음같은 기능이 이에 해당한다.
불연속 할당(noncontiguous allocation) 기법
하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법이다. 생각해 보면 게임이나 포토샵같은 무거운 여러 개의 프로그램들을 어떻게 동시에 작은 물리적 메모리에 올려서 실행시킬 수 있는지 의문이 들 수 있다.
프로그램이 메모리에 적재되어 실행될 때, 전체가 다 올라가지 않는다. 프로그램을 여러 개의 분할로 나눈 뒤, 필요한 부분만 메모리에 올려서 사용한다. 다수의 프로세스들을 짧은 시간 안에 번갈아가며 연산해야하는 CPU는 프로세스의 일부분만 사용해 작업을 수행하고 빨리 다음 프로세스를 연산해야 하기 때문에 매우 합리적이다.
이때, 하나의 프로그램을 분할하는 기준에 따라 페이징(paging) 기법, 세그먼테이션(segmentation) 기법 등으로 나뉜다.
페이징(Paging)
프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식이다. 메모리를 페이지와 같은 크기의 프레임(frame) 단위로 미리 나누어 두고, 빈 프레임에 하나의 페이지를 할당한다.
- 페이지(page) : 프로세스의 주소 공간을 나눈 단위
- 프레임(frame) : 물리적 메모리의 주소 공간을 나눈 단위
이런 방식을 사용하면, 앞서 연속 할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다. 하지만 주소 변환 절차가 다소 복잡하다. 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 주소 변환 정보가 있어야 한다. 따라서 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table)을 가진다.
페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)로 나누어 주소 변환에 사용한다. 이 페이지 번호는 페이지 테이블의 인덱스(index)로 사용되고, 해당 인덱스의 엔트리(entry)에는 그 페이지의 물리적 메모리의 기준 주소, 즉 시작 위치가 저장된다. 이 시작 위치에 페이지 오프셋을 더해주면 요청한 논리적 주소에 매핑된 물리적 주소를 얻을 수 있는 것이다.
그림을 보면, CPU는 물리적 주소를 얻기 위해 페이지 테이블의 p번째 인덱스에 접근한다. 거기에는 물리적 메모리에 위치한 프레임 f의 기준 주소 값이 저장되어 있다. 그 값을 읽은 후, 페이지 오프셋(d)을 더해 최종적인 물리적 주소를 얻어 물리적 메모리에 접근하게 된다.
페이지 테이블 구현과 TLB(Translation Look-aside Buffer)
페이지 테이블은 물리적 메모리에 위치하게 된다. CPU는 이 페이지 테이블에 접근하기 위해 2개의 레지스터를 사용한다.
- 페이지 테이블 기준 레지스터(page-table base register) : 메모리 내에서 페이지 테이블의 시작 위치
- 페이지 테이블 길이 레지스터(page-table length register) : 페이지 테이블의 크기
때문에 사실 CPU가 주소 변환을 위해 페이지 테이블에 접근한 뒤, 변환된 물리적 메모리 주소로 실제 데이터에 접근해야 하기 때문에 두 번의 메모리 접근이 필요하다. 이런 오버헤드를 줄이고 메모리의 접근 속도를 향상시키기 위해 TLB(Translation Look-aside Buffer)라는 고속의 주소 변환용 하드웨어 캐시가 사용된다. 이 TLB에는 빈번히 참조되는 페이지에 대한 주소 변환 정보가 담겨 있다. 만약 요청한 페이지 번호가 TLB에 존재하면 곧바로 물리적 메모리의 프레임 번호를 얻을 수 있다.
TLB는 프로세스의 페이지 번호 정보를 모두 담고 있는게 아니라 페이지 테이블처럼 인덱스로 접근하는 것이 불가능하다. 따라서 페이지 번호에 대한 정보와 이에 대응하는 프레임 번호 값(프레임 시작 주소)을 함께 가지고 있다. 다만 이렇게 되면, 페이지 번호가 TLB에 있는지 확인하기 위해 모든 항목을 다 찾아봐야 하는 오버헤드가 발생한다. 이를 줄이기 위해 일반적으로 병렬 탐색이 가능한 연관 레지스터(associative register)를 함께 사용한다.
계층적 페이징(Hierarchical Paging)
32비트 주소 체계를 사용하는 컴퓨터에서는 보통 페이지 크기가 4KB다. 물리적 메모리가 최대 4GB이기 때문에, 4GB 프로그램을 실행해야 한다고 하면, 1M개의 페이지가 생성되고 페이지 테이블의 항목도 1M가 된다. 그리고 각 항목당 4바이트(32비트)의 주소를 표현해야 하기 때문에, 페이지 테이블을 위해 1M x 4B = 4MB 크기의 메모리 공간이 필요하게 된다.
따라서 수행되는 프로그램이 많아질 수록 상당부분 메모리 공간 낭비가 심해지는데, 심지어 전체 프로그램 주소 공간 중 극히 일부분만 사용되는 특성을 보면, 전체 페이지 테이블이 메모리 공간에 올라가는 것은 심각한 공간 낭비다. 이를 해결하기 위해 계층적 페이징(Hierarchical Paging) 기법을 사용한다.
2단계 페이징(two-level paging) 기법을 예로 들면, 주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용한다.
먼저 외부 페이지 테이블로부터 내부 페이지 테이블의 주소를 얻게 된다. 그리고 다시 내부 페이지 테이블로부터 물리적 메모리 위치(프레임 시작 위치) 정보를 얻어 최종적인 변환이 이루어 진다. 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정해, 이에 대응하는 내부 페이지 테이블을 생성하지 않는다. 때문에 메모리 공간 낭비를 크게 줄일 수 있다.
32비트의 논리적 주소가 어떻게 여러 개의 페이지 테이블을 나타낼 수 있는지, 2단계 페이징 기법을 기준으로 알아보자. 먼저 페이지 크기가 4KB이므로 하나의 페이지 내에서 바이트 오프셋을 결정하기 위해 12비트가 필요하다. 따라서 최하위 12비트는 오프셋으로 사용된다.
- 0000 0000 0000 0000 0000 0000 0000 0000 → 오프셋
다음으로 내부 페이지 번호를 저장해야 하는데, 각각의 내부 페이지 테이블 자체를 하나의 외부 페이지에 보관한다. 즉, 4KB 페이지를 사용하면 내부 페이지 테이블의 크기 역시 4KB가 된다. 페이지 테이블 항목 당 4바이트 이므로, 내부 페이지 테이블은 4KB/4B = 1K 개의 항목을 가지게 된다. 이를 구분하기 위한 비트 수는 10비트다.
- 0000 0000 0000 0000 0000 0000 0000 0000 → 내부 페이지 테이블 번호(인덱스)
마지막으로 나머지 10비트는 외부 페이지 테이블의 인덱스로 사용된다.
- 0000 0000 0000 0000 0000 0000 0000 0000 → 외부 페이지 테이블 번호(인덱스)
프로세스를 구분하기 위해 필요한 주소 공간이 커질수록 여러 개의 페이지 테이블이 필요하게 된다. 다만, 여러 번의 테이블 접근이 필요하기 때문에 시간적 오버헤드가 발생하게 된다. 때문에 앞서 설명한 TLB를 사용하는 것이 효과적이다. 보통 4단계로 구성하면 시간 오버헤드는 그다지 크지 않지만 메모리 공간 효율 효과는 크게 기대할 수 있다.
역 페이지 테이블(Inverted page table)
메모리 주소 공간의 효울을 위해 더 극단적인 방법이 있다. 역페이지 테이블 기법은 논리적 주소에 대한 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다. 즉, 시스템 전체에 페이지 테이블을 하나만 두는 방법이다.
페이지 테이블의 각 항목은 어느 프로세스의 어느 페이지가 이 프레임에 저장된 지에 대한 정보를 보관한다. 위 그림에서 pid는 프로세스 번호이고, p는 페이지 번호다. 페이지 주소 변환 요청이 들어오면, 논리적 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야 한다. 때문에 앞서 언급한 연관 레지스터에 페이지 테이블을 저장한 뒤, 병렬 탐색을 통해 시간적 효율성을 높인다.
공유 페이지(Shared Page)
공유 코드는 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드다. 이 공유 코드를 담고 있는 페이지가 공유 페이지다. 공유 페이지는 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 한다.
공유 페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다. 위 그림에서 libc 1, libc2, libc3, libc4 4개의 페이지가 프로세스 p1, p2, p3에 의해 공유된다면, 4개의 페이지는 각각의 프로세스의 주소 공간 내에서 동일한 위치에 존재해야 한다. 때문에 페이지 테이블에서도 페이지 테이블 번호(인덱스)가 3, 4, 6, 1로 같다. 또한 물리적 메모리에는 하나씩의 코드만 올라간다.