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

         

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


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

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

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

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


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

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

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

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

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

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

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

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



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

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




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


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


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

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

    Пусть первоначально, до назначения на процессор задач i-й процессор в цикле длительности k1
    располагал ресурсом Ri1 = k1
    , в цикле длительности k2


    — ресурсом Ri2 = k2
    и т.д. Пусть на процессор для решения выбрана задача
    с временем решения t
    . Пусть она решается в цикле длительности kj
    . Ее назначение не влияет на порядок решения задач в циклах меньшей длительности, т.к. они обладают более высоким приоритетом. Однако при последующем назначении на этот же процессор задач, решаемых в цикле этой и большей длительности, необходимо учитывать решение задачи — с равным или большим приоритетом.

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




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



Таким образом, прежде чем производить назначение другой задачи,?, решаемой в цикле длительности kj ?, на i-й процессор, необходимо проверить, располагает ли он ресурсом Rij
t?? Если располагает, назначение производится, после чего значения ресурса для l
j уточняются.Если не располагает, производится поиск подходящей задачи.

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


Содержание раздела