Системы жесткого реального времени. Князев В.Н - 4 стр.

     1.    Матрица смежности B = || bij || , i,j=1,...,n, задающая структуру
графа совокупности работ; n - число вершин графа.
     Элементы матрицы определяются следующим образом:

                 1, если Г(i) = {j}, т.е. из i-ой вершины есть
       bij = непосредственный переход в j-ую вершину;
                 0 - в противном случае.
       2.       Вектор времен T = || ti || , i=1,...,n, задающий целочисленные
значения времен выполнения работ Ai (i=1,...,n) на процессорах ВС.
       Кроме того, эвристический метод использует матрицу достижимости
C = || cij || , i,j=1,...,n, являющуюся производной матрицей от матрицы
смежности.
       Элементы матрицы достижимости определяются следующим обра-
зом:
                       1, если Гk(i) = {j}, k∈{1,2,...,n-1}, т.е. из
      cij   =    i –ой вершины есть путь в j-ую вершину ;
                  0 - в противном случае.
      Результатом составления расписания являются временные диаграм-
мы Ганта для каждого процессора ВС реального времени, которые ото-
бражают на временной оси порядок выполнения соответствующих работ и
простоев процессоров и определяют длину расписания ω.
      Суть эвристического метода составления списочных расписаний для
ВС реального времени заключается в следующем.
      В нулевой момент времени список L просматривается слева направо
в поисках открытых работ, т.е. работ, готовых к выполнению. Соответст-
вующий столбец матрицы достижимости в этом случае является нулевым.
      Первая найденная открытая работа назначается для выполнения без
прерываний на первый процессор, и по завершении ее выполнения обнуля-
ется соответствующая строка матрицы достижимости.
      Вообще, в каждый целочисленный момент времени, если имеется
свободный от выполнения работы процессор, список L просматривается
снова. Если нет ни одной работы, готовой к выполнению, то процессор
простаивает. Если же есть несколько свободных от выполнения работ про-
цессоров, то первая найденная открытая работа назначается на процессор с
меньшим номером.
      Расписания, полученные таким способом, называются списочными
расписаниями.




                                      4