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


Категорії засобів обміну інформацією

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

· Сигнальні. Передається мінімальна кількість інформації – один біт, "та чи ні". Використовуються, як правило, для сповіщення процесу про настання якої-небудь події. Ступінь дії на поведінку процесу, що отримав інформацію, мінімальна. Все залежить від того, чи знає він, що означає отриманий сигнал, чи треба на нього реагувати і яким чином. Неправильна реакція на сигнал або його ігнорування можуть привести до трагічних наслідків. Пригадаємо професора Плейшнера з кінофільму "Сімнадцять митей весни". Сигнал тривоги – квітковий горщик на підвіконні – був йому переданий, але професор проігнорував його. І до чого це привело?

· Канальні. "Спілкування" процесів відбувається через лінії зв'язки, надані операційною системою, і нагадує спілкування людей по телефону, за допомогою записок, листів або оголошень. Об'єм передаваної інформації в одиницю часу обмежений пропускною спроможністю ліній зв'язку. Із збільшенням кількості інформації зростає і можливість впливу на поведінку іншого процесу.

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

Потоки виконання

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

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

Ввести масив а

Ввести масив b

Ввести масив

а = а + b

з = а + з

Вивести масив

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

Ввести масив а

Очікування закінчення операції введення

Ввести масив b

Очікування закінчення операції введення

Ввести масив

Очікування закінчення операції введення а = а + b

з = а + з

Вивести масив

Очікування закінчення операції виводу

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

Процес 1 Процес 2

Ввести масив а Очікування введення

Очікування закінчення масивів а і b

операції введення

Ввести масив b

Очікування закінчення

операції введення

Ввести масив

Очікування закінчення а = а + b

операції введення

з = а + з

Вивести масив

Очікування закінчення

операції виводу

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

Процес 1 Процес 2

Створити процес 2

Перемикання контексту

Виділення загальної

пам'яті

Очікування введення

а і b

Перемикання контексту

Виділення загальній пам'яті

Ввести масив а

Очікування закінчення

операції введення

Ввести масив b

Очікування закінчення

операції введення

Ввести масив

Очікування закінчення

операції введення

Перемикання контексту

а = а + b

Перемикання контексту

з = а + з

Вивести масив

Очікування закінчення

операції виводу

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

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

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

Нитка 1 Нитка 2

Створити нитку 2

Перемикання контексту ниток

Очікування введення а і b

Перемикання контексту ниток

Ввести масив а

Очікування закінчення

операції введення

Ввести масив b

Очікування закінчення

операції введення

Ввести масив

Очікування закінчення

операції введення

Перемикання контексту ниток

а = а + b

Перемикання контексту ниток

з = а + з

Вивести масив

Очікування закінчення

операції виводу

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

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

Висновок

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

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

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

Interleaving, race condition і взаємовиключення

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

1. Відрізувати скибочку хліба.

2. Відрізувати скибочку ковбаси.

3. Намазати скибочку хліба маслом.

4. Покласти скибочку ковбаси на підготовлену скибочку хліба.

Неподільні операції можуть мати внутрішні невидимі дії (узяти батон хліба в ліву руку, узяти ніж в праву руку, провести відрізання). Ми ж називаємо їх неделимыми тому, що вважаємо за виконуваних за раз, без переривання діяльності.

Хай є дві активність

P: а b з

Q: d e f

де а, b, з, d, e, f – атомарні операції. При послідовному виконанні активностей ми отримуємо таку послідовність атомарних дій:

PQ: а b з d e f

Що відбудеться при виконання цих активностей псевдопараллельно, в режимі розділення часу? Активності можуть розшаруватися на неподільні операції з різним чергуванням, тобто може відбутися те, що англійською мовою прийнято називати словом interleaving. Можливі варіанти чергування:

а b з d e f

а b d з e f

а b d e з f

а b d e f з

а d b з e f

......

d e f а b з

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

P: x=2 Q: x=3

y=x-1 y=x+1

Що ми отримаємо в результаті їх псевдопаралельного виконання, якщо змінні x і у є для активностей загальними? Очевидно, що можливі чотири разных набору значень для пари (x, у): (3, 4), (2, 1), (2, 3) і (3, 2). Ми говоритимемо, що набір активностей (наприклад, програм) детермінований, якщо всякий раз при псевдопаралельного виконання для одного і того ж набору вхідних даних він дає однакові вихідні дані. Інакше він недетермінований. Вище приведений приклад недетермінованого набору програм. Зрозуміло, що детермінований набір активностей можна небоязливо виконувати в режимі розділення часу. Для недетермінованого набору такого виконання небажане.

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

Введемо набори вхідних і вихідних змінних програми. Для кожної атомарної операції набори вхідних і вихідних змінних – це набори змінних, які атомарна операція прочитує і записує. Набор вхідних змінних програми R(P) (R від слова read) суть об'єднання наборів вхідних змінних для всіх її неподільних дій. Аналогічно, набір вихідних змінних програми W(P) (W від слова write) суть об'єднання наборовши вихідних змінних для всіх її неподільних дій. Наприклад, для програми

P: x=u+v

y=x*w

отримуємо R(P)= {u, v, x, w}, W(P)= {x, у}. Відмітимо, що змінна x присутня як в R(P), так і в W(P).

Тепер сформулюємо умови Бернстайна.

Якщо для двох даних активностей P і Q:

· перетин W(P) і W(Q) порожньо

· перетин W(P) з R(Q) порожньо

· перетин R(P) і W(Q) порожньо

тоді виконання P і Q детерміноване.

Якщо ці умови не дотримані, можливо, паралельне виконання P і Q детерміноване, а може бути, і ні.

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

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

Про недетермінований набір програм (і активностей взагалі) говорять, що він має race condition (стан гонки, стан змагання). У приведеному вище прикладі процеси змагаються за обчислення значень змінних x і у.

Завдання впорядкованого доступу до даних (усунення race condition), що розділяються, у тому випадку, коли нам не важлива його черговість, можна вирішити, якщо забезпечити кожному процесу ексклюзивне право доступу до цих даних. Кожен процес, що звертається до ресурсів, що розділяються, унеможливлює для всіх інших процесів одночасного спілкування з цими ресурсами, якщо це може привести до недетермінованої поведінки набору процесів. Такий прийом називається таким, що взаємовиключає (mutual exclusion). Якщо черговість доступу до ресурсів, що розділяються, важлива для отримання правильних результатів, то одними взаємовиключають вже не обійтися, потрібна взаимосинхронизация поведінки програм.

Важливим поняттям при вивченні способів синхронізації процесів є поняття критичної секції (critical section) програми. Критична секція – це частина програми, виконання якої може привести до виникнення race condition для певного набору програм. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно організувати роботу так, щоб в кожен момент часу тільки один процес міг знаходитися в своїй критичній секції, пов'язаній з цим ресурсом. Іншими словами, необхідно забезпечити реалізацію того, що взаємовиключає для критичних секцій програм. Реалізація того, що взаємовиключає для критичних секцій програм з практичної точки зору означає, що по відношенню до інших процесів, що беруть участь у взаємодії, критична секція починає виконуватися як атомарна операція. Давайте розглянемо наступний приклад, в якому псевдопаралельні взаємодіючі процеси представлені діями різних студентів (таблиця 5.1):

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

Таблиця 5.1.
Час Студент 1 Студент 2 Студент 3
17-05 Приходить в кімнату    
17-07 Виявляє, що хліба немає    
17-09 Йде в магазин    
17-11   Приходить в кімнату  
17-13   Виявляє, що хліба немає  
17-15   Йде в магазин  
17-17     Приходить в кімнату
17-19     Виявляє, що хліба немає
17-21     Йде в магазин
17-23 Приходить в магазин    
17-25 Купує 2 батони на всіх    
17-27 Йде з магазина    
17-29   Приходить в магазин  
17-31   Купує 2 батони на всіх  
17-33   Йде з магазина  
17-35     Приходить в магазин
17-37     Купує 2 батони на всіх
17-39     Йде з магазина
17-41 Повертається в кімнату    
17-43      
17-45      
17-47   Повертається в кімнату  
17-49      
17-51      
17-53     Повертається в кімнату

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

Таблиця 5.2.
Час Студент 1 Студент 2 Студент 3
17-05 Приходить в кімнату    
17-07 Дістає два батони хліба    
17-43   Приходить в кімнату  
17-47     Приходить в кімнату

Отже, для вирішення завдання необхідно, щоб у тому випадку, коли процес знаходиться в своїй критичній ділянці, інші процеси не могли увійти до своїх критичних ділянок. Ми бачимо, що критична ділянка повинна супроводитися прологом (entry section) – "закрити двері зсередини на засув" – і епілогом (exit section) – "відсунути засув", які не мають відношення до активності одиночного процесу. Під час виконання прологу процес винен, зокрема, отримати дозвіл на вхід в критичну ділянку, а під час виконання епілогу – повідомити інші процеси, що він покинув критичну секцію.

У загальному випадку структура процесу, що бере участь у взаємодії, може бути представлена таким чином:

while (some condition) {

entry section

critical section

exit section

remainder section

}

Тут під remainder section розуміються всі атомарні операції, що не входять в критичну секцію.

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

o Вимоги та алгоритми взаємодії процесівСторінка

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