Подкачка и замещение страниц

Что делать, когда нужная страница не в памяти, а памяти больше нет — и какую страницу «выселить».

Замещение страниц — выбор страницы, которую выгрузят из памяти, чтобы освободить кадр под новую, когда все кадры заняты.

Подкачка и page fault

Виртуальной памяти может быть больше, чем физической: часть страниц лежит на диске. Когда программа обращается к странице, которой нет в памяти, происходит page fault («промах страницы»). ОС загружает страницу с диска в свободный кадр. А если свободных кадров нет — нужно какую-то страницу выгрузить. Какую? Это и решает алгоритм замещения.

Цель — выгружать ту страницу, которая дольше всего не понадобится, чтобы промахов было меньше. Промахи дороги: обращение к диску в тысячи раз медленнее памяти.

FIFO: первой пришла — первой ушла

Самый простой алгоритм: выгружаем страницу, которая дольше всех в памяти, независимо от того, нужна ли она. Просто, но не всегда умно — старая страница может быть как раз самой востребованной.

from collections import deque

def fifo(refs, frames):
    mem = deque()
    faults = 0
    for page in refs:
        if page not in mem:
            faults += 1
            if len(mem) >= frames:
                mem.popleft()        # выгнать самую старую
            mem.append(page)
    return faults

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"FIFO, 3 кадра: промахов = {fifo(refs, 3)}")

Вывод:

FIFO, 3 кадра: промахов = 9

LRU: давно не использовалась — на выход

LRU (Least Recently Used) выгружает страницу, к которой дольше всего не обращались. Идея опирается на локальность: что давно не нужно, вряд ли понадобится скоро. На практике LRU обычно лучше FIFO.

def lru(refs, frames):
    mem = []   # конец списка = использовалась недавно
    faults = 0
    for page in refs:
        if page in mem:
            mem.remove(page)
            mem.append(page)        # обновить как недавнюю
        else:
            faults += 1
            if len(mem) >= frames:
                mem.pop(0)          # выгнать давно не использованную
            mem.append(page)
    return faults

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"LRU,  3 кадра: промахов = {lru(refs, 3)}")

Вывод:

LRU,  3 кадра: промахов = 10

Optimal: заглянуть в будущее

Optimal выгружает страницу, которая понадобится позже всех (или не понадобится вовсе). Это идеал — меньше промахов не сделать. Но он требует знать будущее, поэтому на практике недостижим; его используют как эталон для сравнения.

def optimal(refs, frames):
    mem = []
    faults = 0
    for i, page in enumerate(refs):
        if page not in mem:
            faults += 1
            if len(mem) >= frames:
                future = refs[i+1:]
                # жертва — та, что понадобится позже всех (или никогда)
                victim = max(mem, key=lambda p: future.index(p) if p in future else 10**9)
                mem.remove(victim)
            mem.append(page)
    return faults

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"Optimal, 3 кадра: промахов = {optimal(refs, 3)}")

Вывод:

Optimal, 3 кадра: промахов = 7

Сравнение на одной строке обращений

Любопытно: на этой конкретной строке FIFO (9) обогнал LRU (10)! Это напоминает, что ни один реальный алгоритм не идеален на всех входах. Кстати, у FIFO есть забавная аномалия Белади: иногда добавление кадров увеличивает число промахов. У LRU такого не бывает.

Итог

• Обращение к странице не в памяти вызывает page fault — загрузку с диска.
• Если кадров нет, алгоритм замещения выбирает страницу-жертву.
• FIFO выгоняет самую старую, LRU — давно не использованную, Optimal — нужную позже всех.
• Optimal даёт минимум промахов, но требует знать будущее; LRU — практичный фаворит.
• FIFO подвержен аномалии Белади, LRU — нет.