Virtual memory

 

Address translation: EA (effective address) → PA (physical address)

Virtual memory가 있으면 어떤 점이 좋은가?

• Naming and Protection
• Demand Paging

Base and Bound Registers

process가 메모리에 접근할 때는 base(시작), bound(끝)를 기준으로 한다

user process는 EA (effective address) 기준으로, 0부터 메모리 사이즈까지 배정시킨다.

Address translation

• PA: physical address, EA: effective address
• PA = EA+base, check if PA<bound
• Base, bound는 user process (x) privileged mode(o)에서 수정해야 함

그러나 Base & Bound의 단점들이 존재하는데….

Fragmentation

• External fragmentation: free memory가 서로 안 붙어있을 때 (non-contiguous)
• Internal fragmentation:

Sharing

서로 다른 memory space가 일부 memory만 쉐어하는 게 어려움

그래서 나온 것이 segmented ~

Segmented address translation

• 각 process마다 Code segment, Data segment, Stack segment… 이런 식으로 별도의 segment 이 존재한다.
• Segment table에 base&bound pair가 여러 개 있으며, 메모리를 일부분씩 사용한다.
• EA (effective address)의 구성은 다음과 같다

Translation 메커니즘

• Segment translation table이 존재해서, physical address로 매핑해준다.
• translation table은 privileged structure여야 한다

• how to change the mapping when swapping processes?:

Protection bit

• Segment table에 base, bound 이외에도 extra bit들을 추가하기도 함. (Readable? Writeable? Executable? Cachable?)

Paged Address space

• EA space (virtual memory)를 page라는 block으로 나눈다. 쉽게 말해, page: virtual memory block (fixed size)인 것.
• 이 page가 (physical memory에 있는) frame으로 매핑된다. page frame: page에 해당하는 physical memory
• Page table이 EPN을 PPN으로 translate한다

Demand paging

Virtual memory를 처리하는 방법 중 하나로, 말 그대로 page를 필요할 때만 DRAM에서 직접 불러오고 필요없는 페이지들은 하드디스크에 저장

• main memory+disk를 자동으로 manage되는 hierarchical memory system으로 사용한다.
• disk (swap space)를 memory page에 대한 백업 용도로 사용하고 program이 DRAM에 없는 페이지에 접근할 경우 page fault로 OS가 DRAM에서 page를 불러온다.
• miss penalty가 큰 대신에 (dram에서 직접 불러와야 하기 때문에) miss rate가 적음 (page 자체가 크기 때문에)

Page table

• VPN (virtual page number) → PPN (physical page number)로 매핑해주는 일종의 디렉토리
• PTE(page table entry)들의 array

page table은 present bit=1 이면 page frame으로 매핑 되어 있고 (virtual memory address에 해당하는 physical memory가 있다는 뜻) present bit=0 이면 disk로 매핑되어 있다.

Page hit (Present bit = 1)

• PPN + offset → physical address

Page fault

• VM에 있는 word에 접근했는데, 그게 physical memory에 없을 때
• Page fault는 OS의 page fault handler에서 해결함 (cache miss와는 다르게)
• DRAM에서 비어 있는 page frame이 없으면 eviction이 일어나게 된다.

1. Page replacement: evict할 virtual page (예시에서는 vp 4)가 변경되었으면 (dirty이면) disk에 다시 write를 하고, 원래 physical address가 있던 자리에 disk address를 써준다.
2. Load requested page: 아까 비웠던 page frame에 새로운 virtual address를 불러와서, PPN

이 과정 자체를 demand paging이라고 함.

Page size (2021 기출)

• Page size가 크면,

Paged memory

Physical memory (DRAM)을 page 단위로 나눈다.

disk access: page 전체를 memory로 load한다.

• memory translation: VPN (virtual page number)를 physical page number (PPN)로 바꿔주는 것
• 이는 page table을 기준으로 한다. PTE (page table entry)에 써있는 걸 보고 virtual address를 physical address로 바꿔준다.
• Page table은 memory에 있다.
• page가 memory에 있다 → corresponding physical page number가 있다.

• page가 memory에 없다 → page fault가 되며, OS가 disk에서 page를 읽어오도록 한다.

연습문제?

“machine”→ virtual address에 해당

RAM → main memory의 용량이므로 physical address에 해당

page offset = 16 * 2^10 = 2^14 → 14 bits

VPN: virtual address에 해당. 32 - 14 = 18 bits

DRAM = 2^33 bytes. 33 - 14 → 19 bits

Page table에는 VPN 하나당 1개의 entry가 존재한다. (그러나 VPN의 모든 숫자가 PPN과 매칭되진 않을 수도 있음) each entry is 4B → 2^18 * 4 = 2^22 = 4MB

또한, 각 process당 1개의 page table이 존재한다.

연습문제

4KB page = 2^12 bytes → page offset: 12 bits

VPN: 32-12 = 20 bits

16GB DRAM = 2^34 bytes → 34 bits of physical address

PPN: 34-12 = 22 bits

Virtual page size = physical page size = 4KB

# of page table entries = # of virtual page numbers

Virtual memory system의 장점?

• 각자마다 private address space가 있기 때문에, 프로세스 간에 memory를 isolate할 수 있다.
• Demand paging을 통해서, DRAM의 용량보다 큰 program도 돌릴 수 있게 된다.

Page table의 status bits

• Access type
• write protection bit: 위에 말한 protection의 차원에서 write를 해야 하는 경우에 대해서만 write하도록 한다.

page table 사이즈를 줄이는 방법

그 동안은 virtual address마다 전부 PTE가 있었음. 그러면 page table이 너무 많은 공간을 차지하게 된다는 문제점이 있음!

Hierarchical (multi-level) page table:

• "tree structure” = 각 레벨의 PTE가 하위 레벨의 PTE entry를 가리키는 포인터 같은 역할을 하는 것.
• sparse address space에 대해서 효율적이다. (L1 entry를 그냥 null로 보내버리면 되기 때문에)
• Locality가 클수록 fragmentation이 덜 되어서 공간 활용이 더 효율적이다. (쉽게 말해 L1의 포인터가 모두 L2에 있는 걸 가리키고 있어야 좋다)

Hashed (inverted) page table

(Process ID, VPN) → PPN으로 매핑

hashing을 이용해서 VPN ⊕ PID를 정해진 사이즈로 hashing 한다.

page miss의 경우 hash collision chain을 찾는 거 빼면 똑같다

⇒ address space가 매우 크고 virtual memory가 sparse할 때 활용하면 좋다

TLB (Translation Lookaside Buffer)

= 쉽게 말하면, cache of most recently used translations

given a VPN → return PTE

TLB entry:

주어진 VPN에 대해서 PTE를 return한다

tag: PID (process ID) + part of virtual address

Access process

ex. 0x00403FFC 라는 주소를 access 하고 싶다고 하자.

Page size: 4KB

VPN: 0x00403 / Page offset: 0xFFC

1. TLB에서 0x00403을 찾아보자 → 있으면 거기에 해당하는 PPN + page offset 해서 그대로 불러오면 된다
2. 엥 없네 → page table walk!

TLB를 HW or SW, 어디서 관리하는가?

• Hardware: RISC-V, x86, ARM, etc.
• Software: MIPS, etc.

VM과 cache의 관계

• Cache는 physical address를 필요로 하는데 CPU는 virtual address로 시작한다.
• VIPT cache (Virtually-indexed, physically-tagged) cache를 사용한다.\

Virtual cache의 문제점?

1. Homonyms (동음이의어): 서로 다른 2개의 process에 같은 virtual address가 있는 경우, virtual address가 같은데 PA가 여러 번 caching 될 수 있다. → TLB/cache를 PID로 tag해서 중복 방지
2. Synonyms: 서로 다른 virtual address가 같은 physical address를 가리키는 현상을 의미한다.

VIPT (Virtually Indexed, Physically Tagged)

virtually indexed: Virtual Address의 VPN을 이용해 TLB에서 PPN으로 바꾸는 동안

physically tagged: Cache에서는 page offset을 이용해서 cache 안에서 indexing을 한다.

이후, physical tag를 비교해서, match이면 cache hit이 된다.

• VIPT를 쓸 수 있는 조건? Cache size / Associativity = set size ≤ Page size
• Cache set을 인덱싱하는 비트가 page offset에서만 와야 한다.

ex)

• Page size = 4 KB → 2^12 B → 12 bits of offset
• Cache size = 32 KB
• Associativity = 4-way
• 8KB= 2^13B set size
• set size > page size 이기 때문에 synonym 발생. (aliasing)

‣

헷갈리는 거 정리?

Case study: virtual memory in x86

이론적으로는 segment를 이용한 2-level address translation

48-bit address

segmentation을 요즘은 거의 안 쓰고, EA = VA(거의같음) Paging으로 대부분의 isolation과 protection을 해결함.

On context switch: memory management unit한테 page table에 대해 다른 pointer를 사용하도록 한다.