Linux Virtual Memory - Paging pt.2

Virtual Memory Map

Each individual process has many data structures associated with it that the kernel uses to manage the process and its environment. /proc/$PID is the window into those data structures, one of which is the virtual memory map, or /proc/$PID/maps . You can take a look at one of these now if you wish, but it's not yet necessary, and we'll take an in-depth look at these in a later lesson.

So what is it? The Virtual Memory Map is a logical structure that maps the extents of all pages available to the process. If a process tries to read or write to an address that does not exist in the virtual memory map, it triggers a segmentation violation aka segmentation fault, or SEGV, which will usually end in termination of the process.

Primary and Secondary Storage

Primary storage is the memory directly available to the CPU, specifically the system's main memory. It is the physical RAM that we've been talking about up until now. Page frames are locations within primary storage.

The big problems with Primary storage is that while fast, it's the most expensive form of "storage" available, and it loses all data between system boots ( known as Volatile Memory.)

Secondary storage is anything that's not main memory, and is defined by (usually) being non-volatile ( data persists between reboots,) and not connected directly to the cpu. It is usually interfaced with via a storage controller, a completely separate processor, that copies the data over a bus to the memory without involving the CPU except to notify it when the transfer has completed (aka Direct Memory Access, DMA.) Secondary storage includes Hard Drives, Solid State Drives, drives with external media like optical (cd, dvd, blueray) magnetic (tapes, floppy disks) or flash memory (sd-cards, USB sticks.)

Paging

Paging is most simply the action of copying a page of data between primary and secondary storage.

It's important to note that "a page"<noun> is different from "to page"<verb>, or "copy two pages" vs "the kernel pages memory to disk" This should not be an issue for native English speakers, but for anyone who is not completely fluent, watch out for it. I will try my best to not be ambiguous.

Page Table

A Page Table is a data structure that holds information necessary for the kernel to translate a virtual page into a physical page frame, locate available page frames, and perform other functions. The exact implementation of the kernel's page tables is highly complex and will be the topic of multiple lessons in the future. For now it's sufficient to understand the difference between a Virtual Memory Map, and a page table. A virtual memory map relates virtual address ranges to its data, a page table relates virtual pages to physical page frames.

Paging in Operation

Let us look at an (extremely simplified) example of a user executing a command from the shell.

The user types the command and hits enter. The shell then calls the kernel to execute the program indicated by the user. The kernel initializes the data structures for managing the process, and sets up the virtual memory map. This map will point to all of the program code and static data of the command's binary executable file. This is done lazily (technical term,) where the kernel creates the mapping, but does not copy the data in to ram. The kernel then passes control over to the process where it begins executing code. The process now reads code and data from its virtual address space, pages that do not exist in physical memory. This triggers a Page Fault, a signal that indicates that the hardware Memory Management Unit (MMU) does not know how to translate the virtual address (more specifically the page address,) into a physical page frame. When this happens, the kernel will catch and handle the fault.

Note that while "Page Fault" sounds like something went wrong, this is all totally normal operation. It is not like a "Segmentation Fault" where something happened that WAS bad, and the process will not terminate.

The page fault is handled by the kernel looking at the virtual memory map to determine what page is being referenced (in this case the program's code and data,) and will "Page In" the data from disk into memory. It does this by looking at the global page table to find where there exists an available page frame, copies the data from disk to memory, and updates the page table with the mapping from the process's virtual page's address to page frame.

Control is passed back to the process, which re-executes the instruction that caused the fault. The MMU will now have the information to correctly translate the page address, and the process is able to read the data. As a program executes it will eventually read code or data across a page boundary, and it will trigger further page faults.

This was an extremely simplified example, but illustrates the core concept.

When your above process completes, the kernel will keep the resident pages in memory; that way if your program is executed again it will not have to wait on disks to page in the same data again. When the supply of available page frames starts running low, the kernel will choose a page to evict from main memory, marking that page frame available. This page eviction process is another highly complex process (another future lesson,) but at its simplest we can say that if a page is not going to be used again soon, it is a prime candidate to evict.

Physical memory is going to be many times more expensive than secondary storage, and consequently most computers will have secondary storage many times larger than RAM. Since RAM and CPU speeds are so much faster than even SSDs (solid state disks,) it is better to wait until it is known that a process will need to access a page before bringing it into main memory.

I did not go over paging out (moving data from memory to disk.) The reason for that is that there are many ways to trigger a page be written to disk that differ greatly based on properties we have not yet defined (next lesson,) and is not as simple as explaining page faults. After a page is triggered for writing however, the process is simple; the kernel copies the page from memory to secondary storage. Both the process of determining when a page out is triggered and how the kernel decides where to write the data will be covered in future lessons.

SUMMARY

Paging is a way for operating systems to make greater use of available system RAM by breaking the contents up into pages and only keeping resident those necessary for program execution. At this point you have all of the information necessary to understand the basics of operation as they existed on the Atlas Computer . Since technology has progressed a little since 1962, the next lesson will explain some different properties associated with virtual memory mappings and their pages.