Memory: The Pagetable

CS 321 Lecture, Dr. Lawlor, 2006/02/15

See Silberschatz chapter 8 on the hardware's support for virtual & physical memory management.

Program Addresses

You can easily print out the memory addresses of the stack, heap, and code with a program like this.

On Linux, this program prints out:
Location of:
Stack=0xbffff164
Code(main)=0x80484ec
Code(printf)=0x8048414
Global=0x8049864
Dll(errno)=0x4011ca20
Heap (small)=0x804a008
Heap (big)=0x4023a008
The program code is at the lowest address-0x8048ec.  Global variables are immediately above this.  DLLs are at a separate segment starting at 0x40....  The stack is above everything, at 0xbffff164.

On Windows, the same program prints out totally different addresses:
Location of:
Stack=406BFE3C
Code(main)=00401000
Code(printf)=0040105D
Global=004086C0
Dll(errno)=004086C4
Heap (small)=407D1BD0
Heap (big)=408D0020
Here, the program code is lowest, then the globals, then the stack, then the heap.

Note that programmers usually don't care where in memory the stack, heap, and code live--as long as they're somewhere, and they stay there!

Physical Addresses

But the addresses in memory a program sees are not the real addresses where data is stored in physical memory (the RAM chips).  Programs work in "virtual" or "logical" memory, and there's a special CPU-defined and OS-managed data structure called the "page table".  There's a separate page table for each process in the system.  To access a program virtual memory address, the CPU (in principle) looks up the address in the page table to figure out where that address is actually stored in physical memory.

Here's the physical memory (displayed using file_display on the Linux physical memory file /proc/kcore) for two separate processes that each allocated 300MB of memory.  One process wrote red pixels into the memory; the other process wrote green pixels.  Note that even though each process sees his own memory as one contiguous piece, in physical memory the two processes' pages are mixed together randomly--the page table for each process in effect reassembles the scattered pieces into one contiguous array.  Also visible are unused memory (black) and other random data structures and code (which look like noise).

Interleaved red and green pages

The "segmented" appearance of this display is caused by the individual "pages" of memory--the finest granularity piece of memory that can be moved by the page table.  A single page table entry (a set of flags, and a pointer to a real physical memory location) can describe between 4KB and 4MB of physical memory.  See chapter 8.7 for lots of pictures and examples of how the page table is actually addressed.