Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010

“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010




Сторінка17/24
Дата конвертації10.03.2017
Розмір1.41 Mb.
1   ...   13   14   15   16   17   18   19   20   ...   24

5. 3 Базові механізми синхронізації потоків


Сучасні ОС надають широкий набір готових механізмів синхронізації.

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

Синхронізаційні примітиви поділяють на такій основні категорії:



  • універсальні, низького рівня, які можна використовувати різнимииспособами (семафори);

  • прості, низького рівня, кожен з яких пристосований до розв’язання тільки одеієї задачі (мютекси та умовні змінні);

  • універсальні високого рівня, виражені через прості; до цієї групи належить концепція монітора, яка може бути виражена через м’ютекси та умовні змінні;

  • високого рівня, пристосовані до розв’язання конкретної синхронізаційної задачі (блокування читання-записування і бар’єри);

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

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

Класика (з лат. classicus - зразковий) - явище перевірене часом, висока якість якого є загальновизнаною.

Формулювання задачі просте. Припустимо, що в нас є потоки-виробники і потоки-споживачі. Виробник створює об’єкти, споживач їх отримує.

Виробни́цтво - процес створення матеріальних і суспільних благ, необхідних для існування і розвитку. Створюючи певні блага люди вступають у зв'язки і взаємодію – виробничі відносини. Тому виробництво є завжди суспільним.
Завданням є так синхронізувати їхню роботу, щоб споживач не міг намагатися отримувати ще не створені об’єкти, а виробник не міг створити більше об’єктів, ніж сможе отримати споживач.

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



  1. Коли виробник або споживач працює із буфером, решта потоків повинна чекати, поки він завершить свою роботу.

  2. Коли виробник намагається помістити об’єкт у буфер, а буфер повний (у ньому n об’єктів), він має дочекатися, поки в ньому з’явиться місце.

  3. Коли споживач намагається забрати об’єкт із буфера, а буфер порожній, він має дочекатися, поки в ньому з’явиться об’єкт.

5. 3. 1 Семафори


Концепцію семафорів запропонував у 1965 році Е. Дейкстра – відомий голландський фахівець у галузі комп’ютерних наук. Семафори є найстарішими синхронізаційними примітивами з числа тих, які застосовуються на практиці.

Семафор – це спільно використовуваний невід’ємний цілочисловий лічильник, для якого задано початкове значення і визначено такі атомарні операції:



  • Зменшення семафора (down): якщо значення семафора більш від нуля, його зменшують на одиницю, якщо ж значення дорівнює нулю, цей потік переходить у стан очікування доти, поки воно не стане більш від нуля (кажть, що потік “очікує на семафорі” або “заблокований на семафорі”). Таку операцію називають також очікуванням – wait. Ось її псевдокод:

void down(semaphore_t sem)

{

if (sem>0)



sem--;
Псевдокод - це неформальний запис алгоритму, який використовує структуру поширених мов програмування, але нехтує деталями коду, неістотними для розуміння алгоритму (опис типів, виклик підпрограм тощо).

else sleep();

}


  • Збільшення семафора (up): значення семафора збільшують на одиницю; коли прицьому є потоки, які очікують на семафорі, один із них виходить із очікування і виконує свою операцію down. Якщо на семафорі очікують кілька потоків, то внаслідок виконання операції up його значення залишається нульовим, але один із потоків продовжує виконання (у більшості реалізацій вибір цього потоку буде випадковим). Цюоперацію також назтвають сигналізацією – post. Ось її псевдокод:

void up(semaphore_t sem)

{

sem ;



if(waiting_threads())

wakeup(some_thread);

}

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



Дейкстра використовував для операції down позначення P (від голландського probirien – перевіряти), а для операції up – позначення V (від голландського verhoren – збільшувати).
Голландці, також нідерландці (нід. Nederlanders вимоваопис файлу, також Nederlandse volk) - нація, основне населення Нідерландів. Чисельність у Нідерландах становить близько 13 млн. осіб, крім того, групи голландців проживають в інших країнах світу, переважно у США і Канаді.
Ці позначення часто використовують у літературі.

Особливості використання семафорів


Семафори можна використовувати для розв’язання двох різних задач синхронізації.

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

semaphore_t sem=1; //на початку семафор відкритий

down(sem);

// критична секція

up(sem);


  1. За їхньою допомогою можна організовувати очікування виконання деякої умови. Припустимо, що треба організувати очікування одним потоком завершення виконання іншого (аналог операції приєднання). У цьому випадку можна використати семафор із початковим значенням 0 (закритий). Потік, який чекатиме, повинен виконати для цього семафора операцію down, а щоб просигналізувати про завершення потоку, у його функції завершення потрібно для того самого семафоруа виконати up. Ось псевдокод (this_thread означає поточний потік):

Void thread_init()

{

this_thread.sem=0; // На початку виконання потоку семафор видкритий



}

void thread_exit()

{

up(this_thread.sem); // розбудити потік, що очікує, якщо такий є



}

void thread_join(thread_t thread)

{

down(thread.sem); // Очікування завершення потоку thread



}

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


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

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

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

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

Тепер розглянемо синхронізаційні примітиви, які нам потрібні. Кожна синхронізаційна операція потребує окремого семафора.

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

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

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

Ось псевдокод розв’язання цієї задачі:

semaphore_t lock=1; // для критичної секції

semaphore_t empty_items=n; // 0-буфер повний, від початку він порожній

semaphore_t full_items=0; // якщо 0 – буфер порожній

// виробник

void producer()

{

item_t item=produce(); // створити об’єкт



down(empty_otems); // чи є місця для об’єкта?

down(lock); // вхід у критичну секцію

append_to_buffer(item); // додати об’єкт item у буфер

up(lock); // вихід із критичної секції

up(full_items); //повідомити споживачів, що є новий об’єкт

}

// споживач



void consumer()

{

item_t item;



down(full_items); // чи не порожній буфер?

down(lock); // вхід у критичну секцію

item=receive_from_buffer(); // забрати об’єкт item з буфера

up(lock); // вихід із критичної секції

up(empty_items); // повідомити виробників, що є місце

consume(item); // спожити об’єкт

}

5. 3. 2 М’ютекси


Поняття м’ютекса багато в чому збігається з поняттям блокування, визначеним раніше (розділ 5.2). Мютексом називають синхронізаційний примітив, що не допускає виконання деякого фрагмента коду більш як одним потоком. Фактично м’ютекс є реалізацією блокування на рівні ОС.

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

М’ютекс може перебувати у двох станах: вільному і занятому. Початковим станом є “вільний”. Над м’ютексом можливі дві атомарні операції.


  • Зайняти м’ютекс (mutex_lock): якщо м’ютекс був вільний, він стає зайнятим, і потік продовжує своє виконання (входячи у критичну секцію); якщо м’ютекс був зайнятий, потік переходить у стан очікування (кажуть, що потік “очікує на м’ютексі”, або “заблокований на м’ютексі”), виконання продовжує інший потік. Потік, який зайняв м’ютекс, називають власником м’ютекса (mutex owner):
    mutex_lock (mutex_t mutex)

{

if(mutex.state====free)

{

mutex.state=locked;



mutex.owner=this_thread;

}

else



sleep();

}


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

mutex_unlock (mutex_t mutex)

{

if(mutex.owner!=this_thread)



return error;

mutex.state=free;

if(waiting_threads())

wakeup(some_thread);

}

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

Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.



Ось найпростіша реалізація критичної секції за допомогою м/ютекса.

mutex_t mutex;

mutex_lock(mutex);

// критична секція

mutex_unlock(mutex);

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


Висновки


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

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

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

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


1   ...   13   14   15   16   17   18   19   20   ...   24



  • 5. 3. 1 Семафори
  • Особливості використання семафорів
  • Реалязація задачі виробників-споживачів за допомогою семафорів
  • 5. 3. 2 М’ютекси
  • Висновки