Shared memory что это
Разделяемая память
Разделяемую память (англ. Shared memory ) применяют для того, чтобы увеличить скорость прохождения данных между процессами. В обычной ситуации обмен информацией между процессами проходит через ядро. Техника разделяемой памяти позволяет осуществить обмен информацией не через ядро, а используя некоторую часть виртуального адресного пространства, куда помещаются и откуда считываются данные.
После создания разделяемого сегмента памяти любой из пользовательских процессов может подсоединить его к своему собственному виртуальному пространству и работать с ним, как с обычным сегментом памяти. Недостатком такого обмена информацией является отсутствие каких бы то ни было средств синхронизации, однако для преодоления этого недостатка можно использовать технику семафоров.
Примерный сценарий использования разделяемой памяти при реализации технологий «клиент—сервер» имеет вид:
Для работы с разделяемой памятью используются системные вызовы:
В схеме обмена данными между двумя процессами — (клиентом и сервером), использующими разделяемую память, — должна функционировать группа из двух семафоров. Первый семафор служит для блокирования доступа к разделяемой памяти, его разрешающий сигнал — 1, а запрещающий — 0. Второй семафор служит для сигнализации сервера о том, что клиент начал работу, при этом доступ к разделяемой памяти блокируется, и клиент читает данные из памяти. Теперь при вызове операции сервером его работа будет приостановлена до освобождения памяти клиентом.
Реализация разделяемой памяти между драйвером и приложением
Приветствую всех!
В этой небольшой статье речь пойдет об одном способе создания разделяемой памяти, к которой можно будет обращаться как из режима ядра, так и из пользовательского режима. Приведу примеры функций выделения и освобождения памяти, а также будут ссылки на исходники, чтобы можно было попробовать любому желающему.
Драйвер собирался под 32-битную ОС Windows XP (так же проверял его работу и
в 32-битной Windows 7).
Полностью описывать разработку драйвера, начиная с установки WDK(DDK), выбора инструментов разработки, написания стандартных функций драйвера и т.д., я не буду (при желании можно почитать вот и вот, хотя там тоже не много информации). Чтобы статья не получилась слишком раздутой, опишу только способ реализации разделяемой памяти.
Немного теории
Драйвер не создает специального программного потока для выполнения своего кода, а выполняется в контексте потока, активного на данный момент. Поэтому считается, что драйвер выполняется в контексте произвольного потока (Переключение контекста). Очень важно, чтобы при отображении выделенной памяти в пользовательское адресное пространство, мы находились в контексте потока приложения, которое будет управлять нашим драйвером. В данном случае это правило соблюдается, т.к. драйвер является одноуровневым и обращаемся мы к нему с помощью запроса IRP_MJ_DEVICE_CONTROL, следовательно контекст потока не будет переключаться и мы будем иметь доступ к адресному пространству нашего приложения.
Выделение памяти
разбор функции по частям:
Сохраняем указатель, с помощью которого передадим указатель на выделенную память нашему приложению:
Следующий шаг — выделение неперемещаемой физической памяти размером memory_size и построение на ее основе структуру MDL (Memory Descriptor List), указатель на которую сохраняем в переменной pdx->mdl:
Как видно из изображения, структура MDL нам нужна для описания зафиксированных физических страниц.
Затем получаем диапазон виртуальных адресов для MDL в системном адресном пространстве и сохраняем указатель на эти адреса в переменной pdx->kernel_va:
Эта функция возвратит указатель, по которому мы сможем обращаться к выделенной памяти в драйвере (причем независимо от текущего контекста потока, т.к. адреса получены из системного адресного пространства).
В цикле запишем первые 10 ячеек памяти числами от 10 до 1, чтобы можно было проверить доступность выделенной памяти из пользовательского режима:
Теперь необходимо отобразить выделенную память в адресное пространство приложения, которое обратилось к драйверу:
Переменная pdx->vaReturned является указателем на указатель и объявляется в структуре pdx (см. driver.h в папке source_driver). С помощью нее передадим указатель pdx->user_va в приложение:
Освобождение памяти
Здесь происходит освобождение адресного пространства приложения:
ситемного адресного пространства:
затем освобождаются физические страницы:
Обращаемся к драйверу из пользовательского режима
(Весь код приложения смотрите в прилагаемых материалах)
Первое, что необходимо сделать, это получить манипулятор устройства (handle) с помощью функции CreateFile():
Затем необходимо отправить запрос ввода/вывода драйверу с помощью функции DeviceIoControl():
Вызов функции преобразуется в IRP пакет, который будет обрабатываться в диспетчерской функции драйвера (см. DispatchControl() в файле control.cpp драйвера). Т.е. при вызове DeviceIoControl() управление передастся функции драйвера, код которой выше был описан. Так же, при вызове функции DeviceIoControl() в программе DebugView (надо галочку поставить, чтобы она отлавливала события режима ядра) увидим следующее:
По возвращению управления приложению переменная vaReturned будет указывать на разделяемую память (точнее будет указывать на указатель, который уже будет указывать на память). Сделаем небольшое упрощение, чтобы получить обычный указатель на память:
Теперь по указателю data мы имеем доступ к разделяемой памяти из приложения:
При нажатии на кнопку «Allocate memory» приложение передает управление драйверу, который выполняет все действия, описанные выше, и возвращает указатель на выделенную память, доступ к которой из приложения будет осуществляться через указатель data. Кнопкой «Fill TextEdit» выводим содержимое первых 10-и элементов, которые были заполнены в драйвере, в QTextEdit и видим успешное обращение к разделяемой памяти.
При нажатии на кнопку «Release memory» происходит освобождение памяти и удаление созданной структуры MDL.
Исходники
За основу драйвера (source_driver) я взял один из примеров у Уолтера Они (примеры прилагаются к его книге «Использование Microsoft Windows Driver Model»). Так же необходимо скачать библиотеку ядра Generic, т.к. эта библиотека нужна как при сборке, так и при работе драйвера.
Тем, кто хочет попробовать сам
Создаем директорию (н-р, C:\Drivers) и распаковываем туда исходники (source_driver, source_generic_oney и source_app). Если не будете пересобирать драйвер, то достаточно установить новое оборудование вручную (указав inf-файл: sharedmemory.inf) через Панель управления-установка нового оборудования (для Windows XP). Затем надо запустить habr_app.exe (source_app/release).
Если решите пересобирать, то:
1. Необходимо установить WDK.
2. Сначала нужно будет пересобрать библиотеку Generic, т.к. в зависимости от версии ОС папки с выходными файлами могут по разному называться (н-р, для XP — objchk_wxp_x86, для Win7 — objchk_win7_x86).
3. После 1 и 2 пункта можно пробовать собрать драйвер командой «build» с помощью x86 Checked Build Environment, входящую в WDK.
Понимание конфликтов банков разделяемой (shared) памяти в NVIDIA CUDA
Как возникают конфликты разделяемой памяти
Конфликты возникают, когда 2 или более потоков из одного варпа (warp) (для устройств версии 2.0) или половины варпа (для устройстве версии 1.3 и ниже) осуществляют доступ к байтам, которые принадлежат разным 32 битным словам, находящимся в одном банке памяти. В случае конфликта доступ осуществляется последовательно. Количество потоков, обращающихся к банку, называется степенью конфликта. Если степень конфликта N, то доступ осуществляется в N раз медленнее, чем если бы конфликта не было.
Механизм широковещательного доступа
На устройствах версии 1.x конфликта можно избежать, если несколько потоков осуществляют доступ к одному и тому же слову, принадлежащему одному и тому же банку, и только если этот запрос одиночный — в данном случае задействуется механизм широковещательного доступа.
На устройствах версии 2.x таких запросов может быть несколько и осуществятся они будут параллельно (разные потоки могут осуществлять доступ к разным байтам слова).
Особенности доступа на устройствах версии 2.0
При 64 битном доступе конфликт банков возникает только если 2 или более потоков из любой из половин варпа осуществляют доступ по адресам, принадлежащим одному и тому же банку.
При 128 битном доступе как правило возникают конфликты банков второй степени.
Доступ разрядностью больше, чем 32 разбивается на запросы разрядностью 32, 64 и 128 бит.
Как память распределяется по банкам
Память распределяется по банкам таким образом, что каждое 32 битное слово в последовательности, последовательно назначается одному из 32 банков случае устройства версии 2.0 и 16 банков в случае устройства версии 1.3 и ниже. Соответственно номер банка можно рассчитать по следующей формуле:
Номер банка = (Адрес в байтах/4)%32 — для устройства версии 2.0
Номер банка = (Адрес в байтах/4)%16 — для устройства версии 1.x
Примеры доступа к памяти, вызывающие конфликты
Для устройств версии 1.x
1. 8 и 16 битный доступ
__shared__ char shmem8[32];
char data = shmem8[threadIdx.x];
В данном примере первые 4 байта находятся в одном банке, поэтому первые 4 потока будут конфликтовать при доступе
Проблема решается добавлением избыточных данных (padding) и изменение схемы доступа:
__shared__ char shmem8[32*4];
char data = shmem8[threadIdx.x*4];
Для 16-битного доступа:
__shared__ short shmem16[32];
short data = shmem16[threadIdx.x];
В данном примере первые 2 шорта находятся в одном банке, поэтому первые 2 потока будут конфликтовать при доступе
Проблема решается аналогично 8-битному доступу:
__shared__ short shmem16[32*2];
short data = shmem16[threadIdx.x*2];
2. 32-х битный доступ
Для данного типа доступа конфликты банков менее очевидны, но могут возникнуть при, например, такой схеме доступа:
__shared__ int shmem32[64];
int data1 = shmem32[threadIdx.x*2];
int data2 = shmem32[threadIdx.x*2+1];
В этом случае 0-й и 8-й поток читают из 0 и 1 банков соответственно, создавая таким образом конфликт 2-й степени.
Решить эту проблему можно к примеру так:
__shared__ int shmem32_1[32];
__shared__ int shmem32_2[32];
int data1 = shmem32_1[threadIdx.x];
int data2 = shmem32_2[threadIdx.x];
Для устройств версии 2.0
Из-за особенностей широковещательного доступа, 8 и 16 битные схемы доступа на данных устройствах не вызывают конфликтов банков, однако, конфликт может возникнуть в следующем случае:
__shared__ int shared[64];
int data = shared[threadIdx.x*s];
Конфликт возникает, если s — четная. Если s — нечетная, но конфликтов не возникает.
Отслеживание конфликтов банков
NVIDIA Banck Checker
Конфликты можно отследить, если воспользоваться макросом CUT_BANK_CHECKER( array, index), входящим в состав CUDA Utility Toolkit. Для этого необходимо пользоваться этим макросом для доступа к памяти и выполнять приложение в режиме эмуляции. При завершении приложения, будет напечатан отчет о конфликтах.
__shared__ int shared[64];
int data = CUT_BANK_CHECKER(shared, threadIdx.x*s);
CUDA Profiler
Также, для отслеживания конфликтов можно пользоваться профайлером. Данная информация отображается в разделе warp serialize. Данный счетчик показывает количество варпов, которым необходимо сериализовывать свой доступ при адресации константной или разделяемой памяти, другими словами, этот счетчик показывает конфликты банков.
Заключение
В заключение отмечу, что наиболее эффективная методика устранения конфликтов банков — это разработка схем доступа, которая минимизирует их возникновение и последующий анализ приложения профайлером (что никогда не лишнее).
СОДЕРЖАНИЕ
В аппаратном обеспечении
Системы с общей памятью могут использовать:
В программном обеспечении
В компьютерном программном обеспечении общая память либо
Динамические библиотеки обычно хранятся в памяти один раз и сопоставляются с несколькими процессами, и дублируются только страницы, которые должны были быть настроены для отдельного процесса (поскольку символ там разрешается по-разному), обычно с помощью механизма, известного как копирование при записи, которое прозрачно копирует страницу при попытке записи, а затем позволяет успешно выполнить запись в частной копии.
Поддержка Unix-подобных систем
POSIX также предоставляет mmap API для отображения файлов в память; отображение может быть общим, что позволяет использовать содержимое файла в качестве общей памяти.
Поддержка в Windows
В Windows можно использовать CreateFileMapping и MapViewOfFile функцию для отображения области файла в память в нескольких процессах.
Кросс-платформенная поддержка
Некоторые библиотеки C ++ предоставляют переносимый и объектно-ориентированный доступ к функциям общей памяти. Например, Boost содержит библиотеку Boost.Interprocess C ++, а Qt предоставляет класс QSharedMemory.
Поддержка языков программирования
Ускоряем передачу данных в localhost
Один из самых быстрых способ межпроцессного взаимодействия реализуется при помощи разделяемой памяти (Shared Memory). Но мне казалось не логичным, что в найденных мною алгоритмах, память всё равно нужно копировать, а после перезапуска клиента (причём он допускался только один) нужно перезапускать и сервер. Взяв волю в кулак, я решил разработать полноценный клиент-сервер с использованием разделимой памяти.
И так, вначале нужно определить функциональные требования к разрабатываемому клиент-серверу. Первое и основное требование: данные не должны копироваться. Во вторых, «мультиклиентность» — к серверу могут подключаться несколько клиентов. В третьих, клиенты могут переподключаться. И в четвёртых, по возможности ПО должно быть кроссплатформенно. Из налагаемых требований, можно выделить составные части архитектуры:
Реализация клиента и сервера
Реализация передачи данных между клиентами и серверов достаточно тривиальна. Она похоже на реализацию модели поставщик-потребитель (producer-customer) с использованием семафоров, где в качестве «передаваемого» сообщения используется смещение (адрес) передаваемого буфера, а объекты синхронизации заменены на их межпроцессные аналоги. Каждому клиента и серверу соответствует своя очередь смещений, которая играет роль приёмного буфера и семафор, который отвечает за уведомление об изменении очереди. Соответственно, когда буфер отправляется другому процессу, то смещение буфера кладётся в очередь, а семафор освобождается(post). Далее другой процесс считывает данные и захватывает семафор (wait). По умолчанию процесс не ждёт получения данных другим процессом(nonblock). Пример реализации можно взять отсюда. На практике, помимо передачи самого буфера зачастую необходимо еще передать идентифицирующую информацию. Обычно это целочисленное число. Поэтому в метод Send добавлена возможность передачи числа.
Как клиенты подключаются к серверу?
Алгоритм достаточно прост, данные о сервере лежат строго по определённому смещению в разделяемой памяти. Когда клиент «открывает» разделяемую память он считывает структуру по заданному адресу, если её нет, то сервер отсутствует, если есть, то он выделяет память для структуры данных клиента, заполняет её и возбуждает событие на сервере с указанием смещения на структуру. Далее сервер добавляет нового клиента в связанный список клиентов и возбуждает в клиенте событие «подключён». Отключения осуществляется аналогичным образом.
Оценка состояния соединения
Проверка состояния соединения между клиентом и сервером построена аналогично TCP. С интервалом времени отправляется пакет жизни. Если он не доставлен – значит, клиент «рухнул». Также чтобы избежать возможных взаимных блокировок(dead lock) из-за «рухнувшего» клиента, который не освободил объект синхронизации, память для пакета жизни выделяется из собственного резерва сервера.
Реализация менеджера памяти
Как оказалась, самая сложная задача в реализации подобно IPC — это реализация менеджера памяти. Он ведь должен не просто реализовать методы malloc и free по одному из известных алгоритмов, но и не допустить утечки при «падении» клиента, предоставить возможность «резервировать» память, выделять блок памяти по конкретному смещению, не допускать фрагментирования, быть потокобезопасным, а в случаи отсутствия свободных блоков требуемого размера, ожидать его появления.
Базовый алгоритм
За основу реализации менеджера памяти был взят Free List алгоритм. Согласно этому алгоритму, все не выделенные блоки памяти объединяются в односторонний связанный список. Соответственно, при выделении блока памяти (malloc), ищется первый свободный блок, размер которого не меньше требуемого, и удаляется из связанного списка. Если размер запрашиваемого блока меньше чем размер свободного, то свободный блок разбивается на два, первый равен запрашиваемому размеру, а второй «лишнему». Первый блок – это выделенный блок памяти, а второй добавляется в список свободных блоков. При освобождении блока памяти(free), освобождаемый блок добавляется в список свободных. Далее соседние свободные блоки памяти объединяются в один. В сети есть множества реализация менеджера памяти с алгоритмом Free List. Я использовал алгоритм heap_5 из FreeRTOS.
Алгоритмические особенности
С точки зрения разработки менеджера памяти, отличительной особенностью работы с разделяемой памятью является отсутствие «помощи» со стороны ОС. Поэтому помимо списка свободных блоков памяти, менеджер также обязан сохранять информацию о владельце блока памяти. Сделать это можно несколькими способами: хранить в каждом выделенном блоке памяти PID процесса, создать таблицу «смещение выделенного блока памяти – PID», создать массив выделенных блоков памяти для каждого PID отдельно. Поскольку количество процессов обычно мало (не больше 10), то было принято гибридное решение, в каждом выделенном блоке памяти храниться индекс (2 байта) массива смещений выделенных блоков памяти, каждому PID соответствует свой массив, который расположен в конце «блока процесса» (в этом блоке храниться информация о процессе) и является динамическим.
Массив организован хитро, если блок памяти выделен процессом, то в ячейке храниться смещение выделенного блока памяти, если блок памяти не выделен, то в ячейке содержится индекс следующей «не выделенной» ячейки (фактически организован односвязный список «свободных» ячеек массива, как в алгоритме Free List). Такой алгоритм работы массива, позволяет производить удаление и добавление адреса за константное время. Причём при выделение нового блока искать таблицу соответствующую текущему PID необязательно, её смещение всегда известно заранее. А если сохранять смещение «блока процесса» в выделенном блоке памяти, то при освобождении блока искать таблицу также не надо. Из-за принятого допущения о малости количества процессов, «блоки процессов» объединены в односторонний связанный список. Таким образом, при выделении нового блока памяти (malloc) сложность добавление информации о владельце равна О(1), а при освобождении(free) блока памяти О(n), где n – количество процессов использующих разделяемую память. Почему нельзя использовать дерево или хэш-таблицы для быстрого поиска смещения «блока процесса»? Массив выделенных блоков является динамическим, следовательно, смещение у «блока процессов» может измениться.
Как писалось выше, для работы «клиент-сервера» необходимо добавить возможность «резервирования» блоков памяти. Это реализуется достаточно просто, резервный блок памяти «выделяется»для процесса. Соответственно, когда необходимо выделить блок памяти из резерва, то резервный блок процесса освобождается, и далее операции аналогичны обычному выделению. Далее, выделения блока памяти по заданному адресу реализуется тоже просто, т.к. информация о выделанных блоках храниться в «блоке процесса».
При таком большом количестве постоянно хранящейся служебной информации может возникнуть фрагментация памяти из-за разной времени «жизни» блоков, поэтому в менеджере памяти вся служебная информация(большое время жизни) выделяется с конца области, а выделение «пользовательских» блоков(малое время жизни) сначала. Таким образов, служебная информация будет фрагментировать память только при отсутствии свободных блоков.
Структура памяти представлена на рисунке ниже.
А что произойдет, если один из процессов использующих разделяемую память рухнет?
К сожалению, я не нашёл способа получить событие от ОС «процесс завершился». Но есть возможность проверить существует процесс или нет. Соответственно, когда в менеджере памяти возникает ошибка, например, закончилась память, то менеджер памяти проверяет состояние процессов. Если процесса не существует, то на основании данных хранящихся в «блоке процесса» утекшая память возвращается в оборот. К сожалению, из-за отсутствия события «процесс завершился», может возникнуть ситуация когда процесс рухнул в момент владения межпроцессным мъютексом, что естественно приведёт к блокировке менеджера памяти и невозможности запуска «очистки». Чтобы этого избежать, в заголовок добавлена информация о PID владельца мъютекса. Поэтому, при необходимости, пользователь можно вызывать проверку принудительно, скажем каждых 2 секунды. (метод watch dog)
Из-за использования «copy-on-write», может произойти ситуация, когда буфером владеют одновременно несколько процессов, причём по закону подлости, один из них рухнул. В этом случае могут возникнуть две проблемы. Первая, если рухнувший процесс являлся владельцем буфера, то он будет удалён, что приведёт к SIGNSEV у других процессов. Вторая, из-за того что рухнувший процесс не уменьшил счётчик в буфере, то он никогда не будет удалён, т.е. возникнет утечка. Простого и производительного решения этой проблемы я не нашёл, но, к счастью, такая ситуация редкость, поэтому я принял волевое решение, если кроме упавшего процесса есть ещё один владелец, то чёрт с ним, пусть память утекает, буфер перемещается к процессу запустившему очистку.
Обычно менеджер памяти в случае отсутствия свободного блока памяти возвращает NULL или выбрасывает исключение. Но нас ведь «интересует» не выделения блока памяти, а его передача, т.е. отсутствие свободного блока, говорит не об ошибке, а о необходимости подождать пока другой процесс освободит блок. Ожидание в цикле, обычно дурно пахнет. Поэтому менеджер имеет два режима выделения: классический, если нет свободного блока, возвращает NULL и ожидающий, если нет свободного блока, то процесс блокируется.
Реализация оставшихся компонентов
Основу реализации оставшихся компонентов составляет boost, поэтому далее я остановлюсь только на их особенностях. Особенностью компонента, инкапсулирующего работу с разделяемой памятью (далее CSharedMemory) наличие заголовка с межпроцессным мютексом для синхронизации методов работы с разделяемой памятью. Как показала практика, без него не обойтись. Поскольку обычно размер буфера данных не изменяется или изменяется только с начала (например, вставка заголовка в буфера данных для передачи по сети.) алгоритм резервирование памяти в CBuffer отличен от коэффициентного алгоритма резервирования памяти в std::vector. Во-первых, в реализации CBuffer добавлена возможность задавать резерв сначала, по умолчанию он равен 0. Во-вторых, алгоритм резервирования памяти следующий: если размер выделяемого блока меньше 128 байт, то резервируется 256 байт, если размер буфера данных меньше 65536, то резервируется размер буфера плюс 256 байт, в противном случае резервируется размер буфера плюс 512 байт.
Несколько слов по поводу использования sem_init в Linux
Основные источники дают не совсем корректную версию программного кода использования sem_init между процессами. В Linux необходимо выравнивать память для структуры sem_t, например вот так:
Поэтому, если у вас sem_post(sem_wait) возвращает EINVAL, попробуйте выровнять память для структуры sem_t. Пример работы с sem_init.
Итого
В результате получился клиент-сервер, скорость передачи которого не зависит от объёма данных, она зависит только от размера передаваемого буфера. Цена этому – некоторые ограничения. В Linux наиболее существенное из них — это «утечка» памяти после «завершения» процесса. Её можно удалить вручную или перезапустить ОС. При использовании в windows проблема иная, там «утекает» разделяемая память на жёстком диске, если она не была удалена вызовом метода класса сервера. Эта проблема не устраняется перезапуском ОС, только ручным удалением файлов в папке boost_interprocess. Поскольку мне иногда приходиться работать со старыми компиляторами, в репозитории лежит boost версии 1.47, хотя с последними версиями, библиотека работает шустрее.
Результаты тестирования представлены на графике ниже (Linux и QNX тестировались в виртуальной машиной VMBox)
Где взять исходники?
Исходный код стабильной версии лежит здесь. Там же есть и бинарники (+ VC redistributable) для быстрого запуска теста. Для любителей QNX в исходниках есть toolchain для CMake. Напоминаю, если CMake не собирает исходники, почистите переменные окружения, оставляя только каталоги целевого компилятора.
И напоследок ссылка на реализацию LookFree IPC с использованием разделяемой памяти.