Один из самых быстрых способ межпроцессного взаимодействия реализуется при помощи разделяемой памяти (Shared Memory). Но мне казалось не логичным, что в найденных мною алгоритмах, память всё равно нужно копировать, а после перезапуска клиента (причём он допускался только один) нужно перезапускать и сервер. Взяв волю в кулак, я решил разработать полноценный клиент-сервер с использованием разделимой памяти.
И так, вначале нужно определить функциональные требования к разрабатываемому клиент-серверу. Первое и основное требование: данные не должны копироваться. Во вторых, «мультиклиентность» — к серверу могут подключаться несколько клиентов. В третьих, клиенты могут переподключаться. И в четвёртых, по возможности ПО должно быть кроссплатформенно. Из налагаемых требований, можно выделить составные части архитектуры:
- компонент, инкапсулирующий работу с разделяемой памятью;
- менеджер памяти (allocator);
- компонент, инкапсулирующий работу с пересылаемым буфером данных и
реализующий идеологии «copy on write»(далее CBuffer); - межпроцессный мютекс;
- межпроцессная условная переменная или её аналог;
- и непосредственно клиент и сервер.
Проблем работы с разделяемой памятью достаточно много. Поэтому не будем изобретать велосипед и возьмём от boost.interprocess по максимуму. Во-первых, возьмём классы shared_memory_object, mapped_region, которые облегчат нам работы с разделяемой памятью в linux и windows. От туда можно взять и реализацию IPC семафора – который будет выполнять функции как мютекса так и условной переменной. Также возьмём в качестве образца для CBuffer, boost реализацию std::vector (При работе с разделяемой памятью оперировать указателями нельзя, только смещениями. Поэтому std::vector + allocator нам не подойдёт). Ещё в boost можно найти реализацию межпроцессного deque, но как это использовать при разработке клиент-сервера я не нашёл. И остался только вопрос с менеджером памяти(allocator) для разделяемой памяти. Естественно, и он есть в boost, но он ориентирован на решение других задач. Таким образом, от boost будут взяты не требующие компилирования библиотеки (header only). Хотя boost под MSVC может с этой точкой зрения не согласиться, поэтому не забываем про дубину – препроцессор BOOST_ALL_NO_LIB запрещающий использовать «pragma comment».(Воспоминания из ночного монолога: «Какого чёрта линкуются библиотеки boost!»)
Реализация клиента и сервера
Реализация передачи данных между клиентами и серверов достаточно тривиальна. Она похоже на реализацию модели поставщик-потребитель (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_t*)(((uintptr_t)mem+__alignof(sem_t))&~(__alignof(sem_t)-1)Поэтому, если у вас sem_post(sem_wait) возвращает EINVAL, попробуйте выровнять память для структуры sem_t. Пример работы с sem_init.
Итого
В результате получился клиент-сервер, скорость передачи которого не зависит от объёма данных, она зависит только от размера передаваемого буфера. Цена этому – некоторые ограничения. В Linux наиболее существенное из них — это «утечка» памяти после «завершения» процесса. Её можно удалить вручную или перезапустить ОС. При использовании в windows проблема иная, там «утекает» разделяемая память на жёстком диске, если она не была удалена вызовом метода класса сервера. Эта проблема не устраняется перезапуском ОС, только ручным удалением файлов в папке boost_interprocess. Поскольку мне иногда приходиться работать со старыми компиляторами, в репозитории лежит boost версии 1.47, хотя с последними версиями, библиотека работает шустрее.
Результаты тестирования в Windows представлены на графике ниже
Где взять исходники?
Исходный код стабильной версии лежит здесь. Там же есть и бинарники (+ VC redistributable) для быстрого запуска теста. Для любителей QNX в исходниках есть toolchain для CMake. Напоминаю, если CMake не собирает исходники, почистите переменные окружения, оставляя только каталоги целевого компилятора.
И напоследок ссылка на реализацию LookFree IPC с использованием разделяемой памяти.
Автор: Lauren
