Jak działa plik wymiany? Symulacja pamięci wirtualnej w języku C

Pamięć wirtualna jest jednym z najważniejszych mechanizmów współczesnych systemów operacyjnych. Dzięki niej program może korzystać z większej ilości pamięci, niż fizycznie znajduje się w komputerze. Gdy pamięć RAM zaczyna się kończyć, system przenosi rzadziej używane dane do specjalnego pliku na dysku, zwanego plikiem wymiany (ang. swap file lub page file).

Mechanizm ten działa całkowicie przezroczysto dla programu. Programista odczytuje i zapisuje dane w pamięci, a system operacyjny sam decyduje, które fragmenty pozostają w RAM, a które zostaną tymczasowo zapisane na dysku.

Aby lepiej zrozumieć ten proces, można stworzyć prostą symulację w języku C.

Założenia symulacji

Program definiuje:

• 5 stron pamięci (TOTAL_PAGES)
• tylko 2 strony mogą jednocześnie znajdować się w RAM (RAM_PAGES)
• każda strona ma rozmiar 256 bajtów (PAGE_SIZE)
• pozostałe strony przechowywane są w pliku swap.bin

Każda strona reprezentowana jest przez strukturę:

typedef struct {
    int id;
    int loaded;
    int last_used;
    char data[PAGE_SIZE];
} Page;

Pola struktury oznaczają:

• id – numer strony
• loaded – informacja, czy strona znajduje się aktualnie w RAM
• last_used – moment ostatniego użycia strony
• data – dane przechowywane na stronie

Inicjalizacja pamięci

Podczas uruchomienia programu tworzonych jest pięć stron:

Strona 0 -> RAM
Strona 1 -> RAM
Strona 2 -> swap.bin
Strona 3 -> swap.bin
Strona 4 -> swap.bin

Każda strona otrzymuje przykładową zawartość:

Dane strony 0
Dane strony 1
Dane strony 2
Dane strony 3
Dane strony 4

Pierwsze dwie strony pozostają w pamięci operacyjnej, natomiast strony 2–4 zostają zapisane do pliku wymiany.

Zapis strony do pliku wymiany

Funkcja save_page() odpowiada za wyrzucenie strony z RAM.

save_page(victim);

Wewnątrz funkcji wykonywane są trzy kroki:

1. Otwierany jest plik swap.bin.
2. Dane strony są zapisywane pod odpowiednim offsetem.
3. Strona zostaje oznaczona jako niezaładowana.

Przykładowy komunikat:

SWAP OUT: page 0

Oznacza to, że strona 0 została usunięta z pamięci RAM i zapisana na dysku.

Odczyt strony z pliku wymiany

Jeżeli program potrzebuje strony, której nie ma w RAM, wywoływana jest funkcja:

load_page(page);

Funkcja:

1. Otwiera plik swap.bin.
2. Odczytuje odpowiedni fragment pliku.
3. Ładuje dane do pamięci.
4. Oznacza stronę jako aktywną.

Przykładowy komunikat:

SWAP IN : page 2

Oznacza to, że strona została wczytana z pliku wymiany do RAM.

Algorytm LRU

W prawdziwych systemach operacyjnych trzeba zdecydować, którą stronę usunąć z pamięci, gdy zabraknie miejsca.

W tej symulacji wykorzystano algorytm LRU (Least Recently Used).

Jego zasada jest prosta:

Usuwana jest strona, która była używana najdawniej.

Funkcja find_lru() przeszukuje wszystkie strony znajdujące się aktualnie w RAM i wybiera tę z najstarszym znacznikiem czasu.

Przykład:

Strona 0 użyta w chwili 10
Strona 1 użyta w chwili 20

Jeżeli potrzebne będzie miejsce dla kolejnej strony, usunięta zostanie strona 0.

Symulacja page fault

Najciekawsza część programu znajduje się w funkcji:

ensure_loaded(id);

Jeżeli strona znajduje się już w RAM:

READ page 0

następuje natychmiastowy odczyt.

Jeżeli strony nie ma w pamięci:

1. Wybierana jest ofiara metodą LRU.
2. Ofiara trafia do pliku wymiany.
3. Potrzebna strona zostaje odczytana z dysku.
4. Operacja jest kontynuowana.

To dokładnie przypomina prawdziwy page fault obsługiwany przez system operacyjny.

Przykładowy program w GCC

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PAGE_SIZE 256
#define RAM_PAGES 2
#define TOTAL_PAGES 5

typedef struct {
    int id;
    int loaded;
    int last_used;
    char data[PAGE_SIZE];
} Page;

Page pages[TOTAL_PAGES];
int tick = 0;

void save_page(Page *p)
{
    FILE *f = fopen("swap.bin", "r+b");

    if (!f)
        f = fopen("swap.bin", "w+b");

    fseek(f, p->id * PAGE_SIZE, SEEK_SET);
    fwrite(p->data, PAGE_SIZE, 1, f);
    fclose(f);

    p->loaded = 0;

    printf("SWAP OUT: page %d\n", p->id);
}

void load_page(Page *p)
{
    FILE *f = fopen("swap.bin", "rb");

    if (!f) {
        printf("Brak pliku swap\n");
        exit(1);
    }

    fseek(f, p->id * PAGE_SIZE, SEEK_SET);
    fread(p->data, PAGE_SIZE, 1, f);
    fclose(f);

    p->loaded = 1;

    printf("SWAP IN : page %d\n", p->id);
}

int loaded_pages()
{
    int n = 0;

    for (int i = 0; i < TOTAL_PAGES; i++)
        if (pages[i].loaded)
            n++;

    return n;
}

Page *find_lru()
{
    Page *victim = NULL;

    for (int i = 0; i < TOTAL_PAGES; i++) {
        if (!pages[i].loaded)
            continue;

        if (!victim || pages[i].last_used < victim->last_used)
            victim = &pages[i];
    }

    return victim;
}

void ensure_loaded(int id)
{
    Page *p = &pages[id];

    if (p->loaded) {
        p->last_used = ++tick;
        return;
    }

    if (loaded_pages() >= RAM_PAGES) {
        Page *victim = find_lru();
        save_page(victim);
    }

    load_page(p);
    p->last_used = ++tick;
}

void write_page(int id, const char *text)
{
    ensure_loaded(id);

    strcpy(pages[id].data, text);

    printf("WRITE page %d = \"%s\"\n",
           id,
           pages[id].data);
}

void read_page(int id)
{
    ensure_loaded(id);

    printf("READ  page %d = \"%s\"\n",
           id,
           pages[id].data);
}

int main(void)
{
    remove("swap.bin");

    for (int i = 0; i < TOTAL_PAGES; i++) {
        pages[i].id = i;
        pages[i].last_used = ++tick;

        snprintf(
            pages[i].data,
            PAGE_SIZE,
            "Dane strony %d",
            i
        );

        if (i < RAM_PAGES) {
            pages[i].loaded = 1;
        } else {
            pages[i].loaded = 0;

            FILE *f = fopen("swap.bin", "r+b");
            if (!f)
                f = fopen("swap.bin", "w+b");

            fseek(f, i * PAGE_SIZE, SEEK_SET);
            fwrite(pages[i].data, PAGE_SIZE, 1, f);
            fclose(f);
        }
    }

    puts("=== START ===");

    read_page(0);
    read_page(1);
    read_page(2);
    read_page(3);
    read_page(0);
    write_page(4, "NOWE DANE");
    read_page(4);

    return 0;
}

Przykładowe wykonanie programu

Program wykonuje następującą sekwencję:

read_page(0);
read_page(1);
read_page(2);
read_page(3);
read_page(0);
write_page(4, "NOWE DANE");
read_page(4);

Przebieg może wyglądać tak:

=== START ===

READ  page 0 = "Dane strony 0"
READ  page 1 = "Dane strony 1"

SWAP OUT: page 0
SWAP IN : page 2
READ  page 2 = "Dane strony 2"

SWAP OUT: page 1
SWAP IN : page 3
READ  page 3 = "Dane strony 3"

SWAP OUT: page 2
SWAP IN : page 0
READ  page 0 = "Dane strony 0"

SWAP OUT: page 3
SWAP IN : page 4
WRITE page 4 = "NOWE DANE"

READ  page 4 = "NOWE DANE"

Widać tutaj pełny cykl działania pamięci wirtualnej:

• strona jest usuwana z RAM,
• trafia do pliku wymiany,
• później zostaje przywrócona,
• program kontynuuje pracę tak, jakby nic się nie wydarzyło.

Jak wygląda to w rzeczywistym systemie?

W systemach takich jak Windows lub Linux proces jest podobny, ale znacznie bardziej zaawansowany.

Zamiast pięciu stron mogą istnieć miliony stron pamięci.

Procesor korzysta ze specjalnej jednostki MMU (Memory Management Unit), która tłumaczy adresy wirtualne na fizyczne. Gdy program odwołuje się do strony nieobecnej w RAM, procesor generuje wyjątek zwany page fault. Jądro systemu odnajduje stronę w pliku wymiany, ładuje ją do pamięci i pozwala programowi kontynuować wykonywanie instrukcji.

Programista nie musi pisać funkcji takich jak load_page() czy save_page(), ponieważ całość realizowana jest przez system operacyjny.

Podsumowanie

Przedstawiona symulacja pokazuje najważniejsze elementy działania pamięci wirtualnej:

• podział pamięci na strony,
• ograniczoną ilość dostępnego RAM,
• zapis stron do pliku wymiany,
• odczyt stron z pliku wymiany,
• wybór ofiary metodą LRU,
• obsługę sytuacji przypominającej page fault.

Choć program jest niewielki, bardzo dobrze ilustruje zasadę działania pliku wymiany stosowaną przez nowoczesne systemy operacyjne. Dzięki temu łatwiej zrozumieć, dlaczego komputer może uruchamiać programy wymagające większej ilości pamięci niż fizycznie zainstalowany RAM.