4.Елементи теорії конкурентних процесів. Події та процеси
Поведінка широкого класу об'єктів можна описати за допомогою набору подій, що відбуваються на цих об'єктах.
Припустимо, що пасажир купує квиток в автоматі вартістю в 20 коп.
У цьому випадку роботу автомата й пасажира (АП) можна описати в такий спосіб:
50к - монета 50к уводиться в проріз автомат;
КН - натискається кнопка видачі квитка;
К - на виході автомата з'явиться квиток;
З - на виході автомата з'являється здача;
Якщо автомату запропонували монети різного достоїнства, весь процес можна описати іншим рядом подій:
10к - монета 10к уводиться в проріз автомата;
15к - монета 15к уводитися в проріз автомата;
КН - натискається кнопка видачі квитка
К - на виході автомата з'явиться квиток;
З - на виході автомата з'являється здача;
Можливі й інші варіанти. Скажемо, автомат не має можливості видати здачу або кількість введених монет недостатня для покриття вартості квитка. У цьому випадку видається відповідне повідомлення, і повертаються введені монети.
Сукупність всіх можливих подій, що відбуваються на даному об'єкті, становить його опис.
По визначенню об'єкт не може перейти до події, яка відсутня у його описі.
Як правило, виділення й визначення подій пов'язане зі спрощенням опису об'єкта.
У розглянутому прикладі може відбуватися одночасно безліч інших подій, наприклад, контроль вступників, включення й відключення різних блокувань і т.д.
Передбачається, що події відбуваються миттєво в деякий момент часу.
Якщо істотно, що подія а триває в часі, то можна визначити дві події: стосовно до початку (поч. (а)) і до закінчення (кін. (а)).
Як правило, при розгляді подій не так важливий час їхнього здійснення, як порядок їхнього чередування.
Послідовність подій а1,…...., аі,.....,аn, для кожного елемента якої справедливо, що поч. (аі) передує події поч. (аі+1) буде називатися послідовним процесом або просто процесом.
Таким чином, розглянутий вище процес можна описати як:
АІП = <50 к, КН, К, З>
Якщо розглядати виконання програми в однопроцесорному комп'ютері як процес, то кожна зміна стану комп'ютера можна вважати подією. Послідовність цих подій і визначає процес.
Для опису процесу в комп'ютері служать його атрибути, у які входить:
ім'я процесу;
пріоритет для виділення йому процесорного ресурсу;
перелік розширених операцій (права процесу), пов'язані із захистом інформації;
образ (зміст процесу) і.т.д.
Часто прибігають до графічного способу опису процесу.
Кружки відповідають різним станам процесу, стрілки - подіям, що ведуть від одного стану до іншого.
Верхній кружок являє собою корінь дерева - початковий стан. Від нього процес іде вниз уздовж стрілок:
У розглянутому процесі АІП перелік подій визначається внутрішніми взаємодіями (введення монет, натискання кнопки). Їх здійснює користувач.
Поведінку користувача можна виділити в окремий процес, а весь процес АІП представити як систему взаємодіючих послідовних процесів.
Розглянемо 2 комп'ютерні програми а й b і відповідні їм процеси.
Виконання процесів можна реалізувати різними способами:
виконати процеси послідовно;
по черзі виконувати події процесів а й b;
обидва процеси виконувати паралельно;
Стосовно до цих процесів можна сказати, що вони для свого виконання вимагають використання деякого ресурсу (одного або двох процесорів). Процесор у цьому випадку є критичним ресурсом, а самі процесори перебувають у стані конкуренції за володіння цим ресурсом.
Паралельні конкурентні процеси добре представляють особливості їхньої взаємодії на класичному завданні «трапеза філософів».
Відповідно до цього завдання 5 філософів живуть в одному будинку із загальною їдальнею. У їдальні знаходиться великий круглий стіл. Філософи займаються двома видами діяльності:
Обмірковують проблеми і їдять за спільним столом. На столі 5 тарілок і 5 виделок. Вони розташовані так, що праворуч і ліворуч від кожної тарілки лежить по виделці.
Кожний з філософів за столом має своє постійне місце. У центрі стола блюдо зі спагетті, які можна взяти й з'їсти тільки двома виделками. Кожний філософ, відчуваючи голод, підходить до столу, сідає на своє місце, бере ліву, а потому праву виделку, накладає спагетті і їсть. Після трапези він кладе обидві виделки на стіл і йде, щоб продовжити роботу.
Якщо одна з виделок зайнята, філософ чекає її звільнення. Якщо це права виделка, він чекає, не звільняючи ліву.
Тобто ми маємо 5 конкурентних процесів, кожний з яких представляє цикл із 8 повідомлень:
ФІЛ:=<думає; сідає за стіл; бере ліву виделку, бере праву виделку; їсть; кладе обидві виделки; встає>
Час, витрачений на обмірковування й на їжу - випадкові величини. Передбачається, що філософи беруть і кладуть виделки, займають і звільняють місця миттєво.
Крім філософів, діючими елементами системи є виделки. Можна виділити 5 процесів, пов'язаних з виделоками, кожний з 4-мя подіями.
Філ і=< Філ і бере і-у виделку, Філ і кладе і-у виделку, Філ і-1берет і-у виделку, Філ і-1 кладе і-у виделку>
Приведемо діаграми, на яких філософи зображені кружечками, а виделки прямокутниками. Нумерація місць філософів і виделок проведемо від 0 до 4 проти часової стрілки.
Якщо філософ зайняв місце (очікує виделок або їсть) то номер філософа в кружку, якщо немає - те за кружком. Стрілки від прямокутника до кружка означають, що дана виделка зайнята відповідними кружку філософами.
Коли філософ заволодів обома виделками, то він почав їсти (а).
У даний момент всі філософи перебувають у режимі обмірковування. Потому один або декілька сідають за стіл. Якщо Філ і має (і-1)-го й (і+1)-го сусіда за трапезою, він повинен чекати доки звільниться ліва виделка, а потому права. Може бути ситуація, коли всі філософи сядуть за стіл і візьмуть ліву виделку. Тоді всі філософи не зможуть почати їсти (б). Така критична ситуація наз. Deadlock (смертельні обійми). Відбувається нескінченна затримка процесів, що потрапили в цей стан.
Для того, щоб переконається в можливості існування дедлока, потрібно перебрати всі можливі стани системи, що в ряді випадків неможливо.
Однак можна придумати заздалегідь ряд виходів з можливої ситуації Deadlock.
Стосовно до завдання про філософів можна запропонувати додаткову шосту виделку. Цю виделку може взяти будь-який філософ і користуватися їй у якості правої або лівої залежно від ситуації.
Якщо припустити, що за 6 вилкою звертаються філософи у відповідності зі своїм порядковим номером, кому вона потрібна, то відповідно до в) першим її одержить філософ з номером 0. Потім ФІЛ1 одержить одну виделку й т.д. (г)
Нехай тепер ФІЛ1 берет спочатку не ліву виделку а праву виделку. Домовимося, що, якщо два філософи звертаються за однією виделкою, то вона дістається філософові з меншим номером.
Т.ч. при звертання у ВЛ2 філософів 2 і 1 виделка дістається філософові 1. Філ 2 буде чекати, а Філ. 1 буде їсти, Deadlock не утвориться.
Нарешті третій спосіб уникнути Deadlock:
Ввести якогось координатора, який би дозволяв сідати за стіл не більш ніж 4-м філософам одночасно (позиція е)
Введемо модифікацію первісного алгоритму. Нехай кожний з філософів, що взяв ліву виделку й немає правої відразу кладе її на стіл, а потому знову бере. Виникне коливальний процес, у результаті якого процеси замість припинення будуть нескінченно довго виконуватися. Це неприємне явище називається Lifelock (живі обійми).
Однак при невеликій неузгодженості (різної реакції у філософів) один із процесів може захопити виконання (один встигає захопити 2 виделки) Т.ч. досить малі відхилення в синхронізації можуть істотно змінити поведінку системи.
Може виникнути ще одна цікава ситуація. Наприклад, якщо Філ і не дочекавшись своєї правої виделки, поклав ліву, а при звільненні правої захотів її знову взяти, вона може бути вже зайнята сусідом і т.д.
Такий режим реальний, коли сусід Філ і, маючи гарний апетит, значно частіше ніж він з’являється за столом.
Ця ситуація зветься невизначеною відстрочкою (indefinite postponement)