Distributed Shared Memory

Матеріал з Вікіпедії — вільної енциклопедії.
Jump to navigation Jump to search

Розподілена пам'ять (англ. Shared memory) — механізм обміну даними між процесами в Unix і подібних ОС, один з засобів взаємодії між процесами.

Розподілена пам'ять (DSM - Distributed Shared Memory)[ред.ред. код]

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

DSM - віртуальний адресний простір, поділюваний всіма вузлами (процесорами) розподіленої системи. Програми отримують доступ до даних в DSM приблизно так само, як вони працюють з даними в віртуальній пам'яті традиційних ЕОМ. У системах з DSM дані переміщаються між локальною пам’яттю різних комп'ютерів аналогічно тому, як вони переміщуються між оперативною і зовнішньою пам'яттю одного комп'ютера.

Переваги DSM[ред.ред. код]

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

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

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

4.DSM-системи можуть нарощуватися практично безмежно на відміну від систем з пам'яттю, що розділяється, тобто вони є масштабованими. 5.Програми, написані для мультипроцесорів із загальною пам'яттю, можуть в принципі без будь-яких змін виконуватися на DSM-системах (принаймні, вони можуть бути легко перенесені на DSM-системи).По суті, DSM-системи долають архітектурні обмеження мультипроцесорів і скорочують зусилля, необхідні для написання програм, розподілених систем. Зазвичай вони реалізуються програмно-апаратними засобами, але в останні роки з'явилося кілька комерційних MPP з DSM, реалізованої апаратно (Convex SPP, KSR1).

Алгоритми реалізації DSM.[ред.ред. код]

При реалізації DSM центральними є такі питання.

1.як підтримувати інформацію про розташування віддалених даних.

2.як знизити при доступі до віддалених даними комунікаційні затримки і великі накладні витрати, пов'язані з виконанням комунікаційних протоколів.

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

Чотири основних алгоритми реалізації DSM[ред.ред. код]

1.Алгоритм з центральним сервером[ред.ред. код]

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

2.Міграційний алгоритм[ред.ред. код]

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

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

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

3.Алгоритм розмноження для читання[ред.ред. код]

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

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

4.Алгоритм повного розмноження[ред.ред. код]

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

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

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

Всі однопроцесорні системи забезпечують строгу консистентним, але в розподілених багатопроцесорних системах ситуація набагато складніше. Припустимо, що змінна X розташована в пам'яті машини B, і процес, який виконується на машині A, намагається прочитати значення цієї змінної в момент часу T1. Для цього машині B надсилається запит змінної X. Трохи пізніше, в момент часу T2, процес, що виконується на машині B, виробляє операцію запису нового значення в змінну X. Для забезпечення суворої консистентності операція читання повинна повернути в машину А старе значення змінної, незалежно від того, де розташована машина A і наскільки близькі між собою два моменти часу T1 і T2. Однак, якщо T1-T2 дорівнює 1, і машини розташовані один від одного на відстані 3-х метрів, то сигнал про запиті значення змінної повинен бути переданий на машину B зі швидкістю в 10 разів перевищує швидкість світла, що неможливо.

P1: W(x)1 P1: W(x)1
--> t --> t
P2: R(x)1 P2: R(x)0 R(x)1
А) Б)

а) Суворо консистентна пам'ять

б) Пам'ять без суворої консистентності

Послідовність[ред.ред. код]

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

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

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

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

Два приклади правильного виконання однієї програми. У прикладах використовуються наступні позначення:

W(x)1 - запис значення 1 в змінну x; R(x)0 - читання значення 0 з змінної x.

P1: W(x)1 W(y)1
P2: W(z)1
P3: R(x)0 R(y)0 R(z)1 R(y)0
P4: R(x)0 R(y)1 R(z)1 R(x)1

У цьому прикладі процеси бачать запис у порядку W(z)1, W(x)1, W(y)1

P1: W(x)1 W(y)1
P2: W(z)1
P3: R(x)0 R(y)0 R(z)1 R(y)0
P4: R(x)0 R(y)1 R(z)1 R(x)1

Описаний вище міграційний алгоритм реалізує послідовну консистентцію

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

Консистент виходу[ред.ред. код]

У системі зі слабкою консистентністью виникає проблема при зверненні до синхронізованої змінної: система не має інформації про цілі цього звернення - чи процес завершив модифікацію загальної змінної, або готується прочитати значення загальної змінної. Для більш ефективної реалізації моделі консистентності система повинна розрізняти дві ситуації: вхід у критичну секцію і вихід з неї. У моделі консистентності по виходу введені спеціальні функції звернення до синхронизационным змінним: (1) ACQUIRE - захоплення синхронізованої змінної, інформує систему про вхід у критичну секцію; (2) RELEASE - звільнення синхронізованої змінної, що визначає завершення критичної секції. Захоплення і звільнення використовується для організації доступу до всіх загальних змінних, а тільки до тих, які захищаються даної синхронізованої змінної. Такі загальні змінні називають захищеними змінними. Приклад допустимої послідовності подій для моделі з консистентністю по виходу. (Acq(L) - захоплення синхронізованої змінної L; Rel(L) - звільнення синхронізованої змінної).

DSM на базі спільних змінних[ред.ред. код]

У DSM системах з розділеними змінними тільки окремі структури даних розділяються між процесорами. Програміст повинен точно визначити, які змінні в програмі повинні розділятися, а які не повинні.

Знання інформації про режим використання спільних змінних дозволяє скористатися більш ефективними протоколами когерентності.

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

s = 0;

izer = 0;

for (i = 1; i < L2-1; i++)

{

r = A[i-1]*A[i+1];

C[i] = r;

s = s + r*r;

if (A[i]==0) { izer = i};

}

A[izer] = 1;

А - тільки

на читання;

r - приватно (фактично не є розділяється);

C - роздільно використовується (будь-який елемент масиву змінюється не більше, ніж одним процесом, і ніякої процес не читає елемент, змінюваний іншими);

s - редукційна змінна, яка використовується для підсумовування;

izer - змінна, що зберігає індекс останнього нульового елемента масиву А;

Приведення у стан змінних A і r - не вимагається.

Для приведення в стан масиву необхідно при завершенні циклу кожному процесу надіслати іншим всі свої зміни в масиві С.

Для змінної s в кінці циклу треба довиконати операцію редукції - скласти всі часткові суми, отримані різними процесорами у своїх копіях змінної s і розіслати результат всім процесорам (якби початкове значення змінної s було відмінно від нуля, то це треба було б врахувати).

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

Поза циклу приведення у стан змінної A[izer] не потрібно, оскільки на кожному процесорі виконується один і той же оператор, що присвоює одне і те ж значення всім копій змінної.

DSM на базі об'єктів[ред.ред. код]

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