Swap что это в программировании
Механизм Swapping — угроза или паранойя?
Доброго времени суток %username%.
Подготавливая в очередной раз оборудования, ПО и помещение к прохождению аттестации на разные там «конфи» и «перс данные», мне показалось странным что такая область работы ОС как организация Свопинга ни кем, или ни чем не защищается.
Немного взгляда изнутри. Википедия дает довольно сбалансированное определение данному термину:
Свопинг
Один из механизмов реализации виртуальной памяти, при котором отдельные запущенные процессы (обычно неактивные) перемещаются из ОЗУ на жёсткий диск, освобождая ОЗУ для загрузки других процессов. Основное отличие этого механизма от страничного заключается в том, что процессы перемещаются между ОЗУ и жестким диском целиком, поэтому иногда некоторые процессы могут полностью отсутствовать в ОЗУ. При наступлении условий активизации процесса он возвращается диспетчером памяти в ОЗУ. Существуют различные алгоритмы выбора процессов на загрузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.
Все хорошо, еще из жизни мы знаем что своп может быть размещен на дисках в виде файлов (т.е. подчиняться драйверам файловой системы) или же занимать отдельное выделенное место на устройстве, чаще всего в виде выделенного раздела (так называемого раздела подкачки).
Угроза
Исходя из механизма организации свопинга можно утверждать, что ОС руководствуясь неведомыми алгоритмами, переносит неиспользуемые, или ниже приоритетные области памяти на дисковые устройства. После чего освободившиеся области памяти отдает другим процессам. Предположим, что на компьютере ведется работа с важной информации, которая храниться в защищенном виде, на защищенном компьютере и в защищенном помещении. Для работы с данными необходимо приложение, которое снимает защиту на момент ручной или автоматизированной обработки, назовем это — расшифровывание. После расшифровывания данные обрабатываются в «открытом виде».
Если в этот момент ОС решит засвопить рабочий процесс, то все переменные в которых и хранятся данные попадут на устройства хранения в открытом виде. Мало того, закрытые ключи использовавшиеся для расшифровки данных, при неправильном программировании и не использовании специальных носителей информации, так же могу оказаться в свопе.
Ну а дальше дело техники:
Вариант №1. Выключаем компьютер — забираем устройство — копируем своп — возвращаем все назад.
Вариант №2. На ОС настроено удаление совп файла при завершении работы. Нашел такое только в Windows 2008 Server R2. В Linux нашел команду swapoff, не уверен что она делает именно это. При таких условиях жмем — Reset.
Вариант №3. Снимаем образ Acronis’ом.
Полученный файл или область диска изучаем имеющимися у нас способами.
Выключать своп реально не хочется, т.к. действия пользователя в течении дня не предсказуемы. Если есть какие либо мысли или ответы — очень буду рад.
Ну из рекомендации можно посоветовать только пока:
Панель упр.->Система->Дополнительно->Быстродействие->Параметры->
Дополнительно->Виртульная память->Изменить->Без файла подкачки->OK.
Лично я встречал только один носитель информации в описании которого есть такая фраза:
Возможности Rutoken ЭЦП позволяют осуществлять механизм электронной цифровой подписи так, чтобы закрытый (секретный) ключ подписи никогда не покидал пределы токена. Таким образом, исключается возможность компрометации ключа и увеличивается общая безопасность информационной системы.
Это моя первая статья на Хабре, так что не бейте по яндексам.
9.2.5. Присвоение и функция swap()
Связанные с присвоением операторы, перечисленные в табл. 9.4, воздействуют на весь контейнер. Оператор присвоения заменяет весь диапазон элементов в левом контейнере копиями элементов из правого:
c1 = c2; // заменяет содержимое контейнера c1 копией
// элементов контейнера c2
c1 =
После первого присвоения контейнеры слева и справа равны. Если контейнеры имели неравный размер, после присвоения у обоих будет размер контейнера из правого операнда. После второго присвоения размер контейнера c1 составит 3, что соответствует количеству значений, представленных в списке.
Таблица 9.4. Операторы присвоения контейнеров
c1 = c2 Заменяет элементы контейнера c1 копиями элементов контейнера c2. Контейнеры c1 и c2 должны иметь тот же тип с =
В отличие от встроенных массивов, библиотечный тип array поддерживает присвоение. У левых и правых операндов должен быть одинаковый тип:
array а2 = <0>; // все элементы со значением 0
a1 = а2; // замена элементов в a1
а2 = <0>; // ошибка: нельзя присвоить массиву значения из списка
Поскольку размер правого операнда может отличаться от размера левого операнда, тип array не поддерживает функцию assign() и это не позволяет присваивать значения из списка.
Связанные с присвоением операторы делают недопустимыми итераторы, ссылки и указатели на контейнер слева.
Применение функции assign() (только последовательные контейнеры)
Оператор присвоения требует совпадения типов левых и правых операндов. Он копирует все элементы правого операнда в левый. Последовательные контейнеры (кроме array) определяют также функцию-член assign(), обеспечивающую присвоение разных, но совместимых типов, или присвоение контейнерам последовательностей. Функция assign() заменяет все элементы в левом контейнере копиями элементов, указанных в ее аргументе. Например, функцию assign() можно использовать для присвоения диапазона значений char* из вектора в список строк:
names = oldstyle; // ошибка: типы контейнеров не совпадают
// ok: преобразование из const char* в string возможно
Вызов функции assign() заменяет элементы в контейнере names копиями элементов из диапазона, обозначенного итераторами. Аргументы функции assign() определяют количество элементов контейнера и их значения.
Поскольку существующие элементы заменяются, итераторы, переданные функции assign(), не должны относиться к контейнеру, для которого вызвана функция assign().
Вторая версия функции assign() получает целочисленное значение и значение элемента. Она заменяет указанное количество элементов контейнера заданным значением:
// сопровождается slist1.insert(slist1.begin(), 10, «Hiya!»);
list slist1(1); // один элемент; пустая строка
slist1.assign(10, «Hiya!»); // десять элементов; со значением «Hiya!»
Применение функции swap()
Функция swap() меняет местами значения двух контейнеров того же типа. Типы контейнеров и их элементов должны совпадать. После обращения к функции swap() элементы правого операнда оказываются в левом, и наоборот:
vector svec1(10); // вектор из 10 элементов
vector svec2(24); // вектор из 24 элементов
После выполнения функции swap() вектор svec1 содержит 24 строки, а вектор svec2 — 10. За исключением массивов смена двух контейнеров осуществляется очень быстро — сами элементы не меняются; меняются лишь внутренние структуры данных.
За исключением массивов функция swap() не копирует, не удаляет и не вставляет элементы, поэтому она гарантированно выполняется за постоянное время.
Благодаря тому факту, что элементы не перемещаются, итераторы, ссылки и указатели в контейнере, за исключением контейнера string, остаются допустимыми. Они продолжают указывать на те же элементы, что и перед перестановкой. Однако после вызова функции swap() эти элементы находятся в другом контейнере. Предположим, например, что итератор iter обозначал в векторе строк позицию svec1[3]. После вызова функции swap() он обозначит элемент в позиции svec2[3]. В отличие от других контейнеров, вызов функции swap() для строки делает некорректными итераторы, ссылки и указатели.
В отличие от поведения функции swap() с другими контейнерами, когда дело доходит до массивов, элементы действительно обмениваются. Обмен двух массивов потребует времени, пропорционального количеству их элементов.
После выполнения функции swap(), указатели, ссылки и итераторы остаются связанными с тем же элементом, который они обозначили ранее. Конечно, значение самого элемента заменено значением соответствующего элемента другого массива.
Новая библиотека предоставляет функцию swap() в версии члена класса контейнера и в версии, не являющейся членом какого-либо класса. Прежние версии библиотеки определили только версию функции-члена swap(). Функция swap() не являющаяся членом класса контейнера, имеет большое значение в обобщенных программах. Как правило, лучше использовать именно эту версию.
Упражнения раздела 9.2.5
Упражнение 9.14. Напишите программу, присваивающую значения элементов списка указателей на символьные строки в стиле С (тип char*) элементам вектора строк.
В защиту swap’а [в Linux]: распространенные заблуждения
Прим. перев.: Эта увлекательная статья, в подробностях раскрывающая предназначение swap в Linux и отвечающая на распространённое заблуждение на этот счёт, написана Chris Down — SRE из Facebook, который, в частности, занимается разработкой новых метрик в ядре, помогающих анализировать нагрузку на оперативную память. И начинает он своё повествование с лаконичного TL;DR…
Предисловие
Работая над улучшением и использованием cgroup v2, я успел поговорить со многими инженерами об их отношении к управлению памяти, особенно о поведении приложения под нагрузкой и об эвристическом алгоритме операционной системы, используемым «под капотом» для управления памятью.
Повторяющейся темой этих обсуждений стал swap. Тема swap активно оспаривается и плохо понимается даже теми, кто проработал с Linux долгие годы. Многие воспринимают его как нечто бесполезное или очень вредное — мол, это пережиток прошлого, когда памяти было мало и диски являлись необходимым злом, предоставляющим столь нужное пространство для подкачки. И до сих пор, все последние годы, я достаточно часто наблюдаю споры вокруг этого утверждения: немало дискуссий провёл и я сам с коллегами, друзьями, собратьями по индустрии, помогая им понять, почему swap — это по-прежнему полезная концепция на современных компьютерах, имеющих гораздо больше физической памяти, чем в былые времена.
Широкое недопонимание существует и насчёт предназначения swap’а: многие люди видят в нём лишь «медленную дополнительную память» для использования в критических ситуациях, но не понимают его вклад в адекватное функционирование операционной системы в целом при нормальной нагрузке.
Многие из нас слышали такие распространённые фразы о памяти: «Linux использует слишком много памяти», «swap должен быть вдвое больше размера физической памяти» и т.п. Эти заблуждения легко развеять и их обсуждения стали более точными в последние годы, однако миф о «бесполезном» swap гораздо больше завязан на эвристику и таинство, которые не поддаются объяснению с простой аналогией, — для его обсуждения требуется более глубокое понимание управления памятью.
Введение
Сложно говорить, почему наличие swap’а и перемещение в него страниц памяти — хорошо при нормальной работе, не разделяя понимание некоторых базовых нижележащих механизмов в управлении памятью в Linux, поэтому давайте убедимся, что говорим на одном языке.
Типы памяти
В Linux существует множество различных типов памяти, и у каждого из этих типов есть свои свойства. Понимание их особенностей — ключ к пониманию, почему swap важен.
Например, есть страницы («блоки» памяти, обычно по 4k), ответственные за хранение кода для каждого процесса, запущенного на компьютере. Есть также страницы, ответственные за кэширование данных и метаданных, относящихся к файлам, к которым обращаются эти программы для ускорения своих обращений в будущем. Они являются частью страничного кэша [page cache], и далее я буду на них ссылаться как на файловую [file] память.
Есть и другие типы памяти: разделяемая память, slab-память, память стека ядра, буферы и иные, — но анонимная память и файловая память известны лучше других и просты для понимания, поэтому именно они будут использоваться в примерах, которые, впрочем, равносильно применимы и к другим типам.
Память с высвобождением и без
В размышлениях о конкретном типе памяти одним из главных вопросов становится возможность её высвобождения. «Высвобождение» [reclaim] означает, что система может, без потери данных, удалить страницы этого типа из физической памяти.
Для некоторых типов страниц это сделать весьма просто. Например, в случае чистой [clean], т.е. немодифицированной, памяти страничного кэша мы просто кэшируем для лучшей производительности то, что уже есть на диске, поэтому можем сбросить страницу без необходимости в каких-либо специальных операциях.
Для некоторых типов страниц это возможно, но непросто. Например, в случае грязной [dirty], т.е. модифицированной, памяти страничного кэша мы не можем просто сбросить страницу, потому что на диске ещё нет произведённых модификаций. Поэтому необходимо или отказаться от высвобождения [reclamation], или перенести наши изменения обратно на диск перед тем, как сбрасывать эту память.
Для некоторых типов страниц это невозможно. Например, упомянутые раньше анонимные страницы могут существовать только в памяти и никаком ином резервном хранилище, поэтому их необходимо хранить здесь (т.е. в самой памяти).
О природе swap’а
Если поискать объяснения, зачем нужен swap в Linux, неизбежно находятся многочисленные обсуждения его предназначения просто как расширения физической RAM для критических случаев. Вот, например, случайный пост, который я вытащил из первых результатов в Google по запросу «what is swap»:
«По своей сути swap — это экстренная память; запасное пространство для случаев, когда система на какое-то время нуждается в большем количестве физической памяти, чем доступно в RAM. Она считается «плохой» в том смысле, что медленная и неэффективная, и если системе постоянно требуется использовать swap, очевидно, ей не хватает памяти. [..] Если у вас достаточно RAM для удовлетворения всех потребностей и вы не ожидаете её превышения, вы можете прекрасно работать и без swap-пространства».
Поясню, что я вовсе не обвиняю автора этого комментария за содержимое его поста — это «общеизвестный факт», признаваемый многими системными администраторами Linux и являющийся, пожалуй, одним из наиболее вероятных ответов на вопрос о swap’е. К сожалению, это вдобавок и неправильное представление о предназначении и использовании swap’а, особенно на современных системах.
Как я уже писал выше, высвобождение анонимных страниц «невозможно», поскольку анонимные страницы по своей природе не имеют резервного хранилища, к которому можно обратиться при удалении данных из памяти, — таким образом, их высвобождение приведёт к полной утере данных из соответствующих страниц. Однако… что будет, если мы смогли бы создать такое хранилище для этих страниц?
Вот именно для этого и существует swap. Swap — область хранения для этих, кажущихся «невысвобождаемыми» [unreclaimable], страниц, позволяющая отправлять их на устройство хранения по запросу. Это означает, что их можно начинать считать такими же доступными для высвобождения, как и их более простые в этом смысле друзья (вроде чистых файловых страниц), что позволяет эффективнее использовать свободную физическую память.
Swap — это преимущественно механизм для равного высвобождения, а не для срочной «дополнительной памяти». Не swap замедляет работу вашего приложения — замедление происходит из-за начала совокупной конкуренции за память.
Итак, в каких же ситуациях это «равное высвобождение» будет оправданно выбирать высвобождение анонимных страниц? Вот абстрактные примеры некоторых не самых редких сценариев:
Что происходит с использованием swap и без него
Давайте посмотрим на типовые ситуации и к чему они приводят при наличии и отсутствии swap. О метриках «конкуренции за память» я рассказываю в докладе про cgroup v2.
Без конкуренции или с малой конкуренцией за память
С умеренной или высокой конкуренцией за память
При временных всплесках в потреблении памяти
Окей, я хочу системный swap, но как его настроить для конкретных приложений?
Вы же не думали, что в этой статье не будет упоминаний использования cgroup v2?
И в этом вопросе нельзя просто положиться на OOM killer. Потому что OOM killer вызывается только в самых критичных ситуациях, когда система уже оказалась в значительно нездоровом состоянии и, возможно, находилась в нём некоторое время. Необходимо самостоятельно и оппортунистически разрешить ситуацию ещё до того, как задумываться об OOM killer’е.
Тем не менее, выявить давление на память достаточно трудно с помощью традиционных счётчиков памяти в Linux. Нам доступно нечто, что каким-то образом относится к проблеме, однако скорее по касательной: потребление памяти, количество операций сканирования страниц и т.п. — и по одним этим метрикам очень трудно отличить эффективную конфигурацию памяти от той, что приводит к конкуренции за память. У нас есть группа в Facebook, возглавляемая Johannes’ом и работающая над новыми метриками, упрощающими демонстрацию давления на память, — это должно помочь нам в будущем. Больше информации об этом можно получить из моего доклада про cgroup v2, где я начинаю подробнее рассказывать об одной из метрик.
Тюнинг
Сколько же swap’а мне тогда нужно?
В общем случае минимальное количество swap-пространства, требуемого для оптимального управления памятью, зависит от количества анонимных страниц, которые привязаны к пространству памяти и к которым редко обращается приложение, а также от стоимости высвобождения этих анонимных страниц. Последнее — это в большей степени вопрос о том, какие страницы больше не должны удаляться, чтобы уступить место тем анонимным страницам, к которым редко обращаются.
Если у вас достаточно дискового пространства и свежее (4.0+) ядро, большее количество swap’а почти всегда лучше, чем меньшее. В более старых ядрах kswapd — один из процессов ядра, что отвечает за управление swap’ом, — исторически слишком усердствовал в перемещении памяти в swap, делая это тем активнее, чем больше swap’а было доступно. В последнее время поведение swapping’а при наличии большого swap-пространства значительно улучшили. Так что, если вы работаете с ядром 4.0+, большой swap не приведёт к чрезмерному swapping’у. В общем, на современных ядрах нормально иметь swap размером в несколько гигабайт, если такое пространство у вас есть.
Если же дисковое пространство ограничено, ответ в действительности зависит от компромисса, на который вы готовы пойти, и особенностей окружения. В идеале у вас должно быть достаточно swap’а, чтобы система оптимально функционировала при нормальной и пиковой (по памяти) нагрузке. Рекомендую настроить несколько тестовых систем с 2-3 Гб swap’а или более и понаблюдать, что происходит на протяжении недели или около того в разных условиях нагрузки (на память). Если на протяжении этой недели не случалось ситуаций резкой нехватки памяти, что означает недостаточную пользу такого теста, всё закончится занятостью swap’а небольшим количеством мегабайт. В таком случае, пожалуй, разумно будет иметь swap хотя бы такого размера с добавлением небольшого буфера для меняющихся нагрузок. Также atop в режиме логирования в столбце SWAPSZ может показать, страницы каких приложений попадают в swap. Если вы ещё не используете эту утилиту на своих серверах для логирования истории состояний сервера — возможно, в эксперимент стоит добавить её настройку на тестовых машинах (в режиме логирования). Заодно вы узнаете, когда приложение начало перемещать страницы в swap, что можно привязать к событиям из логов или другим важным показателям.
Ещё стоит задуматься о типе носителя для swap’а. Чтение из swap имеет тенденцию быть очень случайным, поскольку нельзя уверенно предсказать, у каких страниц будет отказ и когда. Для SSD это не имеет особого значения, а вот для вращающихся дисков случайный ввод/вывод может оказаться очень дорогим, поскольку требует физических движений. С другой стороны, отказы у файловых страниц обычно менее случайны, поскольку файлы, относящиеся к работе одного запущенного приложения, обычно менее фрагментированы. Это может означать, что для вращающегося диска вы можете захотеть сместиться в сторону высвобождения файловых страниц вместо swapping’а анонимных страниц, но, опять же, необходимо протестировать и оценить, как будет соблюдаться баланс для вашей рабочей нагрузки.
Для пользователей ноутбуков/десктопов, желающих использовать swap для перехода в спящий режим [hibernate], этот факт также необходимо учитывать, поскольку swap-файл тогда должен как минимум соответствовать размеру физической оперативной памяти.
Какой должна быть настройка swappiness?
Это означает, что vm.swappiness — это по существу просто соотношение дорогой анонимной памяти, которую можно высвобождать и приводить к отказам, в сравнении с файловой памятью для вашего железа и рабочей нагрузки. Чем ниже значение, тем активнее вы сообщаете ядру, что редкие обращения к анонимным страницам дороги для перемещения в swap и обратно на вашем оборудовании. Чем выше это значение, тем вы больше говорите ядру, что стоимость swapping’а анонимных и файловых страниц одинакова на вашем оборудовании. Подсистема управления памятью будет по-прежнему пытаться решить, помещать в swap файловые или анонимные страницы, руководствуясь тем, насколько «горяча» память, однако swappiness склоняет подсчёт стоимости в пользу большего swapping’а или большего пропуска кэшей файловой системы, когда доступны оба способа. На SSD-дисках эти подходы практически равны по стоимости, поэтому установка vm.swappiness = 100 (т.е. полное равенство) может работать хорошо. На вращающихся дисках swapping может быть значительно дороже, т.к. в целом он требует случайного чтения, поэтому вы скорее всего захотите сместиться в сторону меньшего значения.
Реальность же в том, что большинство людей не имеют представления о том, чего требует их железо, поэтому настроить это значение, основываясь лишь на инстинкте, затруднительно — это вопрос, требующий личного тестирования с разными значениями. Можно также заняться анализом состава памяти вашей системы, основных приложений и их поведения в условиях небольшого высвобождения памяти.
Приёмы неблокирующего программирования: введение в compare-and-swap
В первой части этого цикла статей мы рассмотрели теорию, стоящую за одновременным доступом в моделях памяти, а также применение этой теории к простым чтениям и записям в память. Правда, этих примитивов оказывается недостаточны для построения высокоуровневых механизмов синхронизации вроде спинлоков, мьютексов и условных переменных. Хоть и полные барьеры памяти позволяют синхронизировать потоки с помощью приёмов, рассмотренных в предыдущей части (алгоритм Деккера), современные процессоры позволяют получить нужный эффект проще, быстрее и гибче — да, всё сразу! — с помощью операций compare-and-swap.
Для программистов ядра Linux операция обмена compare-and-swap выглядит так:
где T может быть либо числовым типом не больше указателя, либо указателем на что-нибудь. Так как в C нет обобщённых функций, то подобный полиморфизм реализуется макросами. cmpxchg() — это очень аккуратно реализованный макрос, который ведёт себя как функция (например, вычисляет аргументы только один раз). В Linux также есть макрос cmpxchg64(), который работает с 64-битными целыми числами и недоступен на 32-битных платформах.
cmpxchg() читает значение по указателю *ptr и, если оно равно old, то заменяет его на new. Иначе же после чтения ничего не происходит. Считанное значение возвращается как результат операции, независимо от того, произошла ли запись. И всё это выполняется атомарно: если другой поток одновременно с cmpxchg() записывает что-то по адресу *ptr, то cmpxchg() ничего не меняет. Либо old становится new, либо текущее значение остаётся нетронутым. Поэтому cmpxchg() называют атомарной операцией read-modify-write.
В ядре Linux cmpxchg() также предоставляет окружающему коду гарантии порядка операций с памятью. Для выполнения атомарного обмена значений требуется и читать, и писать в память. С некоторыми оговорками можно считать, что чтение здесь имеет acquire-семантику, а запись — это release-операция. То есть cmpxchg() будет синхронизироваться с load-acquire и store-release операциями в других потоках.
Стеки и очереди без блокировок
Статья «Lockless algorithms for mere mortals» рассказывает, как compare-and-swap позволяет работать со списками без мьютексов — с подробным разбором и иллюстрациями. Здесь же мы ограничимся рассмотрением односвязного списка в качестве примера: как его реализовать на C, где он может пригодиться. Начнём с простого: как добавляется элемент в начало односвязного списка.
Как мы теперь знаем, присваивание “first” следует выполнять release-операцией, чтобы другие потоки увидели “node->next” после выполнения load-acquire. Хорошо, пока всё идёт по плану и шаблону из первой статьи.
Однако, такой простой код корректно работает лишь для случая, когда ровно один поток может модифицировать список. Если таких потоков-писателей может быть несколько, то уже оба присваивания должны быть защищены критической секцией. В противном случае, если какой-то другой поток изменяет значение first (добавляет элемент, например), то node->next в свежедобавленном элементе может указывать на старое значение first и один элемент списка окажется утерян. Из этого следует важный урок: корректное использование acquire и release-семантики — это необходимое, но отнюдь не достаточное условие корректности неблокирующих алгоритмов. Сами по себе они не защищают вас от логических ошибок и гонок потоков.
К счастью, в данной ситуации вместо блокировки можно воспользоваться cmpxchg(), чтобы поймать ситуацию, когда какой-то другой поток изменил first первым. Следующий код будет корректным уже для любого числа потоков-писателей:
И тут возникают вопросы. Во-первых, что же делать, когда cmpxchg() заметит изменения в first? В нашем случае ответ простой: считать новое значение, обновить node->next, попробовать добавить node в список ещё раз. Это новый элемент, который пока ещё не видно из других потоков. Если нам не повезло с добавлением — никто ничего не заметит.
Второй вопрос гораздо более хитрый: как именно в таком случае следует считывать first? По идее нам не нужна acquire или release-семантика, ведь нас волнует только значение first само по себе. С другой стороны, слишком умный оптимизирующий компилятор может подумать, что раз мы ничего не присваиваем first в этом потоке, то значение не могло измениться и ничего повторно читать из памяти не нужно. Хоть cmpxchg() в Linux и запрещает подобные оптимизации, хорошим тоном считается явно показывать с помощью READ_ONCE(), что мы хотим считать новое значение из памяти.
Улучшенная версия кода выглядит так:
Отлично, добавление в список работает. Перейдём к другой стороне проблемы: как следует забирать значения из этого списка. Зависит из того, чего мы хотим добиться, передавая значения через список, сколько потоков будут из него читать, и в каком порядке они хотят это делать: LIFO или FIFO, от новых элементов к старым или наоборот.
Самый простой случай — это когда все чтения из списка гарантированно происходят после записей. Доступ к списку синхронизируется каким-нибудь другим образом, так что при чтении список уже не изменяется и обычные, не атомарные операции полностью безопасны. Например, если читатели запускаются после писателей, дождавшись завершения потоков, которые собирают список дальнейшей работы, как было в первой статье.
Если читателей много, но им не особо важен порядок элементов в списке — например, пул рабочих потоков, где каждый поток хочет взять себе работы — то для этого достаточно всего одной инструкции:
xchg() подобно cmpxchg() атомарно выполняет одновременно чтение и запись в память. В данном случае читает и возвращает старое значение first, всегда записывая вместо него NULL. То есть переносит значение first в my_tasks. Здесь используется вариант xchg_acquire(), придающий acquire-семантику чтению из памяти, но при этом запись выполняется просто атомарно, без release-семантики (подобно WRITE_ONCE()). Тут достаточно лишь acquire-семантики, потому что release-половинка находится в другом месте (у писателей). В целом, это всё тот же приём из первой части, только расширенный на случай более чем двух потоков.
Можно ли при этом заменить cmpxchg() у писателя на cmpxchg_release() — с записью через release, но обычным чтением? По идее так можно сделать, ведь писателю важно только то, чтобы его запись в “node->next” была видна другим потокам. Однако, acquire-семантика чтения у cmpxchg() имеет полезный побочный эффект: так каждый следующий писатель синхронизируется с предыдущими писателями. Вызовы cmpxchg() упорядочиваются благодаря парам acquire и release-операций:
Только cmpxchg() из третьего потока синхронизирована с xchg_acquire() в четвёртом потоке. Однако благодаря транзитивности, все другие cmxchg() происходят перед xchg_acquire(). Если писатели используют cmpxchg(), то после xchg_acquire() по списку можно пройти уже с помощью обычных операций чтения.
Если бы писатели использовали cmpxchg_release(), то отношения порядка между потоками выглядели бы так:
Четвёртый поток конечно же прочитает node2 из node3->next, потому что он уже прочитал значение first, которое записал третий поток. Но вот для последующих элементов списка наблюдаемый порядок записей других потоков уже не гарантируется — при использовании обычных операций чтения — поэтому четвёртому потоку требуется использовать smp_load_acquire() для прохода по списку, чтобы точно увидеть node1 при чтении node2->next.
Конечно же односвязные списки давно реализованы в ядре Linux — linux/llist.h — поэтому можно не переизобретать колесо и пользоваться готовыми решениями. Теперь обратим внимание на ещё пару интересных функций: llist_del_first() и llist_reverse_order().
llist_del_first() вынимает и возвращает первый элемент списка. Документация предупреждает, что эта функция безопасна только для единственного читателя. Если несколько потоков одновременно забирают элементы списка, то при определённом стечении обстоятельств возможна так называемая проблема ABA. Я не буду вдаваться здесь в детали, просто не надо так делать. Возникает ситуация, похожая на предыдущий пример с rwlock: для корректной работы алгоритма в целом необходимо пользоваться блокировками, но определённые части могут обойтись без них. llist_del_first() позволяет любому количеству писателей добавлять элементы в список с помощью llist_add() без каких-либо блокировок, но если читателей несколько, то они между собой должны пользоваться мьютексом или спинлоком.
llist_del_first() превращает список в LIFO-контейнер (стек). Если же вам требуется FIFO-порядок (очередь), то можно воспользоваться следующим приёмом с llist_reverse_order(). Если забирать элементы из списка пачками с помощью xchg() (или же llist_del_all()), то пачки сохраняют FIFO-порядок между собой, только элементы в них следуют в обратном порядке. Воу, а что если.
Таким образом можно забирать элементы из списка в порядке их поступления, подобно очереди. Как и в случае с llist_del_first(), это работает только если элементы current_batch обрабатываются одним потоком. Полная реализация этого алгоритма с помощью API llist оставляется читателю в качества упражнения.
На этом у меня пока всё. В следующей части мы продолжим изучать атомарные read-modify-write операции, посмотрим, что ещё можно сделать с compare-and-swap и как её можно использовать для ускорения счётчиков ссылок.
Дейв Чиннер — один из основных сопровождающих XFS и Btrfs — оставил замечательный комментарий касательно производительности cmpxchg().
Есть пара достаточно важных моментов про неблокирующие алгоритмы, использующие cmpxchg. Они как бы подразумеваются в статье, но явно не рассматриваются. cmpxchg определяется как «атомарная операция read-modify-write», что технически корректно, но умалчивает некоторые ограничения масштабирования, с которыми сталкиваются «неблокирующие» алгоритмы на основе cmpxchg.
Поэтому большинство алгоритмов в ядре выходят из цикла cmpxchg() после некоторого числа неудач, а потом переходят к плану Б: скажем, захватывают спинлок, чтобы избежать негативных последствий высокой нагрузки на cmpxchg. Например, dentry-кеш использует механизм lockref (lockref_get/lockref_put), который прекращает крутить цикл cmpxchg() после 100 неудачных попыток.
Dentry-кеш ускоряет работу с именами файлов, чтобы ядро не бегало каждый раз в файловую систему заново. Например, если вы открываете только что созданный файл, то он наверняка будет в dentry-кеше и ядру не придётся лишний раз перепроверять, что все промежуточные директории существуют.
Чтобы вы примерно себе представляли, когда конфликты за кеш-линии становятся проблемой (при достижении протоколом когерентности кешей точки насыщения), на моей машине нагрузка на процессор перестаёт линейно расти где-то при 2,5–3 миллионах операций в секунду, если взять простой цикл с cmpxchg() для 64-битного значения на своей собственной кеш-линии, где больше ничего не происходит. Это в 32 потока на машине двухлетней давности с 32 ядрами. Они не прям под завязку нагружены, но если попрофайлить конкретный цикл, создавая 650000 файлов в секунду, то можно наблюдать, как суммарно этот цикл начинает занимать вполне значимое количество ресурсов: единицы процентов процессорного времени.
Если сравнить со спинлоками, то при похожей нагрузке приблизительно треть времени тратится только на то, чтобы крутить спинлоки. Конкретно, если посмотреть на спинлок, защищающий список inode в суперблоке файловой системы, то при 2,6 миллионах доступов в секунду на спинлоки уходит около 10% процессорных ресурсов (то есть 3 из 32 процессоров). Очень похоже на cmpxchg, который начинает тупить где-то в этом же районе, и если подумать, как оба варианта обращаются с кешем, то наблюдаемое поведение вполне логично.
Другими словами, cmpxchg() масштабируется лучше, чем блокирующие алгоритмы, но это не волшебная таблетка, делающая всё быстрее. У cmpxchg() тоже есть пределы масштабируемости, так как это не вполне неблокирущая операция. Впрочем, мой опыт проектирования многопоточных алгоритмов подсказывает, что масштабируемость зависит больше от того, насколько часто алгоритму требуется читать или обновлять разделяемые данные, а не от того, насколько «(не)блокирующий» алгоритм используется. Мьютекс — это ж фактически просто атомарный флажок «захвачено» и немного оптимизаций. Так что неудивительно, что cmpxchg() и атомарные примитивы имеют схожие ограничения в масштабируемости с блокировками — фундаментально, если посмотреть с точки зрения кеша, все эти подходы об одном и том же. Просто cmpxchg() и атомарные операции дают более тонкий контроль над памятью, уменьшая частоту одновременного доступа к данным. Отсюда и выгода: если меньше трогать общую память, то можно делать больше независимой работы.
Искусство многопоточного программирования во многом завязано на понимание того, как алгоритмы работают с памятью. Недостаточно лишь примерно представлять, как работают неблокирующие алгоритмы — нужно чётко понимать, что именно они делают с памятью и когда упираются в пределы своих возможностей. Естественно, знать, когда не нужно использовать неблокирующие алгоритмы вовсе, потому что есть другие способы распараллелить работу — это тоже искусство 🙂
Дейв, огромное спасибо за ответ. Прям в корень зришь — я сомневался, стоит ли вообще рассказывать о связных списках, во многом из-за описанных тобой причин. С одной стороны, связные списки — это прямо классический пример неблокирущих структур данных. С другой стороны, они не настолько широко применимы, как другие вещи, о которых я рассказываю, вот как раз из-за ограничений в масштабируемости. Нет, у связных списков есть своя ниша, но их слишком легко использовать там, где не надо. Например, в тех немногих случаях, когда мне были нужны именно llist, я принял такое решение не потому, что неблокирующее добавление в список — это круто (нет, это прикольно, но у него проблемы с распределением работы между процессорами при повышенной нагрузке). Наоборот, я знал, что писателей будет немного и записи будут редкими, а вот читатель будет лишь один и его хотелось сделать как можно более быстрым. Я бы не назвал это очевидным решением задачи.
В конце концов я всё же рассказал о связных списках, потому что из них выходит хороший пример — и что более важно, закономерно возникает вопрос, когда лучше применять именно неблокирующие алгоритмы.
Вообще я хотел раскрыть эту тему в заключительной части (может теперь передумаю 🙂 но раз такое дело… Чему я хочу научить людей этими статьями, так это с одной стороны не бояться применять неблокирующие алгоритмы: их можно свести к некоторому множеству понятных шаблонов и абстракций — это не тайная магия, доступная лишь избранным. С другой стороны, неблокирующие алгоритмы — это лишь инструмент, один из подходов к решению задач. Часто гораздо более важным моментом оказывается читабельность и простота поддержки кода.
Чтобы добиться максимальной производительности, вам необходимо знать относительную частоту записей и чтений (или распределение работы между быстрой и медленной частями алгоритма). Иначе вы ж понятия не имеете, где у вас могут возникнуть проблемы с масштабируемостью. Неблокирующие алгоритмы — это всегда компромисс (моя история с llist служит примером, но пожалуй наиболее известный пример — это RCU). Стоит иметь это в виду, ведь если ваш код выполняется достаточно редко, то на медленную часть можно не особо обращать внимание, добавить туда мьютекс и превратить много читателей/писателей в одного (в один момент времени), что может значительно упростить вам жизнь, расширив количество применимых шаблонов неблокирующего программирования.