Набор патчей LRU с несколькими поколениями - это значительная переработка подсистемы управления памятью ядра, которая обещает лучшую производительность для ряда рабочих нагрузок; о ней мы писали здесь в апреле. С тех пор разработчиком Ю Чжао были выпущены две новые версии этой работы, причем версия 3 была опубликована 20 мая. С момента публикации первоначального сообщения произошли некоторые значительные изменения, поэтому стоит еще раз взглянуть на нее.
Вкратце напомним: современные ядра ведут два списка наименее недавно использованных страниц памяти (LRU), которые называются "активный" и "неактивный" списки. Первый содержит страницы, которые, как считается, активно используются, а второй содержит страницы, которые, как считается, не используются и могут быть использованы для других целей; достаточно много усилий уходит на то, чтобы решить, когда перемещать страницы между этими двумя списками. Многопоколенная LRU обобщает эту концепцию на несколько поколений, позволяя страницам находиться в состоянии между "вероятно активными" и "вероятно неиспользуемыми". Страницы переходят из старших поколений в новые при обращении к ним; когда память нужна, страницы освобождаются из самого старого поколения. Поколения стареют с течением времени, при этом новые поколения создаются по мере того, как старые поколения полностью освобождаются.
Многоуровневый, многопоколенный LRU
Пожалуй, самым большим изменением с момента первой публикации этой работы является концепция "уровней", которая используется для разделения поколений страниц, что, в свою очередь, облегчает принятие решений о том, какие страницы следует восстанавливать, особенно в системах, где происходит много буферизованного ввода-вывода. В частности, уровни - это способ сортировки страниц в поколении по частоте обращений - но только обращений, осуществляемых через файловые дескрипторы. Когда страница впервые попадает в поколение, она обычно попадает в уровень 0. Если какой-то процесс обращается к этой странице через файловый дескриптор, счетчик использования страницы увеличивается, и она переходит в уровень 1. Дальнейшие обращения к странице будут продвигать ее на более высокие уровни; фактический номер уровня - это логарифм базы-2 счета использования.
Прежде чем рассмотреть, как используются эти уровни, стоит спросить, почему они управляются таким образом - почему учитываются только доступы на основе файловых дескрипторов? Одна из возможных причин не упоминается ни в наборе патчей, ни в обсуждении, но кажется правдоподобной: доступ через файловый дескриптор происходит в результате системного вызова, и его относительно легко и дешево подсчитать. Прямые доступы к памяти со стороны процессора более дорогостоящи и не могут быть отслежены с таким же разрешением.
Другая причина, однако, заключается в том, что этот механизм позволяет внести некоторые изменения в то, как происходит старение страниц, поступающих через ввод-вывод. В современных ядрах страница, которая попадает в память в результате, скажем, вызова read(), сначала добавляется в список неактивных. Это имеет смысл, поскольку эта страница часто никогда больше не будет использоваться. Однако если к странице будет другой доступ, она станет активной, и ядро постарается избежать ее повторного использования. Этот механизм работает лучше, чем его предшественники, но все еще существует возможность того, что процессы, выполняющие много операций ввода-вывода, могут вымыть полезные страницы из активного списка, что снижает производительность системы.
Для улучшения ситуации необходимо использовать существующее в ядре отслеживание теневых страниц. Когда страницы освобождаются для другого использования, ядро на некоторое время запоминает, что содержали эти страницы и когда старое содержимое было вытеснено. Если в ближайшем будущем к одной из этих страниц снова обратятся, что потребует ее возврата из вторичного хранилища, ядро заметит этот "отказ", который является сигналом о том, что активно используемые страницы возвращаются. Как правило, сбои указывают на трэшинг, что не очень хорошо. Ядро может отреагировать на чрезмерное количество отказов, например, увеличив активный список.
Работа LRU с несколькими поколениями настраивает теневые записи для записи того, на каком уровне находилась страница, когда она была восстановлена. Если страница была повреждена, она может быть восстановлена на предыдущем уровне, но повреждение также может быть учтено в связи с этим уровнем. Это позволяет вычислить коэффициент отказов для каждого уровня - какой процент страниц, возвращаемых с этого уровня, впоследствии возвращается обратно в память? Кажется очевидным, что отказов на страницах более высоких уровней - тех, к которым обращаются чаще - вообще стоит избегать.
Эта информация об отказах используется путем сравнения частоты отказов на более высоких уровнях с частотой отказов на уровне 0, который содержит страницы, к которым CPU обращается напрямую, и страницы, к которым вообще не обращались. Если на более высоких уровнях частота отказов выше, чем на уровне 0, то страницы на этих уровнях перемещаются в более молодое поколение и таким образом защищаются (на некоторое время) от восстановления. Это приводит к тому, что возврат направляется на те типы страниц, на которых происходит меньше отказов.
Другая часть головоломки заключается в том, что код управления памятью больше не продвигает страницы автоматически при втором доступе на основе файлового дескриптора, как это делается в современных ядрах. Вместо этого страницы, полученные в результате ввода-вывода, остаются в старом поколении, если только они не были перемещены в результате использования в уровень, на котором отказы происходят чаще, чем на страницах с прямым доступом. Это, как объяснил Чжао в этом длинном сообщении, имеет эффект предотвращения вытеснения этими страницами страниц с прямым доступом, которые используются более интенсивно. Это должно повысить производительность систем, выполняющих много буферизованного ввода-вывода; это замечание Йенса Аксбо (Jens Axboe) предполагает, что это действительно помогает.
Еще одним изменением по сравнению с первой версией является добавление пользовательского регулятора для принудительного удаления одного или нескольких поколений. Цель этой функции, по-видимому, состоит в том, чтобы позволить контроллерам заданий освободить некоторое пространство для входящей работы; этот патч документации содержит немного больше информации.
Несколько поколений патчей
Работа над LRU с несколькими поколениями остается многообещающей, и она вызвала достаточно большой интерес. Однако ее путь в основное ядро все еще выглядит долгим и трудным. Йоханнес Вайнер поднял вопрос, который упоминался и в первой статье: многопоколенная LRU, как она реализована сейчас, находится рядом с существующим кодом управления памятью в качестве отдельной опции, по сути, предоставляя ядру два механизма возврата страниц. Это всегда будет трудно продать по причинам, описанным Вайнером:
Невозможно поддерживать оба механизма, сконцентрировать ресурсы разработки и тестирования и обеспечить достаточно стабильную работу обеих систем, работающих на сложной общей кодовой базе.
Таким образом, новый код должен заменить существующую систему, что очень непросто. Нужно будет показать, что он работает лучше (или, по крайней мере, не хуже) практически при любой рабочей нагрузке, причем на таком уровне уверенности, который мотивировал бы замену кода, имеющего "миллиарды часов производственного тестирования и настройки". Единственный способ сделать это - объединить изменения в виде серии небольших эволюционных шагов. Таким образом, набор исправлений LRU, рассчитанный на несколько поколений, должен быть разбит на ряд изменений, ни одно из которых не является настолько большим, чтобы разработчики управления памятью не сочли возможным их безопасное слияние.
На протяжении многих лет ядро впитывало огромные изменения таким образом, но это не быстрый и не простой процесс. Вейнер предложил несколько областей, на которых можно сосредоточиться, чтобы начать работу над частью этой работы и облегчить рассмотрение остальных. Если следовать этому совету, то некоторый прогресс в объединении LRU с несколькими поколениями может быть достигнут в относительно ближайшем будущем. Но эта функциональность в целом, вероятно, должна пройти через множество поколений правок, прежде чем все это попадет в основное ядро.
https://lwn.net/Articles/856931/