페이징 메모리 관리

페이징 기법의 개념

페이지와 프레임

• 프로세스의 주소 공간(논리주소)을 0번지부터 동일한 크기의 페이지로 나눔 -> 페이지(page)
• 물리 메모리 역시 0번지부터 페이지와 동일한 크기대로 나눔 -> 프레임(frame)
  - 페이지와 프레임에 번호 할당
  - 페이지의 크기는 주로 4KB이며 운영체제마다 다르게 설정 가능(2^n으로 설정 가능, 4KB, 8KB, 16KB.....)
  - 페이지 테이블 : 각 페이지에 대해 페이지 번호와 프레임 번호를 1:1매칭하여 저장하는 테이블

 

 

페이징 기법

• 프로세스의 주소공간(논리주소)와 물리메모리(물리주소)를 페이지, 프레임 단위로 분할하고 프로세스의 각 페이지를 물리 메모리의 프레임에 분산 할당하여 관리하는 기법
  - 프로세스의 주소 공간(논리주소) : 0부터 시작하여 연속적인 주소 공간
  - 프로세스마다 페이지 테이블 존재
  - MMU로 논리 주소의 물리 주소 변환
  - 물리 메모리의 빈 프레임들을 리스트로 관리 필요 -> 프레임 할당 알고리즘
  - 내부 단편화 발생
  - 통상적으로 세그멘테이션보다 우수

 

 

페이징의 우수성

• 용이한 구현
  - 메모리를 0번부터 고정크기 페이지 단위로 단순 분할하기 때문에 구현하기 쉬움
• 높은 이식성
  - 페이징 메모리 관리를 위해 CPU의 의존성이 적으므로(특수 레지스터 불필요) 다양한 컴퓨터 시스템에 쉽게 이식 가능 (세그멘테이션은 base, limit 레지스터가 필수적이지만 페이징은 현대 커퓨터의 표준화 하에 존재하는 기존 하드웨어만으로 동작 가능, MMU, TLB, PTBR 등)
• 높은 융통성
  - 시스템이나 응용에 따라 페이지 크기를 다르게 설정 가능
• 메모리 활용과 시간적 오버헤드면에서 우수
  - 외부 단편화 없으며 이로인해 홀 선택 알고리즘 실행이 필요없음
  - 내부 단편화는 발생하지만 4KB크기의 페이징 시스템일 때, 메모리의 마지막 4KB프레임내부에서만 발생하므로 무시될 수 있을정도로 작음

 

 

페이지 할당 예시

char *p = (char*)malloc(200); // 힙 영역에서 200바이트 동적 할당

 

- 200바이트여도 일단 1개의 페이지를 할당(4KB)
- 예시로 논리페이지 5를 할당받고 물리프레임 2를 할당 받았다면,
    논리 페이지 5의 주소 : 5 * 4KB = 20KB = 20 * 1024 = 20480번지
    물리 프레임 2의 주소 : 2 * 4KB = 8KB = 8 * 1024 = 8192번지
- malloc(200)은 논리주소 20480(페이지 5의 주소)을 리턴

 

*p = 'a';

- 프로세스 내에서 20480 논리 주소 번지에 'a'를 저장
- 논리주소 20480이 MMU에 의해 물리주소 8192로 바뀌어 물리주소 8192번지에 'a'저장

 

free(p);

- 할당받은 논리주소 20480부터 200바이트를 반환
- 페이지 5에는 할당받았던 200바이트만큼만 차지했으므로 페이지 5는 완전히 비게 됨
- 페이지 5가 비었으므로 페이지5와 프레임2가 모두 반환

 

 

 

 

페이징 시스템에서 시스템 호출

• 커널 코드도 논리 주소로 이루어짐
  - 논리 주소 내의 사용자 공간에서 커널 공간에 진입
  - 커널 공간의 논리 주소와 현재 프로세스의 페이지 테이블을 이용하여 물리주소로 변환하고, 물리 메모리의 커널 코드 사용

 

 

페이징 시스템에 대한 정리

• 물리 메모리의 최대 크기
  - 물리 주소의 범위는 32비트 시스템 기준으로 0 ~ 2^32 -1 
  - 한 주소당 1바이트의 크기이므로 물리 메모리의 최대 크기는 2^32 * 1byte = 4GB
• 프로세스의 주소 공간(논리 주소)의 크기
  - 물리 주소의 범위는 메모리 크기에 따라 달라지지만(1GB, 2GB, 4GB...)
  - 32비트 시스템에서 논리 주소는 메모리 크기에 상관없이 4GB로 고정
• 한 프로세스의 최대 페이지 개수
  - 1페이지가 4KB일 경우 4GB / 4KB = 2^32 / 2^12 = 2^20개 = 1M개 = 약 100만개
• 프로세스당 하나의 페이지 테이블이 있으며, 이 때 페이지 테이블의 크기
  - 페이지 테이블 속 한 항목의 크기가 32비트(4byte)일 때
  - 4byte * 2^20 = 2^2 * 2^20 = 2^22byte = 4MB
• 개발자가 작성 가능한 프로그램의 최대 크기
  - 운영체제가 설정한 사용자 공간의 크기와 동일
• 페이지 테이블의 형태
  - 대부분의 항목이 비어있는 희소 테이블(Sparse table)이며 낭비가 심하므로 줄이는 기법이 필요
• 페이지 테이블의 저장공간
  - 메모리에 저장
• 커널 코드의 주소 형태
  - 커널 코드 역시 논리주소로 이루어져 있으며, 현 프로세스의 페이지 테이블을 이용하여 커널 코드의 물리주소에 접근

 

 

 

 

페이징의 논리 주소 구성

• [페이지 번호(p), 오프셋(offset)]
  - 페이지 크기가 4KB(2^12)라면, 페이지 내 각 바이트 주소는 12비트
  - 고로 페이지 내의 위치를 나타내는 오프셋의 크기는 12비트
• 32비트 논리주소 체계에서
  - 상위 20비트는 페이지 번호(2^20개의 페이지로 이루어져있으므로)
  - 하위 12비트는 오프셋(4KB의 페이지 내에서 각 바이트들의 위치 4096개를 나타낼 수 있는 2^12비트)
• 물리주소로 변환시
  - 페이지 번호는 페이지 테이블을 활용하여 프레임 번호로 변환됨
  - 오프셋은 그대로 카피되어 프레임 번호 뒤에 붙음

 

 

페이징 구현

• 하드웨어적 지원
  - CPU의 지원 : CPU에 페이지 테이블이 있는 물리 메모리 주소를 가진 레지스터가 필요 (Page Table Base Register, PTBR)
  - MMU 필요 : 논리 주소의 물리 주소 변환 장치, CPU 패키지 내부에 내장
• 운영체제의 지원
  - 물리프레임의 동적 할당 / 반환 : 물리 메모리의 빈 프레임 리스트를 생성, 관리하며 프로세스의 생성 / 소멸에 따라 동적으로 프레임 할당 / 반환
  - 페이지 테이블 관리 기능 구현 : 프로세스마다 페이지 테이블 생성, 관리. 페이지 테이블이 저장된 물리 메모리 주소를 PCB에 저장
• 프로세스 실행 시
  - 페이지 테이블의 물리 메모리 주소를 CPU의 PTBR에 적재

 

 

 

 

페이지 테이블의 문제점

• 문제 1
  - 한 번 메모리 액세스를 할 때 실제로는 두 번 메모리 액세스가 일어남
  - 페이지 테이블은 몇 MB의 비교적 큰 크기로 메모리에 저장됨
  - CPU가 메모리에 액세스 할 때 마다 페이지 테이블, 데이터 액세스 총 2번의 물리메모리 접근이 발생하여 속도저하
  - 이는 TLB 사용으로 해결
• 문제2
  - 페이지 테이블의 낭비
  - 페이지 테이블은 프로세스의 최대 크기를 기준으로 생성함
  - 프로세스의 실제 크기는 보통 페이지 테이블을 가득 채우지 못하므로 페이지 테이블 내 대부분의 항목은 비어있음
  - 이는 멀티레벨 페이지 테이블로 해결

 

 

TLB 이용

TLB (Translation Look-aside Buffer)로 주소 변환 캐시라고 불림(address translation cache)

- 최근에 접근한 페이지번호와 프레임번호를 한 쌍으로 저장하는 캐시 메모리

• 위치
  - 현대 컴퓨터에서 MMU내부에 존재
• TLB캐시의 구조와 특징
  - [페이지 번호p, 프레임 번호f] 의 형태쌍으로 저장
  - 페이지 번호로 전체 캐시를 동시에 고속 검색 후 프레임 번호를 출력(캐시 전체를 한번에 검색)
  - 고가이며, 크기가 작음(64~1024개 정도 저장)

TLB를 활용한 메모리 액세스 과정

1. CPU로부터 논리 주소 발생
2. 논리 주소의 페이지 번호가 TLB로 전달
3. 페이지 번호와 TLB 내 전체 항목과 동시 비교
   - TLB내에 페이지 번호가 있는 경우 TLB Hit : TLB에서 출력되는 프레임 번호와 오프셋의 쌍으로 물리 주소 완성
   - TLB내에 페이지 번소가 없는 경우 TLB Miss : TLB는 Miss 신호를 발생시키고 MMU는 페이지 테이블로부터 프레임 번호를 읽어와 물리 주소 완성
   - TLB로 전달했던 페이지 번호와 Miss하여 메모리에서 읽어온 프레임번호를 합친 쌍을 TLB에 삽입하여 저장

 

TLB 참조의 지역성

• TLB는 참조의 지역성으로 인해 효과적인 전략
• TLB를 사용하면 순차 메모리 액세스시 실행 속도가 매우 빠름
  - TLB히트가 계속되므로
• TLB를 사용하면 랜덤 메모리 액세스나 배열과 같이 반복이 없는 경우 실행 속도 느림
  - TLB 미스가 자주 발생하며 TLB의 항목이 자주 교체

 

TLB의 성능

• TLB 히트율 높이기 -> TLB 항목 늘리기(TLB는 cache이므로 매우 비쌈, 비용이 증가)
• 페이지 크기로는
  - 페이지가 클수록 TLB 히트 증가 -> 실행 성능향상
  - 하지만 페이지가 클수록 내부 단편화 증가 -> 메모리 낭비
  - 페이지가 크면 장단점이 동시에 존재하므로 선택의 문제
  - 하지만 내부 단편화가 증가하여도 다른 방식보다는 미미하므로 현대에서는 페이지가 커지는 추세 -> 디스크 입출력의 성능 향상을 위해

 

TLB reach
- TLB의 도달 범위로, TLB가 채워졌을 때 Miss없이 작동하는 메모리 액세스 범위
- TLB 항목 수 * 페이지 크기

 

 

 

 

페이지 테이블의 메모리 낭비

32비트 CPU환경에서,

• 프로세스 주소 공간(논리 주소)
  - 4GB / 4KB = 2^32 / 2^12 = 2^20 = 약 100만개의 페이지
• 프로세스당 페이지 테이블 크기
  - 한 항목이 4byte라면, 2^20 * 4byte = 2^20 * 2^2 = 2^22byte = 4MB
• 10MB의 메모리만 사용하는 프로세스가 있다면
  - 실제 사용되는 페이지 테이블 항목은 10MB / 4KB = (10 * 2^20) / 2^12 = 10 * 2^8 = 2560개
• 페이지 테이블 항목 사용률
  - 2560 / 2^20 = 0.00244
  - 매우 낮음
• 페이지 테이블 낭비 해결책
  - 역 페이지 테이블(Inverted Page Table, IPT)
  - 멀티 레벨 페이지 테이블(Multi-Level Page Table)

 

 

역 페이지 테이블(Inverted Page Table, IPT)

- 물리 메모리 전체 프레임에 대해, 각 프레임이 어떤 프로세스의 어떤 페이지에 할당되었는지를 나타내는 테이블

• 시스템에 1개의 역 페이지 테이블을 둔다
  - 역 페이지 테이블의 항목 수 = 물리 메모리의 프레임 개수
• 역 페이지 테이블의 항목
  - [PID, 페이지 번호p]
• 역페이지 테이블의 인덱스
  - 프레임 번호
• 역 페이지 테이블을 사용할 때 논리 주소 형식
  - [PID, 페이지 번호p, 오프셋]
• 역 페이지 테이블을 사용한 주소 변환
  - 논리 주소에서 (PID, 페이지 번호p)로 역 페이지 테이블 검색
  - 일치하는 항목을 발견하면 항목 번호가 바로 프레임번호
  - 프레임 번호와 오프셋을 연결하면 물리주소
  - 물리 프레임을 기준으로 생성된 테이블이므로 각 항목이 물리 프레임을 암시하게 되어 물리프레임 번호는 항목에 담을 필요가 없음
• 페이지 테이블은 프로세스별로 있어야 하지만, 역 페이지 테이블은 시스템에 딱 1개만 있으므로 메모리 절약 가능

 

역페이지 테이블 크기

• 프로세스 번호 : 4byte
• 페이지 번호 : 4byte
  - 프로세스 번호와 페이지 번호의 쌍이 한 항목이므로 한 항목의 크기는 8바이트
• 역페이지 테이블의 항목 수 = 물리 메모리의 크기 / 프레임 크기
  - 역페이지 테이블의 항목 수 = 4GB / 4KB = 2^20개 = 약 100만개
• 역 페이지 테이블 크기는 컴퓨터에 설치된 물리 메모리의 크기에 따라 달라짐
  - 물리 메모리의 크기가 4GB, 프레임이 4KB, 한 항목의 크기가 8바이트라면
  - 역 페이지 테이블의 크기 = 2^32 / 2^12 * 8byte = 8MB
  
• 기존 페이지 테이블과의 비교
  - 4GB의 물리 메모리에서 10개의 프로세스가 실행 중일 때
  - 기존 페이지 테이블 = 4MB * 10개 = 40MB
  - 역 페이지 테이블 = 8MB
  -> 기존의 1/5 수준

 

 

 

멀티 레벨 페이지 테이블

- 프로세스가 현재 사용 중인 페이지들에 대해서만 페이지 테이블을 만드는 방식 -> 기존 페이지 테이블 낭비를 줄임

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

- 오늘날 대부분의 운영체제에서 사용

 

 

2 Level 멀티 레벨 페이지 테이블 구성

• 논리 주소 구성
  - [페이지 디렉토리 인덱스, 페이지 테이블 인덱스, 오프셋]
  - 페이지 크기 4KB
  - 논리 주소 상위 20비트 : 전 10비트는 페이지 디렉토리 인덱스, 후 10비트는 페이지 테이블 인덱스
  - 논리 주소 하위 12비트 : 오프셋

 

2 Level 멀티 레벨 페이지 테이블의 크기

• 2 Level 멀티 레벨 페이지 테이블의 프로세스 하나에 대한 최대 메모리 소모량
  - 페이지 디렉토리 테이블 1개(4KB) + 최대 1024개의 페이지 테이블(페이지 테이블 1개는 4KB)
  - 4KB + 1024 * 4KB = 4KB + 4MB
• 예시 - 프로세스가 1000개의 페이지로 구성되는 경우(4MB의 프로세스)
  - 1000개의 페이지는 1개의 페이지 테이블에 매핑 가능(4KB)
  - 메모리 소모량 = 페이지 디렉토리(4KB) + 1개의 페이지 테이블(4KB) = 8KB
• 예시2 - 프로세스가 400MB인 경우
  - 프로세스 페이지의 개수는 400MB / 4KB = 400 / 4096 = 100 / 1024 개
  - 1024개는 4KB, 즉 1개의 페이지 테이블이므로 총 100개의 페이지 테이블 필요
  - 메모리 소모량 = 4KB + 100 * 4KB = 404KB
• 결론
  - 기존 페이지 테이블의 경우, 프로세스의 크기에 관계없이 프로세스당 4MB가 소모
  - 2 Level 멀티 레벨 페이지 테이블의 경우, 페이지 테이블로 인한 메모리 소모를 확연히 줄일 수 있음