УДК 65.012.122 Н.В. Колесов, д-р техн. наук, Ю.М. Скородумов, М.В. Толмачева, канд. техн. наук, П.В. Юхта, канд. техн. наук (ГНЦ РФ ОАО «Концерн «Центральный научно-исследовательский институт «Электроприбор», Санкт-Петербург); e-mail: kolesovnv@mail.ru АЛГОРИТМ НЕЗАВИСИМОГО НАЗНАЧЕНИЯ ИЕРАРХИЧЕСКИХ ЗАДАНИЙ НА ПРОЦЕССОРЫ В СИСТЕМЕ РЕАЛЬНОГО ВРЕМЕНИ Предложен алгоритм назначения иерархических заданий на процессоры распределенной системы реального времени. <...> Ключевые слова: назначение заданий на процессоры; система реального времени; случайная генерация примеров; иерархическое отношение предшествования. <...> Введение В настоящей работе под назначением понимается процедура соотнесения с каждым процессором некоторого списка решаемых на нем задач. <...> Обычно при разработке таких процедур используется оптимизационная постановка с критериями, обеспечивающими, например, равномерность загрузки процессоров или минимальность необходимого числа процессоров или каналов обмена [1 – 5]. <...> Для систем реального времени при решении задачи назначения дополнительно должно учитываться ограничение, вызванное периодичностью входного потока данных. <...> В момент появления очередной порции данных вычислительная система должна всегда иметь возможность взять их в обработку. <...> В настоящей работе предлагаются алгоритм назначения для систем реального времени, подход к исследованию эффективности алгоритма назначения, а также приводятся результаты этого исследования. <...> Трактуя предметы как задачи, а контейнеры как процессоры, приходим к задаче назначения. <...> Обычно задачу о контейнерах интерпрети28 руют как задачу о назначениях при известном числе процессоров и фиксированных директивных сроках. <...> Для решения задачи о контейнерах предложен целый ряд алгоритмов, которые могут быть интерпретированы как решения задачи назначения. <...> Причем на практике ввиду высокой сложности оптимальных алгоритмов зачастую отдают предпочтение простым эвристическим <...>