Схема с симметричным обслуживанием всех процессов

Они самые сложные, но одновременно самые мощные. ОС распоряжается набором одинаковых процессоров, любой из которых может обращаться к любому устройству ввода – вывода и к любому устройству хранения. Такая симметрия позволяет распределять нагрузку более равномерно и точно, чем другие схемы. Поскольку ОС может выполняться одновременно на множестве процессоров, нужно гарантировать взаимное исключение при работе с общими структурами данных. Кроме того, здесь необходимо использовать методы предотвращения аппаратных и программных конфликтов. Многопроцессорные системы в симметричной схеме в целом являются самыми отказоустойчивыми. Главный недостаток – конкуренция при доступе к ресурсам ОС. Необходимо тщательно продумать организацию таких структур, чтобы предотвратить блокирование данных, исключающие выполнение ОС на нескольких процессорах сразу. Чаще всего для минимизации количества конфликтов глобальные структуры данных делятся на отдельные элементы, доступ к которым может осуществляться независимо.

33) Планирование в многопроцессорных системах. Задачно-независимые алгоритмы планирования.

У планирования те же цели, что и в однопроцессорных. Оно должно обеспечивать максимальную производительность и минимальное время реагирования для всех процессов, обеспечивать все процессоры работой, если в системе есть процессы, ожидающие выполнение; должна обеспечивать соблюдение приоритетов, а также определять на каких процессорах должны выполняться процессы. Ну, и кроме того, обеспечивать обязательное выполнение всех без исключения процессов. За счет увеличения требований, для многопроцессорных ОС растет сложность алгоритмов. Когда нужно определить на каком процессоре должен выполняться процесс, планировщик принимает во внимание несколько моментов.

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

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

Во многих алгоритмах планирования для многопроцессорных систем, процессы организуются в глобальную очередь выполнения и каждая такая очередь содержит все процессы системы, которые готовы к выполнению. Глобальные очереди выполнения можно использовать для сортировки процессов по их приоритетам, по задачам к которым они относятся или по тому какой процесс выполняется последним. В системах могут также использоваться процессорные очереди выполнения. Использование таких очередей характерно для больших слабосвязанных систем, в которых нужно добиться как можно большего уровня успешных обращений к КЭШу и локальной памяти. В процессорных очередях выполнения процессы ассоциируются с определенным процессором и система реализует алгоритм планирования для каждого процессора.

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

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

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

2. Круговой алгоритм планирования процессов – RR – помещает все готовые к выполнению процессы в глобальную очередь выполнения. Этот алгоритм работает почти также как и в однопроцессорных. Процесс выполняется в течение максимум 1 кванта времени, а затем приходит очередь следующего процесса. Ранее выполнявшийся процесс помещается в конец глобальной очереди выполнения. Использование этого алгоритма также предотвращает бесконечно откладывание выполнения процесса, но он не обеспечивает высокую степень параллельности или хорошей привязки к процессорам, поскольку игнорирует связи между процессами.

3. SPF. Кратчайший процесс – первым. При использовании алгоритма SPF первым запускается процесс на полное выполнение которого требуется меньше всего времени. Как вытесняющие, так и невытесняющие версии данного алгоритма демонстрируют меньшее время ожидания для интерактивных процессов, чем алгоритм FCFS, поскольку интерактивные процесс обычно являются короткими. Однако, при использование этого алгоритма запуск на выполнение длинного процесса может бесконечно откладываться, если в системе часто появляются более короткие процессы. Как и все задачно - независимые алгоритмы планирования SPF не обращает внимания на параллелизм и привязку к процессорам.

34)Планирование в многопроцессорных системах. Задачно-ориентированные алгоритмы планирования. Алгоритм SNPF. Круговой алгоритм планирования. Алгоритм копланирования. Динамическое разделение.

У планирования те же цели, что и в однопроцессорных. Оно должно обеспечивать максимальную производительность и минимальное время реагирования для всех процессов, обеспечивать все процессоры работой, если в системе есть процессы, ожидающие выполнение; должна обеспечивать соблюдение приоритетов, а также определять на каких процессорах должны выполняться процессы. Ну, и кроме того, обеспечивать обязательное выполнение всех без исключения процессов. За счет увеличения требований, для многопроцессорных ОС растет сложность алгоритмов. Когда нужно определить на каком процессоре должен выполняться процесс, планировщик принимает во внимание несколько моментов.

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

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

Во многих алгоритмах планирования для многопроцессорных систем, процессы организуются в глобальную очередь выполнения и каждая такая очередь содержит все процессы системы, которые готовы к выполнению. Глобальные очереди выполнения можно использовать для сортировки процессов по их приоритетам, по задачам к которым они относятся или по тому какой процесс выполняется последним. В системах могут также использоваться процессорные очереди выполнения. Использование таких очередей характерно для больших слабосвязанных систем, в которых нужно добиться как можно большего уровня успешных обращений к КЭШу и локальной памяти. В процессорных очередях выполнения процессы ассоциируются с определенным процессором и система реализует алгоритм планирования для каждого процессора.

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

Задачно – ориентированные алгоритмы планирования.

Несмотря на то, что задачно – независимые алгоритмы просты в реализации и их использование требует незначительных накладных расходов, они не учитывают моментов специфичных для планирования процессов в многопроцессорных системах. Процессы, интенсивно взаимодействующие друг с другом в таких системах, будут выполняться не одновременно, поэтому будут долго ожидать ответа на свои запросы, и производительность системы будет низкая. Кроме того, у каждого процессора есть собственный КЭШ и процессы из 1 задачи часто обращаются к общим элементам данных памяти, и планирование этих процессов на один и тот же процессор может увеличить чистоту попаданий в кэш и повысить производительность работы с памятью. В целом, задачно - ориентированные алгоритмы планирования пытаются достичь максимального распараллеливания и привязки к процессорам за счет увеличения сложности алгоритмов.

Алгоритм планирования SNPF (наименьшее количество процессов - первым) – это алгоритм может быть как вытесняющим, и так не вытесняющим, но в обоих вариантах он использует глобальную очередь выполнения. Приоритет задачи в такой очереди будет обратно пропорционален количеству процессов в этой задаче. Если задачи с одинаковым количество процессов конкурируют, пытаясь занять один и тот же процессор, задача которая дольше ожидала поучает приоритет. В невытесняющей версии алгоритма, когда процессор становится доступным, из задачи выбирается процесс, стоящий в начале очереди выполнения и выполняется до завершения. В вытесняющей версии, если в очереди появляется новая задача с малым количеством процессов, она получает высокий приоритет и ее процессы начинают выполняться так скоро как это возможно. Алгоритмы SNPF улучшают параллелизм, поскольку процессы из 1 задачи могут выполняться одновременно. Однако, эти алгоритмы не улучшают привязку к процессорам и кроме того, при их использовании возможна ситуация, когда выполнение задачи с большим количеством процессов будет откладываться бесконечно.

Круговой алгоритм планирования задач помещает все готовые к выполнению задачи в глобальную очередь выполнения. Из этой очереди каждая задача назначается для выполнения группе процессоров. У каждой задачи есть собственная очередь процессов. Если в системе есть p процесосров и она использует кванты продолжительности U, то задача получает p*U процессорного времени. Процессы задачи отправляются на выполнение до тех пор, пока задача не израсходует в общей сложности p*u времени, или пока не выполнится до конца, или не заблокируются все ее процессы. Кроме того, алгоритм может поровну разделить p*u времени между всеми процессами задачи, позволяя каждому процессу выполняться, пока он не израсходует свой лимит времени, не завершиться или не заблокируется. Этот алгоритм не допускает бесконечного откладывания выполнения задачи и обеспечивает хороший уровень параллелизма, но дополнительные накладные расходы на переключение контекстов могут снизить производительность системы, использующий данный алгоритм.

Алгоритм совместного планирования

Алгоритмы используют глобальную очередь выполнения с циклическим доступом. Цель этих алгоритмов выполнять процессы из 1 задачи одновременно, чтобы обеспечить их максимальную привязку к процессорам. Неразделяющий алгоритмы планирования помещает процессы из 1 задачи в смежные позиции глобальной очереди выполнения. Планировщик использует окно, размер которого равен количеству процессоров в системе. Все процессы, попадающие в окно, выполняются параллельно в течение максимум 1 кванта. Выполнив обработку группы процессов, окно перемещается к следующей группе, которая тоже выполняется параллельно в течение 1 кванта. Чтобы добиться максимальной загрузки процессоров, используется следующий подход: если процесс, попавший в окно, не может выполняться, то окно расширяется на 1 процесс вправо, и в течение одного кванта времени выполняется также следующий процесс в очереди, даже если он не принадлежит задаче, выполняемой в данный момент. Поскольку в алгоритмах планирования используется циклический доступ к очереди выполнения, при их использовании невозможно бесконечное откладывание выполнения задачи. Процессы из 1 задача чаще всего выполняются одновременно.