[OSTEP] 스터디 9주차 - 메모리 가상화 4

이 전 시간에는 세그멘테이션에 대해 알아봤다. 이 방법은 공간 관리 문제를 해결하는 방법 중 하나이지만 공간 자체가 단편화될 수 있고, 할당이 점점 더 어려워진다는 문제를 가지고 있다.

그래서 이번에 배울 것은 공간을 동일한 크기의 조각으로 분할하는 페이징에 대해 알아보겠다. 이 방식에서는 프로세스의 주소 공간을 고정 크기의 단위인 페이지로 나눈고 이에 상응하여 물리 메모리도 페이지 프레임이라고 불리는 고정 크기의 슬롯 배열로 간주한다. 각 페이지 프레임은 하나의 가상 메모리 페이지를 저장할 수 있다.

---

간단한 예제 및 개요

위 그림은 총 64바이트이며 4개의 16바이트 페이지로 구성된 주소 공간의 예를 보여준다. 물리 메모리는 고정 크기의 슬롯들로 구성된다.

이 예시는 8개의 페이지 프레임으로 이루어진 128바이트의 작은 물리 메모리를 가정한다. 페이징의 가장 큰 장점은 유연성이다. 페이징을 사용하면 프로세스의 주소 공간 사용 방식과 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 어느 방향으로 커지는지, 어떻게 사용되는지 고민할 필요가 없다.

또 다른 장점은 단순함이다. 운영체제가 64바이트의 가상 주소 공간을 8페이지 물리 메모리에 배치하려면, 단순히 비어있는 4개의 페이지만 찾으면 된다.(이건 위에 16바이트를 1페이지로 가정했기 때문) 이를 위해 운영체제는 빈 페이지 리스트를 유지하고, 리스트의 첫 네 개 페이지를 선택할 수 있다.

운영체제는 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치를 기록하기 위해 프로세스마다 페이지 테이블이 라는 자료구조를 유지한다. 페이지 테이블의 역할은 가상 주소 공간의 각 페이지에 대한 주소 변환 정보(물리 페이지 프레임의 위치)를 저장하는 것이다.

예시에서는 가상 페이지(VP) 0은 물리 페이지 프레임(PF) 3에, VP 1은 PF 7에, VP 2는 PF 5에, VP 3은 PF 2에 매핑되어 있다. 페이지 테이블은 프로세스마다 존재한다는 점을 기억해야 한다. 다른 프로세스를 실행한다면, 그 프로세스를 위한 별도의 페이지 테이블이 필요할 것이다.

---

주소 변환 과정을 살펴보겠다. 64바이트의 작은 주소 공간을 가진 프로세스가 메모리 접근을 수행한다고 가정해 본다.

movl <virtual address>, %eax

이 명령어는 가상 주소의 데이터를 eax 레지스터에 로드한다. 프로세스가 생성한 가상 주소를 변환하기 위해, 먼저 가상 주소를 가상 페이지 번호와 페이지 내의 오프셋이라는 두 개의 요소로 분할한다.

상위 2 비트가 페이지를 선택하는 역할을 하고 나머지 비트는 페이지 내에서 원하는 바이트의 위치를 나타내기에 6비트가 필요하다.

movl 21, %eax

21을 이진수로 변환하면 010101이므로, VPN은 1, Offset은 5다. 앞서 예시에서 VPN 1은 PF 7과 매핑되었으므로, 주소 변환 과정은 다음과 같다.

Offset은 동일하게 적용되고, VPN만 PFN으로 변환되어 최종적으로 1110101이라는 물리 주소를 얻게 된다.

---

페이지 테이블 저장 위치?

페이지 테이블은 매우 커질 수 있다. 예를 들어, 4KB 크기의 페이지를 가지는 전형적인 32비트 주소 공간을 생각해 보겠다. 이 가상 주소는 20비트 VPN과 12비트 Offset으로 구성된다(2^12 = 4KB, 나머지는 VPN).

만약 100개의 프로세스가 실행 중이라면 400MB의 메모리가 필요하다는 것을 의미한다. 현재와 같이 GB 단위의 메모리를 갖고 있는 상황에서도 주소 변환을 위해 이렇게 많은 메모리가 필요하다는 것은 다소 비정상적이다.

위 그림에서 PF0에 페이지 테이블이 존재하는 것을 볼 수 있다.

---

페이지 테이블에는 실제로 무엇이 있는가?

페이지 테이블은 가상 주소(페이지 번호)를 물리 주소(물리 페이지 프레임 번호)로 매핑하는 데 사용하는 자료구조이다. 가장 간단한 형태는 선형 페이지 테이블로, 단순한 배열 형태다. 원하는 물리 프레임 번호(PFN)를 찾기 위해 가상 페이지 번호(VPN)로 배열의 항목에 접근하고, 그 항목의 페이지 테이블 항목(PTE)을 검색한다.

각 PTE에는 다음과 같은 여러 비트들이 포함된다:

• Valid Bit: 특정 변환의 유효 여부를 나타내기 위해 사용. 예를 들어, 프로그램이 실행을 시작할 때 코드와 힙이 주소 공간의 한쪽에 있고 반대쪽은 스택이 차지하고 있을 것이다. 그 사이의 모든 미사용 공간은 invalid로 표시되며, 프로세스가 그런 메모리에 접근하려고 하면 트랩(Trap)이 발생한다.
• Protection Bit: 페이지가 읽기 가능한지, 쓰기 가능한지, 실행 가능한지를 표시하기 위해 사용. 허용되지 않은 방식으로 접근할 경우 트랩이 발생한다.
• Present Bit: 해당 페이지가 물리 메모리에 존재하는지, 아니면 디스크로 스왑 아웃되었는지를 나타내는 데 사용된다.
• Reference Bit: 페이지가 접근되었는지를 추적하는 데 사용. 이는 어떤 페이지가 인기 있는지 결정하여 메모리에 유지되어야 할 페이지를 판단하는 데 유용하다.

---

페이징: 너무 느림

페이징을 사용할 때 페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 가능성이 있다. 페이징의 문제 중 하나는 모든 메모리 참조마다 페이지 테이블에서 주소 변환 정보를 읽어와야 한다는 점이다. 이로 인해 메모리 접근이 최소 한 번 더 발생하게 되는데, 메모리 접근은 비용이 높은 연산이므로 프로그램의 실행 속도가 크게 저하될 수 있다.

이 문제를 해결하기 위해, 하드웨어의 도움을 받을 수 있다. 바로 Translation Lookaside Buffer (TLB) 라는 특별한 하드웨어 캐시를 사용하는 것이다.

---

페이징: 더 빠른 변환 (TLB)

TLB는 CPU의 Memory Management Unit (MMU) 내에 위치한 작고 빠른 하드웨어 캐시다. TLB의 목적은 최근에 사용된 가상 주소와 물리 주소 간의 매핑 정보를 저장하여, 주소 변환 속도를 향상시키는 것이다.

프로세스가 가상 주소를 사용하여 메모리에 접근하면, 하드웨어는 먼저 TLB에서 해당 가상 주소의 변환 정보를 찾아본다. 만약 TLB에 정보가 있다면 (TLB Hit), 곧바로 물리 주소를 얻어 메모리에 접근할 수 있다. 이 경우, 페이지 테이블을 읽는 추가 작업 없이 주소 변환을 완료할 수 있으므로 매우 빠르다.

반면에, 원하는 정보가 TLB에 없는 경우 (TLB Miss)에는 기존대로 페이지 테이블을 참조하여 주소 변환을 진행해야 한다. 이 과정에서 얻은 변환 정보는 향후 재사용을 위해 TLB에 저장된다.

적절한 크기의 TLB를 사용하면, 대부분의 메모리 접근이 TLB Hit로 처리되므로 전체적인 주소 변환 속도가 크게 향상된다. 이렇게 TLB를 사용함으로써 페이징의 성능 문제를 완화하고, 가상 메모리를 실질적으로 사용 가능하게 만들 수 있다.

주요 용어 정리

• 페이징 (Paging): 가상 메모리를 일정한 크기의 페이지 단위로 나누어 관리하는 기법.
• 페이지 (Page): 가상 메모리를 일정한 크기로 나눈 블록. 주소 변환의 기본 단위가 됨.
• 페이지 테이블 (Page Table): 각 페이지의 가상 주소와 실제 물리 주소 간의 매핑 정보를 저장하는 자료구조.
• 주소 변환 (Address Translation): 가상 주소를 물리 주소로 변환하는 과정.
• Translation Lookaside Buffer (TLB): 주소 변환을 가속하기 위한 하드웨어 캐시. 최근 사용된 가상-물리 주소 매핑 정보를 저장함.
• TLB Hit: 원하는 주소 변환 정보가 TLB에 존재하는 경우.
• TLB Miss: 원하는 주소 변환 정보가 TLB에 없는 경우. 페이지 테이블을 참조하여 변환을 진행해야 함.

---

TLB의 기본 알고리즘

1. TLB 검색 과정 가상 주소가 제공되면, 해당 주소의 가상 페이지 번호(VPN)를 추출하고, TLB에서 이 VPN에 해당하는 엔트리를 병렬적으로 검색한다. 일치하는 엔트리가 있는 경우, 그 엔트리에 포함된 물리 페이지 번호(PPN)로 물리 주소를 계산한다.
2. TLB 히트 유효한 엔트리가 존재하면, 즉시 물리 주소를 생성하고 메모리에 액세스한다. 이 과정을 TLB 히트라고 한다.
3. TLB 미스 일치하는 엔트리가 없을 경우, TLB 미스가 발생하며, 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환한다. 변환된 주소는 TLB에 추가되어 다음 접근 시 빠르게 찾을 수 있도록 한다.

예제: 배열 접근

int main() {
    int array[100];
    array[50] = 10;  // 배열의 특정 위치에 데이터 쓰기
    return 0;

이 코드에서 array[50]에 값을 할당하려면 다음과 같은 과정이 필요하다.

1. 가상 주소 0x1400 (50 * 4) 생성
2. TLB 검색: 0x1400에 대한 엔트리가 존재하는지 확인
   • TLB 히트: 엔트리가 존재하면 엔트리에 포함된 물리 페이지 번호를 사용하여 물리 주소를 생성하고 메모리에 액세스
   • TLB 미스: 엔트리가 존재하지 않으면 페이지 테이블 워크를 통해 변환 정보를 검색
3. 페이지 테이블 워크: 페이지 테이블에서 가상 페이지 번호 0x3C에 대한 엔트리를 찾아 물리 페이지 번호를 얻음
4. TLB에 엔트리 추가: 0x1400 (VPN)과 0x0A00 (PPN)으로 구성된 엔트리를 TLB에 추가
5. 물리 주소 생성: 물리 페이지 번호 0x0A00과 오프셋 0x00을 사용하여 물리 주소 0xA000 생성
6. 메모리 액세스: 0xA000 주소에 값 10 저장

---

TLB 미스는 누가 처리할까?

TLB 미스는 Translation Lookaside Buffer(번역 조회 버퍼)에서 원하는 주소 변환 정보를 찾지 못할 때 발생하는 상황이다. TLB 미스를 처리하는 방법은 두 가지가 있다: 하드웨어 관리와 소프트웨어(운영 체제) 관리다.

하드웨어 관리 방식은 주로 복잡한 명령어 집합인 CISC(complex instruction set computers) 구조에서 사용된다. 하드웨어가 TLB 미스를 처리하려면 페이지 테이블에 대한 정보를 갖고 있어야 한다. TLB 미스가 발생하면 하드웨어가 페이지 테이블에서 필요한 정보를 추출하고 TLB를 갱신한 후 명령어를 재실행한다.

반면에 소프트웨어 관리 방식은 최근에 등장한 RISC(reduced instruction set computing) 구조에서 주로 사용된다. TLB 미스가 발생하면 하드웨어가 예외 시그널을 발생시키고, 이를 받은 운영 체제가 커널 모드로 전환하여 트랩 핸들러를 실행한다. 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고 TLB를 갱신한 후에 명령어를 재실행한다.

이 두 가지 방법의 중요한 차이점은 하드웨어 관리 방식은 하드웨어가 직접 TLB 미스를 처리하는 데 반해, 소프트웨어 관리 방식은 운영 체제의 코드가 TLB 미스를 처리한다는 것이다. 소프트웨어 관리 방식은 유연성이 높고 하드웨어 변경에 영향을 받지 않지만, 성능 측면에서는 하드웨어 관리 방식에 비해 부가적인 오버헤드가 있을 수 있다.

TLB 미스가 발생하면 운영 체제의 페이지 폴트 핸들러가 실행되어 페이지 테이블을 참조하여 필요한 가상-물리 주소 변환 정보를 찾는다. 이 정보는 TLB에 로드되고, 이후 메모리 액세스는 TLB 히트로 처리된다.

---

TLB의 구성: 무엇이 있나?

항목	설명
가상 페이지 번호(VPN)	가상 주소에서 추출된 페이지 번호
물리 페이지 프레임 번호(PPFN)	물리 메모리에서 해당 페이지를 저장하는 프레임 번호
엑세스 권한	해당 페이지에 대한 액세스 권한(읽기, 쓰기, 실행)을 나타낸다.
유효 비트	해당 엔트리가 유효한지 여부를 나타낸다.
ASID (Address Space Identifier)	프로세스 간 TLB 엔트리 충돌을 방지

---

TLB의 문제: 문맥 교환

다른 프로세스는 다른 가상 주소 공간을 사용하기 때문에 문맥 교환이 발생하면 현재 프로세스의 TLB 엔트리가 유효하지 않게 될 수 있다.

이 문제를 해결하기 위해 다음과 같은 방법을 사용할 수 있다.

• TLB를 비우기: 문맥 교환이 발생할 때마다 TLB를 비운다.
• ASID(Address Space Identifier) 사용: TLB 엔트리에 ASID를 추가하여 프로세스별 TLB 엔트리를 구분한다.

---

이슈: 교체 정책

TLB Miss가 발생하면 TLB에 새 엔트리를 추가해야 한다. 하지만 TLB는 제한된 크기의 캐시이기 때문에 어떤 엔트리를 교체해야 할지 결정하는 정책이 필요하다.
TLB의 교체 정책은 제한된 공간과 성능 요구 사항을 충족하기 위해 매우 중요하다. 각 정책은 특정 시나리오에서의 성능 최적화를 목표로 한다.

일반적인 교체 정책으로는 다음과 같은 것들이 있다.

• LRU (Least Recently Used): 최근에 사용되지 않은 항목을 먼저 교체한다.
• FIFO (First In, First Out): 먼저 추가된 항목을 먼저 교체한다.
• Random Replacement: 무작위 선택을 통한 교체

---

물리 메모리 크기의 극복: 메커니즘

스왑 공간

개념: 물리 메모리가 부족하면 사용하지 않는 페이지를 하드 디스크의 특정 영역(스왑 공간)에 백업하고, 필요하면 다시 메모리로 불러오는 기술

장점

• 물리 메모리보다 훨씬 저렴한 하드 디스크 공간을 활용하여 가상 메모리 공간을 확장 가능

스왑 공간 사용 방식 - 가상 메모리 공간이 부족하면 사용하지 않는 페이지를 스왑 공간으로 백업하고, 필요하면 다시 메모리로 불러온다.

단점

• 하드 디스크는 메모리보다 훨씬 느려 페이지 폴트 발생 시 성능 저하

---

Present Bit

개념: 페이지 테이블에 존재하는 각 엔트리에 설정되는 플래그 비트

기능: 해당 페이지가 현재 물리 메모리에 존재하는지 여부를 나타냄

활용

• Present bit가 1이면 페이지가 메모리에 존재하므로 바로 접근 가능
• Present bit가 0이면 페이지가 스왑 공간에 존재하므로 페이지 폴트 발생

---

페이지 폴트

개념: 프로세스가 메모리에 존재하지 않는 페이지에 접근하려는 경우 발생하는 예외 상황

처리 과정

1. 운영체제는 해당 페이지를 스왑 공간에서 메모리로 로드
2. 페이지 테이블을 업데이트하여 Present bit를 1로 설정
3. 프로세스가 다시 해당 페이지에 접근하도록 허용

영향: 페이지 폴트는 메모리 접근 지연을 야기하여 성능 저하를 초래한다.