Paging
가상 메모리(virtual memory)를 물리적 메모리(physical memory)로 매핑하는 방법 중 하나!
가상 메모리는 페이지(page)라는 고정 크기의 블록으로 나눠지며,
물리적 메모리는 프레임(frame)이라고 불리는 동일한 크기의 블록으로 나뉜다
Basic method
- 물리적 메모리를 동일한 크기의 프레임으로 나눈다.
- 프레임: 고정된 크기를 갖는 물리적 메모리의 작은 조각
- 가상 메모리를 동일한 크기의 페이지로 나눈다.
- 페이지: 고정된 크기를 갖는 가상 메모리 블록, 프레임과 크기 동일
- 모든 가용 프레임들을 관리: 운영체제는 물리적 메모리를 프레임들로 나누고, 이들 중 어떤 프레임이 사용 가능하고 어떤 것이 사용 중인지를 추적
논리주소를 물리 주소로 변환하기 위해서 페이지 테이블이 사용!
=> 가상 메모리를 사용하는 프로세스가 물리적 메모리에 접근하려면 페이지 테이블이 사용됨
=> 페이지 테이블은 논리 주소를 물리 주소로 매핑하는 데 사용
이를 통해 가상 메모리의 페이지가 물리 메모리의 프레임에 매핑
- 외부 단편화(External fragmentation) 발생 하지 않음
외부 단편화란, 메모리 공간 중 사용하지 않는 작은 조각들이 쌓이면서 연속된 큰 블록을 할당할 수 없는 상태. 페이징 기법은 고정 크기의 페이지로 나누어져 있으므로 외부 단편화가 발생하지 않음- 내부 단편화(Internal fragmentation) 발생할 수 있음
내부 단편화란, 프레임과 페이지의 크기가 정확히 일치하지 않아 발생하는 현상.
가령, 페이지 크기가 4KB이고 프레임 크기가 8KB라면 4KB의 낭비가 발생
이렇게 프레임에 페이지보다 더 많은 공간이 할당되는 경우 내부 단편화가 발생
정리)
- 페이징
- 가상 메모리를 페이지로 나누고 물리적 메모리를 프레임으로 나누어서 주소 변환 수행
- 주소변환: 논리적 주소 => 물리적 주소
논리적 주소는 CPU 가 사용하는 주소 => 페이지 번호(p), 오프셋(d)로 나누어 처리
페이지 번호(p)를 사용하여 페이지 테이블에서 p번째 항목을 찾는다.
해당 항목에는 가상 페이지의 물리적 주소의 시작 위치(f)가 저장되어 있음
물리적 주소는 f (물리적 주소의 시작 위치) + d (페이지 오프셋)로 계산
이를 통해 요청된 논리적 주소에 대응하는 물리적 주소이다.
Implementation of Page Table
-
페이지 테이블은 물리적 메모리인 Main Memory에 상주함.
-
현재 CPU에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용
- 페이지 테이블 기준 레지스터(PTBR; page-table base register)
메모리 내에서 페이지 테이블의 시작 위치를 가리킴 - 페이지 테이블 길이 레지스터(PTLR; page-table length register)
페이지 테이블의 크기를 보관함
- 페이지 테이블 기준 레지스터(PTBR; page-table base register)
-
페이징 기법에서 모든 메모리 접근 연산은 총 2번 필요
- 주소 변환을 위해 페이지 테이블에 접근
- 변환된 주소에서 실제 data/instruction에 접근
-
이러한 오버헤드를 줄이고 메모리의 접근 속도를 향상하기 위해 TLB(Translation Lock-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시를 사용
Associative Register
- parallel search가 가능
- TLB(Translation Look-aside Buffer)에는 page table 중 일부만 존재
- TLB는 페이지 번호와 프레임 번호 쌍을 가지고 있음.
특정 페이지 번호가 있는지 TLB 전체를 찾아봐야 한다.
TLB 풀 스캔 시간이 오래 걸리므로 병렬적으로 탐색이 가능한 연관 레지스터를 사용
Address translation, 주소 변환
page table 중 일부가 associative register에 보관되어 있음
빈번히 참조가 되는 페이지에 대한 주소변환 정보만 담는다.
- 만약 해당 page #가 associative register에 있는 경우
빠르게 page #에 대응되는 frame #를 얻을 수 있다.- 그렇지 않은 경우
main memory에 있는 page table로 부터 frame #를 얻음
- TLB는 context switch 때 flush (remove old entries)
: 이전 프로세스의 주소 변환 정보를 담고 있는 내용 전부 지운다.
새로운 프로세스를 실행할 때마다 TLB를 초기화하여 새로운 프로세스의 주소 변환 정보를 캐싱
프로세스 간 TLB 정보가 공유되지 않으며, 메모리 보호 및 프로세스 독립성 보장
Effective Access Time
EAT = 메모리에 접근하는 평균 시간
EAT = (1 + ε)a + (2 + ε)(1 - a) = 2 + ε - a
주소 변환 정보가 TLB에 존재하는 확률 a에 따라서 달라지는 평균 시간.
따라서 TLB에 캐싱된 주소 변환 정보가 많을수록 (즉, a가 크면 클수록) 평균적인 메모리 접근 시간이 더 짧아지며, 메모리 접근 속도가 향상
TLB에 주소 변환 정보가 존재하는 경우 (확률 a):
요청된 페이지의 주소 변환 정보가 연관 레지스터 (TLB)에 존재한다면,
TLB에서 직접 물리적인 메모리에 접근하는 데 ε시간이 소요.
실제 원하는 데이터에 접근하기 위해 한 번 더 메모리 접근이 필요하므로,
총 시간은 (1 + ε)
따라서 이 경우의 평균 시간은 (1 + ε) * a
TLB에 주소 변환 정보가 존재하지 않는 경우 (확률 1 - a):
요청된 페이지에 대한 주소 변환 정보가 TLB에 존재하지 않는 경우,
요청된 페이지에 대한 주소 변환 정보를 TLB에서 찾는 데 ε시간이 소요.
그리고 페이지 테이블에 접근하는 데도 ε시간이 추가로 소요되며,
실제 원하는 데이터에 접근하기 위해 두 번의 메모리 접근이 필요하므로,
총 시간은 (2 + ε)
따라서 이 경우의 평균 시간은 (2 + ε) * (1 - a)
Two-Level Page Table
2단계 페이징 기법
페이지 테이블 자체를 페이지로 구성하여 주소 공간 낭비를 줄이는 기법.
- 기존의 페이징 기법
- 한 프로세스당 페이지 테이블이 매우 큰 크기를 갖는 문제
- 32비트 주소 체계를 사용하는 컴퓨터에서는 4GB의 주소 공간,
페이지 사이즈가 4K인 경우, 한 프로세스당 페이지 테이블이 1M 크기.
=> 하지만 대부분의 프로그램은 4GB의 주소 공간 중에 일부분만을 사용,
페이지 테이블이 필요 이상으로 크게 되어 주소 공간을 낭비
주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블의 2단계에 걸친 페이지 테이블을 사용
사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정, 여기에 대응하는 내부 페이지 테이블을 생성하지 않음.
페이지 테이블을 위해 사용되는 메모리 공간을 줄이지만, 페이지 테이블의 수가 증가하므로 시간은 더 오래걸린다.
프로세스의 논리적 주소 <P1, P2, d>
두 종류의 페이지 번호(P1, P2)와 페이지 오프셋(d)으로 구분
P1은 외부 페이지 테이블의 인덱스, P2는 내부 페이지 테이블의 인덱스
외부 페이지 테이블로부터 P1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻게 되고, 내부 페이지 테이블로부터 P2만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻은 후,
해당 프레임으로부터 d만큼 떨어진 곳이 바로 찾으려는 물리적 주소
페이지 오프셋 (d):
페이지의 크기가 4KB(2^12 bytes)이므로, 페이지 내에서의 바이트 오프셋을 나타내기 위해서는 12비트가 필요. 따라서 페이지 오프셋 d는 12비트
페이지 테이블 엔트리의 크기가 4바이트라는 가정에 따라 페이지 테이블에는 4KB / 4B = 1,024개의 엔트리가 있음. 이를 구분하기 위해 페이지 테이블 인덱스에는 10비트가 필요.
남은 비트 수는 내부 페이지 테이블 인덱스 P2에 할당. 남은 비트 수는 32 - P1 비트 수 - 페이지 오프셋 d 비트 수 = 32 - 10 - 12 = 10 비트.
따라서 내부 페이지 테이블 인덱스 P2도 10비트로 표현됨.
개발자로서 성장하는 데 큰 도움이 된 글이었습니다. 감사합니다.