Совместное планирование

Совместное планирование — это принцип одновременного в параллельных системах запуска связанных процессов на разных процессорах (параллельно ) . Для реализации этого существуют различные конкретные реализации.

Если приложение состоит из набора процессов, тесно работающих вместе, и если некоторые, но не все процессы запланированы для выполнения, выполняющиеся процессы могут попытаться связаться с теми, которые не выполняются, что приведет к их блокировке. В конечном итоге выполнение других процессов будет запланировано, но к этому времени ситуация может измениться на противоположную, и эти процессы также будут блокировать ожидание взаимодействия с другими. В результате приложение выполняет работу со скоростью не более одного межпроцессного взаимодействия за интервал времени и будет иметь низкую пропускную способность и высокую задержку .

Выполнение

Совместное планирование состоит из двух идей:

• При планировании любого процесса в связанной группе запланируйте выполнение всех них, чтобы они могли эффективно взаимодействовать.
• Если процесс в группе блокируется при взаимодействии с другим процессом в группе, не удаляйте его из процессора. Вместо этого оставьте его состояние загруженным в процессоре на короткое время, предполагая, что он вскоре получит ответ. Если это время истекло, а процесс все еще не стал работоспособным, предположим, что он будет спать в течение длительного времени, и перепланируйте процессор.

Некоторые методы копланирования демонстрируют фрагменты процессов, которые не выполняются одновременно с остальной частью копланированного набора. Эти алгоритмы обычно минимизируют появление этих фрагментов. Групповое планирование — это более строгий вариант совместного планирования, который полностью запрещает фрагменты.

Виды совместного планирования

Исследователи классифицировали три типа совместного планирования: явное совместное планирование , локальное планирование и неявное или динамическое совместное планирование .

Явное совместное планирование требует, чтобы вся обработка происходила одновременно, и обычно реализуется посредством глобального планирования на всех процессорах. Конкретный алгоритм известен как групповое планирование .

Локальное совместное планирование позволяет отдельным процессорам планировать обработку независимо.

Динамическое (или неявное) совместное планирование — это форма совместного планирования, при которой отдельные процессоры по-прежнему могут планировать обработку независимо, но они принимают решения по планированию совместно с другими процессорами.

История

Термин «совместное планирование» был введен Оустерхаутом (1982) . Исходное определение состоит в том, что рабочий набор процессов должен быть запланирован (запланирован для одновременного выполнения), чтобы параллельная программа могла работать .

См. также

• Планирование банд

Примечания

• Оустерхаут, Дж. К. (1982). «Методы планирования для параллельных систем» (PDF) . Материалы Третьей международной конференции по распределенным вычислительным системам : 22–30.