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


Вирішення проблеми producer-consumer за допомогою семафорів

Одному з типових завдань, що вимагають організації взаємодії процесів, є завдання producer-consumer (виробник-споживач). Хай два процеси обмінюються інформацією через буфер обмеженого розміру. Виробник закладає інформацію в буфер, а споживач витягує її звідти. На цьому рівні діяльність споживача і виробника можна описати таким чином.

Producer: while(1){

produce_item;

put_item;

}

Consumer: while(1){

get_item;

consume_item;

}

Якщо буфер заповнений, то виробник повинен чекати, поки в нім з'явиться місце, щоб покласти туди нову порцію інформації. Якщо буфер порожній, то споживач повинен чекати нового повідомлення. Як можна реалізувати ці умови за допомогою семафорів? Візьмемо три семафори: empty, full і mutex. Семафор full використовуватимемо для гарантії того, що споживач чекатиме, поки в буфері з'явиться інформація. Семафор empty використовуватимемо для організації очікування виробника при заповненому буфері, а семафор mutex – для організації того, що взаємовиключає на критичних ділянках, якими є дії put_item і get_item (операції «покласти інформацію» і «узяти інформацію» не можуть перетинатися, оскільки в цьому випадку виникне небезпека спотворення інформації). Тоді рішення задачі на C-подобном мові виглядає так:

Semaphore mutex = 1;

Semaphore empty = N; /* де N – ємкість буфера*/

Semaphore full = 0;

Producer:

while(1){

produce_item;

P(empty);

P(mutex);

put_item;

V(mutex);

V(full);

}

Consumer:

while(1){

P(full);

P(mutex);

get_item;

V(mutex);

V(empty);

consume_item;

}

Легко переконатися, що це дійсно коректне рішення поставленої задачі. Попутно відмітимо, що семафори використовувалися тут для досягнення двох цілей: організації того, що взаємовиключає на критичній ділянці і взаимосинхронизации швидкості роботи процесів.

Монітори

Монітори

Хоча рішення задачі producer-consumer за допомогою семафорів виглядає достатньо витончено, програмування з їх використанням вимагає підвищеної обережності і уваги, ніж частково нагадує програмування на мові Асемблера. Допустимо, що в розглянутому прикладі ми випадково поміняли місцями операції P, спочатку виконавши операцію для семафора mutex, а вже потім для семафорів full і empty. Допустимо тепер, що споживач, увійшовши до своєї критичної ділянки (mutex скинутий), виявляє, що буфер порожній. Він блокується і починає чекати появи повідомлень. Але виробник не може увійти до критичної ділянки для передачі інформації, оскільки той заблокований споживачем. Отримуємо тупикову ситуацію.

У складних програмах провести аналіз правильності використання семафорів з олівцем в руках стає дуже непросто. В той же час звичайні способи відладки програм часто не дають результату, оскільки виникнення помилок залежить від interleaving атомарних операцій, і помилки можуть бути трудновоспроизводимы. Для того, щоб полегшити роботу програмістів, в 1974 році Хором (Hoare) був запропонований механізм ще більш високого рівня, ніж семафори, що отримав назву моніторів. Ми з вами розглянемо конструкцію, декілька що відрізняється від оригінальної.

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

monitor monitor_name {

опис внутрішніх змінних ;

void m1(...){...

}

void m2(...){...

}

...

void mn(...){...

}

{

блок ініціалізації

внутрішніх змінних;

}

}

Тут функції m1..., mn є функціями-методами монітора, а блок ініціалізації внутрішніх змінних містить операції, які виконуються один і лише один раз: при створенні монітора або при найпершому виклику якої-небудь функції-методу до її виконання.

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

Проте одних тільки взаємовиключають недостатньо для того, щоб в повному об'ємі реалізувати вирішення завдань, що виникають при взаємодії процесів. Нам потрібні ще і засоби організації черговості процесів, подібно до семафорів full і empty в попередньому прикладі. Для цього в моніторах було введено поняття умовних змінних (condition variables) (у деяких російських виданнях їх ще називають змінними стани), над якими можна здійснювати дві операції wait і signal, частково схожі на операції P і V над семафорами.

Якщо функція монітора не може виконуватися далі, поки не наступить деяка подія, вона виконує операцію wait над якою-небудь умовною змінною. При цьому процес, що виконав операцію wait, блокується, стає неактивним, і інший процес отримує можливість увійти до монітора.

Коли очікувана подія відбувається, інший процес усередині функції-методу здійснює операцію signal над тією ж самою умовною змінною. Це приводить до пробудження раніше заблокованого процесу, і він стає активним. Якщо декілька процесів чекали операції signal для цієї змінної, то активним стає тільки один з них. Що можна зробити для того, щоб у нас не опинилося двох процесів, що розбудив і пробужденного, одночасно активних усередині монітора? Хор запропонував, щоб пробужденный процес пригнічував виконання процесу, що розбудив, поки він сам не покине монітор. Декілька пізніше Хансен (Hansen) запропонував інший механізм: процес, що розбудив, покидає монітор негайно після виконання операції signal. Ми дотримуватимемося підходу Хансена.

Необхідно відзначити, що умовні змінні, на відміну від семафорів Дейкстри, не уміють запам'ятовувати передісторію. Це означає, що операція signal завжди повинна виконуватися після операції wait. Якщо операція signal виконується над умовною змінною, з якою не пов'язано жодного заблокованого процесу, то інформація про подію, що відбулася, буде загублена. Отже, виконання операції wait завжди приводитиме до блокування процесу.

Давайте застосуємо концепцію моніторів до рішення задачі виробник-споживач.

monitor ProducerConsumer {

condition full, empty;

int count;

void put() {

if(count == N) full.wait;

put_item;

count += 1;

if(count == 1) empty.signal;

}

void get() {

if (count == 0) empty.wait;

get_item();

count -= 1;

if(count == N-1) full.signal;

}

{

count = 0;

}

}

Producer:

while(1){

produce_item;

ProducerConsumer.put();

}

Consumer:

while(1){

ProducerConsumer.get();

consume_item;

}

Легко переконатися, що приведений приклад дійсно вирішує поставлену задачу.

Реалізація моніторів вимагає розробки спеціальних мов програмування і компіляторів для них. Монітори зустрічаються в таких мовах, як паралельний Евклід, паралельний Паськаль, Java і так далі Емуляція моніторів за допомогою системних викликів для звичайних широко використовуваних мов програмування не так проста, як емуляція семафорів. Тому можна користуватися ще одним механізмом з тими, що прихованими взаємовиключають, механізмом, про який ми вже згадували, – передачею повідомлень.

Повідомлення

Повідомлення

Для прямої і непрямої адресації досить два примітиви, щоб описати передачу повідомлень по лінії зв'язку – send і receive. У разі прямої адресації ми позначатимемо їх так:

send(P, message) – послати повідомлення message процесу P;
receive(Q, message) – отримати повідомлення message від процесу Q.

У разі непрямої адресації ми позначатимемо їх так:

send(A, message) – послати повідомлення message в поштову скриньку A;
receive(A, message) – отримати повідомлення message з поштової скриньки A.

Примітиви send і receive вже мають прихований від наших очей механізм того, що взаємовиключає. Більш того, в більшості систем вони вже мають і прихований механізм блокування при читанні з порожнього буфера і при записі в повністю заповнений буфер. Реалізація рішення задачі producer-consumer для таких примітивів стає непристойно тривіальною. Треба відзначити, що, не дивлячись на простоту використання, передача повідомлень в межах одного комп'ютера відбувається істотно повільніше, ніж робота з семафорами імоніторами.

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

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