Memory management: paging, segmentation and virtual memory

Logical and physical addresses, page tables, segments, page faults and disk thrashing.

A10.3Operating systems, software and translatorsA level40 min

At GCSE (F9.6) you met RAM, and virtual memory as the thing that happens when RAM is full. At A level you need to know how the operating system actually divides memory between processes. It has three problems to solve at once:

• sharing: many processes are loaded at the same time, and each needs somewhere to live;
• protection: one process must not read or overwrite another's memory, or the operating system's;
• size: the processes together may need more memory than the computer has.

Paging and segmentation solve the first two. Virtual memory solves the third.

Logical and physical addresses

A program is written as if its memory starts at address 0. That is its logical address (also called a virtual address). The real location in RAM is the physical address. The operating system, with help from the processor's memory management hardware, translates every logical address into a physical one each time the program uses memory. A process can only ever produce addresses inside its own translation, so it cannot reach anyone else's memory.

Paging

In paging, a process's logical memory is split into pages of one fixed size (a few kilobytes is common), and physical memory is split into frames of exactly the same size. Any page can go in any free frame, so a process does not need one continuous block of RAM.

Each process has a page table: entry n says which frame holds page n. A logical address is split into a page number and an offset within the page:

• page number = address DIV page size
• offset = address MOD page size
• physical address = frame number × page size + offset

With a page size of 256 bytes, logical address 700 is page 2 (700 DIV 256), offset 188 (700 MOD 256). If the page table says page 2 is in frame 5, the physical address is 5 × 256 + 188 = 1468. Because 256 is a power of 2, the split is just a split of the binary: the low 8 bits are the offset and the rest is the page number.

PAGE_SIZE = 256
page_table = {0: 3, 1: 6, 2: 5}

for address in [700, 40, 300]:
    page, offset = address >> 8, address & 0xFF      # the same as DIV 256 and MOD 256
    frame = page_table[page]
    print(f"{address} = {address:010b}: page {page}, offset {offset} -> frame {frame} -> {frame * PAGE_SIZE + offset}")

Run this in the simulator

Pages are a physical division: a page boundary can fall in the middle of a subroutine or an array. Since every frame is the same size, any free frame will do, so there are no unusable gaps between blocks. The only waste is inside the last page of each process, which is usually partly empty.

Segmentation

In segmentation, memory is split into segments of different sizes that match the program's logical structure: a segment for the code, one for the data, one for the stack, or one per module. Each segment has an entry in a segment table holding where it starts in physical memory (its base) and how long it is (its limit).

A logical address is a segment and an offset. The offset is checked against the limit, and an address beyond the end of the segment is refused: that is where the error name segmentation fault comes from.

segments = {"code": (4000, 1200), "data": (9000, 300), "stack": (2000, 500)}   # (base, limit)

def translate(segment, offset):
    base, limit = segments[segment]
    if offset >= limit:
        return "segmentation fault"
    return base + offset

print(translate("code", 150))     # 4150
print(translate("data", 299))     # 9299, the last byte of data
print(translate("data", 300))     # one past the end

Run this in the simulator

Because segments vary in size, loading and removing them leaves gaps between segments that may be too small to use. This is external fragmentation.

Real systems often combine them, splitting each segment into pages.

Virtual memory

Virtual memory uses part of secondary storage as if it were extra RAM. Paging makes this natural: a page does not have to be in a frame at all. Pages that are not being used are swapped out to disk, and their page table entries marked as not present.

When a process uses an address in a page that is on disk, the processor raises a page fault. The operating system finds a free frame (swapping another page out to disk if there is none), loads the page from disk into it, updates the page table, and lets the process carry on as if nothing happened.

This lets more processes run than would fit in RAM, and lets a program bigger than RAM run at all. The cost is speed: secondary storage is thousands of times slower than RAM. If RAM is so short that the OS spends more time swapping pages in and out than running processes, the computer slows almost to a stop. This is disk thrashing. The fix is more RAM, or fewer processes.

Task: paging with page faults

Write translate(address) for a paging system. The inputs are:

• PAGE_SIZE, the size of a page and a frame in bytes (256);
• page_table, a dictionary from page number to frame number, where None means the page is on disk;
• free_frames, a list of frame numbers that are free, used from the front;
• addresses, the logical addresses to translate, each a whole number from 0 to 1023.

For each address, work out the page number and offset. If the page's entry is None, handle the page fault: take the first frame out of free_frames, store it in the page table, and print page fault: page <page> loaded into frame <frame>. Then print <address> -> page <page> offset <offset> -> <physical address>, and return the physical address. Call translate for every address in addresses, in order. A page that was loaded by an earlier fault is in memory now, so it does not fault again. The robot stays still.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

PAGE_SIZE = 256
page_table = {0: 5, 1: 2, 2: None, 3: 7}
free_frames = [1, 4]
addresses = [300, 12, 600, 1000, 700]

def translate(address):
    pass

Challenges

1. Work out by hand where logical address 1023 goes with this page table, then check with your program.
2. When free_frames is empty, a page must be swapped out. Choose the page that was loaded first, set its entry back to None, and reuse its frame. Add enough addresses to cause it.
3. Count the page faults for a list of 20 addresses with only 2 frames, then with 4. What would thrashing look like in these numbers?