Конкурентні обчислення
Рівночасні [1]або конкурентні обчислення[2] (англ. Concurrent computing) — це форма обчислень, в якій кілька обчислень виконуються співбіжно, протягом часових відрізків, що перетинаються, на противагу послідовному, де виконання одного обчислення має закінчитись до того як почнеться виконання іншого.
Рівночасність є властивістю системи, якою може бути окрема програма, комп'ютер, чи комп'ютерна мережа. В такі системі існують окремі точки виконання, або "потоки керування" для кожного обчислення ("процесу"). Рівночасною' можна назвати систему де обчислення може продовжитись без очікування на завершення всіх інших обчислень.[3]
Як парадигма програмування, рівночасні обчислення є формою модульного програмування, а саме декомпозиція обчислення на підобчислення які можна виконати водночас. Піонерами в цій області є Едсгер Дейкстра, Пер Брінч Гансен[en], та Тоні Гоар.
Конкурентні завдання можуть почергово працювати на одному процесорному ядрі або виконуватися фізично одночасно на різних ядрах. У першому випадку вони ділять процесорний час; у другому — можуть мати спільну пам'ять, дані чи інші ресурси. Тому конкурентність і паралельність не є повними протилежностями: паралельне виконання описує фізичну одночасність роботи, а конкурентне програмування розглядає організацію кількох завдань і керування їхньою взаємодією.[4][5]
Поняття рівночасних обчислень часто плутають з подібним, але дещо відмінним поняттям паралельних обчислень[6][7], хоча обидва описуються як «паралельні процеси що виконуються протягом спільних часових відрізків». У паралельних обчисленнях декілька обчислень існують і відбуваються одночасно в кожну мить фізичного часу (такт процесора), наприклад на різних процесорах багатопроцесорної машини, їх метою є зменшення часу виконання обчислень.
У рівночасних обчисленнях декілька обчислень існують одночасно (як процеси або потоки виконання), але в кожну мить фізичного часу відбувається лише одне обчислення[a]. Паралельні обчислення неможливі на одному одноядерному процесорі, оскільки в таких системах у кожен момент часу може відбуватися лише одне обчислення. Як наслідок, аспекти синхронізації паралельних обчислень визначаються особливостями апаратної платформи, а конкурентних — програмної.
Для спільних даних застосовують синхронізацію. М'ютекс надає одному виконавцеві виключний доступ до захищеної ділянки коду; семафор може обмежувати кількість одночасних користувачів ресурсу; атомарна операція дозволяє виконати окрему зміну як неподільну дію. Ділянку програми, яка потребує такого захисту, називають критичною секцією.[8]
Інший спосіб взаємодії — передавання повідомлень між процесами. У такій системі завдання надсилають одне одному повідомлення через канали або черги, а обробник повідомлення керує власним станом. Цей підхід широко використовують у моделі акторів і мові Erlang. Він дозволяє обмежити прямий доступ до спільної змінюваної пам'яті, хоча порядок повідомлень, місткість черг і доступність отримувачів усе одно потрібно враховувати.[9]
Основна складність конкурентних програм полягає в тому, що їхній результат може залежати від порядку дій різних виконавців. Наприклад, два потоки повинні збільшити спільний лічильник із 0 до 2. Якщо обидва прочитають 0 і кожен запише 1, остаточне значення буде 1. Це приклад стану гонитви (англ. race condition), який виникає через неузгоджений доступ до спільних даних.[10]
Інша проблема — Взаємне блокування (англ. deadlock). Воно виникає, коли кілька завдань очікують на ресурси, які утримують одне одного, і тому не можуть продовжити роботу. Можливе також голодування (англ. starvation), коли певне завдання тривалий час не отримує необхідного ресурсу. Надмірне блокування зменшує продуктивність: додавання нових ядер не прискорить роботу, якщо більшість потоків очікує на доступ до одного ресурсу.[11]
Класичними прикладами задач такого типу є задача виробника і споживача, задача читачів і письменників і задача обідаючих філософів. Усі вони розглядають правила взаємодії кількох виконавців під час роботи зі спільними даними або обмеженими ресурсами.[12]
Конкурентні обчислення використовують в операційних системах для розподілу процесорного часу, на вебсерверах для обслуговування багатьох запитів, у базах даних для узгодження доступу до записів і в програмах із графічним інтерфейсом, щоб тривалі фонові операції не заважали реагувати на дії користувача.[4][13]
Мови й бібліотеки програмування пропонують різні інструменти: Erlang — легковагові процеси та повідомлення, Go — горутини й канали, Java — потоки та пакет java.util.concurrent, Rust — потоки й засоби контрольованого доступу до спільного стану, а бібліотека asyncio для Python — асинхронні завдання, черги й механізми синхронізації.[9][14][15][16][17]
На розвиток теорії конкурентного програмування вплинули дослідження Едсгера Дейкстри щодо взаємного виключення, акторна модель, запропонована Карлом Г'юїттом та його співавторами 1973 року, і модель комунікуючих послідовних процесів Чарлза Гоара (1978).[18][19][20]
У розподілених системах завдання можуть працювати на різних комп'ютерах, обмінюючись повідомленнями через мережу. Коли вони звертаються до спільної служби, черги або узгоджують спільний стан, виникають проблеми доступу до ресурсів і порядку подій. Якщо ж незалежні частини розрахунку виконуються на різних комп'ютерах у різний час, можливість об'єднати результати визначається самим алгоритмом: наприклад, окремі підрахунки можна підсумувати, але взаємозалежні зміни спільного документа можуть вимагати спеціального узгодження.[21][22]
- ↑ Мейнарович, Є.; Кратко, М. (2010). Англійсько-український словник з математики та інформатики 2010. e2u.org.ua (укр.). Процитовано 23 жовтня 2026.
- ↑ Півняк Г. Г., ред. (2010). конкурентне програмування. Тлумачний словник з інформатики (PDF) (укр.). Дніпропетровськ: Національний гірничий університет. с. 385. ISBN 978-966-350-087-4.
- ↑ Operating System Concepts 9th edition, Abraham Silberschatz. «Chapter 4: Threads»
- 1 2 Multithreading Concepts: Concurrency and Parallelism. Multithreaded Programming Guide (англ.). Oracle. Процитовано 24 жовтня 2026.
- ↑ Pike, Rob (11 січня 2012). Concurrency is not Parallelism. The Go Programming Language (англ.). Процитовано 24 жовтня 2026.
- ↑ Pike, Rob (2012-01-11). «Concurrency is not Parallelism». Waza conference, 11 January 2012. Retrieved from http://talks.golang.org/2012/waza.slide (slides) and http://vimeo.com/49718712 (video).
- ↑ Parallelism vs. Concurrency. Haskell Wiki.
- ↑ Synchronization. The Java Tutorials (англ.). Oracle. Процитовано 24 жовтня 2026.
- 1 2 Concurrent Programming. Erlang System Documentation (англ.). Erlang/OTP. Процитовано 24 жовтня 2026.
- ↑ Thread Interference. The Java Tutorials (англ.). Oracle. Процитовано 24 жовтня 2026.
- ↑ Deadlock. The Java Tutorials (англ.). Oracle. Процитовано 24 жовтня 2026.
- ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. Semaphores. Operating Systems: Three Easy Pieces (PDF) (англ.). Arpaci-Dusseau Books.
- ↑ Transaction Isolation. PostgreSQL Documentation (англ.). PostgreSQL Global Development Group. Процитовано 24 жовтня 2026.
- ↑ Effective Go: Concurrency. The Go Programming Language (англ.). Процитовано 24 жовтня 2026.
- ↑ java.util.concurrent. Java Platform, Standard Edition 21 API Specification (англ.). Oracle. Процитовано 24 жовтня 2026.
- ↑ Fearless Concurrency. The Rust Programming Language (англ.). Процитовано 24 жовтня 2026.
- ↑ asyncio — Asynchronous I/O. Python Documentation (англ.). Python Software Foundation. Процитовано 24 жовтня 2026.
- ↑ Dijkstra, E. W. (1965). Solution of a Problem in Concurrent Programming Control. Communications of the ACM (англ.). 8 (9): 569. doi:10.1145/365559.365617.
- ↑ Hewitt, Carl; Bishop, Peter; Steiger, Richard (1973). A Universal Modular ACTOR Formalism for Artificial Intelligence (PDF). Proceedings of the 3rd International Joint Conference on Artificial Intelligence (англ.). с. 235—245.
- ↑ Hoare, C. A. R. (1978). Communicating Sequential Processes (PDF). Communications of the ACM (англ.). 21 (8): 666—677. doi:10.1145/359576.359585.
- ↑ Lamport, Leslie (1978). Time, Clocks, and the Ordering of Events in a Distributed System (PDF). Communications of the ACM (англ.). 21 (7): 558—565. doi:10.1145/359545.359563.
- ↑ Dean, Jeffrey; Ghemawat, Sanjay (2004). MapReduce: Simplified Data Processing on Large Clusters (PDF). Proceedings of the 6th Symposium on Operating Systems Design and Implementation (англ.).
- ↑ Це не враховує паралелізм що може реалізовуватись ядром процесора, такий як конвеєр команд чи векторні інструкції. Одноядерний, однопроцесорний комп'ютер може мати здатність до деякого паралелізму, наприклад при використанні співпроцесора але сам процесор такої здатності не має.
<ref> існують для групи під назвою «lower-alpha», але не знайдено відповідного тегу <references group="lower-alpha"/>