69770

Планування у багатопроцесорних системах

Лекция

Информатика, кибернетика и программирование

Головною особливістю планування у багатопроцесорних системах є його двовимірність. У цьому розділі розглянемо деякі підходи до організації планування які враховують ці фактори а у наступному важливе поняття спорідненості процесора що впливає на організацію планування у багатопроцесорних системах.

Украинкский

2014-10-09

34.5 KB

1 чел.

Тема 18. Планування у багатопроцесорних системах

Головною особливістю планування у багатопроцесорних системах є його двовимірність. Крім прийняття рішення про те, який потік потрібно поставити на виконання наступним, необхідно визначити, на якому процесорі він має виконуватися. Крім того, важливо виділяти взаємозалежні потоки, що їх доцільно виконувати паралельно на кількох процесорах, аби їм було простіше взаємодіяти один із одним. У цьому розділі розглянемо деякі підходи до організації планування, які враховують ці фактори, а у наступному — важливе поняття спорідненості процесора, що впливає на організацію планування у багатопроцесорних системах.

Планування з розподілом часу

Найпростішим способом організації багатопроцесорного планування незалежних потоків є використання структури даних для готових потоків, спільної для всіх процесорів. Прикладом такої структури може бути багаторівнева черга, яка використовується під час планування із пріоритетами.

Коли потік на одному з процесорів завершує роботу або призупиняється, цей процесор починає виконувати код планувальника ОС. Планувальник при цьому блокує чергу готових потоків, ставить на виконання потік із найвищим пріоритетом і вилучає його керуючий блок із черги. Наступний за пріоритетом потік почне виконуватися на наступному звільненому процесорі і т. д. Такий підхід називають плануванням із розподілом часу, оскільки, як і у традиційних системах із розподілом часу, щоразу приймають рішення щодо використання одного процесора і виконання одного потоку.

Головним недоліком цього підходу є високий ступінь паралелізму доступу до черги готових потоків, що може стати «вузьким місцем» системи. Є ймовірність того, що більшу частину часу потоки проводитимуть в очікуванні на м'ютексі, який захищає чергу. Крім того, немає можливості уникнути перемикання контексту в разі призупинення потоку і подальшої його міграції на інший процесор.

Планування з розподілом простору

Планування з розподілом часу не пристосоване до організації виконання потоків, пов'язаних між собою, оскільки кожен потік розглядають окремо. Для організації виконання пов'язаних потоків необхідно одночасно розглядати кілька процесорів і розподіляти по них набір потоків. Цей підхід називають плануванням із розподілом простору.

Найефективнішим алгоритмом планування із розподілом простору є бригадне планування (gang scheduling). Цей алгоритм працює так.

  1.   Пов'язані потоки (наприклад, потоки одного процесу) одночасно запускають на виконання на максимально можливій кількості процесорів. Такі потоки становлять бригаду (gang).
  2.   Усі потоки бригади виконуються впродовж однакового для всіх кванта часу.
  3.   Після вичерпання кванта часу відбувається повне перепланування для всіх процесорів. Виконання починають потоки іншої бригади.

Якщо кількість потоків бригади менша, ніж кількість процесорів, виконання можуть почати потоки кількох бригад, якщо більша — виконується частина потоків бригади, а інші будуть заплановані до виконання упродовж наступного кванта часу.

Робота цього алгоритму показана на рис. 20.1. По вертикалі відкладено моменти часу, по горизонталі — процесори. Буквами позначено процеси (бригади), цифрами індексу — номери потоків.

Контрольні питання:

1. Планування з розподілом часу.

2. Планування з розподілом простору.


 

А также другие работы, которые могут Вас заинтересовать

695. Кавказская война 1817-1864 годов 102.5 KB
  Деятельность А.П. Ермолова на Кавказе и формирование идеологии мюридизма. Основные этапы войны, имамат: военно-теократическое государство Шамиля. Завершающий этап Кавказской войны.
696. Заселение Северного Кавказа и политика Российской колонизации 103 KB
  Заселение земель Северного Кавказа калмыками и туркменами в 16-18 веках. Состояние горских обществ накануне российской колонизации: особенности феодальных отношений. Взаимоотношения народов Северного Кавказа с Россией в 16-17 веках, первые русские поселения. Политика России на Северном Кавказе в 18-первой половине 19 веков, возведение оборонительных линий и заселение казачеством северокавказских земель. Становление российской администрации на Северном Кавказе и добровольное присоединение северокавказских народов к России.
697. Использование графики в приложениях Windows Forms 108 KB
  Разработать приложение с графическим интерфейсом пользователя, которое позволяет рисовать заданную геометрическую фигуру в клиентской области главного окна, строит и отображает график заданной функции
698. Международная экономическая интеграция 66.5 KB
  Предпосылки и цели международной интеграции. Этапы международной интеграции. Типы интеграционных объединений. Результаты интеграции. Процесс экономического взаимодействия стран, приводящий к сближению хозяйственных механизмов, принимающий форму межгосударственных соглашений.
699. Получение запросов и отчетов в базе данных MS Access 52 KB
  освоение приемов работы с готовой базой данных по созданию простых и сложных запросов и отчетов. Использование связей между таблицами для получения информации из двух и более таблиц.
700. Общая характеристика WWW 124.5 KB
  История возникновения WWW, понятие гипертекста. Интерфейс Web-приложений при работе в сети Internet. Гипертекстовая информационная система World Wide Web. Базы данных Gopher и поисковая система Veronica.
701. Моделирование прохождения сигнала через некогерентный и когерентный приемные тракты 64.5 KB
  Формирование сигнала на выходе приемника с линейным детектором и с фазовым детектором. Наблюдение интерференции сигналов от целей, разделенных интервалом меньше длительности импульса. Оценка влияния длительности зондирующего импульса на разрешение сигналов по времени.
702. Технология составления интерактивного кроссворда средствами Excel 83 KB
  Набор названия или заголовка кроссворда. Заполнение скелета кроссворда. Создание рамочки клеток кроссворда.(вкладка Главная. Панель Шрифт). Проверки правильности результатов.
703. Реализация модели Ханойские башни 56.5 KB
  Разработать программу на языке C#, реализующую модель игры Ханойские башни. В данной курсовой работе спроектирована и разработана программа на языке C#, которая на основе запрошенных у пользователя входных данных моделирует Ханойские башни или позволяет разложить их вручную.