Зокрема, немає великого сенсу в спробах мультипрограммирования решета Ератосфена, оскільки в ньому натуральний ряд відбирається поступовим відсіювання складених чисел. Або, наприклад, алгоритм визначення деякого числа з ряду Фібоначчі не вдасться зробити багатопотоковим, так як кожний наступний член ряду дорівнює сумі двох попередніх, а значить, треба крок за кроком визначати весь ряд. Та й ні до чого «Паралель» алгоритм визначення факторіала (n! = 1 · 2 · 3 · ... · n), оскільки факторіал числа 65 обчислюється за лічені мілісекунди, а підрахувати факторіал більшого числа вже проблематично, адже розрядність цілочисельних змінних в компіляторах має свої обмеження (наприклад, змінна типу ulong є беззнаковим цілим від 0 до 18446744073709551615).
Проте якщо включити фантазію і уявити себе студентом, який повинен вирішити три перераховані завдання в одному алгоритмі, то можливі цікаві варіанти.
Так, талановитий студент XX в. написав би класичний послідовний код, в загальних рисах схожий на наше рішення, наведене на «Мир ПК-диску» в лістингу 1 (на мові C #). У цьому рішенні з тіла програми в строгій послідовності викликаються основні функції: Number (для знаходження максимального простого числа в певному діапазоні від 1 до nNum), Fibonacci (для визначення члена під номером nFib з ряду Фібоначчі) і Factorial (для обчислення факторіала числа nFac) , які проводять відповідні обчислення для цілочисельних аргументів nNum, nFib, nFac. За замовчуванням nNum = 200 000, nFib = 500 000 000, nFac = 65, але при бажанні в виконавчий процес можна передати інші параметри за допомогою рядка запрошення (наприклад, ось так: PCW_SingleThreadTest.exe 1000 100 10) - експериментуйте.
До речі, з метою наочності і компактності лістингу ми не стали робити так звану «захист від ідіотів», і тому передача в програму символьних змінних (або чисел з плаваючою точкою) призведе до передбачуваною помилку. До того ж не варто забувати і про межі значень цілочисельних типів.
По дорозі відзначимо для допитливих читачів, що функція ToDefineTime є другорядною в нашому алгоритмі і призначається лише для спостереження за «продуктивністю» коду (з її допомогою засікається час в мілісекундах, витрачений на виконання ряду поставлених завдань).
Отже, після компіляції алгоритму з лістингу 1 в системі програмування Microsoft Visual C # 2005 ми отримаємо виконавчий файл PCW_SingleThreadTest.exe (див. Лістинг і файл на «Мир ПК-диску»). І на двоядерний платформі (Core 2 Duo E6700, Intel D975XBX, PC2-6400 2 × 512 Мбайт) ця програма виконує закладені обчислення за 1687 мс. Здавалося б, куди швидше?
Однак гіпотетичний студент XXI ст. може запустити виконання функцій Number, Fibonacci і Factorial паралельно, злегка модифікувавши лістинг 1. Адже сучасний студент знає, що програма на C # може являти собою набір потоків, кожен з яких виступає об'єктом класу System.Threading.Thread.
При цьому в просторі імен System.Threading важливо виділити два методи, що дозволяють запускати незалежні фрагменти одного алгоритму в окремих потоках: коли в обчислювальну нитка передається аргумент і коли в цьому немає необхідності. У нашому випадку ми передаємо потокам thread1, thread2 і thread3 відповідні змінні nNum, nFib і nFac, для чого використовується делегат типу System.Threading.ParameterizedThreadStart (див. Лістинг 2 на «Мир ПК-диску»). Якщо ж метод в рамках потоку матиме тип результату void (тобто відсутність типу) з порожнім списком параметрів, тоді створюється делегат типу System.Threading.ThreadStart.
Таким чином, основний шматочок лістингу 1 (однопоточні версія) з послідовним викликом трьох функцій:

Number (nNum);
Fibonacci (nFib);
Factorial (nFac);

можна трансформувати в відповідний фрагмент лістингу 2 (трехпоточная версія):

Thread thread1 = new Thread (new ParameterizedThreadStart (Number));
thread1.Start (nNum);
Thread thread2 = new Thread (new ParameterizedThreadStart (Fibonacci));
thread2.Start (nFib);
Thread thread3 = new Thread (new ParameterizedThreadStart (Factorial));
thread3.Start (nFac);
thread1.Join ();
thread2.Join ();
thread3.Join ();

Тут метод Start запускає окрему нитку обчислень і передає в неї відповідну змінну, а метод Join очікує реального завершення зазначеного потоку. До речі, якби ставилося гіпотетична завдання передати результат обчислення функції Number в функцію Fibonacci як аргумент, то перед запуском нитки thread2 виникла б необхідність дочекатися завершення виконання потоку thread1 методом thread1.Join (), а вже потім запускати thread2.
Слід зауважити, що метод Thread.Join є перевантаженим, і факультативна змінна типу Int32 задавала б час очікування в мілісекундах. Так, метод thread3.Join (5000) чекав би завершення потоку протягом 5 с, після чого можна було б спробувати примусово завершити обчислювальної нитки thread3 методом thread3.Abort (), не чекаючи виведення результатів.
Але не будемо в рамках статті намагатися розповісти про всі можливості мультипрограмування. Тим більше що в мові C # окремий потік може перебувати в одному з наступних станів (визначається властивістю Thread.ThreadState): незапущених (Unstarted), виконання (Running), очікування (WaitSleepJoin), який був загальмований (Suspended), перерваний (Aborted), завершений ( Stopped), - кожне з яких характеризується своїми методами, і детальну інформацію про них (і не тільки) слід шукати в зручній системі допомоги Microsoft Visual Studio 2005.

Ми ж повернемося до компіляції лістингу 2, в результаті якої виходить файл PCW_MultiThreadTest.exe (див. Лістинг і файл на «Мир ПК-диску»). І якщо запустити цю програму на двоядерний платформі (Core 2 Duo E6700, Intel D975XBX, PC2-6400 2 × 512 Мбайт), то стає очевидним виграш від багатопотокової реалізації нашого алгоритму - 1031 мс замість 1687.
Поглянувши на екран, де виводяться результати програми, можна здогадатися, що швидше за все зі своїм завданням справляється функція Fibonacci, а самим ресурсоємним фрагментом алгоритму є решето Ератосфена. Причому за час роботи решета (thread1) без видимих ​​складнощів встигають запуститися і увінчатися успіхом потоки 2 і 3.
Таким чином, витративши додатковий час на невелику модернізацію класичного послідовного алгоритму, можна значно збільшити ефективність його виконання. І не варто думати, що наші висновки далекі від практики. Наприклад, в алгоритмі роботи затребуваного архиватора (або інший варіант - антивіруса) можна організувати окремі обчислювальні потоки для кожного файлу з обраної для архівації (перевірки на віруси) папки. Якщо ж користувач побажає стиснути один великий файл, то можна розбити його на частини і потім все їх піддати архівації в паралельних потоках. Зрозуміло, при різній кількості окремих ниток буде змінюватися ступінь стиснення згаданого файлу, але в більшості випадків можна буде досягти і високій швидкості виконання завдання, і потрібного зменшення початкового об'єму.
Однак в процесі ефективної реалізації технологій мультипрограммирования засмучують два моменти. По-перше, розробка складного програмного забезпечення на увазі високотехнологічні вирішення питань узгодження роботи обчислювальних ниток і коректної передачі даних з одного потоку в інший (наприклад, за допомогою методів класу System.Threading.Monitor). А по-друге, розпаралеленого код програмного додатка швидше за все призведе до падіння продуктивності на застарілих комп'ютерах з одноядерними процесорами.
Давайте вивчимо таблицю результатів запуску нашого алгоритму на різних платформах - у наявності регрес продуктивності багатопотокової версії в окремих конфігураціях трирічної давності. А значить, в тексті ідеальної програми буде потрібно ще і звернення до класів WMI (Windows Management Instrumentation - інструментарій управління ОС Windows) в просторі імен System.Management, щоб визначити кількість логічних процесорів в системі і на підставі їх числа застосувати той чи інший спосіб вирішення поставлених задач.
Наприклад, ось цим шматочком коду можна визначити число ЦП (i):

WqlObjectQuery queryCPU = new WqlObjectQuery ( "Select * from Win32_Processor");
ManagementObjectSearcher findCPU = new ManagementObjectSearcher (queryCPU);
foreach (ManagementObject mo in findCPU.Get ())
{
++ i;
}

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

Повний варіант статті см. На «Мир ПК-диску».

Дозвольте нагадати

Решето Ератосфена - метод, розроблений Ератосфеном і дозволяє відсівати складові числа з натурального ряду. Сутність його полягає в наступному.
Закреслюється одиниця. Число 2 - просте. Закреслюються всі натуральні числа, що діляться на 2. Число 3 - перший незачеркнутое число - буде простим. Далі зачеркиваем все натуральні числа, які діляться на 3. Число 5 - наступне незачеркнутое число - буде простим. І так можна продовжувати до нескінченності.

Числа Фібоначчі - це елементи числової послідовності 1, 1, 2, 3, 5, 8, 13 ..., в якій кожний наступний член дорівнює сумі двох попередніх, а сама ця послідовність називається поруч Фібоначчі. Таким чином, число Фібоначчі можна обчислити за формулою Fibonacci (n) = Fibonacci (n-2) + Fibonacci (n-1). Наприклад, 7-е число з ряду Фібоначчі відповідає Fibonacci (7) = Fibonacci (5) + Fibonacci (6) = 5 + 8 = 13.

Факторіал - це твір натуральних чисел від одиниці до будь-якого даного натурального числа n (т. Е. 1 · 2 · 3 · ... · n), позначається «n!». Наприклад, 7! = 1 · 2 · 3 · 4 · 5 · 6 · 7 = 5040.

Далеко ходити не треба

Уважні читачі могли помітити, що комп'ютерний диск журналу «Світ ПК» останнім часом зазнав значних змін. Причому модернізація нашого електронного додатка торкнулася не тільки зовнішнього вигляду, але і алгоритму пошукової оболонки, який розроблявся компанією «Стокона» ( http://www.stocona.ru/ ).
Тепер відображення диска дуже швидко з'являється на екрані, і користувач може відразу приступати до роботи. Однак за індикаторами роботи жорсткого диска можна здогадатися, що програмна оболонка не перейшла цілком і повністю в режим очікування введення команд читача, а продовжує виконувати якусь роботу в паралельному режимі. Невже многопоточность опинилася поруч з нами?
І ось що з цього питання роз'яснив нам один з розробників системи Богдан Гаркушин:
- Проблема, з якою зіткнулися розробники компанії «Стокона», - це забезпечення швидкого завантаження змісту журналу і швидкого пошуку інформації. Оскільки процес підготовки пошуку є більш тривалим, то його доцільніше виділяти в окремий потік і запускати паралельно із завантаженням змісту журналу. І це дозволяє значно скоротити час очікування основної інформації.
Таким чином, основний потік завантажує статті журналу і відразу надає їх користувачеві для читання. Тим часом допоміжна нитка виконує підготовку даних для пошуку: завантажує словникові бази, тематичні словники, а також кешируєт потрібні файли. І тільки після закінчення роботи допоміжного потоку в основний нитки з'являється можливість виконання всіх пошукових функцій.
До речі, для користувача сигналом про повному завантаженні всіх служб служить зупинка обертання логотипу компанії «Стокона» в правому верхньому кутку інтерфейсу, а не стан індикаторів жорсткого диска.
Зазвичай попередня завантаження даних займає близько хвилини. Тому якщо виконувати її в основному потоці, то час відображення оболонки при запуску значно збільшиться. Але ж для відображення інформації і навігації по файлам «Мир ПК-диска» досить завантаження програми Acrobat Reader, і ця операція сама по собі повинна виконуватися дуже швидко. І тільки коли користувач починає спокійно читати журнал, оболонка ініціює досить трудомістку операцію завантаження допоміжних даних в оперативну пам'ять. Так що не кожен читач помітить потрібну роботу, виконувану другим потоком.

Результати виконання компіляцій