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

메모리 관리 기법 중 페이징 메모리 관리 기법에 대해 더 자세히 알아보자. 

 

페이징(Paging)이란?

프로세스의 주소 강간을 0번지부터 페이지로 불리는 고정 크기로 나누고 물리 메모리 역시 페이지와 동일한 크기로 분할하여, 프로세스와 각 페이지를 물리 메미로의 임의의 페이지에 분산 할당하는 메모리 관리 기법이다. 

 

여기서 물리 메모리 페이지 크기의 메모리 블록을 프레임(frame), 페이지 프레임(page frame) 등으로 부른다. 

 

즉 프로세스의 메모리를 분할해서 관리한다는 것이고 메모리를 참조하려면 각 페이지의 위치를 기록해두어야 할 것이다. 

그래서 프로세스마다 페이지 테이블이 존재하고 이를 통해 물리 프레임에 매핑된다. 

 

MMU  장치는 페이지 테이블을 이용해 논리 주소를 물리 주소로 변환하며,

프로세스에 속한 모든 스레드는 실행시 메모리를 참조하기 위해 프로세스의 페이지 테이블을 이용하게 된다. 

 

앞서 우리는 메모리 관리 기법으로 페이징과 더불어 세그멘테이션에 대해서도 배웠었는데 어째서 페이징이 더 자주  사용 되는 것일까? 

- 페이징은 세그멘테이션에 비해 구현이 쉽다, 고정크기의 페이지로 분할하면 되기 때문이다. 

- CPU에 의존적이지 않기 때문에 이식싱어 높다.

- 시스템에 따라 혹은 응용에 따라 페이지 크기를 달리 설정할 수 있기 때문에 융통성이 높다. 

- 외부 단편회 문제가 없다. 따라서 메모리 활용, 오버헤드 면에서 더 유용하고, 내부 단편화 크기는 작다. 

 

프로세스가 동적 할당을 받는다고 해보자. 

char *p = (char*) malloc (200) ; 

이는 프로세스의 힙 영역에 200 바이트를 동적할당하는 것이다. 

운영체제는 malloc(200) 함수가 요청한 200바이트의 메모리를 할당하기 위해 프로세스의 힙 영역에 페이지를 할당한다. 

그리고 여기에 비어 있는 물리 프레임을 할당한다. 이제 프로세스에 할당한 페이지의 앞 200 바이트를 malloc(200)의 요청 결과로 할당해주고, 논리 주소를 리턴한다. 

 

프로세스의 주소 공간에서 커널 페이지가 활용되는 경우는 프로세스가 시스템 콜을실행하는 경우이다. 

그런데 커널 코드도 논리 주소로 이루어져 있고, 시스템 호출을 통해 커널 코드가 실행될 때 당연하게도 현재 프로세스의 페이지 테이블을 이용해 물리 주소로 변환된다. 

 

그럼 가상 주소 공간 전체를 커버하기 위해 필요한 페이지 테이블의 크기는 어떻게 결졍될까? 

32bit CPU를 기준으로 페이지의 크기가 4KB 일 때, 먼저 가능한 페이지의 개수는 2^32/ 2^12 로 2^ 20 개가 존재할 수 있다. 

그리고 32bit CPU에서 페이지 테이블 항목의 크기는 32bit => 4Byte이다. 각 페이지마다 하나의 페이지 테이블이 필요하기 때문에 총 4MB를 메모리에 저장해야 한다. 

 

 

페이징의 주소 체계 

프로세스의 논리 주소는 [페이지 번호(p), offset(페이지의 각 byte 주소)]로 표현할 수 있다. 

- 32bit 논리 주소에서 상위 20bit는 페이지 번호를 하위 12bit는 offset 주소이다. 

- 하나의 페이지의 크기가 4KB라고 하면, 이 안에서 바이트 하나하나를 식별하려면 0부터 4095까지의 주소가 필요하다. 즉 12bit를 통해 내부의 모든 바이트를 표현할 수 있고, 이 비트를 offset이라고 부르는 것이다. 

- offset은 가상 주소를 효율적으로 물리 주소로 변환하기 위해 필요한데, 상위 20비트(페이지 번호)는 어떤 페이지를 알려주는 역할을 한다, 즉 페이지 테이블에서 해당 물리 프레임을 찾게 해준다. 그리고 하위 12bit(offset)은 해당 페이지 안에서 몇 번째 바이트인지 나타내주는 것이다. 

 

페이지 테이블에는 프로세스의 모든 페이지에 대해 할당된 프레임 번호가 저장되어 있다. 

 

 

페이지 번호 p를 페이지 테이블의 인덱스로 하여 페이제 티에블 항목을 찾으면 페이지 p가 할당된 프레임 번호 f를 찾을 수 있게 된다. 페이지 번호 p를 프레임 번호 f로 바꾸고 offset을 그대로 사용하면 논리 주소를 물리 주소로 변환할 수 있는 것이다. 

 

 

페이징이 구현되려면 하드웨어와 운영체제의 도움이 필요하다.

CPU는 현재 실행중인 프로세스의 페이지 테이블이 적재된 물리 메모리 주소를 가진 레지스터 PTBR(Page Table Base Register)가 필요하고 이 값을 PCB에 저장한다. 그리고 MMU 저장 장치는 CPU 칩에 패키징 된다.

운영체제는 물리 메모리의 빈 프레임을 리스트로 생성하고 관리, 유지한다. 페이지 관리기능을 위해 각 프로세스마다 페이지 테이블이 적재된 물리 메모리 주소를 PCB에 저장하고 프로세스가 스케줄링되어 실행될 때 마다 PCB로부터 페이지 테이블 물리 주소를 CPU내 PTBR 레지스터에 옮겨야 한다. 

 

 

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

하지만 페이지 테이블로 인한 성능저하와 공간 낭비 발생하게 된다. 우선 페이지 테이블은 크키가 크다.

페이지 테이블의 크기는 프로세스의 최대크기(주소 공간)에 맞추어 생성되지만, 실제 프로세스의 크기는 그에 미치지 못한다. 

 

또, CPU가 메모리를 엑세스할 때 즉 논리 주소를 물리 주소로 변환할 때 1) 페이지 테이블에 접근해서 페이지 번호를 기준으로 프레임 번호를 찾는다. 2) 변환된 물리 주소로 실제 데이터에 접근한다. 이렇게 총 2번 물리 메모리에 엑세스 해야하기 때문에 프로세스의 실행 속도가 저하된다. 

 

컴퓨터 시스템에서 물리 메모리의 엑세스 횟수는 매우 종요한데, 하나의 논리 주소를 엑세스 하기 위해 2번의 물리 메모리에 엑세스 하는 것은 성능에 심각한 문제를 남긴다. 

 

TLB(Translation Lookaside Buffer) 

물리 메모리에 2번 엑세스 하는 문제를 해결하기 위해서는 논리 주소를 물리 주소로 바꾸는 과정에서 페이지 테이블을 읽어오는 과정을 없애면 어떨까? 

이런 목적으로 TLB가 도입되었다.

 

TLB는 MMU 내부에 위치해있으며,  CPU가 최근에 엑세스한 페이지 번호와 페이지가 적재된 프레임 번호쌍을 저장하는 캐시 메모리이다. 

이런 의미에서 TBL를 주소 변호나용 캐시라고도 부른다.

 

TLB의 항목은 [페이지 번호, 프레임 번호]로 이루어져 있다.

TLB 캐시에서 페이비 전호와 검색되는 방식은 일반 메모리와 다른데, 모든 항목을 동시에 비교해 당번에 프레임 번호를 반환한다. 

현재 대부분의 상용 CPU 칩은 TLB를 내장하고 있다. 

 

TBL가 있으면 CPU에서 논리주소의 페이지 번호가 TLB에 전달되고, TLB내의 저장된 모든 페이지 번호가 동시에 비교된다. 

이때 TLB 내에 일치하는 항복이 있으면 TLB 히트가 되고, 일치된 TLB 항목의 프레임 번호가 출력된다. 이 프레임 번호와 논리 주소의 offset이 합쳐져 물리 주소가 만들어지고 물리 메모리에 1번만 엑세스하면서 주소 변환이 이루어지는 것이다. 

만약 일치하는 항목이 없을 때는 TLB 미스가 발생하고, MMU는 물리 메모리의 페이지 테이블 항목까지 프레임 번호를 읽어와 물리 주소로 변환하고 엑세스한다. 그리고 방금 미스한 [페이지 번호, 프레임 전호] 쌍을 TLB에 새 항목으로 삽입한다. 

 

즉, TLB를 사용할 때 TLB 히트가 발생하면 바로 물리 주소를 논리 주소로 변환해 물리 메모리에 1번 엑세스할 수 있지만 TLB 미스가 발생하면 TLB를 사용하지 않을 때 처럼 2번의 물리 엑세스를 거쳐 주소 변환이 이루어지는 것이다. 

 

그럼 결국 TLB 히트가 꾸준하게 발생하지 않으면 TLB는 쓰나 마나 물리 메모리에 엑세스를 2번 해야할텐데 TLB가 효과적인 이유는 무엇일까? 

 

TLB와 참조의 지역성 

TLB를 사용한다고해서 모든 프로그램의 실행 속도가 개선되는 것은 아니다. 프로그램의 메모링 엑세스 패턴에 따라 실행 속도가 달라지게 되는데, TLB는 순차 메모리 엑세스 패턴을 가진 프로그램에 효과적이다. 

프로그램은 참조의 지역성을 갖는데, 이는 공간에서도 나타난다. 지금 엑세스 되고 있는 메모리의 주변 번지들이 가까운 미래에 엑스될 확률이 높은데 이런 참조의 지역성을 기반으로 TLB 사용시 히트가 계속되어 실행속도가 계선될 수 있는 것이다. 

하지만 프로그램이 랜덤하게 메모리에 엑세스 하는 경웨는 TLB 미스가 자주 발생할 것이다. 

 

따라서 TLB 성능은 TLB 히트율과 같다. 

TLB 히트율이란 CPU의 메모리 엑세스 횟수에 대한 TLB 히트의 비율을 의미한다. 

이는 TLB의 항목수와 페이지 크기에 비례하게 되는데 항목수가 많으면 비용이 늘어나고, 페이지 크기가 늘어나면 내부 단편화가 증가하기 때문에 적절한 트레이드 오프가 요구된다. 

TLB 도달 범위는 TLB 캐시의 모든 항목이 채워졌을 대 TLB 시스템이 작동하는 메모리 엑세스 범위로 TLB 항목수 * 페이지 크기와 같다. 

 

다른 프로세스의 스레드 컨텍스트로 스위칭 되는 경우 CPU는 다른 프로세스의 주소 공간에서 실행되기 때문에, TLB는 새로운 프로세스의 페이지 테이블 항목들로 교체되어야 한다. 이때 컨텍스트 스위칭이 발생한다. 

 

TLB가 재정의 되는 과정은 

1) CPU의 모든 레지스터들을 TLB에 저장한다

2) 새 프로세스의 PCB에 저장된 페이지 테이블의 주소를 CPU의 PRBR에 적재한다

3) TLB 캐시의 모든 항목을 지운다 

4) 새로 스케줄된 스레드의 TLB에 저장된 레지스터 값들을 CPU에 적재한 후 실행시킨다. 이때 처음에는 TLB 미스가 계속 발생하지만 점차 TLB 캐시가 채워진다

 

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

페이지 테이블로 메모리가 낭비되는 경우는 

1. 페이지 테이블의 일부만 사용되는 경우 

: 많은 프로세스의 실제 크기는 주소 공간의 최대 크기에 이르지 못한다. 즉 페이지 테이블의 일부분만 사용된다.

2. 프로세스마다 페이지 테이블이 존재하는 것 

: 페이지 테이블 크기가 4MB일 때 프로세스 100개 실행중이라면 400MB가 사용된다(프로세스는 가상 주소를 사용해서 모든 주소 공간을 사용하는 것으로 착각한다는 점을 기억하자)

 

이런 문제를 해결하기 위해 역페이지 테이블과 멀티레벨 페이지로 해결한다. 

 

역 페이지 테이블 

기존 페이지 테이블이 프로세스를 중심으로 프로세스의 각 페이지가 적재된 프레임 번호를 저장하는 방식이었다면, 역페이지 테이블은 프레임을 중심으로 물리 메모리의 전체 프레임에 대해 각 프레임이 어떤 프로세스의 어떤 페이지에 할당되었는지 나타내는 테이이다. 

역 페이지 테이블은 시스템당 1개 존재한다. 

 

역 페이지 테이블의 항목은 [프로세스 번호(PID), 페이지 번호(P)] 로 이루어져 있다. 

역 페이지 테이블의 크기는 컴퓨터에 설치된 물리 메모리의 크기에 좌우된다.

 

 

역 페이지 테이블에서 사용하는 시스템에서 논리주소는 [PID, p, offset] 으로 이루어져있다. 

논리주소가 발생되면 MMU는 PID와 P를 통해 역 페이짙 테이블을 검색하고 항목이 발견되면 항목 번호가 프레임 번호이다. 이 프레임 번호와 offset을 연결하면 물리 주소를 만들 수 있게 된다. 

역 페이지 테이블을 물리 메모리에 저장해두고 그 위치는 PTBR이 가리키게 된다. 

 

역 페이지 테이블의 크기는 시스템에 설ㄹ치된 물리 메모리 크기에 달라진다고 했는데, 

만약 32bit CPU라서 4GB의 물리 메모리를 갖고, 페이지의 크기는 4KB, 하나의 페이지 프레임 크기는 페이지 크기와 동일하기에 4KB일 것이다.  물리 페이지의 수는 이때 물리 메모리의 크기 / 페이지의 크기로 2^20 임을 알 수 있고, 이 물리 메모리의 수만큼 역 페이지 테이블이 필요할 것이다. 따라서 2^20 * 8byte(역 페이지 테이블 하나의 크기) = 8MB의 크기를 갖게 된다. 

이는 만약 10개의 프로세스가 실행중이라고 한다면 기존 페이지 테이블은 40MB의 크기를 차지하기 떄문에 1/5나 낭비를 줄일 수 있게 된다. 

 

TLB와 역페이지 테이블이 헷갈릴 수 있는데 정리해보면 

 

항목TLB (Translation Lookaside Buffer)역 페이지 테이블 (Inverted Page Table)

목적	주소 변환 속도 향상 (성능)	페이지 테이블 메모리 낭비 절감 (공간)
역할	최근 변환된 주소를 캐싱	물리 메모리에 맞춘 페이지 테이블 구조
위치	CPU 내부 (하드웨어 캐시)	메인 메모리
단점	용량 작음 (캐시 미스 발생 가능)	변환 속도 느림 (검색 필요)

 

 

이렇게 생각하면 이해하기 쉬울 것이다. 

TLB와 역페이지 테이블은 둘다 페이지 테이블의 문제를 해결하기 위한 것이지만 이 둘은 해결하려는 핀트가 서로 다르다. 

 

멀티 레벨 페이지 테이블 

프로세스에게 할당된 페이지들에 대해서만 페이지 테이블을 만드는 방식이다. 

페이지 테이블을 수십~수백개의 페이지 테이블로 나누고, 이들을 계층적으로 캐싱한다. 

32bit -> 2Lv, 3Lv

64bit -> 4Lv, 5Lv

 

2Lv 테이블의 경우 프로세스의 주소 공간을 1024개의 페이지들로 나누고 1024개의 페이지를 1개의 페이지 테이블로 나타낸다. 

페이지 테이블의 항목이 1024개인 것이다. 각 페이지 테이블의 일부 페이지가 없으면 공간을 그냥 비어둔다. 그리고 프로세스에게 할당되지 않은 페이지에 대해서는 페이지 테이블을 만들지 않아 페이지 테이블의 크기를 줄인다. 

 

1개의 페이지 테이블은 1024 * 4byte = 4KB로 1개의 프레임이 저장 가능하다. 

페이지 테이블이 메모리에 저장되므로 이를 기억하는 페이지 디렉토리가 요구된다.

 

 

페이지 디렉토리와 페이지 테이블의 2단계 과정을 거처야 페이지가 저장된 프레임을 알 수 있도록 구성되어 2LV 페이지라고 불리는 것이다. 

논리 주소는 [페이지 디렉토리 인덱스, 페이지 테이블 인덱스, offset] 으로 이루어져 있다. 

 

 

 

1. 논리주소의 최상위 10비트인 페이지 디렉토리 인덱스가 가리키는 페이지 디렉토리 항목들을 읽고 페이지 테이블의 프레임 번호를 알아낸다. 그리고 페이지 테이블을 물리 메모리로 읽어들인다.

2. 읽어들인 페이지 테이블에서 논리주소의 중간 10비트인 페이지 테이블 인덱스가 가리키는 페이지 테이블 항목에 저장된 프레임 번호를 읽는다

3. MMU는 이 프레임 번호와 논리주소의 offset을 조합해 물리 주소를 완성시킨다. 

 

2Lv 페이지 테이블은 프로세스가 현재 사용하는 페이지에 대해서만 물리 메모리 번호를 기록한다. 사용하지 않는 페이지들에 대해서는 테이블을 만들지 않아서 메모리 낭비를 줄인다. 

 

멀티레벨 테이블의 크기는 페이지 디렉토리 크기 4KB로 시스템에 1개 존재한다. 

페이지 테이블의 개수는 페이지 디렉토리의 항목 개수와 동일하고 최대 1024개 존재할 것이다. 

따라서 1024 * 4KB = 4MB, 하나의 프로세스가 주소 공간을 모두 활용했을 때 4MB + 4KB 의 크기를 가진다. 

 

 

지금까지 메모리 관리에서 페이징이 무엇인지, 그리고 주소 변환 과정에서 페이지가 어떻게 작동하고 어떤 문제를 갖는지 알아보았다. 

페이징의 페이지 테이블은 물리 메모리에 2번의 엑세스를 거쳐야하기에 성능상 문제를 가졌고 동시에 공간적 낭비도 존재했다.

그리고 이 문제를 TLB와 역 페이지 테이블 그리고 멀티레벨 페이지 테이블이 해결하는 과정 또한 알 수 있었다. 

 

다음은 가상 메모리에 대해서 알아보도록 하겠다.