Memory management in Linux - Summary

If you've missed the other parts, following are the links.

Part 1 discusses basic hardware and address binding.

Part 2 discusses logical vs physical address space and memory allocation.

Part 3 discusses memory segmentation and types of segmentation.

Part 4 discusses memory paging and types of paging

Part 5 discusses demand paging and Copy-on-Write (CoW)

Part 6 discusses page replacement, allocation of frames and thrashing

Part 7 discusses memory mapping, memory mapped I/O, allocating kernel memory, buddy system and slab allocation.

This article summarizes of all these parts. Hope this gives you an overall idea starting from a beginner to intermediate level of understanding. If you're looking for detailed understanding, I would recommend reading the book Operating System Concepts by Abraham Silberschatz. For understanding the concepts of memory management, this is the best book I've read. If you're looking for programming concepts of memory management, then the book Linux Kernel Development by Robert Love (3rd Edition) is the one.

Summary of Memory management:

Memory management handles:

• Relocation
• Protection
• Sharing
• Logical organization
• Physical organization

Relocation:

Why virtual memory?

• Physical memory may not be sufficient to run all the programs being requested
• Without virtual memory, holes may appear in the physical memory, called fragmentation
• All programs have access to the entire memory, where security of the system can be compromised

There are two methods of doing virtual memory:

• Paging (uses fixed size memory blocks)
• Segmentation (uses variable size memory blocks)

Paging:

• Virtual memory is divided into small chunks called Pages
• Physical memory is divided into frames
• Pages are mapped to frames using Page tables
• Linux stores page table in CPU cache
• If page table entry is found in CPU cache, then it is hit (data can be fetched in 1 CPU cycle)
• If page table entry is not found in CPU cache, then it is miss (data is fetched directly from the page table)
• If a page is not found in the page table, then the MMU generates an interrupt called Page fault
• As not all the pages from virtual memory fit into to memory, swap memory is used before the physical memory

Handling page fault:

• The MMU checks internal page table to determine if a page reference is valid or invalid
• If the reference is invalid, then Linux terminates the process
• If the reference is valid, then Linux loads the missing page Linux locates a free frame in memory Linux schedules a disk I/O to load the desired page into newly allocated frame When disk I/O is complete, Linux updates the page table to show its frame location and mark it as valid Linux restarts the instruction that generated the page fault

Memory Management Unit (MMU):

• In latest processors, MMU is in-built, integrated into the CPU
• Maps logical addresses to the physical addresses

Protection:

• Processes should not be allowed to access or operate on to the memory locations that are not granted permissions to them
• Protection is checked during the execution of the program
• If the program attempts access memory outside of its granted location, Linux terminates the program with Segmentation fault
• In the case of dynamic libraries, they are stored as a pointer to the library in the executable file. When Linux encounters these pointers, the CPU issues disk I/O and the library is loaded into the memory

Sharing:

• Sharing of memory allows two or more processes to access the same area of memory
• This allows the processes to read, update memory so the other process will have updated information

Logical organization:

• Memory is organized in linear fashion, organized into modules called Segmentation units
• Segmentation units can be written and compiled independently, with different degrees of protection to different modules (conventionally different segments of a binary are compiled together) Code segment - stores the program instructions Stack segment - stores the current program stack Data segment - stores the local and global data of programs
• Each of these segments is represented by an 8-byte descriptor called Segment descriptor
• A segment descriptor is stored in a Global Descriptor Table (GDT) or Local Descriptor Table (LDT)

Physical organization:

• The base-limit registers are used to provide physical organization
• This allows faster access of data though we have fragmented memory

NUMA (Non Uniform Memory Access):

• Allows scaling in multi-processor environment
• Distributed Shared Memory (DSM) is a logical memory structure for multiple processor environment
• All the concepts of UMA hold good for NUMA also, after considering the node id.