5. 페이징

페이징에 들어가기전 매핑 테이블에 대해 알아보자

 

메모리 관리를 수월하게 하기 위해 메모리 관리자는 가상 주소와 물리 주소를 일대일로 매핑한 ‘매핑 테이블’을 사용합니다.

이를 통해 가상 주소가 물리 메모리의 어느 위치에 있는지 알 수 있습니다.

 

• 페이징 매핑 테이블: 페이징 기법에서 사용하는 매핑 테이블
• 세그먼테이션 매핑 테이블: 세그먼테이션 기법에서 사용하는 매핑 테이블

 

 

페이징 기법이란?

고정 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 주소 공간을 같은 크기로 나누어 사용합니다.

구현 방식

가상 주소는 프로세스 입장에서 바라본 메모리 공간으로 항상 0번부터 시작합니다.

• 페이지: 가상 주소의 분할된 영역 ex) 첫 번째 영역 = 페이지 0, 두 번째 영역 = 페이지 1
• 프레임: 물리 주소의 분할된 영역, 가상 주소의 ‘페이지’와 구분하기 위해 ‘프레임’이라고 함
• invalid: 물리 메모리에 없는 데이터로 해당 페이지가 스왑 영역에 있다는 의미

 

주소 변환 과정

페이징 기법에서 가장 주소를 물리 주소로 변환하는 방법에 대해 알아보겠습니다.

위의 이미지에 따르면 페이지 0에는 0~9번지의 10개의 주소가 있고, 페이지 1에는 10~19 번지의 10개의 주소가 있습니다. (페이지와 프레임의 각 크기가 10byte)

프로세스가 30번지의 내용을 읽으려고 할 때의 주소 변환 과정은 아래와 같습니다.

1. 가상 주소 30번지가 어느 페이지에 있는지 찾는다. 30번지는 페이지 3의 0번째 위치에 있다.
2. 페이지 테이블의 페이지 3으로 가서 해당 페이지가 프레임 1에 있다는 것을 알아낸다.
3. 물리 메모리 프레임 1의 0번째 위치에 접근한다. 이 주소 가상 주소 30번지의 물리 주소이다.

프로세스가 가상 주소 18번지에 어떤 값을 저장할 때의 주소 변환 과정은 아래와 같습니다.

1. 가상 주소 18번지가 어느 페이지에 있는지 찾는다. 18번지는 페이지 1의 8번째 위치에 있다.
2. 페이지 테이블의 페이지 1로 가서 해당 페이지가 프레임 3에 있다는 것을 알아낸다.
3. 프로세스가 저장하려는 값을 프레임 3의 8번 위치에 저장한다.

표기법

[VA=<P,D>로 표기]

• VA: 가상 주소
• P: 페이지
• D: 페이지의 처음 위치에서 해당 주소까지의 거리(Distance)(=Offset)
• ex) 가상 주소 30번지: VA=<3,0>, 가상주소 18번지: VA=<1,8>

[PA=<F,D>로 표기]

• PA: 물리 주소(실제 주소)
• F: 프레임
• D: 프레임의 처음 위치에서 해당 주소까지의 거리
• ex) 물리 주소 프레임1의 0번째 위치: PA=<1,0>

<aside> 📌

가상 주소를 <P, D>로 변환하는 공식 (단위: byte)

• P = 나눗셈(가상주소/한 페이지의 크기)의 몫
• D = 나눗셈(가상주소/한 페이지의 크기)의 나머지 </aside>

페이지 테이블 관리

페이지 테이블은 프로세스마다 하나씩 가지고 있는 정보입니다. 여러 개의 프로세스가 메모리에 올라와 있다면 페이지 테이블의 크기가 커지고, 프로세스가 실제 사용할 수 있는 메모리 영역이 줄어드는 문제가 생길 수 있습니다. → 페이지 테이블의 크기를 적절히 유지하는 것이 페이지 테이블 관리의 핵심

 

 

ex) 32bit의 가상 주소 공간은 2^32byte(4GB) → 만약 페이지의 크기가 4KB이면 2^20 개의 페이지 테이블이 존재하게 됨, 각 페이지 항목이 4btye면 테이블 당 2^20 * 4 = 4MB가 됨 ⇒ 프로세스 당 4MB 크기의 테이블이 존재

 

페이지 테이블 기준 레지스터

페이지 테이블 기준 레지스터(PTBR, Page Table Base Register)란? CPU 내부에 있는 레지스터로, CPU가 데이터를 가장 빠르게 접근할 수 있도록 해주는 작은 고속 메모리 공간입니다. 현재 프로세스의 ‘페이지 테이블’이 물리 메모리의 어디에 시작하는지(시작 주소)를 보관합니다.

MMU가 가상 주소를 물리 주소로 변환하려고 할때 해당 프로세스의 페이지 테이블을 참조해야 합니다. 이때 MMU는 PTBR에 저장된 주소를 보고 해당 페이지 테이블의 시작 지점을 빠르게 찾아갈 수 있습니다.

• 페이지 테이블이 운영체제 영역(커널 영역)에 있는 이유
  • 페이지 테이블에는 가상 주소와 물리 주소의 매핑 정보 뿐만이 아니라, 각 페이지에 대한 접근 권한(읽기/쓰기/실행) 정보도 가지고 있음
  • 페이지 테이블은 각 프로세스의 메모리 공관을 관리하고, 가상 주소 변환을 수행하는 등의 운영체제의 챔임하에 관리되는 자료구조임
  ⇒ 시스템의 안성성 및 보안을 위해
• 단점: 두 번 메모리에 접근 (페이지 테이블, 물리 메모리) → 너무 복잡함 ⇒ TLB 추가

변환 색인 버퍼 (TLB, Translation Look-aside Buffer)

TLB이란? MMU 내부에 있는 작고 빠른 캐시 메모리입니다. 최근에 변환되었거나 자주 사용되는 ‘가상 페이지 번호’와 ‘물리 프레임 번호’를 임시로 저장하여 주소 변환 속도를 높입니다.

 

 

• TLB 히트: 원하는 페이지 번호가 변환 색인 버퍼에 있는 경우 → 곧 바로 물리 주소로 변환
• TLB 미스: 원하는 페이지 번호가 변환 색인 버퍼에 없는 경우 → 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환
  • TLB 미스가 나도 메인 메모리 접근 시간에 비하면 빠름

[동작 원리]

1. CPU에서의 정보로 TLB 탐색
   1. TLB 내의 모든 정보를 동시에 탐색
2. TLB에 있으면 바로 물리 주소에 접근
3. TLB에 없으면 페이지 테이블로 들어감

페이지 테이블 구조

계층적 페이지

현대의 컴퓨터는 매우 큰 주소 공간을 가지고 있습니다.이러한 환경에서 페이지 테이블도 상당히 커집니다.

예를 들어, 32bit의 가상 주소 공간을 가진 시스템에서 페이지 크기가 4KB(2^12)라면 2^20개의 페이지 테이블이 존재하게 됩니다. 각 페이지 항목이 4byte면 테이블 당 4MB의 공간이 필요하게 될 것입니다. 이러한 경우 모든 페이지 테이블을 메인 메모리에서 연속적으로 할당하는 것은 어렵습니다.

⇒ 페이지 테이블을 여러 개의 작은 조각으로 나누자!

2단계 페이징 기법

 

 

하나의 거대한 페이지 테이블을 두 개의 작은 테이블로 쪼개서 관리하는 방식입니다.

해시 페이지 테이블

 

32bit 보다 큰 주소 공간을 다룰 대 사용되는 방법으로 페이지 번호를 해싱을 통해 관리합니다. 각 페이지 번호에 대해 해시 함수를 적용해 해당 결과가 페이지에 해당하는 프레임 번호가 됩니다.

 

역 페이지 테이블

기존 페이징 방식과 반대로 페이지 테이블을 구성합니다. 물리 메모리의 프레임 번호를 기준으로 테이블을 구성합니다.

• 물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는지 표시
• 프로세스 수와 상관없이 테이블이 하나만 존재
• 원하는 데이터가 없으면 스왑 영역에서 가져옴

 

페이지 부재(Page Fault)와 처리 과정

페이지 부재는 가상 주소에 해당하는 페이지가 물리 메모리에 없는 상황에서 발생합니다. 이 경우 운영체제가 개입해 필요한 페이지를 디스크에서 불러와야 하므로 성능에 큰 영향을 줄 수 있습니다.

페이지 부재 처리 과정은 다음과 같습니다.

1. CPU가 가상 주소를 참조하고, 해당 페이지가 유효하지 않음을 페이지 테이블의 Valid bit를 통해 확인합니다.
2. 페이지 부재가 발생하면 운영체제가 디스크로부터 해당 페이지를 읽어옵니다.
3. 빈 프레임이 없으면 페이지 교체 알고리즘을 통해 하나를 선택하여 교체합니다.
4. 새로 적재된 페이지의 정보로 페이지 테이블을 갱신하고, CPU는 다시 해당 명령을 실행합니다.

---

페이지 교체 알고리즘

물리 메모리가 가득 찬 경우, 새로운 페이지를 적재하기 위해 기존 페이지를 제거해야 합니다. 어떤 페이지를 제거할지를 결정하는 방식이 페이지 교체 알고리즘입니다.

• FIFO (First-In, First-Out): 가장 먼저 메모리에 들어온 페이지를 제거합니다. 구현이 간단하지만, 오래되었다고 꼭 덜 중요하진 않기 때문에 비효율이 발생할 수 있습니다.
• LRU (Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 제거합니다. 성능은 좋지만 구현이 복잡하고 비용이 큽니다.
• Clock (Second Chance): LRU의 성능을 흉내내면서도 구현이 쉬운 방식입니다. 페이지에 접근되었는지 여부를 확인하여 기회를 한 번 더 주는 구조입니다.

---

TLB와 캐시의 차이점

TLB는 주소 변환을 빠르게 하기 위한 캐시이며, CPU의 일반 데이터 캐시와는 목적과 구조가 다릅니다.

• TLB (Translation Lookaside Buffer): 가상 주소를 물리 주소로 변환하는 정보를 저장하는 고속 메모리입니다. MMU 내부에 위치하며 주소 변환을 가속합니다.
• 데이터 캐시: 실제 프로그램이 사용하는 데이터(변수, 배열 등)를 빠르게 읽기 위해 사용되는 저장소입니다.

TLB는 주소 변환 전용, 캐시는 데이터 접근 전용이라는 점에서 차이가 있습니다.

---

내부 단편화와 외부 단편화

메모리 관리 기법의 특성에 따라 단편화의 종류가 달라집니다.

• 페이징: 고정 크기 페이지 단위로 메모리를 할당하므로 외부 단편화는 발생하지 않지만, 페이지 크기보다 작은 데이터를 저장하면 남는 공간이 생겨 내부 단편화가 발생합니다.
• 세그먼테이션: 가변 크기 세그먼트를 사용하므로 내부 단편화는 없지만, 여러 세그먼트가 메모리에 로딩되고 제거되면서 중간중간 빈 공간이 생겨 외부 단편화가 발생할 수 있습니다.

---

페이징의 장단점 요약

장점

• 가상 주소 공간을 물리 메모리에 연속적으로 배치할 필요가 없으므로 메모리 활용도가 높습니다.
• 외부 단편화가 발생하지 않아 메모리 관리가 용이합니다.
• 각 페이지에 접근 권한을 부여할 수 있어 메모리 보호 기능을 쉽게 구현할 수 있습니다.

단점

• 페이지 크기보다 작은 데이터를 저장할 때 내부 단편화가 발생할 수 있습니다.
• 가상 주소를 물리 주소로 변환하는 데 페이지 테이블을 참조해야 하므로 주소 변환 시간이 증가합니다.
• 페이지 테이블이 커질 경우, 그것을 저장하기 위한 메모리 공간이 과도하게 사용될 수 있습니다.