Управление оперативной памятью держится на одном простом наблюдении: программа обращается к данным неравномерно. Небольшая часть страниц используется постоянно, остальное лежит без дела. Алгоритм LRU, то есть вытеснение самого давно не использованного элемента, превращает это наблюдение в правило: когда свободного места нет, первым кандидатом на удаление становится страница, к которой дольше всего никто не прикасался. На бумаге идея выглядит почти очевидной, однако между формулой и работающим ядром стоит немало инженерных компромиссов. Этот материал разбирает, как LRU превратился из теоретической конструкции в набор практических механизмов, которыми операционные системы пользуются каждую миллисекунду.
Идея выдавливать давно не использованное
Классическая постановка задачи такова. Память разбита на страницы фиксированного размера, обычно четыре килобайта. Набор страниц, которые ядро готово держать в оперативной памяти, ограничен, и когда появляется новая страница, кому-то приходится уступить место. LRU предлагает выбирать жертву по принципу наибольшей давности последнего обращения. Логика апеллирует к временнóй локальности: если страница была нужна недавно, с высокой вероятностью она понадобится снова, а если её не трогали долго, скорее всего, она уже отработала своё.
Свойство этой стратегии хорошо изучено. Для неё доказана конкурентная оценка: на любой последовательности обращений LRU допускает не более чем в k раз больше промахов, чем идеальный предсказывающий алгоритм, где k это размер кэша. Никакой другой детерминированный онлайн алгоритм не гарантирует лучшего отношения. Именно поэтому LRU стал эталоном, с которым сравнивают всё остальное, от кэшей процессоров до серверов-посредников.
Но у красивой теории есть весьма материальная цена. Строгий LRU требует после каждого обращения к странице обновить глобальный порядок давности. Для оперативной памяти компьютера это означает вмешательство в миллионы обращений в секунду, и такая бухгалтерия обошлась бы дороже самой работы программ.
Почему точный стек LRU невозможен в ядре
Точная реализация LRU хранит все страницы в виде стека или двусвязного списка. При каждом чтении или записи соответствующий элемент нужно вытащить из середины и положить на вершину. В кэше базы данных, где обращения проходят через код самой базы, это допустимо: накладные расходы растворяются в стоимости запроса. В ядре операционной системы ситуация иная: обращение к памяти выполняет процессор напрямую, без участия какого-либо кода.
Чтобы перехватывать обращения, пришлось бы либо ставить ловушку на каждую инструкцию чтения, что замедлило бы всё в десятки раз, либо требовать аппаратных счётчиков времени в каждой строке таблицы страниц, а разработчики процессоров такую роскошь не предоставляют. Поэтому ядра операционных систем давно отказались от точного LRU и живут на приближениях, которые использую единственный доступный дешёвый источник информации о давности.
Этим источником служит бит обращения, access bit, который процессор автоматически устанавливает в записи таблицы страниц, PTE, при любом чтении или записи страницы. Один бит не скажет, когда страницу трогали, но он честно отвечает, трогали ли её с тех пор, как ядро последний раз бит сбрасывало. Из этой скромной основы и вырастают все практические замены LRU.
Алгоритм часов и право второго шанса
Самое известное приближение носит название second chance, или алгоритм часов. Страницы расположены по кругу, а воображаемая стрелка обходит их по очереди. Попадая на страницу, алгоритм смотрит на бит обращения. Если бит установлен, страница недавно использовалась: ядро сбрасывает бит и даёт ей второй шанс, двигаясь дальше. Если бит снят, значит за полный оборот стрелки к странице никто не прикасался, и она становится жертвой.
Полиtics поведения стрелки определяет частоту опроса. Слишком частый обход превращает алгоритм в случайный выбор, потому что бит не успевает установиться. Слишком редкий оставляет память грязной и тормозит выделение. Практические варианты привязывают скорость стрелки к дефициту свободных страниц: пока запаса хватает, стрелка почти стоит, при нехватке она ускоряется. Есть и усовершенствование с битом модификации: грязные страницы, требующие записи на диск, целесообразно вытеснять позже чистых, которые можно просто отбросить.
Дальнейшее развитие этой идеи можно видеть в многоуровневых схемах наподобие Clock-Pro или связки активного и неактивного списков в Linux. Там страница проходит испытательный срок в холодной зоне и переходит в тёплую только после повторного обращения, что отсекает одноразовые чтения и приближает поведение к стеку LRU почти без стоимости.
Страничные списки Windows и рабочие наборы
Windows устроила эти идеи в несколько именованных списков, каждый из которых представляет состояние страницы. Активные страницы входят в рабочие наборы процессов или системы и отображены в таблицах страниц. Когда менеджер памяти решает их выселить, страница сначала попадает в список standby, из которого её можно мгновенно вернуть без чтения с диска, потому что содержимое пока цело. Изменённые страницы оседают в списке modified и ждут, пока поток записи сбросит их в файл подкачки или отображённый файл. Дальше идут списки free и zeroed: первый хранит освобождённые страницы, второй страницы, уже заполненные нулями и готовые к выдаче процессу без задержки.
Над всем этим работает механизм рабочих наборов и trimming. У каждого процесса есть квота на число страниц в памяти. Когда системе не хватает места, она начинает отбирать страницы у процессов, превысивших квоту, и у тех, кого не трогали дольше всех. Процесс этого не замечает: его виртуальные адреса остаются на месте, просто при следующем обращении к вытесненной странице случается ошибка страницы, и ядро возвращает её обратно, зачастую прямо из standby без участия диска.
Standby при этом выполняет вторую, менее заметную роль тайного кэша. Раз содержимое страниц в нём сохраняется, система использует список как хранилище вероятно нужных данных. Служба SysMain, в прошлом SuperFetch, следит за историей запуска приложений и заранее подгружает их страницы в standby в моменты простоя. Утренний запуск почты или браузера после такой подготовки обходится почти без диска, хотя формально страницы числятся вытесненными.
Разумный человек может наблюдать эту механику инструментами наподобие RAMMap: там видно, сколько памяти сидит в каждом списке и как standby раздувается после активной работы. Освобождение standby происходит мгновенно, поэтому большой объём этого списка говорит не о проблеме, а о том, что система запаслась данными на будущее.
Дисковые эффекты и почему SSD перевернули картину
Ошибки страниц бывают мягкими и жёсткими. Мягкая ошибка разрешается внутри памяти: страница находится в standby, в рабочем наборе другого процесса или в кэше, и ядро просто перенастраивает таблицу. Жёсткая ошибка, hard fault, требует чтения с диска, из файла подкачки или отображённого файла. Именно жёсткие ошибки исторически определяли ощущение от нехватки памяти: на механическом диске одно обращение стоит около десяти миллисекунд, и серия таких ошибок превращала систему в застывшую картинку.
Твердотельные накопители изменили расклад кардинально. Случайное чтение с SSD занимает десятки микросекунд, то есть раз в сто быстрее, чем у жёсткого диска. Жёсткая ошибка перестала быть катастрофой и стала заметной, но терпимой паузой. Это позволило ядру гораздо спокойнее относиться к урезанию рабочих наборов и держать меньше жирного запаса памяти. Современные системы буквально рассчитаны на то, что подкачка лежит на SSD: пользователь с распухшим браузером чувствует лёгкое промедление там, где раньше наблюдалось многоминутное стояние.
Дальше по этой логике пошло сжатие памяти. Начиная с Windows 10, система при нехватке места отчасти заменяет запись в файл подкачки упаковкой страниц в особую область: вместо похода на диск страницу сжимают и оставляют в оперативной памяти. Распаковка занимает доли микросекунды, что дешевле даже SSD. В диспетчере задач этот объём виден как строка о сжатой памяти в разделе использования. Файл подкачки никуда не делся, он принимает страницы, которые долго никому не нужны или плохо жмутся, но его роль заметно сократилась. Linux движется по соседней тропе через zswap и zram, где сжатый кэш вытесненных страниц живёт в оперативной памяти и держит диск в стороне.
Отдельного упоминания заслуживает счётчик жёстких ошибок в мониторах производительности. Показатель hard faults per second давно служит диагностическим индикатором нехватки памяти, однако на системах с SSD его интерпретацию пришлось пересмотреть: сотни таких ошибок в секунду, ранее означавшие полный паралич, сегодня проходят почти незамеченными. Администраторы научились смотреть не столько на сам счётчик, сколько на задержки диска и долю сжатой памяти, потому что именно они честно показывают, насколько системе реально тесно.
Вкладки, OOM и выбор жертвы на уровне приложений
Когда память заканчивается совсем, вопрос перестаёт быть вопросом вытеснения страниц и становится вопросом выбора между жертвами. Пользователю это знакомо в форме дилеммы: закрыть вкладку самому или дождаться, пока система позовёт механизм OOM killer, который в Linux оценивает процессы по взвешенной сумме занятой памяти и приоритета и завершает крупнейшего нарушителя. Решение грубое, но предсказуемое, и параметры oom_score_adj позволяют защитить критичные службы.
Браузеры свели ту же задачу к более изящной форме. Они замечают, что вкладка давно не активна, сериализуют её состояние и выгружают содержимое из памяти, оставляя на панели лишь обложку. Когда пользователь возвращается, вкладка восстанавливается. По сути это прикладной LRU, реализованный поверх собственных знаний о жизненном цикле страниц: браузеру известно, какие вкладки спят, и он вытесняет их раньше, чем ядро начнёт резать страницы наугад. Сайты через API событий видимости могут подготовиться к выгрузке и сохранить состояние формы или позицию прокрутки.
Сходные приёмы используют мобильные платформы, где фоновые приложения вытесняются по давности почти без участия пользователя. Общая закономерность проста: чем ближе к приложению принимается решение, тем точнее оно отражает реальную ценность данных, а не одну лишь статистику обращений.
Слепые зоны LRU и сканирующие нагрузки
У приятеля у LRU есть и известный провал - сканирующая нагрузка. Одноразовое полное чтение массива данных, будь то резервное копирование, антивирусный обход или загрузка целого диска, проходит по каждой странице ровно один раз. Формально каждая такая страница становится самой недавно использованной и вытесняет из кэша действительно горячие данные, хотя повторного обращения к ней не случится никогда. LRU в этом сценарии работает против здравого смысла: после бэкапа система остаётся с кэшем, забитым копиями бэкапа, и вынуждена заново прогревать память рабочими данными.
Бороться с этим помогают подсказки об одноразовости. Приложение может пометить поток как последовательный и одноразовый, и ядро сразу отправит его страницы в холодную часть списка, не дав им вытеснить горячие. В Windows для этого служит флаг FILE_FLAG_SEQUENTIAL_SCAN при открытии файла, в Linux подсказки дают вызовы posix_fadvise и madvise. В самих накопителях существует похожая идея под именем Dataset Management: хост сообщает контроллеру SSD, какие блоки больше не нужны или каков характер доступа, и прошивка настраивает внутренний кэш и сборку мусора соответственно. На уровне блочных устройств и сетевых хранилищ тоже расходятся схемы сегментированного LRU и адаптивной замены ARC, где списки недавних и частых страниц разведены, и одиночное сканирование не может затопить всё хранилище.
Всё это вместе рисует честный портрет алгоритма. LRU остаётся опорной идеей, но работающая система строится из поправок к нему: биты обращения вместо точных времен, двойные списки вместо одного стека, сжатие вместо диска, подсказки от приложений против слепых сканирований. Теория задала направление, а практика довела его до механизма, который незаметно перетасовывает гигабайты каждые несколько секунд и при этом остаётся дешёвле одного обращения к памяти.