Фрагментация и thrashing

Две болезни управления памятью: память «есть, но не влезает» и система, которая бесконечно гоняет страницы.

Фрагментация — потеря полезной памяти из-за того, как она поделена; thrashing — состояние, когда система тратит почти всё время на подкачку страниц, а не на работу.

Внешняя фрагментация

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

def external(holes, request):
    total = sum(holes)
    fits = [h for h in holes if h >= request]
    print(f"Свободные дыры (КБ): {holes}")
    print(f"Суммарно свободно: {total} КБ")
    print(f"Запрос: {request} КБ непрерывной памяти")
    if fits:
        print(f"OK: помещается в дыру {min(fits)} КБ")
    else:
        print(f"ОТКАЗ: ни одна дыра не вмещает {request} КБ,")
        print(f"хотя свободно {total} КБ — это внешняя фрагментация")

external([100, 300, 200, 50], 400)

Вывод:

Свободные дыры (КБ): [100, 300, 200, 50]
Суммарно свободно: 650 КБ
Запрос: 400 КБ непрерывной памяти
ОТКАЗ: ни одна дыра не вмещает 400 КБ,
хотя свободно 650 КБ — это внешняя фрагментация

Именно от внешней фрагментации спасает paging: страницы кладут в любые свободные кадры, непрерывность не нужна.

Внутренняя фрагментация

Возникает, когда память выдают блоками фиксированного размера (как в paging). Если процессу нужно чуть больше блока, ему дают целый лишний блок, и «хвост» пропадает зря. Память выделена, но используется не полностью.

def internal(page_size, needed):
    pages = -(-needed // page_size)     # округление вверх
    allocated = pages * page_size
    waste = allocated - needed
    print(f"Нужно {needed} байт, размер страницы {page_size}")
    print(f"Выделено {pages} страниц = {allocated} байт")
    print(f"Внутренняя фрагментация: {waste} байт потеряно зря")

internal(4096, 9000)

Вывод:

Нужно 9000 байт, размер страницы 4096
Выделено 3 страниц = 12288 байт
Внутренняя фрагментация: 3288 байт потеряно зря

Thrashing: система «захлёбывается»

Когда процессам в сумме нужно гораздо больше памяти, чем есть физически, начинается беда. Чтобы загрузить нужную страницу, ОС выгружает другую — но та сразу понадобится снова. Система почти всё время занята подкачкой страниц с диска, а полезная работа почти не идёт. Это и есть thrashing (пробуксовка).

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

# Модель: чем больше дефицит памяти, тем выше доля времени на подкачку
needed_pages = [10, 30, 50, 80, 120]
physical_frames = 50

for need in needed_pages:
    if need <= physical_frames:
        swap_ratio = 0.0
    else:
        deficit = (need - physical_frames) / need
        swap_ratio = min(0.95, deficit)   # доля времени на подкачку
    useful = (1 - swap_ratio) * 100
    print(f"Нужно {need:3} страниц (есть {physical_frames}): "
          f"полезной работы {useful:5.1f}%")

Вывод:

Нужно  10 страниц (есть 50): полезной работы 100.0%
Нужно  30 страниц (есть 50): полезной работы 100.0%
Нужно  50 страниц (есть 50): полезной работы 100.0%
Нужно  80 страниц (есть 50): полезной работы  62.5%
Нужно 120 страниц (есть 50): полезной работы  41.7%

Как борются с thrashing

• Рабочее множество (working set). ОС следит, какой набор страниц процесс активно использует, и старается держать его целиком в памяти.
• Снижение мультипрограммирования. Если памяти не хватает, лучше приостановить часть процессов, чем буксовать всем.
• Добавить памяти. Самое прямое решение — больше физической RAM.

Итог

• Внешняя фрагментация — память есть, но разбита на дыры, в которые запрос не влезает.
• Внутренняя фрагментация — потери внутри блоков фиксированного размера.
• Paging устраняет внешнюю фрагментацию, но порождает внутреннюю.
• Thrashing — система занята почти только подкачкой страниц, полезной работы почти нет.
• Борются рабочим множеством, снижением числа процессов и добавлением памяти.