가상 메모리의 개념

가상 메모리는 현재 장착된 물리 메모리 크기와 상관없이 운영체제에서 독자적으로 가상 공간을 구축하여 프로세스를 보다 편히 저장하기 위해 사용되는 기술이다. 가상 메모리를 통해 프로세스는 물리적인 공간에 제약받지 않고 무한한 메모리에 프로세스를 저장할 수 있다.

가상 메모리의 기능

1. 메모리 관리의 단순화 : 각 프로세스마다 가상 메모리의 통일된 주소 공간(상대주소)을 배정할 수 있으므로 메모리 관리가 단순해진다.

2. 메모리 요량 및 안정성 보장 : 물리적인 공간이 아닌 거의 무한한 가상 메모리 공간을 배정함으로써 프로세스 간 메모리 침범이 일어날 여지를 크게 줄여준다.

가상 메모리의 구현

가상 메모리는 MMU라는 메모리 관리 유닛을 사용하여 구현된다. 예를 들어, A 프로세스의 가상 주소가 0x1000 라고 가정하면, CPU는 프로레스의 페이지 테이블을 참조해 가상 주소를 기반으로 offset 값을 대입시켜 A 프로세스의 실제 주소인 0x400000 라는 물리 주소를 참조할 수 있게 된다.

그리고 B 프로세스의 가상 주소도 똑같이 0x1000 라고 한다면 B 프로세스의 페이지 테이블을 사용해 실제 주소 0x600000를 참조할 수 있게 된다.

이렇게 되면 두 프로세스는 동일한 0x1000 이라는 가상 주소를 참조했지만, 실제로는 MMU가 페이지 테이블을 참조해서 실제 메모리 주소를 얻고 그 위치를 참조해서 값을 가져오게 된다.

이렇게 하여 두 프로세스의 주소 공간이 겹치지 않으면서도 같은 가상 주소를 사용 하기에 프로그래머는 다른 프로세스를 관리하더라도 하나의 가상 주소(상대 주소)만 가지고 있으면 된다.

메모리 분할 방식

페이징 기법

고정 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 주소 공간을 같은 크기로 나누어(1/n) 사용한다. 이 방식의 가상 메모리는 항상 0번지부터 시작한다. 이 고정된 영역을 '페이지'라고 부른다. 페이지로 영역을 나누는 이유는 공간적 지역성 때문이다.

VA = <P,D> → PA = <F,D> // P는 페이지, D는 처음 위치에서 해당 주소까지의 거리
F는 프레임(묶음 단위)를 나타내고 그 묶음 중에 원하는 주소를 D를 통해서 찾아낸다.
(D를 변경하지 않는 이유는 페이지와 프레임의 크기를 똑같이 나누었기 때문)

페이징 기법은 프로세스가 생길 때마다 매 번 일정 크기만큼 나눠주기에 실제 프로세스 크기는 작은 경우 할당 된 영역이 낭비되는 내부 단편화가 발생할 수 있다.

페이지 테이블

가상 주소와 물리 주소를 엮어주는 매핑 테이블로서 프로세스마다 하나씩 존재하며, 반드시 물리 메모리에 상주한다. 즉, 프로세스가 많아질 수록 테이블로 인한 메모리 사용이 많아진다.
최근의 윈도우 운영체제는 4096 (4KB)의 페이지 크기를 사용한다.
페이지 테이블의 크기는 32bit 주소체계를 사용하는 시스템의 경우 항목 당 4바이트가 사용되어
4MB의 페이지 테이블 공간을 가진다. 즉, 프로세서마다 4MB의 물리 영역을 할당해야한다.

페이지는 일정한 크기를 가지고 있기 때문에 메모리의 시작 주소만 가지고 있어도 된다.

세그먼테이션 기법

가변 분할 방식을 이용한 메모리 관리 기법으로, 물리 메모리를 프로세스의 크기에 따라 가변적으로 나누어 사용한다. 즉 크기가 큰 프로세스는 그 만큼 많은 영역을 할당받는다. 이 할당받은 영역을 "세그먼트"라고 부른다.

VA = <S,D> // S는 세그먼트 번호, D는 처음 지점에서 해당 주소까지의 거리

세그먼테이션 기법을 사용할 때 잦은 메모리 할당 및 해제로 인해 중간중간에 빈 공간이 생기는 상황이 발생하는데 새로 할당하기에는 작은 공간이지만 무시할 수 없는 영역들이 생기는 외부 단편화 문제가 발생할 수 있다.

세그먼트 테이블

세그먼테이션 기법에서 사용되는 메모리 테이블이다. 세그먼트 테이블은 세그먼트 번호와 시작 주소(base), 세그먼트 크기(limit)를 엔트리로 갖는다. 세그먼트의 크기는 일정하지 않기 때문에, 테이블에 limit 정보가 주어진다. 그리고 CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료시킨다(세그폴트).

세그먼테이션 폴트 : 사용자의 프로세스가 지정된 메모리 공간 밖으로 이동하거나 권한 없이 액세스할 때 발생한다. 침범한 해당 프로세스를 강제로 종료하여 해결한다.

페이지 / 프레임

프레임은 물리 메모리를 일정한 크기로 나눈 블록이고, 페이지는 가상 메모리를 일정한 크기로 나눈 블록이다. 페이지가 하나의 프레임을 할당 받아 물리 메모리에 위치함으로, 페이지는 알맹이, 프레임은 알맹이가 들어갈 틀이라고 생각하시면 쉽습니다. 프레임을 할당 받지 못한 페이지는 외부 저장장치(하드디스크 등)에 저장된다. 프레임과 페이지는 같은 크기로 관리된다. 하드디스크와 메모리간의 데이터 전송(교환)은 프레임 단위로 전송된다.

페이징 기법

각 프로세스의 페이징 시스템

32bit-4GB 시스템을 사용한다고 가정 시 각 프로세스마다 페이지 테이블(4MB)이 존재하며 프로세스 수가 많아질 수록 페이지 테이블의 수 역시 늘어난다. 해당 페이지 테이블을 모두 메모리에 올리거나, 스왑 영역와 연관하여 일부 페이지만 메모리에 올릴 수 있다.

물리 메모리 내 페이지 테이블 영역

각 페이지 테이블의 시작 주소는 해당 프로세스를 담당하는 PTBRp 레지스터에 보관된다.
페이지 테이블 영역은 운영체제 영역에 할당되며 각 프로세스는 PTBR을 통해 프로세스 고유 페이지 테이블에 접근할 수 있다. 위에서 설명한 바와 같이 메모리 크기가 작을 때는 페이지 테이블의 일부 페이지가 스왑 영역으로 옮겨질 수 있다.

메모리 풀

메모리 공간을 필요한 크기, 개수 만큼 사용자가 지정하여 미리 크게 할당받아 놓고 반납하는 기법. 미리 필요한 크기만큼 할당해놓기 때문에 단편화 문제가 발생하지 않고 잦은 메모리 할당과 해제에 비해 오버헤드도 줄일 수 있다. 하지만 할당해놓고 효율적으로 사용하지 않는다면 메모리 누수가 발생할 수도 있다.

페이지 폴트

프로세스가 페이지를 요청했을 때 그 페이지가 물리 메모리에 없는 상황이고 HDD 등에서 메모리를 찾아야하는 상황을 뜻한다. 메모리에 있는 가장 필요없는 영역을 sotre하고, HDD에 있는 요청한 데이터를 해당 영역에 load하여 스와핑한다.

페이지 테이블에는 각 페이지마다 Valid bit가 존재하는데 비트가 0이면 메모리, 1이면 하드디스크에 물리 데이터가 존재한다는 뜻이다.

bit가 0일 때는 주소 필드에 프레임 번호가 저장되고, bit가 1일 때는 데이터가 스왑 영역에 있는 것이므로 스왑 영역의 페이지 주소가 저장된다. (HDD에 있으니 페이지로 불림)

스와핑(Swapping)

스와핑은 보조기억장치(HDD)에 있는 데이터를 주기억장치로 이동하는 기법을 뜻한다.
물리 메모리가 꽉 찬 상태에서 페이지 폴트가 발생했을 때 발생하며
물리 메모리 상에서 가장 필요없는 Victim page(페이지)를 하드디스크로 내리고(swap-out)
그 공간에다 요청한(폴트) 페이지를 하드디스크에서 올려준다(swap-in).

Windows에서 사용하는 하드디스크 일부분을 메모리로서 사용하는 "가상 메모리"는 다른 개념이다.

변환 색인 버퍼(TLB)

가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 버퍼다. 페이지 테이블이 물리 기억장치(주기억장치) 상에 존재하기 때문에, 메모리를 액세스 할 때마다 한 번은 물리 기억장치의 페이지 테이블을 다른 한 번은 기억장치에 필요한 데이터를 총 두 번을 액세스 해야 하기 때문에 액세스 시간을 길어지게 만드는 단점이 생긴다.

이 문제를 해결하기 위해 프로세서에 내장된 캐시의 일종인 변환 우선참조 버퍼(Translation Lookaside Buffer/TLB)를 사용한다.

TLB가 hit일 경우 가상 주소를 물리 주소로 변환하기 위한 페이지 테이블에 접근할 필요가 없으며 (TLB는 메모리가 아닌 프로세서에 내장되어 있기에 훨씬 빠르다),
TLB의 프레임 주소를 토대로 데이터를 불러오기 위한 1번의 메모리 접근만 있으면 된다.

TLB 경우의 수 참조

https://m.blog.naver.com/PostView.nhn?blogId=xowns4817&logNo=221182043348&proxyReferer=http:%2F%2F211.195.6.43%2F

페이지 테이블 맵핑 방식

페이지 테이블을 전부 메모리에 올리기엔 많은 자원이 소모되니 물리 메모리가 적은 시스템의 경우 스왑 영역과 매핑하여 페이지 일부를 TLB에 복사해서 사용한다.
그 방식이 연관(최대 절약), 집합-연관(일부 타협) 매핑 방식이다.

직접 매핑

페이지 테이블 전체가 물리 메모리에 존재하는 일반적으로 사용하는 방식이다.

연관 매핑

페이지 테이블 전체를 스왑 영역(하드디스크)에서 관리하는 방식이다.
물리 메모리의 여유 공간이 적을 때 사용하는 방식이며 일부 페이지만을 메모리(TLB)에 복사한다.
TLB를 사용하여 페이지가 메모리(프레임)에 올려졌는지 스왑(HDD) 영역에 있는지 확인한다.
검색(TLB) 실패 시 페이지가 메모리 상에 없으므로 스왑 영역에서 페이지를 찾아야 한다.

메모리에 접근하기 위해선 TLB를 스캔해 히트 시엔 원하는 페이지가 메모리에 있는 경우이며 바로 물리 주소로 변환할 수 있지만, 미스 시엔 해당 페이지가 메모리에 없는 경우가 되어 스왑 영역의 페이지 테이블을 참조하여 물리 주소로 변환해야 한다(시간 소요).

이 매핑은 대부분의 페이지를 물리 메모리에 보관하지 않아 메모리를 절약할 수 있지만, TLB 미스가 자주 발생할 경우 성능이 떨어진다. 또 TLB는 페이지를 무작위로 가지고 있기 때문에 TLB 스캔 시 모든 버퍼를 검색해야지 찾는 페이지가 메모리(프레임)에 없다는 것을 알 수 있고 그 때야 TLB 미스가 발생하게 된다.

※ 페이지 테이블 매핑은 어디까지나 페이지 테이블을 상대로만 매핑하였기 때문에 TLB 미스가 발생하더라도 페이지 폴트와는 관계없다.
(페이지 테이블 크기 4MB만을 절약하기 위한 기법이기에)
페이지가 스왑 영역에 있어도 물리 주소 자체는 프레임(메모리)에 있을 수 있기 때문.

집합-연관 매핑

연관 매핑을 개선한 방식으로 페이지 테이블들을 일정 크기로 묶어서 이를 묶음 페이지 테이블이라고 칭하고, 선정된 묶음 테이블 하나를 메모리에 올려두고 나머지 묶음 테이블은 스왑 영역으로 보내는 방식이다. 그리고 묶음 테이블을 관리하기 위해 디렉터리(페이지) 테이블을 하나 더 생성한다.
(이를 통해 특정 테이블 묶음이 물리 메모리에 있는지, 스왑 영역에 있는지 확인할 수 있다)

연관 매핑과 더불어 주로 캐쉬-메모리 관계에서 사용되는 방식이다.

1. 매핑 방식

페이지 테이블을 같은 크기의 여러 묶음으로 나누고, 각 묶음의 시작 주소를 가진 디렉터리 테이블을 새로 만들어 관리하는 방식이다.

전체(나머지) 테이블는 스왑 영역에 있지만, 한 묶음은 메모리에 옮긴다. (사진의 묶음 페이지 테이블)
묶음 테이블이 메모리에 있는지, 스왑 영역에 있는지를 표시하는 디렉토리 테이블을 만든다.

묶음으로 관리하여 시작 주소를 알 수 있으므로 연관 매핑처럼 메모리에 올려진 페이지를 하나 하나 살펴보지 않아도 되며, 연관 매핑보단 디렉토리 테이블만큼의 메모리 공간을 더 차지하지만

디렉토리 테이블을 살펴보면 찾는 페이지 묶음이 어느 영역에 있는지 바로 알 수 있으므로 연관 매핑과 달리 물리 메모리상의 페이지 전체를 뒤지지 않아도 TLB 미스를 바로 알 수 있다.
(디렉토리 테이블에서 P1을 통해 인덱싱한다.)
(P2는 기존처럼 프로세스의 페이지 테이블을 식별하고 Distance를 통해 페이지 엔트리를 식별한다.)

• 디렉토리 테이블 역시 페이지 테이블처럼 시작 주소는 PTBR에서 관리하며, PTBR을 통해 디렉토리 위치를 찾을 수 있다.

• 하지만 묶음 페이지 테이블의 시작 주소는 PTBR 아니라 디렉터리 테이블의 값을 통해 별도로 찾아야 한다.

2. 가상 주소

페이지 테이블이 일정 크기의 묶음으로 나뉘기 때문에 가상 주소를 VA=<P1,P2,D>로 바꾸어 표시한다.
페이지 테이블을 10개씩 한 묶음으로 나눌 경우 0~9번 테이블은 0번 디렉토리(b)에 10~19번 테이블은 1번 디렉토리(I)에 속한다.

VA = <P1, P2, D>
VA 158 = <1, 5, 8>
VA 461 = <4, 6, 1>

3. 매핑 구조 <1, 5, 8>

프로세스가 특정 주소를 요구하면 VA=<P1, P2, D>로 변환되고, P1을 이용하여 디렉터리 테이블에서 주소를 찾는다.

찾은 주소가 만약 I(invalid)로 표시되면 TLB 미스가 발생한 것이다.
찾는 테이블이 물리 메모리에 성공적으로 있다면 묶음 테이블의 시작 주소가 디렉토리 테이블에 명시되어 있다.

※ 묶음 테이블의 시작 주소는 PTBR이 취급하는게 아니라 디렉터리 테이블을 통해 찾아야 한다!!!
(물리 메모리에 올라오지 않은 묶음 페이지 테이블들은 디렉토리 테이블에서 I로 표시된다.)

그 후 P2를 이용하여 묶음 내에서의 위치 정보를 통해 물리 주소로 접근할 수 있게 된다.

집합-연관 매핑 구조는 연관 매핑보다 타협적이지만 복잡하고 좀 더 많은 메모리를 소모한다.

https://starrykss.tistory.com/967

관련 용어

스레싱

메모리 영역에 접근하게 될 때, 메모리에 페이지 폴트(Page fault)율이 높은 것을 의미하며, Page Fault가 연속적으로 발생하여 프로세스 수행시간보다 페이지 교체 시간이 많은 상태를 뜻한다.

워킹셋

지역성을 기반으로 가장 많이 사용하는 페이지를 미리 저장해둔 것 워킹 셋에 있는 page들은 page frame에 고정시켜 두는 방법으로 다양한 응용이 가능하여 페이지 폴트를 예방한다.

페이지 테이블 기준 레지스터(PTBR)

프로세스를 위해 존재하며, 페이지 테이블 역시 고유의 주소를 가지는데 이 위치를 저장하기 위해 필요한 레지스터다. 각 페이지 테이블(디렉토리 등)의 시작 주소를 저장한다. 물리 메모리의 크기가 작을 때는 페이지 테이블도 스왑 영역으로 옮겨진다.

Paged-Segmentation 기법

세그먼테이션과 페이징 각각의 장점을 한꺼번에 얻기 위해 두 기법을 동시에 사용하는 현대 OS가 채용하는 기법이다. 먼저 세그먼테이션을 수행하고 각 세그먼트 별로 페이징을 수행한다.

즉, 세그먼트 테이블 내 항목이 그 세그먼트를 위한 페이지 테이블의 시작주소를 알려주도록 한다.

이러면 외부/내부 단편화를 최대한 억제할 수 있다. 하지만 메모리 참조가 한번 더 증가하여 약간의 속도 저하 문제점이 있다.

상식 문제

32비트 시스템에서 페이지 크기가 4KB일 때, 4GB 메모리에 접근하기 위해 필요한 페이지 테이블의 크기는? (페이지 엔트리의 크기는 4Byte 이다.)

페이지 크기는 4KB -> 2^12byte (오프셋에 필요한 비트 수 : 12비트)
메모리 크기는 4GB -> 2^32byte (메모리에 필요한 비트 수 : 32비트)
페이지 번호에 필요한 비트 수 : 32 - 12 = 20비트

따라서 페이지 테이블 크기는 페이지 수 * 엔트리 크기 = 2^20 x 2^2 = 2^22 = 4MB가 된다.

계층 구조

가상 메모리와 캐시 시스템은 계층구조를 이루며 같이 동작한다. 따라서, 데이터가 메인 메모리에 없다면 그 데이터는 캐시에 있을 수 없다. (디스크->메모리->캐시->레지스터)
(TLB->메모리->스왑영역), TLB hit = 메모리에도 페이지(프레임)가 존재