Лекция 3. Управление памятью и файловые системы

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

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

1.1. Уровни иерархии

Уровень	Тип памяти	Типичный объём	Время доступа	Стоимость за ГБ
0	Регистры процессора	десятки–сотни байт	< 1 нс	—
1	Кэш L1	32–128 КБ (на ядро)	~1–2 нс	очень высокая
2	Кэш L2	256 КБ – 1 МБ (на ядро)	~3–10 нс	высокая
3	Кэш L3	4–64 МБ (общий)	~10–30 нс	высокая
4	Оперативная память (RAM)	4–128 ГБ	~50–100 нс	средняя
5	SSD (твердотельный диск)	256 ГБ – 4 ТБ	~25–100 мкс	низкая
6	HDD (жёсткий диск)	1–20 ТБ	~5–10 мс	очень низкая
7	Сетевое хранилище / лента	практически неограничен	десятки мс и более	минимальная

1.2. Принцип локальности

Эффективность иерархии памяти основана на принципе локальности — эмпирическом наблюдении о поведении программ:

Временна́я локальность (temporal locality): если к ячейке памяти обратились сейчас, велика вероятность повторного обращения в ближайшем будущем. Пример — переменная-счётчик в цикле.
Пространственная локальность (spatial locality): если к ячейке обратились, вероятно, скоро понадобятся и соседние ячейки. Пример — последовательный обход массива.

Благодаря локальности кэши, занимая лишь малую долю общего объёма, обеспечивают попадания (cache hits) в 90–99 % случаев, что радикально ускоряет работу.

2. Адресация: физические и логические адреса

2.1. Физические адреса

Физический адрес — это реальный номер ячейки в аппаратной оперативной памяти (RAM). Именно физические адреса «видит» шина памяти и контроллер.

2.2. Логические (виртуальные) адреса

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

2.3. Зачем нужна трансляция адресов

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

Изоляция процессов: каждый процесс работает в собственном виртуальном адресном пространстве и не может напрямую обратиться к памяти другого.
Упрощение компоновки: компилятор и компоновщик генерируют код, привязанный к фиксированным виртуальным адресам, не заботясь о реальном расположении в RAM.
Эффективное использование памяти: ОС может загружать в RAM только те части программы, которые действительно используются.
Разделение кода: несколько процессов могут разделять одну физическую копию библиотеки, отображённую в их виртуальные пространства.

Трансляцию выполняет аппаратный блок — MMU (Memory Management Unit), встроенный в процессор.

3. Простые методы распределения памяти

До появления виртуальной памяти использовались более простые подходы.

3.1. Фиксированные разделы (fixed partitions)

Вся оперативная память делится на разделы фиксированного размера при загрузке системы. Каждому процессу выделяется один раздел.

Достоинство: простая реализация.
Недостаток: внутренняя фрагментация — если процесс использует 300 КБ, а раздел составляет 512 КБ, то 212 КБ пропадают впустую.

3.2. Динамические разделы (dynamic partitions)

Память выделяется процессу ровно столько, сколько нужно. Разделы создаются и уничтожаются по мере запуска и завершения процессов.

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

3.3. Борьба с фрагментацией

Вид фрагментации	Описание	Где возникает	Метод борьбы
Внутренняя	Неиспользуемое пространство внутри выделенного блока	Фиксированные разделы, страничная организация	Уменьшение размера единицы выделения
Внешняя	Свободная память разбросана мелкими фрагментами	Динамические разделы, сегментация	Уплотнение (compaction), страничная организация

4. Виртуальная память и страничная организация

4.1. Идея виртуальной памяти

Виртуальная память — это механизм, позволяющий каждому процессу работать в своём изолированном адресном пространстве, размер которого может превышать объём физической RAM. Части, которые в данный момент не нужны, хранятся на диске (в файле подкачки или swap-разделе).

4.2. Страничная организация (paging)

Это наиболее распространённый метод реализации виртуальной памяти.

Виртуальное адресное пространство делится на блоки фиксированного размера — страницы (pages), обычно 4 КБ.
Физическая память делится на блоки такого же размера — фреймы (frames, page frames).
Соответствие «страница → фрейм» хранится в таблице страниц (page table), которая есть у каждого процесса.

При обращении к виртуальному адресу MMU разбивает его на две части:

Виртуальный адрес = [номер страницы | смещение внутри страницы]

MMU находит номер страницы в таблице страниц, получает номер фрейма и формирует физический адрес:

Физический адрес = [номер фрейма | смещение]

4.3. Многоуровневые таблицы страниц

При 32-битном адресном пространстве и страницах по 4 КБ таблица содержит 2²⁰ ≈ 1 миллион записей. Хранить такую таблицу целиком для каждого процесса расточительно, ведь бо́льшая часть адресного пространства обычно не используется.

Решение — разбить таблицу на несколько уровней:

Двухуровневая (x86-32): виртуальный адрес → [каталог | таблица | смещение]. Каталог содержит указатели на таблицы второго уровня. Неиспользуемые таблицы не создаются.
Четырёхуровневая (x86-64): PML4 → PDP → PD → PT → фрейм. Позволяет адресовать до 256 ТБ виртуальной памяти.
Пятиуровневая (расширение LA57 на новых процессорах): расширяет пространство до 128 ПБ.

5. TLB — Translation Lookaside Buffer

5.1. Проблема производительности

При многоуровневых таблицах одно обращение к памяти требует нескольких дополнительных обращений (по одному на каждый уровень). Это неприемлемо замедлило бы работу.

5.2. Решение: TLB

TLB (Translation Lookaside Buffer) — это небольшой, но очень быстрый кэш трансляций внутри процессора. Он хранит недавно использованные соответствия «номер страницы → номер фрейма».

Типичный размер: 64–1024 записей.
Время поиска: 1 такт (поиск по ассоциативной памяти — по содержимому, а не по индексу).
TLB hit: трансляция найдена, обращение к таблице страниц не нужно.
TLB miss: нужен обход таблицы страниц (page table walk), результат заносится в TLB.

В большинстве рабочих нагрузок TLB hit rate составляет > 99 %, благодаря чему виртуальная память почти не снижает скорость работы.

5.3. Сброс TLB

При переключении контекста (context switch) ОС, как правило, сбрасывает TLB, поскольку у нового процесса другая таблица страниц. Для снижения потерь используются ASID (Address Space Identifier) — теги, позволяющие TLB хранить записи от разных процессов одновременно.

6. Подкачка и алгоритмы замещения страниц

6.1. Страничное прерывание (page fault)

Если процесс обращается к странице, которая в данный момент не загружена в RAM (бит присутствия = 0), процессор генерирует страничное прерывание (page fault). Обработчик в ОС:

Находит нужную страницу на диске (в swap-файле или файле подкачки).
Находит свободный фрейм в RAM (или вытесняет какую-либо страницу).
Загружает страницу в фрейм и обновляет таблицу страниц.
Перезапускает инструкцию, вызвавшую прерывание.

6.2. Алгоритмы замещения страниц

Когда свободных фреймов нет, ОС должна выбрать «жертву» — страницу для вытеснения. Качество выбора определяет число page fault, а следовательно — производительность.

Пример для анализа. Рассмотрим последовательность обращений к страницам при 3 фреймах:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

6.2.1. FIFO (First-In, First-Out)

Вытесняется страница, которая находится в памяти дольше всех.

Прост в реализации (очередь).
Не учитывает реальное использование: может вытеснить часто используемую страницу.
Подвержен аномалии Белади: увеличение числа фреймов может привести к росту числа page fault.
Для приведённой последовательности при 3 фреймах: 15 page faults.

6.2.2. Оптимальный алгоритм (Белади, OPT)

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

Даёт минимально возможное число page fault.
Невозможен на практике: требует знания будущих обращений.
Используется как эталон для оценки других алгоритмов.
Для приведённой последовательности при 3 фреймах: 9 page faults.

6.2.3. LRU (Least Recently Used)

Вытесняется страница, к которой дольше всего не обращались.

Хорошая аппроксимация оптимального алгоритма (опирается на временну́ю локальность).
Сложнее в реализации: нужно отслеживать порядок обращений (штампы времени или стек).
Для приведённой последовательности при 3 фреймах: 12 page faults.

6.2.4. Clock (алгоритм «второго шанса»)

Модификация FIFO с учётом бита обращения (reference bit):

Страницы расположены «по кругу» (циклический список).
Стрелка указывает на кандидата.
Если бит обращения = 1 — обнуляем его, даём «второй шанс», стрелка сдвигается.
Если бит = 0 — страница вытесняется.

Clock — это практический компромисс: проще LRU в реализации, но значительно лучше FIFO.

6.3. Сравнение алгоритмов

Алгоритм	Page faults (пример)	Сложность	Практичность
FIFO	15	O(1)	Простой, но неэффективный
OPT	9	—	Теоретический эталон
LRU	12	O(n) / аппаратная	Хорош, но дорог в реализации
Clock	~12–13	O(1) аморт.	Используется в реальных ОС

7. Сегментация vs страничная организация

7.1. Сегментация

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

Достоинство: соответствует логической структуре программы; упрощает совместное использование и защиту (например, сегмент кода — «только чтение»).
Недостаток: внешняя фрагментация (сегменты имеют разный размер).

7.2. Сравнение

Характеристика	Страничная организация	Сегментация
Единица деления	Страница (фиксир. размер)	Сегмент (переменный размер)
Фрагментация	Внутренняя (небольшая)	Внешняя
Видимость программисту	Прозрачна	Может быть видна
Защита	На уровне страниц	На уровне сегментов
Совместное использование	Сложнее	Естественнее

7.3. Сегментно-страничная организация

Архитектура x86 исторически поддерживает оба механизма одновременно: виртуальный адрес сначала транслируется через сегментный блок в линейный адрес, затем — через страничный блок в физический. На практике в современных ОС (Linux, Windows, macOS) сегментация используется минимально (плоская модель: все сегменты покрывают всё пространство), а реальное разделение выполняет страничная организация.

8. Файловая система: понятие и задачи

8.1. Определение

Файловая система (ФС) — это способ организации, хранения и доступа к данным на носителе информации. ФС определяет, как данные размещаются на диске, как именуются, как обеспечивается целостность и контроль доступа.

8.2. Задачи файловой системы

Хранение данных: размещение файлов на физическом носителе и учёт свободного пространства.
Именование: предоставление человекочитаемых имён вместо дисковых адресов.
Доступ: чтение, запись, выполнение, навигация по каталогам.
Целостность: защита от потерь данных при сбоях (журналирование, контрольные суммы).
Контроль доступа: разграничение прав на файлы и каталоги.

8.3. Метаданные

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

9. Структура файловой системы

9.1. Общая схема

На низком уровне любая ФС размещается на разделе диска и содержит:

Суперблок / заголовок — описание ФС: тип, размер, расположение ключевых структур, счётчик свободных блоков.
Структуры метаданных — описание файлов (inode, MFT-записи и т.д.).
Блоки данных — собственно содержимое файлов.
Карта свободного пространства — bitmap или другой механизм учёта.

9.2. inode (Unix/Linux)

В файловых системах семейства Unix (ext4, XFS, Btrfs и др.) каждый файл описывается структурой inode (index node):

Номер inode — уникальный идентификатор файла в пределах ФС.
Хранит: тип файла, права доступа, владельца, группу, размер, временны́е метки, счётчик жёстких ссылок.
Содержит указатели на блоки данных: прямые (direct), косвенные (indirect), двойные и тройные косвенные.
Не хранит имя файла — имя хранится в записи каталога, которая связывает имя с номером inode.

9.3. MFT — Master File Table (NTFS)

В NTFS (Windows) аналогом inode служит MFT — таблица, где каждому файлу соответствует запись (обычно 1 КБ):

Запись содержит атрибуты: имя файла, временны́е метки, права (security descriptor), данные.
Малые файлы (< ~700 байт) могут храниться прямо в MFT-записи (резидентное хранение).
Для больших файлов запись содержит список экстентов (runs) — непрерывных участков на диске.

9.4. Сравнение inode и MFT

Характеристика	inode (ext4)	MFT (NTFS)
Размер записи	256 байт (по умолчанию)	1024 байт
Имя файла	В каталоге	В MFT-записи (атрибут)
Малые файлы	Inline data (ext4)	Резидентное хранение
Указатели на данные	Прямые + косвенные блоки / extents	Экстенты (runs)
Журнал	Отдельная структура	$LogFile

10. Типы файловых систем

10.1. Обзор основных ФС

ФС	ОС	Журнал	Макс. размер файла	CoW	Особенности
ext4	Linux	Да (метаданные + опц. данные)	16 ТБ	Нет	Стандарт Linux, extents, обратная совместимость
XFS	Linux	Да (метаданные)	8 ЭБ	Нет	Высокая производительность, масштабируемость
Btrfs	Linux	Да	16 ЭБ	Да	Снапшоты, RAID, сжатие, контрольные суммы данных
NTFS	Windows	Да	16 ЭБ (теор.)	Нет	ACL, шифрование (EFS), сжатие, альтернативные потоки
APFS	macOS, iOS	Да	~8 ЭБ	Да	Клонирование, снапшоты, шифрование, оптимизация для SSD
FAT32	Все	Нет	4 ГБ	Нет	Универсальная совместимость, флешки, SD-карты

10.2. Ключевые понятия

Журналирование (journaling): перед записью изменений на диск ФС записывает намерения в специальный журнал. При сбое журнал позволяет восстановить согласованное состояние, избегая длительной проверки (fsck/chkdsk).
Копирование при записи (Copy-on-Write, CoW): при изменении данных блок не перезаписывается «на месте», а копируется в новое место, затем обновляется указатель. Это обеспечивает атомарность и позволяет дешёво создавать снапшоты (мгновенные снимки состояния).

11. Ссылки: жёсткие и символические

11.1. Жёсткая ссылка (hard link)

Жёсткая ссылка — это дополнительная запись в каталоге, указывающая на тот же inode, что и оригинальный файл. По сути, это просто ещё одно имя для тех же данных.

Счётчик ссылок в inode увеличивается на 1.
Файл физически удаляется только когда счётчик ссылок становится равен 0.
Ограничения: нельзя создавать жёсткие ссылки на каталоги (во избежание циклов), нельзя создавать через границы файловых систем (разные ФС — разные таблицы inode).

11.2. Символическая ссылка (symbolic link, symlink)

Символическая ссылка — это отдельный файл, содержащий путь к целевому файлу или каталогу.

Имеет собственный inode.
Может указывать на файлы в других файловых системах.
Может указывать на каталоги.
Если целевой файл удалён, ссылка становится «повисшей» (dangling symlink).

11.3. Сравнение

Свойство	Жёсткая ссылка	Символическая ссылка
Собственный inode	Нет (разделяет с оригиналом)	Да (свой inode)
Через границы ФС	Нет	Да
На каталоги	Нет (как правило)	Да
При удалении оригинала	Данные сохраняются	Ссылка «повисает»
Содержимое	Те же блоки данных	Путь к цели

Аналог в Windows: NTFS hard links и symbolic links (доступны с Windows Vista/2008). В macOS также поддерживаются оба типа, причём APFS поддерживает особый механизм — firmlinks (для системных томов).

12. Права доступа

12.1. Модель Unix (DAC — Discretionary Access Control)

Каждый файл имеет три набора разрешений для трёх категорий субъектов:

Категория	Описание
Owner (u)	Владелец файла
Group (g)	Группа, к которой принадлежит файл
Other (o)	Все остальные пользователи

Каждый набор содержит три бита:

Бит	Буква	Для файла	Для каталога
read	r (4)	Чтение содержимого	Просмотр списка файлов
write	w (2)	Изменение содержимого	Создание/удаление файлов
execute	x (1)	Запуск как программы	Переход в каталог (cd)

Пример: rwxr-xr-- (754) — владелец может всё, группа — читать и выполнять, остальные — только читать.

Дополнительные биты: SUID, SGID, sticky bit — расширяют модель для специальных сценариев (запуск с правами владельца, наследование группы, защита файлов в общих каталогах).

12.2. ACL (Access Control Lists)

Классическая модель Unix ограничена тремя категориями. ACL позволяют задавать индивидуальные права для произвольных пользователей и групп.

В Linux: POSIX ACL (команды getfacl, setfacl).
В Windows (NTFS): ACL — основной механизм управления доступом. Каждый объект имеет Security Descriptor с DACL (discretionary) и SACL (аудит).
В macOS: поддерживаются расширенные ACL поверх стандартной Unix-модели.

12.3. RBAC (Role-Based Access Control)

RBAC — модель, в которой права назначаются не конкретным пользователям, а ролям. Пользователь получает набор ролей, а роль определяет набор разрешений.

Широко применяется в корпоративных системах, серверных ОС, облачных платформах (AWS IAM, Kubernetes RBAC).
Упрощает администрирование: при смене должности сотрудника достаточно изменить его роли.
В SELinux (Linux) и AppArmor реализованы элементы MAC (Mandatory Access Control), которые дополняют DAC и RBAC.

12.4. Сравнение моделей

Модель	Гибкость	Сложность	Где применяется
Unix rwx	Низкая	Минимальная	Базовая модель во всех Unix-подобных ОС
ACL	Высокая	Средняя	NTFS, POSIX ACL в Linux/macOS
RBAC	Очень высокая	Высокая	Корпоративные системы, облака, Kubernetes

13. Пользователи, группы и принцип наименьших привилегий

13.1. Пользователи и группы

Во всех современных ОС существует система учётных записей:

Linux/macOS: пользователи хранятся в /etc/passwd, группы — в /etc/group. Суперпользователь — root (UID 0).
Windows: учётные записи управляются через SAM (Security Accounts Manager) или Active Directory. Суперпользователь — Administrator.

Группы позволяют объединять пользователей и назначать общие права на ресурсы, что значительно упрощает администрирование.

13.2. Принцип наименьших привилегий (Principle of Least Privilege)

Каждый субъект (пользователь, процесс, сервис) должен иметь только те права, которые минимально необходимы для выполнения его задач.

Примеры реализации в разных ОС:

Linux: обычная работа от непривилегированного пользователя, sudo для разовых операций, capabilities для дробления прав root.
Windows: механизм UAC (User Account Control) — даже администратор по умолчанию работает с ограниченными правами; повышение требует явного подтверждения.
macOS: аналогичная модель — по умолчанию процессы работают без root; для привилегированных операций запрашивается пароль.
Контейнеры и облака: каждый контейнер работает с минимальным набором capabilities; в Kubernetes — SecurityContext, PodSecurityPolicy.

13.3. Системные пользователи и демоны

Помимо «человеческих» учётных записей, ОС содержит системных пользователей (например, www-data, nobody, daemon в Linux; SYSTEM, NETWORK SERVICE в Windows). Каждый системный сервис работает под отдельным пользователем с минимальными правами — это ограничивает ущерб при компрометации.

14. Вопросы для самопроверки

Перечислите уровни иерархии памяти от самого быстрого к самому медленному. Объясните, почему нельзя использовать только один тип памяти.
В чём разница между физическим и виртуальным адресом? Какой компонент выполняет трансляцию?
Чем отличается внутренняя фрагментация от внешней? Приведите примеры ситуаций, в которых они возникают.
Опишите процесс трансляции виртуального адреса в физический при страничной организации. Какую роль играет TLB?
Дана последовательность обращений к страницам: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 при 3 фреймах. Сколько page fault произойдёт при алгоритмах FIFO и LRU?
Что хранится в inode? Почему имя файла не входит в inode?
Сравните ext4 и NTFS по трём критериям: журналирование, максимальный размер файла, механизм хранения метаданных.
Чем жёсткая ссылка отличается от символической? Почему нельзя создать жёсткую ссылку на файл в другой файловой системе?
Объясните модель прав доступа Unix (rwx). Какие ограничения у этой модели, и как их преодолевает ACL?
Что такое принцип наименьших привилегий? Приведите примеры его реализации в Linux и Windows.