Method of managing the execution of tasks of a multithreaded program according to a given dependency graph
Performance is one of the main non-functional requirements for software. As a result of the increase in the number of cores in central processing units in recent decades, the use of multithreading technology has become a primary means of improving software performance. This study analyzes the proble...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2024
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/642 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-642 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/76/9f21f8eeb760cf99b0ef1396d34af976.pdf |
| spelling |
pp_isofts_kiev_ua-article-6422025-02-15T13:30:00Z Method of managing the execution of tasks of a multithreaded program according to a given dependency graph Метод управління виконанням задач багатопотокової програми за заданим графом залежностей Nesterenko, K.P. Stetsenko, I.V. software; multithreading; performance; reliability; dependency graph; parallel computing; С++ UDC 004.41+004.42 програмне забезпечення; багатопотоковість; швидкодія; надійність; граф залежностей; паралельні обчислення; C++ УДК 004.41+004.42 Performance is one of the main non-functional requirements for software. As a result of the increase in the number of cores in central processing units in recent decades, the use of multithreading technology has become a primary means of improving software performance. This study analyzes the problems that arise from developing multithreaded programs and ways to address them. A method for managing the execution of tasks in a multithreaded program based on a given dependency graph is proposed and its implementation in the C++ language is demonstrated. Its aim is to reduce the resource intensity of software development and increase its reliability by addressing problems typical of developing multithreaded programs. The results of experimental research on a test set of tasks are provided, demonstrating increased performance through the use of the proposed method.Prombles in programming 2024; 2-3: 239-246 Швидкодія є однією з головних нефункціональних вимог до розробки програмного забезпечення. Як наслідок збільшення кількості ядер центральних процесорів протягом останніх десятиліть, використання технології багатопотоковості стало основним засобом підвищення швидкодії програмного забезпечення. У даному дослідженні аналізуються проблеми, які виникають в результаті розробки багатопотокових програм, та способи їх вирішення. Запропоновано метод управління виконанням задач багатопотокової програми за заданим графом залежностей та розглянута його реалізація мовою C++. Його метою є зменшення ресурсоємності розробки програмного забезпечення та збільшення його надійності шляхом вирішення проблем, характерних для багатопотокових програм. Наведено результати експерименального дослідження на тестовому наборі задач, що доводять збільшення швидкодії за рахунок використання запропонованого методу.Prombles in programming 2024; 2-3: 239-246 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/642 10.15407/pp2024.02-03.239 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 239-246 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 239-246 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 239-246 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/642/694 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-15T13:30:00Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
software multithreading performance reliability dependency graph parallel computing С++ UDC 004.41+004.42 |
| spellingShingle |
software multithreading performance reliability dependency graph parallel computing С++ UDC 004.41+004.42 Nesterenko, K.P. Stetsenko, I.V. Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| topic_facet |
software multithreading performance reliability dependency graph parallel computing С++ UDC 004.41+004.42 програмне забезпечення багатопотоковість швидкодія надійність граф залежностей паралельні обчислення C++ УДК 004.41+004.42 |
| format |
Article |
| author |
Nesterenko, K.P. Stetsenko, I.V. |
| author_facet |
Nesterenko, K.P. Stetsenko, I.V. |
| author_sort |
Nesterenko, K.P. |
| title |
Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_short |
Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_full |
Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_fullStr |
Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_full_unstemmed |
Method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_sort |
method of managing the execution of tasks of a multithreaded program according to a given dependency graph |
| title_alt |
Метод управління виконанням задач багатопотокової програми за заданим графом залежностей |
| description |
Performance is one of the main non-functional requirements for software. As a result of the increase in the number of cores in central processing units in recent decades, the use of multithreading technology has become a primary means of improving software performance. This study analyzes the problems that arise from developing multithreaded programs and ways to address them. A method for managing the execution of tasks in a multithreaded program based on a given dependency graph is proposed and its implementation in the C++ language is demonstrated. Its aim is to reduce the resource intensity of software development and increase its reliability by addressing problems typical of developing multithreaded programs. The results of experimental research on a test set of tasks are provided, demonstrating increased performance through the use of the proposed method.Prombles in programming 2024; 2-3: 239-246 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/642 |
| work_keys_str_mv |
AT nesterenkokp methodofmanagingtheexecutionoftasksofamultithreadedprogramaccordingtoagivendependencygraph AT stetsenkoiv methodofmanagingtheexecutionoftasksofamultithreadedprogramaccordingtoagivendependencygraph AT nesterenkokp metodupravlínnâvikonannâmzadačbagatopotokovoíprogramizazadanimgrafomzaležnostej AT stetsenkoiv metodupravlínnâvikonannâmzadačbagatopotokovoíprogramizazadanimgrafomzaležnostej |
| first_indexed |
2025-07-17T09:36:52Z |
| last_indexed |
2025-07-17T09:36:52Z |
| _version_ |
1850412931434414080 |
| fulltext |
239
Паралельне програмування
УДК 004.41+004.42 http://doi.org/10.15407/pp2024.02-03.239
К.П. Нестеренко, І.В. Стеценко
МЕТОД УПРАВЛІННЯ ВИКОНАННЯМ ЗАДАЧ
БАГАТОПОТОКОВОЇ ПРОГРАМИ ЗА ЗАДАНИМ ГРАФОМ
ЗАЛЕЖНОСТЕЙ
Швидкодія є однією з головних нефункціональних вимог до розробки програмного забезпечення. Як
наслідок збільшення кількості ядер центральних процесорів протягом останніх десятиліть, використан-
ня технології багатопотоковості стало основним засобом підвищення швидкодії програмного забезпе-
чення. У даному дослідженні аналізуються проблеми, які виникають в результаті розробки багатопото-
кових програм, та способи їх вирішення. Запропоновано метод управління виконанням задач багатопо-
токової програми за заданим графом залежностей та розглянута його реалізація мовою C++. Його ме-
тою є зменшення ресурсоємності розробки програмного забезпечення та збільшення його надійності
шляхом вирішення проблем, характерних для багатопотокових програм. Наведено результати експери-
менального дослідження на тестовому наборі задач, що доводять збільшення швидкодії за рахунок ви-
користання запропонованого методу.
Ключові слова: програмне забезпечення, багатопотоковість, швидкодія, надійність, граф залежностей,
паралельні обчислення, C++
K.P. Nesterenko, I.V. Stetsenko
METHOD OF MANAGING THE EXECUTION OF TASKS
OF A MULTITHREADED PROGRAM ACCORDING TO
A GIVEN DEPENDENCY GRAPH
Performance is one of the main non-functional requirements for software. As a result of the increase in the
number of cores in central processing units in recent decades, the use of multithreading technology has become
a primary means of improving software performance. This study analyzes the problems that arise from
developing multithreaded programs and ways to address them. A method for managing the execution of tasks
in a multithreaded program based on a given dependency graph is proposed and its implementation in the C++
language is demonstrated. Its aim is to reduce the resource intensity of software development and increase its
reliability by addressing problems typical of developing multithreaded programs. The results of experimental
research on a test set of tasks are provided, demonstrating increased performance through the use of the
proposed method.
Keywords: software, multithreading, performance, reliability, dependency graph, parallel computing, С++
Вступ
Основна мета використання бага-
топотокового підходу під час розроблення
програмного забезпечення – це підвищен-
ня показників швидкодії програмного ко-
ду. Проте інший, не менш важливий ас-
пект багатопотокової розробки - це збе-
реження надійності програмного забезпе-
чення.
Використання багатопотоковості та
інструментів синхронізації може призвести
до ряду помилок: Data race, Race Condition,
Deadlock, Livelock та Starvation [2].
Наявність цих проблем в коді під
час виконання програми може призводити
до різних наслідків - від крешів до непе-
редбачуваної або некоректної поведінки
програми. Підходи до вирішення проблем
багатопотоковості можуть суттєво відріз-
нятися залежно від використовуваної мо-
ви програмування, фреймворку, засобів
розробки тощо. Проте усі вони мають пев-
ні недоліки у застосуванні, оскільки мо-
жуть негативно впливати як на ресурсоєм-
ність процесу розробки, так і на швидко-
дію розробленого програмного коду.
Принципово ці підходи можна поділити на
два типи: ті, що не дозволяють виникнення
помилки, та ті, що дозволяють інженеру
© К.П. Нестеренко, І.В. Стеценко, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
240
Паралельне програмування
виявити помилку в тому випадку, коли
вона сталася.
Метою даного дослідження є змен-
шення ресурсоємності розробки багатопо-
токових програм та підвищення їхньої на-
дійності за рахунок розробки програмних
засобів, які дають змогу запобігти виник-
ненню або сприяти швидкому виявленню
помилки в коді багатопотокової програми.
1. Огляд існуючих рішень
1.1. Data race. Data race виникає у
тих випадках, коли два потоки звертаються
одночасно до однієї і тієї самої ділянки
пам’яті, водночас хоча б один з них вико-
нує операцію запису [2]. Класичним меха-
нізмом для запобігання виникнення Data
race у багатопотоковому коді є викорис-
тання синхронізації. За допомогою синх-
ронізованого доступу до даних, можливо
гарантувати, що певна ділянка пам’яті од-
ночасно може бути модифікована лише
одним потоком, або що вона не буде мо-
дифікована в процесі вичитування її пото-
ком. Інструменти синхронізації є не-
від’ємною складовою сучасних мов про-
грамування і продовжують розвиватися,
розширюючи можливості розробників у
керуванні багатопоточною програмою та її
ресурсами, наприклад, С++ Concurrency
Library [3].
Проте використання примітивів си-
нхронізації має свої недоліки, основним з
яких є зменшення швидкодії програмного
коду. Окрім того, що безпосередньо сам
факт застосування примітиву, як-от, захо-
плення м’ютекса потоком, займає додатко-
вий час на виконання, також значна кіль-
кість часу може бути втрачена потоками на
очікування, доки звільниться ресурс, за-
хищений примітивом синхронізації.
Для підвищення швидкодії програ-
много коду розробники все частіше засто-
совують підходи до розробки програмного
забезпечення без використання примітивів
синхронізації, які блокують виконання
потоків [4]. Проте в такому випадку знач-
но підвищується ризик виникнення про-
блеми Data race. Для вирішення цієї про-
блеми використовують різноманітні засо-
би, які виявляють дану помилку безпосе-
редньо під час виконання програмного
коду, наприклад, Data Race Detector у мові
програмування Golang [5], або статично
аналізуючи написаний програмний код [6].
Останнім часом з’являються напра-
цювання, пов’язані із застосуванням шту-
чного інтелекту для виявлення Data race в
програмному коді [7]. Проте використання
подібних засобів для виявлення Data races
теж має недоліки, оскільки вимагає впро-
вадження додаткових інструментів у про-
цесі розроблення та тестування програм-
ного забезпечення, які збільшують загаль-
ну ресурсоємність розробки.
1.2. Race condition. Race condition,
на відміну від Data race, є набагато склад-
нішою для виявлення проблемою, оскільки
природа її не технічна, а семантична. Ви-
значення терміну Race condition можна
формалізувати як проблему, яка виникає
внаслідок того, що від порядку виконання
операцій в потоках, змінюється результат
виконання програми [8].
Аналогічно з помилкою Data race,
для виявлення Race condition існують певні
засоби, які за допомогою статичного аналі-
зу коду [9] або за рахунок виявлення небе-
зпечних шаблонів під час виконання коду
[10] попереджають розробника про потен-
ційну можливість виникнення даної про-
блеми. Проте точність подібного виявлен-
ня часто не є задовільною.
Водночас формалізованих методів
та засобів для уникнення Race condition в
загальному випадку немає. Зменшити кі-
лькість даних помилок або уникнути їх в
цілому можна тільки використовуючи пе-
вні методи та архітектурні підходи до роз-
робки багатопотокових програм [11].
1.3. Deadlock. Deadlock – це стан
багатопотокової програми, коли два або
більше потоків не можуть продовжити
своє виконання через взаємне блокування
одне одного. Класичною стратегією для
уникнення проблеми Deadlock є підхід, в
якому отримання потоком усіх необхідних
йому ресурсів відбувається виключно на
початку його виконання [12]. Таким чином
унеможливлюється ситуація, коли може
утворитися циклічна залежність між двома
потоками. Потік або виконується, або че-
кає доки не звільняться усі потрібні йому
241
Паралельне програмування
ресурси. Проте даний підхід негативно
впливає на показники швидкодії, оскільки
в загальному випадку потоку не потрібні
усі ресурси в кожен окремий момент вико-
нання, і відповідно в цей час вони могли б
бути використані іншими потоками.
Для виявлення Deadlock існує бага-
то різноманітних методів та алгоритмів.
Наприклад, можна за допомогою таймерів
контролювати час виконання певних кри-
тичних ділянок коду у потоках і, якщо цей
час виконання перевищує певне граничне
значення, повідомляти розробника про
потенційний Deadlock [12]. Також варто
зазначити, що для Deadlock існують стра-
тегії відновлення виконання програми у
випадку його виникнення [13], що надзви-
чайно важливо для систем з підвищеними
вимогами до надійності.
1.4. Starvation. Starvation – це стан
багатопотокової програми, коли один з
потоків не може виконувати задачу через
неможливість отримати доступ до потріб-
них ресурсів. Такий стан може виникнути
через помилки в проєктуванні багатопото-
кових програм, коли захищені примітива-
ми синхронізації ресурси використовують-
ся потоками впродовж тривалого часу.
Через це інші потоки витрачають значну
кількість часу в очікуванні звільнення пот-
рібного ресурсу.
Для уникнення Starvation зазвичай
використовують алгоритми пріоритезації
[14] або планування задач [15], які гаран-
тують, що в певний момент часу задача
буде виконана, та дозволяють розподілити
задачі таким чином, щоб мінімізувати ви-
трати часу на очікування звільнення ресу-
рсів.
Для виявлення Starvation можуть
використовуватися різноманітні програмні
засоби, які досліджують метрики про час
виконання окремих функцій в потоках і
дають змогу розробнику виявити та випра-
вити проблемні ділянки програмного коду
[16]. Подібні засоби часто інтегрують в
процеси автоматизації тестування програ-
много забезпечення для того, щоб постійно
контролювати стан програмного коду та
повідомляти розробників про аномалії чи
проблеми щодо швидкодії.
В результаті аналізу існуючих про-
блем багатопотоковості та можливих варі-
антів їх рішень, можна стверджувати, що
вирішення даних проблем суттєво збіль-
шує ресурсоємність розробки багатопото-
кового програмного забезпечення. Також
деякі з існуючих рішень негативно впли-
вають на швидкодію програмного забезпе-
чення, що ставить розробника перед скла-
дним вибором між швидкодією та надійні-
стю програмного продукту.
Отже, проблема зменшення ресур-
соємності розробки багатопотокового про-
грамного забезпечення без втрат його на-
дійності та показників швидкодії, вимагає
подальшого дослідження.
2. Метод управління виконанням
задач багатопотокової програми
за заданим графом залежностей
2.1. Загальний опис методу. Осно-
вна ідея методу управління виконанням
задач багатопотокової програми на основі
графу залежностей полягає в тому, щоб
задати процес виконання задач, на які роз-
биті обчислення, у вигляді графу залежно-
стей, де кожна вершина графа відповідає
певній конкретній задачі, а дуги графу по-
значають залежності між цими задачами.
Водночас задачі можуть бути виконані
паралельно в потоках з урахуванням об-
межень, накладених залежностями між
ними.
Метод управління виконанням за-
дач багатопотокової програми на основі
графу залежностей дає змогу описати про-
цес виконання багатопотокового програм-
ного коду у зрозумілій та добре структуро-
ваній формі, а також уникати або виявляти
проблеми, що виникають в результаті ви-
користання синхронізації виконання задач.
2.2. Формалізований опис методу.
Припустимо, що для успішного виконан-
ня програми вона має виконати K задач :
A={A0, …, AK-1}. Кожній задачі з множи-
ни A ставиться у відповідність вершина
графу G: G0, …, GK-1. Якщо між задачами
Ai та Aj, де 0 ≤ i, j < K, існує семантична
залежність або задачі Ai та Aj під час сво-
го виконання використовують спільний
ресурс, то між відповідними вершинами
242
Паралельне програмування
графу Gi та Gj існує зв’язок і йому у від-
повідність ставиться у графі дуга (Gi, Gj).
Під семантичною залежністю задач розу-
міємо таку їх залежність, коли результат
виконання програми залежить від послі-
довності виконання задач Ai та Aj і водно-
час тільки один з можливих результатів є
коректним.
Задачі в ході виконання програми
можуть дозавантажуватись, утворюючи
нові вершини та нові дуги у графі, та вида-
лятись у разі успішного виконання. Задача
Ax може бути виконана в програмі тоді і
тільки тоді, коли у графі залежностей не
існує жодної дуги (Gi, Gх), 0 ≤ i < K. Якщо
задача Ax виконана, вона видаляється з
графу разом з дугами (Gх, Gі), де 0 ≤ i < K.
Виконання програми вважається успіш-
ним, коли множина вершин графу залеж-
ностей G на момент завершення програми
є порожньою, тобто усі завантажені на
виконання задачі були виконані.
2.3. Програмний опис методу. Ос-
новою реалізації методу управління вико-
нанням задач багатопотокової програми на
основі графу залежностей є імплементація
класу GraphManager, що буде відповідати
за порядок виконання задач. Відповідно
даний клас повинен контролювати список
наявних задач, обирати задачі, які можуть
бути виконані, та після їх виконання онов-
лювати існуючі залежності.
Для представлення задачі у вигляді
вершини графу залежностей потрібно
створити клаc GraphNode, який буде міс-
тити інформацію про задачу, яка має бути
виконана, та список задач, від яких зале-
жить вона та залежні від неї. Залежності
між задачами встановлюються розробни-
ком після того, як відповідні об’єкти класу
GraphNode були додані у GraphManager.
Під час імплементації методу роз-
робник повинен представити наявні в про-
грамі типи задач у вигляді окремих класів
SomeConcreteJob, які є нащадками абстра-
ктного класу AbstractJob.
2.4. Вирішення проблем багато-
потоковості за допомогою методу. Для
уникнення проблеми Race condition розро-
бнику достатньо вказати на залежність між
задачами, від порядку виконання яких за-
лежить коректність результату роботи
програми. Метод гарантує, що задачі, зі
встановленими залежностями, будуть ви-
конані саме у вказаному порядку одна від-
носно одної.
Для уникнення проблеми Data race
та покращення показників швидкодії, за
рахунок можливості частково відмовитися
від примітивів синхронізації для захисту
доступу до певних об’єктів, розробник має
можливість встановити залежність між
задачами, які вимагають ексклюзивний
доступ до певних ресурсів на час свого
виконання, та дозволити паралельно вико-
нувати задачі, які не модифікують спільні
ресурси.
Не зважаючи на те, що запропоно-
ваний метод не дозволяє уникнути виник-
ненню проблем Deadlock та Livelock, з
його допомогою досить просто імплемен-
тувати механізм, який буде виявляти дані
проблеми ще до початку виконання графу
залежностей. Оскільки проблема Deadlock
виникає у випадку наявності взаємної за-
лежності між синхронізованими ресурсами
у двох потоках, то в контексті даного ме-
тоду, задача пошуку потенційних Deadlock
зводиться до задачі пошуку циклів у графі,
для вирішення якої існує багато розробле-
них алгоритмів [17].
Запропонований метод не дозволяє
повністю уникнути проблеми Starvation.
Проте він дозволяє її мінімізувати, а також
імплементувати механізми моніторингу за
часом виконання та очікування задач без
використання сторонніх засобів контролю.
Метод управління виконанням задач бага-
топотокової програми на основі графу за-
лежностей дає змогу розробнику налашту-
вати граф таким чином, щоб жодна задача
не мала очікувати на звільнення певного
спільного ресурсу після початку свого ви-
конання. Натомість така задача просто не
буде запущена допоки ресурс не звіль-
ниться, тобто не буде виконана вимога
залежності між задачами. Відповідно в цей
час ресурси системи можуть бути спрямо-
вані на виконання задачі, яка в даний мо-
мент часу не має залежностей, або залеж-
ності якої вже були виконані. Проте, це не
дозволяє уникнути випадку, коли існує
задача, на яку існує залежність у великої
кількості інших задач, а відповідно вони не
243
Паралельне програмування
можуть виконуватися допоки вона успіш-
но не завершиться. Для виявлення подіб-
них проблем нескладно імплементувати
механізми, що будуть слідкувати за станом
графу, фіксувати для кожної задачі час її
виконання та час її очікування на виконан-
ня тощо. На основі цієї інформації розроб-
ник зможе вносити зміни до програмного
коду, націлені на виправлення проблених
ділянок коду та покращення показників
швидкодії програмного засобу.
3. Експериментальне дослідження
ефективності методу управління
виконанням задач
багатопотокової програми за
заданим графом залежностей
3.1. Опис тестового програмного
забезпечення. Для перевірки ефективності
запропонованого методу, була розроблена
програма мовою С++, яка за допомогою
шаблону проєктування Strategy, дозволяє
виконати один і той самий набір задач або
за допомогою звичайної реалізації багато-
потокової програми, або на основі графу
залежностей. Для управління потоками
використовується шаблон проєктування
Thread Pool (рис. 1).
Для того, щоб мати можливість
конфігурувати, за допомогою якого підхо-
ду виконувати задачі, був створений інте-
рфейс IJobManager (рис. 2). Інтерфейс ін-
капсулює механізм, за допомогою якого
Thread Pool обирає наступну задачу для
виконання.
Рис. 1. Імплементація шаблону
проєктування ThreadPool у вигляді класу.
Рис. 2. Клас IJobManager.
Інтерфейс IJobManager імплемен-
тований у класах DefaultJobManager (рис.
3) та GraphJobManager (рис. 4). Клас
DefaultJobManager імплементований за
допомогою класичної черги за принци-
пом «перший зайшов – перший вийшов».
Відповідно він відображає класичний
сценарій написання багатопотокової про-
грами, де відповідальність за синхроніза-
цію повністю покладена на примітиви
синхронізації.
Рис. 3. Клас DefaultJobManager.
GraphJobManager в свою чергу ім-
плементований за допомогою запропоно-
ваного методу. В середині класу міститься
структура даних m_graphMap, яка ставить
кожній задачі у відповідність вершину
графу, описану за допомогою класу
GraphNode (рис. 5).
244
Паралельне програмування
Рис. 4. Клас GraphJobManager.
Рис. 5. Клас GraphNode.
Кожен екземпляр класу GraphNode
зберігає в середині себе кількість невикона-
них залежностей для відповідної задачі, або
іншими словами, кількість дуг графу, які
входять у дану його вершину. Також кожен
екземпляр зберігає покажчики на інші екзем-
пляри класу GraphNode, фактично описуючи
дугу графу що виходять з даної вершини.
Коли для вершини графу виконані усі
залежності, вона переміщується у чергу для
виконання в класі GraphJobManager. Також в
класі GraphJobManager присутня функція
AddJobDependency, яка дозволяє вказати на
залежність між задачами, тобто фактично
створити нову дугу у графі залежностей.
3.2. Опис тестового набору даних
та сценаріїв тестування. Для тестування
Thread Pool був сконфігурований пул 4
потоків. Набір тестових задач складений з
4 груп по 100 задач, які можна представи-
ти у вигляді множин A={A0, …, A99},
B={B0, …, B99}, C={C0, …, C99}, D={D0,
…, D99}. Всередині кожної групи, імітую-
чи реальні умови виконання для багатопо-
токової задачі, вважаємо, що існує певний
ресурс, до якого на час виконання задача
отримати ексклюзивний доступ за допомо-
гою м'ютекса. Після цього задача 10 мс
імітує виконання обчислень, використо-
вуючи підхід Busy wait [18], і успішно за-
вершує своє виконання. Використання са-
ме Busy wait обумовлено прагненням уни-
кнути впливу механізмів оптимізації вико-
ристання потоків, реалізованих в опера-
ційній системі, на отриманий результат.
Для отримання більш точних резуль-
татів для порівняння тестовий набір задач
виконується 100 разів для кожної з реаліза-
цій. При цьому збираються наступні метри-
ки: найшвидший час виконання, найгірший
час виконання, середній час виконання.
Щоб отримати показники часу ви-
конання програми, для обчислення задано-
го набору задач за допомогою графу зале-
жностей, побудованого на основі запропо-
нованого методу, замість
DefaultJobManager буде використаний
GraphJobManger. Додаючи задачі у Graph-
JobManger, їй у відповідність буде створе-
на вершина графу, описана за допомогою
класу GraphNode. Далі за допомогою фун-
кції AddJobDependency будуть створені
залежності між задачами, тобто додані
дуги у графі залежностей. В даному випа-
дку об’єктом залежностей є ресурс, виді-
лений для кожної з груп задач. Тоді за до-
помогою функції AddJobDependency ство-
римо залежності між задачами наступним
чином: кожна задача Ai буде залежати від
виконання задачі Ai-1, Bi від Bi-1, Ci від Ci-1
та , Di від Di-1 де i ∈ [1, 99].
Варто зазначити, що, оскільки кла-
сичний підхід до виконання багатопотоко-
вих задач імплементований за допомогою
черги, загальний час виконання задач буде
залежати від їх порядку в цій черзі. Відпо-
відно було розроблено 3 сценарії для тес-
тування класичного підходу: найкращий,
найгріший та реалістичний.
245
Паралельне програмування
Найкращим сценарієм буде вважа-
тися випадок, коли задачі у черзі розміще-
ні так, що кількість часу, витрачена зада-
чами на очікування на доступ до ресурсів,
є мінімальною. Такий сценарій буде відпо-
відати розміщенню задач у черзі, коли во-
на складається з послідовностей задач,
кожна з яких знаходиться у різній групі, а
відповідно вимагає різний ресурс для сво-
го виконання. Тобто послідовність задач в
черзі матиме наступний вигляд: {A0, B0,
C0, D0, …, A99, B99, C99, D99}
Найгіршим сценарієм буде вважа-
тися випадок, коли задачі у черзі розміще-
ні таким чином, що кількість часу, витра-
чена задачами на очікування на доступ до
ресурсів, є максимальною. Такий сценарій
буде відповідати розміщенню задач у чер-
зі, коли групи задач (див. підрозділ 3.2)
розміщені у черзі послідовно. Тобто послі-
довність задач в черзі матиме наступний
вигляд: {A0, …, A99, B0, …, B99, C0, …, C99,
D0, …, D99}.
Реалістичним буде вважатися сце-
нарій, де задачі розміщуються у черзі ви-
падковим чином, імітуючи умови набли-
жені до тих що можуть статися під час
реального виконання програми.
3.3. Результати тестування. Ре-
зультати експериментів, представлені у
таблиці 1, свідчать, що у порівнянні з реа-
лістичним та найгрішим сценаріями вико-
нання, запропонований метод продемонст-
рував значно вищу швидкодію. Цей ре-
зультат було досягнуто за рахунок того,
що дозволяє розробнику самостійно задати
порядок виконання задач за допомогою
введення залежностей між ними (див. під-
розділ 2.1), тим самим зменшивши вплив
механізмів синхронізації на загальний час
виконання програми.
Результат у найкращому сценарії
виконання демонструє мінімальну різницю
у швидкодії на користь класичного підхо-
ду. Це легко пояснюється тим, що у дано-
му випадку порядок виконання задач в
обох підходах співпадає, проте запропоно-
ваний метод має додаткову витрату часу
на побудову та оновлення графу залежнос-
тей. Проте, враховуючи, що в реальних
умовах подібний сценарій може трапитися
надзвичайно рідко.
Таблиця 1
Результати експериментального дослі-
дження швидкодії виконання задач
Сценарій
виконання
задач
Час виконання, мс
найменший найбільший середній
найкращий 1002,95 1007,52 1003,50
найгірший 3913,40 3918,90 3914,39
реалістичний 1513,09 1603,00 1548,52
за графом
залежностей
1005,07 1019,02 1006,70
Отже, за результатами експеримен-
тального дослідження доведено, що запро-
понований метод дає змогу підвищити
швидкодію тестової програми в середньо-
му на 35% у порівнянні з класичним під-
ходом: (1548,52−1006,7)1548,52 ∙ 100 = 35% .
Висновки
Проведено аналіз проблем, які ви-
никають під час розробки багатопотокових
програм. Для кожної з проблем були наве-
дені актуальні методи їхнього вирішення,
визначені переваги та недоліки.
Запропоновано метод управління
виконанням задач багатопотокової про-
грами за заданим графом залежностей.
Описано загальну ідею методу, формаль-
ний опис методу, програмний опис методу,
а також, яким чином даний метод вирішує
зазначені проблеми і які переваги для роз-
робника він забезпечує у порівнянні з іс-
нуючими методами.
Розроблено тестове програмне за-
безпечення та тестовий набір задач, на
якому проведено заміри швидкодії запро-
понованого методу та класичного підходу
до виконання задач у потоках. Проаналізу-
вавши отриманий результат, було зробле-
но висновок, що запропонований метод
дає змогу підвищити швидкодію тестової
програми в середньому на 35% у порів-
нянні з класичним підходом.
В подальшому планується продов-
жити розвиток використання методу для
розробки багатопотокових програм на ос-
нові графу залежностей за рахунок ство-
рення повноцінного середовища розробки
багатопотокових програм на його основі.
246
Паралельне програмування
Література
1. S. Borkar, and Chien, A. (2011) ‘The Future of
Microprocessors’, Communications of the ACM,
54, 67-77.
2. Yuan L., (2006) ‘Multithreaded programming
challenges, current practice, and languages/tools
support’, in 2006 IEEE Hot Chips 18 Symposium
(HCS), Stanford, CA, 2006, pp. 1-134.
3. Gregoire, M. (2021) ‘Multithreaded Programming
with C++’, in Professional C++, 5th Edition. John
Wiley & Sons, pp. 915-967.
4. Fraser, K. and Harris, T. (2007) ‘Concurrent
programming without locks’, ACM Transactions
on Computer Systems, 25, 2, 5–es. Available at:
https://doi.org/10.1145/1233307.1233309 (Ac-
cessed: 13 April 2024).
5. Chabbi, M. and Ramanathan, M. (2022) ‘A study
of real-world data races in Golang’, in
Proceedings of the 43rd ACM SIGPLAN
International Conference on Programming
Language Design and Implementation (PLDI
2022), pp. 474-489.
6. Kahlon, V. et el. (2007), ‘Fast and Accurate Static
Data Race Detection for Concurrent Programs’,
Lecture Notes in Computer Science, 4590, 226-
239.
7. Chen, L. et el. (2023). Data Race Detection Using
Large Language Models’ in SC-W '23: Proceed-
ings of the SC '23 Workshops of The International
Conference on High Performance Computing,
Network, Storage, and Analysis, pp. 215–223.
8. Netzer, R. and Miller, B. (1992) ‘What are Race
Conditions?: Some Issues and Formalizations’,
ACM letters on programming languages and
systems, 1, 74-88. Available at:
https://doi.org/10.1145/130616.130623 (Accessed:
13 April 2024).
9. Flanagan, C. and Freund, S. (2001). Detecting
Race Conditions in Large Programs’ in PASTE
'01: Proceedings of the 2001 ACM SIGPLAN-
SIGSOFT workshop on Program analysis for soft-
ware tools and engineering, pp. 90-96.
10. Yousaf, M. et el. (2021) ‘Efficient Identification of
Race Condition Vulnerability in C Code by Ab-
stract Interpretation and Value Analysis’ in IEEE
International Conference on Cyber Warfare and
Security. Available at:
https://doi.org/10.1109/ICCWS53234.2021.97029
54 (Accessed: 13 April 2024)
11. Ortega-Arjona, J.L. (2004) ‘The Manager Workers
Pattern’ in European Conference on Pattern Lan-
guages of Programs, pp. 53-64.
12. Singhal, M. (1989) ‘Deadlock detection in
distributed systems’, Computer, 22, 37 - 48.
13. Park, Y., Scheuermann, P. and Tung, H. L. (1995),
‘A Distributed Deadlock Detection and Resolution
Algorithm Based on A Hybrid Wait-for Graph and
Probe Generation Scheme’, in CIKM '95:
Proceedings of the fourth international conference
on Information and knowledge management, pp.
378-386.
14. Jabbour, R. and Elhajj, I. (2008) ‘SAF-PS:
Starvation Avoidance for Priority Scheduling’ in
2008 5th International Multi-Conference on
Systems, Signals and Devices, SSD'08, 1-6.
Available at:
https://doi.org/10.1109/SSD.2008.4632789 (Ac-
cessed: 13 April 2024).
15. Gawanmeh, A. et el. (2021). Starvation Avoidance
Task Scheduling Algorithm for Heterogeneous
Computing Systems. Available at:
https://doi.org/10.1109/CSCI54926.2021.00339
(Accessed: 13 April 2024).
16. Abbaspour, S. et el. (2016) ‘A Model for
Systematic Monitoring and Debugging of
Starvation Bugs in Multicore Software’. Available
at: https://doi.org/10.1145/2975954.2975958 (Ac-
cessed: 13 April 2024).
17. Nesterenko, A. (2012) ‘Cycle detection algorithms
and their applications’, Journal of Mathematical
Sciences, 182, 518-526.
18. Blieberger, J., Burgstaller, B., Scholz, B. (2003),
‘Busy Wait Analysis’, Lecture Notes in Computer
Science, 2655, 142-152.
Одержано: 06.04.2024
Внутрішня рецензія отримана: 22.04.2024
Зовнішня рецензія отримана: 27.04.2024
Про авторів:
1Нестеренко Костянтин Павлович,
аспірант кафедри інформатики та
програмної інженері
https://orcid.org/0000-0003-3921-4324
1Стеценко Інна Вячеславівна,
доктор технічних наук, професор,
професор кафедри інформатики
та програмної інженерії
http://orcid.org/ 0000-0002-4601-0058
Місце роботи авторів:
1Національний технічний університет
України «Київський політехнічний
інститут імені Ігоря Сікорського»,
03056, м. Київ,
проспект Берестейський 37.
Тел.: (044) 236-9651
e-mail: k.nesterenko@kpi.ua,
stiv.inna@gmail.com
|