CSAPP(9) - Virtual Memory

메모리를 여러 프로세스가 공유하면 CPU사용량이 늘어나고 에러를 발생시킬 수 있다. 메모리를 효율적으로 사용하고 에러를 줄이기 위해 현대 시스템은 virtual memory라는 가상 메모리 추상화를 제공한다. 가상 메모리는 커널 소프트웨어가 각 프로세스에게 제공하는 크고, 균일하고, 개인적인 주소 공간이다.

가상 메모리의 능력

• 메모리를 디스크에 저장된 주소 공간의 캐시처럼 사용.
  • 활성화된 영역만 메모리에 올린다.
• 메모리 관리의 단순화
  • 각 프로세스에 균일한 주소 공간을 제공
• 각 프로세스의 주소 공간이 충돌하지 않도록 보호

1. Physical and Virtual Addressing

CPU가 물리 주소를 사용하여 메모리의 접근하는 방식을 물리 어드레싱이라 한다.

현대 프로세스는 가상 어드레싱을 사용한다.

• 주소 변환 : 가상 주소를 물리 주소로 바꾸는 것
  • Memory Management Unit(MMU)는 CPU칩 내에 있으며, OS에 의해 관리되는 룩업 테이블(메모리에 존재)를 사용해서 변환

2. Address Spaces

각 데이터 개체는 여러 독립적인 주소를 가진다.

• 메모리의 각 바이트는 가상 주소 공간의 가상 주소와 물리 주소 공간의 물리 주소를 가진다.

3. VM as a Tool for Caching

개념적으로, 가상 메모리는 디스크에 있는 N개의 연속된 바이트 크기 셀의 배열로 구성된다.

• 각 바이트는 고유한 가상 주소를 갖고, 이게 배열의 인덱스다.
• 디스크 내 배열의 내용은 메모리에 캐시된다
  • 디스크의 데이터는 블락이라는 단위로 쪼개져 메모리로 전송된다. VM 시스템은 가상 메모리를 virtual page라는 고정 크기 블락으로 쪼갠다. 물리 메모리 또한 physical page로 쪼갠다.

가상 페이지 집합은 세개로 나뉜다.

• Unallocated : VM에 의해 할당되지 않은 페이지. 데이터도 없고, 디스크 공간을 점유하지 않음
• Cached : 물리 메모리에 캐시된 페이지.
• Uncached : 물리 메모리에 캐시되지 않은 패이지.

3.1. DRAM Cache Organization

DRAM 캐시란 VM 시스템의 가상 페이지를 말한다.

• DRAM 캐시 미스는 SRAM 미스에 비해 비용이 크다(속도가 느리다)
• 페널티가 크기 때문에 가상 페이지는 크다. (4KB~2MB) 또한 같은 이유로 write-through 대신 write-back을 사용한다.(쓰기 연산을 미룬다.)

3.2. Page Tables

다른 캐시와 마찬가지로 물리 메모리에서 victim page를 선택하고, 디스크에서 DRAM으로 가상 페이지를 복제하는 등의 작업이 필요하다. 이러한 기능은 OS 소프트웨어와 MMU(메모리 관리 유닛) 내 주소 변환 하드웨어, 페이지 테이블이라 하는 물리 메모리에 저장된 자료구조의 조합으로 구성된다.

• 주소 변환 하드웨어는 페이지 테이블을 읽어서 가상 주소를 물리 주소로 변환한다.
• os는 페이지 테이블을 관리하고 페이지를 disk과 DRAM사이에 전달한다.

• 유효 비트가 설정되면, 주소 필드는 물리 페이지 시작 주소를 가르킨다.
• 유효 비트가 설정되지 않고
  • null 주소이면, 가상 페이지가 할당되지 않았다.
  • 이외의 경우, 주소는 디스크의 가상 페이지 시작 주소를 가르킨다.

3.4. Page Faults

1. 주소 변환 하드웨어는 메모리에서 페이지 테이블을 조회
2. 유효 비트를 통해 캐시되지 않음을 확인
3. 페이지 폴트 예외를 발생
4. 커널의 페이지 폴트 핸들러를 호출
   1. 핸들러는 희생 페이지를 선택
   2. 희생 페이지가 수정되었다면 disk에 복사(write-back)
   3. 페이지 테이블 업데이트
   4. 디스크의 가상 페이지를 물리 페이지로 복사
   5. 페이지 테이블 업데이트
5. 폴트 명령을 재수행
   1. 캐시됨을 확인
   2. 페이지 히트. 주소 변환 하드웨어의 정상 수행

3.6. Locality to the Rescue Again

지역성 덕분에 가상 메모리는 꽤 잘 동작한다.

활성 페이지가 물리 메모리의 크기를 초과하면 thrashing 현상이 발생한다.

• 페이지가 연속해서 swap-in/out

4. VM as a Tool for Memory Management

가상 메모리는 메모리 관리와 보호를 쉽게 만든다.

• 요구 페이징과 분리된 가상 주소 공간의 조합을 이용해
• 링킹, 로딩, 코드와 데이터 공유, 애플리케이션 메모리 할당을 쉽게 한다.

os는 각 프로세스에 분리된 페이지 테이블을 제공하여 분리된 가상 주소 공간을 제공한다.

• 동일한 물리 페이지를 공유한다.

• 단순한 링킹 : 분리된 주소 공간은 각 프로세스가 동일한 메모리 이미지 형태를 갖게 한다. 이는 링커가 물리 메모리의 코드와 데이터 위치와 독립적인 완전 링크된 실행파일을 쉽게 만들 수 있게 한다.
• 단순한 로딩 : 목적 파일 내 .text와 .data 영역을 로드하기 위해, 리눅스 로더는 가상 페이지를 할당하고 not cached로 표시한다. 또한 페이지 테이블 엔트리를 목적 파일을 가리키도록 한다. 로더는 절대 디스크의 데이터를 메모리로 복사하지 않는다. vm에 의해서만 자동으로 요구시에 복사된다.
  • 이러한 연속된 가상 페이지 집합을 임의의 파일 위치에 매핑하는 것을 memory mapping이라 한다.
  • 각 응용 프로그램이 고유의 메모리 맵을 가진다.
• 단순한 공유 : OS는 여러 프로세스가 하나의 코드 복제본을 공유하도록 한다. (커널, 표준 C 라이브러리 등)
• 단순한 메모리 할당 : 동적 메모리 할당을 할 때, os가 인접한 물리 페이지를 찾을 필요가 없다. 페이지는 물리 메모리에 흩어져 있다.

5. VM as a Tool for Memory Protection

유저 프로세스에게 허용되지 않아야 할 것들

• 읽기 전용 코드 영역 수정
• 커널의 코드나 자료구조를 읽거나 수정
• 다른 프로세스의 메모리를 읽거나 수정
• 다른 프로세스와 공유하는 가상 페이지를 수정
  • 모든 프로세스가 허용하지 않는 경우

페이지 테이블에 허용 비트를 추가해 구현

• SUP : 커널 모드에만 접근 허용
• 특정 명령이 허용을 위반하면 CPU는 보호 폴트를 발생시킨다. 커널의 예외 핸들러는 제어를 넘겨받아서 프로세스에게 SIGSEGV 시그널을 보낸다. (segmentation fault)

6. Address Translation

페이지 히트 시 CPU 하드웨어의 수행 단계

1. 프로세스는 가상 주소를 생성해 MMU에 보낸다.
2. MMU는 PTE(page table entry) 주소를 생성하고 캐시/메인 메모리에 요청한다.
3. 캐시/메모리는 PTE 주소를 MMU에 반환
4. MMU는 물리 주소를 구성하고 캐시/메모리에 요청한다.
5. 캐시/메모리는 요청 데이터 워드를 프로세서에 반환한다.

페이지 폴트 시에는 하드웨어와 OS커널의 협력이 필요하다.

1. 위의 1~3과 동일
2. PTE의 유효 비트가 0이면 MMU는 CPU로부터 커널의 페이지 폴트 예외 핸들러로 제어를 전달하는 예외를 발생시킨다.
3. 폴트 핸들러는 물리 메모리 내 희생 페이지를 식별하고, 그 페이지가 이전에 수정되었다면 디스크에 쓴다.
4. 폴트 핸들러는 새 페이지를 메모리로 가져온 뒤, 메모리의 PTE를 갱신한다.
5. 기존 프로세스에 제어를 반환한다. CPU는 가상 주소를 MMU에 재전송하고 페이지 히트 과정을 거친다

많은 시스템에서 가상 메모리와 SRAM 캐시를 같이 사용하는데, 대부분은 물리 주소를 캐시한다.

TLB로 주소 변환 속도 증가

• TLB(transition lookaside buffer)란 MMU내에 있는 페이지 테이블의 캐시
• 작은 가상 주소의 캐시

멀티 레벨 페이지 테이블

페이지 테이블은 꽤 크고 메모리에 전체가 상주하는 것은 비효율적이다. 멀티 레벨 페이지 테이블은 이 문제를 해결한다.

다단계 페이지 테이블 구조는 다음 방법으로 메모리 사용량을 줄인다.

1. 레벨 1 테이블에 PTE가 null이면 다음 단계의 테이블은 존재할 필요가 없다.
2. 레벨 1 테이블만 메모리에 상주하고 다음 단계의 테이블은 스왑 아웃할 수 있다. 자주 사용되는 테이블만 메모리에 캐시할 수 있다.

멀티 레벨 구조가 느릴 것 같지만, TLB가 다른 레벨의 PTE를 캐시하는 것을 통해 단일 레벨 페이지 테이블과 유사한 속도를 보인다.

7. The Intel Core i7 / Linux Memory System

필요할 때 자세히 보기

8. Memory Mapping

리눅는 가상 메모리 영역을 디스크의 object와 연관시켜 초기화한다. 이를 메모리 매핑이라 한다. 가상 메모리 영역은 2가지 종류의 객체로 매핑된다.

• 리눅스 파일 시스템의 Regular file
  • 일반 디스크 파일의 연속적인 영역으로 매핑.
  • 파일 영역은 페이지 크기로 나눠진다.
    • 각 조각은 가상 페이지의 초기 내용으로 이루어짐.
  • 요구 페이징이기에 이 가상 페이지들은 물리 메모리에 올라가지 않는다.
  • 가상 메모리 영역이 파일 영역보다 크면 0으로 패딩된다.
• 익명 파일
  • 커널에 의해 생성된 파일
  • 0으로 채워져 있음
  • CPU가 최초로 가상 페이지에 접근하면
    • 커널은 희생 페이지를 찾고, 스왑 아웃한다.
    • 페이지를 0으로 채우고, 페이지 테이블을 갱신
  • 메모리와 디스크 간 실제 데이터는 전송되지 않음
  • demand-zero pages 라고 불림

둘 다 가상 페이지가 초기화되면, 스왑 파일(스왑 영역)을 통해 스와핑된다. 스왑 공간은 실행중인 프로세스에 할당할 수 있는 가상 페이지의 총량을 제한한다.

8.1. Shared Objects Revisited

메모리 매핑 아이디어는 가상 메모리 시스템이 전통적인 파일 시스템과 통합될 수 있지 않을까 하는 생각에서 나왔다.

프로세스 추상화는 각 프로세스가 고유의 가상 주소를 가지도록 한다. 그러나 많은 프로세스가 동일한 읽기 전용 코드 영역을 사용하기에, 중복이 발생하여 메모리가 낭비된다.

메모리 매핑은 여러 프로세스의 객체 공유를 쉽게 만든다. 객체는 공유 객체 혹은 개인 객체로 가상 메모리에 매핑된다.

• 공유 객체에 특정 프로세스가 write하면 다른 프로세스도 보이고 디스크의 원본 객체에도 반영된다.
  • 공유 객체가 매핑된 가상 메모리 영역을 공유 영역이라 한다.
• 개인 객체에 대한 변경은 다른 프로세스가 모른다. 디스크의 객체에도 반영되지 않는다.
  • 매핑된 가상 메모리 영역은 개인 영역이라 한다.

각 객체는 고유 파일명이 있으니 커널은 빠르게 동일 물리 페이지로 연관시킬 수 있다. 핵심은 공유 객체의 단일 복제본만 물리 메모리에 적재할 수 있다는 것.

개인 객체는 copy-on-write 로 가상 메모리에 매핑된다.

• 최초에는 단일 복제본만 물리 메모리에 올린다
• 프로세스가 쓰기를 시도하면 보호 폴트가 발생한다. 물리 메모리에 페이지의 새 복제본을 만들고 페이지 테이블을 갱신한다. 이후 폴트 핸들러가 반환되고 CPU는 쓰기를 재시도한다.
• 개인 객체의 페이지 복제를 가능한 마지막까지 미룸으로써 물리 메모리의 낭비를 막는다.

fork

• 새 프로세스는 기존 프로세스와 동일한 자료구조(페이지 테이블 등)을 읽기 전용으로 유지하며, copy-on-write한다.

execve 를 통해 로딩하고 실행하는 과정

• 기존 프로세스의 유저 영역을 제거
• 개인 영역 매핑. copy-on-write
  • 유저 스택, 런타임 힙, bss 영역은 0으로 채워진 개인 영역(익명 파일 매핑)
  • 코드, 데이터 영역은 실행 가능 파일에 매핑
• 공유 영역 매핑
  • 실행 가능 파일이 공유 객체와 링크되어 있다면 동적으로 링크되고, 유저의 가상 주소 공간으로 매핑된다.
• 프로그램 카운터 설정
  • 코드 영역의 진입점으로 PC를 설정

mmap 유저 레벨 메모리 매핑

mmap 함수는 가상 메모리의 새 영역을 만들어서 객체와 매핑한다.

• 커널에 새 가상 메모리 영역을 요청하고, 파일 디스크립터로 명시된 객체를 신규 영역에 매핑한다.
• 파일 입출력, 요구 페이징, IPC, 동적 메모리 할당 등을 구현할 때 쓰인다.

9. Dynamic Memory Allocation

저수준 mmdp을 통해서 가상 메모리 영역을 생성 및 삭제하는게 가능하지만, 동적 메모리 할당자를 사용하는게 더 편리하고 이식성있는 방법이다.

할당자는 가변 크기 블럭의 집합으로 힙을 유지한다.

• 각 블럭은 가상 메모리의 연속된 덩어리로, allocated 거나 free 상태다.
• 할당자는 두 유형이 있는데, 할당된 블럭을 해제하는 책임에 따라 구분된다.
  • 명시적 할당자는 할당된 블럭을 명시적으로 해제해야 한다. C 표준라이브러의 malloc 패키지.
  • 암시적 할당자는 프로그램이 할당된 블럭을 더 이상 쓰지 않는지 감지한다. 가비지 컬렉터

왜 동적 메모리 할당하는가?

• 프로그램이 실행되기 전에 자료구조의 크기를 모를 수 있기 때문이다.

할당자의 책임과 목적

• 임의의 요청 시퀀스를 처리
• 요청에 즉시 응답
  • 요청을 재정렬하거나 버퍼링해서는 안됨
• 힙만 사용
• 블럭 정렬
• 할당된 블럭을 수정하지 않기
  • 할당된 블럭에 압축 등의 조작은 할 수 없다. 해제된 블락만 조작 가능

단편화

• 나쁜 힙 효율성의 주 원인
• 내부 단편화
  • 할당된 블럭이 요청보다 크면 발생
• 외부 단편화
  • 어떠한 블락도 요청보다 크지 않을 때 발생
• 외부 단편화가 정량화 및 예측이 어렵기 때문에, 할당자는 많은 수의 적은 블럭보다 적은 수의 큰 블락을 유지하려고 한다.

10. Garbage Collection

명시적 할당자의 경우 애플리케이션이 힙 블록을 할당하고 해제하는 책임을 가진다. 이는 많은 에러를 발생시킨다.

가비지 컬렉터는 자동으로 가비지 힙 블록을 해제한다. 주기적으로 가비지 블록을 식별하여 free를 호출한다.

10.1. Garbage Collector Basics

gc는 메모리를 그래프로 본다.

• root 노드 : 힙 블락에 대한 포인터를 가진 레지스터, 스택내 변수, 전역 변수와 연관됨.
• heap 노드 : 할당된 힙 블락과 연관됨.
• 루트 노드로부터 닿을 수 없는 노드를 가비지로 본다.

gc는 요구 발생 시 또는 애플리케이션과 별도 스레드에서 실행된다.

• malloc이 적합한 유휴 블럭을 찾지 못하면 gc를 호출한다. 이후에도 찾지 못하면 os에 추가 메모리를 요청한다. 추가 메모리가 없다면 NULL 포인터를 반환한다.

10.2. Mark & Sweep Garbage Collectors

• 마크 단계 : 루트 노드와 연결된 노드를 마크한다.
• 스윕 단계 : 마크되지 않은 블록을 해제한다.

11. Common Memory-Related Bugs in C programs

• 잘못된 포인터 역참조
  • 세그멘테이션 예외 : 매핑되지 않은 메모리 영역을 역참조 시 발생
  • 보호 예외 : 읽기 전용 메모리 영역에 쓰려고 할 때 발생
• 초기화되지 않은 메모리 읽기
  • 동적 메모리 할당을 받아도 해당하는 힙 메모리는 0으로 초기화되지 않는다. 0임을 가정하고 코드 작성시 에러 발생
• 스택 버퍼 오버플로
  • 스택에 생성한 버퍼 크기 이상의 데이터를 쓸 때 발생
• 포인터와 포인터가 가리키는 객체가 같은 크기임을 가정했을 때 에러 발생
• 댕글링 포인터
  • 할당 해제한 힙 블록의 데이터를 참조
• 메모리 누수
  • 사용 완료한 힙 블록을 해제하지 않아 메모리 누수
• 등등.

12. Summary

• 가상 메모리는 물리 메모리의 추상화
• 프로세서는 가상 어드레싱이라는 방식으로 가상 메모리가 물리 메모리를 참조할 수 있게 한다.
  • 프로세스는 가상 주소를 물리 주소로 변환하여 메모리에 접근한다.
  • os의 페이지 테이블과, 하드웨어의 협력으로 변환이 가능하다.
• 가상 메모리의 주기능
  • 자동으로 디스크의 가상 주소 공간을 메인 메모리로 캐싱
    • 디스크에 있는 페이지의 참조는 페이지 폴트를 발생시킴
  • 메모리 관리를 단순화
    • 링킹, 프로세서 간 데이터 공유, 프로세스 메모리 할당, 프로그램 로딩을 단순화
  • 메모리 보호를 단순화
    • 페이지 테이블의 보호 비트를 이용
• TLB 는 하드웨어 내에 존재하는 페이지 테이블의 캐시
• 메모리 매핑
  • 가상 메모리를 디스크의 파일과 연관시킨다.
  • 데이터 공유, 프로세스 생성, 프로그램 로딩에 효과적
  • mmap을 통해 가상 주소 공간을 생성하고 제거한다.
  • malloc을 통해 힙에 동적 메모리 할당한다.
  • 명시적 할당자는 메모리 블록을 직접 관리하고, 암시적 할당자는 자동으로 관리한다.(가비지 컬렉터)