OS - Memory Management

Select Connection: INPUT[inlineListSuggester(optionQuery(#permanent_note), optionQuery(#literature_note), optionQuery(#fleeting_note)):connections]

Memory is a large array of bytes. Each byte has its own absolute address.

A process (which is a running program) needs to be mapped to absolute addresses and loaded into main memory. Also it accesses data and instructions that themself are loaded into memory and have an address. When the process is ended, that portion of memory is deemed available.
This needs algorithms for Memory Management to optimize memory usage.

Address Binding

• The compiler binds symbolic addresses to relocatable addresses (e.g., “14 bytes from the beginning of the module”).
• The linker or loader binds the relocatable address to an absolute address.

Can bind at:

• Compile time
• Load time
• Execution time

Logical vs Physical Address Space

• Logical: address generated by the CPU.
• Physical: address seen by the memory unit (loaded into the memory-address register).

In terms of binding:

• Compile and load time generate identical logical and physical addresses.
• At execution time, logical and physical addresses differ.
  • Logical address = virtual address.
  • Mapping from virtual to physical is done by hardware: the MMU (memory-management unit).

Dynamic loading

• Previously assumed the entire program was loaded all at once into physical memory.
  • In practice, a routine is not loaded until it is called.
• In C/C++, this is a manual process (using dl functions).

Paging

With contiguous memory allocation, we get the problem of memory fragmentation, regardless of which allocation algorithm is used.

Paging:

A memory-management scheme that permits a process’s physical address space to be non-contiguous.

• Avoids external fragmentation.

Basic method:

• Break physical memory into fixed-size blocks (frames) and logical memory into fixed-size blocks (pages).
• When a process is executed, its pages are loaded into any available frame.
  • The logical address is divided into a page number (p) and a page offset (d).
    • p is used as an index into a per-process page table, which contains the base address of each frame.
• The translation is handled by the MMU.
• No external fragmentation, but some internal fragmentation may occur.
  • Trade-off: smaller pages reduce internal fragmentation but increase overhead and I/O.

SIDENOTE
In Linux, you can examine the ELF file to see how many segments a program has and how many pages it needs.

• readelf -l [program] — examine the ELF file itself.
• cat /proc/[PID]/maps — this is the OS map of the pages. Each row is a range of virtual memory addresses. You can get the exact number of pages the OS has allocated by subtracting the ranges and dividing by the page size (usually 4096; can be found with getconf PAGESIZE).

TLB (Translation Look-Aside Buffer)

• Small, fast-lookup hardware cache.
• Each entry has a key and a value; the item to be searched is compared with all keys simultaneously.

How it works with page tables:

• Contains only a few page-table entries.
• The MMU first checks the TLB.
  • If found, the frame number is immediately available and used to access memory.
  • If not found (TLB miss), fall back to the basic page-table method and add the entry to the TLB.
    • If the TLB is full:
      • Certain entries are wired down (non-removable).
      • Replacement policies such as LRU or round-robin are used.
• Some TLBs store ASIDs (address-space identifiers).
  • The ASID is checked on each lookup; a mismatch causes a TLB miss.
  • If ASIDs are not stored, the TLB must be flushed every time a new page table is selected, to avoid stale entries.

Shared pages

Sharing common code, for example libc.

Structure of the Page table

Hierarchical paging

• Two-level paging: the page table itself is also paged.
• The issue arises with 64-bit address spaces — the outer page table would still be enormous, requiring multiple levels (UltraSPARC uses 7!).

Hashed Page tables

• The hash value is the virtual page number.
  • Each entry contains a linked list of elements that hash to the same location.
  • Each element consists of 3 fields:
    • Virtual page number.
    • Value of the mapped page frame.
    • Pointer to the next element in the list.

Inverted Page tables

• Problem: each page table may consist of millions of entries, consuming large amounts of physical memory just to track how other physical memory is used.
• Solution: inverted page table.
  • Has one entry for each real page of memory.
  • Each entry stores the virtual address of the page in that real memory location, along with information about the process that owns it.
• With this method, sharing pages is not allowed.

Swapping

A process can be temporarily swapped out of memory to a backing store, then brought back in for continued execution.

• Standard swapping: swaps the whole process. No longer used.
• Swapping with paging: swaps individual pages of a process. Widely used.

---

flashcards/stem/os

What is the difference between internal and external fragmentation in OS memory management?::internal happens inside an allocated block, while external between allocated blocks

What is the difference between a logical and a physical address?::A logical address is generated by the CPU; a physical address is what the memory unit actually sees (loaded into the memory-address register).

What hardware device maps virtual addresses to physical addresses?::The MMU (memory-management unit).

What problem does paging solve?::External memory fragmentation from contiguous allocation.

In paging, what are frames and pages?::Frames are fixed-size blocks of physical memory; pages are fixed-size blocks of logical memory.

What is the TLB?::A small, fast hardware cache that stores a subset of page-table entries to speed up address translation.

What is the inverted page table’s key trade-off?::It saves memory (one entry per physical frame instead of per virtual page), but makes page sharing impossible.

What is hierarchical paging?::The page table itself is paged, creating multiple levels to avoid a single huge page table.

What is swapping with paging?::Individual pages of a process are swapped to a backing store and back, rather than the whole process. Widely used today.