우리가 사용하는 프로그램은 디스크에 저장되어 있고 프로그램을 실행하는 것은 CPU다. CPU는 디스크에 직접 접근할 수 없어서 메인 메모리(DRAM)에 프로그램을 적재한 뒤에 CPU가 이를 읽어서 인스트럭션을 실행하는 것이다.
우리는 컴퓨터를 사용할 때 여러가지 프로그램을 한 번에 실행하는데 운영체제에서는 다수의 프로세스를 메모리에서 효율적으로 사용하기 위해 페이징이라는 기법을 사용한다. 이러한 페이징의 개념과 원리에 대해 알아보자.
주소 공간
메인 메모리는 위와 같이 연속적인 주소공간으로 이루어져 있으며 각 주소공간에 바이트 단위로 데이터를 할당한다. CPU는 메모리의 주소로 데이터에 접근하는데, 직접 실제 주소로(물리적 주소) 접근하지 않고 논리적 주소를 통해 접근한다.
논리적 주소란 CPU와 프로세스 입장에서의 주소라고 생각할 수 있다. 각 프로세스는 0번지부터 시작하는 가상의 주소값을 부여받아 실행된다. 논리적 주소는 MMU라는 장치를 통해서 물리적 주소로 매핑되며 이를 통해 CPU는 논리적 주소로 실제 메모리 주소에 접근할 수 있게 된다.
논리적 주소를 사용하는 이유
논리적 주소를 사용하면 다음과 같은 다양한 장점을 얻을 수 있다.
- 프로세스 격리
멀티 프로세싱에서는 여러개의 프로세스가 메모리에 할당된다. 논리적 주소를 사용해 프로세스가 접근 가능한 주소를 제한하여 프로세스간 주소공간을 침범하는 것을 막을 수 있다.
- 메모리 효율성
논리적 주소를 사용하면 빈 메모리 주소공간을 유연하게 할당받을 수 있다. 프로세스가 물리 주소를 사용한다면 디스크에서 메인메모리에 할당될 때 항상 같은 주소공간에 할당되어야 하고 이는 효율적으로 메모리를 사용할 수 없게 만들 것이다. 또한 가상메모리를 구현하는데 있어서도 논리적 주소는 핵심적인 역할을 하기도 한다.
32bit 프로세서의 메모리
32bit 프로세서는 주소를 32bit로 표현하며, 메모리는 바이트단위로 주소를 할당한다. 32bit로 2^32 까지의 주소공간을 표현할 수 있으며 이는 40,000,000,000 의 근사치이다. 40억 바이트는 4GB이므로 32bit 프로세서는 4GB 이상의 메모리에 접근할 수 없다.
외부 단편화
프로그램을 실행하기 위해 디스크에 있는 데이터를 메모리로 로드해야 한다고 했다. 그런데 디스크에 있는 데이터를 메모리에 연속적인 공간에 할당하게 되면 외부 단편화라는 문제가 발생한다.
위 그림은 8GB 램에 프로그램 데이터를 연속된 주소공간에 할당하는 예시이다. 프로세스 A, B, C가 순차적으로 메모리에 할당되었다가 프로세스 B가 작업을 마치고 메모리 할당을 해제한 상황이다. 이 상태에서 2GB 크기의 프로세스 D를 할당하려고 한다면 메모리에 2GB의 여유 공간이 있지만, 이 공간이 연속적이지 않아 메모리에 로드할 수 없는 상황이 발생한다.
이처럼 총 사용 가능한 메모리 공간은 충분하지만 이 공간이 나누어져 있어 실제로 할당할 수 없는 문제를 외부 단편화라고 한다.
내부 단편화
메모리 단편화에는 외부 단편화 뿐만 아니라 내부 단편화 라는 개념도 있다. 만약 위 예시에서 900MB 크기를 가지는 프로세스를 1GB 공간에 할당한다면 100MB가 남게된다. 이처럼 필요한 공간보다 더 많은 메모리가 할당되어 내부에 남는 공간이 생기는 것을 내부 단편화라고 한다.
외부 단편화 해결 방법
외부 단편화를 해결하는 방법은 Compaction과 Paging이 있다.
Compaction은 왼쪽 그림처럼 메모리에 할당된 데이터들을 재배치하여 빈 공간을 한 곳으로 모으는 방법이다. 하지만 Compaction을 위해서는 데이터를 복사하는 오버헤드가 너무 커서 사용되지 않는 방법이다.
Paging은 오른쪽 그림처럼 메모리를 일정한 크기로 나누고 데이터를 불연속적으로 할당하는 방법이다. 이 방법은 내부단편화가 발생할 수 있지만 메모리를 효율적으로 관리할 수 있고 가상메모리를 구현하기 위해서 기본적으로 사용되는 기법이기도 하다. 실제로 이러한 장점들로 인해 현대에는 Paging 기법으로 메모리를 관리한다.
페이징
앞서 말했듯이 페이징은 연속 할당의 외부단편화 문제를 해결하기 위해 고안된 방식으로 메모리를 일정한 크기의 블록으로 나눠 불연속할당하는 방식이다. 나누어진 블록을 가상 메모리에서는 페이지, 물리 메모리에서는 프레임이라고 한다.
페이징을 통해 외부단편화는 해결했지만 하나의 프로세스가 불연속적인 공간에 흩어져 있어 어떤 프레임이 어떤 페이지에 위치해 있는지에 대한 정보가 필요하다. 또한, 여러 바이트로 이루어진 페이지에서 몇 번째 바이트에 원하는 명령어가 있는지도 알아야 한다.
페이지 테이블
페이지 테이블은 어떤 프레임이 어떤 페이지에 위치해 있는지 매핑해주기 위한 정보를 가지고 있다. 프로세스의 논리적 주소는 연속적인 공간을 할당 받으며, 불연속적으로 위치한 물리적 주소공간을 페이지 테이블로 매핑하여 마치 연속적인 주소공간을 사용하는 것과 같은 효과를 낼 수 있다.
위 그림은 페이지 테이블을 간단하게 나타낸 예시이다. 4개의 블록으로 나누어진 프로세스를 예시로 들었으며 프레임이 실제 몇 번 페이지에 위치해 있는지 페이지 테이블을 통해 알 수 있다.
오프셋
페이지 단위로 데이터에 접근한 후에는 페이지의 몇 번째 바이트에 원하는 명령어가 있는지 알아야 한다.
페이지 테이블의 예시 그림에서 1번 페이지를 집중적으로 살펴보자. 해당 예시에서는 하나의 페이지가 4byte라고 가정하였다. 오프셋은 바이트 단위로 표현하기 때문에 0번~3번까지 4개의 오프셋이 생기게 된다. 페이지 테이블을 통해서 프레임 위치를 찾고, 오프셋을 더해주면 실제 데이터 위치를 찾을 수 있게 된다.
페이지 테이블과 오프셋에 대한 개념을 이해했다면, 논리 주소에 대해 좀 더 자세히 알아보자.
위와 같이 10bit 주소 체계를 가지는 CPU에서 4bit를 offset으로 사용한다고 가정해보자.
4bit의 offset을 가진다는 것은 하나의 페이지가 2^4 = 16 byte라는 뜻이다.
또한 남은 6bit는 페이지 번호를 표현할 수 있으므로 2^6 = 64개의 페이지를 표현할 수 있다. 따라서 페이지 테이블도 64개의 값을 가지고 있어야 한다.
32bit 프로세서의 주소 체계
예시를 위해 위에서 작은 비트 값을 예시로 들었지만, 일반적인 프로세서와 운영체제에서는 하나의 페이지를 4KB로 설정한다. 그렇다면 32bit 주소체계를 사용하는 프로세서에서는 페이지 번호를 표현하기 위해 몇 비트를 사용하고, 오프셋은 몇 비트를 사용하는지 한 번 더 계산해보자.
하나의 페이지가 4KB(4096Byte)라는 것은 4096=2^12 로, 12bit를 오프셋으로 사용한다는 뜻이다.
32bit 중 12bit를 오프셋으로 사용하므로 자연스럽게 남은 20bit는 페이지 번호를 나타내기 위해 사용하게 되는 것이다.
x86-64 프로세서의 주소 체계
64bit 프로세서에서는 얼마나 많은 가상 주소를 표현할 수 있을까? 64bit 프로세서는 64bit의 주소를 표현할 수 있으므로 2^64=16 엑사바이트 만큼의 주소공간을 표현할 수 있다. 가상메모리 관점에서 접근한다고 해도 이는 터무니 없이 큰 용량이다. 그렇기 때문에 실제로는 주소를 표현하는데 모든 비트를 사용하지 않고 논리적 주소에서 36bit, 물리적 주소에서 28bit 를 페이지 번호를 나타내는데 사용한다고 한다.
이미지 출처 - https://narakit.tistory.com/146
페이지 번호와 페이지 테이블 주소 매핑
페이지 테이블을 설명하면서 페이지 번호가 페이지 테이블에 자동적으로 매핑되는 것 처럼 설명하였다.
0x12345ABC번 논리주소에서 0x12345가 페이지 번호이고 0xABC가 오프셋일 때, 메모리의 0x12345번 주소에 가면 원하는 페이지 테이블이 있는것 처럼 오해할 수 있을 것 같다. 하지만 아주 잘못된 생각이다.
애초에, 해당 주소체계는 32bit인데 페이지번호는 20bit만 사용하기 때문에 주소와 매핑되지 않는다. 또한, 프로세스별로 페이지테이블을 가지기 때문에 페이지 번호로 페이지 테이블을 찾아가는 것은 더더욱 말이 안된다.
(이런 예시를 드는 이유는 내가 그렇게 이해했었기 때문이다..😭)
페이지 테이블 또한 메모리에 저장되어 있는 값이기 때문에, 프로세스의 페이지 테이블이 메모리의 몇 번 주소에 저장되어 있는지도 알아야 한다. 프로세스에 맞는 페이지테이블의 주소를 매핑해주는 작업은 PTBR(Page Table Base Register)이라는 레지스터가 해준다. PTBR은 프로세스의 페이지테이블이 시작하는 주소값을 저장하고 있다. 또한 프로세스가 메모리 공간을 침범하지 않도록 격리하기 위해 자신의 페이지 테이블 범위를 넘지 않도록 제한하는 PTLR(Page Table Length Register)도 존재한다.
풀리지 않은 문제들
여기까지 이해했다면 페이징에 대해서 기본적인 개념을 이해했다고 할 수 있다. 하지만 아직 풀리지 않은 문제가 많다.
불연속 할당을 위해 페이징이라는 개념이 등장했는데, 정작 이를 구현하기 위한 페이지테이블은 연속된 메모리 공간에 저장되어야 하는 문제가 있다.
또한 논리주소를 물리주소로 변환하기 위해 페이지 테이블을 거쳐 메모리에 두 번 접근해야 한다는 문제도 있다.
다음 포스팅에서는 이러한 문제를 어떻게 해결하는지 알아보도록 하자.
참고자료
https://narakit.tistory.com/146
https://charles098.tistory.com/106
