swap в программировании что это
Функция SWAP в языке С: что это и как работает
Функция SWAP в С
Для простой реализации функции SWAP в Си из стандартной библиотеки можно воспользоваться следующим шаблоном:
// после выполнения программы результат будет таким: x = 9, y = 8
Функция SWAP в С может применяться и в более сложных конструкциях, например:
int a=100, b=200; //присваиваем значения переменным: a=100, b=200
std::swap(a,b); // функция swap меняет значения переменных: a=200, b=100
std::vector foo (2,a), bar (3,b) //проводим операции: foo:2×200 bar:3×100
std::swap(foo, bar); //swap меняет значения операций: foo:3×100 bar:2×200
for (std::vector ::iterator it=foo.begin(); it!=foo.end(); ++it)
После выполнени я э та программ а нам выдаст следующий результат:
foo содержит: 100 100 100
Функция SWAP в С работает не только с числами, но и с другими типами данных, например со строками:
using namespace std;
string b = “Программирование“;
Результат выполнения такой программы будет следующий:
Значение переменной «а» до применения функции SWAP: Функция
Значение переменной «b» до применения функции SWAP: Программирование
Значение переменной «а» после применения функции SWAP: Программирование
Значение переменной «b» после применения функции SWAP: Функция
Заключение
Функция SWAP в С работает с любыми типами данных. Чтобы она сработала, у переменных обязательно должно быть какое-то значение. Она ничего не возвращает, а просто меняет местами значения переменных.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
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*) элементам вектора строк.
Приёмы неблокирующего программирования: введение в 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). Стоит иметь это в виду, ведь если ваш код выполняется достаточно редко, то на медленную часть можно не особо обращать внимание, добавить туда мьютекс и превратить много читателей/писателей в одного (в один момент времени), что может значительно упростить вам жизнь, расширив количество применимых шаблонов неблокирующего программирования.
Механизм Swapping — угроза или паранойя?
Доброго времени суток %username%.
Подготавливая в очередной раз оборудования, ПО и помещение к прохождению аттестации на разные там «конфи» и «перс данные», мне показалось странным что такая область работы ОС как организация Свопинга ни кем, или ни чем не защищается.
Немного взгляда изнутри. Википедия дает довольно сбалансированное определение данному термину:
Свопинг
Один из механизмов реализации виртуальной памяти, при котором отдельные запущенные процессы (обычно неактивные) перемещаются из ОЗУ на жёсткий диск, освобождая ОЗУ для загрузки других процессов. Основное отличие этого механизма от страничного заключается в том, что процессы перемещаются между ОЗУ и жестким диском целиком, поэтому иногда некоторые процессы могут полностью отсутствовать в ОЗУ. При наступлении условий активизации процесса он возвращается диспетчером памяти в ОЗУ. Существуют различные алгоритмы выбора процессов на загрузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.
Все хорошо, еще из жизни мы знаем что своп может быть размещен на дисках в виде файлов (т.е. подчиняться драйверам файловой системы) или же занимать отдельное выделенное место на устройстве, чаще всего в виде выделенного раздела (так называемого раздела подкачки).
Угроза
Исходя из механизма организации свопинга можно утверждать, что ОС руководствуясь неведомыми алгоритмами, переносит неиспользуемые, или ниже приоритетные области памяти на дисковые устройства. После чего освободившиеся области памяти отдает другим процессам. Предположим, что на компьютере ведется работа с важной информации, которая храниться в защищенном виде, на защищенном компьютере и в защищенном помещении. Для работы с данными необходимо приложение, которое снимает защиту на момент ручной или автоматизированной обработки, назовем это — расшифровывание. После расшифровывания данные обрабатываются в «открытом виде».
Если в этот момент ОС решит засвопить рабочий процесс, то все переменные в которых и хранятся данные попадут на устройства хранения в открытом виде. Мало того, закрытые ключи использовавшиеся для расшифровки данных, при неправильном программировании и не использовании специальных носителей информации, так же могу оказаться в свопе.
Ну а дальше дело техники:
Вариант №1. Выключаем компьютер — забираем устройство — копируем своп — возвращаем все назад.
Вариант №2. На ОС настроено удаление совп файла при завершении работы. Нашел такое только в Windows 2008 Server R2. В Linux нашел команду swapoff, не уверен что она делает именно это. При таких условиях жмем — Reset.
Вариант №3. Снимаем образ Acronis’ом.
Полученный файл или область диска изучаем имеющимися у нас способами.
Выключать своп реально не хочется, т.к. действия пользователя в течении дня не предсказуемы. Если есть какие либо мысли или ответы — очень буду рад.
Ну из рекомендации можно посоветовать только пока:
Панель упр.->Система->Дополнительно->Быстродействие->Параметры->
Дополнительно->Виртульная память->Изменить->Без файла подкачки->OK.
Лично я встречал только один носитель информации в описании которого есть такая фраза:
Возможности Rutoken ЭЦП позволяют осуществлять механизм электронной цифровой подписи так, чтобы закрытый (секретный) ключ подписи никогда не покидал пределы токена. Таким образом, исключается возможность компрометации ключа и увеличивается общая безопасность информационной системы.
Это моя первая статья на Хабре, так что не бейте по яндексам.