НОУ ІНТУІТ, Лекція, Планувальник завдань
Планувальник завдань грає сполучну роль між завданнями (робочими елементами) та потоками. Безліч завдань програми виконується одними й тими самими робочими потоками, кількість яких динамічно оптимізується планувальником з урахуванням можливостей обчислювальної системи, фактичної завантаженості системи та прогресом виконання завдань. Планувальник завдань включає черги завдань (одна глобальна і безліч локальних черг), стратегії розподілу завдань та робочі потоки, які фактично виконують завдання.
Організація паралельного застосування за допомогою пулу потоків дозволяє уникнути накладних витрат, пов'язаних із запуском та завершенням потоків для кожного фрагмента в програмі, що допускає розпаралелювання.
Таким чином, додаток складається з основного потоку, в якому можуть запускатися нові потоки користувача, і набору робочих потоків. Робочі потоки існують протягом усього життя програми; спочатку знаходяться в "сплячому" стані, але можуть бути задіяні для обробки завдань користувача. Робочі потоки включаються в обробку, якщо код програми є робота з об'єктами бібліотеки Task Parallel Library ( Task , Parallel , PLINQ ) або безпосередня робота з пулом потоків ThreadPool.
У наступному фрагменті перевіряємо, чи дійсно робочі потоки здійснюють обробку завдань користувача:
Отже, отримуємо, що завдання Task виконується в пулі, методи Parallel.Invoke, Parallel.For не явно створюють завдання, які також виконуються в пулі. Метод Main і потік користувача не є робочими потоками пула. Частина роботи, що визначається методами Parallel.Invoke , Parallel.For , може виконувати в основному потоці.
Пул потоків складається з глобальної черги,організованої за принципом FIFO , та безлічі локальних черг, організованих за принципом LIFO. Дисципліна черги FIFO (first-in, first-out) передбачає, що перший доданий елемент першим надійде на обробку. Робочі потоки звертаються до глобальної черги та одержують завдання на обробку. Доступ кількох потоків до одного ресурсу – черги завдань – вимагає застосування синхронізації для уникнення проблеми гонки даних. Синхронізований доступ потоків знижує швидкодію обробки. Чим менше "обчислювальне навантаження" завдань, тим частіше потоки змагаються за доступ до черги.
Для зменшення накладних витрат, пов'язаних із необхідністю синхронізації доступу потоків до глобальної черги, структуру пулу потоків введено локальні черги. Кожна локальна черга відповідає одному робочому потоку.
Локальні черги призначені для вкладених завдань. Завдання, які оголошуються і запускаються з потоку користувача, є завданнями верхнього рівня ( top-most level tasks ). Такі завдання містяться у глобальну чергу і розподіляються по робочих потоках. При виконанні задачі верхнього рівня робочий потік додає у свою локальну чергу всі вкладені завдання.
Вкладені завдання розміщуються в локальну чергу робочого потоку, в якому виконується батьківське завдання. Локальні черги організовані за принципом LIFO (last-in, first-out). Першим вкладеним завданням, яке буде виконуватися робочим потоком, буде те завдання, яке додано до черги останньої. Такий порядок пояснюється можливою локальністю даних. Остання додана вкладена задача використовує загальні дані у найближчому оточенні.
Завдяки стратегії планувальника inlined execution (див. нижче), не варто побоюватися блокування потоку, якщоостаннє вкладене завдання посилається на попереднє підзавдання (очікує завершення або події попереднього завдання).
Опція PreferFairness
Якщо зворотний порядок виконання завдань не бажаний, можна використовувати опцію PreferFairness під час створення завдань. Такі завдання містяться у глобальну чергу. Організація глобальної черги за принципом FIFO дозволяє сподіватися, що вкладені завдання, створені з опцією PreferFairness, виконуватимуться в порядку додавання.
Розглянемо наступний фрагмент:
У цьому фрагменті – одне завдання верхнього рівня, яке міститься у глобальну чергу. При обробці завдання tMain в одному з робочих потоків вкладені завдання t1 і t2 поміщаються в локальну чергу робочого потоку. Завдання t3 і t4 створені з опцією PreferFairness, тому додаються до глобальної черги. Порядок обробки вкладених завдань локальної черги – зворотний порядок додавання. Спочатку оброблятиметься завдання t2, потім t1. Завдання t3 і t4 обробляються порядку додавання, тобто. спочатку t3, потім t4. У якому робочому потоці фактично виконуватиметься завдання t1, t2, t3 і t4 залежить від завантаженості інших робочих потоків (див. механізм WorkStealing). Але можна сказати, що з завдань t1 і t2 створені передумови послідовного виконання у тому робочому потоці, як і батьківське завдання tMain . Для завдань t3 і t4 створено передумови паралельного виконання інших робочих потоках пула. Слід пам'ятати, що виконання вкладених завдань інших робочих потоках то, можливо пов'язані з накладними витратами під час використання даних батьківської завдання.
Таким чином, опція PreferFairness застосовується не для зміни порядку виконання завдань (для цього простіше змінити порядок додавання вкладених задач у локальнучерга ), а забезпечення умов паралельного виконання вкладених завдань у різних робочих потоках.
Оптимізація виконання завдань виконується за допомогою трьох стратегій планувальника: стратегія запозичення завдань (work-stealing), стратегія динамічної зміни числа робочих потоків (thread-injection), стратегія inlined execution.
Стратегія Work Stealing
Стратегія work-stealing полягає в тому, що вільний робочий потік за умови відсутності завдань, що очікують, у глобальній черзі запозичує завдання в одного із завантажених робочих потоків. Для вирішення проблеми синхронізації доступ до кожної локальної черги здійснюється за допомогою двох ключів: private key – покажчик на останній доданий елемент (завдання), який використовується лише одним робочим потоком – утримувачем черги; public key - покажчик на перший доданий елемент, який використовується сторонніми робочими потоками для запозичення (work-stealing).
Синхронізація реалізована лише відкритого ключа, оскільки є можливість звернення кількох вільних робочих потоків до локальної черги зайнятого потоку. Механізм запозичення завдань вносить корективи у обробку вкладених завдань. Якщо запозичення завдань немає, то вкладені завдання виконуються послідовно щодо одного робочому потоці порядку зворотному додаванню. При запозиченні вкладені завдання можуть виконуватися паралельно різних робочих потоках.
Стратегія Inlined Execution
Стратегія inlined execution застосовується у разі блокування завдання, що виконується. Якщо завдання, що виконується, блокується викликом очікування завершення завдання, яка знаходиться в локальній черзі цього ж робочого потоку, то планувальник виконує завдання з черги. Така стратегія дозволяєуникнути взаємоблокування робочого потоку (dead-lock), яка може виникнути при певному порядку вкладених завдань у локальній черзі. Стратегія inlined execution застосовується лише до завдань у локальній черзі блокованого робочого потоку.
Розглянемо наступний фрагмент:
У задачі tParent по черзі додаються до локальної черги tChild1 , tChild2. Передбачається, що спочатку має завершити свою роботу батьківське завдання, потім керування буде передано задачі tChild2, і тільки після цього tChild1 . Але оператор очікування Wait блокує батьківське завдання. Без стратегії планувальника Inlined thread поточний робочий потік був заблокованим. Але насправді планувальник (середовище виконання) фіксує виклик Wait і передає керування очікуваним завданням tChild1.
Стратегія Inlined execution працює при викликах Wait для конкретної задачі в локальній черзі та виклику Wait All для очікування кількох завдань локальної черги. Виклик Wait Any не призводить до передачі керування вкладеним завданням. Це з тим, що у разі методу Wait Any виникає ситуація невизначеності – кому передати управління? Вкладена задача, яка буде обрана першою для виконання та буде переможницею. Метод очікування Wait Any спочатку передбачає змагальність виконання завдань з метою виявлення переможця – завдання, яке першим завершило виконання.
Стратегія Thread-Injection
Стратегія thread-injection застосовується для оптимізації числа робочих потоків. Застосовуються два механізми динамічної зміни числа робочих потоків. Перший механізм застосовується з метою уникнути блокування робочих потоків: планувальник додає ще один робочий потік, якщо не спостерігає прогресу під час виконання завдання. При цьому планувальник нерозрізняє, чи потік дійсно в заблокованому стані, чекаючи будь-якої події, чи потік завантажений корисною тривалою роботою (long-running task). У разі виконання "довгих" завдань така стратегія планувальника не покращує, а навіть погіршує продуктивність. При зростанні числа потоків виникає конкуренція за фізичні ядра обчислювальної системи, з'являються накладні витрати на перемикання контекстів. Щоб уникнути неправильних дій планувальника, рекомендується виконувати більш "короткі" завдання, а довгі обчислювально-ємні завдання запускати з опцією LongRunning:
Ця опція змушує планувальник виділити для завдання власний потік і не контролювати прогрес виконання цього завдання. Потік "довгого" завдання не входить до групи робочих потоків пулу, тому планувальник не застосовує стратегії оптимізації роботи цього потоку і не використовує потік для виконання інших завдань, що очікують в пулі.
Другий механізм стратегії thread-injection додає чи видаляє робочі потоки залежно від результатів виконання попередніх завдань. Якщо збільшення кількості потоків призвело до зростання продуктивності, то планувальник збільшує кількість потоків. Якщо продуктивність не зростає, кількість потоків скорочується. Евристичний алгоритм прагне знайти оптимальну кількість потоків при поточному завантаженні обчислювальної системи. Зменшення обсягу завдань також допомагає планувальнику знайти оптимальний варіант. Другий механізм доповнює перший і дозволяє уникнути необмеженого додавання робочих потоків без покращення продуктивності.