1. 페이징 메모리 관리 개요
1.1 페이징 개념
페이징(paging) 프로세스의 주소 공간을 0번지부터 페이지(page)로 불리는 고정크기로 나누고 물리 메모리도 0번지부터 페이지와 동일한 크기로 분할하여 프로세스의 각 페이지를 물리 메모리의 임의의 페이지에 분산 할당하는 메모리 관리 기법
페이징 기법의 기본 이론
- 주소 공간을 페이지크기로 나누고 페이지 경계를 고려하지 않고 코드, 데이터, 힙을 배치
- 프로세스의 주소공간은 논리주소공간 0번지부터 시작하여 이어져있지만 프로세스는 물리 메모리의 여러 프레임에 분산 할당되어있음
페이지 테이블은 프로세스마다 만들어지며, 프로세스에 속한 모든 스레드는 실행 시 프로세스의 페이지 테이블을 이용한다
페이징의 우수성
- 구현이 쉽다 : 메모리를 0번지부터 고정 크기의 페이지로 분할
- 이식성이 높다 : cpu에 의존적이지 않음, 다양한 컴퓨터 시스템에 동일한 방식으로 쉽게 구현
- 융통성이 높다 : 시스템에 다라 페이지 크기를 달리 설정 할 수 있음
- 외부 단편화가 없고 홀 선택 알고리즘을 실행할 필요가 없어 메모리 활용과 오버헤드에 우수하다
1.2 페이지 테이블
프로세스가 동적 할당 받을 때
프로세스의 힙과 스택 영역은 프로세스의 실행 중에 페이지가 생기기도 하고 소멸되기도 하면서 계속 변한다
char *p = (char*)malloc(200); // 프로세스의 힙 영역에서 200 바이트 동적 할당운영체제는 malloc(200) 함수가 요청한 200 바이트 메모리 할당을 위해 프로세스의 힙 영역에 페이지 5 할당, 비어있는 물리 프레임 2를 할당하여 프로세스 페이지 테이블에 기록
페이지 5 = 5 _ 4KB = 20480 물리주소 2 = 2 _ 4KB = 8192
*p = 'a'; // 페이지 5에 문자 'a' 기록cpu는 논리주소 20480 번지에 ‘a’를 저장하는것으로 실행하지만 실제로는 mmu에 의해 논리주소 20480이 물리주소 8129로 바뀌어 물리 메모리 8129번지에 ‘a’ 저장
free(p); // 할당받은 메모리 반환페이지 5 내에 할당된 200바이트 반환, 페이지 5와 프레임 2 모두 반환되어 다음 메모리 할당에 사용 페이지 테이블 항목 5에 null 기록
시스템 호출시 프로세스 페이지 테이블 활용
프로세스가 시스템호출을 실행하는 경우 커널 페이지 활용
커널 코드도 논리 주소로 되어있으며, 시스템 호출을 통해 커널 코드가 실행될 때 현재 프로세스의 페이지 테이블을 이용하여 물리 주소로 변환된다
1.3 단편화
세그멘테이션과 달리 페이징에선 외부 단편화가 발생하지 않음 내부 단편화의 크기도 극히 작음
2. 페이징의 주소 체계
2.1 페이징의 논리 주소
논리주소 = [ 페이지 번호(p), offset ]
2.2 논리 주소의 물리 주소 변환
p를 페이지 테이블 인덱스로 하여 페이지 테이블 항목을 찾으면 페이지 p가 할당된 프레임 f를 얻을 수 있음 페이지 p를 프레임 번호 f로 바꾸고 옵셋을 그대로 사용하면 논리 주소를 물리 주소로 바꿀 수 있음
2.3 페이징 구현
하드웨어 지원
- PTBR(Page Table Base Register)
- 현재 실행중인 프로세스의 페이지 테이블이 적재된 물리 메모리 주소를 가진 레지스터
- MMU 장치가 CPU 칩에 패키징
운영체제 지원
-
메모리 프레임을 동적으로 할당/반환하는 기능
-
페이지 테이블을 관리하는 기능
-
프로세스마다 페이지 테이블이 적재된 물리 주소를 PCB에 저장
-
프로세스가 스케줄되어 실행될 때마다 물리 주소를 PTBR로 이동
3. 페이지 테이블의 문제점과 TLB
3.1 페이지 테이블의 문제점
페이지 테이블로 인한 성능 저하와 공간 낭비
- 페이지 테이블은 메모리에 있어 cpu가 메모리를 액세스할 때마다 페이지 테이블 액세스 1번, 물리 메모리 액세스 1번으로 프로세스 실행 속도를 저하시킴
- 페이지 테이블 낭비 - 페이지 테이블 크기는 프로세스의 최대 크기에 맞춰 생성되지만 실제 프로세스 크기는 그보다 작아 메모리 낭비를 가져옴
3.2 두 번의 물리 메모리 액세스
메모리 액세스 = 페이지 테이블 항목 읽기 + 데이터 액세스 = 두 번 이루어짐
- cpu 가 메모리 액세스를 위해 논리 주소(페이지 2)를 발생
- mmu에 의해 논리주소 → 물리 주소로 변환 (PTBR이 페이지 테이블 항목 물리 주소 계산)
- 페이지 테이블 항목 읽기
- 데이터 액세스
배열 n[100]에 담긴 100개의 정수를 합하는 코드에서 진행되는 메모리 액세스
- n[i]를 읽기 위해 두 번 물리 메모리가 액세스 됨
- 배열 n이 모두 한 페이지에 들어 있으므로 배열 n을 읽는 동안 모두 페이지 테이블 항목 2를 액세스
[!개선책] 처음 n[0]을 읽을 때, 페이지 테이블 항목 2를 MMU내에 저장해두면 나머지 n[1] ~ n[99] 를 읽는 동안 물리 메모리에서 페이지 테이블 항목 2를 반복해서 읽을 필요가 없지 않을까?
3.3 TLB 이용
TLB
TLB(Translation Look-aside Buffer)는 CPU가 최근에 액세스 한 페이지 번호와 페이지가 적재된 프레임 번호의 쌍을 저장하는 캐시 메모리, 주소 변환용 캐시 라고도 부름
TLB = [페이지 번호 p, 프레임 번호 f]
- TLB는 논리 주소에 담긴 페이지 번호를 TLB 내의 각 항목을 순차적으로 비교하지 않고 모든 항목과 동시에 비교하여 단번에 프레임 번호를 출력함
- 내용-주소화 기억 장치 , 연관 메모리라고도 부름
TLB를 활용한 메모리 액세스
- 처음 TLB 미스가 발생하는 한 번의 경우에만 물리 메모리를 두 번 액세스
- 동일한 페이지를 연속하여 액세스 하는 동안 TLB 히트가 계속 발생
TLB와 참조의 지역성
- 순차 메모리 액세스 패턴을 가진 프로그램 = TLB 히트가 계속 발생 , 실행 성능 개선
- 참조의 지역성 - 코드나 데이터가 단시간 내 다시 액세스 될 가능성이 높기 때문
- 랜덤하게 메모리를 액세스 할 경우 = TLB 미스가 자주 발생 & 테이블 액세스 횟수가 많아짐
TLB 성능과 TLB 도달 범위(TLB reach / TLB coverage)
TLB 성능 = TLB 히트율 = CPU 메모리 액세스 횟수 대비 TLB 히트 횟수 비율
- 페이지 크기가 클수록 TLB 히트율이 높아지고 실행 성능이 향상됨, 내부 단편화 증가 = 메모리 낭비
TLB 도달 범위 : TLB 성능을 나타내는 지표
- TLB 항목 수 * 페이지 크기
TLB를 고려한 컨텍스트 스위칭 재정립
- cpu의 모든 레지스터들을 TBD에 저장
- 새 프로세스의 PCB에 저장된 페이지 테이블 주소를 CPU내 PTBR에 적재
- TLB 캐시의 모든 항목 제거
- 새로 스케줄된 스레드의 TCB에 저장된 레지스터 값들을 cpu에 적재 후 실행
- TLB 캐시 비우고 실행 → TLB 미스 발생
4. 심화 학습 : 페이지 테이블의 낭비 문제 해결
4.1 페이지 테이블의 메모리 낭비
페이지 테이블로 인한 메모리 낭비의 요인
- 페이지 테이블의 일부 항목만 사용
- 프로세스의 실제 크기는 주소 공간의 최대치에 이르지 못함
- 응용 프로그램이 페이지 테이블의 일부만 사용하여 페이지 테이블로 인한 메모리 낭비가 큼
- 프로세스마다 페이지 테이블 존재
4.2 역 페이지 테이블
역 페이지 테이블 구성
- 기존 페이지 테이블 - 프로세스 중심으로 프로세스의 각 페이지가 적재된 프레임 번호 저장
- 역 페이지 테이블 - 프레임을 중심으로 물리 메모리의 전체 프레임에 대해 각 프레임이 어떤 프로세스의 어떤 페이지에 할당되었는지 나타내는 테이블
역 페이지 테이블 항목 = [ 프로세스 번호(PID), 페이지 번호 P ]
논리 주소의 물리 주소로의 변환
논리 주소 = [ 프로세스 번호(PID), 페이지 번호(p), 옵셋(offset) ]
- 논리 주소 발생 → mmu가 pid와 p로 역 페이지 테이블 검색 후 일치하는 항목 탐색 → 항목이 발견되면 발견된 프레임 번호(f)와 옵셋을 연결하여 물리 주소를 만들고 물리 주소 발생
역 페이지 테이블의 크기
시스템에 설치된 물리 메모리의 크기에 따라 달라짐
역 페이지 테이블 크기 = 총 프레임 개수 * 한 항목의 크기 (프로세스 번호 + 페이지 번호)
역 페이지 테이블의 크기는 실행중인 프로세스의 개수와 관계없이 항상 동일하므로 실행중인 프로세스의 개수가 많은수록 더욱 효과적
역 페이지 테이블 구성
- 선형 역 페이지 테이블 방식
- 주소 변환 시 역 페이지 테이블 항목을 처음부터 하나씩 비교하여 일치하는 항목을 찾는 방식
- 비교에 많은 시간 소요
- 해시 역 페이지 테이블 방식
- 선형 역 페이지 테이블 방식을 개선한 방식
- 역 페이지 테이블을 해시 테이블로 만들고 해시 함수를 이용해 PID와 p를 키로 해싱하여 단번에 일치하는 항목을 찾고 물리 주소로 변환
4.3 멀티레벨 페이지 테이블
현재 사용중인 페이지들에 대해서만 페이지 테이블을 만드는 방식 = 페이지 테이블 낭비 감소
2-레벨 페이지 테이블 개요
- 현재 프로세스에게 할당된 페이지들에 대해서면 페이지 테이블이 만들어짐
- 불필요한 페이지 테이블 크기 감수
- 페이지 디렉터리 필요 : 페이지 테이블이 저장된 메모리 프레임의 번호를 기억하는 테이블
페이지 디렉터리와 페이지 테이블의 2단계 과정을 거쳐야 페이지가 저장된 프레임을 알 수 있도록 구성해 2-레벨 페이지 테이블이라고 부름
2-레벨 페이지 테이블 구성
논리 주소 = [ 페이지 디렉터리 인덱스, 페이지 테이블 인덱스, 옵셋 ]
2-레벨 페이지 테이블에서 논리 주소의 물리 주소 변환 과정
- 페이지 디렉터리 인덱스(논리주소 최상위 10비트)가 가리키는 항목을 읽고 페이지 테이블 프레임 번호를 알아낸다. 그리고 페이지 테이블을 물리 메모리로 읽어들인다
- 읽어들인 페이지 테이블에서 페이지 테이블 인덱스(논리 주소 중간 10비트)가 가리키는 페이지 테이블의 항목에 저장된 프레임 번호(f)를 읽는다.
- mmu가 프레임 번호와 논리 주소의 옵셋을 결합하여 물리 주소를 완성한다
2-레벨 페이지 테이블이 형성되는 과정
황기태, [명품 운영체제], 생능 출판사, 2023