69770

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

Лекция

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

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

Украинкский

2014-10-09

34.5 KB

1 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

30506. Процессы и потоки. Объекты межпроцессной синхронизации. Понятие гонок и взаимной блокировки 56.12 KB
  Понятие гонок и взаимной блокировки Доска Ответ В компьютерных науках поток выполнения англ. Реализация потоков выполнения и процессов в разных операционных системах отличается друг от друга но в большинстве случаев поток выполнения находится внутри процесса. Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы такие как память тогда как процессы не разделяют этих ресурсов. В частности потоки выполнения разделяют инструкции процесса его код и его контекст значения...
30507. Процессы и потоки. Объекты межпроцессорной синхронизации. Понятие гонок и взаимной блокировки 24.85 KB
  Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы такие как память тогда как процессы не разделяют этих ресурсов. dedlock ситуация в многозадачной среде или СУБД при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов занятых самими этими процессами. Процессы в текущий момент удерживают полученные ранее ресурсы могут делать запросы на получение новых ресурсов. Условие отсутствия принудительного освобождения ресурсов англ.
30508. Сравнение компонентно-объектной модели, среды .NET и Java. Их преимущества и недостатки 25.5 KB
  Идеология .NET заключается в максимально полном использовании ресурсов платформы, на которой работает среда выполнения .NET. В результате возможности Java ограничены усредненным набором функций API виртуальной машины, и программистам на Java недоступны все функции той или иной платформы, на которой выполняются приложения
30510. Определение иерархической и реляционной модели, их достоинства и недостатки. Основные операции реляционной алгебры. Общий процесс преобразования ER-диаграммы в реляционную схему 87.94 KB
  Пример табличной формы представления отношения Номер зачетной книжки Дисциплина Оценка C12298 Программирование 5 C1229891 Дискретная математика 4 C14407 Программирование 3 . Элементы отношения называют кортежами или записями. Каждый кортеж отношения соответствует одному экземпляру сущности определённого типа. Операции реляционной алгебры ВЫБОРКАНа входе используется одно отношение результат новое отношение построенное по той же схеме содержащее подмножество кортежей исходного отношения удовлетворяющих условию выборки.
30511. Структурированный язык запросов SQL. История создания языка SQL. Подмножество SQL - Data Definition Language (DDL). Модификация схем базы данных . Стандартные типы данных. Вычисляемые столбцы. Подмножество SQL - Data Query Language (DQL) 65.5 KB
  Модификация схем базы данных . Стандартные типы данных. Доска то что выделено курсивом устно Язык SQL имеет два основных компонента: язык DDL Dt Definition Lnguge предназначенный для определения структур базы данных; язык DML Dt Mnipultion Lnguge предназначенный для выборки и обновления данных. Для определения данных символьного типа используется следующий формат: CHRCTER [VRYING] [length] Битовые данные тип bit Битовый тип данных используется для определения битовых строк т.
30512. Синтаксис оператора SELECT. Обзор его подразделов (списка выборки, секций FROM, WHERE, GROUP BY, HAVING, OREDER BY).. Способы упорядочивания итогового набора в секции OREDER BY 23.79 KB
  SELECT селект оператор DML языка SQL возвращающий набор данных выборку из базы данных удовлетворяющих заданному условию. При формировании запроса SELECT пользователь описывает ожидаемый набор данных: его вид набор столбцов и его содержимое критерий попадания записи в набор группировка значений порядок вывода записей и т. Синтаксис оператора SELECT SELECT column_list FROM tble_nme [WHERE условие] [GROUP BY условие] [HVING условие] [ORDER BY условие] SELECT Ключевое слово которое сообщает базе данных о том что оператор является...
30513. Разделение ресурса 68.3 KB
  Способы решения проблемы гонок: Локальная копия Синхронизация Метод блокирующей переменной Метод строгого чередования Алгоритм Деккера Алгоритм Петерсона Комбинированный способ Локальная копия Самый простой способ решения копирование переменной x в локальную переменную. В общем виде алгоритм выглядит следующим образом: Поток: while stop { synchronizedSomeObject { {criticl_section} } } Метод блокирующей переменной Суть метода состоит в том что если значение этой переменной равно например 1 то ресурс занят другим...