Tags: #◇Computer Science #◇CSOPESY #◇Operating Systems #◇08 - Main Memory

CSOPESY 08 - Main Memory

◇Overview

The CPU can only execute instructions and access data that is loaded into main memory (RAM). Because memory is a limited and shared resource, the Operating System faces the complex challenge of managing it securely and efficiently across multiple active processes. The core goals of memory management include Relocation (allowing processes to load into any memory region), Protection (preventing illegal memory accesses), Sharing (allowing controlled access to shared memory, like libraries), and providing a logical abstraction for programmers.

This note covers the evolution of memory management from simple contiguous allocation to sophisticated noncontiguous techniques like paging, addressing external and internal fragmentation, and the hardware that makes rapid memory virtualization possible.

◇Key Concepts

Basic Hardware & Protection

• Base and Limit Registers: To enforce memory protection, hardware relies on these two registers. The Base Register holds the smallest valid physical address, while the Limit Register specifies the size of the memory range. The CPU hardware checks every generated logical address to ensure it falls within these bounds.
• Kernel Mode Privilege: Changing the base and limit registers requires privileged instructions executable only in Kernel Mode. Any unauthorized access out of bounds triggers a fatal hardware trap to the OS.

Address Binding & Logical vs. Physical Memory

• Address Binding: The process of mapping logical program addresses to physical memory addresses. It can occur at Compile Time (absolute code), Load Time (relocatable code), or Execution Time (addresses mapped dynamically on the fly).
• Logical (Virtual) Address: The address generated by the CPU. This is all the user program ever sees.
• Physical Address: The actual hardware memory location.
• Memory-Management Unit (MMU): The hardware device responsible for translating logical addresses to physical addresses at run-time. In contiguous allocation, it simply adds the Base Register to the logical address.

Contiguous Memory Allocation

Early OS designs assigned each process to a single, continuous block of memory. When a process requested memory, the OS searched for an available "hole".

• First-Fit: Allocates the first hole that is big enough. Fast and often efficient.
• Best-Fit: Allocates the smallest hole that is big enough. Requires searching the whole list and produces tiny leftover holes.
• Worst-Fit: Allocates the largest hole, leaving a potentially useful large remainder. Usually the poorest performer.

Fragmentation

• External Fragmentation: Over time, contiguous allocation scatters small, unusable holes throughout memory. Even if the total free memory is sufficient for a new process, no single hole is large enough. (Rule of thumb: 50% rule).
• Internal Fragmentation: When memory is allocated in fixed-size blocks (like pages), the space inside the block that the process doesn't use is wasted.
• Solution to External Fragmentation: Compaction (shuffling memory to merge free space) is slow. The modern hardware solution is Paging.

Paging

Paging breaks physical memory into fixed-sized blocks called Frames, and logical memory into blocks of the same size called Pages.

• Logical Address Translation: Every address consists of a Page Number ($p$) and a Page Offset ($d$). The page number acts as an index into the Page Table, which contains the base physical frame number ($f$). The MMU combines $f$ and $d$ to form the physical address.
• Paging completely eliminates external fragmentation but introduces internal fragmentation on the last page of a process.

Optimizing Paging: TLB and Hierarchical Page Tables

• Translation Look-aside Buffer (TLB): Because keeping the page table in RAM doubles memory access time (one access for the table, one for the data), a high-speed, associative hardware cache called the TLB is used. If a page number is in the TLB (TLB Hit), translation is nearly instantaneous.
• Multi-Level Page Tables: For large 32-bit and 64-bit address spaces, a single continuous page table is too large. The page table itself is paged (e.g., a Page Directory pointing to smaller Page Tables).
• Hashed & Inverted Page Tables: Hashed tables hash the virtual page number. Inverted page tables track physical frames rather than virtual pages, dramatically saving memory at the cost of lookup speed.

Swapping

To increase the degree of multiprogramming, inactive processes (or their pages) can be temporarily swapped out to a backing store (SSD/HDD) to free up RAM. Modern OSes use Page Swapping (paging out individual pages rather than whole processes). Note that mobile OSes (iOS/Android) often avoid swapping to disk due to flash memory write limits, instead relying on aggressive background app termination or voluntary memory release.

◇Algorithms & Formulas

Logical to Physical Translation (Paging)

Given a logical address format with a page size of $2^n$ bytes:

• The lowest $n$ bits constitute the Page Offset ($d$).
• The remaining upper bits constitute the Page Number ($p$).
• Physical Address: (Frame_Number_from_Table[p] * Page_Size) + d

Contiguous Allocation Calculation

• Valid Address Check: 0 <= Logical Address < Limit Register
• Physical Address: Logical Address + Base Register

◇Code Examples

Simulating MMU Translation (Paging)

PAGE_SIZE = 4096 # 2^12 bytes, meaning 12 bits for offset
page_table = {
    0: 5,  # Virtual Page 0 is in Physical Frame 5
    1: 12, # Virtual Page 1 is in Physical Frame 12
    2: 7   # Virtual Page 2 is in Physical Frame 7
}

def translate_address(logical_address):
    # Extract page number and offset
    page_number = logical_address // PAGE_SIZE
    page_offset = logical_address % PAGE_SIZE
    
    if page_number not in page_table:
        raise Exception("Page Fault! Page not in memory.")
        
    frame_number = page_table[page_number]
    
    # Calculate physical address
    physical_address = (frame_number * PAGE_SIZE) + page_offset
    return physical_address

# Example: logical address 8200
# 8200 // 4096 = 1 (Page 1)
# 8200 % 4096 = 8 (Offset 8)
# Frame for Page 1 is 12. Physical = (12 * 4096) + 8 = 49160
print(f"Physical address: {translate_address(8200)}")

◇References & Navigation

• Previous Topic: ◇CSOPESY 07 - Synchronization Tools
• Next Topic: ◇CSOPESY 09 - Virtual Memory
• Related Notes: