> Б) Розробити програму запобігання взаємних блокувань процесів в обчислювальній системі при наявності одного ресурсу кожного типу.
Приклад алгоритму виявлення блокувань
при наявності декількох екземплярів ресурсів кожного типу.
Для виявлення взаємних блокувань в цьому випадку використовуються матричні операції. Нехай, наприклад, є n процесів, які захоплюють і вимагають ресурси P1, ..., Pn. Нехай є m класів ресурсів, при цьому усередині кожного класу є кілька ресурсів:
E1 клас 1
E2 клас 2
Ei клас C
...................
Em клас m
Завдання передбачає наступні поняття (рис. 3.5):
Вектор існуючих ресурсів E (E1, E2, ..., Em);
Вектор доступних ресурсів A (A1, A2, ..., Am), Ai в цьому векторі дорівнює кількості примірників ресурсів класу i доступних в поточний момент часу;
C - матриця поточного розподілу ресурсів (якому процесу які ресурси належать), C (ij) - кількість примірників ресурсу j, яке займає процес P (i).
R - матриця запитів ресурсів (який процес який ресурс запросив), (ij) - кількість примірників ресурсу j, яке хоче отримати процес P (i).
Рис. 3.5. Вектори ресурсів обчислювальної системи
Загальна кількість ресурсів дорівнює сумі зайнятих і вільних ресурсів.
Алгоритм виявлення взаімоблокіровок заснований на порівнянні векторів:
. Знаходиться процес Pi для якого i-й рядок матриці R? A.
. Якщо такий процес знайдений, то додаємо i-й рядок матриці C до вектора A і повертаємося до кроку 1.
. Якщо таких процесів немає, то робота програми закінчується, тому відбувається взаємне блокування.
Для реалізації роботи цього алгоритму була розроблена програма (малюнок 3.6).
Приклад. Нехай є 4 класу ресурсів - плоттери, сканери, принтери, HDD і 4 процесу - Р 1, Р 2, Р 3, Р 4.
Е=(4 4 3 1) - вектор існуючих ресурсів.
А=(2 +1 0 1) - вектор доступних ресурсів.
- матриця поточного розподілу ресурсів
- матриця запитів ресурсів
Прямуємо алгоритмом:
Знаходимо процес Pi, для якого i-й рядок матриці R? A. З усіх 4-х процесів цій умові задовольняють два процеси - Р1, Р2.
Р1R1? A1 2000 lt; +2101
Р2R2? A2 +0100 lt; +2101
Додаємо 1-й рядок матриці C до вектора A.
С1 + А=(2 0 1 0) + (2 1 0 1)=4 1 1 1 А=(4 +1 +1 +1)
маркіруючи першому процес - Р1.
Знову шукаємо процес Pi, для якого i-й рядок матриці R? A. Таких процесів дві - Р2, Р3.
Додаємо 2-й рядок матриці C до вектора A.
С2 + А=(0 2 1 0) + (4 1 1 1)=4 3 2 1 А=(4 3 2 1)
маркіруючи другий процес - Р2.
Шукаємо процес Pi, для якого i-й рядок матриці R? A. Таких процесів дві - Р3, Р4.
Додаємо третій рядок матриці C до вектора A.
С3 + А=(0 1 0 0) + (4 3 2 1)=4 4 2 1 А=(4 2 квітня 1)
маркіруючи 3-ой процес - Р3.
Додаємо 4-й рядок матриці C до вектора A.
С4 + А=(0 0 1 0) + (4 4 2 1)=4 4 3 1
маркіруючи останній четвертий процес - Р4.
виконати всі 4 процесу - Р1, Р2, Р3, Р4.
Перевірка: А=(4 4 3 1)=Е=(4 4 3 1). Після виконання всіх чотирьох процесів вектор доступних ресурсів дорівнює вектору існуючих ресурсів.
Рис. 3. Виявлення взаємних блокувань процесів в обчислювальній системі за наявності декількох ресурсів кожного типу.
Завдання №4
Вихідні дані. Дана симетрична мультипроцесорна система. Всі N=4 процесорів системи незалежні, однотипні і функціонально еквівалентні. Гранична швидкість обміну по шині V=266, причому кожен процесор при вирішенні задачі вимагає швидкості обміну P=70 мбайт/сек.
Завдання:
) Розробити структурну і функціональну схеми арбітражу зі зміною пріоритетів для мультипроцесорної системи і описати алгоритм її роботи. Децентралізований арбітраж.
) Визначити максимальне число процесорних модулів, що підключаються до шини без досягнення шиною насичення.
) Запропонувати для схеми методи подолання ефекту насичення в шині.
Ріс.4.1.Структурная схема
Максимальне число процесорних модулів, підключаемих до шини без досягнення ефекту насичення розраховується за формулою:
N=V/P
N=266/70=3
