37. Підхід портфеля задач

У разі використання підходу портфеля задач (workpile) або бригади робітників (work crew) робочі потоки здійснюють запити на свої частини роботи (одиниці роботи) із «портфеля задач», який зазвичай є чергою. Під час виконання робочо­му потокові надають можливість додавати нові одиниці роботи в портфель (для наступного використання іншими потоками). Використання моделі завершуєть­ся, коли в портфелі не залишається одиниць роботи; керуючий потік може також припинити виконання явно (якщо, наприклад, воно триває занадто довго або, на­впаки, результату досягнуто раніше, ніж спорожнів портфель задач).

Основні переваги цього підходу полягають у його простоті, автоматичному розподілі навантаження між робочими потоками, добрій масштабованості.

Розглянемо базову послідовність кроків у разі використання портфеля задач.

1. Основний потік створює набір робочих потоків у призупиненому стані, зано­сить у портфель вихідну роботу і відсилає сигнал про це, поновлюючи один із робочих потоків. Після цього він залишається чекати сигналу про закінчення роботи.

2. Робочий потік забирає одиницю роботи з портфеля (звичайно з початку чер­ги), обробляє її та продовжує чекати нової роботи. Наприклад, під час багато- потокового пошуку у файловій системі роботою може бути ім'я каталогу, а її обробкою — обхід цього каталогу.

3. Під час виконання дій робочому потокові може знадобитися створити нову одиницю роботи. Щоб передоручити частину роботи іншому потокові, він до­дає її в портфель (звичайно в кінець черги). Прикладом може бути ситуація, коли під час обходу каталогу трапляється підкаталог. Його ім'я можна помі­стити в портфель, передавши роботу з його обходу іншому потокові.

4. Якщо усі потоки забрали свої роботи з портфеля і жоден не додав нової, остан­ній з потоків, що завершують роботу, відсилає решті сигнал про закінчення роботи.

38. Підхід конвеєра

У разі використання підходу конвеєра (pipeline) задачу передають набору потоків, кожен із яких обробляє дані услід за попереднім потоком і перед тим, як почне обробку наступний, подібно до робітника на конвеєрі. Паралельність алгоритму полягає в тому, що дані можуть переміщатися конвеєром одні за одними, і оброб­ка даних може бути почата задовго до того, як завершиться робота з попередніми. Звичайно способи обробки на кожному етапі конвеєра відрізняються (такий кон­веєр називають гетерогенним); є також гомогенні конвеєри, у яких на кожному етапі виконують той самий код.

Конвеєр є узагальненням моделі виробників-споживачів на п потоків, при цьому

стандартний зв'язок між виробником і споживачем підтримується між будь-яки­ми двома сусідніми потоками конвеєра.

1. Кожен потік очікує отримання даних, після чого він обробляє їх і намагається передати наступному потокові; якщо той не готовий до цього, потік-відправ- ник чекає.

2. Відіславши дані, потік-відправник поновлює потік-одержувач і продовжує очі­кування нових даних.

Цикл роботи конвеєра починається з передавання даних його першому пото­кові, а закінчується тим, що кінцевий одержувач (зазвичай головний потік) чекає отримання даних останнім потоком конвеєра і зчитує ці дані як остаточний ре­зультат.