Main challenge in using main memory

In multi-process environments, multiple processes share main memory at the same time. So depending on which processes run concurrently, the following thing are dynamically changed.

• The total amount of memory that each process can use
• The memory address of data used in processes
• The physical location of data (main memory or disk)

Virtual Memory (VM)

Provides each process an illusion of the exclusively-use of large memory
Processes think that they use their own memory that can store everything related to them

• CPU and OS manage the mapping between the virtual memory, physical memory and disk

Advantages

• Processes do not need to think about the effect of other processes in using memory
  • The memory space used by processes is fixed virtually
  • Simple development of programs
• Virtual addresses of different processes are mapped to different physical addresses
  • Only OS can manage this mapping information
  • One process cannot access another's data

Term

• Page: the minimum unit of information in virtual memory containing multiple blocks
• Page fault: when an requested page is not present in main memory
• Virtual address: an address that corresponds to a data location in virtual memory
• Physical address: an address that corresponds to a data location in physical memory
• Disk address: an address that corresponds to a data location in disk

Address translation (address mapping)

In virtual memory, pages are mapped from virtual address to physical or disk addresses

• At this time, fully associative placement is used

VM address translation

• 32-bit virtual memory address
• Virtual memory size: $2^{32}$ Bytes = 4GB
• Page size: 4KB = $2^{2+10}$ Bytes
• Physical memory size: 1GB = $2^{30}$ Bytes
• Num of physical pages = $2^{18}$

Total page table size

Num of PTEs $\times$ PTE size = num of virtual pages $\times$ 4Bytes
= Virtual memory size / page size $\times$ 4Bytes
= $2^{32} / 2^{12} \times 2^2$ Bytes = $2^{32 - 12 + 2}$ Bytes = 4MB

TLB (translation Lookaside Buffer)

Since the page tables are stored in main memory, every memory access by a program can take at least twice as long
: one memory access to obtain the physical address and a second access to get the data

TLB is a cache that keeps tract of recently used address mappings to try to avoid an access to the page table.
: cache of page table

Typical TLB structure

• TLB size: 16 ~ 512 page entries
• Fully associative TLBs (used in systems that use small TLBs)
  or Small associative TLBs (used in systems that use large TLBs)
• Replacement policy: random (for fast handling)
• Hit time: 0.5 ~ 1 clock cycle
• Miss penalty: 10 ~ 100 clock cycles
• Miss rate: 0.01% ~ 1%

Integrating TLB, Cache, memory

• Fully-associative TLB
• Physical memory size = 4GB (=$2^{32}$)
• Page size = 4KB = (=$2^{12}$)
• Direct mapped cache
• Num of cache blocks = $2^8$
• Cache block size = $2^4$ word

Workflow

• Access TLB first
• Access cache using physical addresses: "physically addressed cache"

Physically addressed cache

• Physically indexed & physically tagged
  Both the cache index and tag are physical addresses

• 32-bit virtual address
• Page size = $2^p$ Bytes
• Physical memory size = $2^t$ Bytes (t-bit physical address)
• Block size = $2^m$ words
• Num of sets in a cache = $2^s$ sets

Scenario

1. TLB -> hit, Cache -> hit, VM -> hit
   • Best case
   • TLB가 hit이므로 Page table 볼 필요가 없음
   • 즉 main memory 접근 필요 없음
   • 또 Cache가 hit이므로 TLB에 의해 가상주소 -> 실제주소, 이 실제주소로 Cache 접근
2. TLB -> miss, Cache -> hit, VM -> hit
   • TLB가 miss이므로 Page table에 접근해서 가상주소 -> 실제주소 변환 필요 (메모리 접근 1회 필요)
   • Cache는 hit이므로 더 이상 메모리 접근 없음
3. TLB -> miss, Cache -> miss, VM -> miss
   • Worst case
   • 최악의 경우로 memory에서 miss 발생 -> page fault
   • 즉 valid bit가 0이므로 OS가 제어를 넘겨받음
4. VM -> miss면, Cache와 TLB가 무조건 miss
   • 계층구조를 이루고 있기 때문에 hit가 생길 수 없음

Virtually addressed cache

• Virtually indexed & virtually tagged
  Both the cache index and tag are virtually address

• 32-bit virtual address
• Page size = $2^p$ Bytes
• Physical memory size = $2^t$ Bytes (t-bit physical address)
• Block size = $2^m$ words
• Num of sets in a cache = $2^s$ sets

Physically-addressed cache VS virtually-addressed cache