[CS:APP] 9.3 - 9.4 : 가상 메모리 질문 털이

2025.04.23 - [컴퓨터 이론] - [CS:APP] 9 : Virtual Memory [- 9.8]

[CS:APP] 9 : Virtual Memory [- 9.8]

 

9.3 VM as a Tool for Caching

[원문] 가상 메모리는 배열로 조직된다?

가상 메모리 공간은 페이지 단위로 나뉘어 있고, 이 페이지들을 배열처럼 연속적으로 관리한다.

즉, 주소 공간 전체를 같은 크기의 페이지들로 분할하고, 각 페이지는 페이지 테이블이라는 배열 구조를 통해 물리 메모리와 매핑된다.

• 페이지는 가상 주소 공간을 일정한 크기로 나눈 단위이다. 배열의 각 인덱스처럼 취급한다.
• 페이지 테이블은..
  • 배열의 인덱스는 가상 페이지 번호를 가리키고,
  • 배열의 값은 대응되는 물리 페이지 번호와 속성 정보를 뜻한다.
  • 즉, 가상 페이지 번호 = 물리 페이지 프레임 + 속성 으로 매핑된다.
• MMU가 할 일
  • CPU가 가상 주소를 생성하면, MMU가 페이지 번호를 인덱스로 삼아 페이지 테이블을 참조해 물리 주소를 계산한다.

아니 그니까 왜 배열이라고 표현하냐고?

페이지 번호는 정수 인덱스처럼 사용된다. (0 1 2 ..) 이 정수 인덱스로 페이지 테이블에 접근하게 된다.

• 물리적으로는 비연속일 수 있지만, 논리적으로는 배열처럼 관리된다. 이 구조 덕분에 MMU가 빠르고 단순하게 매핑이 가능하다.

즉, 가상 주소 공간이 일정 크기의 블록으로 나뉘고, 이 블록들이 배열처럼 번호가 붙어 페이지 테이블을 통해 관리 된다는 구조적 비유이다.

가상 페이지의 상태는 세 가지 명확히 구분되어 서로 겹치지 않는 영역으로 나뉜다.

• 이 세 영역은 가상 주소 공간을 기능에 따라 나눈 것이며, 보호/접근 방식, OS의 관리 방법 등이 다르다.

상태	뜻	설명
Unallocated	가상 페이지가 아직 어떤 물리 메모리와도 연결되어 있지 않다.	아직 사용되지 않는다. 접근시 폴트 발생!
Cached	해당 가상 페이지가 물리 메모리에 올라와 있다.	실행 중이며 접근이 가능하다. MMU가 바로 변환 할 수 있다.
Uncached	디스크 등 보조 저장 장치에만 존재한다.	최근 사용하지 않아 물리 메모리에서 제거 되었다. 접근 시 페이지 폴트 발생 후 다시 로딩된다.

Unallocated (1)→ Cached (2)→ Uncached (3)→ Cached

• (1) 처음 접근 시 페이지 폴트 과정을 통해 Cached로 바뀐다.
• (2) 오래 쓰이지 않으면 스왑 아웃되어 Uncached가 된다.
• (3) 다시 필요해지게 되면, 디스크에서 읽어오며 스왑 인이 일어난다.

대체 왜 이런걸 나눕니까?

여러가지 이유가 있다.

• 메모리 자원을 효율적으로 관리하기 위해서이다.
  → 필요할 때만 메모리를 할당한다. 쓰지 않는 것은 디스크로 쫓아내버린다.
• 페이지 폴트 처리의 근거가 되기 때문이다.
  → 어떤 페이지가 캐시됐는지 알아야 폴트를 처리 할 수 있다.
• OS의 메모리 관리 전략 구현에 필요하다. 예를 들어 LRU 교체 등.

즉, 가상 메모리의 상태는 그 페이지가 현재 어떻게 관리되고 있는지를 나타낸다.
이 세 가지의 상태는 각 페이지가 메모리에 대해 어떤 상태인지를 구분하는 구체적인 표현이다.
이 상태 구분은 페이지 폴트나 스왑 동작을 이해 할 때 매우 중요해진다.

9.3.1 DRAM Cache Organization

• 책 초반부분에 SRAM과 DRAM을 다룬 부분이 있는데, 대략적으로만 따지고 가자.
  • SRAM은 CPU 캐시 L1, L2, L3를 구성하며, 매우 빠르고 그만큼 비싸다. 용량도 적다.
  • DRAM은 RAM을 구성하며, 상대적으로 느리지만 싸고, 용량이 크다.
    • DRAM은 데이터 유지를 위해 지속적으로 리프레시가 필요하다.

DRAM Cache Organiztion은 뭐지?

SRAM, DRAM, SSD(HDD)를 딱 올려놓고 보면, DISK 영역에 해당하는 SSD가 SLOOOOOOOW 하다.
→ 디스크 접근의 순수한 횟수를 줄여야하는 전략을 생각해야한다.

CPU와 DRAM의 속도 차이를 메우기 위한 전략을 어떻게 조직하는가를 뜻한다.
가상 메모리를 기반으로 할 때, DRAM은 일종의 "페이지 캐시"로 동작한다.

• DRAM은 전체 가상 주소 공간의 일부를 물리적으로 캐싱해두는 역할을 한다.
• 이때 "어떤 가상 페이지를 DRAM에 둘지", "어디에", "언제 쫓아낼지" 같은 전략이 필요하다.
• write-through가 아닌 write-back 방식을 채택한 것이 DRAM 캐시라고 하는데..
  • Write-through : CPU가 캐시에 쓰면, 동시에 즉시 메인 메모리에도 작성한다는 것.
    • 데이터 일관성 유지에는 용이하겠지만, 필요하지 않은 쓰기도 포함된다는 점이 단점이다.
  • Write-back : CPU가 캐시에 먼저 쓰고, 나중에 변경된 경우에만 메모리로 반영한다.
    • 데이터 일관성이 아쉽지만, 쓰기 횟수가 줄어든다는 점이 채택 될만한 요소이다.

쓰기 성능이 압도적으로 중요하고, 디스크 접근을 줄이는게 핵심인 환경에서는 write-back이 우선이다.

9.3.2 Page Tables

어떤 가상 페이지가 DRAM에 어디에 있는지를 어떻게 추적할까? DRAM에 연속적으로 배치되어있지 않으니, 이것을 추적해야한다.

적합한 도구 중 중심이 되는 것이 바로 페이지 테이블이다.

페이지 테이블 : 페이지 테이블 엔트리 (Page Table Entry | PTE)의 배열로 구성되어있다.

• 각 가상 페이지 번호 (Virtual Page Number | VPN)에 대해,
  그것이 현재 어떤 물리 페이지 번호에 매핑되어있는지를 기록한 매핑 표
• PTE의 구성요소. 이것은 구조체로써의 의미가 있으며 PTE 자체에 다른 의미는 없다.

항목	설명
Valid Bit	이 가상 페이지가 DRAM에 현재 존재합니까?
Physical Page Number | PPN	있다면, where?
Protection Bits	읽기 쓰기 실행 허용 여부. chmod 아시죠? RWX = 101 | 읽실O쓰X
Dirty Bit	페이지의 수정여부를 확인한다. write-back의 트리거가 된다.
Accessed Bit	최근에 접근되었는가? 어떤 시간 기준이 없고, 그냥 주기적으로 관찰됨

• 왜 중요한가?
  • MMU는 가상 주소에서 물리 주소로 변환한다고 했다. MMU가 이 페이지 테이블을 참조해야 한다.
  • 이를 통해 :
    • 유효한 접근인지 확인한다 (Valid Bit)
    • 어느 물리 메모리 주소로 접근해야 하는지 결정한다.
    • 보호 비트로 접근 제어
    • 페이지 교체 시 기준을 제공 할 수 있다.
• 작동 흐름
  • CPU는 어떤 가상 주소에 접근을 요청한다. MMU는 해당 가상 주소에서 가상 페이지 번호를 얻어낸다.
  • Page Table로 가서 해당 가상 페이지 번호에 해당 하는 항목을 조회한다.
  • Vaild Bit가 1이면 :
    • 해당 Physical Page Number로 물리 주소를 생성한다.
  • Valid Bit가 0이면 :
    • Page Fault가 발생하여 디스크에서 해당 파일을 찾아오며, Page Table을 갱신한다.
  • 가상 페이지 번호를 못찾는 경우가 있을까?
    • 있다. 이 경우에는 해당 가상 주소에 대해 아직 메모리에 적재된 적이 없다라는 의미를 가진다.
      • 즉, Page Table에 항목이 있음에도 Valid Bit가 0이 된다. Page Fault가 일어날 것이다.
      • 찾긴 찾지만, 유효하지 않은 상태이다.
  • Physical Page Number으로 물리 주소 생성하는 공식이 정확히 있는건가?
    • 예.
    • VA = [ VPN ,  가상 페이지 번호 | Offset, 페이지 내 오프셋]
      • 가상 주소는 이런식으로 나뉘게 된다. VA가 오른쪽 두 개로 나뉜다고 보자.
      • 그리고 페이지 테이블을 통해 VPN을 사용해서 PPN을 얻었다고 하자.
    • PA = [ PPN,   물리 페이지 번호 |  Offset, 페이지 내 오프셋]
      • Offset 값만 유지한 채로, 앞 부분만 변경시키는 구조이다.

9.3.3 Page Hits

• 이 예시 이미지에서 가상 메모리 VP 2의 내용을 읽겠다고 쳐보자.
• 이 페이지는 DRAM에 캐시되어 있다. 나중 파트에서 설명할 기술을 사용하여, 주소 변환 하드웨어는 가상 주소를 인덱스로 사용해 PTE 2를 찾아 메모리에서 읽는다.
  • Valid Bit이 0으로 설정되어 있으므로, 주소 변환 하드웨어는 VP 2가 DRAM에 캐시되어 있음을 알 수 있다.
  • 따라서 PTE 안의 물리 메모리 주소(이 주소는 PP 1에 캐시된 페이지의 시작을 가리킨다)를 사용하여, 해당 워드의 물리 주소를 구성한다.
• 다 했다!

9.3.4 Page Faults

• DRAM 캐시 미스가 난 경우를 Page Faults라고 한다. 아래 그림은 Fault 발생 이전의 예시 페이지 테이블 상태이다 :

• CPU는 VP 3의 워드를 참조하려고 하지만, DRAM에 없다!
  • 주소 변환 하드웨어는 PTE 3을 일겅보지만, Valid Bit가 0이라서 VP 3이 캐시되어 있지 않음을 확인했다.
  • Page Fault가 발생한다.
    • 이 예외는 Page Fault Exception Handler(커널의 페이지 폴트 예외 처리기)를 호출한다.
    • 커널은 대체할 희생 페이지(Victim page)를 선택한다. 이 경우, PP 3에 저장된 VP 4이다.
  • 그 다음, 커널은 VP 4가 더 이상 DRAM에 없음을 반영해야 하니 페이지 테이블 항목을 수정한다.
    • 그리고 커널은 VP 3에 해당하는 내용을 디스크에서 읽어온다. PP 3에 복사, PTE 3을 갱신한다.
      예외 처리기는 여기까지 다 하고 종료된다.
    • 처리기가 반환되면, Fault를 일으킨 명령어가 재시작되며 동일한 가상 주소가 전달된다.

• 이것은 폴트 이후 상황이 수습된 페이지 테이블 상태이다.
  • 가상 메모리는 1960년 대 초에 고안되었는데, 이는 CPU - 메모리 간 속도 격차 떄문에 SRAM 캐시 등장 이전이었다.
    • 그 결과 Virtual Memory System은 SRAM 캐시와는 다른 용어 체계를 사용한다. 그러나 개념은 유사하다.
      • 가상 메모리 용어에서 블록을 페이지라고 한다.
      • 디스크와 메모리 사이에 페이지 단위로 전송하는 행위는 swapping, paging이라고 한다.
      • 페이지가 디스크에서 DRAM으로 옮겨지는 것은 swap in / page in 이라고 한다.
      • 반대로 DRAM에서 디스크로 옮겨지는 것은 swap out / page out 이라고 한다.
    • 그리고 미스가 발생 할 때까지 기다렸다가 그 시점에 페이지를 swap in 하는 전략을 demand paging (수요 페이징) 이라고 한다. 참조되기 전에 미스를 예측하여 페이지를 미리 swap in 하려는 다른 접근도 가능하나, 현대의 모든 시스템은 수요 페이징을 사용한다.

9.3.5 Allocating Pages

새로운 메모리 페이지를 할당 할 때 일어나는 일이다. 예를 들어 malloc을 한방 조진다.
그러면 여기서는 VP 5가 할당이 되며, 이를 위해 디스크 상에 공간을 생성하고 PTE 5를 갱신하여 새로 생선된 디스크 상의 페이지를 가리키도록 설정한다.

9.3.6 Localitiy to the Rescue Again

개념을 배우는 과정에서 많은 사람들은 가상 메모리가 매우 비효율적일 것이라는 첫 인상을 받는다.
큰 miss penalty는 페이징이 프로그램 성능을 더 나쁘게 만들 것이라고 걱정하게 된다.
하지만 실제로 가상 메모리는 잘 작동하는 것이 그 주된 이유는 지역성 떄문이다.

• 지역성은 메모리 시스템에서 최근에 사용된 데이터나 근처에 있는 데이터가 다시 사용될 가능성이 높다는 성질이다.
  • 시간 지역성 (Temporal Locality) : 최근에 접근한 데이터가 곧 다시 접근 될 가능성이 높다.
    • 같은 배열을 반복문에서 여러 번 참조하는 경우가 해당된다.
  • 공간 지역성 (Spatial Locality) : 인접한 메모리 위치에 있는 데이터가 연속적으로 접근될 가능성이 높다.
    • 배열에서 다음 인덱스를 순차적으로 참조하는 경우가 해당된다.
• 역할
  • 가상 메모리 시스템은 디스크와 RAM 간의 데이터 전송에서 발생하는 성능 저하를 해결하기 위해 지역성을 활용한다.
  • 페이지 크기가 중요한 역할을 하며, 이 크기를 잘 설정하면 디스크에서 페이지를 읽어 올 때 필요한 데이터가 같이 로드되서이다.
    
    • 페이지 크기가 1MB인데 내가 1000KB짜리 데이터를 들고오면 남은 24KB를 지역성을 위한 데이터 불러올 용도로 활용 할 수 있다.
      • 그럼 페이지 크기가 처음부터 좀 더 커도 될 것  같은데요?
      • 안돼!!
    • 내부 단편화, 페이지 교체 비용 등 여러가지 이유로 그렇게 선호되는 상황이 아니다. 그래서 잘 설정해야 한다.
  • 예를 들어, 공간 지역성에 맞게 인접한 페이지들을 함께 로드해 두면, 후속 접근 시 디스크 접근을 줄일 수 있다.
• 우리는 지역성을 사실 캐시에서 처음 다루었다 : 
  • 고속 메모리 시스템들은 지역성 덕분에 성능을 크게 향상 시킬 수 있다.
  • 시간 지역성 덕분에 최근에 접근한 데이터가 캐시에 남아있으면 다시 빠르게 접근 할 수 있다.
  • 공간 지역성 덕분에 인접한 데이터가 함께 캐시되며, 그만큼 캐시 히트율이 증가하고 성능이 향상된다.

프로그램이 전체 실행 동안 참조하는 고유의 페이지 수가 물리적 메모리 크기를 초과 할 수는 있다.

• 지역성의 원칙은 어느 시점에서든 프로그램이 작은 활성 페이지 집합인 작업 집합 또는 레지던트 집합을 처리한다고 예측한다.
• 작업 집합이 메모리에 로드된 후 초기 오버헤드가 발생하면, 이후 작업 집합에 대한 참조는 hit로 처리되며 추가적인 디스크 트래픽이 발생하지 않는다. 뭔말이야?

프로그램이 적합한 시간 지역성을 가질 때 가상 메모리 시스템은 매우 이상적으로 작동한다.

• 당연하지만 모든 프로그램이 좋은 시간적 지역성을 보이는 것은 아니다.
• 작업 집합의 크기가 물리적 메모리 크기를 초과하면, 프로그램은 쓰레싱(thrashing)이라는 안좋은 일을 하게 된다.
  • 이는 페이지가 지속적으로 swap in/out을 반복하는 현상이다.
  • 가상 메모리는 대개 효율적이지만, 성능이 느려진다면, thrashing의 발생 가능성을 염두해야 한다.

9.4 VM as a Tool for Memory Management

지금까지 우리는 단일 페이지 테이블이 단일 가상 주소 공간을 물리적 주소 공간에 매핑하는 방식으로 가정했었다.

• 실제로 운영체제는 각 프로세스마다 별도의 페이지 테이블과 별도의 가상 주소 공간을 제공한다.
  • 테이블의 시작점을 모아둔 테이블은 어디서 관리하냐?
    
    • 여기서 논하는 페이지 테이블과 가상 주소 공간도 프로세스 갯수만큼 존재 하겠지만, 운영체제의 커널에서 관리된다.
     

• 여기 예시 이미지를 보자.
  • 프로세스 i의 페이지 테이블은 VP 1을 PP 2에 매핑하고, VP 2를 PP 7에 매핑한다.
  • 프로세스 j의 페이지 테이블은 VP 1을 PP 7에 매핑하고, VP 2를 PP 10에 매핑한다.
    • 여러 가상 페이지가 동일한 공유 물리적 페이지에 매핑 될 수 있음을 알고 있어야한다. VP 7!
  • 요구 페이징과 별도의 가상 주소 공간의 결합은 시스템에서 메모리가 사용되고 관리되는 방식에 깊은 영향을 미친다.
    • 특히 가상 메모리는 무궁무진한 단순화 효과를 가져다 준다 :

링크 단순화

• 문제점 : 기존 방식에서는 각 실행 파일이 물리 메모리 어디에 놓일지 알고 있어야 했다. 링커는 그에 맞춰 절대 주소를 생성해야 했다
• 가상 메모리가 존재한 이후,
  • 모든 프로세스에 동일한 메모리 이미지 레이아웃을 제공 할 수 있게 되었다.
  • 코드 세그먼트의 0x400000, 데이터 세그먼트와 스택의 적절한 위치를 배치 할 수 있게 되었다.
  • 링커는 물리적 위치를 몰라도 되는 완전 연결(executable) 파일만 만들면 된다

로딩 단순화

• 문제점 : 전통적 로더는 실행 파일을 메모리에 복사해야 하고, 이를 위해 디스크 I/O와 복잡한 버퍼 관리가 필요하다.
• 가상 메모리가 존재한 이후,
  • 로더는 단순히 가상 페이지를 할당하고 "invalid"로 표시한 뒤, 페이지 테이블에 파일 오프셋 <-> 가상 페이지 매핑만 설정한다.
  • 실제 데이터 복사는 첫 접근 시(OS가 자동으로 페이징 인) 일어나므로, 초기 로드 코드를 최소화 할 수 있다.

공유 단순화

• 문제점 : 라이브러리나 커널 코드를 프로세스마다 별도로 메모리에 올리면 메모리 낭비가 심해졌었다.
• 가상 메모리가 존재한 이후,
  • 여러 프로세스의 페이지 테이블에 동일한 물리 페이지를 매핑시킨다. (.text 세그먼트, libc 함수 등)
  • 코드만 공유하고, 각자의 데이터, 힙, 스택은 고유하기 유지하여 격리와 재사용을 동시에 실현 할 수 있게 되었다.

메모리 할당 단순화

• 문제점 : 전통적 힙 관리에서는 연속된 물리 페이지를 확보해야 하지만, 단편화가 심해지기 쉬웠다.
• 가상 메모리가 존재한 이후,
  • 프로세스가 malloc 등으로 k개의 연속된 가상 페이지를 요청한다.
  • 그러면, OS는 물리 메모리 어디서든 임의의 k개 프레임을 찾아 매핑해주면 끝!
  • 물리적 연속성은 전혀 신경쓰지 않아도 된다. 이것은 설계와 구현을 크게 단순화 시킨다.