Монітори і семафори. Обідають філософи.
Блокування критичних секцій дозволяє впоратися з проблемою гонки даних. Як засіб блокування ми розглянули оператор lock мови С #. Але Framework. Net включає кілька класів, що дозволяють організувати блокування. Велика кількість різних засобів для вирішення однієї задачі часто свідчить про те, що універсальний засіб, що підходить для всіх випадків життя, відсутня.
Оператор lock фактично є надбудовою над класом Monitor. запис:
можна розглядати як коротку форму наступному записі:
Статичний метод Enter класу Monitor закриває критичну секцію, занурену в try-блок, посилальним об'єктом locker. Семантика така ж, як і у оператора lock. Всі інші потоки, які намагаються увійти в критичну секцію, закриту ключем locker. будуть вибудовуватися в чергу, чекаючи, поки секція не буде відкрита. При будь-якому завершенні try -блока виконується блок finally. знімає блокування.
У класу Monitor є й інші методи, що дозволяють організувати блокування. Деякі потоки, як і деякі люди, ненавидять довге стояння в черзі. У таких ситуаціях вони воліють взагалі відмовитися від виконання завдання або спробувати прийти іншим разом, коли, можливо, черги не буде. Таким потокам клас Monitor надає метод TryEnter. має наступний синтаксис:
У класу Monitor є ще три важливих методу - Wait. Pulse. PulseAll. Ці методи викликаються всередині критичної секції. Вони взаємопов'язані і дозволяють двом або декільком потокам синхронізувати свою роботу, посилаючи один одному повідомлення.
Нехай, виконуючи дії в критичній секції, потік виявляє, що інший потік повинен виконати деяку обробку закритого ресурсу. У цій ситуації потік повинен призупинити свою роботу, звільнити тимчасово ресурс, щоб дати іншому потоку провести необхідну обробку, а потім повідомити призупинений потік, що він може продовжити роботу. Методи Wait - Pulse дозволяють реалізувати описаний сценарій. Метод Wait дозволяє призупинити роботу потоку в критичній секції. Метод Pulse надсилає повідомлення, що дозволяє призупинення потоку продовжити виконання. Метод PulseAll дозволяє продовжити виконання всім призупиненим потокам.
Метод Wait перевантажений, і ми розглянемо тільки основний його варіант, який має наступний синтаксис:
Параметр obj задає синхронизирующий об'єкт, що закриває критичну секцію. Зазвичай метод не використовує значення, що повертається і викликається як оператор, а не як функція. Точна семантика методу така. Метод звільняє синхронизирующий об'єкт, потік перериває роботу і стає в спеціальну чергу очікування повідомлення. Коли інший метод, який захопив звільнений об'єкт синхронізації, виконує метод Pulse. то перший метод з черги очікування перекладається в чергу готових до виконання потоків. Коли настає черга виконуватися методом, то відновлюється його стан, відновлюються всі раніше зроблені блокування і метод продовжує працювати.
Метод Pulse має наступний синтаксис:
При виконанні методу повідомляється чергу очікування потоків з синхронизирующим об'єктом obj. В результаті потік з цієї черги переходить в стан готовність. Коли потік, що викликав метод Pulse. звільнить блокування, то готовий потік продовжить виконання.
Кооперація методів Wait - Pulse дозволяє вирішувати багато завдань взаємодії потоків, які неможливо вирішити іншими способами.
Перш ніж навести приклад, який демонструє взаємодію потоків, ще раз скажу про важку долю програмістів, що створюють паралельні програми. Приклад на застосування методів Wait і Pulse з офіційної документації коректно працює, тільки за умови, що з двох запущених потоків один з них працює першим, в іншому випадку виникає клінч і додаток зависає. Коли я став працювати над альтернативним проектом, то теж довелося повозитися, перш ніж позбутися від постійно виникає ситуації клінчу.
Приклад кооперації двох потоків з використанням схеми Wait - Pulse
Розглянемо кооперацію двох потоків на прикладі наступної задачі. Нехай потокам необхідно обробити деякий безліч даних. Перший потік займається основною обробкою цих даних за умови, що кожен елемент цих даних відповідає певним вимогам. Якщо ця умова не виконується, то потік призупиняє свою роботу, даючи можливість іншому потоку довести елемент даних до потрібної кондиції, після чого перший потік може продовжити свою роботу.
Для простоти будемо вважати, що безліч оброблюваних даних - це масив цілих чисел. Сама обробка зводиться до знаходження максимального елемента. При цьому елементи масиву повинні задовольняти умові, що кожен з них не менше 100. Другий потік замінює "малі" елементи значеннями, переважаючими 100.
Ось як виглядає клас, який здійснює потрібну обробку масиву. Почнемо з загального опису класу:
Обидва потоки будуть працювати над загальною пам'яттю об'єктів цього класу. Мінлива resource - це оброблюваний масив. Інші змінні необхідні для обміну інформацією взаємодіючих потоків. Конструктор класу і методи-властивості виконують типову для них роботу. Метод Init дозволяє створити первинний масив, що підлягає обробці.
Додамо тепер в клас метод, який буде виконуватися в першому потоці, обчислюючи максимальний елемент і припиняючи свою роботу щоразу, коли черговий елемент менше 100:
Зверніть увагу на зв'язку Monitor.Pulse і Monitor.Wait. - повідомляємо інший потік, щоб він міг перейти в стан готовності, і переходимо в режим очікування. А ось як виглядає код іншого потоку, що виправляє "некоректні" елементи:
Якщо метод першим починає роботу, то він входить в режим очікування. В іншому випадку він виправляє елемент і виконує зв'язку методів Pulse - Wait. Відновлення роботи відбувається з перевірки умови завершення обробки масиву. Якщо перший потік закінчив роботу, то завершує роботу і другий потік. Рекомендую уважно вивчити структуру взаємодії потоків, оскільки вона не настільки проста, як здається з першого погляду.
Наведу результати одного сеансу роботи:
збільшити зображення
Мал. 5.6. Результати кооперативної роботи двох потоків
Ще один спосіб блокування надають семафори. У семафорів є дві важливі особливості:
- Семафори суворіші, ніж звичайні способи блокування. У них немає синхронизирующего об'єкта, і вони ніякої потік не допускають в критичну секцію, коли вона зайнята.
- Семафори м'якші, ніж звичайні способи блокування. Вони дозволяють увійти в критичну секцію декільком потокам.
Семафори дозволяють моделювати ситуацію допуску клієнтів на територію, що охороняється з обмеженим числом місць. Прикладами можуть служити такі місця, як стоянка для автомобілів, ресторан, спальний вагон. Якщо всі місця на стоянці зайняті, то створюється черга і в'їхати на стоянку можна тільки після виїзду автомобіля із стоянки.
Семафори часто використовуються при організації роботи з сервером, дозволяючи зменшити навантаження на сервер, обмежуючи число клієнтів, що одночасно працюють з сервером.
Клас SemaphoreSlim задає реалізацію семафорів. У класу два конструктора. У першого конструктора один параметр, який представляє початкове число потоків, яким дозволяється проходити за семафор. В процесі роботи операційна система може збільшити число допускаються потоків. У другого конструктора другий параметр дозволяє задати максимальну кількість потоків, яке не можна перевищувати. Часто семафори використовуються в режимі допуску тільки одного потоку.
У класу SemaphoreSlim є два основні методи - Wait і Release. Методи перевантажені, але ми обмежимося описом однієї реалізації цих методів.
Нехай створений семафор sem. допускає n клієнтів. Тоді при кожному виконанні виклику sem.Wait () число клієнтів, яким дозволено вхід, зменшується на одне. Як тільки це число стає рівним нулю, утворюється черга клієнтів.
Метод Release виконує зворотну операцію, збільшуючи число допускаються клієнтів на одиницю, поки не буде досягнуто максимальне значення.
Ми продемонструємо роботу семафорів на прикладі класичної задачі паралельного програмування - задачі про "обідають філософів".
обідають філософи
Питання про "обідають філософів", запропонована Е. Дейкстрой, добре демонструє проблеми, що виникають при паралельно протікають процеси, і зокрема добре знайому нам проблему клінчу. Опускаючи деякі художні подробиці завдання, приведу її в наступному формулюванні.
П'ять філософів запрошені на обід. Їх посадили за круглий стіл, перед кожним з них стоїть блюдо спагетті, праворуч від страви лежить вилка. Як годиться справжнім філософам, гості не стільки їдять, як віддаються роздумам. Коли філософ згадує про їжу, то він бере свою вилку, але незабаром виявляє, що є спагетті однієї виделкою неможливо. Якщо вилка сусіда вільна, то він бере вилку сусіда і їсть, поки знову не занурюється в роздуми, звільняючи обидві вилки. Якщо ж вилка сусіда зайнята, то філософ очікує її звільнення, не випускаючи свою вилку.
Проаналізуємо цю задачу з позицій паралельного програмування. Обід кожного філософа це окремий процес, що включає три стадії - роздуми, очікування і їжі. Всі процеси протікають паралельно. Спільними ресурсами, використовуваними процесами, є вилки. Кожному процесу потрібні два ресурси. Кожен з них він розділяє з сусіднім процесом. В ході обіду може виникнути клінч. Якщо все філософи одночасно захочуть перейти до їжі, то, взявши кожен по вилці, вони все перейдуть в стан очікування. Будучи щирими філософами, їм і в голову не прийде звільнити вилку, давши можливість насититися своєму сусідові.
У чому складність реалізації такого завдання. Всі філософи використовують один і той же спосіб їжі - один і той же метод. Різниця лише в використовуваних ресурсах - качанах, переданих як параметри методу. Починаючи їжу, для гарантованого успіху філософу варто було б заблокувати обидва необхідних йому ресурсу. Однак пропоновані методи блокування не дозволяють блокувати ресурси, вони блокують критичну секцію, - код, в якому використовуються ресурси. Звичайно, неважко заблокувати код повністю, заблокувавши тим самим все вилки. Але це погане рішення, оскільки тоді в кожен момент є спагетті може тільки один філософ, в той час як, не порушуючи правила, є одночасно можуть два філософа, використовуючи 4 з 5 вилок (в загальному випадку обідати одночасно можуть N / 2 філософів).
Як уникнути клінчу, що не блокуючи можливості обіду всіх, хто лишився філософів? Одне з можливих рішень полягає в тому, щоб приставити до філософам слугу, який зобов'язаний стежити за тим, щоб всі філософи не могли одночасно приступити до їжі. Якщо хоча б одна вилка вільна, то це гарантує відсутність клінчу.
У нашому рішенні, також гарантує відсутність клінчу, використовується інша стратегія - стратегія упорядкування використання ресурсів. Філософи легко навчаються. Навчимо парних філософів (філософів з парними номерами) спочатку брати вилку справа, а непарних філософів першої брати вилку ліворуч. Таке рішення дозволяє уникнути клінчу. Дійсно розглянемо двох сусідніх філософів, які одночасно вирішили є. Лівий з них захопив ліву вилку, правий - праву. Вилка між ними вільна і дістанеться одному з філософів (тому, хто швидше реагує). Один з цієї пари філософів їстиме, його сусіди чекати звільнення вилок. Ситуація клінчу не виникає.
Подібне рішення часто застосовується на практиці. У містах, де часто виникають автомобільні пробки, по непарних днях дозволяється їздити машинам з непарними номерами, по парних днях - з парними номерами.
Перейдемо до побудови програмної моделі для нашої задачі. Наведу спочатку загальний опис класу, що моделює обід філософів:
Вилки, що представляють ресурси, уявімо як масив об'єктів класу SemaphoreSlim. Кожна вилка - це своєрідний семафор, розрахований, зауважте, тільки на одного клієнта. Якщо вона піднята, то інший філософ, який претендує на цю вилку, повинен буде чекати. Апетити філософів обмежені, - змінна repeat показує, скільки раз філософи можуть приступати до їжі, щоб насититися. Масив states буде зберігати історію станів, в яких знаходилися філософи в процесі обіду.
Додамо тепер в наш клас метод, не започатковано паралельно протікають процеси обіду кожного з філософів:
Для кожного філософа створюється свій потік. Всі потоки запускаються для паралельного виконання. Всі потоки виконують один і той же метод DinnerForFhilosophers. При запуску методу передається параметр, що задає номер філософа.
Метод DinnerForFhilosophers описує сам процес обіду. Ось його код:
Спочатку за номером філософа визначаються потрібні йому ресурси. Потім відбувається впорядкування ресурсів. Потім в циклі виконуються три етапи - думати, чекати і є. Коли філософ бере першу вилку (left_fork.Wait), він входить в стан очікування, а вилка стає недоступною для інших філософів. Коли філософ бере другу вилку (right_fork.Wait) він приступає до їжі, а вилка стає недоступною для інших філософів. Після закінчення їжі обидві вилки звільняються. Завдяки введеному правилом упорядкування взяття вилок вдається уникнути клінчу.
Розглянемо тепер код консольного проекту з процедурою Main. моделює роль господаря, організуючого обід філософів:
У жодного господаря, який на обід відводить мало часу, не всі філософи встигають хоч що-небудь з'їсти, не кажучи вже про те, щоб наїстися:
Мал. 5.8. голодні філософи