|
1 т' т Т, k Т, Т 1 1 1 1 0 2 4 1 6 8 1 1 1 1 0 12 14 16 1 8 2 1 1 0 22 24 (а) Т, т? 1 1 1 т. Т6 1 1 Рисунок 2.1.2 Определение времени потока (по Ганту, альтернативное представление SPT) Например, на рисунке 2.1.2, b F = 16. Если задачи на этом рисунке перегруппировать в форму SPT плана, как показано на рисунке 2.1.2, с, то F = 11. Отсюда вывод: упорядочивание наидлиннейшего времени обработки (longest-processing-time sequencing, LPT) максимизирует то, что SPT минимизирует. Процедуры планирования, формирующие противоположные последовательности, называются противоположными. В рамках рассмотрения одноресурсных моделей следует также отметить процессы с жесткими ограничениями и конвейерные модели. В первом случае, предмет обсуждения так называемое критичное по времени управление цикличными/периодичными процессами в АСУ. Процесс называется критичным по времени, если для задач, входящих в него, определены частоты и времена выполнения. Каждый запуск задачи должен 40 |
о Ef I I I I г 8 10 12 14 16 I T~ 18 20 22 24 (a) I 26 (b) (c) Рис. 2.4. Определение времени потока (по Ганту, альтернативное представление SPT) На диаграмме Ft время потока i-й задачи в последовательности определяется как Л = 2>(/)> /=1 где p(f) представляет время обработки задачи, занимающую у-ю позицию в плане. Другими словами, время потока задачи это просто время завершения выполнения задачи. Среднее время потока определяется как /=1 Например, на рис. 2.4 b, F = 16. Если задачи на этом рисунке перегруппировать в форму SPT плана, как показано на рис. 2.4, с, то F= 11. Отсюда вывод: упорядочивание наидлиннейшего времени обработки (longest-processing-time sequencing, LPT) максимизирует то, что SPT минимизирует. Процедуры планирования, формирующие противоположные последовательности, называются противоположными. 46 В рамках рассмотрения однопроцессорных следует также отметить мультипрограммирование с жесткими ограничениями и конвейерные модели. В первом случае, предмет обсуждения так называемое критичное по времени управление цикличными/периодичными процессами в АСУ. Процесс называется критичным по времени, если для задач, входящих в него, определены частоты и времена выполнения. Каждый запуск задачи должен происходить в границах временного интервала, определенного частотой, либо совершаться по сигналу внешнего прерывания. Набор этих процессов может представлять вычисления, которые необходимо выполнить для управления конкретной системой реального времени. Примером такой реальной среды, в работе будет представлена среда автоматизированной системы технической диагностики электронных устройств. С точки зрения вычислительной загрузки, отличие систем такого рода от обычной мультипрограммной системы заключается в том, что заранее известен характер необходимых вычислений. Кроме того, реакция системы обязательно должна происходить внутри строго установленных пределов; также не допустимо говорить (в отличие от типичной системы), что «большинство откликов информационно-управляющей системы (ИУС) такого рода должны произойти в течение х секунд». В дальнейшем обсуждение вопроса критичных по надежности исполнения распределенных алгоритмов будем вести на основе модели критичного по времени процесса (time-critical process, TCP), изображенного на рис. 2.5. у—Interrupts—v -ЕРис. 2.5. Модель процесса критичного по времени (TCP) В этой модели Е представляет назначенное время выполнения одной итерации процесса. Время Т, иногда называемое структурным временем, 47 |