[STUDY] 페이징

개발공부/CS스터디

[STUDY] 페이징

jnnjnn 2024. 4. 16. 00:05

지난 시간에 페이징과 세그멘테이션은 불연속 할당 방식으로 가상메모리를 구현한 메모리 할당 방식이라는 것을 배웠다.

간단히 개념만 짚고 넘어갔던 부분을 좀 더 자세히 알아보자

페이징

페이징은 물리 메모리에 외부 단편화가 생기지 않도록 나눈 후 같은 크기로 가상 메모리를 나눈다.

이는 메모리의 효율적 관리를 위해서이다.

Page(페이지) : 가상 메모리를 일정한 크기로 나눈 블록

Frame(프레임) : 물리 메모리를 일정한 크기로 나눈 블록

페이지 크기 = 프레임 크기

이렇게 나눈 프로세스의 페이지들은 물리적 메모리의 조각인 프레임에 불연속적으로 할당된다

불연속 할당이란?

하나의 프로세스가 통째로 연속되어서 메모리에 할당되는 것이 아니라

어떠한 단위로 쪼개져서 연속되지 않고 할당되는 것을 말함

이때, 페이지와 프레임의 대응 관계도는 페이지 테이블에 저장된다.페이지 테이블은 프로세스 하나당 한개씩 존재한다.

즉 프로세스와 페이지 테이블의 갯수는 똑같이 n개이다.

페이지 테이블

하나의 열(column)으로 이루어져 있다
논리 주소의 페이지와 1:1로 대응되어 페이지 테이블 0번의 값은 페이지 0번의 물리 주소 위치를 나타낸다
해당 논리 주소가 물리메모리에 있지 않을 경우 invalid라고 표시된다. 이는 해당 페이지가 스왑 영역에 있는 것을 의미한다

페이지 테이블의 주소 변환

메모리 각 주소의 크기는 1Byte로 페이지와 프레임의 각 크기가 10Byte라면, 총 10개의 주소가 페이지에 저장될 수 있다. 즉, 페이지 0에는 0~9번지의 10개의 주소가 있고, 페이지 1에는 10~19번지의 10개의 주소가 있다. 이것은 물리 공간도 마찬가지로 각 프레임에 10개의 주소가 있다.

가상 주소를 물리 주소로 변환하면

1. 가상 주소 30번지가 어느 페이지에 있는지 찾는다. 30번지는 페이지 3의 0번째 위치에 있다

2. 페이지 테이블의 페이지 3으로 가서 해당 페이지가 프레임 1에 위치한다는 것을 알아낸다

3. 물리 메모리 프레임 1의 0번째 위치에 접근한다. 이 주소가 가상 주소 30번지의 물리 주소이다.

마찬가지로

1. 가상 주소 18번지는 페이지 1의 8번째 위치에 있다

2. 페이지 테이블의 페이지 1로 가서 해당 페이지가 프레임 3에 있다는 것을 알아낸다.

3. 가상 주소 18번지의 물리 주소는 프레임 3의 8번 위치이다

정형화된 주소 변환

정형화된 페이징 기법에서는 가상 주소를 VA=<P,D>로 표현한다.

VA = 가상 주소
P = 페이지
D = 페이지의 처음 위치에서 해당 주소까지의 거리(distance). Offset이라고도 한다

위의 예시에서 가상 주소 30번지를 VA=<P,D>로 표현하면 VA=<3,0>으로 작성할 수 있다. 이는 가상 주소 페이지 3의 0번째 주소라는 것이다. 같은 방법으로 가사 주소 18번지는 VA=<1,8>이다.

페이징 기법에서 주소 변환은 가상 주소 VA=<P,D>를 물리 주소 PA=<F,D>로 변환하는 것이다.

PA = 물리 주소, 실제 주소
F : 프레임
D : 프레임의 처음 위치에서 해당 주소까지의 거리

16bit CPU의 주소 변환 예

위에서는 한 페이지의 크기를 10Byte로 가정했지만 컴퓨터는 2진법을 사용하므로 한 페이지의 크기는 2의 지수로 분할된다.

가상 주소를 <P,D>로 변환하는 공식

P = (가상 주소 / 한 페이지의 크기)의 몫

D = (가상 주소 / 한 페이지의 크기)의 나머지

한 페이지의 크기가 512(2^9)Byte라면 가상 주소 2049번지의 P는 2049/512의 몫인 4, D는 2049/512의 나머지인 1이다. 따라서 <4,1>로 표현된다.

16bit의 CPU 컴퓨터에서 한 프로세스가 사용할 수 있는 가상 메모리의 크기는 2^16Byte이다.

한 페이지의 크기를 2^10Byte라 가정하면, 페이지 개수는 2^6개가 된다.

따라서 가상 주소로 사용할 수 있는 16bit 중 6bit는 페이지 번호로, 10bit는 페이지의 처음 위치에서 해당 주소까지의 거리로 사용된다.

페이지 테이블 관리

페이지 테이블의 관리가 복잡한 이유는 시스템에 여러 개의 프로세스가 존재하고, 프로세스마다 페이지 테이블이 하나씩 있기 때문이다.

페이지 테이블은 물리 메모리 영역에 적재되는데 테이블의 크기는 프로세스의 수에 비례하며 커지므로 실행하는 프로세스의 수가 많아지면 페이지 테이블의 크기가 같이 커지고 이에 따라 프로세스가 사용할 수 있는 메모리 영역이 줄어든다.

따라서 페이지 테이블의 크기를 적정하게 유지하는 것은 페이지 테이블 관리의 핵심이다

물리 메모리의 크기가 작을 때는 프로세스 뿐만 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨진다.

이러한 페이지 테이블에 빠르게 접근하기 위해 PTBR이라는 레지스터가 존재한다

페이지 테이블 기준 레지스터(Page Table Base Register, PTBR)

각 프로세스의 프로세스 제어 블록(PCB)에 저장되는 데이터로 메모리 내에 페이지 테이블의 시작 주소를 가지고 있다.

페이지 테이블 맵핑 방식

1. 직접 매핑(direct mapping)

페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식이다
가장 단순한 방식으로 물리 메모리가 충분할 때 사용할 수 있다
모든 페이지를 물리 메모리에 가지고 있기 때문에 주소 변환 속도가 빠르다
residence bit = 0 인 경우 해당 페이지가 스왑 영역에 있는 것으로 페이지를 메모리에 적재 후 다시 검사한다
residence bit = 1인 경우 해당 엔트리의 p'를 확인한다

2. 연관 매핑(associative mapping)

페이지 테이블 전체를 스왑 영역에서 관리하는 방식으로 그 중 일부만 물리 메모리에 가지고 있다
물리 메모리의 여유 공간이 작을 때 사용하는 방식이다
페이지 테이블의 일부를 무작위로 가져오기 때문에 페이지 번호와 프레임 번호 둘 다 표시한다
물리 메모리에 저장된 일부분의 테이블을 변환 색인 버퍼(Translation Look-aside Buffer, TLB) 이라고 한다

연관 매핑에서는 메모리에 접근하기 위해 먼저 TLB에 접근한다. 이때 원하는 페이지 번호가 TLB에 있는 경우 TLB 히트라고 하며, 곧바로 물리 주소로 변환된다. 원하는 페이지 번호가 TLB에 없을 경우는 TLB 미스라고 하며, 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환한다

TBL 미스가 빈번하게 발생하는 경우 시스템 성능이 떨어지는 단점이 있다

3. 집합-연관 매핑(set-associative mapping)

연관 매핑의 단점을 개선한 방식이다
페이지 테이블을 일정한 집합으로 자르고, 자른 덩어리 단위를 물리 메모리에 가져온다
해당 집합이 물리 메모리에 있는지, 스왑 영역에 있는지 저장하는 집합 테이블(set table)을 생성하여 TLB 미스를 빠르게 알아낼 수 있다
I (Invalid)는 해당 집합이 스왑 영역에 있다는 의미이다
집합 2에 속한 페이지가 180번지에 있는 것을 의미한다

4. 역매핑(invert mapping)

다른 매핑들과 반대로 물리 메모리의 프레임 번호를 기준으로 테이블을 구성하는 방법이다
물리 메모리 상의 프레임 수와 테이블의 열거 수가 같다
프로세스의 수와 상관없이 테이블이 하나만 존재하여 테이블의 크기가 매우 작다
각 엔트리는 프로세스의 아이디(PID)와 해당 프레임에 있는 페이지 번호를 가진다
해당 프로세스의 아이디와 페이지 번호가 물리 메모리에 있는지 역매핑 테이블에서 검색한다
페이지 테이블을 모두 검사해야 하므로 검색 시간을 낭비하는 단점이 있다