Конкурентност
Во рамките на информатичката наука, поимот конкурентност претставува својство на систем кај кој два или повеќе алгоритми се извршуваат паралелно и потенцијално имаат меѓусебна интеракција[1]. Конкурентните системи претставуваат инхерентно дистрибуиран системи. Алгоритмите може да бидат извршени во рамките на еден сметач кој содржи мултиобработувачско јадро или истото може да се извршува на повеќе сметачи, во кој случај станува збор за дистрибуиран компјутерски систем. Голем број на математички модели се развиени за да се опишат интаракциите на конкурентните системи. Најпознат модел е моделот на петри мрежи, додека постојат и други како process calculi, Parallel Random Access Machine и Actor model.
Поради фактот дека текот на извршувањето на алгоритмите кај конкурентните системи е недетерминистички, за да се поедностави анализата на конкурентните системи, како и анализата на алгоритмите кои работат на овие системи, создадени се модели на конкурентни системи во зависност од податоците и операциите кои системот ги извршува. Разликуваме неколку видови и тоа:
- SISD Систем кој извршува една инструкција врз еден податок, т.е. ова претставува централизиран неконкурентен систем.
- SIMD Систем кој извршува една инструкција врз повеќе податоци едновремено
- MISD Систем кој извршива повеќе едновремени операции врз ист податок
- MIMD Системи кои извршуваат повеќе операции врз повеќе податоци
SIMD
уреди"Single instruction multiple data" или Една инструкција за повеќе податоци е модел на конкурентност кај кој системот извршува само една инструкција во дадено време, додека инструкцијата се извршува на низа од податоци. Пример за ваков систем е мултиплицирањето на вектори кај SSD обработувачите. Вередностите на векторот се спакувани во континуирана мемориска локација, додека обработувачот извршува само една инструкција која се пропагира низ сите ќелии во кои се сместени податоците од векторот.
SIMT
уреди"Single instruction multiple threads" овој систем е модификација на SIMD системот. Разликата е во тоа што кај овој систем, за секој од податоците е поврзана состојба (или нишка) која е локална за тој податок. Пример за ваков систем е графичкиот обработувач. Пример за обработка на ваков систем претставува примерот за кластер од сметачи кои извршуваат Map-Reduce алгоритам. Секој од јазлите во кластерот ќе ја извршува истата Map инструкција врз еден од низата на податоци, па оттука системот гледан како целина ќе извршува една операција (функцијата мап) на повеќе податоци. Во ваквиот модел најчесто се јавува проблемот на "редослед на промена на податоците" и проблемот на "користење стари податоци".
MIMD
уреди"Multiple instructions multiple data" овие системи се најсложени конкурентни системи. Системот овозможува секој од сегментите да извршува резлични операции врз различни податоци. Пример за ваков систем претставува кластер од сметачи кои поддржуваат дистривуиран податотека систем. Секој од јазлите во кластерот, во исто време, извршува различна операција (читање или пишување) врз различни податоци (различни податотеки). Поради сложеноста на овие системи, кај нив најчесто можат да се јават следниве проблеми: "користење стари податоци", "заклучување на ресурси", "блокирање".
Проблеми поврзани со конкурентноста
уредиПоради тоа што процесите во рамките на конкурентниот систем имаат меѓусебна интеракција, бројот на возможни патеки на извршување е значајно голем, што како резултат може да доведе до тоа однесувањето на системот да биде недетерминистичко, т.е. да не може да се предвиди крајниот резултат врз основа на зададените влезни параметри. Конкурентното користење на споделени ресурси може да довде до блокирање (dead-lock) и до појава на феноменот наречен "изгладнување"[3].
Користење на стари податоци
уредиКористењето на стари податоци претставува проблем на конкурентност кој настанува кога кај алгоритмот постои временска разлика помеѓу моментот кога податоците се прочитани и моментот кога податоците се употребени. За полесно да го илустрираме проблемот, да го земеме за пример следниов сегмент на код:
a = b;
a = a + 1;
if (a == b+1 ) {
System.out.println ("Нема проблем со стари податоци");
} else {
System.out.println("Настана проблем со стари податоци");
}
За системот да може да ја изврши втората линија од кодот, системот треба повторно да ја прочита вредноста на а од мемориската локација во која е сместена променливата. Очекувано е дека по извршувањето на втората линија, a ќе ја има вредноста на b+1, па така линијата 3 ќе биде вистинита и системот ќе испечати "Нема проблем со стари податоци". Ова е точно кај неконкурентните системи, додека кај конкурентните системи, постои можност друг алгоритам кој се извршува едновремено на системот да ја има променето вредноста на b, па така при извршувањето на линијата 3, изразот (а == b+1) ќе биде невистински и алгоритмот ќе испише "Настана проблем со стари податоци".
Надминувањето на овие проблеми најчесто се врши со заклучување на ресурсите за да не дојде до промена додека алгоритмот работи на нивна промена.
Заклучување на ресурси
уредиЗаклучувањето на ресурси се врши заради синхронизација на алгоритмите кои работат на конкурентниот систем. Најчест проблем кои се јавува при ваквото заклучување е проблемот на отклучување на ресурсот, имено, доколку поради несоодветно кодирање или поради непредвидена грешка, алгоритмот кој го има заклучено ресурсот не е во состојба да го отклучи ресурсот, сите останати алгоритми кои работат на системот ќе чекаат бесконечно ресурсот да стане достапен.
Блокирање
уредиБлокирањето е проблем кој е последица на заклучувањето на ресурсите во конкурентен систем. Доколку во системот имаме повеќе учесници (алгоритми) кои користат повеќе од еден заеднички ресурс, иако редоследот на залкучување и отклучување на ресурсот за секој од дадените алгоритми е детерминистички, вкупниот редослед по кој ресурсите ќе се заклучуваат или отклучуваат во системот стануве многу комплексен и тежнее да биде недетерминистичен. Последица на ваквата недетерминираност е веројатноста да еден алгоритам, кој користи два ресурси, успее да ги зајкучи првиот ресурс и да чека на заклучување на вториот ресурс (поради тоа што вториот ресурс сè уште е во употреба). Доколку алгоритмот кој го има заклучено вториот ресурс, зависи од првиот ресурс (и чека тој да стане достапен за да го заклучи), настанува блокирање на системот. Првиот алгоритам нема да може да заврши и да го ослободи првиот ресурс пред вториот ресурс да стане достапе, и обратно, вториот алгоритам нема да може да заврши пред првиот ресурс да стане достапен. Двата алгоритми ќе се чекаат меѓусебно бесконечно долго. Најпознат пример за илустрација на блокадата е примерот за филозовската вечера. Овој пример отсликува навидум едноставен систем заснован на едноставни правила (филозофот или чека на стапчињата или јади), кој поради ефектите на конкурентноста, може да влезе во состојба на блокада. Наједноставен начин на надминување на блокадата во системите е да се воведе квазистохастички временски интервал на чекање на ресурсот да стане достапен по што алгоритмот би се откажал, би ги ослободил сите заклучени ресурси и би чекал квазистохастички временски интервал за да проба повторно да се обиде да ги заклучи сите ресурси и да ја заврши зададената работа.
Редослед на промена на податоците
уредиРедоследот на кој податоците се променети, иако навидум личи на тривијално прашање гледано од аспект на краен резултат, може да има последици врз системот. Да земеме за пример две банкарски трансакции, едната е +1000 денари а другата е -800 денари. Доколку двете се аплицираат на една сметка (која има почетна состојба 0), како краен резултат ќе дадат +200 денари. Но, ако земеме дека прво била направена трансакцијата од -800 денари, тогаш сметката влегла во негативно салдо и истата е предмет на пресметка на затезна камата, доколку ако прво била направена трансакцијата од +1000 денари, сметката била предмет на пресметка на позитивна камата. Икао ова сè уште делува тривијално, кога системот ќе се пондерира врз интербанкарски трансакции, проблемот на редоследот на трансакции достигнува милионски суми. При дизајнирање на конкурентни системи треба да се води сметка за ефектот кој редоследот на трансакции го има врз финалната состојба на системот. Наједноставен трик за обезбедување на правилен редослед е употребата на растечки број со кој се маркира секоја трансакција. Системот може да го заклучи редоследот на трансакции според растечкиот број на трансакцијата. Ова може да се модифицира кај дистрибуираните системи со употреба на временски маркер, т.е. секоја трансакција се маркира со времето во кое трансакцијата настанала.
За еден ситем велиме дека е конвергентен доколку системот, без разлика на бројот и видот на меѓусостојби, секогаш завршува во една иста состојба. Пример од областа на физиката е системот со една пружина на која е обесен еден тег. Кога системот е смирен (тегот е во нултата точка), гравитацијата која делува не тегот е поништена од силата на пружината. Доколку тегот се помести од нултата точка системот почнува да оцилира. Осцилациите се пригушени, па по извесно време системот повторно ќе ја воспостави балансот помеѓу гравитацијата и силата на пружината, т.е. осцилациите на системот ќе конвергираат во нултата точка. Друг пример за балансиран систем е системот за книговодство. Без разлика на бројот на промени во системот, крајното салдо во главната книга е секогаш 0 или системот е балансиран. Во реалниот свет, системот за книговодство работи во услови на дистрибуирана аквизиција на податоци и интегрирано пренесување на податоци (од други системи кон системот за книговодство). Во ваква конкурентна ситуација, посои голема веројатност да настане случајна или намерна грешка во податоците и системот за книговодство да престане да биде балансиран, т.е. крајното салдо во главната книга да е различно од 0. Ова го нарекуваме неконвергентна состојба на системот. За да се надмине овој проблем, системот дозволува вметнување на корекциона трансакција која по извршувањето ќе го врати системот во балансирана состојба. При дизајнирање на конкурентни системи мора да се предивди начин со кој состемот ќе може да се врати во балансирана состојба, т.е. потребно е да се предвидат неконвергентните состојби кои системот може да ги заземе и за сите нив да се обезбеди метод со кој системот ќе се врати во балансирана состојба. Треба да се напомене дека предвидувањето на начините на кој системот може да заземе неконвергентна состојба и нивно анулирање, икао нетреба да биде занемарено, е помалку продуктивно поради тоа што постојат условно неограничен број на начини на кој системот може да заземе неконвергентна состојба, додкеа постојат релативно мал број на неконвергентни состојби кои системот може да ги заземе.
Поврзано
уредиНаводи
уреди- ↑ „Concurrency (computer science)“. Wikimedia Foundation, Inc.
- ↑ Flynn, Michael J (September, 1972). „Some Computer Organizations and Their Effectiveness“. IEEE Transactions on computers. C-21 (9): 948–960. doi:10.1109/TC.1972.5009071. Проверете ги датумските вредности во:
|date=(help) - ↑ Cleaveland, Rance; Scott Smolka (December, 1996). „Strategic Directions in Concurrency Research“. ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252. Проверете ги датумските вредности во:
|date=(help) - ↑ Anderson, Ross (2008). Security Engineering: A Guide to Building Dependable Distributed Systems. Wiley Publishing. ISBN 9780470068526.
Дополнителна литература
уреди- Taubenfeld, Gadi (2006). Synchronization Algorithms and Concurrent Programming. Pearson / Prentice Hall. стр. 433. ISBN 0131972596.
- Leppäjärvi, Jouni (2008). A pragmatic, historically oriented survey on the universality of synchronization primitives (PDF). University of Oulu. Архивирано од изворникот (PDF) на 2011-07-17. Посетено на 2011-05-13.