2015-01-30
344
Правильное разделение алгоритма между несколькими ЦСП в многопроцессорной системе является одной из важнейших предпосылок повышения ее производительности. Основной целью при этом является баланс загруженности процессоров, т.е. минимизация времени ожидания процессором завершения другой задачи. Тот факт, что к большинству алгоритмов ЦОС предъявляются требования выполнения действий всегда в течение одного и того же постоянного интервала времени, упрощает разбиение алгоритма на подзадачи. Время выполнения каждой подзадачи может быть оценено и принято постоянным. Это дает возможность статического распределения загрузки процессоров (до начала выполнения) и позволяет отказаться от использования сложных алгоритмов динамического распределения подзадач на процессоры по время функционирования системы.
Для оценки загруженности каждого процессора может использоваться диаграмма Ганта. Для ее построения необходимо разбить алгоритм ЦОС на подзадачи и определить связи между задачами. Если подзадача доступна в текущем списке задач, то для ее назначения на процессор может использоваться управляющий алгоритм Грэхама. Суть этого алгоритма заключается в том, что если процессор не загружен работой, то на него будет поставлена очередная задача в списке задач. Если поставленная задача обработки сигнала является детерминированной, то алгоритм Грэхама может использоваться для статического распределения задач по процессорам. Диаграмма Ганта распределения задач по процессорам показывает, какие процессоры незагружены (ожидают завершения выполнения другой задач(и)), а какие перегружены. На рис. 4 приведены примеры диаграмм Ганта, иллюстрирующих назначение 9 задач на 2 и 3 процессора (рис. 4а и 4б соответственно) в соответствием с алгоритмом Грэхама.
|
|
|
| Процессор 1 | T1 | T9 | ||||||||||
| Процессор 2 | T2 | T4 | T5 | T7 | ||||||||
| T3 | --- | T6 | T8 |
а
| Процессор 1 | T1 | T8 | --- | ||||||||||||
| Процессор 2 | T2 | T5 | T9 | ||||||||||||
| T3 | T6 | --- | |||||||||||||
| Процессор 3 | T4 | T7 | --- |
б
Зависимости между задачами:
- задачи упорядочены от 1 до 9 по приоритету в убывающем порядке;
- задача 1 должна завершиться до начала выполнения задачи 9;
- задача 4 должна завершиться до начала выполнения задач 5,6,7,8
Рис.4
Вторая диаграмма на рис.4 иллюстрирует пример, когда добавление четвертого процессора в систему увеличивает суммарное время выполнения задачи. Причиной этого является то, что задача, имеющая наибольшую длительность обслуживания, имеет низший приоритет и короткие подзадачи (5, 6, 7, 8) завершаются первыми. Поэтому подзадача № 9 начинает выполняться позже и суммарное время выполнения алгоритма увеличивается.
