[운영체제] 10. 페이징

1. 페이징의 개요

1) 연속 메모리와 Segmentation 기법의 단점

- 프로그램이 한 두 개 이상이면 문제가 발생

• Segment의 크기가 클 경우 메모리 할당이 가면 갈수록 어려워진다.
• 관리 자체가 더 힘들다 -> 검색 효율이 저하되며 메모리 운용 속도도 저하된다.

-> 이와 같은 문제로 페이징 기법이 등장했다.

2) 페이징이란?

- 고정 - 분할 방식을 이용한 가상 메모리 관리 기법이다.

- 프로세스의 주소 공간을 0번지부터 동일한 크기의 페이지로 나눈다.

- 물리 메모리도 역시 0번지부터 페이지 크기로 나누고 프레임이라 부른다.

- 페이지의 크기는 주로 4KB이다.

- 페이지 테이블은 각 페이지에 대해 페이지 번호와 프레임 번호를 1:1로 저장하는 테이블이다.

3) 페이징의 장점

1. 용이한 구현 : 고정 크기로 단순하게 분할한다.

2. 높은 이식성 : 페이징 메모리 관리를 위해 CPU에 의존하는 것이 없다.

3. 높은 융통성 : 시스템에 따라 응용에 따라 페이지 크기를 달리 설정할 수 있다.

4. 메모리 활용과 시간 오버레드 면에서 우수 : 외부 단편화가 일어나지 않고 내부 단편화도 매우 적게 발생한다.

-> 최대 내부 단편화 크기 = (단일 페이지 크기 - 1) * 페이지 개수 (일반적으로 마지막 페이지에서 발생)

 

다음은 페이징의 예제이다.

1. 페이지의 크기는 4KB이다.

2. 프로세스의 영역은 총 4가지 영역으로 이루어져 있다. (코드, 데이터, 힙, 스택)

1) 코드 영역은 페이지 0 ~ 2에 걸쳐 있다.

2) 데이터 영역은 페이지 2 ~ 3에 걸쳐 있다.

3) 힙 영역은 페이지 3 ~ 4에 걸쳐 있다.

4) 스택 영역은 맨 마지막 페이지 1개를 사용하고 있다.

-> 총 페이지의 크기는 4KB * 6 = 24KB이다.

3. 페이지 테이블은 주소 공간의 모든 페이지를 나타내는 항목을 포함하고 있다.

-> 현재는 6개의 항목만 사용된다. (페이지가 6개라)

4) 페이징 구현

1. 하드웨어 지원

- CPU의 지원 : 페이지 테이블이 있는 메모리 주소를 가진 레지스터 (PTBR)가 필요하다.

- MMU 장치 : 논리 주소의 물리 주소 변환, 페이지 테이블을 저장하고 검색하는 빠른 캐시를 포함한다.

2. 운영체제 지원

- 페이지 테이블 관리 기능 구현 : 동적 할당 및 반환, 빈 프레임 리스트 생성 관리 유지

5) 총 정리

1. 상황 : 32비트 CPU에서 페이지 크기가 4KB인 경우

1) 물리 메모리의 최대 크기는? -> 4GB (32비트 CPU의 최대 크기)

2) 프로세스 주소 공간의 크기 -> 물리 메모리 크기와 같음. 따라서 4GB

3) 프로세스 다 최대 페이지의 개수 -> 총 4GB에서 페이지의 크기인 4KB로 나눈다. -> 2^20개

4) 페이지 테이블의 크기 : 4바이트 * 2^20 = 2^22 바이트

---

2. 페이징 주소 관리

1) 주소 변환

페이징에서는 가상 주소를 VA = <P, O>로 표현한다.

- P : 페이지 번호

- O : 페이지의 처음 위치에서 해당 주소까지의 거리

 

Ex) 페이지 크기가 10B일 때 가상 주소 32번지?

VA = <3, 2>

2) 페이징의 논리 주소 구성

페이지의 크기가 4KB라면 페이지 내를 표현하기 위한 주소 크기는 12비트 크기이다. (4K = 2^12)

오프셋은 12비트로 표현이 된다.

 

32비트의 논리 주소 체계에서 나머지 상위 20비트는 페이지 번호가 된다.

 

ex) VA = 0x12345678의 경우

<P, O> = <12345, 678> 이다.

3) PTBR

- 프로세스가 페이지 테이블에 빠르게 접근하기 위한 레지스터이다. 각 페이지 테이블의 시작 주소는 PTBR에 저장된다.

-> 문맥 교환 시 PCB에 저장

---

3. 페이지 테이블 관리

1) 페이지 테이블 관리

메모리 관리자는 특정 프로세스가 실행될 때마다 해당 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환하는 작업을 반복한다.

- 페이지 테이블은 메모리 관리자가 자주 사용하는 자료구조이므로 반드시 빨리 접근되어야 한다.

- 따라서 페이지 테이블은 물리 메모리 영역 중 운영체제 영역의 일부에 모아둔다.

- 하지만 대다수 프로세스들이 모든 메모리 공간을 쓰지는 않는다. 그래서 비어 있는 공간도 존재한다.

- 또한 페이지 테이블도 스왑 대상으로 오버헤드가 증가한다.

2) TLB (Translation Look-aside Buffer)

- 논리 주소를 물리 주소로 바꾸는 과정에서 페이지 테이블을 읽어오는 시간을 없애거나 줄이는 기법 

- 여기서 사용되는 캐시가 주소 변환 캐시이다. 이 캐시는 MMU 안에 위치하여, 최근에 접근한 '페이지와 프레임 번호'의 쌍을 항목으로 저장하는 캐시 메모리이다.

- 연관 매핑 기법을 사용한다.

- Cost가 사아아앙당하다.

3) TLB 메모리 액세스

1. CPU로부터 논리 주소 발생

2. 논리 주소의 페이지 번호가 TLB로 전달

3. 페이지 번호와 TLB 내에 모든 항목을 동시에 비교

1) TLB에 페이지가 있는 경우, hit -> TLB에서 출력되는 프레임 번호와 offset 값으로 물리 주소 완성

2) TLB에 페이지가 없는 경우, miss -> MMU는 페이지 테이블로부터 프레임 번호를 읽어와서 물리 주소 완성, 미스한 페이지의 [페이지번호, 프레임번호] 항목을 TLB에 삽입

4) TLB 성능

1. TLB 참조의 지역성

- TLB는 참조의 지역성으로 인해 효과적인 전략이다.

- TLB 히트가 계속됨

- TLB를 사용하면, 랜덤 메모리 액세스나 반복이 없는 경우 실행 속도가 느리다. -> 미스도 계속됨

2. TLB의 성능을 높이는 방법

- TLB 히트율 높이기 -> TLB 항목 늘리기

- 페이지 크기 늘리기 (하지만 내부 단편화 가능성)

3. TLB reach = 페이지 크기 * TLB 개수

5) 페이지 테이블 메모리 낭비 문제

- 32비트 CPU 환경에서 프로세스당 페이지 테이블 크기

-> 아까 프로세스의 주소 공간이 100만 개 페이지로 구성되어 있다고 하였다.

-> 한 항목이 4바이트이면 프로세스당 페이지의 테이블은 2^20 * 4바이트 = 4MB이다.

-> 이게 한 두 개가 아니라면 ... 낭비가...

-> 이로써 해결 방법은 IPT와 multi-level page table이 있다.

6) IPT (역 페이지 테이블)

: 물리 메모리의 프레임 번호를 기준으로 테이블을 작성한다.

-> 역 페이지 테이블의 항목 수 = 물리 메모리의 프레임 개수

-> 역 페이지 테이블 항목 : [pid, 페이지 번호]

-> 역 페이지 테이블의 인덱스 : 프레임 번호

-> 논리 주소의 형식 = [pid, 페이지 번호, 옵셋]

-> 가상 주소 VA = <pid, 페이지 번호, offset>

-> 하지만 전체 검사가 필요하므로 속도는 저하된다.

-> 시스템에 1개 존재한다.

-> 역 페이지 테이블의 항목 개수 = 물리 메모리의 크기 / 프레임 크기

7) Multi - Level Page Table

: 페이지 테이블을 수십 ~ 수백 개의 작은 페이지 테이블로 나누고 여러 레벨로 구성

-> 현재 사용 중인 페이지에 대해서만 테이블을 만드는 형식

-> VA = <page directory index, page num, index>

MLPT

 

 

- 최대 메모리 소모량 : 페이지 디렉터리 메모리 + 페이지 테이블 메모리

ex1) 프로세스가 1000개의 페이지로 구성

-> 1개의 페이지 테이블로 매핑 가능 -> 4KB + 4KB 

ex2) 프로세스가 400MB

-> 프로세스 페이지 개수 = 400MB / 4KB = 100 * 1024개

-> 페이지 테이블 100개 매핑

-> 100 * 4KB + 4KB

8) 해시 페이지 테이블

- 64비트 환경을 위한 페이지 테이블 관리 기법

---

4. 메모리 접근 권한

메모리 접근 권한은 메모리의 특정 번지에 저장된 데이터를 사용할 수 있는 권한이다. (r : read, w : write, x : execute)

1) 프로세스의 영역 별 메모리 접근 권한

1. 코드 영역

: 자기 자신을 수정하는 프로그램은 없기에 읽기와 실행만 가짐

2. 데이터 영역

: 데이터는 크게 읽거나 쓸 수 있는 데이터와 읽기만 가능한 데이터로 나눌 수 있다. (상수는 읽기만)

2) 메모리 접근 권한까지 고려한 페이지 테이블

- 페이지마다 접근 권한이 다르기 때문에 페이지 테이블의 모든 행에는 메모리 접근 권한과 관련된 권한 비트를 추가한다.

- 하지만 페이지 테이블이 커진다.

-> 이를 해결하기 위한 방법으로 Segmentation - Paging Hybrid Approach가 있다.

Segmentation - Paging Hybrid Approach

세그멘테이션과 페이징 기법을 혼용해서 사용하는 방법이다.

---

5. 캐시 메모리 (매핑)

1) 캐시 메모리

- 캐시 메모리는 CPU와 메모리 사이의 속도 차이를 줄이기 위한 고속 메모리이다.

- 프로그래머는 캐시를 조작할 수 없다. 명령어가 없기 때문이다.

- Cache Hit And Miss

-> 적중률 = hit 횟수 / 전체 참조 횟수

2) 캐시의 인덱싱

- 캐시는 블록 단위로 구성되어 있다.

- 각각의 블록은 데이터를 담고 있으며 주소값을 키로써 접근

- 블록의 개수와 블록의 크기가 캐시의 크기를 결정한다.

- 주솟값 전체를 키로 사용하지 않고 그 일부만을 사용한다. -> 인덱스 중복 위험

3) Tag Matching

- 인덱스의 충돌을 줄이기 위해 주소값의 일부를 태그로 사용한다.

- 태그가 추가됨으로써 더 많은 공간이 필요하다.

- 캐시 사이즈는 변함이 없지만 오버헤드가 증가한다.

- 태그 길이가 짧기는 하다. 또한, 구현이 단순하고 속도가 빠르다.

- 하지만, 적중률이 낮다. 따라서, 대용량 캐시 메모리일 경우에만 직접 사상 방식을 이용한다.

4) 완전 연관 사상

장점 : 직접 연관 사상보다 적중률이 높다.

단점 : 태그의 길이가 길고 속도가 느리다. 또한, 하드웨어가 추가로 필요하다.