ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Алгоритм булочної (Bakery algorithm)

Алгоритм Петерсона дає нам рішення задачі коректної організації взаємодії двох процесів. Давайте розглянемо тепер відповідний алгоритм для n взаємодіючих процесів, який отримав назву алгоритм булочної, хоча стосовно наших умов його слід було б швидше назвати алгоритм реєстратури в поліклініці. Основна його ідея виглядає так. Кожен клієнт (він же процес), що знов прибуває, отримує талончик на обслуговування з номером. Клієнт з найменшим номером на талончику обслуговується наступним. На жаль, із-за неатомарності операції обчислення наступного номера алгоритм булочної не гарантує, що у всіх процесів будуть талончики з різними номерами. У разі рівності номерів на талончиках у двох або більш за клієнтів першим обслуговується клієнт з меншим значенням імені (імена можна порівнювати в лексикографічному порядку). Структури даних, що розділяються, для алгоритму – це два масиви

shared enum {false, true} choosing[n];

shared int number[n];

Спочатку елементи цих масивів ініціюються значеннями false і 0 відповідно. Введемо наступні позначення

(а,b) < (с,d), якщо а < з

або якщо а == з і b < d

max(a0, a1 ...., an) – це число до таке, що

до >= ai для всіх i = 0 ...,n

Структура процесу Pi для алгоритму булочної приведена нижче

while (some condition) {

choosing[i]= true;

number[i]= max(number[0] ...,

number[n-1]) + 1;

choosing[i]= false;

for(j = 0; j < n; j++){

while(choosing[j]);

while(number[j]!= 0 && (number[j],j) <

(number[i],i));

}

critical section

number[i]= 0;

remainder section

}

Доказ того, що цей алгоритм задовольняє умовам 1 – 5, виконаєте самостійно як вправу.

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

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

Команда Test-and-Set (перевірити і привласнити 1)

Про виконання команди Test-and-Set, що здійснює перевірку значення логічної змінної з одночасною установкою її значення в 1, можна думати як про виконання функції

int Test_and_Set (int *target){

int tmp = *target;

*target = 1;

return tmp;

}

З використанням цієї атомарної команди ми можемо модифікувати наш алгоритм для змінної-замку, так щоб він забезпечував ті, що взаємовиключають

shared int lock = 0;

while (some condition) {

while(Test_and_Set(&lock));

critical section

lock = 0;

remainder section

}

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

Команда Swap (обміняти значення)

Виконання команди Swap, що обмінює два значення, що знаходяться в пам'яті, можна проілюструвати наступною функцією:

void Swap (int *a, int *b){

int tmp = *a;

*а = *b;

*b = tmp;

}

Застосовуючи атомарну команду Swap, ми можемо реалізувати попередній алгоритм, ввівши додаткову логічну змінну key, локальну для кожного процесу:

shared int lock = 0;

int key;

while (some condition) {

key = 1;

do Swap(&lock,&key);

while (key);

critical section

lock = 0;

remainder section

}

Висновок

Послідовне виконання деяких дій, направлених на досягнення певної мети, називається активністю. Активності складаються з атомарних операцій, що виконуються нерозривно, як одиничне ціле. При виконання декілька активностей в псевдопаралельному режимі атомарні операції різних активностей можуть перемішуватися між собою з дотриманням порядку проходження усередині активностей. Це явище отримала назва interleaving (чергування). Якщо результати виконання декілька активностей не залежать від варіанту чергування, то такий набір активностей називається детермінованим. Інакше він носить назву недетерміновану. Існує достатня умова Бернстайна для визначення детермінованої набору активностей, але воно накладає дуже жорсткі обмеження на набір, вимагаючи практично не взаємодіючих активностей. Про недетермінований набір активностей говорять, що він має race condition (умова гонки, змагання). Усунення race condition можливо при обмеженні допустимих варіантів чергувань атомарних операцій за допомогою синхронізації поведінки активностей. Ділянки активностей, виконання яких може привести до race condition, називають критичними ділянками. Необхідною умовою для усунення race condition є організація того, що взаємовиключає на критичних ділянках: усередині відповідних критичних ділянок не може одночасно знаходитися більш за одну активність.

Для ефективних програмних алгоритмів усунення race condition окрім умови того, що взаємовиключає потрібне виконання наступних умов: алгоритми не використовують спеціальних команд процесора для організації тих, що взаємовиключають, алгоритми нічого не знають про швидкості виконання процесів, алгоритми задовольняють умовам прогресу і обмеженого очікування. Всі ці умови виконуються в алгоритмі Петерсона для двох процесів і алгоритмі булочної – для декількох процесів.

Застосування спеціальних команд процесора, що виконують ряд дій як атомарну операцію, – Test-and-Set, Swap – дозволяє істотно спростити алгоритми синхронізації процесів.

Семафори

Розглянуті в кінці попередньої лекції алгоритми хоча і є коректними, але достатньо громіздкі і не володіють елегантністю. Більш того, процедура очікування входу в критичну ділянку припускає достатньо тривале обертання процесу в порожньому циклі, тобто марну витрату дорогоцінного часу процесора. Існують і інші серйозні недоліки у алгоритмів, побудованих засобами звичайних мов програмування. Допустимо, що в обчислювальній системі знаходяться два взаємодіючі процеси: один з них – H – з високим пріоритетом, інший – L – з низьким пріоритетом. Хай планувальник влаштований так, що процес з високим пріоритетом витісняє низькопріоритетний процес всякий раз, коли він готовий до виконання, і займає процесор на весь час свого CPU burst (якщо не з'явиться процес з ще більшим пріоритетом). Тоді у випадку, якщо процес L знаходиться в своїй критичній секції, а процес H, отримавши процесор, підійшов до входу в критичну область, ми отримуємо тупикову ситуацію. Процес H не може увійти до критичної області, знаходячись в циклі, а процес L не отримує управління, щоб покинути критичну ділянку.

Для того, щоб не допустити виникнення подібних проблем, були розроблені різні механізми синхронізації більш високого рівня. Опису ряду з них – семафорів, моніторів і повідомлень – і присвячена дана лекція.

Семафори

Одним з перших механізмів, запропонованих для синхронізації поведінки процесів, стали семафори, концепцію яких описав Дейкстра (Dijkstra) в 1965 році.

Концепція семафорів

Семафор є цілу змінну, що набуває ненегативних значень, доступ будь-якого процесу до якої, за винятком моменту її ініціалізації, може здійснюватися тільки через дві атомарні операції: P (від данського слова proberen – перевіряти) і V (від verhogen – збільшувати). Класичне визначення цих операцій виглядає таким чином:

P(S): поки S ? 0 процес блокується;

S = S – 1;

V(S): S = S + 1;

Цей запис означає наступне: при виконанні операції P над семафором S спочатку перевіряється його значення. Якщо воно більше 0, то з S віднімається 1. Якщо воно менше або рівне 0, то процес блокується до тих пір, поки S не стане більше 0, після чого з S віднімається 1. При виконанні операції V над семафором S до його значення просто додається 1. У момент створення семафор може ініціалізувати будь-яким ненегативним значенням.

Подібні змінні-семафори можуть з успіхом застосовуватися для вирішення різних завдань організації взаємодії процесів. У ряді мов програмування вони були безпосередньо введені в синтаксис мови (наприклад, в ALGOL-68), в інших випадках реалізуються за допомогою спеціальних системних викликів. Відповідна ціла змінна розташовується усередині адресного простору ядра операційної системи. Операційна система забезпечує атомарність операцій P і V, використовуючи, наприклад, метод заборони переривань на час виконання відповідних системних викликів. Якщо при виконанні операції P заблокованими виявилися декілька процесів, то порядок їх розблокування може бути довільним, наприклад, FIFO.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти