09. 페이징 메모리 관리

1 페이징 메모리 관리 개요

1.1 페이징 개념

• 프로세스의 주소 공간을 0번지부터 페이지(page)로 불리는 고정 크기로 나누고 물리 메모리 역시 0번지부터 페이지와 동일한 크기로 분할하여, 프로세스의 각 페이지를 물리 메모리의 임의의 페이지에 분산 할당하는 메모리 관리 기법
• 물리 메모리에서 페이지 크기의 메모리 블록을 프레임(frame), 페이지 프레임(page frame), 혹은 물리 페이지(physical page)라고 부른다.
• 페이지 테이블은 프로세스마다 만들어지며, 프로세스에 속한 모든 스레드는 실행 시 프로세스의 페이지 테이블을 이용한다.

페이징의 우수성

분할 할당의 대표적인 두 방법(세그먼테이션, 페이징) 중 페이징이 여러 면에서 우수하다. 그 이유는

1. 구현이 쉽다. 메모리를 0번지부터 고정 크기의 페이지로 분할
2. 이식성이 높다. CPU에 의존적이지 않기 때문
3. 융통성이 높다. 시스템에 따라 혹은 응용에 따라 페이지의 크기를 달리 설정 가능
4. 세그먼테이션에서 발생하는 외부 단편화가 없고 홀 선택 알고리즘을 실행할 필요가 없어 메모리 활용과 시간 오버헤드 면에서 훨씬 우수하다. 물론 내부 단편화가 발생하지만, 그 크기는 매우 작다.

1.2 페이지 테이블

4GB의 주소 공간을 가지는 프로세스에 대해 프로세스의 주소 공간과 페이지 테이블, 물리 메모리의 관계 사례 페이지 = 4kb

프로세스가 동적 할당 받을 때

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

시스템 호출시 프로세스의 페이지 테이블 활용

커널 코드도 논리 주소로 되어 있으며, 시스템 호출을 통해 커널 코드가 실행될 때 현재 프로세스의 페이지 테이블을 이용하여 물리 주소로 변환

페이지와 페이지 테이블에 대한 정리

32비트 CPU를 가진 컴퓨터, 페이지 크기 4KB

• 물리 메모리의 최대 크기는 얼마인가?
  • 32비트 CPU → $2^{32}$바이트 = 4GB
• 프로세스의 주소 공간 크기는 얼마인가?
  • 프로세스가 차지할 수 있는(접근할 수 있는) 최대 공간
  • 프로세스의 주소 공간은 $2^{32}$바이트 = 4GB
  • 물리 메모리 크기에 상관없음
• 한 프로세스는 최대 몇 개의 페이지로 구성되는가?
  • 프로세스 주소 공간을 페이지 크기로 나눈값
  • $4GB/4KB=2^{32}/2^{12}=2^{20}개=1M개=약100만개$
• 프로세스 당 하나의 페이지 테이블이 있다. 페이지 테이블의 크기는?
  • 프로세스는 최대 총 $2^{20}$개의 페이지로 구성
  • 페이지 테이블은 모든 페이지에 대해 물리 프레임의 번호를 저장하므로 $2^{20}$개 항목을 확보 해야함
  • 페이지 테이블 항목에는 물리 프레임 번호만 저장되고 프레임 번호가 32비트(4바이트)로 구성된다고 했을때
  • $2^{20}개\times 4바이트=4MB$
• 응용프로그램이 하나의 프로세스라고 할 때 응용프로그램의 최대 크기, 즉 개발자가 작성할 수 있는 프로그램의 최대 크기는?
  • 운영체제가 설정한 사용자 공간의 크기
• 페이지 테이블은 어디에 존재하는가?
  • 메모리에 저장
  • CPU칩 내에 페이지 테이블 베이스 레지스터(page table base register, PTBR)를 두어 현재 실행중인 프로세스의 페이지 테이블이 저장된 메모리의 주소를 저장
• 커널 코드가 논리 주소로 되어 있는가 물리 주소로 되어 있는가?
  • 논리주소로 컴파일되어 있음

1.3 단편화

• 외부 단편화 X
• 내부 단편화 - 매우 작음

2 페이징의 주소 체계

2.1 페이징의 논리 주소

• 논리 주소 = [ 페이지 번호(p), 옵셋(offset)]
• 옵셋은 페이지 내에서의 상대 주소
• 페이지 크기가 4KB(=$2^{12}$)일때
  • 페이지 내의 각 바이트 주소(옵셋 주소) → 12 비트
  • 32비트 논리 주소에서 하위 12비트가 페이지 내 옵셋 주소, 상위 20비트가 페이지 번호

2.2 논리 주소의 물리 주소 변환

2.3 페이징 구현

하드웨어 지원

• PTBR(Page Table Base Register) - 현재 실행 중인 프로세스의 페이지 테이블이 적재된 물리 메모리 주소를 가지는 레지스터
• MMU

운영체제 지원

• 페이지 테이블 관리
• 각 프로세스마다 페이지 테이블이 적재된 물리 메모리 주소를 PCB에 저장하고 프로세스가 스케줄되어 실행될 때마다 PCB로부터 PTBR로 이동

3 페이지 테이블의 문제점과 TLB

3.1 페이지 테이블의 문제점

1. 페이지 테이블은 메모리에 저장하는데 CPU가 메모리를 액세스할 때마다 페이지 테이블 액세스 1번, 데이터의 물리 메모리 액세스 1번으로, 물리 메모리를 2번 액세스하여 프로세스의 실행 속도 저하
2. 페이지 테이블의 크기는 프로세스의 최대 크기에 맞추어 생성되지만, 실제 프로세스의 크기는 그에 못 미치기 때문에, 페이지 테이블의 많은 항목들이 비어 있어 메모리 낭비를 가져온다

3.2 2번의 물리 메모리 액세스

실제 CPU의 메모리 액세스 과정

메모리 액세스 = 페이지 테이블 항목 읽기 1번 + 데이터 액세스 1번

1. CPU가 메모리 액세스를 위해 논리 주소 발생
2. MMU가 페이지 테이블 항목의 물리 주소 계산 - PTBR + 페이지 번호
3. 페이지 테이블 항목 읽기
4. 데이터 액세스

3.3 TLB를 이용한 2번의 물리 메모리 액세스 문제 해결

TLB(Translation Look-aside Buffer)

• MMU 내부에 위치
• ‘CPU가 최근에 액세스한 페이지 번호와 페이지가 적재된 프레임 번호의 쌍’을 저장하는 캐시 메모리
• TLB의 항목 = [페이지 번호 p, 프레임 번호 f]
• 주소 변환용 캐시(address translation cache) 라고도 함
• 모든 항목과 동시에 비교하여 단번에 프레임 번호 출력
• TLB의 크기가 작기 때문에 최근에 액세스한 소수의 ‘페이지와 프레임’의 번호를 저장

TLB를 활용한 메모리 액세스

TLB를 사용하는 경우, 히트가 발생하면 바로 주소 변환이 일어나므로 1번만 물리 메모리를 액세스 한다.

TLB와 참조의 지역성

• 순차 메모리 액세스 패턴을 가진 프로그램에게 매우 효과적
  • 참조의 지역성(locality of reference) - 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복 액세스
• 랜덤하게 메모리를 액세스하는 경우 TLB 로 얻는 이득이 크지 않음

TLB 성능과 TLB 도달 범위(TLB reach/TLB coverage)

성능

• TLB 히트율(TLB hit ratio) - CPU의 메모리 액세스 횟수에 대한 TLB 히트 횟수의 비율
  • 항목 수와 페이지의 크기에 비례
  • 항목수↑ → 성능↑ → 비용↑
  • 페이지 크기↑ → 성능↑ → 내부 단편화↑
  • 페이지의 크기는 디스크 입출력 성능 향상을 위해 커지는 추세
• TLB 도달 범위(TLB reach) - TLB 캐시의 항목 수와 페이지 크기가 모두 고려된 성능 지표
  • TLB 캐시의 모든 항목이 채워졌을 때 TLB 미스 없이 작동하는 메모리 액세스의 범위로 정의
  • TLB 항목 수 $\times$ 페이지 크기

TLB를 고려한 컨텍스트 스위칭 재정립

• 동일한 프로세스의 다른 스레드가 실행 - TLB 항목 교체 불필요
• 다른 프로세스의 스레드로 컨텍스트 스위칭 되는 경우
  1. CPU의 모든 레지스터들을 TCB에 저장
  2. 새 프로세스의 PCB에 저장된 페이지 테이블의 주소를 PTBR에 적재
  3. TLB 캐시의 모든 항목 제거
  4. 새로 스케줄된 스레드의 TCB에 저장된 레지스터 값들을 CPU에 적재한 후 실행

4 심화 학습: 페이지 테이블의 낭비 문제 해결

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

• 페이지 테이블의 일부 항목만 사용
• 프로세스마다 페이지 테이블 존재

4.2 역 페이지 테이블(IPT, inverted page table)

역 페이지 테이블의 구성

• 시스템에 1개
• 프레임을 중심으로 물리 메모리의 전체 프레임에 대해 각 프레임이 어떤 프로세스의 어떤 페이지에 할당되었는지 나타내는 테이블
• [ 프로세스 번호(PID), 페이지 번호 p ]

논리 주소의 물리 주소로의 변환

• 논리 주소 = [ 프로세스 번호(PID). 페이지 번호(p), 옵셋(offset) ]

역 페이지 테이블의 크기

• 시스템에 설치된 물리 메모리의 크기에 따라 달라진다
• 실행중인 프로세스의 개수와 관계없이 항상 동일
• 실행 중인 프로세스의 개수가 많을수록 효과적
• 예) 4GB의 물리 메모리가 설치된 시스템
  • $역페이지테이블의크기=2^{20}개\times 8바이트=8MB$

역 페이지 테이블 구현

• 선형 역 페이지 테이블(linear inverted page table)
  • 처음부터 하나씩 비교하여 일치하는 항목 찾기
• 해시 역 페이지 테이블(hashed inverted page table)
  • 해시 테이블로 만듬
  • PID와 p를 키로 해싱하여 단번에 일치하는 항목을 찾기

4.3 멀티레벨 페이지 테이블

• 프로세스가 현재 사용 중인 페이지들에 대해서만 페이지 테이블을 만드는 방식
• 페이지 테이블을 수십~수백 개의 작은 페이지 테이블로 나누고 이들을 계층적으로 구성하는 방법
• 32비트 OS에서는 2-레벨과 3-레벨 사용
• 64비트 OS에서는 4-레벨 또는 5-레벨 까지 사용

2-레벨 페이지 테이블 개요

• 프로세스의 주소 공간을 1024개의 페이지들로 나눈다
• 1024개의 페이지를 1개의 페이지 테이블로 나타낸다
• 페이지 테이블의 항목은 1024개
• 각 페이지 테이블이 저장된 메모리 프레임의 번호를 기억하는 페이지 디렉터리를 사용
• 페이지 디렉터리의 크기 4KB로 1개의 프레임에 저장
• 페이지 디렉터리와 페이지 테이블의 2단계 과정을 거쳐야하기 때문에 2-레벨 페이지 테이블이라고 함

2-레벨 페이지 테이블의 구성

논리 주소 = [ 페이지 디렉터리 인덱스, 페이지 테이블 인덱스, 옵셋 ]

2-레벨 페이지 테이블에서 논리 주소의 물리 주소 변환 과정

1. 페이지 디렉터리 인덱스가 가리키는 페이지 디렉터리 항목을 읽고, 이 항목에 기록된 페이지 테이블의 프레임 번호 확인. 그리고 페이지 테이블을 물리 메모리로 읽어 들인다.
2. 읽어 들인 페이지 테이블에서, 페이지 테이블 인덱스가 가리키는 페이지 테이블의 프레임 번호를 읽는다.
3. MMU는 프레임 번호와 논리 주소의 옵셋을 결합하여 물리 주소를 완성한다.

2-레벨 페이지 테이블이 형성되는 과정

페이지 디렉터리는 페이지 테이블의 목록이라고 생각

1. 프로세스가 실행될 때, 운영체제는 페이지 디렉터리 1개와 페이지 테이블 1개를 생성 후 프레임에 적재, 빈 프레임을 찾아 첫 번째 페이지를 적재, 페이지 테이블1의 첫 번째 항목에 프레임 번호 기록
2. 운영체제는 빈 프레임을 찾아 페이지 1을 적재하고 페이지 테이블 1의 두 번째 항목에 기록
3. 그 후 계속해서 프로세스에게 페이지를 할당하여 페이지 테이블1의 1024개 항목을 다 사용하면, 새로운 페이지 테이블 2를 생성하고 프레임에 적재. 이후 페이지 디렉터리의 두 번째 항목에 기록. 이후 1번 과정과 같이 프레임을 할당, 페이지 테이블 2의 첫 번째 항목에 기록
4. 스택 사용시

2-레벨 페이지 테이블의 크기

• 최대 메모리 소모량 = $4MB+4KB$
• 프로세스가 1000개의 페이지를 사용 할 때 = 1개의 페이지 디렉터리 + 1개의 페이지 테이블 = $4KB+4KB=8KB$
• 400MB의 프로세스 = 1개의 페이지 디렉터리 + 100개의 페이지 테이블 = $4KB+100\times 4KB=404KB$

Ref.

황기태, “명품 운영체제”, (주)생튼출판사(2021)