Параллельное программирование

Организация и оптимизация параллельных процессов

Разбить на страницы
Показывать лекцию целиком

Общая схема параллельных вычислений при обслуживании потока заявок (в АСУ)

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

(рис 8.1) Схема параллельного вычислительного процесса

Общий алгоритм функционирования АСУ в виде макропрограммы отображен блоком 1.

Каждая макроинструкция может заключать большой объем работ. Это — отдельные операторы, задачи (функциональные модули), задания, процессы и др. Макропрограмма либо содержит макроинструкции, которые соответствуют логическим операторам, влияющим на выбор ее ветви, либо имеет специальный блок управления. В результате выполнения этих операторов формируется (блок 2) поток макроинструкций (очередь), подлежащих выполнению процессорами. При этом могут учитываться значения логических переменных, как рассчитанные по макропрограмме (внутреннее управление), так и выработанные на основе внешнего воздействия: управляемым объектом, параметрами управляемого технологического процесса, оператором с пульта или терминала. Т.е. на этом уровне вырабатывается непосредственно поток заданий.

Затем (блок 3) формируется некоторая интерпретация потока заданий (макроинструкций) для диспетчера.

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

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

Особенности параллельного вычислительного процесса в системе реального времени

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

В целом АСУ реального времени на основе использования ВС является многоканальной системой массового обслуживания, поскольку, как правило, управление производится сразу большим числом объектов (множеством летательных аппаратов, множеством вырабатываемых изделий и т.д.). Общая схема организации вычислительного процесса та же, что и выше.

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

Возьмем возможную временную диаграмму (рис. 8.2).

(рис 8.2) Схема параллельных вычислений в реальном времени

Пусть ВС состоит из двух процессоров. Общий алгоритм управления разбивается на частные задачи, решаемые в циклах двух длительностей $$\delta _{1}$$ и $$\delta _{2},$$ пусть $$\delta _{2} = 2\delta _{1}$$. Информационно зависимые задачи, решаемые в цикле длительности $$\delta _{1}$$, отражены графом G1, а задачи, решаемые в цикле длительности $$\delta _{2}$$, — графом G2. Графы — взвешенные: вес вершины равен условному времени решения соответствующей задачи, что отражено на диаграмме.

Примечание. О многоциклическом режиме решения задач в АСУ.

Предположим, мы управляем каким-то "быстрым" объектом или процессом. Нам надо с большой частотой выдавать управляющие воздействия. Они вырабатываются (на некотором временном интервале) по одним и тем же алгоритмам, т.е. циклически решаются одни и те же задачи. Их решение привязывается к сигналам прерывания, которые выдаются с одной и той же частотой. Но могут решаться периодически и другие задачи, для точности результатов которых достаточна более низкая частота: задачи оценки состояния среды, меняющейся плавно, задачи отображения и т.д. Таким образом, в целом в системе одновременно циклически решаются много задач, но в циклах разной длительности. В общем случае решаемые задачи информационно взаимозависимы.

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

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

Из диаграммы видно, что в момент начала цикла длительности $$\delta _{2}$$, а, следовательно, и цикла длительности $$\delta _{1}$$, включается супервизор (отмечен черным), функции которого значительно шире, чем при включении в начале только цикла длительности $$\delta _{1}$$ (отмечен светлым). В результате его работы возможна смена состава решаемых задач. Если в системе есть и диспетчер, его работа может быть учтена увеличением времени работы супервизора.

Предполагают, что задачи, решаемые в каждом цикле меньшей длительности $$(\delta _{1})$$, обладают более высоким приоритетом, чем задачи, решаемые в циклах большей длительности $$(\delta _{2})$$.

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

Процессор 1 сначала выбирает для решения задачу 1. Из готовых к решению задач процессор 2 может выбрать лишь задачу 6. После решения задачи 1 появляется возможность решения высокоприоритетных задач 2 и 3. Задача 2 выбирается процессором 1, а процессор 2 прерывает задачу 6 и приступает к решению задачи 3. (Неизбежен циклический анализ очереди на появление задач, приоритет которых выше приоритета решаемых задач.) После решения задачи 3 начинается решение задачи 5, а после решения задачи 2, с учетом того, что к этому моменту решена и задача 3, начинается решение задачи 4. После окончания решения задачи 5 продолжается решение задачи 6, затем начинается решение задач 7 и 8. Однако их решение прерывается началом выполнения следующего цикла длительности $$\delta _{1}$$, в котором вновь воспроизводится план решения задач 1--5. Лишь во время решения процессором 1 задачи 1 продолжается решение задачи 7 процессором 2. В соответствии с приоритетом решение задач 7 и 8 заканчивается. В следующем цикле длительности $$\delta _{2}$$ весь рассмотренный план решения задач 1--8 повторяется, и так — до изменения состава задач в соответствии с условиями работы управляющей системы.

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

Централизованные и децентрализованные ВС

Классификация

ВС делятся на централизованные и децентрализованные. Это связано с реализованными в них способами управления, или диспетчирования.

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

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

Таким образом, в чистом виде децентрализованное диспетчирование не применяется.

Централизованное диспетчирование

В более сложном виде задача диспетчирования возникает в централизованных ВС. В чем она заключается?

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

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

(рис 8.3) Информационный граф и расширенная матрица следования

Показана соответствующая ему матрица следования S и расширенная матрица следования S*, содержащая и столбец весов.

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

Формально: пусть задано множество работ $$A = \{ \alpha _{1} , \dots , \alpha _{m}\}$$ и известно множество временных оценок этих работ T = {t1 , ..., tm}, а также известна частичная упорядоченность, задаваемая матрицей следования S. Пусть ВС — однородная (т.е. все процессоры обладают одинаковой производительностью) и содержит n процессоров. Пусть в результате распределения множества работ A между n процессорами каждый ( i -й) процессор оказался занятым решением задач в течение времени Ti. Тогда время решения всей совокупности задач$$\begin{align*} T_{\text{реш}} = \max_{i=1, ..., n} \{T_i\} \end{align*}$$

Задачей диспетчера является распределение работ $$\alpha _{1},\dots ,\alpha _{m}$$ между процессорами, обеспечивающее$$\begin{align*} T_{\text{реш}} - \frac{1}{n} \sum_{j=1}^m t_j \longrightarrow \min \end{align*}$$

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

Децентрализованное диспетчирование в многоканальном и многоциклическом режиме

Рассмотрим схему организации параллельного вычислительного процесса в реальном времени.

Система управления обслуживает в многоканальном режиме ряд однотипных объектов. Одновременно обслуживаемые объекты могут находиться на разных стадиях обслуживания. По каждому объекту циклически и в разных комбинациях решаются задачи из некоторого заранее установленного множества информационно взаимосвязанных задач. Частичная упорядоченность задач задается расширенной матрицей следования S*.

  • Рассмотрим случай, когда задачи решаются в цикле одной длительности.

    Супервизор формирует матрицу S', которая отражает множество решаемых задач по всем объектам (или по всем занятым каналам обслуживания), обслуживаемым в данное время, и список или очередь Q, содержащий информацию о решаемых задачах (рис. 8.4).

    (рис 8.4) Информация для одноциклического режима обслуживания

    (Для этого из матрицы S* для каждого объекта исключаются строки и столбцы, соответствующие нерешаемым задачам, и блочно-диагональным наращиванием строится S'.)

    Каждая задача характеризуется именем, номером i канала или объекта, по которому она решается, относительным приоритетом p, значением t времени решения, контрольным временем t0, по истечении которого следует сделать вывод об аварийной ситуации.

    При обращении процессора к очереди, назначение очередной задачи на процессор производится на основе анализа S*. Из множества задач, которым соответствуют нулевые строки этой матрицы, выбирается еще не назначенная задача с максимальным приоритетом (минимальное значение p ) из тех, которые по времени выполнения укладываются в ресурс процессора в цикле (см. далее). Если таких задач с одинаковым приоритетом несколько, из них выбирается задача с максимальным временем выполнения. Назначенная задача отмечается, чтобы исключить повторное назначение.

    После решения любой задачи и исключения информации о ней из S* могут оказаться "открытыми" задачи, обладающие более высоким приоритетом, чем некоторые из тех, которые уже решаются. В этом случае возможен один из вариантов, когда диспетчер того процессора, на котором закончилось решение некоторой задачи, после назначения (себе) очередной задачи производит попытку дополнительного назначения другим процессорам. Находится готовая к решению задача с максимальным приоритетом и для него — с максимальным временем t. Процессоры последовательно опрашиваются. По опросу прерывается работа того процессора, который решает задачу с приоритетом меньшим, чем приоритет найденной задачи, и с текущим ресурсом времени в цикле $$\delta,$$ превышающим t. Ему выдается сигнал прерывания, по которому он выполняет прерывание и обращается к очереди. Тогда эта задача будет назначена вместо прерванной.

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

    Циклическая работа процессоров организуется с помощью прерывания от системы синхронизации (таймера или СЕВ). В этом случае восстанавливается исходный вид матрицы S* и очередь Q. Процесс решения задач повторяется, если супервизор не внес коррективы в их состав.

  • Многоциклический режим. Пусть часть задач решается в цикле длительности $$k_{1}\delta$$, часть — в цикле длительности $$k_{2} \delta$$ и т.д. Всего — r длительностей, и k1 < k2 < ... < kr. (Обычно k1 = 1.) Через интервалы, кратные $$\delta,$$ в ВС формируются сигналы прерывания, анализируемые диспетчерами процессоров. Если $$k_{\mu } > k_{\nu }$$, то все задачи, решаемые в цикле $$k_{\nu }\delta$$, обладают более высоким приоритетом, чем все задачи, решаемые в цикле $$k_{\mu }\delta$$.

    При составлении комплексного задания объединяют его части, относящиеся к циклам одинаковой длительности. Каждая часть заканчивается признаком "конец задания для $$k_{j}\delta$$ " j = 1 , ... , r (рис. 8.5). По этому признаку после выполнения всего задания для данного цикла и поступления сигнала от системы синхронизации о начале следующего цикла этой же длительности восстанавливается исходный вид соответствующей части задания. После этого диспетчеры производят дополнительное назначение в соответствии с готовыми к решению более приоритетными задачами, т.е. начинают новый цикл по возможности с более приоритетных задач.

    (рис 8.5) Многоциклический режим параллельного решения задач

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

    Как же считается и учитывается этот ресурс? Рассмотрим его как переменный ресурс времени Rij, которым располагает i -й процессор, i = 1, ... , n, в цикле длительности $$k_{j}\delta , j = 1 , \dots , r$$.

    Пусть первоначально, до назначения на процессор задач i -й процессор в цикле длительности $$k_{1}\delta$$ располагал ресурсом $$R_{i1} =k_{1}\delta$$, в цикле длительности $$k_{2}\delta$$ — ресурсом $$R_{i2} = k_{2}\delta$$ и т.д. Пусть на процессор для решения выбрана задача $$\alpha$$ с временем решения $$t_{\alpha }$$. Пусть она решается в цикле длительности $$k_{j} \delta$$. Ее назначение не влияет на порядок решения задач в циклах меньшей длительности, т.к. они обладают более высоким приоритетом. Однако при последующем назначении на этот же процессор задач, решаемых в цикле этой и большей длительности, необходимо учитывать решение задачи — с равным или большим приоритетом.

    Запишем оператор определения нового значения вычислительного ресурса в цикле длительности $$k_{j} \delta$$ и в циклах большей длительности после единичного назначения на этот же процессор в цикле $$k_{j} \delta$$$$\begin{align*} R_{il}: = R_{il}\frac{k_l}{k_j}t_\alpha, \,l = j,\, j + 1 \dts r \end{align*}$$

    Здесь ресурс оценивается приближенно, без учета дискретности работ, соразмерности длительности циклов и неточности определения $$t_{\alpha }$$.

    •

    Таким образом, прежде чем производить назначение другой задачи, $$\beta,$$ решаемой в цикле длительности $$k_{j} \beta$$, на i -й процессор, необходимо проверить, располагает ли он ресурсом $$R_{ij} \ge t_{\beta }$$? Если располагает, назначение производится, после чего значения ресурса для l >= j уточняются. Если не располагает, производится поиск подходящей задачи.

    Это и было отражено выше при рассмотрении назначения в одно- и многоциклическом режиме решения задач.

    Комбинированное диспетчирование в ВС с очередью

    Рассмотрим более детально, применительно к сложным системам обработки информации или к АСУ, как организуется параллельный процесс в таких системах. При этом мы увидим, что в реальных системах принципы централизованного и децентрализованного управления причудливо переплетаются. Будем ориентироваться на ВС с очередью, обеспечивающей виртуализацию вычислительного ресурса (процессоров), что характерно для семейства "Эльбрус". Такие ВС в значительной степени обеспечивают децентрализованное диспетчирование.

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

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

    Стек процессора обладает активным оборудованием, на которое налагается стек процесса для его активизации (рис. 8.6), т.е. для выполнения процесса.

    (рис 8.6) Комбинированное диспетчирование в ВС с очередью

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

    Ранее говорилось, что информационной основой работы процессоров ВС является очередь процессов "к процессору", которую составляют пассивные стеки процессов. Из очереди процессов процессоры выбирают задания по мере окончания выполнения принятых ранее или при необходимости их прерывания. Очередь процессов может формироваться на основе любого числа элементов процессов. Естественно, при реализации это число приходится ограничивать. В соответствии с готовностью к выполнению и выполнением различают три состояния процессов: активен, т.е. стек данного процесса находится на стеке одного из процессоров и, следовательно, этот процесс выполняется; готов к выполнению, т.е. данный процесс не выполняется только из-за отсутствия свободного процессора; ждет, т.е. процесс не может выполняться, пока не произойдет некоторое событие, обусловленное приоритетом или информационной взаимосвязью процессов. В частности, если в ВС реализован механизм семафоров, регулирующий частичную упорядоченность процессов, то процесс может находиться в состоянии ожидания открытия семафора ("висеть" на семафоре).

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

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

    На рис. 8.7 отражен текущий вид очереди, а также те связи (штриховыми линиями), которые возникнут, если откроются семафоры A и B выполняемыми на процессорах процессами.

    (рис 8.7) Учёт приоритета задач в очереди

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

    Для повышения надежности и универсальности используемых ресурсов стеки процессоров могут быть нежестко закреплены за процессорами (см. идею решающих полей!). В стеке процессора в основном концентрируются устройства памяти процессоров, основные регистры, над которыми производятся операции. Операционные устройства могут быть отделены от собственно процессора и рассматриваться отдельно. Собственно процессором остается устройство управления, ведающее обработкой потока инструкций, их назначением для выполнения. Это допускает перекоммутацию (показана штриховой линией на рис. 8.8) связи процессор-стек процессора в случае отказов процессоров, т.к. стек отказавшего процессора соответствует пассивному стеку некоторого процесса. При этом может быть учтен приоритет решаемых процессорами задач.

    (рис 8.8) ВС с управляющими процессором и стеком

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

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

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

  • Данная процедура находит среди всех активных стеков стек выполняемого процесса с минимальным приоритетом. При этом возможны два случая:

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

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

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

    Элемент же децентрализованного управления ВС может осуществляться с помощью периодического включения в состав очереди управляющего процесса, объединяющего ряд процедур управления. При каждом включении этого процесса подготавливается его следующее включение вновь. С таким процессом может быть связан семафор C, открытие которого может производиться по достижении таймером некоторого значения времени $$T = t + \tau$$, где t — время настоящей активации управляющего процесса; $$\tau$$ — период его активации (период или такт управления). Тогда управляющий процесс должен начинаться с процедуры ЖДАТЬ (С,Т) и включать в себя процедуру ЗАКРЫТЬ (С).

    Очевидно, что такое решение не обеспечивает оперативной и синхронной работы средств ВС и чревато возможностью отказа ВС без выхода на процедуры управления. Поэтому подстановку управляющих процессов в очередь все же целесообразно поручить управляющему процессору (считая, что им может быть один из процессоров ВС, решающий и основные задачи из очереди). На рис. 8.9 это — управляющие процессы УП1 и УП2. Но это, как говорилось ранее, — когда отсутствуют жесткие требования к моменту принятия решения.

    (рис 8.9) Два управляющих процесса в очереди

    Управляющий процессор реагирует на сигналы прерывания, поступающие в жестком временном режиме — с периодом $$\tau.$$ По поступлении на управляющий процессор сигнала прерывания может быть произведена его перекоммутация на управляющий стек процессора или подстановка в очередь необходимого управляющего процесса. В этом случае обработка управляющих процессов производится так же, как и других процессов, теми процессорами, которые их выбрали для выполнения в соответствии с виртуализацией вычислительного ресурса.

    Подводя итог анализу способов организации управления вычислительным процессом в ВС, можно выделить три возможности:

  • 1) управление через очередь, при котором управляющий процесс периодически подставляется в очередь и реализуется процессором, выбравшим его в соответствии с дисциплиной обслуживания очереди. Такой способ управления приемлем, например, для таких работ, как реорганизация памяти, оценка состояния средств и др.;
  • 2) выполнение одним из процессоров функции головного или управляющего. Его работа по обслуживанию очереди периодически прерывается для выполнения функций управления ВС;
  • 3) наличие в системе специального управляющего процессора (иногда называемого ХОСТ-процессором), в силу назначения и исполнения не участвующего в обслуживании очереди. В многопроцессорных ВС, совмещающих различные режимы обработки информации и нуждающихся в сложном планировании использования ресурсов, целесообразно включение в состав ВС специализированных управляющих процессоров.
    •

    Концептуальные основы распараллеливания в МВК семейства "Эльбрус"

    Управление процессами в МВК семейства "Эльбрус"

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

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

    Стек пассивного процесса (рис. 8.10) состоит из шапки и активной области.

    (рис 8.10) Стек активного процесса

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

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

    Информационной основой работы процессоров МВК является очередь процессов (" к процессору " ), которую составляют указатели на пассивные стеки процессов. Очередь упорядочена по приоритетам. Из очереди процессоры выбирают задания (процессы) по мере окончания выполнения принятых ранее или при их прерывании. В очереди есть и так называемые "ждущие" процессы, которые по мере выполнения условий задержки (например, открытия семафоров) занимают место в соответствии со значением приоритета.

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

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

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

    Распараллеливание в МВК. Семафоры

    Распараллеливание для полного использования ресурсов МВК осуществляется двумя путями:

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

    Синхронизация информационно взаимосвязанных процессов производится с помощью механизма семафоров.

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

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

    ОБЪЯВИТЬ (С) — объявляется список семафоров C, выделяется память и задается тип переменной при трансляции.

    ЗАКРЫТЬ (С) — присваивает семафорам, перечисленным в списке C, значение "закрыт".

    ЖДАТЬ (С) — в случае, если в C указаны семафоры со значением "закрыт", прерывает выполняемый процесс. Стек процесса условно дополняет очереди к закрытым семафорам, перечисленным в списке C. Таким образом, если с данной процедуры начинается выполнение некоторой работы, то оно будет поставлено в зависимость от условий выполнения каких-то других работ. Концом выполнения процедуры является переход к анализу очереди процессов для последующей загрузки процессора.

    ОТКРЫТЬ (С) — семафорам, указанным в списке C, присваивается значение "открыт" и процессоры из очередей к данным семафорам переводятся в очередь для продолжения их выполнения.

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

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

    (рис 8.11) Синхронизация распараллеливания с помощью семафоров

    Выше рассмотрен механизм семафоров для информационно взаимосвязанных или взаимодействующих процессов. Однако семафоры применяются и для синхронизации обращений к общим данным и другим общим ресурсам. Рассмотрим вариант, применяемый в МВК "Эльбрус-2".

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

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

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

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

    Указанных операций достаточно для решения различных задач синхронизации при использовании общих ресурсов.

    Реализация конвейера на симметричной ВС

    В СССР существовал опыт построения ВС конвейерного типа на основе систем типа MIMD. Такая система ("Украина"), названная рекурсивной машиной, разрабатывалась под руководством В.М. Глушкова в ИК АН УССР. Этот опыт уже тогда продемонстрировал общность принципа симметричных ВС, хотя направленность разработки на параллельное выполнение циклов типа "пересчет", по нашему мнению, раскрыта не полностью.

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

    Пусть, однако, длительность решения задач управления одним объектом в несколько раз превосходит значение T, а характер решаемых задач не допускает их распараллеливания.

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

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

    Свяжем теперь процессоры ВС в один конвейер, на первую станцию которого будем подавать заявки на обслуживание с максимальной частотой, обусловленной тактом, а с последней станции будем снимать результаты обработки информации — с той же частотой (рис. 8.12).

    (рис 8.12) Организация конвейера

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

    Некоторый выход из положения виден в том случае, когда в рассмотренном режиме производится управление одним объектом. Тогда на основе "физики" процесса может быть справедливым предположение, что каждый результат обработки информации, полученный в i+n-1 -м такте, на основе некоторой пролонгации соответствует данным, как бы полученным не в i -м, а в i+n-2 -м такте. Т.е. необходимо исследовать возможность пролонгации "устаревших" результатов на тот такт, в котором они получены. Такой пролонгацией на последней станции конвейера должен заканчиваться последний этап обработки заявки.

    Технология data flow на уровне процедур и процессов в симметричной ВС

    "Идеальные" модели data flow (системы, управляемые потоком данных, потоковые ВС) не нашли практического воплощения. Вместе с тем, каждый разработчик, реализовавший при распараллеливании какой-то метод синхронизации частично упорядоченного множества работ, которое представляет собой любая программа или программный комплекс, утверждает, что он создал архитектуру data flow. Это традиционно увеличивает престиж разработки.

    Следуя все же изначальной идее, мы под принципом data flow будем понимать такой способ синхронизации параллельного вычислительного процесса, когда отдельные составляющие его работы — программные модули, процессы, процедуры, инструкции, команды — имеют возможность распознавания и заявления о наличии всех данных для своего выполнения. Исполнительные устройства также имеют возможность распознавать работы, для которых существуют все необходимые наборы исходных данных, и выбирать эти работы для выполнения. После выполнения они влияют на состав исходных данных других работ, пополняя их. Все это способствует синхронизированному, осмысленному процессу, максимальной загрузке оборудования, автоматическому использованию всех возможностей реализуемых алгоритмов по распараллеливанию.

    Принцип data flow также можно использовать на двух уровнях распараллеливания вычислительного процесса.

    Рассмотрим возможность его воплощения на симметричных ВС с помощью механизма синхронизации "почтовых ящиков" (рис. 8.13).

    (рис 8.13) Схема data flow с помощью "почтовых ящиков"

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

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

    Отметим также, что целесообразно совмещать принцип data flow с принципом децентрализованных ВС. Это вновь оказывается совместимым с основной идеологией семейства "Эльбрус".

    Страницы:

    Общая схема параллельных вычислений при обслуживании потока заявок (в АСУ)

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

    (рис 8.1) Схема параллельного вычислительного процесса

    Общий алгоритм функционирования АСУ в виде макропрограммы отображен блоком 1.

    Каждая макроинструкция может заключать большой объем работ. Это — отдельные операторы, задачи (функциональные модули), задания, процессы и др. Макропрограмма либо содержит макроинструкции, которые соответствуют логическим операторам, влияющим на выбор ее ветви, либо имеет специальный блок управления. В результате выполнения этих операторов формируется (блок 2) поток макроинструкций (очередь), подлежащих выполнению процессорами. При этом могут учитываться значения логических переменных, как рассчитанные по макропрограмме (внутреннее управление), так и выработанные на основе внешнего воздействия: управляемым объектом, параметрами управляемого технологического процесса, оператором с пульта или терминала. Т.е. на этом уровне вырабатывается непосредственно поток заданий.

    Затем (блок 3) формируется некоторая интерпретация потока заданий (макроинструкций) для диспетчера.

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

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

    Особенности параллельного вычислительного процесса в системе реального времени

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

    В целом АСУ реального времени на основе использования ВС является многоканальной системой массового обслуживания, поскольку, как правило, управление производится сразу большим числом объектов (множеством летательных аппаратов, множеством вырабатываемых изделий и т.д.). Общая схема организации вычислительного процесса та же, что и выше.

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

    Возьмем возможную временную диаграмму (рис. 8.2).

    (рис 8.2) Схема параллельных вычислений в реальном времени

    Пусть ВС состоит из двух процессоров. Общий алгоритм управления разбивается на частные задачи, решаемые в циклах двух длительностей $$\delta _{1}$$ и $$\delta _{2},$$ пусть $$\delta _{2} = 2\delta _{1}$$. Информационно зависимые задачи, решаемые в цикле длительности $$\delta _{1}$$, отражены графом G1, а задачи, решаемые в цикле длительности $$\delta _{2}$$, — графом G2. Графы — взвешенные: вес вершины равен условному времени решения соответствующей задачи, что отражено на диаграмме.

    Примечание. О многоциклическом режиме решения задач в АСУ.

    Предположим, мы управляем каким-то "быстрым" объектом или процессом. Нам надо с большой частотой выдавать управляющие воздействия. Они вырабатываются (на некотором временном интервале) по одним и тем же алгоритмам, т.е. циклически решаются одни и те же задачи. Их решение привязывается к сигналам прерывания, которые выдаются с одной и той же частотой. Но могут решаться периодически и другие задачи, для точности результатов которых достаточна более низкая частота: задачи оценки состояния среды, меняющейся плавно, задачи отображения и т.д. Таким образом, в целом в системе одновременно циклически решаются много задач, но в циклах разной длительности. В общем случае решаемые задачи информационно взаимозависимы.

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

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

    Из диаграммы видно, что в момент начала цикла длительности $$\delta _{2}$$, а, следовательно, и цикла длительности $$\delta _{1}$$, включается супервизор (отмечен черным), функции которого значительно шире, чем при включении в начале только цикла длительности $$\delta _{1}$$ (отмечен светлым). В результате его работы возможна смена состава решаемых задач. Если в системе есть и диспетчер, его работа может быть учтена увеличением времени работы супервизора.

    Предполагают, что задачи, решаемые в каждом цикле меньшей длительности $$(\delta _{1})$$, обладают более высоким приоритетом, чем задачи, решаемые в циклах большей длительности $$(\delta _{2})$$.

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

    Процессор 1 сначала выбирает для решения задачу 1. Из готовых к решению задач процессор 2 может выбрать лишь задачу 6. После решения задачи 1 появляется возможность решения высокоприоритетных задач 2 и 3. Задача 2 выбирается процессором 1, а процессор 2 прерывает задачу 6 и приступает к решению задачи 3. (Неизбежен циклический анализ очереди на появление задач, приоритет которых выше приоритета решаемых задач.) После решения задачи 3 начинается решение задачи 5, а после решения задачи 2, с учетом того, что к этому моменту решена и задача 3, начинается решение задачи 4. После окончания решения задачи 5 продолжается решение задачи 6, затем начинается решение задач 7 и 8. Однако их решение прерывается началом выполнения следующего цикла длительности $$\delta _{1}$$, в котором вновь воспроизводится план решения задач 1--5. Лишь во время решения процессором 1 задачи 1 продолжается решение задачи 7 процессором 2. В соответствии с приоритетом решение задач 7 и 8 заканчивается. В следующем цикле длительности $$\delta _{2}$$ весь рассмотренный план решения задач 1--8 повторяется, и так — до изменения состава задач в соответствии с условиями работы управляющей системы.

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

    Централизованные и децентрализованные ВС

    Классификация

    ВС делятся на централизованные и децентрализованные. Это связано с реализованными в них способами управления, или диспетчирования.

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

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

    Таким образом, в чистом виде децентрализованное диспетчирование не применяется.

    Централизованное диспетчирование

    В более сложном виде задача диспетчирования возникает в централизованных ВС. В чем она заключается?

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

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

    (рис 8.3) Информационный граф и расширенная матрица следования

    Показана соответствующая ему матрица следования S и расширенная матрица следования S*, содержащая и столбец весов.

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

    Формально: пусть задано множество работ $$A = \{ \alpha _{1} , \dots , \alpha _{m}\}$$ и известно множество временных оценок этих работ T = {t1 , ..., tm}, а также известна частичная упорядоченность, задаваемая матрицей следования S. Пусть ВС — однородная (т.е. все процессоры обладают одинаковой производительностью) и содержит n процессоров. Пусть в результате распределения множества работ A между n процессорами каждый ( i -й) процессор оказался занятым решением задач в течение времени Ti. Тогда время решения всей совокупности задач$$\begin{align*} T_{\text{реш}} = \max_{i=1, ..., n} \{T_i\} \end{align*}$$

    Задачей диспетчера является распределение работ $$\alpha _{1},\dots ,\alpha _{m}$$ между процессорами, обеспечивающее$$\begin{align*} T_{\text{реш}} - \frac{1}{n} \sum_{j=1}^m t_j \longrightarrow \min \end{align*}$$

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

    Децентрализованное диспетчирование в многоканальном и многоциклическом режиме

    Рассмотрим схему организации параллельного вычислительного процесса в реальном времени.

    Система управления обслуживает в многоканальном режиме ряд однотипных объектов. Одновременно обслуживаемые объекты могут находиться на разных стадиях обслуживания. По каждому объекту циклически и в разных комбинациях решаются задачи из некоторого заранее установленного множества информационно взаимосвязанных задач. Частичная упорядоченность задач задается расширенной матрицей следования S*.

  • Рассмотрим случай, когда задачи решаются в цикле одной длительности.

    Супервизор формирует матрицу S', которая отражает множество решаемых задач по всем объектам (или по всем занятым каналам обслуживания), обслуживаемым в данное время, и список или очередь Q, содержащий информацию о решаемых задачах (рис. 8.4).

    (рис 8.4) Информация для одноциклического режима обслуживания

    (Для этого из матрицы S* для каждого объекта исключаются строки и столбцы, соответствующие нерешаемым задачам, и блочно-диагональным наращиванием строится S'.)

    Каждая задача характеризуется именем, номером i канала или объекта, по которому она решается, относительным приоритетом p, значением t времени решения, контрольным временем t0, по истечении которого следует сделать вывод об аварийной ситуации.

    При обращении процессора к очереди, назначение очередной задачи на процессор производится на основе анализа S*. Из множества задач, которым соответствуют нулевые строки этой матрицы, выбирается еще не назначенная задача с максимальным приоритетом (минимальное значение p ) из тех, которые по времени выполнения укладываются в ресурс процессора в цикле (см. далее). Если таких задач с одинаковым приоритетом несколько, из них выбирается задача с максимальным временем выполнения. Назначенная задача отмечается, чтобы исключить повторное назначение.

    После решения любой задачи и исключения информации о ней из S* могут оказаться "открытыми" задачи, обладающие более высоким приоритетом, чем некоторые из тех, которые уже решаются. В этом случае возможен один из вариантов, когда диспетчер того процессора, на котором закончилось решение некоторой задачи, после назначения (себе) очередной задачи производит попытку дополнительного назначения другим процессорам. Находится готовая к решению задача с максимальным приоритетом и для него — с максимальным временем t. Процессоры последовательно опрашиваются. По опросу прерывается работа того процессора, который решает задачу с приоритетом меньшим, чем приоритет найденной задачи, и с текущим ресурсом времени в цикле $$\delta,$$ превышающим t. Ему выдается сигнал прерывания, по которому он выполняет прерывание и обращается к очереди. Тогда эта задача будет назначена вместо прерванной.

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

    Циклическая работа процессоров организуется с помощью прерывания от системы синхронизации (таймера или СЕВ). В этом случае восстанавливается исходный вид матрицы S* и очередь Q. Процесс решения задач повторяется, если супервизор не внес коррективы в их состав.

  • Многоциклический режим. Пусть часть задач решается в цикле длительности $$k_{1}\delta$$, часть — в цикле длительности $$k_{2} \delta$$ и т.д. Всего — r длительностей, и k1 < k2 < ... < kr. (Обычно k1 = 1.) Через интервалы, кратные $$\delta,$$ в ВС формируются сигналы прерывания, анализируемые диспетчерами процессоров. Если $$k_{\mu } > k_{\nu }$$, то все задачи, решаемые в цикле $$k_{\nu }\delta$$, обладают более высоким приоритетом, чем все задачи, решаемые в цикле $$k_{\mu }\delta$$.

    При составлении комплексного задания объединяют его части, относящиеся к циклам одинаковой длительности. Каждая часть заканчивается признаком "конец задания для $$k_{j}\delta$$ " j = 1 , ... , r (рис. 8.5). По этому признаку после выполнения всего задания для данного цикла и поступления сигнала от системы синхронизации о начале следующего цикла этой же длительности восстанавливается исходный вид соответствующей части задания. После этого диспетчеры производят дополнительное назначение в соответствии с готовыми к решению более приоритетными задачами, т.е. начинают новый цикл по возможности с более приоритетных задач.

    (рис 8.5) Многоциклический режим параллельного решения задач

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

    Как же считается и учитывается этот ресурс? Рассмотрим его как переменный ресурс времени Rij, которым располагает i -й процессор, i = 1, ... , n, в цикле длительности $$k_{j}\delta , j = 1 , \dots , r$$.

    Пусть первоначально, до назначения на процессор задач i -й процессор в цикле длительности $$k_{1}\delta$$ располагал ресурсом $$R_{i1} =k_{1}\delta$$, в цикле длительности $$k_{2}\delta$$ — ресурсом $$R_{i2} = k_{2}\delta$$ и т.д. Пусть на процессор для решения выбрана задача $$\alpha$$ с временем решения $$t_{\alpha }$$. Пусть она решается в цикле длительности $$k_{j} \delta$$. Ее назначение не влияет на порядок решения задач в циклах меньшей длительности, т.к. они обладают более высоким приоритетом. Однако при последующем назначении на этот же процессор задач, решаемых в цикле этой и большей длительности, необходимо учитывать решение задачи — с равным или большим приоритетом.

    Запишем оператор определения нового значения вычислительного ресурса в цикле длительности $$k_{j} \delta$$ и в циклах большей длительности после единичного назначения на этот же процессор в цикле $$k_{j} \delta$$$$\begin{align*} R_{il}: = R_{il}\frac{k_l}{k_j}t_\alpha, \,l = j,\, j + 1 \dts r \end{align*}$$

    Здесь ресурс оценивается приближенно, без учета дискретности работ, соразмерности длительности циклов и неточности определения $$t_{\alpha }$$.

    •

    Таким образом, прежде чем производить назначение другой задачи, $$\beta,$$ решаемой в цикле длительности $$k_{j} \beta$$, на i -й процессор, необходимо проверить, располагает ли он ресурсом $$R_{ij} \ge t_{\beta }$$? Если располагает, назначение производится, после чего значения ресурса для l >= j уточняются. Если не располагает, производится поиск подходящей задачи.

    Это и было отражено выше при рассмотрении назначения в одно- и многоциклическом режиме решения задач.

    Комбинированное диспетчирование в ВС с очередью

    Рассмотрим более детально, применительно к сложным системам обработки информации или к АСУ, как организуется параллельный процесс в таких системах. При этом мы увидим, что в реальных системах принципы централизованного и децентрализованного управления причудливо переплетаются. Будем ориентироваться на ВС с очередью, обеспечивающей виртуализацию вычислительного ресурса (процессоров), что характерно для семейства "Эльбрус". Такие ВС в значительной степени обеспечивают децентрализованное диспетчирование.

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

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

    Стек процессора обладает активным оборудованием, на которое налагается стек процесса для его активизации (рис. 8.6), т.е. для выполнения процесса.

    (рис 8.6) Комбинированное диспетчирование в ВС с очередью

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

    Ранее говорилось, что информационной основой работы процессоров ВС является очередь процессов "к процессору", которую составляют пассивные стеки процессов. Из очереди процессов процессоры выбирают задания по мере окончания выполнения принятых ранее или при необходимости их прерывания. Очередь процессов может формироваться на основе любого числа элементов процессов. Естественно, при реализации это число приходится ограничивать. В соответствии с готовностью к выполнению и выполнением различают три состояния процессов: активен, т.е. стек данного процесса находится на стеке одного из процессоров и, следовательно, этот процесс выполняется; готов к выполнению, т.е. данный процесс не выполняется только из-за отсутствия свободного процессора; ждет, т.е. процесс не может выполняться, пока не произойдет некоторое событие, обусловленное приоритетом или информационной взаимосвязью процессов. В частности, если в ВС реализован механизм семафоров, регулирующий частичную упорядоченность процессов, то процесс может находиться в состоянии ожидания открытия семафора ("висеть" на семафоре).

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

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

    На рис. 8.7 отражен текущий вид очереди, а также те связи (штриховыми линиями), которые возникнут, если откроются семафоры A и B выполняемыми на процессорах процессами.

    (рис 8.7) Учёт приоритета задач в очереди

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

    Для повышения надежности и универсальности используемых ресурсов стеки процессоров могут быть нежестко закреплены за процессорами (см. идею решающих полей!). В стеке процессора в основном концентрируются устройства памяти процессоров, основные регистры, над которыми производятся операции. Операционные устройства могут быть отделены от собственно процессора и рассматриваться отдельно. Собственно процессором остается устройство управления, ведающее обработкой потока инструкций, их назначением для выполнения. Это допускает перекоммутацию (показана штриховой линией на рис. 8.8) связи процессор-стек процессора в случае отказов процессоров, т.к. стек отказавшего процессора соответствует пассивному стеку некоторого процесса. При этом может быть учтен приоритет решаемых процессорами задач.

    (рис 8.8) ВС с управляющими процессором и стеком

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

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

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

  • Данная процедура находит среди всех активных стеков стек выполняемого процесса с минимальным приоритетом. При этом возможны два случая:

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

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

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

    Элемент же децентрализованного управления ВС может осуществляться с помощью периодического включения в состав очереди управляющего процесса, объединяющего ряд процедур управления. При каждом включении этого процесса подготавливается его следующее включение вновь. С таким процессом может быть связан семафор C, открытие которого может производиться по достижении таймером некоторого значения времени $$T = t + \tau$$, где t — время настоящей активации управляющего процесса; $$\tau$$ — период его активации (период или такт управления). Тогда управляющий процесс должен начинаться с процедуры ЖДАТЬ (С,Т) и включать в себя процедуру ЗАКРЫТЬ (С).

    Очевидно, что такое решение не обеспечивает оперативной и синхронной работы средств ВС и чревато возможностью отказа ВС без выхода на процедуры управления. Поэтому подстановку управляющих процессов в очередь все же целесообразно поручить управляющему процессору (считая, что им может быть один из процессоров ВС, решающий и основные задачи из очереди). На рис. 8.9 это — управляющие процессы УП1 и УП2. Но это, как говорилось ранее, — когда отсутствуют жесткие требования к моменту принятия решения.

    (рис 8.9) Два управляющих процесса в очереди

    Управляющий процессор реагирует на сигналы прерывания, поступающие в жестком временном режиме — с периодом $$\tau.$$ По поступлении на управляющий процессор сигнала прерывания может быть произведена его перекоммутация на управляющий стек процессора или подстановка в очередь необходимого управляющего процесса. В этом случае обработка управляющих процессов производится так же, как и других процессов, теми процессорами, которые их выбрали для выполнения в соответствии с виртуализацией вычислительного ресурса.

    Подводя итог анализу способов организации управления вычислительным процессом в ВС, можно выделить три возможности:

  • 1) управление через очередь, при котором управляющий процесс периодически подставляется в очередь и реализуется процессором, выбравшим его в соответствии с дисциплиной обслуживания очереди. Такой способ управления приемлем, например, для таких работ, как реорганизация памяти, оценка состояния средств и др.;
  • 2) выполнение одним из процессоров функции головного или управляющего. Его работа по обслуживанию очереди периодически прерывается для выполнения функций управления ВС;
  • 3) наличие в системе специального управляющего процессора (иногда называемого ХОСТ-процессором), в силу назначения и исполнения не участвующего в обслуживании очереди. В многопроцессорных ВС, совмещающих различные режимы обработки информации и нуждающихся в сложном планировании использования ресурсов, целесообразно включение в состав ВС специализированных управляющих процессоров.
    •

    Концептуальные основы распараллеливания в МВК семейства "Эльбрус"

    Управление процессами в МВК семейства "Эльбрус"

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

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

    Стек пассивного процесса (рис. 8.10) состоит из шапки и активной области.

    (рис 8.10) Стек активного процесса

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

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

    Информационной основой работы процессоров МВК является очередь процессов (" к процессору " ), которую составляют указатели на пассивные стеки процессов. Очередь упорядочена по приоритетам. Из очереди процессоры выбирают задания (процессы) по мере окончания выполнения принятых ранее или при их прерывании. В очереди есть и так называемые "ждущие" процессы, которые по мере выполнения условий задержки (например, открытия семафоров) занимают место в соответствии со значением приоритета.

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

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

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

    Распараллеливание в МВК. Семафоры

    Распараллеливание для полного использования ресурсов МВК осуществляется двумя путями:

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

    Синхронизация информационно взаимосвязанных процессов производится с помощью механизма семафоров.

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

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

    ОБЪЯВИТЬ (С) — объявляется список семафоров C, выделяется память и задается тип переменной при трансляции.

    ЗАКРЫТЬ (С) — присваивает семафорам, перечисленным в списке C, значение "закрыт".

    ЖДАТЬ (С) — в случае, если в C указаны семафоры со значением "закрыт", прерывает выполняемый процесс. Стек процесса условно дополняет очереди к закрытым семафорам, перечисленным в списке C. Таким образом, если с данной процедуры начинается выполнение некоторой работы, то оно будет поставлено в зависимость от условий выполнения каких-то других работ. Концом выполнения процедуры является переход к анализу очереди процессов для последующей загрузки процессора.

    ОТКРЫТЬ (С) — семафорам, указанным в списке C, присваивается значение "открыт" и процессоры из очередей к данным семафорам переводятся в очередь для продолжения их выполнения.

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

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

    (рис 8.11) Синхронизация распараллеливания с помощью семафоров

    Выше рассмотрен механизм семафоров для информационно взаимосвязанных или взаимодействующих процессов. Однако семафоры применяются и для синхронизации обращений к общим данным и другим общим ресурсам. Рассмотрим вариант, применяемый в МВК "Эльбрус-2".

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

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

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

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

    Указанных операций достаточно для решения различных задач синхронизации при использовании общих ресурсов.

    Реализация конвейера на симметричной ВС

    В СССР существовал опыт построения ВС конвейерного типа на основе систем типа MIMD. Такая система ("Украина"), названная рекурсивной машиной, разрабатывалась под руководством В.М. Глушкова в ИК АН УССР. Этот опыт уже тогда продемонстрировал общность принципа симметричных ВС, хотя направленность разработки на параллельное выполнение циклов типа "пересчет", по нашему мнению, раскрыта не полностью.

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

    Пусть, однако, длительность решения задач управления одним объектом в несколько раз превосходит значение T, а характер решаемых задач не допускает их распараллеливания.

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

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

    Свяжем теперь процессоры ВС в один конвейер, на первую станцию которого будем подавать заявки на обслуживание с максимальной частотой, обусловленной тактом, а с последней станции будем снимать результаты обработки информации — с той же частотой (рис. 8.12).

    (рис 8.12) Организация конвейера

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

    Некоторый выход из положения виден в том случае, когда в рассмотренном режиме производится управление одним объектом. Тогда на основе "физики" процесса может быть справедливым предположение, что каждый результат обработки информации, полученный в i+n-1 -м такте, на основе некоторой пролонгации соответствует данным, как бы полученным не в i -м, а в i+n-2 -м такте. Т.е. необходимо исследовать возможность пролонгации "устаревших" результатов на тот такт, в котором они получены. Такой пролонгацией на последней станции конвейера должен заканчиваться последний этап обработки заявки.

    Технология data flow на уровне процедур и процессов в симметричной ВС

    "Идеальные" модели data flow (системы, управляемые потоком данных, потоковые ВС) не нашли практического воплощения. Вместе с тем, каждый разработчик, реализовавший при распараллеливании какой-то метод синхронизации частично упорядоченного множества работ, которое представляет собой любая программа или программный комплекс, утверждает, что он создал архитектуру data flow. Это традиционно увеличивает престиж разработки.

    Следуя все же изначальной идее, мы под принципом data flow будем понимать такой способ синхронизации параллельного вычислительного процесса, когда отдельные составляющие его работы — программные модули, процессы, процедуры, инструкции, команды — имеют возможность распознавания и заявления о наличии всех данных для своего выполнения. Исполнительные устройства также имеют возможность распознавать работы, для которых существуют все необходимые наборы исходных данных, и выбирать эти работы для выполнения. После выполнения они влияют на состав исходных данных других работ, пополняя их. Все это способствует синхронизированному, осмысленному процессу, максимальной загрузке оборудования, автоматическому использованию всех возможностей реализуемых алгоритмов по распараллеливанию.

    Принцип data flow также можно использовать на двух уровнях распараллеливания вычислительного процесса.

    Рассмотрим возможность его воплощения на симметричных ВС с помощью механизма синхронизации "почтовых ящиков" (рис. 8.13).

    (рис 8.13) Схема data flow с помощью "почтовых ящиков"

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

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

    Отметим также, что целесообразно совмещать принцип data flow с принципом децентрализованных ВС. Это вновь оказывается совместимым с основной идеологией семейства "Эльбрус".

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^