|
монотонными приоритетами (rate monotonic priority, RMP). Для этой схемы верхняя граница коэффициента использования равна U = п(2и" -1), где п количество TCP процессов. Этот результат означает, что допустимая сумма факторов индивидуальной загрузки должна быть значительно меньше 1, чтобы гарантировать, что каждый процесс будет завершен вовремя. При большом количестве задач ресурс должен быть недозагружен более чем на 30 %. Эта схема является оптимальной с условием, что для некоторого набора задач план не может быть сформирован никаким правилом назначения с фиксированными приоритетами, если он не может быть сформирован RMP схемой. Рассмотренное правило назначения является фиксированным или статичным правилом, в котором относительные приоритеты задач основаны на частотах задач и не меняются во время выполнения. Прежде чем закончить рассмотрение одноресурсных планов и перейти к многоресурсным, остановимся кратко на классе, так называемых, конвейерных планов, в которых более чем один ресурс включен в совместное выполнение ряда задач и в которых существует последовательная взаимосвязь между ресурсами. Это, однако, не соответствует случаю многоресурсного планирования. Просто, задача, которую необходимо выполнить, должна быть обслужена сначала одним из ресурсов, а потом другими. Это чередование должно соблюдаться для всех задач, входящих в план, но никакого требования идентичности ресурсов не вводится. 2.1.3. Мультиресурсные модели Здесь мы рассмотрим планы формирования распределенных процессов, в которых для оптимизации показателей производительности используется 43 |
Согласно методике Серлина эффективным алгоритмом распределения является тот, который предоставляет достаточно процессорного времени TCP для своевременного выполнения при уменьшении длительности вынужденных простоев. Длительность вынужденного простоя это время, в течение которого работа процессора должна быть приостановлена для разрешения внутренних конфликтов. Лью и Лайленд пытались найти наибольший возможный коэффициент использования при условии завершения всех задач в рамках, временных ограничений. Коэффициент использования U (названный Серлином коэффициентом загрузки) для п TCP процессов определяется как »=1 В данном случае (однопроцессорное планирование) могут быть получены оптимальные решения для схемы с фиксированными приоритетами, в которой, например, задание с частотой £ имеет более высокий приоритет, чем задание с частотой fc если f> Такую схему называют схемой назначениями с монотонными приоритетами (rate monotonic priority, RMP), или интеллектуальным алгоритмом с фиксированными приоритетами (intelligent fixed priority (IFP) algorithm). Для этой схемы верхняя граница коэффициента использования равна U = п(211п -1), где п количество TCP процессов. Этот результат означает, что допустимая сумма факторов индивидуальной загрузки должна быть значительно меньше 1, чтобы гарантировать, что каждый процесс будет завершен вовремя. При большом количестве задач процессор должен быть недозагружен более чем на 30 %. Эта схема является оптимальной с условием, что для некоторого набора задач план не может быть сформирован никаким правилом назначения с фиксированными приоритетами, если он не может быть сформирован IFF или RMP алгоритмами. 49 Рассмотренное правило назначения является фиксированным или статичным правилом, в котором относительные приоритеты задач основаны на частотах задач и не меняются во время выполнения. Прежде чем закончить рассмотрение однопроцессорных планов и перейти к; многопроцессорным, остановимся кратко на классе, так называемых, конвейерных планов, в которых более чем один процессор включен в совместное выполнение ряда задач и в которых существует последовательная, взаимосвязь между процессорами. Это, однако, не соответствует случаю многопроцессорного планирования. Просто, задача, которую необходимо выполнить, должна быть обслужена одним из процессоров, а потом другими. Это чередование должно соблюдаться для всех задач, входящих в план, но никакого требования идентичности процессоров не вводится. 2.1.3. Мультипроцессорные модели В этом параграфе мы рассмотрим планы формирования распределенных алгоритмов, в которых для оптимизации показателей производительности используется более одного процессора: В первой части обычные среды, для которых осуществляется формирование алгоритмов преобладают обсужденные ранее параметры, используемые в* большинстве работ по планированию. То есть исследуется ряд идентичных процессоров, набор задач с равными или* неравными временами обслуживания и (возможно, пустой) порядок предшествования. Рассматриваются схемы как с приоритетами, так и без приоритетов. Во второй части рассматривается формирование распределенных алгоритмов для особых сред планирования, а именно, вводятся дополнительные требования и ограничения различного вида: ограниченное число ресурсов для каждого из класса, периодически выполняемые работы с указанным временем инициирования и завершения и присутствие промежуточных ограничений внутри распределенных планов. 50 |