Memory

Why VM

Now-a-days processes are RAM hungry. Every Program(eg: adobe photoshop, microsoft teams) need more RAM.
if 10 such processes want to run simultaneously then 10GB RAM is needed which is not available. VM is illusion to program that it has complete access to RAM.

Virtual Memory & Physical Memory

	Virtual Memory = Hard Disk	Physical Memory = RAM
Size	Bigger	Smaller wrt HD. Stores data and machine code currently being used by the system.
Contains	Pages	Frames
Memory Allocation	Contigous	Contigous
Max Memory Sizes	hard Disk=4GB. Virtual Memory=3GB hard Disk=1TB. Virtual Memory=966GB	hard Disk=4GB. Physical Memory=1GB hard Disk=1TB. Virtual Memory=4GB

Terms

Page

Pages are fixed sized blocks of Virtual Memory.
Size: Page size is typically 4KB, but varies as per OS(upto 64KB).
Pages are mapped to frames in physical memory

Frame

Frames are fixed-size blocks of physical memory.
Page and frame are of same size
Physical memory is divided into frames
Pages from virtual memory are loaded into available frames in physical memory

Paging

Memory management scheme that eliminates the need for contiguous allocation of physical memory/RAM
It divides both virtual and physical memory into fixed-sized blocks, called pages and frames respectively.
When a program accesses data, the operating system maps the virtual address to a physical address using page tables.
And program gets executed even if they are not entirely loaded into physical memory/RAM.

Pure Demand Paging

Type of paging where pages are loaded into RAM/memory only when they are needed (i.e., on demand).
Initially, none of the program’s pages are loaded into RAM/physical memory.
When a page is accessed for the first time, a page fault occurs, and the operating system loads the required page from Virtual Memory/Hard disk into a free frame in RAM/physical memory.
Advantage of Paging: Minimizes RAM usage and allows for efficient use of available RAM/memory.

Page Fault

Page fault occurs to bring page(From Virtual Memory) to RAM/Physical Memory.
MMU uses a trap instruction to switch control to kernel mode.

Trap Instruction (trap())

To bring required pages(From Virtual Memory) to RAM/Physical Memory, CPU uses a trap instruction to switch control to kernel mode. accessing physical page

            @startuml
            participant a.exe as aexe
            participant CPU as cpu
            participant MMU as mmu
            participant PageTable as pt
            participant "trap_handler()\n\nrunning in RAM" as th
            participant "Hard-Disk/Virtual" as hd
            
            note over aexe  #Cyan
            Access 0x1234
            (Virtual address)
            end note 
            
            aexe -> cpu: Read 0x1234
            note over cpu  #Khaki
            Find physical address
            corresponding to 0x1234
            end note
            
            cpu -> mmu: Get Physical address for 0x1234
            note over mmu #LightGreen
            Divide 0x1234 into
            
            page number=1
            offset=0x034
            end note
            
            mmu -> pt: Is Page number=1 present?
            pt -> mmu: entry not present
            note over mmu  #LightGreen
            PAGE FAULT situation
            Signal CPU to issue trap()
            end note
            
            mmu -> cpu: execute trap()\ntrap is software interrupt
            
            note over cpu  #Khaki
            Save current process(a.exe)
            state & switch to kernel
            mode
            end note
            
            cpu -> th: Execute trap() handler
            note over th  #LightBlue
            trap_handler() {
              Get address of Virtual page
              Find page on Hard Disk
            }
            end note
            
            th -> mmu: Give me address of Virtual Page?
            mmu -> th: page address=0x789
            th -> hd: Find page=0x789
            hd -> th: page=x0789
            
            note over th   #LightBlue
            trap_handler() {
              Find free frame on RAM
            }
            end note
            th -> th: Find free/victim \nframe on RAM
            
            hd -> th: Read identified page into frame
            
            th -> pt: Update page table entry
            note over pt  #LightPink
            Page     Frame
            0x1234   0x567
            end note
            
            th -> mmu: Page Table updated
            mmu -> cpu: Page Table updated
            cpu -> pt: Get Physical address
            pt -> cpu: 0x567
            cpu -> aexe: 0x567
            
            note over cpu #Khaki
            cpu resumes operation
            end note
            
            note over aexe   #Cyan
            program reads content
            at RAM=0x567
            end note
            
            @enduml

Page Table

Stores mapping of Pages(Hard Disk/Virtual Memory) to Frames(RAM/Physical memory). trie

MMU(Memory Management Unit) Translate Virtual to Physical Address

Takes Virtual address(of Virtual Memory/Hard Disk) as Input provides Physical Address(of RAM) as output ie translate virtual to physical address.
CPU and MMU are present on single Die, ie on same chip. Mapping of Virtual Address to Physical Address is stored in PAGE TABLE.

TLB(Translation lookaside buffer)

Practically from complete Page Table only a small fraction of the page table entries are heavily read; the rest are barely used.
TLB is hardware inside MMU which stores only few entries(8-256) for Virtual-to-Physical mapping.

TLB Example: Request for Virtual Page comes to TLB
- if TLB entry found-> TLB Hit
- else TLB miss(goes to Page Table), find entry updates Page Table. restarts trap instruction.

Problem with TLB

TLB being small, if it happens process tries to get unused page every time, there will be lot of TLB misses
Solution: Software to maintain a cache internally.

Translation from Virtual Address(Hard Disk) to Physical Address(RAM)

Translation typically involves two components:
- Page number(or fragment): identifies a page in the virtual address space
- Offset: specifies the exact location within a page.

	16 bit Architecture	32 bit Architecture	64 bit Architecture
Bus Size	16 bit = 2 bytes - 2¹⁶=65535 (can access 64KB memory) - you can plug huge Hard disk but that will be no use since in 1 go Only 2 bytes can be accessed	32 bit = 4 bytes - 2³²=4,294,967,296 (can access 4GB memory) - you can plug huge Hard disk but that will be no use since in 1 go Only 4 bytes can be accessed	64 bit = 8 bytes - 2⁶⁴=18x10¹⁸ (can access 18x10⁹GB memory)
Fragment	4 bits	20 bits
Offset 2^12 = 4096 Can access every bit inside page	12 bits	12 bits

Conversion Example(16 bit system)

We have above page table


            Virtual Memory/Hard Disk	Physical Memory/RAM
    Size	64KB	                    32KB
    Count	64k/4k = 16 Pages	        32k/4k = 8 Frames

1. Program accesses virtual address=0


        Code-Segment    
            MOV REG 0 ----> CPU
                             --Get Physical Address for 0--> MMU
                             <--Physical Address 8192-  Page-0 maps to Frame-2
          //MMU has mapped all virtual addresses between 0-4095 onto physical addresses 8192-12287.

2. Program accesses virtual address=8192


        Code-Segment    
            MOV REG 8192 -> CPU
                             --Get Physical Address for 8192-->       MMU
                             <--Physical Add (24k=24x1024=24576)-- Page-3 maps to Frame-6

3. Program accesses virtual address=20500

1stPage(0-4095), 2nd(4096-8191), 3rd(8192-12281), 4th(12282-16383), 5th(16384-20479), 6th(20480-24576)
20500 falls 20 byte inside 6th Page.


        Code-Segment    
            MOV REG 20500 -> CPU
                              -Get Physical Address for 20500-->       MMU
                                                                  Page-6 maps to Frame3
                              <--Physical Add 12302---- Frame-3-start:12282. PhysicalAdd=12282+20=12302

4. Program accesses unmapped address virtual address=24576

Page Fault? CPU issues trap() system call. OS picks a LRU Frame(from Physical Memory/RAM) and moves/writes back to the Hard-Disk/Virtual-Memory. Then copies Page into RAM. MMU updates mapping.
Page Eviction: Movement of pages in/out of RAM is done by SWAPPER.


        Code-Segment
            MOV REG 24576 ---> CPU
                                --Return PhyAdd for 24576-> MMU
                                                            not present
                                                            trap()
                                                                RAM(PM)                             Hard-Disk(VM)
                                                                  --Frame=0 moved to VM-------------->
                                                                  <-Page 24576 loaded in RAM(at address 0)--
                                                      MMU(Updates Mapping)
                                                      Page(12K not mapped)  
                                                      Page-24K maps to Frame0
                                <---Virtual Address 0----

Conversion Example(32,64 bit system)

Problem with Page Table

32 bit = 4 bytes. 2³² = 4,294,967,296 (can access 4GB memory)
4294967296/4096 = 10,48,576 = 1 Million Page entries in Virtual Page Table

Solution-1: TLB

Solution-2: Multilevel Page Tables(32 Bit system)

32 bit address = 10 Bit(Page-Table-1. 2¹⁰=1024 pages) + 10 Bit(Page-Table-2. 1024 pages) + 12 Bit(offset).

Page-Table-1: Contains 1024 pages, each of size = 4KB
Page-Table-2: Contains 1024 pages, each of size = 4KB. multilevel-page-table