Едновременен достъп до групи от обекти

Опитвам се да разработя приложение, което се състои от набор от нишки, използвайки алгоритъм за кражба на работа за едновременно изпълнение на задачи.

Тези задачи

  • достъп до предварително определен набор от обекти;
  • трябва "атомично" да придобие разрешения за четене/запис на всички обекти, до които има достъп, преди действително да стартира;
  • при завършване (и гарантирано, че в крайна сметка ще завършат) освобождават предметите, които придобиват.

Един възможен начин за решаване на този проблем е всяка нишка да вземе задача в даден момент, след което да се опита да заключи всеки от обектите, като използва предварително определен ред. Ако поне едно не успее, освободете всички ключалки и продължете с друга задача.

Този метод обаче увеличава вероятността от гладуване на задачи с големи зависимости на обекти и дори може да доведе до активни заключвания.

Има ли друг метод за придобиване на набор от ключалки, като същевременно се увеличи едновременността? (без глобално заключване) Или може би да промените системата по начин, който вече не е необходим? Ако е така, има ли добри документи за това?

ps: Както thiton отговори, това е обобщена версия на проблема с „философите за хранене“. Търся нецентрализирани решения, по-специално алгоритми, които се справят добре при голямо натоварване (добавяне и изтриване на задачи).


scheduled-tasks concurrency scheduling mutual-exclusion
person João Rafael    schedule 01.08.2011    source източник

Отговори (3)


arrow_upward
0
arrow_downward

Вашият проблем се нарича Ding Philosophers. Под тази ключова дума трябва да намерите каквото количество литература ви е необходимо :-).

person thiton    schedule 02.08.2011
comment
Сега си спомням! най-точно това е обобщеният проблем с философите за хранене без ограничението за 2 вилици/философ. - person João Rafael; 02.08.2011

arrow_upward
1
arrow_downward

Подреждането на ресурси е валиден подход. Друг лесен подход, който идва на ум, е да се въведе споделен арбитър, който да съхранява информация за наличността на ресурси. Задачите биха заключили всички ресурси, от които се нуждаят, чрез арбитъра в една атомна стъпка „acquire(r1, r2, ..., rn)“ и ще ги освободят по подобен начин с „release(r1, r2, ..., rn)“.

Ако искане за „придобиване“ A може да бъде удовлетворено, арбитърът ще се увери, че никоя друга задача не може да придобие нито един от ресурсите, държани от A, докато A не ги освободи обратно.

Арбитърът може да използва няколко стратегии, за да удовлетвори входящи заявки:

  1. Отхвърлете заявка, която не може да бъде незабавно удовлетворена - задачите ще трябва да опитат отново. Това отваря вратата за запушвания и глад.
  2. Съхранявайте всички входящи заявки в опашка и ги обслужвайте по FIFO начин, когато ресурсите, необходими за началната заявка, станат достъпни.
  3. Съхранявайте всички неудовлетворени заявки в списък (без да блокирате изискваните от тях ресурси) и ги преглеждайте (може би с приоритет за по-стари заявки) всеки път, когато някои ресурси бъдат освободени, за да намерите заявка, която може да бъде удовлетворена.
person Vaclav Pech    schedule 02.08.2011
comment
Това е валидно решение. Въпреки това, тъй като има един единствен арбитър, всички задачи трябва да изчакат в опашката за заключване на арбитъра, което причинява спорове. Освен това нишката за проверка на възможни едновременни задачи се изпълнява в една нишка и това ще постави ограничение на максималната едновременност. - person João Rafael; 02.08.2011
comment
Сега, като мисля за вашия много валиден коментар, вероятно бих проектирал такава арбитърна система по начин, по който арбитърът няма да работи с нишки, а със задачи. Блокирането на задача (част от работа) при изчакване на ресурс вероятно ще има много по-малко въздействие върху пропускателната способност в сравнение с блокирането на нишки. само сортирайте ресурси за задачи и - person Vaclav Pech; 02.08.2011
comment
(продължение) Арбитърът постепенно щеше да прочете задачите, да им присвои поисканите ресурси и да изплюе онези, които изкараха всички ресурси в пул от нишки за обработка. При условие, че задачите отнемат известно време за изпълнение, еднонишковият арбитър може да не се превърне в пречка. - person Vaclav Pech; 02.08.2011
comment
Предполагам, че всичко се свежда до размера на задачата. Както си представям системата, тези задачи ще бъдат много малки, може би от порядъка на хиляди процесорни цикъла. Ето защо аз питам за децентрализиран алгоритъм. Може би ще внедря и двете и ще видя кое работи по-добре. - person João Rafael; 03.08.2011

arrow_upward
0
arrow_downward

Ако дадена задача се опита да заключи обекти само за да се провали в даден момент, възможно е друга задача да не успее да заключи обект, тъй като първата задача го притежава в момента.

Мисля, че бих използвал глобално заключване, когато се опитвам да придобия ключалките първоначално и може би също така, когато ги освобождавам накрая.

Бих се тревожил за максимална едновременност, когато едно просто решение се окаже неадекватно на практика.

person MRAB    schedule 01.08.2011
comment
На теория тези задачи се изпълняват много бързо и нишките през повечето време ще се опитват да измислят задача, която да изпълнят. Използването на глобално заключване ще влоши проблема, тъй като процесът на вземане на решение ще бъде направен от една нишка, вместо да бъде разпределен. - person João Rafael; 02.08.2011