Способ параллельной обработки упорядоченных потоков данных

Способ параллельной обработки упорядоченных потоков данных

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Предлагаемое изобретение относится к вычислительной технике и, в частности, к способам параллельной обработки нескольких цифровых потоков данных, каждый из которых представляет последовательность дискретных наборов данных определенного вида, например, IP пакетов и т.п.

Уровень техники

При обработке цифровых данных часто возникает задача параллельной обработки нескольких цифровых потоков данных, имеющих в общем случае разную скорость, с помощью автоматического многоканального устройства, обеспечивающего необходимую обработку каждого входного потока и передачу его в обработанном виде в соответствующий выходной поток, причем характерная скорость обработки данных в каждом канале обработки может быть существенно меньше скорости входного потока, а требуемая скорость обработки каждого входного потока без задержки обеспечивается за счет наличия множества каналов обработки.

Важными условиями успешной работы такого устройства является обеспечение точного соблюдения последовательности обработанных данных в каждом выходном потоке соответствующей последовательности во входном потоке, а также высокая производительность.

Характер обработки данных может быть различным, например это может быть преобразование входных пакетов протокола АТМ в выходные пакеты протокола IP, преобразование входных зашифрованных/незашифрованных пакетов IP соответственно в расшифрованные/зашифрованные пакеты IP и т.д.

Так, известен способ передачи данных между одним или несколькими первыми сетевыми портами, принимающими один или несколько первых потоков данных, и одним или несколькими вторыми сетевыми портами, передающими один или несколько вторых потоков данных [1].

Способ включает следующие действия:

- посылку данных от одного или несколько первых потоков данных во множество каналов обработки;

- обработку данных параллельно двумя или более каналами обработки;

- получение данных, обработанных каналами обработки и

- посылку обработанных данных в один или несколько вторых потоков в один или несколько вторых портов,

причем, по крайней мере, в одном потоке из первого и второго потоков данные передаются в кадрах (frames), и каждый кадр в таком одном потоке обработан одним (единственным) каналом обработки, но, по крайней мере, два кадра в одном потоке обработаны двумя различными каналами обработки.

Данные, полученные в каждом первом потоке данных, передаются в соответствующий второй поток данных в том же самом порядке, в котором эти данные были в первом потоке данных.

После получения из первого потока каждый кадр перед посылкой на обработку в канал обработки снабжается дополнительными атрибутами (данными), в состав которых включают, по крайней мере,

- номер кадра в первом потоке и

- идентификатор канала, в который посылается данный кадр.

Для обеспечения правильного порядка следования обработанных кадров в соответствующем втором потоке организуется стек памяти, сформированный по принципу "первым пришел - первым ушел" (first in - first out, FIFO), куда записываются идентификаторы канала для тех каналов обработки, в которые посылаются кадры из первого потока.

Поэтому когда после получения из канала обработки обработанный кадр посылается во второй поток, то это делается в порядке следования идентификаторов каналов в стеке FIFO.

Следует отметить, что при описании известного способа используется оригинальная терминология, согласно которой, в частности, термин "кадр" подразумевает дискретный набор цифровых данных определенного формата, соответствующий какому-либо принятому протоколу (ATM, IP и др.).

Для реализации известного способа используется система, включающая:

- первый блок для посылки данных от одного или нескольких первых потоков данных к множеству каналов обработки, в котором, по крайней мере, в одном потоке из первого и второго потоков, данные передаются в кадрах, причем первый блок выполнен с возможностью посылать каждый кадр только в один из каналов обработки, а также послать, по крайней мере, два разных кадра в два различных канала обработки;

- множество каналов обработки, каждый из которых содержит отдельный процессор;

- второй блок для получения данных, обработанных каналами обработки, и посылки обработанных данных в один или несколько вторых потоков в один или несколько вторых портов;

- блок управления порядком для обеспечения второго блока идентификаторами каналов для каждого канала обработки, которому посылается кадр первым блоком,

причем второй блок выполнен с возможностью получать идентификаторы каналов от блока управления порядком в таком же самом порядке, в котором соответствующие кадры расположены, по крайней мере, в одном первом потоке,

при этом, когда второй блок получает идентификатор канала, то второй блок посылает кадр из соответствующего канала обработки во второй поток, так что кадры посылаются, по крайней мере, в один второй поток из каналов обработки в порядке, определяемом идентификаторами каналов.

В известном способе предусмотрена обработка кадров как постоянного, так и переменного размера. В общем случае даже при обработке кадров постоянного размера по заранее установленному алгоритму время обработки отдельных кадров может отличаться из-за различных факторов (неодинаковая скорость работы отдельных каналов, разное время обращения к памяти и пр.). Поэтому вполне может возникнуть ситуация, когда текущий кадр первого потока уже обработан в каком-либо канале обработки, но не может быть передан на выход системы, поскольку предыдущий кадр, за которым он следует, еще не обработан и не передан на выход во второй поток. В этой ситуации система дожидается окончания обработки и передачи на выход сначала предыдущего кадра, а затем текущего, чтобы обеспечить правильный порядок следования кадров.

Еще более заметно такие задержки могут проявиться при обработке кадров переменного размера. Такие задержки снижают производительность системы, что является недостатком известного способа.

Известен также способ обеспечения работы сетевой системы для параллельной обработки потоков данных [2], причем система содержит

- первый блок, обеспечивающий

- прием входных потоков данных из внешних сетевых соединений;

- разделение входных потоков данных на части;

- снабжение каждой части каждого входного потока данных атрибутами;

- посылку частей каждого входного потока данных в процессорные блоки для обработки;

- совокупность процессорных блоков, каждый из которых имеет в своем составе процессор и буфер памяти для хранения обработанных частей входных потоков данных и обеспечивает

- обработку по заданному алгоритму частей входных потоков данных;

- посылку обработанных частей входных потоков данных в соответствующие выходные потоки данных;

- хранение обработанных частей входных потоков данных в буфере памяти до момента выполнения условий посылки этих частей в соответствующий выходной поток данных;

- второй блок, обеспечивающий

- прием обработанных частей входных потоков данных;

- формирование и модификацию выходных очередей, содержащих (выходные маркеры обработки), причем количество выходных очередей соответствует количеству выходных потоков данных;

- передачу обработанных частей входных потоков данных в виде соответствующих выходных потоков данных во внешнюю сеть;

причем первый блок связан с совокупностью процессорных блоков и со вторым блоком, а процессорные блоки также связаны со вторым блоком.

Согласно способу в одном из предлагаемых вариантов реализации:

- получают входные потоки данных из сетевых соединений в первом блоке;

- задают требуемое соответствие между входными и выходными потоками данных;

- формируют во втором блоке выходные очереди потоков, количество которых соответствует количеству выходных потоков данных;

- формируют в каждом процессорном блоке выходные очереди процессорных блоков, количество которых соответствует количеству выходных потоков данных;

- посылают части входных потоков данных для обработки в процессорные блоки, причем каждая часть каждого входного потока данных снабжается атрибутами, в состав которых включается

- идентификатор процессорного блока, в который посылается данная часть входного потока;

- идентификатор входного потока;

- помещают идентификатор процессорного блока, в который послана очередная часть входного потока данных для обработки, в выходную очередь потока второго блока, которая соответствует заданному выходному потоку и содержит (выходной маркер обработки);

- обрабатывают части входных потоков данных в процессорных блоках для получения соответствующих частей выходных потоков данных;

- записывают идентификатор процессорного блока, в котором закончилась обработка части определенного входного потока данных, в выходную очередь этого процессорного блока, которая соответствует заданному выходному потоку;

- обеспечивают {порядок следования} частей выходных потоков данных из (процессорных блоков), который соответствует порядку частей входных потоков данных, причем для обеспечения {правильного порядка следования}

- сравнивают идентификатор процессорного блока, в котором закончилась обработка части первого потока, с правильным очередным идентификатором процессорного блока в (выходном маркере обработки) и, если при сравнении идентификаторы не совпадают, то

- сохраняют обработанную часть первого потока в буфере памяти данного процессорного блока;

- записывают идентификатор процессорного блока в выходную очередь данного процессорного блока;

- обрабатывают следующую часть входного потока данных в данном процессорном блоке;

- если при сравнении идентификаторы совпадают, то

- посылают части выходных потоков данных из процессорных блоков во второй блок для формирования выходных потоков данных, в которых порядок следования частей соответствует порядку следования частей в соответствующих входных потоках и

- после посылки очередной обработанной части первого потока модифицируют в каждом процессорном блоке идентификатор этого процессорного блока в выходной очереди этого процессорного блока для соответствующего выходного потока и в (выходном маркере обработки) соответствующего выходного потока. В известном способе предусмотрена обработка частей входного потока данных (сетевых пакетов) как постоянного, так и переменного размера.

Здесь также при обработке частей входного потока данных по заранее установленному алгоритму время обработки отдельных частей может отличаться из-за различных факторов (неодинаковая скорость работы отдельных процессорных блоков, разное время обращения к памяти и пр.). Поэтому вполне может возникнуть ситуация, когда отдельная часть входного потока уже обработана в каком-либо процессорном блоке, но не может быть немедленно передана на выход системы, поскольку предыдущая часть входного потока еще не обработана.

Для обеспечения порядка следования частей выходного потока данных, точно совпадающего с порядком следования частей соответствующего входного потока данных, используется специально сформированная очередь, первый элемент которой (выходной маркер обработки) является идентификатором процессорного блока, из которого должна поступить в выходной поток данных очередная обработанная часть входного потока данных.

В качестве идентификатора могут использоваться целые числа, адреса в памяти, индексы массивов и пр.

После посылки части входных потоков данных для обработки в процессорные блоки помещают идентификатор процессорного блока, в который послана очередная часть входного потока данных для обработки, в выходную очередь потока второго блока, которая соответствует заданному выходному потоку и содержит (выходной маркер обработки), причем

- перед записью идентификатора процессорного блока блокируют доступ к выходной очереди, обеспечивая, таким образом, исключительный доступ на запись со стороны этого процессорного блока (и запрет на запись со стороны любого другого процессорного блока);

- осуществляют запись идентификатора путем выполнения атомарных операций, а затем

- снимают блокировку доступа.

После окончания обработки в каком-либо процессорном блоке части входного потока данных проводится проверка соответствия идентификатора этого процессорного блока и правильного идентификатора из выходного маркера обработки.

Если при сравнении эти идентификаторы совпадают, то обработанная часть входного потока данных передается на выход системы во второй блок, а выходной маркер обработки модифицируется путем удаления из его очереди номера данного процессорного блока.

Если же эти номера не совпадают, то обработанную часть первого потока сохраняют в буфере памяти данного процессорного блока и запоминают идентификатор данного процессорного блока в выходной очереди данного процессорного блока, организованной в формате стека памяти FIFO.

После этого процессорный блок останавливается и непрерывно производит проверку номера этого процессорного блока и правильного номера из выходного маркера обработки до момента, пока эти номера совпадут.

Согласно предпочтительному варианту реализации способа, если номера не совпадают, процессорный блок получает из первого блока новую часть входного потока данных и обрабатывает ее. После окончания обработки новой части входного потока данных снова проводится проверка соответствия идентификатора из стека выходной очереди этого процессорного блока и правильного номера из выходного маркера обработки.

Если эти номера совпадают, то обработанная часть входного потока данных передается из буфера памяти данного процессорного блока на выход системы во второй блок, а выходной маркер обработки модифицируется путем удаления из его очереди номера данного процессорного блока.

Модифицируется также стек выходной очереди данного процессорного блока путем удаления из него идентификатора данного процессорного блока, передавшего на выход обработанную часть входного потока данных.

Известный способ принят за прототип для предлагаемого технического решения.

Недостатком известного способа является невысокая производительность даже в предпочтительном варианте реализации способа, которая возникает из-за задержки при проверке идентификатора определенного процессорного блока и правильного номера из выходного маркера обработки до момента, пока эти номера совпадут, поскольку, если совпадение не произошло, то следующий момент проверки возникает только после обработки новой части входного потока данных.

Раскрытие изобретения

Техническим результатом является повышение производительности обработки входных потоков за счет устранения ожидания момента окончания обработки очередной части входного потока в случаях, когда предыдущие части уже обработаны.

Для этого предлагается способ параллельной обработки упорядоченных потоков данных в вычислительной системе, причем система содержит

- первый блок, обеспечивающий

- прием входных потоков данных из внешних сетевых соединений;

- разделение входных потоков данных на части;

- снабжение каждой части каждого входного потока данных атрибутами;

- передачу частей каждого входного потока данных в процессорные блоки для обработки;

- совокупность процессорных блоков, каждый из которых имеет в своем составе процессор и средства для хранения обработанных частей входных потоков данных и обеспечивает

- обработку по заданному алгоритму частей входных потоков данных;

- передачу обработанных частей входных потоков данных в соответствующие выходные потоки данных;

- хранение обработанных частей входных потоков данных до момента выполнения условий посылки этих частей в соответствующий выходной поток данных;

- передачу обработанных частей входных потоков данных в другие процессорные блоки;

- получение обработанных частей входных потоков данных из других процессорных блоков;

- поиск заданных элементов в атрибутах частей входных потоков данных;

причем первый блок связан с совокупностью процессорных блоков,

способ, заключающийся в том, что

- получают входные потоки данных из сетевых соединений в первом блоке;

- передают части входных потоков данных для обработки в процессорные блоки, причем каждая часть каждого входного потока данных снабжается атрибутами, в состав которых включается

- идентификатор входного потока;

- идентификатор положения данной части во входном потоке;

- обрабатывают части входных потоков данных в процессорных блоках для получения соответствующих частей выходных потоков данных;

- обеспечивают порядок следования частей выходных потоков данных из процессорных блоков, который соответствует порядку частей входных потоков данных, причем для обеспечения порядка следования

- проводят поиск процессорного блока, в котором обрабатывается часть определенного входного потока данных, находившаяся в определенном первом потоке перед частью, уже обработанной в рассматриваемом процессорном блоке, причем,

если после поиска таких процессорных блоков найдено несколько, то

- выбирают тот процессорный блок, в котором обрабатывается часть определенного входного потока данных, расположенная наиболее близко к обработанной части определенного входного потока;

- передают обработанную часть определенного входного потока данных из рассматриваемого процессорного блока в выбранный процессорный блок, а также, при наличии, ранее полученные от других процессорных блоков обработанные части входного потока данных;

если после поиска таких процессорных блоков не найдено, то

- передают обработанные части входного потока данных в соответствующий выходной поток данных, в которых порядок следования частей соответствует порядку следования частей в соответствующем входном потоке, с учетом ранее полученных от других процессорных блоков обработанных частей входного потока данных.

Таким образом, в отличие от известного способа в предложенном способе после окончания обработки части определенного входного потока данных не происходит задержки, а обработанная часть входного потока данных передается из рассматриваемого процессорного блока в выбранный процессорный блок. Вслед за передачей обработанной части рассматриваемый процессорный блок сразу принимает для обработки очередную часть какого-либо входного потока данных и начинает ее обрабатывать.

Можно отметить также, что эта очередная часть может принадлежать другому входному потоку данных, отличному от определенного входного потока данных, к которому принадлежала ранее обработанная и переданная часть. Такая возможность отсутствует в прототипе, поскольку в нем используются идентификаторы процессорных блоков, привязанные, в конечном счете, к какому-либо одному входному потоку данных до окончания его обработки, а это также снижает производительность системы.

Краткое описание чертежей

На фиг.1 показана схема, поясняющая принцип организации очереди FIFO с помощью атрибутов Next и Last структуры данных packets_info.

На фиг.2 показан общий алгоритм передачи обработанного пакета на выход системы.

На фиг.3 показан алгоритм поиска "предшественника" среди обрабатываемых пакетов.

На фиг.4 показан алгоритм передачи списка обработанных пакетов программным потоком своему текущему "предшественнику".

На фиг.5 показан алгоритм проверки очереди пакетов, полученных от "последователей", которые программный поток должен передать на выход системы.

На фиг.6 показан алгоритм поиска "предшественника" с помощью поля predecessor_value, выполняемый программным потоком при организации отправки обработанных пакетов на выход системы.

На фиг.7 показан жизненный цикл объекта, доступ к которому контролируется с помощью механизма подсчета ссылок.

На фиг.8 показан алгоритм функции GetReference механизма подсчета ссылок.

На фиг.9 показан алгоритм функции RequestToDisableSharedMode механизма подсчета ссылок.

На фиг.10 показан алгоритм функции ReleaseReference механизма подсчета ссылок.

Осуществление изобретения

Рассмотрим пример реализации предложенного способа в сетевом маршрутизаторе, выполненном в виде многопроцессорной вычислительной системы и предназначенном для преобразования множества входных потоков данных, получаемых из внешней сети передачи данных (например, сетевых пакетов данных из сети Интернет), во множество выходных потоков данных, передаваемых, например, во внутреннюю корпоративную сеть передачи данных.

Для определенности можно рассмотреть входные потоки данных, представляющие собой последовательность пакетов данных, сформированных по протоколу TCP/IP и зашифрованных с использованием какого-либо стандарта (например, DES) с известными параметрами.

Задачей маршрутизатора будет расшифровка входных потоков данных и передача их во внутреннюю сеть передачи данных потребителям (обычным пользователям).

Для приема входных потоков данных маршрутизатор содержит

- нескольких сетевых интерфейсов, обеспечивающих прием и передачу сетевых пакетов данных;

- нескольких процессорных блоков, каждый из которых представляет собой процессор общего назначения (например, на базе архитектуры x86 или ARM), выполняющих обработку принятых пакетов,

- оперативной памяти, предназначенной для хранения принятых сетевых пакетов, а также информации, необходимой для функционирования системы.

Архитектура процессоров общего назначения должна поддерживать следующие типы операций:

- атомарная (непрерываемая) операция чтения ячейки памяти с последующей записью нового значения (далее обозначается AtomicExchange), например, для архитектуры x86 - это команда процессора "xchg";

- атомарная (непрерываемая) операции чтения ячейки памяти с последующей записью считанного значения увеличенного на заданное число (далее - AtomicAdd), например, для архитектуры x86 - это команда процессора "lock xchgadd".

Маршрутизатор функционирует под управлением операционной системы (ОС), способной функционировать в многопроцессорной конфигурации (например, ОС Linux).

Для реализации предложенного способа для каждого процессорного блока обеспечивается выполнение дополнительно следующих функций, отсутствующих в прототипе:

- передачу обработанных частей входных потоков данных в другие процессорные блоки;

- получение обработанных частей входных потоков данных из других процессорных блоков;

- поиск заданных элементов в атрибутах частей входных потоков данных;

Передача обработанных частей входных потоков данных в соответствующие выходные потоки данных обеспечивается каждым процессорным блоком. Непосредственная передача данных во внутреннюю сеть может осуществляться с помощью одной или нескольких сетевых карт, соединенных с внутренней сетью.

Функции, требуемые для реализации предложенного способа, должны обеспечиваться прикладным программным обеспечением (ППО), которое может быть разработано специалистом по программированию (программистом) на основе приведенных сведений о назначении функций.

Компоненты ОС, обеспечивающие управление сетевыми интерфейсами - драйверы сетевых интерфейсов - помещают принятые сетевые пакеты в оперативную память. Дополнительно к каждому принятому пакету драйвер создает в оперативной памяти специальную структуру данных (далее - packet_info), которая состоит из следующих полей (атрибутов):

- адрес пакета данных из определенного входного потока данных в оперативной памяти;

- адрес следующего пакета данных из определенного входного потока данных в очереди (последовательности) пакетов (далее Next);

- адрес последнего пакета данных в очереди (последовательности) пакетов (далее Last);

Атрибуты Last и Next предназначены для организации очереди из принятых пакетов, формируемой по схеме FIFO. У последнего пакета данных в очереди в поле Next записан 0 (нуль).

Принцип организации очереди FIFO с помощью указанных полей приведен на фиг.1.

После копирования пакета в память драйвер добавляет соответствующую ему структуру packet_info в FIFO очередь принятых пакетов. Доступ к очереди синхронизируется посредством стандартной функции ОС (примитива синхронизации, например, spinlock в ОС Linux), обеспечивающей эксклюзивный доступ к синхронизируемому объекту (например, ячейке памяти). Указанный примитив функционирует следующим образом: для получения доступа к объекту компонент ОС должен "захватить" (lock) примитив, после чего может модифицировать объект, а затем "отпустить" примитив (unlock).

Обработка пакетов выполняется в программных потоках обработки ОС (например, kernel threads в ОС Linux), причем количество программных потоков не превышает количества процессорных блоков в системе, и каждый программный поток выполняется только в одном процессорном блоке.

Каждый программный поток имеет два состояния:

- "занят" - производит обработку сетевого пакета, а также действия по сохранению порядка следования пакетов;

- "свободен" - ожидает нового пакета для обработки, при этом поток не выполняется своим процессорным блоком.

Ожидание программным потоком нового пакета для обработки может быть реализовано с помощью стандартного механизма синхронизации ОС, например ожидание на примитиве синхронизации семафор в ОС Linux.

Количество программных потоков, находящихся в определенном состоянии, хранится в оперативной памяти в виде специальной структуры данных (далее - threads_info). Доступ к этой структуре также синхронизирован с помощью примитива синхронизации очереди FIFO.

Драйвер сетевого интерфейса после добавления packet_info в очередь принятых пакетов на основе данных структуры threads_info определяет, есть ли в данный момент программный поток обработки в состоянии «свободен». Если такой программный поток есть, то драйвер использует соответствующий механизм примитива синхронизации ОС для активации программного потока.

Для обработки сетевого пакета в программном потоке используют специальную структуру (далее - descriptor), которая хранит всю необходимую информацию для выполнения требуемых действий над сетевым пакетом и отправки его на выход из системы.

Каждый программный поток имеет свой фиксированный набор структур descriptor, зарезервированных в оперативной памяти. Количество структур в наборе каждого программного потока равно количеству программных потоков в системе. Этим гарантируется, что у программного потока всегда будет свободная структура descriptor, для обработки нового пакета.

Структура descriptor может быть в трех состояниях:

- "занят" - используется для обработки пакета;

- "свободен" - может использоваться программным потоком для обработки нового пакета;

- переходное состояние от "занят к "свободен" - пакет обработан, но структура еще не может быть использована для обработки нового пакета.

Управление состояниями структуры descriptor осуществляется посредством специального программного механизма подсчета ссылок на объект и дополнительных флагов, описанных ниже.

Структура descriptor состоит из полей, приведенных в табл.1

Таблица 1
Обозначение	Тип	Назначение
state	ссылка	характеризует состояние структуры descriptor
id	число	идентификатор входного сетевого потока, из которого взят пакета, описываемый данной структурой descriptor
order_id	беззнаковое целое число	порядковый номер пакета во входном сетевом потоке; считается, что пакет А расположен в входном сетевом потоке перед пакетом Б, если разность их порядковых номеров, представленная в виде целого числа со знаком, будет отрицательна
predecessor_value	адрес	адрес структуры descriptor, которая описывает пакет ("предшественник"), расположенный во входном сетевом потоке данных перед обрабатываемым пакетом
predecessor_state	ссылка	ссылка для синхронизации доступа к полю predecessor_value
packets_list	адрес	адрес первого элемента очереди, состоящей из структур packet_info; данная очередь используется для передачи пакетов между программными потоками в процессе определения порядка следования их на выход системы; наряду с адресом packet_info в данном поле храниться два флага Predesessor_Refn Successor_Ref
stop	число	признак, что descriptor не находится в состоянии "занят"
free	число	признак, что descriptor находится в состоянии "свободен"

Структура descriptor переходит в состояние "свободен", только когда ссылка state перешла в состояние модификации объекта, таким образом, в состоянии "свободен" ссылка state находится в состоянии модификации.

В состоянии "занят" структуры descriptor ссылка state находится в состоянии совместного доступа к объекту.

Получение сетевого пакета программным потоком для обработки

Программный поток после активации драйвером или окончания обработки пакета получает доступ к очереди принятых пакетов, "захватывая" примитив синхронизации, и забирает первый пакет из очереди.

Если нет пакетов для обработки, то программный поток освобождает примитив синхронизации, переходит в состояние «свободен» и ожидает активации на соответствующем примитиве синхронизации ОС.

Если пакет имеется, то после извлечения его из очереди программный поток формирует идентификатор входного сетевого потока данных, которому принадлежит пакет, используя номер сетевого интерфейса в ОС, тип протокола сетевого уровня, а также информацию из заголовка сетевого уровня (например, информацию из IP заголовка: IP адреса источника и получателя, тип протокола транспортного уровня). Затем пакету присваивается порядковый номер, который отражает его расположение во входном потоке данных. Идентификатор потока и порядковый номер сохраняются программным потоком в оперативной памяти в структуре descriptor, адрес которой записан в переменной free_descriptor. У каждого программного потока имеется своя переменная free_descriptor. В данной переменной всегда в момент получения пакета на обработку хранится адрес структуры descriptor в состоянии "свободен" из набора структур descriptor программного потока.

После заполнения соответствующих полей программный поток переводит структуру descriptor в состояние "занят" (ссылка state в режим совместного использования). Затем записывает адрес структуры descriptor в оперативную память в переменную current_descriptor. С каждым программным потоком связана своя переменная current_descriptor.

Затем программный поток освобождает примитив синхронизации очереди, после чего считается, что он перешел в состояние "занят". Программный поток приступает к обработке пакета (расшифровка по заданному алгоритму, возможны также дополнительные предусмотренные действия по маршрутизации, применению правил фильтрации и т.п.).

Передача пакета на выход системы

После обработки для определения правильного порядка следования пакета на выход из системы (на соответствующий сетевой интерфейс) программный поток выполняет поиск "предшественника" (predecessor) из обрабатываемых в данный момент другими программными потоками пакетов.

"Предшественник" - это пакет из того же входного сетевого потока данных, что и обработанный данным программным потоком, но расположенный во входном сетевом потоке перед ним, т.е. имеющий меньший порядковый номер.

В структуре descriptor предусмотрено поле predecessor_value, в которое помещается адрес структуры descriptor, используемой программным потоком, производящим обработку найденного "предшественника". Доступ остальных программных потоков к полю predecessor_value синхронизируется посредством механизма подсчета ссылок. Для этой цели в descriptor предусмотрено поле predecessor_state типа reference.

Передача пакета на выход из системы зависит от наличия "предшественника".

Если "предшественник" не был найден, то это означает, что все пакеты из определенного входного сетевого потока до текущего обработанного пакета уже переданы на выход системы, вследствие чего обработанный пакет передается на выход системы (драйверу сетевого интерфейса для отправки).

Если "предшественник был найден, то программный поток добавляет пакет (список пакетов в общем случае, см. ниже) в очередь пакетов packets_list в структуру данных descriptor "предшественника". В процессе добавления программный поток проверяет признаки состояния в структуре descriptor "предшественника". Если признаки указывают состояние "занят", то пакет успешно добавлен в его очередь. Теперь передачу пакета далее на выход системы выполнит программный поток, выполняющий обработку "предшественника".

Если "предшественник" находится в переходном состоянии (в состоянии "занят" он быть не может, поскольку программный поток, добавляющий пакет (список пакетов), удерживает ссылку на него), то добавления не происходит. При этом, если у "предшественника" были пакеты в очереди, то программный поток формирует из этих пакетов и своего пакета (списка пакетов) новый список пакетов.

Затем программный поток проводит поиск "предшественника" в состоянии "занят", используя поле predecessor_value в структуре descriptor "предшественника". Если поиск успешен, то найденный "предшественник" используется для передачи ему пакетов аналогично описанному выше. Если же "предшественник" так и не был найден, то программный поток передает список пакетов на выход системы (драйверам соответствующих сетевых интерфейсов).

После передачи списка пакетов на выход системы (согласно описанному выше алгоритму) программный поток проверяет очередь пакетов в своей структуре descriptor (переменная current_descriptor). Если в процессе проверки программный поток обнаруживает, что очередь пуста либо в данный момент другой программный поток пытается добавить пакеты для отправки, то данный программный поток выставляет признак переходного состояния своей структуры descriptor и переходит к получению следующего пакета. Иначе программный поток получает все пакеты из очереди и передает их по описанному выше алгоритму.

Схема передача пакетов на выход системы приведена на фиг.2.

Поиск "предшественника" среди обрабатываемых пакетов

Программный поток выполняет поиск "предшественника", просматривая поочередно переменные current_descriptor остальных программных потоков (далее - descr) и сравнивая значения идентификатора входного сетевого потока и порядкового номера обрабатываемого пакета с такими же параметрами своего current_descriptor (далее - current).

Перед выполнением сравнения программный поток получает ссылку de-scr.state, что блокирует переход этой структуры descriptor в свободное состояние (для повторного использования).

Если descr - первый найденный описатель, удовлетворяющий требованиям "предшественника", то программный поток пытается получить его ссылку prede-cessor_state. В случае успеха адрес descr сохраняется как "кандидат в предшественники" (переменная pred). Полученная ссылка descr.predecessor_state гарантирует, что в состоянии перехода descr из состояния "занят" в состояние "свободен" значение descr.predecessor_value сохраниться до тех пор, пока current удерживает эту ссылку (descr не может перейти в состояние "свободен", поскольку программный поток ранее получил его ссылку descr.state).

Если descr - первая найденная структура descriptor, удовлетворяющая вышеперечисленным требованиям, то программный поток получает ссылку descr.predecessor_state и, в случае успеха, descr сохраняется как "кандидат в предшественники".

Если на предыдущих итерация поиска уже был найден «кандидат в предшественники», то в таком случае производится сравнение порядковых номеров descr и "кандидата в предшественники" для определения, кто из них "ближе" к current.

Если ближе оказался descr, то программный поток получает ссылку descr.predecessor_state и в случае успеха запоминает descr в качестве "кандидата в предшественники", а ссылки бывшего "кандидата в предшественники" освобождаются.

В результате успешного поиска последний найденный "кандидат в предшественники" будет считаться "предшественником", его адрес будет сохранен в current_descriptor.predecessor_value, а программный поток передаст ему свой обработанный пакет, чтобы программный поток "предшественника" отправил его на выход системы после своего пакета.

Последовательность поиска "п