[컴퓨터 SW] Virtual Memory

이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다.

 이 글에서는 virtual memory에 대해 알아본다.

 disk size는 memory size보다 훨씬 크고 memory size는 꽤 작기 때문에 실제로 한 번에 실행할 수 있는 process의 개수가 한정된다. 그러나 virtual memory를 통해 하나의 process에 격리된 하나의 private linear address space를 제공할 수 있게 된다. 이외에도 locality에 의해 memory를 효율적으로 사용할 수 있게 되고, memory 관리를 단순화하며, address space를 격리할 수 있는 장점이 있다.

 

Virtual Memory

Virtual Memory Concept

executable object file to memory

 Static Linking 포스팅의 Executable Object File에서 각 executable object file이 메모리에 올라가면 오른쪽 그림과 같이 text section은 0x400000부터 시작한다는 것을 배웠다. 모든 process가 이렇게 작동한다! 실제로 메모리는 하나뿐인데 어떻게 같은 주소를 사용할 수 있을까? 바로 virtual memory를 사용해서이다.

 

virtual memory를 사용하지 않는 경우

 memory는 M개의 연속된 byte size cell의 배열이며, 이 때 모든 byte는 고유의 physical address를 가진다.

 microcontroller와 같이 단순한 기계들은 위 그림과 같이 virtual memory를 사용하지 않고, CPU가 직접 memory에 접근한다. 이 방법을 physical address addressing이라 한다.

 

virtual memory를 사용하는 경우

 그러나 컴퓨터와 같이 한 번에 여러개의 process를 실행시켜야 하는 복잡한 기기인 경우 위 그림과 같이 virtual memory를 사용한다. CPU가 memory에 접근할 때 MMU에게 virtual address에 해당하는 값을 달라고 요청하면 MMU는 virtual address를 physical address로 변환하고 이 physical address로 memory에 접근한다.

MMU : Memory Management Unit. virtual address를 physical address로 변환한다.
page : disk의 최소 단위.

 

 

Address Space

 총 3가지의 address space로 구분할 수 있다.

• linear address space : {0, 1, 2, 3, ... }과 같이 음수가 아닌 정수가 연속적으로 나열된 집합.
• virtual address space : {0, 1, 2, ... , N-1}와 같이 N( = 2$^n$)개의 virtual address의 집합.
• physical address space : {0, 1, 2, ... , M-1}와 같이 M = 2$^m$개의 physical address의 집합.

 

 

Virtual Memory for Caching

 virtual memory는 disk에 저장된 N size byte array이며, 이 값들은 필요 시 main memory인 DRAM에 저장된다. 즉 memory가 disk의 cache처럼 사용되는 것이다! 이 때 disk의 byte array가 DRAM에 caching되는 최소 단위를 page라고 하며 크기 P = 2$^p$로 표현한다.

 disk에 있는 virtual address space의 page를 virtual page, memory에 있는 physical address space의 page를 physical page라고 부른다.

cache했을 때는 최소 단위가 메모리의 연산 단위인 1byte - block이었다면, 여기서는 disk의 연산 단위인 page를 사용한다.

 

memory가 disk의 cache처럼 사용된다.

 이 때 virtual page는 아래 3가지 종류가 존재한다.

• unallocated : virtual memory system에 의해 아직 할당되지 않은 page.
• cached : physical memory에 caching된 virtual page.
• uncached : physical memory에 caching되지 않은 virtual page.

 

Miss Penalty 처리 방식

 DRAM은 SRAM보다 10배 가량 느려 cache miss가 나더라도 그렇게 큰 penalty를 가지지 않는다. 그러나 disk는 memory보다 약 1만배 가량 느리기 때문에 cache가 나는 경우 매우 큰 penalty를 가진다. 이를 해결하기 위해 몇 가지 기법을 사용한다.

• page size를 크게 잡는다. 보통 4KB 또는 8KB로 잡는다.
• fully associative하게 잡아, 모든 virtual page가 모든 physical memory에 caching될 수 있다. 이렇게 하면 특정 virtual page가 physical page에 caching되어있는지 여부를 확인하기 위해 모든 physical memory를 확인해야 하기 때문에 virtual page와 physical page를 매핑하는 page table이라는 data structure를 이용하며 이를 통해 특정 virtual page가 physical page에 있는지 여부를 바로 알 수 있다.
• write-through 대신 write-back를 사용한다.
• page miss가 났을 때 disk로부터 해당 page를 가져오는 것을 기다리기보다 다른 process에게 flow control을 넘긴다.

 

Page Table

page table

 앞서 설명했듯 page table은 virtual page와 physical page를 매핑하는 자료구조이다.

 page table element는 1bit의 valid bit, 그리고 address field로 구성된다.

• valid bit가 1인 경우 해당 address는 DRAM에 caching된 physical address의 시작 주소를 값으로 가지고, DRAM에 caching되어 있음을 의미한다.
• valid bit가 0이고 address가 null이 아닌 경우 disk의 virtual page address의 시작 주소를 값으로 가진다.
• valid bit가 0이고 address가 null이라면 아무것도 아닌 상태이다.

 

Page Hit

 위 그림에서 CPU가 virtual page 2를 읽는다고 가정하자. 이 때 읽으려 하는 virtual page가 physical memory에 저장되어 있는 상태이며, 이를 page hit라고 한다.

 

Page Fault

 위 그림에서 CPU가 virtual page 3을 읽는다고 가정하자. 이 때 읽으려는 virtual page가 physical memory에 없는 상태이며 이를 page fault라고 한다.

 이 경우 page fault exception이 발생해 page fault handler가 page를 disk에서 physical memory으로 가져온다. 이 때 physical memory에 모든 page가 caching된 상태라면 교체 알고리즘에 따라 physical memory에서 없앨 victim page를 선정하고, 만약 수정된 상태라면 disk로 write-back한다.

 

page fault 발생 시 : virtual page 4가 교체됨

 위 그림의 경우 CPU가 virtual page 3을 읽는 상황에서 page fault가 발생했고, page fault handler가 virtual page 4를 victim page로 선정한 상태의 그림이다. 이후 virtual page 4를 write-back하고 virtual page 3을 disk로부터 가져온다. 물론 page table의 값도 수정된다.

 

Page Allocation

page allocation bef/aft

 page table의 valid bit가 0이고 address가 null이라면 해당 page는 아직 allocate되지 않은 상태이다. 이 때 virtual page를 disk에 할당하고 해당 page를 page table에 올린다. 이 상태에서는 아직 해당 데이터에 접근하지 않은 상태이기 때문에 physical memory에는 올라가지 않은 상태가 된다.

 

Locality

 virtual page 기술 또한 disk를 caching하는 기법이므로 locality가 높을 때 잘 돌아간다. program locality와 동일하게 process는 특정 virtual page에 계속해서 접근하는 경향이 있는데, 이 virtual page들을 working set이라고 한다.

 이 때 working set size가 main memory size보다 작다면 최초의 page fault 이후에는 모든 virtual page가 main memory에 올라가므로 작업 효율이 좋을 것이다. 그러나 working set size가 main memory size보다 크다면 page fault가 계속 일어나게 된다. 이 현상을 thrashing이라고 한다.

 

 

Virtual Memory for Memory Management

메모리 관리 측면에서 virtual memory

virtual memory는 fully associative하기 때문에 모든 virtual page가 모든 physical memory에 caching될 수 있다. 

 따라서 모든 process는 자신만의 virtual address space를 가지기 때문에 [자신만이 main memory를 사용한다]는 추상화를 가질 수 있게 된다. 그래서 모든 process는 같은 형식의 virtual address를 가진다.

 또한, 이 특성 때문에 서로 다른 virtual page가 같은 physical page에 매핑될 수도 있다. 위 예시에서 read-only library code의 경우 process 1과 2에서 모두 사용하는데, 같은 physical page에 매핑함으로써 page 하나를 아낄 수 있다.

 

 

Virtual Memory for Memory Protection

page table element에 permission bit 추가

 위 그림처럼 page table entry에 read, write, sup에 대한 비트를 추가하고 permission bit에 따라 page 접근을 아주 쉽게 막을 수 있다.

 

 

Address Translation

용어

cache 관련 bit 쪼개기

virtual memory 관련 bit

1. 크기 관련
   • N = 2$^n$ : virtual address space의 주소 개수
   • M = 2$^m$ : physical address space의 주소 개수
   • P = 2$^p$ : page size (단위는 byte)
2. Virtual Address에서
   • VPO : virtual page offset. PPO에서 사용할 값.
   • VPN : virtual page number. PTE에서 VPN에 해당하는 virtual pgae에 접근해 valid 여부를 판단한다.
   • TLBI : TLB index. cache index와 동일하게 index로 위치를 지정한다.
   • TLBT : TLB tag. cache tag와 동일하게 tag로 해당 정보가 있는지 검사한다.
3. Physical Address에서
   • PPO : physical page offset. 
   • PPN : physical page number
   • CO : cache offset
   • CI : cache index
   • CT : cache tag

 

 이렇게 주어졌을 때, 다음과 같은 방식으로 bit 개수를 정한다.

• p는 VPO과 PPO의 bit 개수. 이 때 log$_2$P = p.
• VPN bit 개수 = n - p, PPN bit 개수 = m - p.
• TLBI bit 개수는 log$_2$(TLB set 개수)
• TLBT bit 개수 = VPN bit 개수 - TLBI bit 개수
• CI bit 개수 = log$_2$(cache set 개수), CO = log$_2$(cache block 개수), CT = m - [CI bit 개수] - [CO bit 개수]

 

과정

 PTE를 기반으로 virtual address를 physical address로 변환하는 과정은 다음과 같다.

참고로 page table의 주소는 PTBR, page table base register 안에 있다.

 

PTE의 값으로 virtual address를 physical address로

• VPN을 이용해 page table의 VPN번째 entry를 살핀다.
  • PTE valid bit가 1인 경우 : page hit이므로 PTE에서 PPN을 알아오고, 여기에 VPO를 붙여 physical address를 만든다.
  • PTE valid bit가 0인 경우 : page fault이므로 exception을 발생시킨다.

 

 

TLB, Translation Lookaside Buffer

TLB

 page table은 main meory에 존재하기 때문에 miss cost가 존재한다. 이를 보완하기 위해 MMU 내부의 L1 cache에 위치한 TLB를 사용하며, TLB는 page table의 cache이다.

 동작 방식은 cache와 완전히 동일하지만 block이 없는 구조이다. 즉 offset이 없다! TLB는 오직 TLB index와 TLB tag만 존재한다. page table의 cache인 만큼 내부에는 PTE가 들어가 있다.

context switch가 발생할 경우 TLB의 모든 valid bit를 0으로 설정한다.

 

 

전체 과정

 어떤 instruction을 수행하기 위해 CPU가 memory access를 요청했을 때 TLB를 포함해서 한 번에 보자.

1. CPU가 MMU에게 virtual address를 보낸다.
2. MMU는 VPN에서 TLBT와 TLBI를 이용해 TLB를 살핀다.
   • TLB Hit인 경우 TLB로부터 PTE를 받아온다.
     • TLB hit이면서 해당 virtual page가 physical memory에 없는 경우는 없다. 이러한 경우는 TLB에 PTE가 들어온 상태에서 해당 virtual page가 victim page로 선정되는 경우밖에 없는데 page fault handler는 victim page로 선정된 page의 TLB의 valid bit를 0으로 설정하기 때문이다.
   • TLB Miss인 경우 MMU에서 PTE address를 생성하고 memory에 해당 PTE를 요청하고, 받는다.
     • PTE를 받았을 때 Page Hit인 경우 memory에서 PTE를 받는다. 동시에 TLB도 갱신한다.
     • PTE를 받았을 때 Page Fault인 경우
       • MMU가 page fault exception을 발생시킨다.
       • page fault handler가 victim page를 선정한다. 만약 dirty page라면 disk에 값을 쓴다.
       • disk에서 필요한 page를 memory로 보내고, memory는 page table을 갱신한다.
       • 다시 처음의 단계로 돌아간다. (이 경우 TLB Miss이지만 Page Hit인 경우가 된다.)
3. MMU가 PTE로부터 physical address를 추출해 이를 cache나 memory에게 보낸다.
4. cache나 memory가 받은 physical address에 있는 데이터를 CPU로 보낸다.

 

 같은 로직으로 diagram도 있다.

TLB hit인 경우

 

TLB miss && Page Hit인 경우

 

TLB miss && Page Fault

 

 

Multi Level Page Table

 4KB(2$^{12}$) page size, 각 PTE size가 8byte이고 virtual address가 48bit인 경우를 생각해 보자. 이 경우 page table의 크기는 2$^{48-12+3}$ = 2$^{39}$ = 512GB가 된다. 너무 크다!

 

구조

multi level page table

 이러한 문제를 해결하기 위해 multi level page table을 사용한다. multi level page table의 경우에는 여러 level의 page table로 표현하며 사용하지 않는 page table의 경우에는 할당하지 않는다. 위 예시의 경우 level 1의 2-7이 null, 9부터 1023까지 null인 상황이다. 단일 page table이었다면 사용하지 않는 모든 것들도 다 할당했겠지만 multi level을 사용하면 필요한 부분만 조금씩 할당할 수 있다. 실제로 level 2 page table을 보면 level 1에 할당되어있는 PTE 0, PTE 1, PTE 8에 해당하는 page table만 만들어진 것을 볼 수 있다. 이렇듯 필요없는 page table을 만들지 않기 때문에 메모리를 절약할 수 있다.

 

Multi Level Page Table Address Translation

 multi level page table에서 address translation은 VPN을 여러 개로 쪼개어 각 level의 page table을 순서대로 검사한다. 이를 page walk라고 한다.

multi level page table의 address translation

 

 

 

Memory Mapping

 virtual memory area는 disk object와 연결해서 초기화하며, 이 과정을 memory mapping이라 한다. 이 때 아래 2가지값에 의해 초기화될 수 있다.

• regular file : executable object file과 같은 실제 파일. page byte가 file의 byte와 동일하다.
• anonymous file : user stack이나 heap 등. 제일 처음의 fault는 physical page를 0으로 채운다. (demand-zero page) 한 번 값이 써지면 다른 dirty page와 동일하다.
  • 이 때 dirty page는 memory와 swap file에 잠시 저장되었다가 disk에 저장된다.
  • swap file은 virtual memory가 모두 mapping되었을 때 사용하며, user stack 또는 heap에서 page eviction이 일어났을 때 swap file에 넣어준다.

 

Shared Objects

shared objects

 library와 같이 공통적으로 쓰는 것을 포함할 때는 shared object를 사용하면 메모리 낭비를 일으키지 않는다.

 

copy-on-write before / after

 이 때 copy-on-right라는 기법을 사용할 수 있다. 왼쪽 그림에서처럼 처음에는 같은 shared object를 가리키는 상황에서 virtual memory의 값이 수정된다면 오른쪽 그림처럼 수정된 부분만 다른 memory를 가리키게 하는 방법이다.

 

 

 

 

 

 

 

잘못된 내용이나 지적, 오탈자 등은 언제나 환영합니다.