69770

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

Лекция

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

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

Украинкский

2014-10-09

34.5 KB

1 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

42307. Дослідження розімкнутої лінійної системи за допомогою середовища MATLAВ 123 KB
  Він повинен включати назва предмета номер і назва лабораторної роботи прізвище та ініціали авторів номер групи прізвище та ініціали викладача номер варіанта короткий опис досліджуваної системи результати виконання всіх пунктів інструкції які виділені сірим фоном див. Визначте смугу пропускання системи найменшу частоту на якій АЧХ стає менше ніж дБ. Побудуйте модель системи в просторі стану.
42308. Хранимые процедуры в MySQL 94 KB
  Введение Хранимые процедуры один из наиболее мощных инструментов предлагаемых разработчикам приложений баз данных MySQL для реализации бизнеслогики. Хранимые процедуры англ stoied proceduies позволяют реализовать значительную часть логики приложения на уровне базы данных и таким образом повысить производительность всего приложения централизовать обработку данных и уменьшить количество кода необходимого для выполнения поставленных задач. Помимо этих широко известных преимуществ использования хранимых процедур общих для большинства...
42309. ОПРЕДЛЕНИЕ УСКОРЕНИЯ СИЛЫ ТЯЖЕСТИ С ПОМОЩЬЮ УНИВЕРСАЛЬНОГО МАЯТНИКА 246 KB
  Пусть – длина нити маятника т – его масса. Если пренебречь силами сопротивления движению то на тело маятника действуют две силы: сила тяжести и натяжение нити . В проекции на направление касательной уравнение движения маятника запишется так: 1 Знак минус возникает потому что проекция силы противоположна направлению отклонения...
42310. ОПРЕДЕЛЕНИЕ ОПТИЧЕСКИХ ХАРАКТЕРИСТИК ОКРАШЕННЫХ РАСТВОРОВ И РАССЕИВАЮЩИХ СРЕД 995.5 KB
  Изучение особенностей прохождения света через оптически однородные и неоднородные среды. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ При прохождении света через среды и через растворы в частности происходит уменьшение его интенсивности вследствие взаимодействия световой волны с частицами вещества. Такое ослабление света называется экстинкцией. Экстинция обусловлена двумя причинами: поглощением и рассеянием света.
42311. ОПРЕДЕЛЕНИЕ КОНЦЕНТРАЦИИ РАСТВОРОВ С ПОМОЩЬЮ КРУГОВОГО ПОЛЯРИМЕТРА 301 KB
  Исследование процесса поляризации света при прохождении его через растворы определение концентрации оптически активного раствора по величине угла поворота плоскости поляризации. Если колебания светового вектора происходят только в одной проходящей через луч плоскости свет называется плоско или линейно поляризованным. Это приборы которые свободно пропускают колебания параллельные плоскости поляризатора и полностью или частично задерживают колебания перпендикулярные его плоскости. Поляризатор частично...
42312. ОПРЕДЕЛЕНИЕ КАЧЕСТВА ОБРАБОТКИ ПОВЕРХНОСТИ С ПОМОЩЬЮ МИКРОИНТЕРФЕРОМЕТРА 672.5 KB
  Теория и опыт неопровержимо свидетельствуют что свет представляет собой электромагнитные волны диапазона 040106 – 076106 метров. Электромагнитные волны – поперечные характеризуются колебанием двух векторов: напряженности электрического поля и магнитной индукции . Колебания электрической и магнитной составляющих поля световой волны происходят в одинаковых фазах во взаимно перпендикулярных плоскостях. Как показывает исследование векторы и единичный вектор направления вдоль которого происходит распространение волны образуют...
42313. ОПРЕДЕЛЕНИЕ ГРАНИЦ СПЕКТРА БЕЛОГО СВЕТА С ПОМОЩЬЮ ДИФРАКЦИОННОЙ РЕШЕТКИ 1.49 MB
  Волновая поверхность падающей волны плоскость щели и экран параллельны друг другу. Поскольку щель бесконечна картина наблюдаемая в любой плоскости перпендикулярной к щели будет одинакова. Разобьем открытую часть волновой поверхности на параллельные краям щели элементарные зоны ширины . Ее можно найти проинтегрировав по всей ширине щели : .
42314. ИЗУЧЕНИЕ ДИСПЕРСИИ СВЕТА 735.5 KB
  Наблюдение дисперсии света определение зависимости показателя преломления от длины волны светового излучения для конкретного вещества. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Одним из наиболее давно известных человеку оптических эффектов является преломление света заключающееся в том что при переходе через границу двух сред луч света скачком меняет свое направление как бы претерпевает излом. Преломление света характеризуется относительным показателем преломления.
42315. ИССЛЕДОВАНИЕ РЕЗОНАНСНЫХ ЯВЛЕНИЙ В ЭЛЕКТРИЧЕСКИХ ЦЕПЯХ 735.5 KB
  Падение напряжения на конденсаторе . Для тока в катушке имеем: сдвиг фаз между током в контуре и напряжением на конденсаторе составляет π 2 ток опережает по фазе напряжения на конденсаторе на π 2 рис. Для напряжения закон изменения имеет вид: При колебаниях происходит периодический переход электрической энергии конденсатора в магнитную энергию катушки . Для определения напряжения на конденсаторе разделим 1 на С имеем Чтобы найти закон изменения силы тока продифференцируем 1 по времени: Обозначим...