[운영체제] 9. 페이징 메모리 관리

황재성·2022년 6월 3일

메모리 관리 운영체제 페이징

운영체제

목록 보기

9/9

페이징 메모리 관리 개요

페이징 개념

1) 페이지와 프레임

프로세스의 주소 공간을 0번지부터 동일한 크기의 페이지로 나눔
물리 메모리 역시 0번지부터 페이지 크기로 나누고, 프레임이라고 부름
코드, 데이터, 스택 등 프로세스의 구성 요소에 상관없이 고정 크기로 분할한 단위
페이지와 프레임에 번호 붙임
페이지의 크기
- 주로 4KB, 운영체제마다 다르게 설정 가능
페이지 테이블
- 각 페이지에 대해 페이지 번호와 프레임 번호를 1:1로 저장하는 테이블

2) 페이징 기법

프로세스의 주소공간과 물리 메모리를 페이지 단위로 분할하고, 프로세스의 각 페이지를 물리 메모리의 프레임에 분산 할당하고 관리하는 기법
프로세스의 주소공간
- 선형적인 주소공간(0에서 시작하여 연속적인 주소공간)
프로세스마다 페이지 테이블 있음
논리 주소의 물리 주소 변환 : MMU에 의해
물리 메모리의 빈 프레임 리스트 관리 필요
- 프레임 할당 알고리즘 : 빈 프레임 중에서 선택알고리즘 필요
내부 단편화 발생
세그먼테이션보다 우수

페이징의 우수성

용이한 구현
- 메모리를 0번지부터 고정 크기로 단순히 분할하기 때문
높은 이식성
- 페이징 메모리 관리를 위해 CPU에 의존하는 것 없음
- 다양한 컴퓨터 시스템에 쉽게 이식 가능
높은 융통성
- 시스템에 따라 응용에 따라 페이지 크기 달리 설정 가능
메모리 활용과 시간 오버헤드면에서 우수
- 외부 단편화 없음
- 내부 단편화는 발생하지만 매우 작음
- 홀 선택 알고리즘을 실행할 필요 없음

페이지와 페이지 테이블(1)

[설명]

4GB의 주소 공간을 가지는 프로세스
페이지 크기 4KB
프로세스
- 코드 : 페이지0 ~ 페이지2에 걸쳐 있음
- 데이터 페이지2 ~ 페이지3에 걸쳐 있음
- 힙 : 페이지3 ~ 페이지4에 걸쳐 있음
- 스택 : 사용자 공간의 맨 마지막 페이지에 할당, 1페이지 사용
현재 프로세스는 6개의 페이지를 사용하고 있음
- 프로세스의 크기 : 6 x 4KB = 24KB
페이지 테이블
- 페이지 테이블은 주소공간의 모든 페이지를 나타낼 수 있는 항목을 포함
- 현재 6개의 항목만 사용. 대부분의 항목은 비어 있음

페이지와 페이지 테이블(2)

[설명]
1) 프로세스가 동적 할당 받을 때

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

200바이트 할당 요청
- 1페이지 (4KB) 할당
- 논리 페이지 5할당, 물리 프레임 2할당
1) 페이지 5의 논리 주소 : 54KB = 20KB = 201024 =20480번지
2) 프레임 2의 물리 주소 : 2*4KB = 8192번지
- malloc(200)은 페이지 번호 5의 논리 주소 20480을 리턴

*p = 'a';

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

free(p);

20480번지에서 할당 받은 200바이트 반환
- 반환 후 페이지 5 전체가 비게 되므로, 페이지 5와 프레임 2가 모두 반환

페이지와 페이지 테이블(3)

[설명]

프로세스가 시스템 호출을 실행할 때
- 커널 공간의 페이지 k에 담긴 커널 코드 실행
- 커널 코드 역시 논리 주소로 되어 있음
- 현재 프로세스 테이블에서 페이지 k의 물리 프레임 780090을 알아내고 물리 프레임 780090에 적재된 커널 코드 실행

[중요사항]

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

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

** 32비트 CPU에서, 페이지 크기가 4KB인 경우
1. 물리 메모리의 최대 크기는?

물리 주소의 범위는 0 ~ 232 -1
한 주소 당 한 바이트 크기이므로 물리 메모리의 최대 크기는 232 = 4GB

프로세스의 주소 공간의 크기?

232 개의 주소들이므로, 총 4GB
물리 메모리는 1GB, 2GB, 4GB 등 다양하게 설치될 수 있지만, 프로세스의 주소 공간은 물리 메모리 크기에 상관없이 4GB

한 프로세스는 최대 몇 개의 페이지로 구성되는가?

4GB/4KB = 232/212 = 220개 = 1M개 = 약 100만 개

프로세스 당 하나의 페이지 테이블이 있다. 페이지 테이블의 크기는?

페이지 테이블 항목 크기가 32비트(4B)라면
4바이트*220 = 222바이트 = 4MB

응용프로그램이 하나의 프로세스라고 할 때, 응용프로그램의 최대 크기, 즉 개발자가 작성할 수 있는 프로그램의 최대 크기는?

운영체제가 설정한 사용자 공간의 크기

페이지 테이블 모양은

대부분이 비어 있는 희소 테이블

페이지 테이블은 어디에 존재하는가?

메모리에 저장

커널 코드가 논리 주소로 되어 있는가 물리 주소로 되어 있는가?

커널 코드 역시 논리 주소로 되어 있음. 그러므로 커널 코드가 실행될 때 역시 물리 주소로 바뀌어야 하는데 이때 사용되는 페이지 테이블은 현재 프로세스의 페이지 테이블이 사용됨

페이징에서의 단편화

외부 단편화 발생 없음
내부 단편화 발생
- 코드와 데이터가 주소 공간에서 연속되어 있다.
- 스택이나 힙에 생성하는 페이지는 계속 변하므로 단편화 계산에서 제외한다면
- 프로세스의 마지막 페이지에만 단편화 발생
- 단편화의 평균 크기 = 페이지의 1/2 크기

페이징 개념 확인

** 32비트 CPU에서, 페이지의 크기가 2KB, 현재 설치된 메모리 1GB, 프로세스 A는 사용자 공간에서 54321바이트를 차지한다고 할 때

물리 메모리의 프레임 크기는?

2KB로 페이지 크기와 동일

물리 메모리의 프레임 개수는?

물리 메모리를 프레임 크기로 나누면 됨. 1GB/2KB = 230/211 = 219개, 약 50만 개

프로세스 A의 주소 공간 크기와 페이지의 개수는?

프로세스의 주소 공간 크기는 232 = 4GB. 페이지의 개수 = 232/211=221개 = 2M개 = 약 2백만 개

프로세스 A는 몇 개의 페이지로 구성되는가? 프로세스 A를 모두 적재하기 위한 물리 프레임의 개수는?

프로세스 A의 실제 크기가 54321 바이트이므로, 2KB(2048)로 나누면 26.5이므로 27개 페이지(프레임)

페이지 테이블 항목의 크기가 4바이트라고 할 때, 프로세스 A의 페이지 테이블의 크기는?

테이블 항목이 총 221개이므로 221*4바이트 = 223바이트 = 8MB

페이징에서 단편화 메모리의 평균 크기는?

프로세스의 코드와 데이터 연속되어 있으므로, 마지막 페이지에만 단편화가 생긴다. 평균은 페이지의 반이므로 1KB

페이지의 크기와 단편화의 관계는?

페이지의 크기가 크면 단편화도 커진다. 하지만 극히 미미하다.

페이지의 크기와 페이지 테이블의 크기 관계는?

페이지 크기가 크면 페이지 개수가 작아지고 페이지 테이블의 크기도 작아진다.

페이징의 주소 체계

페이징의 논리 주소

논리 주소 구성

[페이지 번호(p), 옵셋(offset)]
- 페이지 크기가 4KB(=212)라면, 페이지 내 각 바이트 주소 12비트
- 옵셋 크기는 12비트
32비트 논리 주소 체계에서,
- 상위 20비트는 페이지 번호
- 하위 12비트는 옵셋

논리 주소의 물리 주소 변환 개념

페이징 구현

하드웨어 지원

CPU의 지원
- CPU에 페이지 테이블이 있는 메모리 주소를 가진 레지스터 필요
- Page Table Base Register (PTBR)
- 이 레지스터는 운영체제에 의해 제어
MMU 장치
- 논리 주소의 물리 주소 변환
- 페이지 테이블을 저장하고 검색하는 빠른 캐시 포함
- 메모리 보호 - 페이지 번호가 페이지 테이블에 있는지, 옵셋이 페이지의 범위를 넘어가는지 확인

운영체제 지원

프레임의 동적할당/반환 및 페이지 테이블 관리 기능 구현
- 프로세스의 생성/소멸에 따라 동적으로 프레임 할당/반환
- 물리 메모리에 할당된 페이지 테이블과 빈 프레임 리스트 생성 관리 유지
- 컨텍스트 스위칭 때, PCB로부터 페이지 테이블의 물리주소를 CPU의 PTBR 레지스터에 로딩

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

2가지 문제점
1. 1번에 메모리 액세스를 위한 2번의 물리 메모리 액세스

페이지 테이블은 몇 MB의 크기로 메모리에 저ㅏㅇ
CPU가 메모리를 액세스할 때마다, 2번의 물리 메모리 액세스 -> 실행 속도 저하
TLB 사용으로 해결

페이지 테이블의 낭비

프로세스의 실제 크기는 매우 작기 때문에
대부분의 페이지 테이블 항목이 비어 있는 문제
2레벨 페이지 테이블 등 방법으로 해결

C프로그램이 실행될 때 메모리 액세스 과정 분석

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
	sum += n[i];

32비트 CPU, 페이지는 4KB

배열 n[100]의 논리 주소는 0x2000(페이지2)부터 시작

배열 n[100]의 물리 주소는 0x7000(프레임7)부터 시작

배열 n[100]의 크기는 400바이트이며 페이지2에 모두 들어 있음

페이지 테이블은 물리 메모리 0xA000번지부터 시작

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

1) 문제 해결 실마리

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

2) TLB(Tranlation Look-aside Buffer) 사용

주소 변환 캐시(address translation cache) 로 불림
-> 최근에 접근한 '페이지와 프레임 번호'의 쌍을 항목으로 저장하는 캐시 메모리
위치
-> 현대 컴퓨터에서는 MMU내에 존재
TLB캐시의 구조와 특징
-> [페이지 번호 p, 프레임 번호 f]를 항목으로 저장
-> 페이지 번호를 받아 전체 캐시를 동시에 고속 검색, 프레임 번호 출력, content-addressable memory, associative memory라고 불림(연관 메모리)
-> 고가, 크기 작음(64~1024개의 항목 정도 저장)

TLB를 활용한 메모리 액세스

CPU로부터 논리 주소 발생
논리 주소의 페이지 번호가 TLB로 전달
페이지 번호와 TLB 내 모든 항목 동시에 비교

TLB에 페이지가 있는 경우, TLB hit
- TLB에서 출력되는 프레임 번호와 offset 값으로 물리 주소 완성
TLB에 페이지가 없는 경우, TLB miss
- TLB는 miss 신호 발생
- MMU는 페이지 테이블로부터 프레임 번호를 읽어와서 물리 주소 완성
- 미스한 페이지의 [페이지번호, 프레임번호] 항목을 TLB에 삽입

TLB가 있는 경우 C프로그램 실행 과정 분석

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
	sum += n[i];

배열이 2개의 페이지에 걸쳐 있는 경우 TLB 활용 사례

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
	sum += n[i];

배열 n[2000]의 논리 주소는 0x2000부터 시작하여 페이지 2,3에 걸쳐 존재

배열 n[2000]의 물리 주소는 0x7000부터 시작하여 프레임 7과 9에 나누어 할당

페이지 테이블이 메모리 0xA000번지에서 시작

TLB로 부터 얻는 교훈

1) TLB와 참조의 지역성

TLB는 참조의 지역성으로 인해 효과적인 전략임
TLB를 사용하면, 순차 메모리 액세스 시에 실행 속도 빠름
- TLB 히트가 계속됨(메모리의 페이지 테이블 액세스할 필요 없음)
TLB를 사용하면, 랜덤 메모리 액세스나 반복이 없는 경우 실행 속도 느림
- TLB 미스 자주 발생
- TLB의 항목 교체(TLB 항목의 개수 제한되기 때문)

2) TLB의 성능

TLB 히트율 높이기 -> TLB 항목 늘이기(비용과의 trade-off)
페이지 크기
- 페이지가 클수록 TLB 히트 증가 -> 실행 성능 향상
- 페이지가 클수록 내부 단편화 증가 -> 메모리 낭비
- 이 둘 사이에는 trade-off 존재, 선택의 문제
- 페이지가 커지는 추세 : 디스크 입출력의 성능 향상을 위해

3) TLB reach - TLB 성능 지수(figure of merit)

TLB 도달 범위
TLB가 채워졌을 때, 미스없이 작동하는 메모리 액세스 범위
TLB 항목 수 X 페이지 크기

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

CPU의 모든 레지스터를 PCB에 저장
PCB에 있는 프로세스의 페이지 테이블의 주소를 MMU(CPU)의 Page Table Base Register(PTBR)로 로딩

TLB 미스 시에 페이지 테이블을 액세스하여 물리 주소를 알아내고
TLB로 페이지 테이블 엔트리 이동하기 위함

TLB 내용 모두 지우기

새로운 프로세스의 실행이 시작되면 TLB 미스가 발생하고 TLB에 항목이 채워지기 시작함
큰 비용 대가

새 프로세스 컨텍스트(CPU레지스터)를 PCB에서 CPU로 로딩

페이지 테이블의 메모리 낭비 문제 해결

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

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

프로세스의 주소 공간
- 4GB/4KB = 232/212 = 220 = 약 100만 개의 페이지로 구성
프로세스 당 페이지 테이블의 크기
- 한 항목이 4바이트이면 220 x 4바이트 - 4MB

2) 10MB의 메모리를 사용하는 프로세스가 있다고 하면

실제 활용되는 페이지 테이블 항목 수
- 10MB/4KB = 10 x 220/212 = 10 x 28 = 2560개
실제 활용되는 페이지 테이블 비율
- 10 x 28/220 = 10/212 = 0.0024
- 매우 낮음

페이지 테이블 낭비 문제의 해결책

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

시스템에 하나의 역 페이지 테이블만 둠
- 역 페이지 테이블 항목의 수 = 물리 메모리의 프레임 개수
역 페이지 테이블 항목
- [프로세스번호(pid), 페이지 번호(p)]
역 페이지 테이블의 인덱스
- 프레임 번호
역 페이지 테이블을 사용한 주소 변환
- 논리 주소에서 (프로세스번호, 페이지 번호)로 역 페이지 테이블 검색
- 일치하는 항목을 발견하면 항목 번호가 바로 프레임 번호임
- 프레임 번호와 옵셋을 연결하면 물리주소

멀티 레벨 페이지 테이블

페이지 테이블은 하나의 페이지에 넣고 페이지 테이블을 가리키는 페이지 구성
사용 중인 페이지들에 대해서만 페이지 테이블 구성

역 페이지 테이블의 크기

1) 역 페이지 테이블의 개수

시스템에 1개 존재
2) 역 페이지 테이블의 크기
역 페이지 테이블의 항목 크기
- 프로세스 번호와 페이지 번호로 구성
- 프로세스 번호와 페이지 번호가 각각 4바이트라면, 항목 크기는 8바이트
역 페이지 테이블의 항목 수 = 물리 메모리 크기/프레임 크기
- 예) 물리 메모리가 4GB, 프레임 크기 4KB이면
역 페이지 테이블 항목 수 = 4GB/4KB = 220 개 = 약 100만개
역 페이지 테이블의 크기는 컴퓨터에 설치된 물리 메모리 크기에 따라 달라짐
- 물리 메모리는 컴퓨터마다 서로 다르게 설치될 수 있음
- 예) 물리 메모리가 4GB, 프레임 크기가 4KB, 한 항목의 크기가 8바이트라면 역 페이지 테이블의 크기는 = 220 개 항목 x 8 바이트 = 8MB

3) 기존 페이지 테이블과 비교

예) 10개의 프로세스가 실행 중일 때,
기존 페이지 테이블 = 4MB x 10개 = 40MB 크기
역 페이지 테이블 = 8MB (기존의 1/5 수준)
역 페이지 테이블 구현
- Linear inverted page table
- Hashed inverted page table - PID와 p를 키로 해싱하여 단번에 일치하는 항목을 찾고 물리 주소로 변환한다. - PowerpC, UltraSPAC