Голодування

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

1. Потік T_R1 відкриває блокування для читання L.
2. Потік T_W1 намагається відкрити блокування L для записування і призупиняється.
3. Потік T_R2 відкриває блокування L для читання.
4. Потік T_R1 виконує операцію закриття блокування, але блокування L залишається зайнятим T_R2.
5. Потік T_R3 відкриває блокування L для читання.
6. Потік T_R2 виконує операцію закриття блокування, але блокування L залишається зайнятим T_R3 (і т.д.).

У результаті додаткові потоки-читачі захоплюватимуть блокування L до того, як його звільнять усі попередні читачі. Це означає, що L ніколи повністю не звільниться, і потік записувач T_W1 ніколи не отримує керування. Таку ситуацію, як і під час планування, називають голодуванням.

Для блокувань із кращим записуванням голодування потоку-записувача бути не може. У нашому випадку потік T_R2 на кроці 3 призупиниться і після закриття блокування потоком T_R1 на кроці 4 потік T_W1 дістане можливість виконуватися. З іншого боку, у цьому випадку за певних умов можна отримати голодування потоків-читачів.

Остаточного розв’язання проблеми голодування не запропоновано, рекомендують ретельно зважувати можливість використання різних типів блокувань і розраховувати можливість навантаження, яке може призвести до голодування.

5.3.5. Синхронізація за принципом бар’єра

Іноді буває зручно розбити задачу (наприклад, складний розрахунок) на кілька послідовних етапів, при цьому виконання наступного етапу не може розпочатися без цілковитого завершення попереднього. Якщо на кожного етапі роботу розподілити по окремих потоках, які паралельно виконуватимуть кожен свою частину, виникає запитання: яким чином дочекатися завершення всіх потоків попереднього етапу до початку наступного?

Звичайне використання thread_join() тут не підходить, тому що приєднати можна якийсь конкретний потік, а не цілий набір потоків. Для розв’язання цього завдання запропоновано концепцію спеціального синхронізаційного об’єкта – бар’єра.

Бар’єр – це блокування, яке зберігають доти, поки кількість потоків, що очікують, не досягне деякого наперед заданого числа, після чого всі ці потоки продовжують своє виконання.

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

Операції бар’єра

Розглянемо дві операції бар’єра.

· Ініціалізація бар’єра (barrier_init). Параметром даної операції є n – кількість потоків, які ми синхронізуємо на цьому бар’єрі. Внутрішній лічильник призупинених потоків покладають рівним нулю. Значення n після виклику barrier_init міняти не можна.

· Очікування на бар’єрі (barrier_wait). Внаслідок даної операції лічильник призупинених потоків збільшують на одиницю. Якщо він не досягнув n, цей потік призупиняють(кажуть, що він «очікує на бар’єрі»). Якщо ж після збільшення лічильник виявляється рівним n (досягнуто максимальної кількості потоків для бар’єра) усі потоки, що очікували на бар’єрі, поновлюються (ситуація переходу бар’єра), при цьому одному з них повертають спеціальне значення (зазвичай -1), а іншим – нуль. Надалі потік, що отримав це спеціальне значення, може зробити деякі підсумкові дії після переходу бар’єра. При переході бар’єра його «скидають» (внутрішній лічильник призупинених потоків знову покладають рівним 0) і він починаючи із наступної операції barrier_wait блокуватиме потоки знову.

Ось псевдокод прикладу використання бар’єра:

barrier_t barrier_step; //бар’єр етапу

void thread_fun() { //функція потоку, розбита на етапи

int res;

step1(); //виконання дій етапу 1

res = barrier_wait(barrier_step); //очікування завершення етапу 1

if (res == -1) step1_done();

step2();//виконання дій етапу 2

res = barrier_wait(barrier_step); // очікування завершення етапу 2

if (res == -1) step2_done();

//тощо

}

//n – кількість потоків для виконання поетапної задачі

void run() {

thread_t threads[n];

barrier_init(barrier_step, n); //бар’єр для n потоків

for (i=0; i<n; i++)

threads[i] = thread_create(thread_fun); //створюємо n потоків

for (i=0; i<n; i++)

thread_join(threads[i]); //очікуємо завершення n потоків

}

Тут виконання функції потоку розбито на етапи. Кожен етап не може бути виконаний без цілковитого завершення попереднього. Створюють n потоків, кожен з яких приходить до бар’єра наприкінці етапу. Після переходу бар’єра потоки починають виконувати дії наступного етапу, в кінці якого стоїть новий бар’єр і т.д. Після кожного етапу один із потоків підбиває його результати, викликаючи функцію done() для цього етапу.

Розділ 6

Міжпроцесова взаємодія

6.1. Види міжпроцесової взаємодії

Реалізація міжпроцесової взаємодії здійснюється трьома основними методами: передавання повідомлень, розподілюваної пам’яті та відображуваної пам’яті. Ще одним методом IPC (interprocess communication) також можна вважати технологію сигналів.

Сигнали були розглянуті раніше, тому що їхнє використання не зводиться тільки для організації IPC (синхронізаційні сигнали є засобом оповіщення процесу про виняткову ситуацію); без них складно пояснити ряд базових понять керування процесами (наприклад, очікування завершення процессу).

6.1.1. Методи розподілюваної пам’яті

Методи розподілюваної пам’яті (shared memory) дають змогу двом процесам обмінюватися даними через загальний буфер пам’яті. Перед обміном даними кожний із тих процесів має приєднати цей буфер до свого адресного простору з використанням спеціальних системних викликів (перед цим перевіряють права). Буфер доступний у системі за допомогою процедури іменування, термін його існування звичайно обмежений часом роботи всієї системи. Дані в ньому фактично є спільно використовуваними, як і для потоків. Жодних засобів синхронізації доступу до цих даних розподілена пам’ять не забезпечує, програміст, так само, як і при розробці багатопотокових застосувань, має організовувати їх сам.

6.1.2. Методи передавання повідомлень

В основі методів передавання повідомлень (message passing) лежать різні технології, що дають змогу потокам різних процесів (які, можливо, виконуються на різних комп’ютерах) обмінюватися інформацією у вигляді фрагментів даних фіксованої довжини, котрі називають повідомленнями (messages). Процеси можуть приймати і відсилати повідомлення, при цьому автоматично забезпечується їхнє пересилання між адресними просторами процесів одного комп’ютера або через мережу. Важливою особливістю технологій передавання повідомлень є те, що вони не спираються на спільно використовувані дані – процеси можуть обмінюватися повідомленнями, навіть не знаючи один про одного.

6.1.3. Технологія відображуваної пам’яті

Ще однією категорією засобів міжпроцесової взаємодії є відображувана пам’ять (mapped memory). У ряді ОС відображувана пам’ять є базовим системним механізмом, на якому ґрунтуються інші види міжпроцесової взаємодії та системні вирішення. Звичайно ввідображувану пам’ять використовують у поєднанні з інтерфейсами файлової системи, в такому разі говорять про файли, відображувані у пам’ять (memory-mapped files).

Ця технологія зводиться до того, що за допомогою спеціального системного виклику (зазвичай це nmap()) певну частину адресного простору процесу однозначно пов’язують із вмістом файлу. Після цього будь-яка операція записування в таку пам’ять спричиняє зміну вмісту відображеного файлу, яка відразу стає доступною усім застосуванням, що мають доступ до цього файлу. Інші застосування теж можуть відобразити той самий файл у свій адресний простір і обмінюватися через нього даними один з одним.

6.1.4. Особливості міжпроцесової взаємодії

Тепер можна порівняти характеристики міжпроцесової взаємодії із характеристиками взаємодії потоків одного процесу.

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

· Проблема синхронізації доступу до спільно використовуваних даних є актуальною для взаємодії потоків і для міжпроцесової взаємодії із використанням розподілюваної пам’яті. Використання механізму передавання повідомлень не ґрунтується на спільно використовуваних даних.

6.2. Базові механізми міжпроцесової взаємодії

Розглянемо особливості організації взаємодії між потоками різних процесів. Основною характеристикою такої взаємодії є те, що у процесів немає спільного адресного простору, тому тут не можна безпосередньо працювати зі спільно використовуваними даними, як це було можливо для потоків. Тут ітиметься переважно про процеси, під якими розуміють потоки різних процесів.

6.2.1. Міжпроцесова взаємодія на базі спільної пам’яті

Для вирішення проблеми міжпроцесової синхронізації необхідно:

1. організувати спільну пам’ять між процесами (це може бути розподілювана пам’ять або файл, відображений у пам’ять);

2. розмістити в цій пам’яті стандартні синхронізаційні об’єкти (семафори, м’ютекси, умовні змінні);

3. використовуючи ці об’єкти, працювати зі спільно використовуваними даними, як це робилося у разі використання потоків.

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

6.2.2. Основи передавання повідомлень

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

Як було вже згадано, засоби передавання повідомлень ґрунтуються на обміні повідомленнями – фрагментами даних змінної довжини. Основою такого обміну є не спільна пам’ять, а канал зв’язку (communication channel). Він забезпечує взаємодію між процесами (для того, щоб спілкуватися, вони повинні створити канал зв’язку) і є абстрактним відображенням мережі зв’язку. Абстрактність каналу дає змогу реалізувати його не тільки на основі мережної взаємодії, але й спільної пам’яті (коли процеси перебувають на одному комп’ютері). При цьому такі зміни в реалізації будуть сховані від процесів, що взаємодіють.

Виокремлюють такі характеристики каналів зв’язку: спосіб задання; кількість процесів, які можуть бути з’єднані одним каналом; кількість каналів, які можуть бути створені між двома процесами; пропускна здатність каналу (кількість повідомлень, які можуть одночасно перебуватив системі й бути асоційованими з цим каналом); максимальний розмір повідомлення; спрямованість зв’язку через канал (двобічний або однобічний зв’язок).

В однобічному зв’язку для конкретного процесу допускають передавання даних тільки в один бік.

Примітиви передавання повідомлень

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

Є два примітиви передавання повідомлень: send (для відсилання повідомлення каналом) і receive (для отримання повідомлення з каналу).

Розглянемо, як особливості реалізації send і receive дають змогу виділити різні класи методів передавання повідомлень.

Зазначені примітиви передавання повідомлень можуть задавати прямий і непрямий обмін даними. При прямому обміні даними необхідно явно вказувати процес, з яким необхідно обмінюватися інформацією. Непрямий обмін здійснюють через спеціальний об’єкт (поштову скриньку, порт); процеси можуть поміщати повідомлення в поштову скриньку і отримувати їх звідти. Зазвичай кілька процесів мають доступ до однієї поштової скриньки, застосовуючи під час її пошуку методи іменування. Більшість сучасних технологій обміну повідомленнями використовує непрямий обмін даними. Прикладом прямого обміну є традиційні сигнали.

Синхронне й асинхронне передавання повідомлень

Можна виокремити різні групи методів передавання повідомлень залежно від того, як вони дають можливість відповісти на два запитання.

1. Чи може потік бути призупинений під час виконання операції send, якщо повідомлення не було отримане?

2. Чи може потік бути призупинений під час виконання операції receive, якщо повідомлення не було відіслане?

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

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

· Якщо пропускна здатність дорівнює нулю (повідомлення не можуть очікувати в системі), відправник завжди має очікувати, поки одержувачу не надійде повідомлення, а одержувач має очікувати, поки повідомлення йому не буде відіслано. Два процеси мають явно домовлятися про майбутній обмін.

· Якщо пропускна здатність обмежена (у системі можуть перебувати максимум n повідомлень для цього каналу), відправник має очікувати тільки тоді, коли черга повідомлень для цього каналу переповнена (у ній перебуває рівно n повідомлень), одержувач має очікувати, якщо ця черга порожня.

· Якщо пропускна здатність необмежена, очікування можливе тільки для одержувача за порожньої черги.

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

Розв’язання задачі виробників-споживачів за допомогою повідомлень

Розглянемо розв’язання задачі виробників-споживачів із використанням асинхронного передавання повідомлень. Організовують дві поштові скриньки – для виробника і для споживача. Якщо скринька порожня, потік очікуватиме, поки в ній не з’явиться повідомлення.

Поштові скриньки виробника та споживача мають свої особливості.

Скринька виробника може містити тільки порожні повідомлення загальною кількістю не більше n. Наявність m повідомлень у цій скриньці служить сигналом для виробника, що в буфері є місце для m об’єктів. Щоб відіслати дані в буфер, виробник забирає зі скриньки одне повідомлення, заповнює його даними і відсилає в скриньку споживача. Заповнивши буфер, виробник спустошить свою скриньку і буде змушений чекати, поки споживач не помістить у неї порожнє повідомлення.

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

На початку роботи скриньку виробника заповнюють порожніми повідомленнями загальним числом n (це буде означати, що він може зробити n об’єктів).

Функції producer() і consumer() схожі. І виробник, і споживач у циклі намагаються забрати повідомлення із своїх скриньок. Якщо це вдається виробникові, він заповнює повідомлення даними і відсилає його у скриньку споживача, якщо це зможе зробити споживач, він скористається повідомленням і відішле порожнє повідомлення у скриньку виробника. Після цього цикл триває.

Ось алгоритм розв’язання цієї задачі:

message_t null_nsg; //порожнє повідомлення

mailbox_t producer_mailbox, consumer_mailbox; //поштові скриньки

int n = 100; //розмір буфера

void producer() {

message_t producer_msg;

for (;;) {

//забрати повідомлення зі скриньки виробника,

//чекати, якщо вона порожня

receive(consumer_mailbox, producer_msg);

producer_msg.data = produce();

//відіслати заповнене повідомлення у скриньку споживача

send(consumer_mailbox, producer_msg);

}

}

void consumer() {

message_t consumer_msg;

for (;;) {

//забрати повідомлення зі скриньки споживача чекати якщо вона порожня

receive(consumer_mailbox, consumer_msg);

consume(consumer_msg.data);

//відіслати у скриньку виробника порожнє повідомлення

//повідомивши йому про те, що у буфері є місце

send(producer_mailbox, null_msg);

}

}

void main () {

//заповнити скриньку виробника порожніми повідомленнями

for (int i=0; i<n; i++)

send(producer_mailbox, null_msg);

//запустити producer() і consumer() паралельно

}

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

6.2.3. Технології передавання повідомлення

Дата добавления: 2014-01-05