[OS] Memory management

메모리 관리와 주소 변환 구조의 이해

운영체제가 여러 프로세스를 동시에 실행하는 멀티프로그래밍 환경에서는 물리 메모리를 효율적이면서도 안전하게 관리할 수 있어야 한다. 이를 위해 고안된 여러 메모리 관리 전략 중, 주소 공간의 개념과 주소 변환 구조는 가장 핵심적인 요소 중 하나이다.

1. 멀티프로그래밍을 위한 메모리 관리

멀티프로그래밍에서는 여러 프로세스가 동시에 물리 메모리에 올라가 있어야 한다. 이때 중요한 요구사항은 다음과 같다.

• 각 프로세스는 운영체제나 다른 프로세스의 메모리에 접근해서는 안된다.
• 따라서 메모리 보호 기능(Protection)이 필수적이다.

가장 기본적인 구현 방식은 Base와 Limit 레지스터를 사용하는 것이다.

2. 논리 주소와 물리 주소(Logical Address, Physical Address)

프로세스가 사용하는 주소는 논리 주소(Logical Address), 즉 가상 주소(Virtual Address)이다. 이는 CPU가 명령 실행 중 생성하는 주소이며, 실제 메모리상의 위치인 물리 주소(Physical Address)와는 다르다. 이 둘을 매핑하는 역할은 메모리 관리 장치(MMU)가 담당한다.

가상 주소의 도입은 사용자 프로세스가 실제 물리 메모리 주소를 알 필요 없이, 마치 항상 0번지부터 시작하는 것처럼 착각하게 만들어준다. 이는 보호성과 프로그램 독립성, 프로세스 간 충돌 방지 등을 가능케 한다.

가상 주소의 필요성

초기의 컴퓨터 시스템에서는 프로그램이 물리 메모리 주소를 직접 다루어야 했다. 즉, 사용자는 프로그램을 메모리의 어느 위치에 적재할지 수동으로 지정해야 했고, 그에 따라 메모리 참조 연산 역시 물리 주소 기반으로 직접 코딩해야 했다.

하지만, 이런 방식은 다음과 같은 여러 문제를 일으킨다.
1. 물리 메모리 관리의 복잡성
- 사용자는 자신이 작성한 프로그램이 어느 위치에 로드될지 직접 고려해야 한다.
- 운영체제가 동시에 여러 프로세스를 실행하는 환경에서, 모든 사용자가 서로 충돌하지 않게 메모리 위치를 일일이 지정하는 것은 현실적으로 불가능하다.
2. 프로그램 간 충돌의 위험
- 만약 하나의 프로그램이 실수로 다른 프로그램이 사용하는 메모리 공간을 접근하거나 덮어쓰게 되면, 시스템 전체가 불안정해질 수 있다.
- 이는 보안과 안정성 측면에서 큰 위협이 된다.

이러한 문제를 해결하기 위해 등장한 개념이 바로 가상 주소(Virtual Address)이다.

가상 주소란? 사용자 프로그램이 실제 물리 메모리를 알 필요 없이, 자신만의 독립적인 주소 공간을 가진 것처럼 실행되도록 하는 추상화된 주소 체계이다.

가상 주소는 다음과 같은 이점을 제공한다.

• 프로그램 독립성 보장 : 각 프로그램은 마치 주소 0부터 시작하는 것처럼 실행된다. 따라서 프로그램이 어디에 로드되는지 신경 쓸 필요가 없다.
• 메모리 보호와 격리 : 가상 주소 공간은 각 프로세스에 독립적으로 주어지기 때문에, 서로의 메모리에 접근할 수 없다. 이는 메모리 보호와 보안을 자연스럽게 실현한다.
• 운영체제의 유연한 메모리 관리 : 프로그램 로더는 가상 주소를 기반으로 프로그램을 적절한 물리 메모리 위치에 적재하고, MMU가 이를 물리 주소로 변환해준다. 이 덕분에 프로그램은 자신이 사용하는 메모리의 실제 위치를 몰라도 정상적으로 동작할 수 있다.

3. 간단한 MMU를 이용한 주소 변환

기본적인 MMU는 재배치 레지스터(Relocation Register) 하나만으로도 가상 주소를 물리 주소로 바꿀 수 있다. CPU가 생성한 가상 주소에 이 값을 더하면 해당 물리 주소가 된다. 여기에 Limit Register를 함께 사용하면 접근 가능 범위를 검증하는 보호 기능도 제공할 수 있다.

운영체제에서 여러 프로세스를 동시에 관리하려면, 어떤 논리 주소(Logical Address)가 실제 어떤 물리 주소(Physical Address)에 매핑되는지 알아야 하며, 이 주소 접근이 합법적인지를 반드시 검증해야 한다. 이 두 가지 기능을 동시에 제공하는 기법이 메모리 매핑과 보호(Memory Mapping and Protection)이다.

이 구조는 두 개의 간단한 하드웨어 레지스터로 구현할 수 있다.
1. Relocation Register(or Base Register) : 현재 실행 중인 프로세스가 접근할 수 있는 가장 작은 물리 주소를 저장한다.
2. Limit Register : 해당 프로세스가 사용할 수 있는 주소 범위(논리 주소 공간의 크기)를 나타낸다.

이 두 레지스터의 조합을 통해, CPU가 생성하는 모든 주소는 다음과 같은 절차로 검사된다.
1. CPU가 생성한 가상 주소가 리미트 값을 넘지 않는지 확인한다.
2. 가상 주소에 재배치 값을 더해 물리 주소를 계산한다.
3. 계산된 물리 주소가 유효한 범위에 있는지 다시 검증한다.

이러한 매핑 및 보호 구조는 프로세스 전환 시에도 핵심적인 역할을 한다.

• 스케줄러(Scheduler)는 프로세스를 선택할 때 해당 프로세스의 PCB에 저장된 베이스/리미트 값을 레지스터에 로드한다.
• 이후 실행되는 동안, CPU는 생성하는 모든 주소에 대해 자동으로 이 값을 참조하며 유효성을 검사하게 된다.

이 방식은 다음과 같은 장점을 가진다.

• 다른 프로세스나 운영체제의 메모리에 대한 불법 접근 차단
• 각 프로세스의 메모리 공간 보호 및 격리 보장
• 하드웨어 수준의 빠르고 효율적인 주소 변환 및 보호 수행

4. 연속 메모리 할당(Contiguous Allocation)

초기의 메모리 관리 기법은 각 프로세스가 연속적인 메모리 블록을 할당받는 방식이었다. 이는 관리가 간단하다는 장점이 있으나, 외부 단편화(External Fragmentation)라는 큰 문제를 안고 있다.

• 외부 단편화(External Fragmentation) : 메모리가 중간중간 비어 있지만, 할당 가능한 큰 덩어리의 연속 공간이 없어 새로운 프로세스를 위한 할당이 불가능해지는 현상을 의미한다.
  

이를 해결하기 위한 두 가지 방식은 아래와 같다.

• 압축(Compaction) : 메모리의 내용을 재배치하여 빈 공간을 한 곳으로 모은다. 하지만, Compaction 시에 엄청난 Copy 오버헤드가 발생하여 성능이 떨어진다.
  

• 비연속 할당(non-contiguous Allocation) : 프로세스가 연속된 메모리 공간이 아닌, 여러 조각으로 나뉘어 저장될 수 있도록 한다. -> Paging

5. Paging

비연속 할당을 실현하기 위한 핵심 기법인 페이징, 다음과 같은 방식으로 작동한다.

• 물리 메모리를 고정된 크기의 블록인 프레임(Frame)으로 나누고,
• 가상 메모리 역시 같은 크기의 페이지(Page)로 나눈다.(Frame size == Page size)
• 프로세스가 실행되면, 필요한 페이지를 임의의 빈 프레임에 적재하고, 이 매핑 정보를 페이지 테이블(Page Table)에 저장한다.

6. 주소 변환 구조(Address Traslation Architecture)

앞서 설명한 페이징 구조에서 CPU가 생성하는 가상 주소는 페이지 테이블을 통해 물리 주소로 변환된다. 이 과정을 정확히 수행하기 위해, 가상 주소는 두 개의 논리적 구성 요소로 나뉜다.

• 페이지 번호(Page Number)-(p) : 가상 주소에서 어떤 페이지인지 나타낸다.
• 페이지 오프셋(Page Offset)-(d) : 해당 페이지 내에서의 위치
  

MMU는 페이지 번호를 이용해 페이지 테이블에서 해당 페이지에 대응하는 프레임 번호를 찾고, 여기에 오프셋을 더해 최종 물리 주소를 계산한다.

주소 비트 계산 방법

주소 분할을 위해 필요한 비트 수는 하드웨어적으로 정해지는 페이지 크기와 전체 가상 주소 공간의 크기에 따라 결정된다.

• 가상 주소 공간 크기가 2m 바이트이고,
• 페이지 크기가 2n 바이트라면,
  가상 주소는 다음과 같이 구성된다.
  

즉, 전체 주소 중 상위 m-n 비트는 페이지 번호를, 하위 n비트는 페이지 오프셋을 나타나게 된다.

예를 들어, 가상 주소가 16비트이고 페이지 크기가 4KB(212바이트)라면: 페이지 번호는 상위 4비트, 페이지 오프셋은 하위 12비트

이 구조는 주소를 신속하고 체계적으로 분할해 MMU가 효율적으로 물리 주소를 계산할 수 있게 한다.

Example : 32바이트 메모리에서의 페이징 주소 변환

• 가상 주소 공간 크기 : 16(24), 즉 4비트 주소(m==4)
• 페이지 크기 : 4(22), 즉 2비트 오프셋(n==2)
• 페이지 번호 : 4 - 2 = 2비트
• 페이지 오프셋 : 2비트

7. Internal Fragmentation

페이징 방식은 외부 단편화는 해결하지만, 새로운 문제인 내부 단편화(Internal Fragmentation)를 발생시킬 수 있다. 이는 페이지 크기 단위로 메모리를 할당하기 때문에, 마지막 페이지가 완전히 채워지지 않으면 남은 공간이 낭비되기 때문이다.

예를 들어, 페이지 크기가 4KB인데 실제로 필요한 데이터가 512바이트밖에 없다면 나머지 3584바이트는 사용되지 않고 낭비된다. 이처럼 일부 페이지의 사용되지 않는 공간이 누적되면서 전체 시스템 메모리 효율이 저하될 수 있다.

8. Memory Protection

운영체제는 단순히 주소를 매핑하는 것에 그치지 않고, 각 페이지에 대해 읽기/쓰기 권한을 지정할 수 있다. 이를 위해 페이지 테이블 항목마다 보호 비트(Protection Bit)를 함께 저장한다.

• 각 페이지에 대해 읽기 전용(Read-only) 또는 읽기-쓰기(Read/Write) 권한을 설정할 수 있다.
• 커널 코드나 텍스트 섹션은 일반적으로 읽기 전용으로 설정되어, 사용자 프로세스가 이를 변경하지 못하도록 한다.

이 보호 비트는 MMU가 주소 변환 과정에서 함께 확인하며, 권한을 위반한 접근 시에는 exception을 발생시켜 운영체제가 대응하게 한다.

9. Valid-InValid Bit

모든 가상 주소가 항상 물리 메모리에 매핑되어 있는 것은 아니다. 일부 페이지는 아직 메모리에 적재되지 않았을 수 있으며, 이는 다음과 같은 상황에서 발생한다:

• 가상 메모리 공간이 물리 메모리보다 클 경우
• 페이지가 교체되어 디스크로 스왑된 경우

이를 식별하기 위해 각 페이지 테이블 엔트리에는 Valid-Invalid Bit가 추가된다.

• Valid : 해당 페이지가 현재 물리 메모리의 프레임에 적재되어 있음
• Invalid : 페이지가 메모리에 존재하지 않음

만약 CPU가 invalid로 표시된 페이지를 참조하려 하면, 이는 운영체제에게 exception을 발생시키고, 운영체제는 해당 페이지를 디스크에서 메모리로 적재하는 등의 처리(Page fault)를 수행한다.

위 그림에서 Page6에 대해 접근하려하면, page table의 valid-invalid bit가 invalid 비트이므로 메모리에 존재하지 않음을 의미한다. 해당 page에 대해 접근 시도를 할 경우, page fault exception을 발생시켜 프로세스가 강제 종료된다.

Example

아래 코드의 경우,

//Example1
int* ptr = null;
*ptr = 10; //0번지에 10 저장 시도

//Example2
int* ptr;
ptr = malloc(4); //0x08044444;
*ptr = 10;

위 코드처럼 malloc을 통해 heap 영역을 사용하는 경우 heap 영역은 DRAM과 매핑이 되어있으므로, 매핑되어 있는 frame에 10을 저장한다.

//Example3
int a; 

int main(){
	int b;
    int c;
    a = 10;
    b = 20;
    c = 30;
}

위 코드의 경우 전역변수는 initialized Data 섹션, 지역 변수는 stack이 DRAM과 매핑되어 있으므로 데이터를 정상적으로 저장할 수 있다.

Shared Pages: 다수의 프로세스를 위한 코드 공유

운영체제는 여러 프로세스가 동일한 프로그램(예: 텍스트 에디터)을 동시에 실행하는 상황을 자주 마주한다. 예를 들어, 40개의 프로세스가 각각 150KB의 코드 영역과 50KB의 데이터 영역을 사용하는 경우 총 8000KB의 물리 메모리가 필요하다. 하지만 코드 영역은 대부분 읽기 전용(Read-only)이며 실행 중 변경되지 않는 순수 코드(pure code) 혹은 재진입 가능 코드(reentrant code)이므로, 모든 프로세스가 각자 복사본을 가질 필요는 없다.

해결책: Shared Pages
하나의 코드 복사본만 물리 메모리에 유지하고, 각 프로세스의 페이지 테이블이 이 공통 복사본을 참조하도록 하면 물리 메모리를 절약할 수 있다. 반면, 데이터 페이지는 프로세스마다 다르므로 개별적으로 매핑된다.

공유 가능한 예시: 컴파일러, 윈도우 시스템, 런타임 라이브러리, 데이터베이스, System V IPC의 공유 메모리 등

Hierarchical Page Table: 대용량 주소 공간 문제 해결

32비트 시스템에서 페이지 크기가 4KB(212)이고 각 페이지 엔트리가 4바이트라면, 전체 논리 주소 공간을 위한 페이지 테이블의 크기는 다음과 같이 계산된다.

• 페이지 수 : 232/212 = 220 (약 100만개)
• 총 페이지 테이블 크기 : 220 x 4B = 4MB

이는 각 프로세스마다 4MB의 연속적인 공간이 필요하다는 뜻으로, 대용량 주소 공간(예: 64비트)에서는 매우 비효율적이다.

Hierarchical Page Table
이 문제를 해결하기 위해 계층적 페이지 테이블 구조가 도입되었다. 이는 마치 프로세스 주소 공간처럼 페이지 테이블 자체도 페이지 단위로 나누어 비연속적으로 메모리에 배치하는 방식이다. 대표적인 예로 2단계 페이지 테이블이 있다.

2단계 페이징 구조

32비트 주소 공간을 다음과 같이 분할한다.

• 상위 10비트(p1): 1차 페이지 테이블의 인덱스
• 중간 10비트(p2): 2차 페이지 테이블의 인덱스
• 하위 12비트(d): 페이지 내 오프셋

즉, 가상 주소는 <p1, p2, d>로 구성되고, 두 단계에 걸쳐 물리 프레임으로 접근한다.

Segmentation: 프로그램 의미에 따른 메모리 분할

프로그래머의 관점에서 프로그램은 연속적인 주소 공간이 아니라 다음과 같이 논리적인 구성 요소들로 나뉜다.

이러한 구성 요소들은 크기를 예측하기 어렵고, 실행 중 동적으로 증가하거나 감소할 수 있다. 이를 고려하여 물리 메모리 역시 논리적 단위로 나누어 관리하는 방식이 Segmentation이다.

Segment?

세그먼트는 프로그래머가 인식할 수 있는 논리 단위이며, 일반적으로 다음과 같이 구성된다.

• Text code
• Global variables
• Heap
• Stacks
• Standard C library or imported shared library
  

주소는 < 세그먼트 번호, 오프셋 > 형태로 표현된다. 예를 들어, display gkatnsms <0, 500>, malloc은 <2, 0>으로 식별할 수 있다.

하드웨어 구현
세그먼트 테이블은 각 세그먼트의 시작 주소(base)와 길이(limit)를 저장하며, CPU가 생성한 <세그먼트 번호, 오프셋>을 통해 물리 주소로 변환한다. 예를 들어, 세그먼트 2의 바이트 53번은 base + offset = 4300 + 53 = 4353으로 변환된다.

Intel Pentium : 세그멘테이션과 페이징의 결합

Intel Pentium 아키텍처는 순수 세그멘테이션과 세그멘테이션+페이징을 모두 지원한다. 다음과 같은 구조를 가진다:

세그멘테이션

• 최대 세그먼트 크기: 4GB
• 프로세스당 최대 세그먼트 수: 214 개
  - Private Segment(213) : 프로세스 전용
  • Shared Segment(213) : 여러 프로세스 간 공유

디스크립터 테이블

• GDT(Golbal Descriptor Table) : 공유 세그먼트
• LDT(Local Descriptor Table) : 개별 프로세스 세그먼트
• 주소는 <selector, offset> 형태이며, selector는 segment number(s), GDT/LDT(g), 보호 비트(p)를 포함한다.

Intel Pentium의 페이징
Pentium은 두 가지 페이지 크기를 지원한다. (4KB, 4MB) 4KB 페이지를 사용하는 경우, 2단계 페이징이 적용되며 다음과 같이 가상 주소가 구성된다.(10비트 page directory p1, 10비트 Page table p2, 12비트 offset d)

현재 프로세스의 page directory에 대한 포인터는 CR3 레지스터에 저장되어 있다.

TLB: 주소 변환을 가속화하는 캐시(Translation Look-aside Buffer)

가상 메모리 시스템에서 CPU는 프로그램이 사용하는 가상 주소를 실제 물리 주소로 변환해야 한다. 이 과정은 페이지 테이블을 참조해 이뤄지는데, 페이지 테이블은 메모리 상의 자료구조이므로 접근 자체가 시간 소모적이다. 만약 매번 페이지 테이블을 통해 주소를 변환해야 한다면, 메모리 접근 시간은 크게 증가하게 된다.

이때 등장하는 것이 TLB(Translation Look-aside Buffer)다. TLB는 최근에 접근한 가상 페이지 번호와 물리 프레임 번호의 매핑 정보를 저장하는 고속 캐시이다. 일반적으로 TLB는 하드웨어에 내장되어 있어 접근 속도가 매우 빠르며, 페이지 테이블을 매번 조회하지 않아도 된다. CPU가 메모리에 접근할 때 먼저 TLB를 확인하고, 만약 원하는 페이지에 대한 정보가 있다면 이를 TLB hit이라고 한다. 반대로 없다면 TLB miss가 발생하며, 이 경우 페이지 테이블을 조회해 다시 TLB에 해당 정보를 저장하게 된다.

TLB는 주소 변환의 병목을 줄이는 핵심 장치이지만, TLB의 크기는 제한적이기 때문에 효율적인 교체 전략과 함께 사용된다. 예를 들어, LRU(Least Recently Used) 방식으로 오래 사용되지 않은 항목을 제거하고 새로운 매핑을 추가할 수 있다.

Address Translation Overhead: 성능 저하의 원인

주소 변환 자체는 메모리 접근 과정에서 필수적인 단계지만, 이로 인해 발생하는 오버헤드는 시스템 성능에 직접적인 영향을 준다. 주소 변환 오버헤드는 TLB miss와 Page Fault가 함께 작용할 때 더 심각해진다.

주소 변환이 TLB에서 해결되지 못하면, CPU는 페이지 테이블을 메모리에서 읽어야 한다. 이때마다 메모리 접근이 발생하며, 이는 일반적인 데이터 접근보다 더 많은 시간이 소요된다. 특히, 페이지 테이블 자체가 계층 구조를 가질 경우(예: 다단계 페이지 테이블), 변환에 필요한 메모리 접근 횟수는 더 늘어난다. 이를 Address Translation Overhead라고 하며, 이는 곧 메모리 접근의 지연을 의미한다.

또한, 주소 변환 결과 해당 페이지가 물리 메모리에 없는 경우, 페이지 폴트가 발생한다. 이때 운영체제는 디스크에서 해당 페이지를 읽어 들여야 하며, 이 과정은 수 밀리초 단위의 시간 지연을 야기한다. 예를 들어, 메모리 접근 시간은 수십~수백 나노초인 반면, 디스크 접근은 평균적으로 8밀리초 이상 소요된다. 이처럼 페이지 폴트가 자주 발생하면 전체 시스템의 Effective Memory Access Time은 수천 배 이상 증가할 수 있다.