Memory Management

Each process has one page table.

Simpified

Linking For linking, each process has its code in address 0x400000. This allows easy linking as the linker can establish fixed addressess.

Loading When data is mapped into a process address space, the operating system kernel will not allocate any memory. Instead it waits to map virtual memory to physical memory.

• So, when loading processes to memory, .data and .text section is entered into the page table and marked as invalid (meaning it's not mapped to RAM).
• This process is called memory mapping.
• Physical mapping is only done when a page fault occurs.

Sharing Shared libraries used by serveral processes (like stdio), it will not be copied multiple times into the RAM.

• Code and read-only data is sharable because it is read only.

Memory Allocation Mapping is not a static construct, so you can modify the page table.

When you do a malloc call or whenever a process needs more memory, you are creating new entries in the page table.

• Mapped to arbitrary pages in physical memory.
• Does not have to be continguous
• The process sends requests to OS kernel to grow the virtual address space or create a new regions. (mmap (request changes to its virtual address space) or sbrk can do this).

Memory Protection

A page may be kernel only (when the supervisor bit SUP = yes) or read-only (e.g., code)

• kernal means the code can only be run by processes in kernel mode.
• if unauthorized users (like user) tries to access kernel only pages, then it will create a page fault.

	SUP	READ	WRT	EXEC	Addresss
VP 0	no	yes	no	yes	PP6
VP 1	no	yes	yes	no	PP4
VP 2	yes	yes	yes	no	PP2

• The headers are the permission
• And PP2 is the address of the physical memory
• In general, if a code is executable (EXEC) then it shouldn't be writable.

Address Translation

Recal the address space is made up of:

• virtual memory size: $N = 2^n$ bytes
• physical memory size: $M = 2^m$ bytes
• page (a block of memory): $P = 2^P$ bytes
• A virtual memory address can be encoded in $n$ bits

Task: maps virtual address to physical address.

• Virtual address (VA): used by machine code instruction
• Physical address (PA): location in RAM

Formally, MAP: $VA \rightarrow PA \cup 0$ where MAP(A) $= PA$ if in RAM or $=0$ otherwise

• Note this happens very frequently in machine code. We will do this in hardware with the Memory Management Unit (MMU)

Architecture

• the virtual page number is the page that the MMU is trying to translate. We use this number to select the page from the page table.
  • If the page is marked as valid, then we can find its physical page number. This is the number that will preprsent the physical address.
  • If the page is not marked valid, it produces a page fault.

Page Hit

• sizeof(PTE) = sizeof(pointer)
  • (PTE = Page table entry)
• Virtual Address (VA): the CPU requests data at virtual address
• Page Table Entry Address (PTEA): is used to look up the page table entry in the page table
• Page Table Entry (PTE): returns the page table entry
• Physical Address (PA): gets the physical address from entry, look up in memory
• Data: returns data from memory to CPU.

Page Fault

• Virtual Address (VA): the CPU requests data at virtual address
• Page Table Entry Address (PTEA): is used to look up the page table entry in the page table
• Page Table Entry (PTE): returns the page table entry
• Exception: the page is not in physical memory
• Page fault exception handler allocates a physical page of memory.
  • if everything is full, then we vitim page to disk
  • new page is loaded to memory along with its data
  • update the page table entry to unmap the old PTE and add a new PTE for this newly allocated and populated data.
  • The CPU is going to re-attempt the instruction that caused the page fault. Memory request re-done.
• Page faults are very expensive.

Page miss exceptrion is a complex task as we have to

• identify which page to remove from RAM (victim page)
• load page from disk to RAM (loading into RAM is very slow)
• update page table entry
• trigger do-over of instruction that caused exception

There is an added complexity of handling in software.

Refinements

On-CPU Cache

An On-CPU Cache integrates cache and virtual memory.

• we claim that having on-disk memory is too slow, so having data in ram is the only practical solution.

Recall:

• we previously claimed that using RAM is too sloww
• having data in cache only practical solution

Both are true, so we need to combine.

The MMU resolves virtual address to physical address

• physical address is checked against cache
• and if the cache misses in page table retrieval, get the page table from memory
• cache miss in data retrieval, get data from memory.

Slow look-up time

Use translation lookahead buffer (TLB)

• Every memory-related instruction must pass through MMU (virtual memory look-up)
• Very frequent, this has to be very fast
• Locality to the rescue
  • subsequent look-ups in same area of memory
  • look-up for a page can be cached

Translation Lookup Buffer:

• Same structure as cache
• Break up address into 3 parts
  • lowest bits: offset in page
  • middle bits: index (location) in cache
  • highest bits: tag in cache
• Associative cache: more than one entry per index

Architecture

• translation lookup buffer (tlb) on CPU chips
• look up page table entry in TLB
• page table entry not in TLB
• Retrieve page table entry from RAM.

Huge address space

Use multi-level page table.

When using an array structure, most of the address space is not used.

You'll have a higher table called the "page directory" that points to a "page table"