Конкурентно програмиране

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

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

Пионери в областта на конкурентното програмиране включват Едсхер Дейкстра, Пер Бринк Хансен и Тони Хор.

Конкурентни изчисления

Конкурентните изчисления са свързани с паралелните изчисления, но двете са различни,^[1]^[2] въпреки че концепциите споделят дефиницията „множество процеси, които се изпълняват по едно и също време“.

Паралелните изчисления се изпълняват буквално по едно и също време – примерно, на различни процесорни ядра на устройство с многоядрен процесор – с цел ускоряване на изпълнението. Те не са възможни на едноядрен процесор, защото на такъв може да се извършва само едно изчисление в даден момент. Контрастно на това конкурентните процеси могат да се изпълняват на едно ядро, като се раздели изпълнението на всеки процес на стъпки, отнемащи определено време. По този начин на определен интервал от време се преминава от изпълнението на стъпка от един процес към стъпка от изпълнението на друг процес. Така във всеки един момент се изпълнява само един процес, но множество процеси са частично изпълнени.

Конкурентните изчисления могат да се изпълняват в застъпващи се периоди от време, но без това да е задължително. Структурирането на софтуерните системи като съставени от множество конкурентни, комуникиращи части може да бъде полезно при справянето със сложността, независимо от това дали частите ще се изпълнят паралелно.^[3]^{:с. 1}

Конкурентните изчисления могат да се изпълняват паралелно,^[1]^[4] като се назначи за всеки процес отделен процесор или процесорно ядро или като се разпредели изчислението в мрежа, но в общия случай езиците, инструментите и техниките за паралелно програмиране могат да не са подходящи за конкурентно програмиране, и обратно.

Точното време, в което задачите в конкурентна система се изпълняват, зависи от зададеното разписание и не е задължително те да се изпълняват конкурентно. Например, ако имаме задачи Т1 и Т2:

Т1 може да бъде изпълнена и завършена преди Т2
Т2 може да бъде изпълнена и завършена преди Т1
Т1 и Т2 могат да се изпълнят едновременно на едноядрен процесор, като се редуват стъпките от изпълнението им на определен период от време
Т1 и Т2 могат да се изпълнят паралелно (паралелизъм) на отделни процесори или процесорни ядра

Координиране на достъпът до споделени ресурси

Конкурентното програмиране има за цел да структурира компютърната програма, като я раздели на процеси, които могат да се изпълняват независимо един от друг. Взаимодействието и коректната комуникация между различните процеси и координацията на конкурентния достъп до споделени ресурси са основните предизвикателства при конкурентното програмиране.^[4] Потенциални проблеми включват условие на състезание (race condition), взаимно блокиране (deadlock) и ресурсен глад (resource starvation). Например при следния алгоритъм за теглене на суми от разплащателна сметка представена чрез споделения ресурс „balance“:

  bool withdraw(int withdrawal)
  {
     if (balance >= withdrawal)
     {
         balance -= withdrawal;
         return true;
     }
     return false;
  }

Представете си, че balance=500 и два конкурентни процеса извикват withdraw(300) и withdraw(350). Ако ред 3 при двете операции се изпълни преди ред 5, и двете операции ще намерят условието balance >= withdrawal за вярно и ще се изпълни намаляването на баланса с изтеглените суми. Но, тъй като и двата процеса се изпълняват, общата изтеглена сума ще е по-голяма от оригиналния баланс. Такива проблеми със споделени ресурси изискват употребата на контрол на конкурентността (concurrency control) или не-блокиращи алгоритми (non-blocking algorithm).

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

Модели на конкурентност

Има няколко модела на конкурентно програмиране.

Модел – Участник
- модел за сигурност – Обектна способност
Мрежа на Петри
Изчислителни процеси като:
Входно/ Изходна автоматизация

Изпълнение

Има различни методи за осъществяване на конкурентно програмиране. Например изпълнение на всяко изчислително изпълнение като процес на операционната система или осъществяване на изчислителен процес като набор от нишки в рамките на един процес на операционната система.

Конкурентно взаимодействие и комуникация

Споделена памет: конкурентните компоненти си комуникират чрез промени по съдържанието на обща памет (примерно Java и C#). Този вид конкурентно програмиране обикновено изисква някаква форма на заключване (например mutexes, semaphores или monitors), за да може да се координират отделните нишки. Програма, която изпълнява всички от тях, се нарича thread-safe.
Предаване на съобщения: компонентите си общуват чрез размяна на съобщения (примерно Scala, Erlang and occam). Обменът на съобщения може да се извършва асинхронно или синхронно „рандеву” стил, в който изпращачът се блокира, докато не изпрати съобщението. Пращането на асинхронните съобщения може да е ненадеждно (наричат се ”Прати и се моли”). Предаването на съобщения тенденциозно е по-лесно от Споделената памет и се смята за по-стабилна форма на конкурентно програмиране. Предаването на съобщения може ефективно да се осъществи върху симетрични микропроцесори, със или без споделена памет.

История

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

Разпространение

Конкурентността е силно застъпена в изчислителната техника, като се среща от хардуер на единични чипове до световни мрежи. Следват примери.

На ниво програмен език:

На ниво операционна система:

Computer multitasking, включва и двата (кооперативен и изпреварващ multitasking)
- Time – sharing което заменя последователната пакетна обработка на задачите с конкурентна такава.
Процес
Нишка

На ниво мрежа мрежовите системи обикновено са конкурентни по своя характер, тъй като те се състоят от отделни устройства.

Езици поддържащи конкурентно програмиране

Тези езици често се определят като Конкурентно Ориентирани или Конкурентно Ориентирани Програмни Езици (КОПЕ). Днес, най-често използваните езици за програмиране, които имат специфични конструкции за конкурентност са Java и C#. И двата езика фундаментално използват конкурентният модел Споделена памет със заключване чрез monitors. От езиците ползващи модела Предаване на съобщения може би най-популярен към момента е Erlang. Много конкурентните езици за програмиране са разработени по-скоро като езици за научни изследвания (например Pict), отколкото като езици за производствена употреба. Въпреки това, езици като Erlang, Limbo и occam се използват за промишлена употреба в различни периоди през последните 20 години. Езици, в които конкурентността играе важна роля, са:

Ada
C++
C#
D
Erlang
FORTRAN
Go
Java
JavaScript
LabVIEW
Modula-2
Node.js
Perl
Python и много други.

Вижте също

Паралелни изчисления

Източници

↑ ^а ^б "Concurrency is not Parallelism", Waza conference Jan 11, 2012, Роб Пайк (презентация) (видео)
↑ Parallelism vs. Concurrency // Haskell Wiki.
↑ Schneider, Fred B. On Concurrent Programming. Springer, 1997. ISBN 9780387949420.
↑ ^а ^б Ben-Ari, Mordechai. Principles of Concurrent and Distributed Programming. 2nd. Addison-Wesley, 2006. ISBN 978-0-321-31283-9.

Външни препратки

Конкурентно програмиране в C# – Презентация по темата на СофтУни
Паралелно и разпределено програмиране с Java – Материали по темата на Иван Момчев ТУ – София

[waza-1] а ^б "Concurrency is not Parallelism", Waza conference Jan 11, 2012, Роб Пайк (презентация) (видео)

[2] Parallelism vs. Concurrency // Haskell Wiki.

[3] Schneider, Fred B. On Concurrent Programming. Springer, 1997. ISBN 9780387949420.

[benari2006-4] а ^б Ben-Ari, Mordechai. Principles of Concurrent and Distributed Programming. 2nd. Addison-Wesley, 2006. ISBN 978-0-321-31283-9.

[1]

[2]

[3]

[4]