Лекція: Редагування Управління багатозадачністю, програма, процес, потік. Дисципліни планування. Організація взаємодії між процесами.

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Програма, процес, стан процесу

Запуск програми на виконання відбувається таким чином: операційній системі вказується ім'я файлу, що містить виконуваний код. У відповідь система виконує наступні дії:

  • знаходить у файловій системі файл із вказаним ім'ям;
  • завантажує програму, що зберігається в цьому файлі, до оперативної пам'яті;
  • проводить налагоджування програмного коду, тобто модифікує адреси команд;
  • повідомляє процесору початкову адресу (адресу першої команди), тобто встановлює лічильник адреси у стан, який відповідає адресі першої команди;</li>
  • починає виконання програми, тобто передає управління програмі.

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

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

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

ОС виділяє у програмному коді послідовність команд та даних, які описують процес — створює його. Створити процес - це значить:

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

Протягом існування процесу його виконання може бути багаторазово перервано і поновлено. Для того, щоб відновити виконання процесу, необхідно відновити стан його операційного середовища. Кожний процес описується відповідним набором даних — контрольним блоком процесу (Process Control Block - РСВ), що описує його поточний стан. Стан операційного середовища характеризується вмістом регістрів центрального процесора, програмного лічильника, режимом роботи процесора, покажчиками на відкриті файли, інформацією про незавершені операції уведення-виведення, кодами помилок, виконуваних даним процесом системних викликів і т.д. Ця інформація називається контекстом процесу і зберігається у спеціальній змінній Context.

Крім цього, операційній системі для реалізації планування процесів необхідна додаткова інформація: ідентифікатор процесу, стан процесу, дані про ступінь привілейованості процесу, місце перебування кодового сегмента й інша інформація. У деяких ОС (наприклад, в ОС UNIX) інформацію такого роду називають дескриптором процесу. Дескриптор процесу в порівнянні з контекстом містить більш оперативну інформацію, що повинна бути легко доступна підсистемі планування процесів. Контекст процесу містить менш актуальну інформацію і використовується операційною системою тільки після того, як прийнято рішення про поновлення перерваного процесу.

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

Контекст і дескриптор використовуються операційною системою для керування виконанням процесу, шляхом зміни його стану. Розрізняють наступні стани процесу:

  • новий (new) — процес щойно створений;
  • виконуваний (running) — активний стан процесу, під час якого процес керує всіма необхідними ресурсами і безпосередньо виконується процесором;
  • очікування (waiting) — пасивний стан процесу, процес
  • заблокований, він не може виконуватися внаслідок очікування певної події: завершення операції уведення-виведення, отримання повідомлення від іншого процесу, звільнення необхідного йому ресурсу;
  • готовий (ready) — пасивний стан процесу, процес заблокований у зв'язку з зовнішніми стосовно нього обставинами: процес має всі необхідні для нього ресурси, він готовий виконуватися, однак процесор зайнятий виконанням іншого процесу;
  • завершений (terminated) — процес завершив свою роботу.

У стані виконання в однопроцесорній системі може знаходитися тільки один процес, а в стані очікування чи готовності — кілька процесів. Життєвий цикл процесу починається зі стану „готовий”, коли процес готовий до виконання. При активізації процес переходить у стан „виконуваний” і знаходиться в ньому доти, поки або сам він звільнить процесор, перейшовши в стан очікування якої-небудь події, або буде насильно "витиснутий" із процесора, наприклад, внаслідок вичерпання відведеного даному процесу кванта процесорного часу. В останньому випадку процес повертається в стан ротовий”. У цей же стан процес переходить зі стану очікування, після того, як очікувана подія відбудеться.

Рис. 1. Зміни стану процесу під час його виконання

Наприклад:

  1. новий процес необхідно розмістити в основній пам'яті, отже, йому необхідно виділити частину адресного простору;
  2. процесу в стані „готовий" необхідно надати процесорний час;
  3. виконуваний процес може звертатися до пристроїв уведення/виведення файлів збережених на диску.

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

  • визначення моменту часу для зміни виконуваного процесу;
  • вибір процесу на виконання з черги готових процесів;
  • переключення контекстів "старого" і "нового" процесів.

Одним з методів планування процесів, орієнтованих на ефективне завантаження ресурсів, є метод черг ресурсів. Нові процеси знаходяться у вхідній черзі, яку часто називають чергою завдань (job queue). Вхідна черга розташовується в зовнішній пам'яті, у вхідній черзі процеси очікують звільнення ресурсу — адресного простору основної пам'яті. Готові до виконання процеси розташовуються в основній пам'яті і зв'язані чергою готових процесів або ready queue. Процеси в цій черзі чекають на отримання процесорного часу. Процес у стані чекання завершення операції уведення/виведення знаходиться в одній з черг до пристроїв уведення/виведення, що зветься devices queue.

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

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

  1. алгоритми на основі квантування — надання певного часового інтервалу для виконання процесу;
  2. алгоритми, що використовують оцінювання важливості виконання задачі— пріоритети.

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

Витісняючі та невитісняючі алгоритми планування

Забезпечення одночасного виконання кількох задач (багатозадачність) передбачає розподіл процесорного часу між задачами. Планувальник (складова ОС) відбирає завдання з черги готових процесів і передає їх на виконання центральному процесору. Існує два варіанти реалізації використання виконуваними задачами центрального процесора: кооперативна або невитісняюча (non-preemptive) та витісняюча (preemptive) багатозадачність (multitasking).

Кооперативна (non-preemptive multitasking) багатозадачність використовує розподіл процесорного часу з очікуванням. Активний процес займає процесор стільки часу, скільки йому необхідно, потім передає управління планувальнику операційної системи для вибору з черги іншого, готового до виконання процесу. Операційна система сама не може призупинити або зупинити активний процес. При цьому, якщо певний процес займає досить багато процесорного часу, то всі інші змушені непродуктивно простоювати.

Витісняюча багатозадачність {preemptive multitasking) метод, при якому рішення про перемикання процесора з виконання одного процесу на виконання іншого приймається диспетчером задач операційної системи, а не активною задачею. Витісняючу багатозадачність часто називають істинною багатозадачністю.

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

Рис. 2. Витісняюча багатозадачність

Основною відмінністю між preemptive і non-preemptive варіантами багатозадачності є ступінь централізації механізму планування задач. При витісняючій багатозадачності механізм планування задач цілком зосереджений в операційній системі, і програміст пише свій додаток, не піклуючись про те, що він буде виконуватися паралельно з іншими задачами. При невитісняючій багатозадачності механізм планування розподілений між системою і прикладними програмами. Прикладна програма, одержавши управління від операційної системи, сама визначає момент завершення своєї чергової ітерації (процесу) і передає управління ОС за допомогою системного виклику (переривання), а ОС формує черги задач і обирає за певним алгоритмом (наприклад, з урахуванням пріоритетів) наступну задачу до виконання. Такий механізм створює проблеми як для користувачів, так і для розроблювачів, оскільки „завислий” процес зупиняє рух черги.

Однак розподіл функцій планувальника між системою і додатками не завжди є недоліком, а за певних умов може бути і перевагою, оскільки дає можливість розробнику самому проектувати алгоритм планування, найбільш придатний для даної задачі. Оскільки програміст сам визначає в програмі момент часу передачі управління, то при цьому виключаються нераціональні переривання програм у "незручні" для них моменти часу. Крім того, легко вирішуються проблеми спільного використання даних: задача під час кожної ітерації використовує їх монопольно, протягом часу виконання (runtime) дані не можуть бути змінені. Істотною перевагою (non-preemptive) систем є більш висока швидкість переключення з задачі на задачу.

Прикладом ефективного використання невитісняючої багатозадачності є операційна система NetWare, де, завдяки цьому, досягнута висока швидкість виконання файлових операцій. Менш вдалим виявилося використання невитісняючої багатозадачності в операційному середовищі Windows 3.x, для якої є характерним „захоплення” процесора, не зважаючи на те, що використовується квантування часу. У всіх високопродуктивних сучасних операційних системах (UNIX, Windows NT, OS/2, YАХ/VMS), реалізована витісняюча багатозадачність.

Стратегії планування з використанням квантування

Відповідно до алгоритмів, що використовують алгоритми квантування часу процесора, зміна активного процесу відбувається, якщо:

  • процес завершився і полишив систему,
  • виникла помилка,
  • процес перейшов у стан очікування,
  • вичерпано квант процесорного часу, відведений даному процесу.

Процес, що вичерпав свій квант, переводиться у стан „готовий” і очікує, коли йому буде наданий новий квант процесорного часу, а на виконання відповідно до визначеного правила вибирається новий процес з черги готових. Таким чином, жоден процес не займає процесор надовго, тому квантування широко використовується в системах розподілу часу.

Кванти, які виділяються процесам, можуть бути однаковими для всіх процесів, або різними. Кванти можуть бути фіксованої величини, або змінюватися в різні періоди життя процесу. Процеси, які не повністю використали виділений їм квант (наприклад, через необхідність виконання операцій уведення-виведення), можуть одержати, або не одержати компенсацію у вигляді привілеїв при наступному обслуговуванні.

Стратегія перший прийшов — перший обслуговується (first come — first served (FCFS))

FCFS є найбільш простою стратегією планування процесів і полягає в тому, що процесор передається процесу, який раніш всіх інших його запросив. Коли процес потрапляє в чергу готових процесів, process control block приєднується до хвоста черги.

Рис. 3. Стратегія планування процесів FCFS

Новоутворений процес комутатором процесів передається на виконання, після чого займає місце у черзі. Середній час чекання для стратегії FCFS часто досить великий і залежить від порядку надходження процесів у чергу готових процесів і їх кількості. Стратегії FCFS властивий так званий “ефект конвою”. У тому випадку, коли в комп'ютері існує один великий процес і кілька малих, то всі процеси збираються на початку черги готових процесів, а потім у черзі до пристроїв. Таким чином, “ефект конвою” призводить до зниження завантаженості як процесора, так і периферійного обладнання.

Стратегія „найбільш коротка робота - першою”. (Shortest Job First —SJF)

Одним з методів боротьби з “ефектом конвою” є стратегія, що дозволяє найкоротшому процесу з черги виконуватися першим — найбільш коротка робота першою (Shortest Job First —SJF).

Найбільші труднощі в практичній реалізації SJF полягають у тому, що заздалегідь не можна визначити час наступного обслуговування. Тому стратегія SJF часто застосовується в планувальниках, що обслуговують пакетний режим. У цьому випадку замість величини часу наступного обслуговування використовується допустимий максимальний час иконання завдання, якии задається програмістом перед відправленням завдання на виконання.

“Карусельна” стратегія планування (RR-Round Robin)

Round Robin стратегія застосовується в системах розподілу часу. Визначається невеликий відрізок часу, який названий квантом часу. Черга готових процесів розглядається як кільце (рис. 8). Процеси циклічно переміщаються по черзі, одержуючи CPU на час, який дорівнює одному кванту. Новий процес додається в хвіст черги. Якщо процес не завершився в межах виділеного йому кванта часу, його робота примусово переривається, і він переміщається в хвіст черги

Рис. 4. Стратегія планування процесів Round Robin

Властивості Round Robin стратегії залежать від величини часового кванта q. Чим більше часовий квант, тим ближче Round Robin стратегія наближається до FCFS стратегії. При дуже малих значеннях часового кванта Round Robin стратегія називають розподілом процесора — processor sharing. Теоретично це означає, що кожний з N процесів працює зі своїм власним процесором, продуктивність процесора дорівнює 1/N від продуктивності фізичного процесора.

Стратегії планування з використанням пріоритетів

Друга група алгоритмів планування використовує поняття “пріоритет” процесу.

Пріоритет - це число, що характеризує ступінь привілейованості процесу при використанні ресурсів обчислювальної машини, зокрема, процесорного часу: чим вище пріоритет, тим вище привілей, чим вище привілей процесу, тим менше часу він буде проводити в чергах.

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

Внутрішні фактори:

  1. потреба у виділенні пам'яті;
  2. кількість відкритих файлів;
  3. відношення середнього часу уведення/виведення до середнього часу використання CPU;
  4. потреба в периферійних пристроях.

Зовнішні фактори:

  1. важливість процесу;
  2. вартість машинного часу;
  3. час виконання.

Внутрішні фактори можуть використовуватися для автоматичного призначення пріоритетів операційною системою, а зовнішні для примусового — оператором:

  1. збільшується пріоритет процесів, що очікують уведення від користувача, для оперативної реакції на його дії (наприклад уведення даних за допомогою клавіатури або миші);
  2. якщо пріоритет процесу найменший, то він збільшується;
  3. якщо пріоритет процесу найбільший, то він зменшується.

Описані раніше стратегії можуть розглядатися як окремі випадки стратегії пріоритетного планування: при стратегії FCFS припускається, що всі процеси мають однакові пріоритети; при SJF — пріоритет є величина, обернена часу наступного обслуговування.

Використовується два різновиди пріоритетних алгоритмів: алгоритми, що використовують відносні пріоритети, і алгоритми, що використовують абсолютні пріоритети. В обох випадках вибір процесу з черги готових процесів здійснюється однаково: вибирається процес, що має найвищий пріоритет, тільки різним чином вирішується проблема визначення моменту зміни активного процесу. У системах з відносними пріоритетами активний процес виконується доти, поки він сам не залишить процесор у результаті виникнення помилки або завершення, перейшовши в стан очікування. Для систем з абсолютними пріоритетами, існує ще одна умова переривання виконання активного процесу: поява в черзі готових процесів процесу з пріоритетом, більшим від пріоритету активного процесу. У цьому випадку перерваний процес переходить у стан „готовий”.

Головний недолік пріоритетного планування полягає в можливості блокування на невизначено довгий час низькопріоритетних процесів. Відомий випадок, коли в 1973 році в Массачусетському технологічному інституті МГГ при зупинці комп'ютера IBM 7094 у черзі готових процесів були виявлені процеси, запущені у 1967 і все ще не виконані.

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

Планування з використанням багаторівневої черги. (Multilevel queue scheduling)

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

Стратегія багаторівневої черги розділяє чергу готових процесів на кілька черг, у кожній з яких знаходяться процеси з однаковими властивостями, і кожна з яких може плануватися індивідуальною стратегією, наприклад Round Robin для інтерактивних процесів і FCFS -для пакетних процесів.

Вибір черги здійснюється за наступними правилами:

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

Планування з використанням багаторівневої черги зі зворотними зв'язками (Multilevel feedback queue sheduling)

Звичайна багаторівнева черга не допускає переміщення процесів між чергами. Багаторівнева черга зі зворотними зв'язками припускає, що процеси за певних умов можуть переміщатися між чергами. Процеси спочатку попадають у чергу 0, де кожному з них надається квант часу, наприклад, рівний 8 мс. Процеси, що не встигли виконатися протягом цього часу, переміщаються в чергу 1. Процеси з черги 1 починають опрацьовуватися тільки тоді, коли черга 0 стає порожньою. Процеси, що не виконалися в черзі 1 (#=16 мс) переміщаються в чергу 2. Процеси з черги 2 будуть опрацьовуватися тільки в тому випадку, якщо стають порожніми черги Oil.

Розглянута стратегія є найбільш універсальною і поєднує в собі властивості всіх розглянутих раніше стратегій: FCFS, SJF, пріоритетної, RR, багаторівневої черги.

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

Потоки (нитки)

Розглядаючи процеси, ми відзначали, що операційна система забезпечує автономне виконання процесів, їх ізольованість один від одного: кожний процес виконується у своєму віртуальну адресному просторі, для кожного процесу визначаються свої ресурси - файли, змінні з метою захисту одного процесу від іншого. Однак задача, розв'язувана в рамках одного процесу, може мати внутрішній паралелізм, що у принципі дозволяє прискорити її вирішення. Наприклад, у ході виконання задачі відбувається звертання до зовнішнього пристрою, і на час цієї операції можна не блокувати цілком виконання процесу, а продовжити обчислення по іншій гілці процесу. Для цих цілей сучасні ОС пропонують використовувати порівняно новий механізм багатопоточного опрацювання (multithreading). При цьому вводиться нове поняття "потік" (thread). Сучасні процесори досить добре пристосовані до опрацювання потоків, оскільки фізично використовують багаторівневі конвеєри команд.

Потоки — це об’єкти, які отримують час процесора, на тих же умовах, що і процеси. У сучасних ОС процесорний час виділяється квантами не процесам, а породженим ними потокам. Кожний процес має хоча б один потік і дозволяє виконувати в межах процесу кілька потоків. Подібно традиційним процесам (тобто процесам, що складаються з одного потоку), потоки можуть знаходитися в одному з наступних станів: виконуваний, очікування і готовий; поки один потік заблокований, інший потік того ж процесу може виконуватися. Крім розподілу адресного простору, усі потоки можуть спільно використовувати відкриті файли, таймери, сигнали, системні підпрограми і т.п. Подібно до процесів, для потоків створюються контекст і дескриптор потоку, однак різні потоки в рамках одного процесу не настільки незалежні, як окремі процеси.

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

Потоки, породжені процесом в межах виконуваної задачі можна розділити на дві групи:

  • асиметричні (asymmetric threads) — це потоки, які вирішують різні задачі і, як правило, не мають спільних ресурсів. Один відповідає за друк, інший опрацьовує повідомлення від клавіатури і мишки, третій керує автоматичним збереженням документу користувача;
  • симетричні потоки (symmetric threads) — виконують одну і ту ж роботу, розділяють одні і ті ж ресурси і виконують один код. Наприклад: сервери баз даних при обслуговувані кількох клієнтів, для кожного клієнта породжується новий потік.

Багатопотокове опрацювання підвищує ефективність роботи системи в порівнянні з багатозадачним. Задача, реалізована з використанням кількох потоків у рамках одного процесу, може бути виконана швидше за рахунок розпаралелення виконання п окремих частин. Сучаснии процесор, за рахунок ефекту „відставання шини більш ефективно працює саме на розпалалелених задачах, тобто час обміну даними через більш повільну шину не втрачається на непродуктивне очікування, а використовується на опрацювання команд іншої нитки. Наприклад, якщо електронна таблиця була розроблена з урахуванням можливостей багатопотокового опрацювання даних, то користувач може проводити обчислення й одночасно продовжувати заповнювати таблицю; багатопотоковий сервер управління базами даних може паралельно опрацьовувати запити кількох клієнтів.

Багатопроцесорні системи

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

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

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

Для отримання максимальної потужності у сучасних ЕОМ використовуються як найновіші досягнення розвитку елементної бази, так і нові рішення в архітектурі комп'ютерів. Втілюючи ідею одночасного виконання кількох дій, розглядають дві реалізації: конвеєрність і власне паралельність.

Паралельне опрацювання. Якщо певний пристрій виконує одну операцію за одиницю часу, то тисячу операцій він виконає за тисячу одиниць. Якщо припустити, що є п'ять таких незалежних пристроїв, які працюють одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту ж роботу виконає за 1000/N одиниць часу.

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

Припустимо, що в операції можна виділити п'ять мікрооперацій, кожна з яких виконується за одну одиницю часу. Якщо є один неподільний послідовний пристрій, то 100 пар аргументів він опрацює за 500 одиниць, якщо кожну мікрооперацію виконати в окремому конвеєрному пристрої, то на п'ятій одиниці часу на різній стадії обробки такого пристрою будуть знаходиться перші п'ять пар аргументів, а весь набір зі ста пар буде опрацьований за 5+99=104 одиниці часу — прискорення в порівнянні з послідовним пристроєм майже в п'ять разів (відповідно кількості ступенів конвеєра).

Усі сучасні мікропроцесори, Pentium П, Ш, IV, Athlon, PA-8200, MIPS R10000 або Power2 SuperChip використовують той або інший метод паралельного опрацювання, хоча ці ідеї з'явилися досить давно і були реалізовані у деяких комп'ютерах у 60-70 роках. Після належного відпрацьовування технології і здешевлення виробництва ідеї паралельного опрацювання даних почали використовуватися в комп'ютерах середнього класу, а сьогодні все це в повному обсязі втілюється в робочих станціях і персональних комп'ютерах.

Сьогодні розвиток високопродуктивної обчислювальної техніки проводиться у чотирьох напрямках:

  1. Векторно-конвейєрні комп'ютери. Особливістю таких машин є конвеєрні функціональні пристрої, які містять набір векторних інструкцій у системі команд. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри. Типовим представником даного напрямку є лінія векторно-конвеєрних комп'ютерів CRAY компанії Cray Research.
  2. Масивно-паралельні комп'ютери з розподіленою пам'яттю. Ідея побудови комп'ютерів цього класу досить проста, реалізується з серійних мікропроцесорів з локальною пам'яттю, об'єднаних за допомогою комунікаційного середовища, наприклад, мережі. Серед переваг виділяють простий підбір оптимальної конфігурації, якщо потрібна висока продуктивність — додаються процесори, якщо ні — вилучаються. Недоліком є мала швидкість міжпроцесорної взаємодія відносно локального опрацювання даних самими процесорами. Написати ефективну програму для таких комп'ютерів досить складно, а для деяких алгоритмів іноді просто неможливо.

До даного класу належать комп'ютери Intel Paragon, IBM SP1, Parsytec, до певної міри IBM SP2 і CRAY T3D/T3E, хоча в цих комп'ютерах вплив зазначеного недоліку намагаються зробити мінімальним. До цього ж класу можна віднести і мережі комп'ютерів, що досить часто розглядають як дешеву альтернативу дорогим суперкомп'ютерам.

  1. Паралельні комп'ютери з загальною пам'яттю. Вся оперативна пам'ять таких комп'ютерів розподіляється між кількомами однаковими процесорами. Це знімає проблеми попереднього класу, але додає нові -число процесорів, що мають доступ до загальної пам'яті з технічних причинах не можна зробити великим. До даного напрямку входять багато сучасних багатопроцесорних SMP-комп'ютерів, сервер HP Т600 або Sun Ultra Enterprise 5000.
  2. Останній напрямок не є самостійним, а скоріше являє собою комбінації попередніх трьох. З кількох процесорів, традиційних або векторно-конвеєрних і загальної для них пам'яті формується обчислювальний вузол. Якщо обчислювальної потужності отриманого вузла не досить, то об'єднують кілька вузлів високошвидкісними каналами. Подібну архітектуру називають кластерною, по такому принципу побудовані CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 і інші. Саме цей напрямок на сьогодні є найбільш перспективним.

Продуктивність багатопроцесорних систем не зростає пропорційно числу використовуваних процесорів. Відповідно приципу Амдала максимальний виграш, що можна отримати, незалежить від кількості використовуваних процесорів у системі і не перевищуватиме 10-кратного прискорення виконання програми. 10 - це теоретична верхня оцінка найкращого випадку, коли ніяких інших негативних факторів немає.

Оцінювання критеріїв планування процесів

Використання різних алгоритмів планування задач вимагає визначення певних критеріїв, що дозволяють оцінити ефективність використання системних ресурсів обчислювальної системи, встановити придатність ОС для вирішення відповідних завдань. Як правило, для порівняння алгоритмів планувальників використовуються критерії:

  1. використання ЦП (CPU utilization). Завантаження CPU теоретично може знаходитися в межах від 0 до 100%. У реальних системах використання CPU знаходиться в межах 40% для легко завантаженого CPU і 90% для достатньо завантаженого CPU;
  2. пропускна здатність CPU (throughput). Пропускна здатність CPU вимірюється кількістю процесів, що виконуються за одиницю часу;
  3. час обороту (turnaround time). Для деяких процесів важливим критерієм є повний час виконання, тобто інтервал від моменту появи процесу у вхідній черзі до моменту його завершення. Цей час названий часом обороту і включає час чекання у вхідній черзі, час чекання в черзі готових процесів, час чекання в чергах до пристроїв, час виконання процесором і час уведення/виведення;
  4. час очікування (waiting time). Під часом очікування розуміємо сумарний час перебування процесу в черзі готових процесів;
  5. час відгуку (response time). Для суто інтерактивних програм важливим показником є час відповіді або час, що пройшов від моменту розміщення процеса у вхідній черзі до моменту першого звертання до термінала.

Очевидно, що оптимальна стратегія планувальника повинна бути спрямована на:

  1. максимізацію середніх значень завантаженості і пропускної здатності,
  2. мінімізацію часу очікування і часу відгуку.