[Lecture 19] Virtual Memory: Hardware and Performance

#Physical Memory Addressing

오늘날 자동차, 엘리베이터 및 디지털 사진 프레임과 같은 장치에 내장된 마이크로 컨트롤러와 같은 "간단한" 시스템에 사용된다

#단점

• 초기 시스템들에서는 Physical Memory Addressing을 사용했다
  • 각 프로그램은 DRAM에서 전체 메모리 공간을 유지했었다
  • 한 번에 "활성"할 수 있는 프로그램의 수를 제한했다
  • 프로그램 메모리 공간의 절대 크기를 DRAM 크기로 제한했다
  • 주소 보호에 대한 자연스러운 지원이 제공되지 않았음
• 프로그램이 실행되는 모든 시간 동안
  • 그 프로그램은 instruction의 작은 부분에만 접근할 가능성이 클 것이다
  • 그 프로그램은 데이터의 작은 부분에만 액세스할 가능성이 클 것이다

#Virtual Memory / 가상 메모리

가상메모리는 주기억장치(main memory)처럼 사용할 수 있는 보조기억장치의 일부분이다. 보통 우리가 하드디스크라고 부르는 보조 기억장치에 저장되어 있는 프로그램이나 데이터가 실행(또는 처리)되려면 주기억장치로 옮겨져야 한다. (이 과정을 “적재” 또는 “로딩”이라고 부른다.)

즉, 프로그램이나 데이터를 실행할 때 보조기억장치에 있던 것을 주기억장치로 가지고 와야 하는데  주기억장치 공간에 비해 실행될 프로그램이 크거나,  동시에 실행될 프로그램이 여러 개라서 주기억장치 공간이 부족하다면 어떻게 될까?

출처: https://terms.naver.com/entry.naver?docId=3607482&cid=58598&categoryId=59316

 

실행이 제대로 되지 않는다.
 
이런 문제를 해결하기 위한 방법이 가상메모리이다. 가상메모리는 당장 실행해야 하는 부분만 주기억장치에 넣고 나머지는 보조기억장치에 넣어 동작하도록 한다.

 

예를들어 페이지 단위로 세분된 자료와 프로그램들은 컴퓨터의 운영시스템에 의해 주기억장치와 보조기억장치간에 서로 전송이 가능하기 때문에 컴퓨터 시스템은 사실상 존재하는 것보다 더 큰 기억용량을 가지고 있는 것처럼 보이게 할 수 있다. 그러므로 컴퓨터 시스템을 마치 무한정의 주기억장치를 가지고 있는 것처럼 사용할 수 있다. 그 예로서, 5백12KB의 실제 기억용량(주기억용량)을 가지고 있는 컴퓨터는 디스크상의 보조기억장치와 가상기억장치 운영시스템을 사용하여 16MB의 기억용량을 가진 것처럼 동작할 수 있다.

출처: https://terms.naver.com/entry.naver?docId=4383223&cid=59941&categoryId=59941

가상메모리를 사용하는 시스템은 여러 프로그램이 동시에 실행되는 것처럼 보여도 어느 한 순간에는 한 개의 프로그램만 실행되고, 한 프로그램내에서도 그중 일부만 실행하기 때문에 당장 필요한 부분만 주기억장치에 저장하고, 나머지는 그대로 보조기억장치에 두고 실행함으로써 실제의 메모리 용량보다 큰 프로그램이나 여러 개의 프로그램을 실행할 수 있도록 해준다.

이때, 실행할 프로그램을 일정한 크기의 작은 단위로 나눈 것을 페이지(page)라 하고 주기억장치를 동일한 크기로 나눈 것을 페이지 프레임(page frame)이라 하며, 페이지 단위로 주기억장치에 올리는 기법을 페이징(paging)이라고 한다. 운영체제에 따라 서로 다른 크기의 단위로 나눈 세그먼트(segment)를 사용하기도 한다.

만약 실행 과정에서 프로세스A의 페이지1과 페이지2, 프로세스B의 페이지3가 필요하다면, 프로세스별 페이지 테이블을 참조해 해당 페이지들만 주기억장치에 적재된다. 이후 다른 페이지들이 실행을 위해 필요하게 되면 이미 수행을 마친 페이지들의 자리로 적재(loading)하여 나머지 부분을 실행하게 된다.

#Virtual Memory Details

• 기본 메모리를 보조(디스크) 스토리지의 "캐시"로 사용
  • CPU 하드웨어와 운영 체제(OS)가 공동으로 관리
• 프로그램들이 메인 메모리 (DRAM)를 공유함
  • 각각 코드와 데이터가 들어 있는 개인 가상 주소 공간을 확보
  • DRAM은 자주 사용되는 코드와 데이터를 보유한다
  • 다른 프로그램으로부터 보호됨
• CPU 및 OS가 가상 주소를 물리적 주소로 변환
  • VM "블록"을 페이지라고 부름
  • VM 변환 "miss"를 페이지 부재(page fault)라고 한다

가상 메모리는 현대 모든 최신 서버, 노트북 및 스마트폰에 사용되며, 컴퓨터 과학의 위대한 아이디어 중 하나로도 꼽힌다

 

참고로 우리가 흔히 사용하는 gdb에서도 virtual memory를 볼수있다. gdb를 사용하면 물리적 주소가 아닌 가상 주소가 표시된다)

#Process Virtual Memory Image

• OS는 다음을 유지한다:
  • 각 프로세스의 주소 공간의 구조
  • 어느 주소가 유효한 주소인지
  • 무엇을 참조하는지
  • 심지어 현재 주 메모리에 없는 것들도 유지한다

• 보조 기억 장치에 "가상" 공간이 있음
• 가상 공간은 고정 크기의 "페이지"로 구분된다
• 가상 페이지를 필요에 따라 DRAM에 복사한다

#Paging to/from Disk

프로세스에 의해 실제로 액세스되는 실제 메모리에 있는 데이터만 보유한다

 

각 프로세스마다 다음과 같은 map유지: { virtual addresses } → { physical addresses } ∪ { disk addresses }

 

OS가 매핑을 관리하고, 물리적(할당된 경우)에 매핑할 가상 주소 및 Disk를 결정한다

 

• 디스크 주소에는 다음이 포함된다
  • 실행 파일 .text, 초기화 데이터
  • 스왑 공간 / Swap space(일반적으로 지연 할당됨 / lazily allocated)
  • Memory-mapped (mmap'd) 파일
• Demand paging: 처음 액세스할 때 디스크에서 데이터를 지연 가져오기
  • 응용 프로그램에 대해 알 수 없음

#VM as a Tool for Caching

개념적으로 가상 메모리는 디스크에 저장된 N개의 연속 바이트 배열이다. 디스크의 어레이 내용이 물리적 메모리(DRAM 캐시)에 캐시된다. 이러한 캐시 블록을 페이지(page)라고 한다 (크기는 P = 2^p 바이트).

#DRAM Cache Organization

• DRAM 캐쉬 organization에는 막대한 miss penalty가 있다
  • DRAM은 SRAM보다 약 10배 느리다
  • Disk는 DRAM보다 약 10,000배 느림
• 결과들
  • 큰 페이지(블록) 크기: 일반적으로 4KB, 때로는 4MB
  • Fully associative
    • 모든 VP는 모든 PP에 배치할 수 있다
    • 캐시 메모리와는 다른 "대형" 매핑 함수 필요
  • 매우 정교하고 비용이 많이 드는 교체 알고리즘
    • 하드웨어에 구현하기엔 너무 복잡하고 개방적임
  • write-through가 아닌 write-back

#Page Table Enables Address Mapping

Page table: 가상 페이지를 실제 페이지에 매핑하는 PTE(page table entries) 배열

 

DRAM의 프로세스별 커널 데이터 구조:

#Page Hit

page hit: 물리적 메모리에 있는 VM word reference (DRAM 캐시 hit)

#Page Fault / 페이지 부재

Page Fault: 물리적 메모리에 없는 VM 워드에 대한 reference (DRAM 캐시 miss)

#Handling Page Fault

Page miss으로 인해 page fault 발생 (exception)

Page fault handler가 제거할 대상을 선택한다(여기서는 VP 4)

miss된 VM 페이지(여기서는 VP 3)가 디스크에서 PM(여기서 PP 3)으로 복사됨.

그 다음 페이지 테이블이 업데이트됨

위반 명령이 다시 시작된다: page hit

페이지를 DRAM에 복사하지 못할 때까지 기다리는 것을 demand paging이라고 한다

#Allocating Pages

가상 메모리의 새 페이지(VP 5) 할당:

#Locality

• 가상 메모리는 매우 비효율적인 것처럼 보이지만 구역성 때문에 작동한다
• 어느 시점에나 프로그램은 working set이라고 하는 활성 가상 페이지(active virtual pages) 집합에 액세스하는 경향이 있다
  • 잠정 구역성이 더 나은 프로그램은 더 작은 작업 세트(working set)를 가질 것이다
• if (작업 세트 크기 < 메인메모리 크기)
  • compulsory misse 후 한개의 process에서 우수한 성능 제공
• If ( SUM(작업 세트 크기) > 메인메모리 크기)
  • 쓰래싱(Thrashing): 페이지를 연속적으로 교환(복사)하는 성능 저하

#VM Address Translation

• Virtual Address Space (가상 주소 공간)
  • V = {0, 1, …, N–1}
• Physical Address Space (물리적 주소 공간) / 실장되어 있는 메모리 내의 위치를 지정하기 위해 이용되는 어드레스의 집합
  • P = {0, 1, …, M–1}
• Address Translation
  • MAP: V → P U {∅}
• 가상 주소 a의 경우
  • 가상 주소 a의 데이터가 P의 물리적 주소 a'에 있는 경우 MAP(a) = a'
  • 가상 주소 a의 데이터가 물리적 메모리에 없는 경우 MAP(a) = ∅
    • 유효하지 않거나 디스크에 저장됨

#Summary of Address Translation Symbols

• 기본 매개 변수
  • N = 2^n: 가상 주소 공간의 주소 수
  • M = 2^m: 물리적 주소 공간의 주소 수
  • P = 2^p: 페이지 크기 (바이트)
• 가상 주소(Virtual Address / VA)의 구성 요소
  • TLBI: TLB index
  • TLBT: TLB tag
  • VPO: Virtual page offset
  • VPN: Virtual page number
• 물리적 주소(Physical Address / PA)의 구성 요소
  • PPO: Physical page offset (same as VPO)
  • PPN: Physical page number

#Address Translation With a Page Table

#Address Translation: Page Hit

1: 프로세서가 가상 주소를 MMU(Memory management unit)로 보냄

2-3:  MMU가 메모리의 페이지 테이블에서 PTE(page table entry)를 가져옴(fetch).

4: MMU가 물리적 주소를 캐시/메모리로 전송

5: 캐시/메모리가 프로세서로 데이터 워드 전송

*PTEA = PTE Adress (page table entry address)

#Address Translation: Page Fault

1: 프로세서가 가상 주소를 MMU로 보냄

2-3: MMU가 메모리의 페이지 테이블에서 PTE를 가져옴 (fetch)

4: 유효한 비트가 0이므로 MMU는 페이지 부재 예외를 트리거함

5: 핸들러가 대상(victim)을 식별 (dirty인 경우 디스크로 page out)

6: 핸들러가 새로운 페이지를 page in하고 메모리의 PTE 업데이트

7: 핸들러가 원래 프로세스로 돌아가 fault instruction을 다시 시작

#Integrating VM and Cache

*VA: virtual address, PA: physical address, PTE: page table entry, PTEA = PTE address

#Speeding up Translation with a TLB

• 페이지 테이블 항목(PTE)이 다른 메모리 단어처럼 L1에 캐시되는 경우
  • PTE는 다른 데이터 reference에 의해 제거될 수 있다
  • PTE 적중에는 여전히 약간의 L1 지연이 필요하다
• 해결책: Translation Lookaside Buffer (TLB)
  • MMU의 작은 set-associative 하드웨어 캐시
  • 가상 페이지 번호를 실제 페이지 번호와 매핑
  • 적은 수의 페이지에 대한 전체 페이지 테이블 엔트리 포함

#Accessing the TLB

MMU는 가상 주소의 VPN (Virtual page number) 부분을 사용하여 TLB에 액세스한다

#TLB Hit

TLB 적중 시 캐시/메모리 액세스 제거

#TLB Miss

TLB miss로 인해 추가적인 캐시/메모리 액세스(PTE를 얻기 위해)가 발생함. 다행히도, TLB miss는 드물다 (왜 그럴까?).

#VM as a Tool for Memory Protection

권한 비트로 PTE 확장
MMU는 각 액세스에서 이러한 비트를 확인한다

#Examples of 2-Level TLB Organization

#Summary

• 가상 메모리에 대한 프로그래머의 관점
  • 각 프로세스에는 고유한 개인 선형 주소 공간이 있다
  • 다른 프로세스에 의해 손상될 수 없음
• 가상 메모리에 대한 시스템의 관점
  • 가상 메모리 페이지를 캐싱하여 메모리를 효율적으로 사용한다
    • 지역성 때문에만 효율적이다
  • 메모리 관리 및 프로그래밍 간소화
  • 권한을 확인할 수 있는 편리한 배치 지점을 제공하여 보호 단순