Планирование в многопроцессорных системах (классификация архитектур, коммуникационных сред и вычислительных систем, назначение процессоров, принципы и типы планирования)

42.Планирование в многопроцессорных системах (классификация архитектур, коммуникационных сред и вычислительных систем, назначение процессоров, принципы и типы планирования)

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

Мультипроцессорная система с общей памятью.

С-процессор.

В данном случае все процессы обладают равным доступом ко всей физической памяти. Временные показатели (из трех вариантов) лучшие.

Мультикомпьютерная система с передачей сообщений.

М – память одного компьютера.

С – процессор одного компьютера.

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

Распределенная система.

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

Мультипроцессорные системы.

Основные модели:

1)  Для каждого процессора создается собственная копия ОС. Память распределяется статически. Отсутствует совместное обслуживание процессов и пользование страниц. Необходимо отказаться от поблочного кэша, иначе это приведет к порче данных. Планирование осуществляется отдельно для каждой ОС (каждого процессора).

2)  Модель «хозяин-подчиненный». Создается одна копия ОС и связывается с процессором – хозяином. Только этот процессор может выполнять системные задачи. Остальные процессоры (подчиненные) являются ресурсом для вычислений и могут выполнять только пользовательские задачи.

3)  Симметричные мультипроцессоры. Памяти находится всего одна копия ОС. Все ЦП равнозначны. При системном вызове на каком-то ЦП происходит прерывание и переход в режим ядра для обработки вызова на этом же ЦП. Для обеспечения взаимоисключений необходимо выделить ряд критических областей в самой ОС и связать их мьютексами.

Планирование.

1)  Ведение списка или множества списков для разных приоритетов. Освобождающиеся процессоры выбирают процессы из списка по очереди.

2)  «умное планирование». Если процесс входит в критическую область, захватывается мьютекс, то он не останавливается по кванту времени, а выполняется до освобождения мьютекса.

3)  Родственное планирование. По возможности процессы отправляются на обработку к тому процессору, который обрабатывал их до этого.

4)  Планирование по модели «производитель-потребитель».

Планирование с разделением пространства. Алгоритмы этой группы позволяют выполнять связанные процессы на разных процессорах (бригадное, планирование на основе управления степенью распараллеливания процессов).

Планирование в мультикомпьютерах.

В отличии от мультипроцессорных систем, здесь планирование процессов происходит в два этапа. На первом, каждый новый процесс назначается какому-либо процессору (необходимо обеспечить равномерную нагрузку на все ЦП). На втором, каждый процессор планирует запуск процессов внутри себя по алгоритмам однопроцессорной системы. После назначения процесса какому-либо ЦП этот процесс уже не может выполняться на другом ЦП.

Детерминированный графовый алгоритм. Если известны схемы обмена данными между процессами, то процессы назначаются ЦП таким образом, чтобы минимизировать сетевой трафик. Алгоритм: стоится граф связей между процессами, затем разбивается на подграфы так, чтобы между ними было как можно меньше связей. Распределенный эвристический алгоритм, инициируемый отправителем. Если создающий процесс ЦП перегружен, то он пытается случайным образом найти такой ЦП, который перегружен меньше него, и передать ему процесс. Распределенный эвристический алгоритм, инициируемый получателем. При завершении процесса анализируется загруженность данного процессора. Если он свободен, то ищет случайным образом загруженный процессор и запрашивает процесс на выполнение. Алгоритм торгов. ЦП формирует предложение. Каждому ЦП назначается цена. При создании дочернего процесса, родительский анализирует рынок и выбирает самый дешевый ЦП. Процесс отправляет заявку со своей ценой этому ЦП. Из всех заявок ЦП выбирает самый дорогой и начинает выполнение процесса. Цена процессоров корректируется.

Планирование в распределенных системах.

Направление распределенных систем – осуществление связи в глобальных сетях и предоставления доступа к ресурсам. Поэтому планируются не процессы. А предоставление ресурсов.

Аспекты планирования:

Определение исполнительных ресурсов для каждого задания.

Определение времени, в течение которого ресурсы отводятся заданию.

Метод опережающего планирования.

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

44.Планирование реального времени (Определения СРВ, ОСРВ, временных характеристик, классификации, алгоритмы планирования)

В системах реального времени очень важную роль играют временные показатели.

Жесткие системы реального времени – системы, в которой сроки для каждой задачи известны и строго ограничены.

Гибкие системы реального времени – системы, в которых выход за временные рамки возможен, но нежелателен.

Периодические события возникают регулярно, через определенные интервалы времени.

Апериодические события возникают спонтанно, непредсказуемо.

Требования к ОС реального времени:

Детерминированность – жестко регламентированное время реакции ОС на событие. Предсказуемость – реакция на запрос не зависит от каких-либо внешних факторов. Управляемость со стороны пользователя (создание диапазона приоритетов…) Надежность Восстановление после сбоев.

Планирование в системах реального времени.

Пусть в систему поступает m периодических событий.

Р1…Рm – периоды наступления событий.

С1…Сm – время обработки событий в секундах.

Тогда системы реального времени, удовлетворяющие условию:

называется планируемыми.

Параметры планирования:

1)  Предельный срок завершения процесса

2)  Резерв времени, оставшегося до завершения.

Политика EDF.

На выполнение выбирается тот процесс, у которого предельный срок завершения ближе.

Политика LSF.

Выбирается тот процесс, у которого резерв времени, оставшегося до завершения, меньше.

Политика RMS.

Учитывает наличие периодических процессов. У каждого такого процесса есть параметр – период наступления событий р. Тогда приоритет процесса тем выше, чем больше значение 1/р (частота выполнения процесса). В остальном осуществляется обычное приоритетное планирование.