Виртуальная память и файловые системы

Страничная организация памяти, таблица страниц и TLB, алгоритмы замещения страниц, пробуксовка, устройство файловых систем FAT, NTFS, ext4, журналирование.

Виртуальная память решает две задачи сразу: позволяет запускать программы, которым нужно больше памяти, чем есть физически, и изолирует процессы друг от друга. Файловая система делает то же для дискового пространства.

Виртуальные и физические адреса

Каждый процесс видит собственное непрерывное адресное пространство.
Преобразование адреса выполняет блок управления памятью (MMU):

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

При размере страницы 4 КБ смещение занимает 12 бит (2¹² = 4096).
Для 32-разрядного адреса на номер страницы остаётся 20 бит → 1 048 576 страниц.

Таблица страниц хранит соответствие «номер виртуальной страницы → номер физического кадра» плюс биты состояния: присутствия, изменения (dirty), обращения, прав доступа.

Буфер трансляции TLB

Обращение к таблице страниц в памяти удвоило бы время каждого доступа. Поэтому последние преобразования кэшируются в TLB — небольшой ассоциативной памяти внутри процессора.

Среднее время доступа:

  t = h·(t_TLB + t_память) + (1 − h)·(t_TLB + 2·t_память)

h — доля попаданий в TLB, на практике 0,98…0,99

Пример: t_TLB = 1 нс, t_память = 100 нс, h = 0,98
  t = 0,98·101 + 0,02·201 = 99 + 4 = 103 нс
  Накладные расходы всего 3 % вместо двукратного замедления.

Отказ страницы и подкачка

1. Процесс обращается к адресу, страница которого не загружена в память.
2. MMU обнаруживает сброшенный бит присутствия и вызывает прерывание — page fault.
3. Операционная система находит свободный кадр; если свободных нет, выбирает жертву алгоритмом замещения.
4. Если страница-жертва изменялась (бит dirty), её записывают в файл подкачки.
5. Нужная страница читается с диска в освободившийся кадр, таблица обновляется.
6. Команда, вызвавшая отказ, выполняется повторно.

Пробуксовка

Если процессам суммарно не хватает памяти, система начинает тратить почти всё время на подкачку: страница вытесняется и тут же требуется снова. Загрузка процессора падает, диск работает непрерывно — это состояние называют пробуксовкой (thrashing).

• Причина — сумма рабочих наборов процессов превышает объём физической памяти.
• Рабочий набор — страницы, к которым процесс обращался за последний интервал времени.
• Решение: снизить степень многозадачности, выгрузив часть процессов целиком, либо добавить памяти.
• Внешне проявляется как «система зависла, но диск шумит» — при заполненном ОЗУ и активном свопе.

Файловые системы

Как хранится файл

• Непрерывное размещение: быстрый доступ, но фрагментация свободного пространства и невозможность роста файла.
• Связный список кластеров (FAT): нет внешней фрагментации, зато произвольный доступ требует прохода по цепочке.
• Индексное размещение (inode в ext4, MFT в NTFS): таблица блоков файла, произвольный доступ за одно обращение.
• Экстенты: вместо перечисления блоков хранят диапазоны «начало плюс длина» — компактнее для больших файлов.

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

Файл 5 КБ при размере кластера 4 КБ занимает 2 кластера = 8 КБ
Потеряно 3 КБ, то есть 37 %

10 000 мелких файлов по 1 КБ при кластере 4 КБ
→ занято 40 МБ вместо 10 МБ

Отсюда выбор: крупный кластер быстрее для больших файлов,
мелкий экономнее для множества маленьких.

Журналирование

Запись файла состоит из нескольких операций: обновить данные, изменить размер, поправить время. Сбой питания между ними оставит файловую систему в противоречивом состоянии. Журнал решает проблему: сначала намерение записывается в журнал, затем выполняется, затем запись из журнала удаляется. После сбоя система по журналу либо докатывает, либо откатывает незавершённую операцию.

Права доступа и связи

ls -l
# -rw-r--r--  1 user group  1024 Aug 17 10:00 report.txt
#  ↑↑↑ ↑↑↑ ↑↑↑
#  владелец / группа / остальные

chmod 644 report.txt      # rw- r-- r--
chmod 755 script.sh       # rwx r-x r-x
chmod u+x script.sh       # добавить право выполнения владельцу

ln    original.txt hard.txt    # жёсткая ссылка: тот же inode
ln -s original.txt soft.txt    # символическая: отдельный файл с путём

stat report.txt           # inode, размер, время доступа и изменения
df -h                     # свободное место
du -sh /var/log           # размер каталога

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