Управление памятью

Каждый вызов `malloc()`, каждый запуск программы, каждое открытие файла - OS распределяет память между тысячами процессов. Но как компьютер с 16 ГБ RAM запускает программы, требующие в сумме 50 ГБ? Почему процесс не может просто обратиться к любому адресу памяти? Почему игра вылетает с 'out of memory', когда в диспетчере задач показано 8 ГБ свободной RAM?

• **Почему Chrome занимает 2 ГБ памяти?** Каждая вкладка - отдельный процесс с виртуальным адресным пространством. OS создаёт иллюзию, что у каждого процесса 2⁶⁴ байт памяти, хотя физической RAM всего 16 ГБ.
• **Как Redis держит 100 ГБ данных в памяти?** Виртуальная память + swapping. Часто используемые данные в RAM (hot cache), редкие - на SSD. MMU и OS делают это прозрачно для приложения.
• **Почему игры требуют 'непрерывный блок памяти'?** Старые движки используют contiguous allocation для текстур. Современные (Unreal, Unity) используют paging-based allocators, устраняя проблему фрагментации.

Цели урока

• Объяснить иерархию: registers → L1/L2/L3 → RAM → SSD → HDD по скорости и цене за байт
• Различать address binding на compile, load и execution time
• Сравнить contiguous allocation, paging, segmentation и их trade-offs
• Знать internal vs external fragmentation и стратегии compaction
• Понимать роль MMU: трансляция логического адреса в физический

Иерархия памяти

**Память компьютера** организована как иерархия уровней, каждый из которых отличается скоростью доступа, объёмом и стоимостью. Понимание этой иерархии - ключ к написанию эффективного кода.

**Почему иерархия важна?** Доступ к регистру занимает **0.3 наносекунды**. Доступ к RAM - **100 наносекунд** (в 300 раз медленнее!). Доступ к диску - **10 миллисекунд** (в 33 миллиона раз медленнее регистра). Если бы обращение к регистру длилось 1 секунду, то чтение с диска заняло бы **1 год**.

**Принцип локальности** - основа эффективного использования иерархии памяти: • **Temporal locality (временная):** Если данные использовались недавно, вероятно, будут использованы снова • **Spatial locality (пространственная):** Если данные по адресу X использовались, вероятно, скоро понадобятся данные рядом (X+1, X+2)

**Cache miss vs Cache hit:** • **Cache hit** - данные найдены в кеше (~1-10 нс) • **Cache miss** - нужно идти в RAM (~100 нс) или на диск (мкс-мс) Программа с 90% cache hit в 10 раз быстрее программы с 50% cache hit!

**Задача OS:** Управлять RAM (main memory), предоставляя каждому процессу изолированное адресное пространство и перемещая редко используемые данные на диск (swapping).

Привязка адресов

**Адресная привязка (address binding)** - процесс сопоставления логических адресов программы с физическими адресами в RAM. Программа оперирует виртуальными адресами, OS переводит их в физические.

**Три момента привязки адресов:** 1. **Compile time** - адреса жёстко прописаны в коде (MS-DOS .COM файлы). Программа может загрузиться только по фиксированному адресу 2. **Load time** - адреса определяются при загрузке в память. Требует перемещаемый код (relocatable code) 3. **Execution time** - адреса переводятся "на лету" при выполнении. Требует аппаратную поддержку (MMU)

Современные OS используют **execution time binding** через MMU (Memory Management Unit) - специальный чип в процессоре, который транслирует виртуальные адреса в физические.

**Логическое vs физическое адресное пространство:** • **Логическое (виртуальное)** - адреса, которые видит программа. На 64-битной системе от 0 до 2⁶⁴ (16 exabytes!) • **Физическое** - реальные адреса в RAM. При 16 ГБ RAM физических адресов максимум 16 ГБ

**Релокация (relocation)** - изменение адресов при загрузке программы. Простейший механизм: **base register + offset**.

Непрерывное размещение

**Непрерывное размещение (contiguous allocation)** - каждый процесс занимает **единый непрерывный блок** физической памяти. Самый простой метод, использовался в ранних OS.

**Задача размещения:** Когда приходит новый процесс размером N, OS должна найти свободный блок >= N. Существует несколько стратегий:

**Алгоритмы размещения:** • **First Fit** - взять первый подходящий блок (быстро, но может оставить маленькие дырки) • **Best Fit** - взять наименьший достаточный блок (экономит место, но медленный поиск) • **Worst Fit** - взять наибольший блок (надежда что останется полезная дырка, редко применяется) • **Next Fit** - как First Fit, но продолжать с места последней аллокации

**Защита памяти в contiguous allocation:** Используются два регистра - **base** и **limit**. MMU проверяет каждый адрес:

**Проблемы contiguous allocation:** • Фрагментация памяти (следующая концепция) • Невозможность роста процесса (нужно переместить весь блок) • Неэффективное использование RAM

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

**Фрагментация (fragmentation)** - главная проблема управления памятью. Память есть, но она разбита на маленькие куски и не может быть использована эффективно.

**Два типа фрагментации:** • **Внешняя фрагментация (external)** - достаточно свободной памяти, но она разбита на маленькие несмежные блоки • **Внутренняя фрагментация (internal)** - процессу выделено больше памяти, чем нужно, остаток тратится впустую

**Решения внешней фрагментации:** 1. **Compaction (уплотнение)** - сдвинуть все процессы вместе, объединив свободную память в один блок. Проблема: очень дорого (нужно переписать много данных и обновить адреса) 2. **Paging (страничная организация)** - разделить память на маленькие фиксированные блоки (страницы). Процесс может занимать несмежные страницы. Решает внешнюю фрагментацию!

**Внутренняя фрагментация (internal fragmentation):** Возникает когда память выделяется **фиксированными блоками** (например, страницами по 4 КБ). Процесс запрашивает 3.5 КБ, получает целую страницу 4 КБ. 0.5 КБ тратится впустую внутри выделенного блока.

**Paging полностью решает внешнюю фрагментацию**, но вводит небольшую внутреннюю. Это приемлемый trade-off - в среднем теряется 0.5 страницы (2 КБ) на процесс против невозможности использовать сотни мегабайт при внешней фрагментации.

**Интересный факт:** Исследования показали, что в системе с contiguous allocation после нескольких часов работы может тратиться впустую **до 50%** RAM из-за внешней фрагментации! Paging снижает потери до **1-3%** (internal fragmentation).

Ключевые идеи

• **Иерархия памяти:** От регистров (0.3 нс) до HDD (10 мс) - разница в 33 миллиона раз! Эффективная программа использует принципы локальности для минимизации cache misses.
• **Address binding:** Программа работает с виртуальными адресами, MMU транслирует их в физические на лету. Это позволяет OS перемещать процессы, изолировать их и использовать больше памяти, чем физически установлено (swapping).
• **Contiguous allocation:** Процесс занимает единый блок памяти. Просто, но приводит к внешней фрагментации. Алгоритмы First/Best/Worst Fit пытаются эффективно использовать дырки в памяти.
• **Фрагментация:** Внешняя (память разбита на куски) решается paging. Внутренняя (выделено больше чем нужно) - неизбежный overhead фиксированных страниц (~1-3% потерь).

Связанные темы

Управление памятью - основа для понимания виртуальной памяти и производительности:

• Виртуальная память (Virtual Memory) — Paging и swapping позволяют программам использовать больше памяти, чем физически доступно. Demand paging загружает страницы по требованию
• Процессы — Каждый процесс имеет изолированное адресное пространство благодаря MMU. fork() копирует виртуальные страницы через copy-on-write
• Файловые системы — Memory-mapped files (mmap) отображают файл в адресное пространство процесса. OS подгружает страницы файла по требованию как обычную память
• Алгоритмы замещения страниц — Когда RAM заканчивается, какую страницу вытеснить на диск? LRU, Clock, Second Chance - алгоритмы выбора жертвы для swapping

Вопросы для размышления

• Почему 64-битная система может адресовать 2⁶⁴ байт (16 exabytes), но никто не устанавливает столько RAM? Где виртуальные адреса, которые не отображены в физическую память?
• Если paging решает внешнюю фрагментацию, почему malloc всё ещё использует free lists и алгоритмы типа First Fit? Разве OS не управляет всей памятью?
• Почему увеличение размера страницы с 4 КБ до 2 МБ (huge pages) ускоряет базы данных, но может замедлить обычные приложения?
• Как OS гарантирует, что два процесса не получат доступ к одной и той же физической памяти случайно? Что произойдёт если баг в MMU?

Связанные уроки

• os-08-virtual-memory — Виртуальная память строится поверх физической организации
• os-02-processes — Каждый процесс имеет собственное адресное пространство
• os-16-memory-advanced — NUMA, huge pages, memory-mapped I/O - продвинутые темы
• rt-39