[컴퓨터 구조] 메모리[6] - 가상메모리(Virtual Memory)

 

 

 

 

 

 

🧐 가상 메모리

메인 메모리를 2차 저장장치(디스크)의 캐시로 사용하는 기술을 의미합니다.

이전까지는 캐시가 어떻게 최근에 사용한 코드와 데이터 부분에 대한 빠른 접근을 제공하는지 알아보았습니다.

 

같은 방법으로, 메인 메모리가 보통 자기 디스크로 구현되는 2차 저장장치를 위한 캐시로 동작할 수 있습니다.

이러한 기술을 가상 메모리(Virtual Memory)라고 부릅니다.

 

가상 메모리를 사용하게 된 주요 동기는 두가지입니다.

1. 여러 프로그램들이 효과적이고 안전하게 메인 메모리를 공유할 수 있게 하기 위하여

2. 작고 제한된 크기의 메인 메모리에서 프로그래밍해야 하는 제약을 제거하기 위해서

이 기법이 탄생한 지 수십년이 지난 지금은 첫 번째 이유로 널리 사용되고 있습니다.

 

 

 

 

다수의 프로그램이 같은 메모리를 사용할 수 있게 하려면, 모든 프로그램이 반드시 자신에게 할당된 메인 메모리 부분만 읽고 쓸 수 있게 하여 각 프로그램을 다른 프로그램으로부터 보호할 수 있어야 합니다.

 

캐시가 한 프로그램에서 활발히 사용되는 부분만 담고 있는 것과 마찬가지로, 메인 메모리도 많은 프로그램이 활발히 사용하는 부분만 담고 있으면 됩니다.

 

가상 메모리는 메인 메모리는 물론 프로세서도 효율적으로 공유하게 해줍니다.

 

프로그램을 컴파일할 때는 프로그램이 다른 어떤 프로그램들과 메모리를 공유할지 알 수 없습니다.

 

실제로 메모리를 공유하는 프로그램은 가상 머신들이 수행되는 동안 동적으로 변하게 됩니다.

 

이러한 동적 상호작용 때문에 각 프로그램들이 자신만의 주소 공간(space address), 즉 이 프로그램만 접근 가능한 별개의 메모리 영역으로 컴파일되기를 바랍니다.

 

가상 메모리는 프로그램의 주소 공간을 실제 주소(physical address)로 변환하여 줍니다.

(실제 주소는 메인 메모리 내의 주소를 의미합니다.)

 

이러한 변환 과정이 한 프로그램의 주소 공간을 다른 프로그램으로부터 보호(protection)하여 줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 가상 주소와 실제 주소

가상 메모리와 캐시에 적용되는 개념 자체는 같을지라도 역사적 뿌리가 다르다보니 서로 다른 용어를 사용하게 되었습니다.

가상 메모리에서 블록은 페이지(page)라 불리고, 가상 메모리 실패(miss)는 page fault라 불립니다.

가상 메모리를 갖는 프로세서가 가상 주소(virtual address)를 내보내면, 하드웨어와 소프트웨어가 협력하여 가상 주소를 실제 주소(physical address)로 변환한 후, 메인 메모리 접근에 사용합니다.

 

 

아래 그림은 page로 구성된 가상 주소 메모리가 메인 메모리로 사상되는 것을 보여줍니다.

이 과정을 주소 변환(address translation) 또는 주소 사상(address mapping)이라고 부릅니다.

 

프로세서는 가상 주소를 만들어내는 반면, 메모리는 실제 주소를 사용하여 접근됩니다.

가상 메모리와 메인 메모리 모두 page 단위로 나누어져 있어서, 가상 page가 실제 page로 사상됩니다.

 

그림에서 보이는 것과 같이 가상 page가 메인 메모리에 없을 수도 있어서 실제 주소(physical address)로 사상되지 않을수도 있습니다.

이 경우에는 page는 디스크에 있습니다.

 

또한 2개의 가상 주소가 같은 실제 주소를 가리키도록 함으로써 실제 페이지를 공유할 수 있습니다.

 

이러한 기능은 2개의 다른 프로그램이 데이터와 코드를 공유할 수 있도록 해줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 주소 변환의 기본 아이디어

가상 주소(virtual address) = 가상 페이지 번호(virtual page number) + 페이지 변위(page offset)

가상 메모리 시스템의 주소는 가상 페이지 번호와 페이지 변위로 나누어집니다.

가상 페이지 번호 = 가상 메모리 주소 / 페이지당 바이트 수

 

 

아래 그림은 가상 페이지 번호가 실제 페이지 번호로 변환되는 것을 보여줍니다.

위 그림을 통해 다음을 알 수 있습니다.

실제 페이지 번호는 실제 주소의 상위 부분을 구성합니다.

페이지 변위는 실제 주소의 하위 부분을 구성하며, 변환 후에도 바뀌지 않습니다.

페이지 변위 필드의 비트 수는 페이지의 크기를 결정합니다.

즉 위의 예시에서는 페이지 변위의 비트 수가 12개이므로, 페이지의 크기는 $2^{12}$ = 4KiB 입니다.

또한 메인 메모리의 크기는 $2^{40}$ = 1TiB인 반면 Virtual Memery의 크기는 $2^{48}$ = 256TiB입니다.

 

가상 주소로 참조 가능한 페이지 수는 실제 주소로 참조 가능한 페이지 수와 같지 않아도 됩니다.

실제 페이지보다 더 많은 수의 가상 페이지가 무한히 큰 가상 메모리 환상의 기초가 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 가상 메모리 설계와 Page Fault

가상 메모리에서 page fault를 처리하는 데 수백만 사이클이 소요됩니다.

 

보통 크기의 페이지의 경우 첫 번째 워드를 꺼내는 데 걸리는 시간이 거의 대부분인 이러한 이러한 엄청난 miss penalty 때문에 가상 메모리 설계에 대해 몇 가지 중요한 결정이 내려졌습니다.

긴 접근시간을 보상할 만큼 페이지가 충분히 커야 합니다.

page fault 발생률을 줄이는 구성이 바랍직합니다.
이를 위해 page를 fully associative 방식으로 메인 메모리에 배치합니다.

page fault는 소프트웨어로 처리할 수 있습니다.
이 부담이 디스크를 접근하는 시간과 비교할 때 더 작습니다.
게다가 소프트웨어는 페이지 배치에 좋은 알고리즘을 사용할 수 있는데, 실패율이 조금만 줄어도 충분히 그러한 알고리즘의 구현 비용을 보상할 수 있기 때문입니다.

가상 메모리에서 write through 방식을 사용하면 시간이 너무 오래 걸리기 때문에 적절하지 못합니다.
따라서 write back을 사용합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 page 배치와 찾기

page fault의 penalty가 엄청나게 크기 때문에, page 배치를 최적화함으로써 page fault 발생률을 줄이고자 합니다.

 

가상 페이지가 어떠한 실제 페이지로도 사상될 수 있게(fully associative) 하면 운영체제는 page fault 발생 시 어떤 page든 마음대로 선택하여 교체할 수 있습니다.

예를 들면 운영체제가 페이지 사용을 추적하는 정교한 알고리즘과 복잡한 자료구조를 사용하여 앞으로 오랫동안 필요하지 않을 것 같은 페이지를 선택할 수 있습니다.

 

유연하고 효과적인 교체 방식을 사용함으로써 페이지 부재 발생률을 낮추고 fully associative 페이지 배치의 사용을 단순화시킬 수 있습니다.

 

fully associative 방식을 사용할 때 가장 큰 어려움은 엔트리의 위치를 알아내는 것입니다.

왜냐하면 상위 계층의 어디에도 있을 수 있기 때문입니다.

 

메모리 전체를 검색하는 것은 비실용적이라서 가상 메모리 시스템에서는 메인 메모리를 인덱스하는 표를 사용합니다.

이 표를 페이지 테이블(page table)이라 부르며 메모리 내에 생성됩니다.

 

 

 

 

 

 

 

 

 

 

🧐 page table

가상 메모리 시스템에서 가상 주소를 실제 주소로 변환해 주는 테이블

page table은 메모리에 존재하며, 가상 페이지 번호로 인덱스됩니다.

 

해당 페이지가 실제 메모리(메인 메모리) 내에 있을 때 테이블 엔트리는 가상 페이지에 대응되는 실제 페이지 번호를 가지고 있습니다.

 

각 프로그램은 각자 자신의 page table을 가지고 있으며, 페이지 테이블은 그 프로그램의 가상 주소 공간을 메인 메모리로 사상합니다.

 

메모리 내 page table의 위치를 나타내기 위해 페이지 테이블의 시작 주소를 나타내는 레지스터가 하드웨어에 포함됩니다.

이 레지스터를 페이지 테이블 레지스터(page table register)라 부릅니다.

 

 

아래 그림은 하드웨어가 어떻게 페이지 테이블 레지스터, 가상 주소, 페이지 테이블을 이용하여 실제 주소를 만들어 내는지를 보여줍니다.

유효 비트는 캐시에서처럼 페이지 테이블 엔트리마다 하나씩 붙어 있습니다.

(위 그림에는 나와있지 않지만, reference bit와 dirty bit 등의 추가 비트도 필요합니다. 이는 이후 살펴보겠습니다.)

이 비트가 1이면 그 페이지는 메모리에 있으며 페이지 테이블 엔트리에 실제 페이지 번호가 있습니다.

0이라면 그 페이지는 메모리에 없는 것이고 따라서 page fault가 발생합니다.

 

페이지 테이블은 있을 수 있는 가상 페이지에 대한 사상을 모두 다 갖고 있기 때문에 태그가 필요 없습니다.

즉 위의 경우 페이지 테이블의 인덱스 범위는 0 ~ $2^{36} -1 $ 입니다.

 

캐시 용어로 설명하자면, 페이지 테이블 접근에 사용되는 인덱스는 블록 주소 전부, 즉 가상 페이지 번호로 되어 있습니다.

 

 

 

 

 

 

 

 

 

 

🧐 page fault

가상 페이지의 유효 비트가 0이면 page fault가 발생하며, 운영체제가 제어를 넘겨받게 됩니다.

제어를 넘기는 것은 예외 메커니즘에 의해 행해집니다.

 

운영체제가 제어를 갖게 되면 계층의 다음 수준(보통 플래시 메모리나 자기 디스크)에서 그 페이지를 찾아서, 이 페이지를 메인 메모리의 어디에 넣을 것인지 결정해야 합니다.

 

가상 주소만으로는 그 페이지가 2차 메모리 내 어디에 있는지를 바로 알 수 없습니다.

따라서 가상 메모리 시스템에서는 가상 주소 공간 내 각 페이지의 2차 메모리상의 위치를 알고 있어야 합니다.

 

메모리 내의 페이지가 언제 쫓겨날지를 미리 알 수 없기 때문에, 운영체제는 대부분 프로세스를 생성할 때 프로세스의 모든 페이지를 위한 공간을 플래시 메모리나 디스크상에 마련합니다.

 

이 디스크상의 공간을 swap space라고 부릅니다.

swap space는 프로세스의 가상 메모리 공간 전체를 위해 예약된 디스크 공간입니다.

이때 각 가상 페이지가 디스크의 어느 곳에 저장되는지를 기록하기 위한 자료구조를 만듭니다.

 

이 자료구조는 페이지 테이블의 일부분일 수도 있으며, 페이지 테이블과 같은 방법으로 인덱스되는 다른 자료구조일 수도 있습니다.

아래 그림은 단일 테이블이 실제 페이지 번호나 2차 메모리 주소를 담고 있을 때의 구조를 보여줍니다.

페이지 테이블은 가상 메모리의 각 페이지를 메인 메모리의 페이지나 디스크에 저장된 페이지로 사상합니다.

실제 페이지 주소 테이블과 디스크 페이지 주소 테이블이 논리적으로는 1개의 테이블에 존재하지만, 많은 시스템이 이들을 별도의 자료구조 2개에 저장합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 교체

운영체제는 어떤 프로세스와 어떤 가상 주소가 각 실제 페이지를 사용하는지를 추적하는 자료구조도 만듭니다.

page fault가 발생했을 때, 메인 메모리 내의 모든 모든 페이지가 사용 중이면 운영체제는 교체할 페이지를 선택해야 합니다.

 

page fault 발생을 최소화해야 하기 때문에, 대부분의 운영체제는 가까운 시간 내에 사용되지 않는 페이지를 선정하려고 합니다.

 

이를 위해 운영체제 과거를 이용하여 미래를 예측하는 LRU(least recently used) 교체 방법을 사용합니다.

이는 이전 글에서도 살펴보았듯이 사용한 지 가장 오래된 페이지를 찾습니다.

교체된 페이지는 2차 메모리상의 swap space에 써집니다.

 

 

완벽하게 LRU 방식을 구현하는 것은 메모리를 참조할 때마다 자료구조를 갱신해야 하기 때문에 비용이 많이 듭니다.

따라서 많은 운영체제는 최근에 어떤 페이지가 참조되고 참조되지 않았는지를 추적하는 유사 LRU 방식을 사용합니다.

 

운영체제가 LRU 페이지를 찾는 것을 돕기 위해 참조 비트(reference bit)를 두고, 페이지가 접근될 때마다 그 값을 1로 합니다.

 

운영체제는 주기적으로 참조 비트를 0으로 만들고, 후에 참조된 페이지만 다시 1로 만들어서, 특정 시간 동안 어떤 페이지들이 접근되었는지를 알 수 있게 합니다.

 

 

 

 

 

 

 

 

 

🧐 쓰기

가상 메모리의 경우 계층구조의 다음 계층(디스크)에 쓰는 데 수백만 사이클이 소요됩니다.

그러므로 쓰기 버퍼를 설치해서 디스크에 write through를 하는 것은 매우 비실용적입니다.

 

그 대신 가상 메모리 시스템은 write back을 사용합니다.

쓰기 동작은 메인 메모리 내의 페이지에서만 수행하고, 페이지가 메모리에서 교체될 때 디스크에 복사합니다.

 

 

가상 메모리 시스템에서 write back 방식은 또 다른 장점을 가집니다.

디스크 전송시간이 디스크 접근시간보다 짧기 때문에, 한 워드씩 디스크에 쓰는 것보다 페이지 전체를 힌꺼번에 쓰는 것이 훨씬 더 효율적입니다.

 

write  back 방식이 각각의 워드를 전송하는 것보다 능률적이기는 하지만 여전히 대가가 존재합니다.

그러므로 교체할 페이지가 결정되면, 무조건 디스크에 쓰는 것이 아니라 해당 페이지를 디스크에 쓸 필요가 있는지 없는지를 알아보아야 합니다.

 

메모리에 적재된 이후 페이지에 쓰기를 한 적이 있는지를 표시하기 위하여 page table에 갱신 비트(dirty bit)를 추가합니다.

 

 

 

 

 

 

 

 

 

🧐 TLB

페이지 테이블이 메모리에 있기 때문에, 프로그램에 의한 모든 메모리 접근은 최소한 2배의 시간이 걸립니다.

실제 주소를 얻기 위한 메모리 접근 한 번과 데이터를 얻기 위한 또 한 번의 접근이 필요하기 때문입니다.

 

접근 성능을 높이기 위한 핵심은 페이지 테이블에 대한 참조의 지역성(locality)을 이용하는 것입니다.

어떤 가상 페이지 번호의 변환이 사용되면, 이 페이지상의 워드 참조는 공간적 지역성과 시간적 지역성을 갖기 때문에 가까운 미래에 그 주소 변환이 다시 필요할 가능성이 높습니다.

 

따라서 요즘의 컴퓨터들에는 최근에 사용된 변환을 가지고 있는 특별한 캐시가 있습니다.

이 특별한 주소 변환 전용 캐시는 변환 캐시라 부르는 것이 정확한 표현이겠으나, 통상적으로 변환 참조용 버퍼(translation lookaside buffer, TLB)라고 부릅니다.

TLB : page table에 접근하는 것을 피하기 위해 최근에 사용된 주소 사상을 보관하고 있는 캐시

 

 

아래 그림은 TLB의 각 태그 항목이 가상 페이지 번호의 일정 부분을 갖고 있으며, TLB의 데이터 항목이 실제 페이지 번호를 갖고 있음을 보여줍니다.

TLB는 캐시이기 때문에 태그 필드가 있어야 합니다.

 

접근하려는 페이지와 일치하는 엔트리가 TLB 내에 없을 경우, page table을 조사해야 합니다.

page table은 페이지의 실제 페이지 번호를 제공하거나(이 번호는 TLB의 엔트리로 저장됩니다.),

페이지가 디스크에 있음(이 경우 page fault가 발생)을 표시합니다.

 

page table은 모든 가상 페이지의 엔트리를 가지고 있기 때문에,

즉 다른 말로는 TLB와는 달리 page table은 캐시가 아니기 때문에 태그 필드가 필요 없습니다.

 

 

 

TLB가 있으므로, 이제는 참조할 때마다 페이지 테이블 대신 TLB에 접근하기 때문에 TLB는 갱신 비트(dirty bit)나 참조 비트(reference bit)같은 다른 상태 비트들을 포함해야 합니다.

 

메모리를 참조할 때마다 TLB에서 가상 페이지 번호를 찾아봅니다.

적중되면 실제 페이지 번호는 주소를 만드는 데 쓰이고, 해당 엔트리의 참조 비트(reference bit)는 1이 됩니다.

 

TLB miss가 발생하면, 이 miss가 page fault인지 혹은 단순한 TLB miss인지를 알아야 합니다.

페이지가 메인 메모리에 존재한다면 그 변환이 TLB에 없을 뿐이지 page fault는 아닙니다.

이 경우에는 프로세서가 그 변환을 페이지 테이블에서 읽어 TLB에 적재하고 참조를 다시 시도함으로써 TLB miss를 처리할 수 있습니다.

 

페이지가 메인 메모리에 존재하지 않으면, TLB miss는 page fault를 의미합니다.

이 경우에는 프로세서가 예외를 사용하여 운영체제를 호출하여 처리합니다.

 

TLB는 메인 메모리 내의 페이지보다 훨씬 적은 수의 엔트리를 가지고 있기 때문에, 단순 TLB miss는 page fault보다 더 빈번하게 발생합니다.

 

 

 

 

TLB의 일반적인 값들은 다음과 같습니다.

• TLB 블록의 수(엔트리) : 16 ~ 512개
• 블록 크기 : 1~2 페이지 테이블 엔트리
  • (보통 각각 4~8 바이트, 즉 32~64 비트, page table의 블록의 수는 보통 $2^{32}$ ~ $2^{64}$사이이므로 32~64비트로 충분하다)
• hit time : 0.5 ~ 1 클럭 사이클
• miss penalty : 10 ~ 100 클럭 사이클
• miss rate : 0.01 ~ 1 %

 

 

 

 

 

아래는 fully assosiative 방식의 TLB를 사용하고, directed mapped 방식의 데이터 캐시를 사용하는 예시입니다.

이때 페이지 크기는 $2^{12}$ = 4KiB와 32비트 주소를 사용합니다.

따라서 가상 페이지 번호는 20비트(32 - 12)입니다.

 

실제 주소의 크기는 가상 주소와 같으며, 16개의 엔트리를 갖는 블록은 fully associative인 것을 알 수 있습니다.