Проблемът с философите за хранене

Проблемът с философите за храненее класически пример, използван в компютърните науки за илюстриране на проблеми със синхронизацията при разработването на паралелни алгоритми и техники за решаване на тези проблеми.

Проблемът е формулиран през 1965 г. от Edsger Dijkstra като изпитно упражнение за студенти. Като пример взехме конкурентен достъп до лентово устройство. Скоро проблемът е формулиран от Ричард Хоар във вида, в който е известен днес [1] [2] [3] .

Съдържание

Петима мълчаливи философи седят около кръгла маса, с чиния спагети пред всеки философ. Вилици лежат на масата между всяка двойка най-близки философи.

Всеки философ може или да яде, или да мисли. Яденето не е ограничено от количеството останали спагети - подразбира се безкрайно количество. Но философът може да яде само когато държи две вилици, взети отдясно и отляво (алтернативна формулировка на проблема предполага купи с ориз и клечки вместо купи със спагети и вилици).

Всеки философ може да вземе най-близката вилица (ако има такава) или да я остави, ако вече държи такава. Вдигането на всяка вилица и връщането й на масата са отделни действия, които трябва да се извършват едно след друго.

Въпросът на задачата е да се разработи модел на поведение (паралелен алгоритъм), при който никой от философите няма да гладува, тоест той вечно ще редува ядене и мислене.

Проблемът е формулиран по такъв начин, че да илюстрира проблема за избягване на задънена улица – състояние на системата, при което прогресът е невъзможен.

Например, може да се посъветва всеки философ да изпълни следния алгоритъм:

Медитирайте, докато лявото се освободивилица. Когато вилицата е свободна, вземете я.
Медитирайте, докато дясната вилица бъде освободена. Когато вилицата е свободна, вземете я.
Яжте
Поставете лявата вилица
Поставете дясната вилица
Повторете алгоритъма отначало

Това решение на проблема е неправилно: то позволява на системата да достигне състояние на безизходица, където всеки философ е взел вилицата отляво и чака вилицата отдясно да се освободи [4] .

Проблемът с недостига на ресурси (англ. resource starvation) може да възникне независимо от безизходицата, ако един от философите не може да овладее лявата и дясната вилица поради проблеми със синхронизацията. Например, може да се предложи правило, според което философите трябва да оставят вилицата обратно на масата, след като са изчакали пет минути, за да има друга вилица, и да изчакат още пет минути, преди да се опитат да хванат вилиците отново. Тази схема елиминира възможността за блокиране (тъй като системата винаги може да премине в друго състояние), но все още има възможност за „зацикляне“ на системата (англ. livelock), при което състоянието на системата се променя, но тя не върши никаква полезна работа. Например, ако и петимата философи се появят в трапезарията по едно и също време и всеки вдигне лявата вилица по едно и също време, философите ще изчакат пет минути с надеждата да получат дясната вилица, след това ще оставят лявата вилица и ще изчакат още пет минути, преди да се опитат да вземат вилиците отново.

Взаимното изключване (англ. mutual exclusion) е основната идея на "Проблемът на философите за хранене". Този проблем е общ, абстрактен сценарий за обяснение на този тип проблем. Грешките на философите илюстрират трудностите, които възникват в реалното програмиране, когато няколко програми изискват изключителнидостъп до споделени ресурси. Тези въпроси се изучават в областта на паралелните изчисления.

Първоначалната цел на Дейкстра при формулирането на проблема на философа за хранене е да демонстрира възможни проблеми с външни компютърни устройства като лентови устройства [1] . Обхватът на тази задача обаче се разширява много повече и сложностите, разглеждани в задачата, по-често възникват, когато множество процеси се опитват да получат достъп до набор от данни, който се актуализира.

Системите, които трябва да се справят с голям брой едновременни процеси (като ядрата на операционната система), използват хиляди ключалки и точки за синхронизация. Това изисква стриктно спазване на методологиите и протоколите, ако трябва да се избегнат блокирания, глад и повреда на данните.

Сравнително просто решение на проблема се постига чрез добавяне на сервитьор близо до масата. Философите трябва да изчакат разрешението на сервитьора, преди да вземат вилицата. Тъй като сервитьорът знае колко вилици се използват в момента, той може да вземе решения относно разпределението на вилиците и по този начин да предотврати блокада на философите. Ако четири от пет вилици вече се използват, тогава следващият философ, който поиска вилица, ще трябва да изчака разрешението на сервитьора - което няма да бъде получено, докато вилицата не бъде пусната. Предполага се, че философът винаги се опитва да вземе първо лявата вилица, а след това дясната (или обратното), което опростява логиката. Сервитьорът работи като семафор, концепция, въведена от Дейкстра през 1965 г. [5] .

За да покажем как работи това решение, нека приемем, че философите са обозначени с A до D по посока на часовниковата стрелка. Ако философите А и Б ядат, тогава са заети четири вилици. Философ B седи между A и C, така ченито една от вилиците не му е достъпна. В същото време философите D и D имат достъп до една неизползвана вилица между тях. Да предположим, че философът G е гладен. Ако той веднага вземе безплатна вилица, тогава става възможно взаимно блокиране на философите. Ако вместо това поиска разрешение от сервитьора, той го моли да изчака - и можете да сте сигурни, че щом чифт вилици е свободен, тогава поне един философ ще може да вземе две вилици. Така безизходицата става невъзможна.

Йерархия на ресурсите

Друго просто решение се постига чрез присвояване на частичен ред на ресурсите (форкове в този случай) и приемане на конвенцията, че ресурсите се изискват в този ред и се връщат в обратен ред. Освен това не трябва да има два нередовни ресурса, използвани от една и съща единица работа.

Нека ресурсите (вилиците) са номерирани от 1 до 5 и всяка работна единица (философ) винаги взима първо вилицата с най-нисък номер, а след това вилицата с най-висок номер от двете налични. След това философът първо поставя вилицата с по-голямото число, а след това тази с по-малкото. В този случай, ако четирима от петима философи вземат вилицата с най-нисък номер едновременно, вилицата с най-висок възможен номер ще остане на масата. Така петият философ няма да може да вземе нито една вилица. Освен това само един философ ще има достъп до вилицата с най-висок номер, така че той може да яде с две вилици. Когато приключи с използването на вилиците, той ще постави първо вилицата с най-висок номер на масата, след това по-малката, като по този начин ще позволи на другия философ да вземе липсващата вилица и да започне да яде.

Това решение е предложено от Dijkstra.

Докато йерархията на ресурсите избягва взаимнотоключалки, това решение не винаги е практично, особено когато списъкът с необходимите ресурси не е известен предварително. Например, ако работна единица притежава ресурс 3 и 5 и реши, че се нуждае от ресурс 2, тогава тя трябва да освободи ресурс 5, след това 3, след това да завладее ресурс 2 и след това отново да поеме ресурс 3 и 5. Компютърните програми, които работят с голям брой записи в база данни, не могат да работят ефективно, ако трябва да освободят всички записи с горни индекси, преди да поемат притежание на нов запис. Това прави този метод непрактичен.

Базирано на монитор решение

Примерът по-долу показва решение, при което разклоненията не са изрично представени. Философите могат да ядат, ако никой от съседите им не яде. Подобно на системата, при която философите, които не могат да вдигнат втората вилица, трябва да оставят първата вилица, преди да опитат отново.

При липса на блокажи, свързани с вилицата, философите трябва да гарантират, че началото на храненето не се основава на стара информация за състоянието на съседите. Например: Ако Философ Б види, че А не яде в даден момент и след това се обърне и погледне С, А може да започне да яде, докато Философ Б гледа С. С помощта на един мютекс този проблем може да бъде избегнат. Това блокиране не е свързано с разклоненията, но е свързано с решението на процедурите, които могат да променят състоянието на философите. Това се осигурява от монитора.

Алгоритъмът за наблюдение прилага схема за проверка, вземане и поставяне и споделя взаимно изключващо се заключване. Имайте предвид, че философите, които искат да ядат, няма да имат вилици.

Ако мониторът позволи на философа, който иска да яде, да действа, тогава философът отново завладява първата вилица, преди да вземе вече свободната втора.

Накраятекущото хранене, философът уведомява монитора, че и двете вилици са свободни.

Заслужава да се отбележи, че този алгоритъм на монитора не решава проблема с глада. Например, философ B може да чака безкрайно време за своя ред, ако философите A и B имат припокриващи се периоди на хранене. За да сте сигурни, че нито един философ не остава гладен, можете да следите колко пъти гладен философ не е ял, когато съседите му поставят вилиците си на масата. Ако броят пъти надхвърли определена граница, такъв философ ще премине в състояние на гладуване и алгоритъмът на монитора ще принуди процедурата за получаване на вилица, изпълнявайки условието за предотвратяване на гладуване на някой от съседите.

Философът, който не може да вземе вилиците, защото съседът му гладува, е в полезен режим на изчакване съседът на съседа му да приключи с яденето. Тази допълнителна зависимост намалява паралелността. Увеличаването на праговата стойност на гладуване намалява този ефект.