[CS] Chapter 08 가상 메모리의 기초

📌 가상 메모리의 개요

1. 가상 메모리 시스템

가상 메모리의 개념

현대 메모리 관리의 가장 큰 특징은 물리 메모리의 크기와 프로세스가 올라갈 메모리의 위치를 신경 쓰지 않고 프로그래밍하도록 지원한다는 것입니다. 이것을 가능하게 하는 메모리 시스템을 가상 메모리라고 부릅니다. 가상 메모리는 물리 메모리의 크기와 상관없이 프로세스에 커다란 메뢰 공간을 제공하는 기술이니다. 이 기술 덕분에 프로세스는 운영체제가 어디에 있는지, 물리 메모리의 크기가 어느 정도인지 신경 쓰지 않고 마음대로 메모리를 사용할 수 있습니다.

가상 메모리의 크기와 주소

논리 주소의 크기는 물리 메모리의 주소 공간에 비례하지만, 가상 주소는 물리 메모리 공간이 아닌 가상의 주소 공간을 가집니다.

이론적으로 가상 메모리의 크기는 무한대입니다. 그러나 실제로 가상 메모리의 최대 크기는 컴퓨터 시스템이 가진 물리 메모리의 최대 크기로 한정되며, CPU의 비트에 따라 결정됩니다. 32bit CPU의 경우 32bit로 표현할 수 있는 최댓값인 2$^{32}$-1(16진수로 FFFFFFFF), 약 4GB가 메모리의 최대 크기이므로 가상 메모리의 최대 크기도 약 4GB입니다.

가상 메모리 시스템에서는 물리 메모리의 내용 중 일부를 하드디스크의 일부 공간, 즉 스왑 영역으로 옮깁니다. 스왑 영역은 하드디스크에 존재하지만 메모리 관리자가 관리하는 영역으로서 메모리의 일부이며, 가상 메모리의 구성 요소 중 하나입니다. 메모리 관리자는 물리 메모리의 부족한 부분을 스왑 영역으로 보충합니다. 물리 메모리가 꽉 차면 일부 프로세스를 스왑 영역으로 보내고(스왑아웃), 몇 개의 프로세스가 작업을 마치면 스왑 영역에 있는 프로세스를 메모리로 가져옵니다(스왑인).

가상 메모리의 크기

가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리(실제 메모리)와 스왑 영역을 합한 크기입니다.

가상 메모리 시스템에서 메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 실제 메모리의 물리 주소로 변환합니다. 이러한 작업을 동적 주소 변환(DAT, Dynamic Address Translation)이라고 합니다. 동적 주소 변환을 거치면 프로세스가 아무 제약 없이 사용자 데이터를 물리 메모리에 배치할 수 있습니다.

2. 매핑 테이블의 필요성과 역할

가상 메모리 시스템에서 가변 분할 방식을 이용한 메모리 관리 기법은 세그먼테이션, 고정 분할 방식을 이용한 메모리 관리 기법은 페이징이라고 합니다.

3. 지역성

지역성(locality) : 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질

국부성 또는 집약성이라고도 하며 크게 공간의 지역성, 시간의 지역성, 순차적 지역성으로 나뉩니다.

1. 공간의 지역성 :
   공간의 지역성(spatial locality)은 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높음을 의미합니다.

2. 시간의 지역성 :
   시간의 지역성(temporal locality)은 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높음을 의미합니다.

3. 순차적 지역성 :
   순차적 지역성(sequential locality)은 작업이 순서대로 진행되는 것을 의미합니다.

지역성 이론은 많은 곳에서 사용됩니다. 특히 캐시는 지역성 이론을 사용하는 대표적인 장치입니다. 시간적으로나 지역적으로 가까이 있는 데이터를 가져옴으로써 캐시 적중률을 높일 수 있습니다. 예를 들어 현재 5행을 실행하고 있다면 10~19행과 200~219행 중에서 당연히 10~19행을 가져오는 것이 유리합니다. 프로그램을 작성할 때 goto 문을 사용하지 말라고 하는 것도 이러한 이유입니다. 지역성에 근거하여 현재 실행하는 행과 가까운 행을 캐시 메모리로 가져오고 있는데 갑자기 goto 문을 사용하여 엉뚱한 행으로 이동해 버리면 이미 가져온 데이터가 쓸모없어집니다.

페이지 교체 알고리즘(page replacement algorithm)도 지역성 이론을 기반으로 합니다. 페이지 교체 알고리즘은 메모리가 꽉 차 특정 페이지를 스왑으로 보내야만 새로운 페이지를 받을 수 있는 상황에서 물리 메모리에 있는 페이지 중 하나를 골라 내보낼 때 사용합니다. 쫓아낼 페이지를 선정할 때는 되도록 앞으로 사용할 가능성이 적은 페이지를 찾아야 하는데 이 때 사용하는 이론이 지역성입니다.

📌 페이징 기법

1. 페이징 기법의 구현

페이징 기법은 고정 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 주소 공간을 같은 크기로 나누어 사용합니다. 왼쪽의 가상 주소는 프로세스 입장에서 바라본 메모리 공간으로 항상 0번부터 시작합니다. 가상 주소의 분할된 각 영역을 페이지라고 부르며 첫 번째 영역은 페이지 0, 두 번째 영역은 페이지 1과 같이 번호를 매겨 관리합니다. 물리 메모리의 각 영역은 가상 주소의 페이지와 구분하기 위해 프레임(frame)이라고 부릅니다. 페이지와 프레임의 크기는 같습니다.

화살표는 가상 주소의 각 페이지가 물리 메모리의 어디에 위치하는지를 나타냅니다. 크기가 같기 때문에 페이지는 어떤 프레임에도 배치될 수 있습니다. 즉 어떤 페이지가 어떤 프레임에 있는지에 대한 연결(매핑) 정보는 페이지 테이블에 담겨 있습니다.

invalid는 해당 페이지가 스왕 영역에 있다는 의미입니다.

2. 페이징 기법의 주소 변환

주소 변환 과정

정형화된 주소 변환

페이징 기법에서는 가상 주소를 VA=<P, D>로 표현합니다. VA는 가상 주소(virtual address), P는 페이지(page), D는 페이지의 처음 위치에서 해당 주소까지의 거리(distance)를 의미합니다.

가상 주소 30번을 VA=<P, D> 방식으로 정의하면 VA=<3, 0>으로 작성할 수 있습니다. 이는 페이지 3의 0번 주소라는 의미입니다.

페이징 기법의 주소 변환은 가상 주소 VA=<P, D>를 물리 주소 PA=<F, D>로 변환하는 것입니다. PA는 물리 메모리의 주소를 가리키는 용어로 물리 주소 또는 실제 주소라고 합니다. PA=<F, D>에서 F는 프레임(frame), D는 프레임의 처음 위치에서 해당 주소까지의 거리(distance)를 의미합니다.

페이지 테이블에서 페이지 번호를 찾아 해당 프레임 번호를 쫓아가면 됩니다. 페이지 테이블은 페이지 번호와 프레임 번호로 구성되며, 각각의 한 줄을 페이지 테이블 엔트리(PTE; Page Talbe Entry)라고 부릅니다. 페이지 테이블은 페이지 번호와 프레임 번호로 구성된 페이지 테이블 엔트리의 집합입니다.

16bit CPU의 주소 변환 예

페이지의 크기가 다양할 경우 가상 주소를 <P, D>로 변환하는 공식은 다음과 같습니다.

가상 주소를 <P, D>로 표현하는 공식

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

16bit CPU 컴퓨터에서 한 페이지의 크기가 2$^{10}$B일 때 페이징 시스템의 구성을 살펴봅시다. 16bit CPU 컴퓨터에서 한 프로세스가 사용할 수 있는 가상 메모리의 크기는 2$^{16}$(65,536)B입니다. 사용자는 0번부터 65535(2$^{16}$-1)번까지 가상 주소 공간을 사용할 수 있습니다. 한 페이지의 10bit는 페이지의 처음 위치에서 해당 주소까지의 거리로 사용합니다.

페이지의 크기가 2$^{10}$(1,024)B이므로 전체 페이지의 수는 2$^{6}$, 즉 64개이고 페이지 0번부터 63번까지 존재합니다.

실제 메모리가 최대가 아니더라도 잘 작동한다는 것을 보여주기 위해 일부러 물리 메모리의 크기를 작게 잡아 도식화했습니다. 이 경우 부족한 물리 메모리는 스왑으로 처리하면 됩니다. 따라서 물리 주소의 부족한 부분은 페이징 시스템에서 문제가 되지 않습니다.

물리 주소의 크기와 상관 없이 가상 주소를 많이 사용하면 페이지 테이블의 크기가 늘어나고, 적게 사용하면 페이지 테이블의 크기가 줄어듭니다.

3. 페이지 테이블 관리

메모리 공유

프로세스는 메모리에 올라와야 실행이 가능하므로 모든 프로세스의 일부 페이지가 물리 메모리의 프레임에 올라와 있고, 어떤 페이지가 어떤 프레임에 있는지 관리하기 위해 프로세스마다 페이지 테이블을 운영 중입니다.

페이지 테이블은 메모리 관리자가 자주 사용하는 자료구조이므로 필요시 빨리 접근할 수 있어야 합니다. 따라서 페이지 테이블으느 물리 메모리 영역 중 운영체제 영역의 일부분에 모아놓습니다. 시스템 내에는 여러 개의 프로세스가 존재하고 프로세스마다 하나의 페이지 테이블이 있기 때문에 전체 페이지 테이블의 크기는 프로세스의 수에 비례해서 커집니다. 한 번에 실행하는 프로세스의 수가 많으면 페이지 테이블의 크기가 같이 커지고, 그에 따라 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듭니다.

페이지 테이블 관리의 가장 큰 문제는 페이지 테이블의 크기가 작지 않다는 것입니다. 따라서 페이지 테이블의 크기를 적정하게 유지하는 것이 페이지 테이블 관리의 핵심입니다.

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

페이지 테이블에 빠르게 접근하기 위해 레지스터가 존재합니다. 각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 재빨리 파악할 필요가 있습니다. 그래서 각 페이지 테이블의 시작 주소를 페이지 테이블 기준 레지스터(PTBR; Page Table Base Register)에 보관합니다. 페이지 테이블 기준 레지스터는 각 프로세스의 프로세스 제어 블록에 저장되는 데이터로, 물리 메모리 내에 페이지 테이블의 시작 주소를 가지고 있습니다.

쓰기 시점 복사

프로세스 A가 사용하더 전체 페이지 테이블을 복사하면 프로세스를 손쉽게 복사할 수 있습니다. 그런데 프로세스를 복사하면 공유할 수 있는 프레임도 있지만 공유할 수 없는 프레임도 있습니다.

그렇다면 공유할 수 없는 데이터를 저장하기 위한 메모리 공간은 언제 확보해야 할까요? 사용할지 안 할지 모르는 데이터를 위해 새로운 공간을 만드는 것은 낭비입니다. 그러므로 운영체제는 필요한 순간까지 새로운 프로엠의 확보를 미룹니다.

데이터 변화가 있을 때까지 복사를 미루는 방식을 쓰기 시점 복사(copy on write)라고 합니다.

변환 색인 버퍼

가상 주소를 물리 주소로 변환하는 작업은 CPU 안에 있는 메모리 관리 유닛(MMU)이 담당합니다. 가상 주소를 물리 주소로 변환하려면 메모리에 두 번 접근해야 합니다.

1. 페이지 테이블은 메모리에 있기 때문에 MMU는 메모리에 있는 페이지 테이블에 접근하여 물리 주소로 변환합니다.

2. 변환된 물리 주소를 이용하여 필요한 데이터를 가져옵니다.

CPU 안에 있는 레지스터가 캐시에 접근할 때보다 물리 메모리에 접근할 때 시간이 몇 배 이상 더 걸립니다. 따라서 가상 주소를 물리 주소로 변환한 후 데이터를 가져오기 위하여 메모리에 두 번이나 접근하는 방식은 CPU 성능을 떨어뜨립니다.

이러한 문제를 개선하기 위하여 페이지 테이블의 일부를 CPU 안쪽으로 가져오는데, 이를 변환 색인 버퍼(TLB; Translation Look-ahead Buffer)라고 합니다. 변환 색인 버퍼는 캐시된 페이지 테이블입니다. 지역성 이론에 근거하여 현재 사용 중이거나 사용이 예상되는 페이지 테이블의 일부를 CPU 안쪽에 가져옵니다.

먼저 주소 변환을 위해 변환 색인 버퍼를 찾습니다. 원하는 페이지 번호가 변환 색인 버퍼에 있으면 TLB 히트(TLB hit)라고 하며, 곧바로 물리 주소로 변환됩니다. 원하는 페이지 번호가 없으면 TLB 미스(TLB miss)라고 하며, 메모리에 있는 페이지 테이블을 사용하여 프레임 번호로 변환합니다.

메모리에 있는 페이지 테이블에는 모든 페이지 번호가 순서대로 나열되어 있기 떄문에 1개의 열로 구성되었습니다. 그러나 CPU 안에 존재하는 변환 색인 버퍼에는 전체 페이지 테이블의 일부만 있어 <페이지 번호, 프레임 번호>의 쌍으로 이루어집니다. 변환 페이지 버퍼는 페이지 번호와 프레임 번호의 2개 열로 구성됩니다. 변환 색인 버퍼를 검색할 때는 하드웨어적으로 병렬 검색이 가능하도록 구성됩니다. 즉, 한번에 모든 행의 페이지를 검생하여 원하는 데이터가 있는지 확인할 수 있습니다.

역 페이지 테이블

역 페이지 테이블(invert page table) 방식은 기존 페이징 방식과는 반대로 페이지 테이블을 구성합니다. 이 방식은 물리 메모리의 프레임 번호를 기준으로 테이블을 구성하는 것으로 물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는지를 표시합니다.

역 페이지 테이블의 가장 큰 특징은 프로세스의 수와 상관없이 테이블이 하나만 존재한다는 것입니다. 따라서 테이블의 크기가 작다는 장점이 있습니다.

역 페이지 테이블 0번 행은 프레임 0번에 어떤 프로세스의 페이지가 있는지 표시합니다.

역 페이지 테이블은 테이블의 크기가 작지만 프로세스가 물리 메모리에 접근할 때 프로세스 아이디와 페이지 번호를 모두 찾아야 하는 것이 단점입니다.

역 페이지 테이블 방식에서 주소 변환 시 메모리 관리자는 주소 변환을 해야 하는 프로세스 아이디와 페이지 번호가 물리 메모리에 있는지를 역 페이지 테이블에서 검색합니다. 원하는 프레임 번호가 있는 경우, 역 페이지 테이블의 위치가 프레임 번호가 됩니다.

다단계 페이지 테이블

주소 공간이 늘어나 페이지 테이블의 크기가 늘어나면 한꺼번에 관리하기가 힘들어집니다. 이러한 문제를 해결하기 위해 만든 방식이 다단계 페이지 테이블입니다. 다단계 페이지 테이블의 기본 구조는 일정 크기로 자른 페이지 테이블의 바깥쪽에 이를 관리하는 새로운 테이블을 만드는 것입니다.

새로 생성한 1차 테이블(집합 테이블, set table)은 일정하게 자른 2차 페이지 테이블의 물리 메모리 시작 주소를 나타냅니다.

1차 테이블에서 I(Invalid)라고 표시된 것은 해당 2차 페이지 테이블이 아직 만들어지지 않았다는 의미입니다. 다단계 페이지 테이블 방식에서는 전체 페이지 테이블을 한꺼번에 만들지 않고 필요할 때마다 만듭니다.

페이지 테이블의 크기가 매우 큰 경우, 3단계나 4단계 페이지 테이블 방식이 사용되기도 하며 페이지 테이블의 주소는 계속 세분화됩니다. 이러한 특징 때문에 다단계 페이지 테이블 방식을 멀티페이지 매핑(multi-page mapping)이라고 부릅니다.

다단계 페이지 테이블 방식의 장점은 크기가 큰 페이지 테이블을 같은 크기의 묶음으로 나누어서 효율적으로 관리할 수 있다는 것입니다. 페이지 테이블 전체를 한꺼번에 만들지 않고 필요할 때마다 생성하고 관리함으로써 물리 메모리의 공간을 효율적으로 관리할 수 있습니다.

📌 세그먼테이션 기법

세그먼테이션 기법 : 가변 분할 방식을 이용한 가상 메모리 관리 기법

이 기법은 물리 메모리를 프로세스 크기에 따라 가변적으로 나누어 사용합니다.

1. 세그먼테이션 기법의 구현

페이징 기법과 마찬가지로 세그먼테이션 기법도 테이블을 사용하는데 이를 세그먼테이션 테이블(segmentation table) 또는 세그먼테이션 매핑 테이블(segmentation mapping table)이라고 합니다.

세그먼테이션 테이블에는 세그먼트의 크기를 나타내는 limit와 물리 메모리의 시작 주소를 나타내는 address가 있습니다. 페이징 기법에서는 메모리를 같은 크기의 페이지 단위로 분할하기 때문에 크기 정보를 유지할 필요가 없지만 세그먼테이션 기법에서는 프로세스 크기에 따라 메모리를 분할하기 때문에 크기 정보를 포함합니다. 각 세그먼트가 자신에게 주어진 메모리 영역을 넘어가면 안 되기 때문에 세그먼트의 크기 정보에는 크기를 뜻하는 size 대신 제한을 뜻하는 limit를 사용합니다.

세그먼테이션 기법에서도 물리 메모리가 부족할 때는 스왑 영역을 사용합니다.

장점 : 메모리를 프로세스 단위로 관리하기 때문에 세그먼테이션 테이블이 작고 단순

단점 : 물리 메모리의 외부 단편화로 인해 관리가 복잡

2. 세그먼테이션 기법의 주소 변환

세그먼테이션 기법에서는 가상 주소를 VA=<S, D>로 표현합니다. S는 세그먼트 번호(segment number), D는 세그먼트 시작 지점에서 해당 주소까지의 거리(distance)를 의미합니다.

1. 먼저 가상 주소를 구합니다. 프로세스 A는 세그먼트 0으로 분할되었으므로 S는 0, D는 32입니다. 따라서 가상 주소는 VA=<0, 32>입니다.

2. 세그먼테이션 테이블에서 세그먼트 0의 시작 주소 120을 알아낸 후 거리 32를 더하여 물리 주소 152번을 구합니다. 이때 메모리 관리자는 거리가 세그먼트의 크기보다 큰지 점검합니다. 크다면 메모리를 벗어나는 것이므로 메모리 오류를 출력하고 해당 프로세스를 강제 종료합니다. 크지 않다면 물리 주소를 구합니다.

3. 물리 주소 152번에 접근하여 원하는 데이터를 읽거나 씁니다.

세그먼테이션 테이블의 limit는 메모리를 보호하는 역할을 합니다.

트랩(trap) : 자신의 영역을 벗어나는 주소에 접근하거나 숫자를 0으로 나누는 것과 같이 사용자가 의도치 않게 일으키는 인터럽트

트랩이 발생하면 운영체제는 사용자에게 세그먼테이션 오류(segmentation fault)메시지를 보냅니다. 결과적으로 가상 주소인 VA=<S, D>에서 D는 메모리 보호의 의미를 담고 있습니다.

📌 캐시 매핑 기법

1. 캐시 직접 매핑

메모리의 페이징 방식과 마찬가지로 캐시도 메모리를 일정 크기로 나누며 일정 크기로 나눈 덩어리를 페이지 P라고 부릅니다. CPU가 메모리에 접근하려 할 때 사용하는 주소를 <P, D>로 표현하는데 여기서 P는 페이지 번호, D는 페이지 내에서 거리를 의미합니다. 여기까지는 페이징 기법과 똑같습니다.

캐시 직접 매핑에서는 메모리의 어떤 블록에서 올라온 페이지인지만 확인하면 됩니다.

캐시 직접 매핑 방식의 가장 큰 특징은 메모리의 페이지가 캐시의 정해진 위치에만 들어갈 수 있다는 것입니다.

장점 : 메모리 페이지가 캐시의 같은 위치에 올라오기 때문에 태그만 확인하면 캐시 히트나 캐시 미스를 빠르게 확인할 수 있습니다.

단점 : 페이지가 같은 위치에만 올라오기 때문에 자리다툼이 발생합니다.

2. 캐시 연관 매핑

메모리가 캐시의 어느 위치에도 자유롭게 올라갈 수 있으므로 캐시가 메모리의 주소를 전부 가지고 있습니다.

장점 : 캐시 메모리를 자유롭게 사용할 수 있습니다.

단점 : 캐시 히트인지, 캐시 미스인지 확인하기 위해 캐시의 모든 주소를 검색해야 합니다.

따라서 캐시 연관 매핑은 캐시 직접 매핑보다 느립니다.

3. 캐시 집합-연관 매핑

캐시 집합-연관 매핑은 캐시 직접 매핑과 캐시 연관 매핑의 장점만 취한 방식입니다.

끝이 00(bd00)으로 끝나는 페이지는 캐시에 하나밖에 없기 때문에 자리다툼이 일어난다고 앞서 언급했습니다. 집합-연관 매핑에서는 직접 매핑을 하는 캐시 메모리를 K개로 나눔으로써 같은 끝자리를 가진 캐시 메모리도 K개가 되어 자리다툼 문제가 완화되었습니다. 또한 집합 내에서 직접 매핑을 사용하기 때문에 연관 매핑처럼 모든 캐시를 뒤지는 일 없이 바로 캐시 히트 여부를 알 수 있습니다.

이처럼 집합-연관 매핑에서는 직접 매핑의 자리다툼 문제가 완화됩니다.