1. Загальна частина
1.1. Зміст
1.2. Завдання
1.3. Введення
2. Апаратна організація МПВК
2.1. Структурна схема МПВК
2.2. Функціональна схема елемента комутаційної матриці
2.3. Організація оперативної пам'яті
2.3.1. Пам'ять з розшаруванням
2.3.2. Застосування коду Хеммінга в модулях пам'яті
2.4. Організація резервування та відновлення при відмові будь-якого компоненту МПВК
3. Організація функціонування ОС на МПВК
3.1. Симетрична багатопроцесорна обробка (SMP)
3.2. Нитки
3.2.1. Підходи до організації ниток і управління ними в різних варіантах ОС UNIX
3.3. Семафори
3.3.1. Визначення семафорів
3.3.2. Реалізація семафорів
3.4. Статті без ситуації
3.5. Запобігання тупикових ситуацій
3.5.1. Лінійне впорядкування ресурсів
3.5.2. Ієрархічне впорядкування ресурсів
3.5.3. Алгоритм банкіра
3.6. Захист інформації
4. Література
1.2 Завдання
(варіант № 16)
Розробити багатопроцесорний обчислювальний комплекс за наступними вихідними даними:
* Використовувати матрицю з перехресної комутацією;
* Кількість процесорів - 8;
* Кількість блоків ОЗУ - 4;
* Кількість каналів вводу-виводу - 4;
Потрібно розробити структурну схему комутаційної матриці і функціональну схему елемента комутаційної матриці.
Описати функціонування ОС для організації багатопроцесорної обробки.
Описати організацію резервування та відновлення обчислювального процесу при відмові будь-якого компоненту багатопроцесорного обчислювального комплексу.
1.3 Введення
Розробка багатопроцесорних (МПВК) і багатомашинних (ММВК) обчислювальних комплексів, як правило, має на меті підвищення або рівня надійності, або рівня продуктивності комплексу до значень недоступних або важкореалізоване (реалізуються з великими економічними витратами) у традиційних ЕОМ.
На більшості класів розв'язуваних завдань для досягнення високої продуктивності найбільш ефективні МПВК. Це пов'язано з великою інтенсивністю інформаційних обмінів між підзадачами, що призводить до занадто високим накладних витрат в ММВК. ММВК, в принципі, дозволяють досягти багато більшої продуктивності завдяки кращій масштабованості, проте ця перевага виявляється тільки при відповідності виконуваних завдань умові максимального подовження незалежних гілок програми, що не завжди можливо.
Вказаний в завданні МПВК з матрицею перехресної комутації дозволяє досягти найбільшої продуктивності, що пов'язано з мінімізацією ймовірності конфліктів при доступі до компонентів комплексу. При побудові МПВК на основі доступу з використанням однієї або декількох загальних шин конфлікти доступу набагато більш ймовірні, що призводить до помітного зниження продуктивності в порівнянні з МПВК на основі матриці перехресної комутації.
Виходячи з цих міркувань було вирішено проектувати МПВК за критерієм максимальної продуктивності, менше приділяючи уваги високої відмовостійкості комплексу. Це рішення також обгрунтовується і тим, що сучасні мікроелектронні вироби мають цілком достатньою надійністю для переважної більшості комерційних застосувань, що робить економічно необгрунтованим істотне ускладнення комплексу з метою досягнення високої відмовостійкості.
2. Апаратна організація МПВК
2.1 Структурна схема МПВК
У МПВК з перехресної комутацією всі зв'язки здійснюються за допомогою спеціального пристрою - комутаційної матриці. Комутаційна матриця дозволяє пов'язувати один з одним будь-яку пару пристроїв, причому таких пар може бути скільки завгодно - зв'язку не залежать один від одного. Структурна схема МПВК наведена на малюнку:
Комутаційна матриця виконує передачу даних між процесорами і пам'яттю, а також між процесорами вводу-виводу і пам'яттю. Комутуються тільки внутрішні шини МПВК, основне призначення яких - високошвидкісна передача даних, для цих шин немає сенсу вимагати більшої протяжності провідників або стандартизації з метою спрощення підключення додаткових пристроїв. Високошвидкісний обмін з периферійними пристроями здійснюється за допомогою процесорів вводу-виводу, які є контролерами периферійних високошвидкісних шин, до яких, у свою чергу і підключаються контролери відповідних пристроїв. На роль таких периферійних шин підходять, наприклад, VME (застосовується в МПВК фірми Digital Equipment Company), SBus (застосовується в МПВК фірми Sun Microsystems) або PCI (застосовується в МПВК, побудованих на процесорах фірми Intel сімейства x86).
У SMP сумісної системі переривання керуються контролерами APIC (Advanced Programmable Interrupt Controller), БІС яких серійно випускаються багатьма виробниками мікроелектронних виробів (наприклад DEC, Sun, IBM, Texas Instruments). Дані контролери мають розподіленою архітектурою, в якій функції управління переривань розподілені між двома функціональними блоками: локальним (ЛБ) і введення-виведення (БВВ). Ці блоки обмінюються інформацією через шину, яка називається шиною комунікацій контролера переривань (ШККП). Пристрій вводу-виводу визначає появу переривання, адресує його локальному блоку і посилає по шині ШККП. Блоки APIC спільно відповідають за доставку переривання від джерела переривань до одержувачів по всій системі. Використання такої організації додатково збільшує розширюваність за рахунок розвантаження поділу між процесорами навантаження з обробки переривань. Завдяки розподіленої архітектурі, локальні блоки або блоки вводу-виводу можуть бути реалізовані в окремій мікросхемі або інтегровані з іншими компонентами системи.
У МПВК подібної структури немає конфліктів через зв'язки, залишаються тільки конфлікти з-за ресурсів. Можливість одночасної зв'язку декількох пар пристроїв дозволяє домагатися дуже високої продуктивності комплексу. Важливо відзначити і таку обставину, як можливість встановлення зв'язку між пристроями на будь-яке, навіть тривалий час, тому що це абсолютно не заважає роботі інших пристроїв, але дозволяє передавати будь-які масиви інформації з високою швидкістю, що також сприяє підвищенню продуктивності комплексу.
Крім того, до переваг структури з перехресної комутацією можна віднести простоту і уніфікованість інтерфейсів всіх пристроїв, а також можливість вирішення всіх конфліктів у комутаційної матриці. Важливо відзначити і те, що порушення якийсь зв'язку призводить не до виходу з ладу всього пристроїв, тобто надійність таких комплексів досить висока. Однак і організація МПВК з перехресної комутацією не вільна від недоліків.
Перш за все - складність нарощування ВК. Якщо в комутаційної матриці заздалегідь не передбачити великої кількості входів, то введення додаткових пристроїв до комплексу потребують установки нової комутаційної матриці. Істотним недоліком є і те, що комутаційна матриця при великій кількості пристроїв у комплексі стає складною, громіздкою і досить дорогим. Треба врахувати ту обставину, що комутаційні матриці будуються зазвичай на схемах, швидкодія яких істотно вище швидкодії схем і елементів основних пристроїв - тільки за цієї умови реалізуються всі переваги комутаційної матриці. Це обставина значною мірою ускладнює і здорожує комплекси.
2.2 Функціональна схема елемента комутаційної матриці
Комутаційна матриця (див. розділ "Структурна схема МПВК") являє собою прямокутний двовимірний масив з комутаційних елементів, встановлених у місцях перетину шин процесорів і пам'яті (по структурній схемі МПВК). Функції кожного з цих елементів прості - при наявності керуючого сигналу повинна бути забезпечена двосторонній зв'язок між шинами з боку процесора і шинами з боку пам'яті. При відсутності керуючого сигналу зв'язок повинен бути відсутнім, сигнали на шинах повинні поширюватися далі.
Чи не становить істотних проблем синтез такого блоку на стандартних логічних елементах, однак кожен такий блок містить два (як мінімум) послідовно з'єднаних логічних елемента, що вносить досить відчутну затримку. Таке рішення входить в протиріччя з вимогою підвищеної швидкодії елементів комутаційної матриці і призводить до необхідності підвищення швидкості роботи за рахунок застосування логіки високої швидкодії, що не завжди можливо або бажано.
Виходом є застосування спеціалізованих інтегральних мікросхем, що випускаються деякими виробниками мікроелектроніки. У Texas Instruments це ІМС SN74CBT3384 (розрядність 10 біт), SN74CBT16244 (розрядність 16 біт), SN74CBT16210 (розрядність 20 біт), у Cypress Semiconductor - CYBUS3384 (два комутатора в одному корпусі з розрядністю 5 біт кожний), у Sun Microelectronics - STP2230SOP. Дані ІМС мають достатню швидкодію (затримка розповсюдження 5.2 - 10.0 нс, що відповідає максимальній тактовою частотою 190 - 100 МГц) і досить невисоку ціну (кілька доларів за одиницю в партіях від 1000 штук).
Всі ІМС цього сімейства мають практично однакову функціональну схему:
Видно, що шина даних комутується польових транзистора з ізольованим затвором, на який подається керуюче напругу з входу управління. Елемент повністю симетричний по входу і виходу даних, що робить його застосування досить зручним.
2.3 Організація оперативної пам'яті
Пам'ять МПВК повинна задовольняти вимогам високої швидкодії і високій надійності. Незважаючи на досить високі характеристики за цими показниками, що забезпечуються сучасної елементної бази, за допомогою відносно нескладних і недорогих методів можна досягти істотно більш високих показників швидкодії і надійності.
З метою підвищення швидкодії має сенс застосувати розшарування пам'яті за адресами на 4 модуля (розбивка на 4 модуля обумовлено в завданні, так що доцільно застосувати це розбиття для покращення швидкодії МПВК). Більш докладно розшарування за адресами буде розглянуто нижче.
Для підвищення надійності модулів пам'яті було вирішено застосувати коригуючі коди. Найбільш поширений код Хеммінга дозволяє виправляти одиночні і виявляти подвійні помилки. Більш докладно його застосування розглядається нижче.
2.3.1 Пам'ять з розшаруванням
Наявність в системі безлічі мікросхем пам'яті дозволяє використовувати потенційний паралелізм, закладений в такій організації. Для цього мікросхеми пам'яті часто об'єднуються в банки або модулі, що містять фіксовану кількість слів, причому тільки до одного з цих слів банку можливе звернення в кожний момент часу. Як уже зазначалося, в реальних системах наявна швидкість доступу до таких банків пам'яті рідко виявляється достатньою. Отже, щоб отримати більшу швидкість доступу, треба здійснювати одночасний доступ до багатьох банкам пам'яті. Одна із загальних методик, що використовуються для цього, називається розшаруванням пам'яті. При розшаруванні банки пам'яті зазвичай упорядковуються так, щоб N послідовних адрес пам'яті i, i +1, i 2 ,..., i + N-1 припадали на N різних банків. У i-тому банку пам'яті знаходяться тільки слова, адреси яких мають вигляд k * N + i (де 0
Узагальненням ідеї розшарування пам'яті є можливість реалізації декількох незалежних звернень, коли декілька контролерів пам'яті дозволяють банкам пам'яті (або групам розшарованих банків пам'яті) працювати незалежно.
Якщо система пам'яті розроблена для підтримки численних незалежних запитів (як це має місце при роботі з кеш-пам'яті, при реалізації багатопроцесорної і векторної обробки), ефективність системи буде в значній мірі залежати від частоти надходження незалежних запитів до різних банків. Звернення з послідовним адресами, або, в більш загальному випадку, звернення за адресами, що відрізняється на непарне число, добре обробляються традиційними схемами розшарованої пам'яті. Проблеми виникають, якщо різниця в адресах послідовних звернень парна. Одне з рішень, що використовується у великих комп'ютерах, полягає в тому, щоб статистично зменшити вірогідність подібних звернень шляхом значного збільшення кількості банків пам'яті. Наприклад, у суперкомп'ютері NEC SX/3 використовуються 128 банків пам'яті.
Подібні проблеми можуть бути вирішені як програмними, так і апаратними засобами.
2.3.2 Застосування коду Хеммінга в модулях пам'яті
З метою підвищення загальної надійності модулів оперативної пам'яті було вирішено застосувати зберігання даних в коді Хеммінга, який за рахунок надмірності дозволяє коригувати поодинокі помилки і виявляти помилки більшої кратності. Код Хеммінга отримав широке поширення завдяки простоті кодерів і декодерів, а також мінімальної надмірності.
Так як більшість сучасних високопродуктивних мікропроцесорів мають розрядність 64 біта, необхідно забезпечити розрядність пам'яті не менше 64 біт. Цією розрядності відповідає код Хеммінга (72, 64), що означає наявність 64 інформаційних розрядів і 8 контрольних. Можна розрахувати ефект від застосування коригуючого кодування:
Нехай ймовірність відмови одиночного модуля пам'яті розрядністю 1 біт за деякий час P1 = 10-5, тоді вірогідність відмови одного з необхідних 64 модулів пам'яті за той же час Pзаг = 64 * P1 = 6.4 * 10-4. У разі застосування коду Хеммінга для втрати інформації необхідні дві помилки в 72-х розрядах: Pзаг = (72 * P1) * (71 * P1) = 5.112 * 10-7. Таким чином надійність зростає більш ніж на три порядки при збільшенні вартості на 12.5%. Зрозуміло ці міркування правильні лише у випадку пренебрежимо малу ймовірність відмов і вартості кодера і декодера в порівнянні з модулями пам'яті, однак у випадку реальних обсягів пам'яті це дійсно так.
2.4 Організація резервування та відновлення при відмові будь-якого компоненту МПВК
Однією з цілей створення МПВК є досягнення підвищеної надійності обчислювальної системи. Підвищення надійності функціонування в МПВК досягається простіше, ніж в однопроцесорних ЕОМ, однак вимагає ускладнення організації як апаратури МПВК, так і системного програмного забезпечення, а для досягнення найбільшого ефекту такої модифікації нерідко вимагає і прикладне програмне забезпечення. При правильній організації МПВК відмови не призводять до втрати даних або припинення обчислювального процесу, а або взагалі не позначаються на роботі МПВК, або викликають поступову деградацію обчислювальної потужності. Заходи щодо забезпечення відмовостійкості свої для кожного компонента МПВК.
Відмови оперативної пам'яті були розглянуті вище. Відмови в комутаційної матриці також як і відмови оперативної пам'яті доцільно маскувати застосуванням кодів, що коректують помилки. Найбільш складні для виявлення і відновлення інформації відмови процесорів, проте у разі наявності вбудованих засобів самоконтролю або при періодичному прогоні на кожному процесорі контрольних тестів, завдання виявлення вирішується досить легко. Відновлення обчислювального процесу полягає у виключенні операційною системою що відмовив процесора зі списку доступних і запуску на іншому процесорі потерпілого процесу з останньої контрольної точки. Відмови процесорів вводу-виводу виявляються досить легко, відновлення через наявність 4-х ідентичних за функціями ПВВ також нескладно - треба лише підключення критичних для роботи МПВК периферійних пристроїв до всіх ПВВ з відповіднимиющей комутацією. Відмови самих периферійних пристроїв - найбільш проста і добре продумана частина організації відмовостійкості. Найбільш часто застосовується той чи інший вид резервування на рівні пристроїв - навантажене, ненавантаженого або ковзне.
Необхідно відзначити, що підтримки операційної системи не вимагає в даному випадку лише організація відмовостійкості оперативної пам'яті, комутаційної матриці і деяких периферійних пристроїв. Всі інші рішення вимагають тієї або іншої підтримки на рівні ядра операційної системи МПВК.
Також варто підкреслити, що, незважаючи на можливості організації відмовостійкості МПВК, всі найбільш серйозні реалізації стійких до відмов обчислювальних систем є ММВК. Це пояснюється більшою ізольованістю, а отже і до меншого впливу відмовили модулів на інші модулі в ММВК.
3. Організація функціонування ОС на МПВК
ОС МПВК повинна виконувати всі функції ОС однопроцесорній ЕОМ, однак додатково вона повинна забезпечувати ефективне використання ресурсів багатопроцесорного комплексу (див. розділи "Симетрична багатопроцесорна обробка", "Нитки"). Так як проблеми реалізації ОС більш серйозні, ніж у однопроцесорному варіанті, необхідно приділити особливу увагу забезпеченню коректного конкурентного доступу (пропонується використання семафорів - див "Семафори"). Для уникнення простоїв системи необхідно уникати безвихідних ситуацій (див. розділи "Статті без ситуації", "Запобігання тупикових ситуацій"). Так як ефективних алгоритмів дозволу тупиків без втрати інформації, в загальному випадку, не існує, ці методи не розглядаються (це в основному знищення процесів, починаючи з найменш пріоритетних процесів по будь-якому визначеному заздалегідь критерієм).
Загалом можна сказати, що ОС багатопроцесорних ЕОМ схожі по функціях і реалізації на ОС однопроцесорних ЕОМ, однак вони виконують деякі додаткові функції, а реалізація основних функцій часто більш складна.
3.1 Симетрична багатопроцесорна обробка
(Symmetric Multiprocessor Processing - SMP)
Для багатопроцесорної обробки завжди потрібні і відповідні апаратні платформи, і операційні системи. Однак ОС можуть використовувати багатопроцесорні платформи кількома різними способами. При асиметричною багатопроцесорної обробці процеси прикладних програм призначаються конкретному процесору на апаратній платформі. Нитки кожного процесу повинні чекати, поки призначений ним процесор звільниться. Такий метод, як правило, менш ефективний, ніж симетричний метод. Симетрична багатопроцесорна обробка припускає, що всі процесори мають однакові можливості.
Під симетричною багатопроцесорної обробкою звичайно розуміють рівноправне поділ між процесорами різних завдань, у числі яких в асиметричних системах можуть бути ввід-висновок або числові обчислення. У SMP системі всі процесори функціонально ідентичні, і будь-яке завдання може виконуватися на будь-якому процесорі. SMP ОС запускає процес (нитка) із загальної черги на першому звільнилося процесорі, як тільки виконання процесу (нитки) після пріоритетного переривання ОС поновлюється. У SMP-моделі навантаження динамічно розподіляється між процесорами, так що неможлива ситуація, в якій одні центральні процесори перевантажені, в той час як інші нічим не зайняті.
Хоча всі процесори в SMP системі функціонально ідентичні, виділяється два їх типу: завантажувальний процесор (BSP) і прикладні процесори (АР). Який процесор грає роль завантажувального, визначається апаратними засобами або спільно апаратурою та BIOS. Це зроблено для зручності і має значення лише під час ініціалізації та вимикання. BSP-процесор відповідає за ініціалізацію системи та за завантаження ОС. АР-процесор активізується після завантаження ОС.
Симетричність має два важливих аспекти: симетричність пам'яті і введення-виведення. Пам'ять симетрична, якщо всі процесори спільно використовують загальний простір пам'яті і мають у цьому просторі доступ з одними і тими ж адресами. Симетричність пам'яті припускає, що всі процесори можуть виконувати єдину копію ОС. У такому випадку будь-які існуючі системи та прикладні програми будуть працювати однаково, незалежно від числа встановлених в системі процесорів. Вимога симетричності вводу-виводу виконується, якщо всі процесори мають можливість доступу до одних і тих же підсистемах вводу-виводу (включаючи порти та контролери переривання), причому будь-який процесор може отримати переривання від будь-якого джерела. Деякі багатопроцесорні системи, що мають симетричний доступ до пам'яті, в той же час є асиметричними стосовно перериваннях пристроїв введення-виведення, оскільки виділяють один процесор для обробки переривань. Симетричність введення-виведення допомагає прибрати потенційно вузькі місця вводу-виводу і тим самим підвищити розширюваність системи.
Системи, що володіють симетричністю пам'яті і введення-виведення, дозволяють забезпечити розширюваність апаратних засобів, а також стандартизувати програмні засоби.
Є дві загальні реалізації SMP, відомі як сільносвязанная і слабосвязанная. Сільносвязанная реалізація базується на схемі, відповідно до якої процесори спільно використовують дані з пулу загальних ресурсів, перш за все, із загальної пам'яті. Слабосвязанние системи використовують механізм обміну повідомленнями між процесами для спільного використання ресурсів, коли це необхідно. У деяких слабосвязанних системах кожен процесор може навіть мати свій власний контролер диска і інші підсистеми.
Найбільш доцільно використовувати симетричну сільносвязанную модель. Тоді ОС забезпечує потужну підтримку симетричною багатопроцесорної обробки, так як планувальник в ядрі ОС функціонує на рівні нитки, тому сервер може призначити дві нитки одного процесу різних процесорів. Це особливо корисно для прикладних програм баз даних, де запити можуть бути розщеплені на нитки і розподілені між процесорами, що веде до значного збільшення продуктивності.
Щоб повніше скористатися перевагами SMP при організації багатозадачності, виконання ниток процесу контролюється за допомогою пріоритетних переривань. Пріоритетне переривання дозволяє операційній системі підтримувати контроль над програмами, яку програму і коли запускати, так що збилися програми не можуть поневолити систему і викликати проблеми. При пріоритетних переривання - постійна, що займають мікросекунди запуск і зупинка декількох програм - як тільки відновлюється виконання нитки, ОС може призначити її іншому процесора.
Основною перевагою такої архітектури є те, що прикладні програми мають у своєму розпорядженні стільки центральних процесорів, скільки є в наявності у сервера. Так як операційна система займається плануванням роботи процесорів, прикладних програм немає необхідності знати про кількість наявних процесорів. Операційна система призначить кожну нитку першому вільному процесора. Планувальник дозволяє розподіляти навантаження і в остаточному підсумку виконувати програми точно з тією ж швидкістю, з якою кілька центральних процесорів і можуть з ними впоратися.
Однією з переваг SMP-платформ, є їх масштабованість. Компанія, що реалізувала однопроцесорних систему з таким сервером, в майбутньому буде мати можливість реалізувати SMP з тією ж самою версією ОС. Якщо завдання зростають поступово, не обов'язково викладати відразу всі гроші. Навпаки, можна придбати спочатку сервер тільки з одним процесором, а пізніше додавати додаткові процесори. Якщо масштабованість реальна, то в міру того, як розвивається інформаційна система і, відповідно, вимоги користувачів до потужності системи, можна додати ще один процесор без якої-небудь зміни програмного забезпечення.
Для досягнення масштабованості важливо використовувати також асинхронні операції. При асинхронному введення/виведення процесу не треба чекати завершення читання або запису, перш ніж він приступить до виконання іншого завдання. Кожен процес створюється з використанням єдиної нитки, яка виступає окремим блоком під час виконання процесором команд програми. Програми можуть запускати нові нитки в міру потреби, і ОС призначає і контролює їх без участі високорівневої прикладної системи.
Прикладна програма може використовувати декілька ниток, не порушуючи основний потік програми. Програма може створити окрему нитку для кожної операції. Кожна з цих ниток, або операцій, з точки зору користувача, може виконуватися на окремому процесорі без контролю з боку прикладної програми.
Така архітектура має ще одну перевагу. Накладні витрати пов'язані радше з процесом, ніж з ниткою. Крім того, нитки створюються швидше, ніж процеси, і вони спільно використовують пам'ять всередині процесу, так що нитках немає необхідності здійснювати будь-яку спеціальну передачу даних. Крім цього, всі ресурси процесу доступні всім нитках всередині процесу.
Звичайно, для роботи з текстовими редакторами і електронними таблицями міць багатопроцесорної архітектури не буде потрібно. Однак більш актуальним вона є в рамках мережного сервера або сервера бази даних, відповідального за оперативну обробку транзакцій, що надходять від великої кількості користувачів.
При виборі прикладної програми необхідно з'ясувати, чи використовує продукт всі переваги ОС на рівні нитки, а не на рівні процесу. Визначаючи продуктивність і гнучкість будь-якої системи як єдиного цілого, необхідно мати на увазі, що апаратне забезпечення, мережева операційна система та прикладне програмне забезпечення працюють разом.
Необхідно мати на увазі, що ефективність не росте лінійно при додаванні ще одного процесора. Для будь-якої SMP-системи вигода від додаткового процесора поступово сходить нанівець з додаванням кожного наступного процесора.
Продуктивність не зростає лінійно, оскільки ОС повинна керувати кожним процесором і, отже, взаємодією процесора з внутрішніми викликами та периферійними пристроями на шині. Коли нитка в однопроцесорній системі не може більш виконуватися до здійснення деякого умови, процесор маскує програмне переривання так, що ніякий інший процес не може скористатися даним ресурсом. Потім він зберігає стан нитки, щоб виконання коду могло відновитися при здійсненні умови.
Коли є тільки один процесор, досить просто зберігати опис рівнів переривання і масок, які контролюють доступ до структур даних ОС. З додаванням кожного нового процесора це завдання стає все більш важким. Операційна система для SMP-платформи повинна уточнити, що тільки один процесор в даний момент виконує сегмент коду, який змінює глобальну структуру даних.
В системі з одним процесором маскованих переривання запобігає використання процесором ресурсу. Але в SMP-середовищі цей механізм не дає можливості гарантувати, що різні процеси не будуть мати доступу до того ж самому ресурсу через інше переривання.
У SMP ОС доцільно використовувати метод взаімоблокіровкі для управління переривань між процесорами. По суті, взаімоблокіровка є програмною процедурою, яка блокує доступ другого процесора до вже зайнятого ресурсу. Наприклад, коли ядро хоче отримати доступ до захищеної області, такий як чергу відкладених викликів процедур, воно повинно "придбати" замок, який пов'язаний з чергою. Якщо замок знаходиться в розпорядженні будь-якого процесора, то інший процесор намагається отримати замок до тих пір, поки його не звільнить інший процесор.
Такий метод дозволяє запобігти псуванню процесорами глобальних структур даних на рівні ядра. Однак при реалізації непродуманої, він може призвести до того, що процесори будуть діяти протягом тривалого періоду, чекаючи звільнився замок. Цей метод добре працює, коли виконуються невеликі фрагменти коду. Такий код найбільш часто використовується в функції ядра, які не викликають зовнішні процедури, не витісняються з пам'яті і не генерують переривань. Таким чином, у багатьох випадках взаімоблокіровка не діє, у той час як ядро може синхронізувати нитки між процесорами.
Ядро також може керувати ниткою, призначаючи їй одне з трьох станів: готова, виконується або чекає. Коли нитка чекає результатів запиту, ядро змінює стан нитки з "виконується" на "чекає" і видаляє його з черги на виконання. Після того, як нитка отримала очікувану нею інформацію, ядро змінює стан нитки з "чекає" на "готова" і повертає її в чергу. Нитка виконується, коли з'являється можливість.
Хоча це пояснення поверхово, воно все ж таки показує, наскільки складним для операційної системи виявляється керування синхронізацією декількох процесів. У міру додавання нових процесорів до системи накладні витрати на управління конфліктами зростають, і це зменшує віддачу від ОС, орієнтованих на симетрично-багатопроцесорну обробку.
3.2 Нитки (threads)
Поняття "легковагої процесу" (light-weight process), або, як прийнято називати його в сучасних варіантах ОС, "thread" (нитка, потік управління) давно відомо в області операційних систем. Інтуїтивно зрозуміло, що концепції віртуальної пам'яті й потоку команд, що виконується в цій віртуальній пам'яті, в принципі, ортогональні. Ні з чого не випливає, що однією віртуальної пам'яті повинен відповідати один і тільки один потік управління. Тому, наприклад, в ОС Multics допускалося (і було прийнятої практики) мати довільну кількість процесів, які виконуються в загальною (що розділяється) віртуальної пам'яті.
Зрозуміло, що якщо кілька процесів спільно користуються деякими ресурсами, то при доступі до цих ресурсів вони повинні синхронізуватися (наприклад, з використанням семафорів, див. розділ "Семафори"). Багаторічний досвід програмування з використанням явних примітивів синхронізації показав, що цей стиль "паралельного" програмування породжує серйозні проблеми при написанні, налагодженні і супроводі програм (найважче виявляються помилки в програмах зазвичай пов'язані з синхронізацією). Це стало однією з причин того, що в традиційних варіантах ОС поняття процесу жорстко пов'язувалося з поняттям окремої і недоступною для інших процесів віртуальної пам'яті. Кожен процес був захищений ядром операційної системи від неконтрольованого втручання інших процесів. Багато років це вважалося одним з основних достоїнств системи (утім, це думка існує і сьогодні).
Однак зв'язування процесу з віртуальною пам'яттю породжує, принаймні, дві проблеми. Перша проблема пов'язана з так званими системами реального часу. Такі системи, як правило, призначені для одночасного управління кількома зовнішніми об'єктами і найбільш природно представляються у вигляді сукупності "паралельно" (або "квазіпараллельно") виконуваних потоків команд (тобто взаємодіючих процесів). Однак якщо з кожним процесом пов'язана окрема віртуальна пам'ять, то зміна контексту процесора (тобто його перемикання з виконання одного процесу на виконання іншого процесу) є відносно дорогою операцією. Тому традиційний підхід перешкоджав використання системи в додатках реального часу.
Другий (і може бути більш істотною) проблемою стала поява так званих симетричних мультипроцесорних комп'ютерної архітектури (SMP - Symmetric Multiprocessor Processing). У таких комп'ютерах фізично присутні кілька процесорів, які мають однакові за швидкістю можливості доступу до спільно використовуваної основної пам'яті. Поява подібних машин на світовому ринку, природно, вивело на перший план проблему їх ефективного використання. Зрозуміло, що при застосуванні традиційного підходу до організації процесів від наявності загальної пам'яті не дуже багато толку (хоча при наявності можливостей розділяється пам'яті про це можна сперечатися). До моменту появи SMP з'ясувалося, що технологія програмування все ще не може запропонувати ефективного і безпечного способу реального паралельного програмування. Тому довелося повернутися до явного паралеліьному програмування з використанням паралельних процесів в загальним віртуальним (а тим самим, і основний) пам'яті з явною синхронізацією.
Що ж розуміється під "ниткою" (thread)? Це незалежний потік управління, що виконується в контексті деякого процесу. Фактично, поняття контексту процесу змінюється в такий спосіб. Все, що не відноситься до потоку управління (віртуальна пам'ять, дескриптори відкритих файлів і т. д.), залишається в загальному контексті процесу. Речі, які характерні для потоку управління (регістровий контекст, стеки різного рівня і т. д.), переходять з контексту процесу в контекст нитки. Загальна картина показана на малюнку:
Як видно з цього малюнка, всі нитки процесу виконуються в його контексті, але кожна нитка має свій власний контекст. Контекст нитки, як і контекст процесу, складається з призначеної для користувача та ядерної складових. Користувацька складова контексту нитки включає індивідуальний стек нитки. Оскільки нитки одного процесу виконуються в загальній віртуальної пам'яті, всі нитки процесу мають рівні права доступу до будь-яких частинах віртуальної пам'яті процесу, стек (сегмент стека) будь-якої нитки процесу в принципі не захищений від довільного (наприклад, через помилки) доступу з боку інших ниток . Ядерна складова контексту нитки включає її регістровий контекст (зокрема, вміст регістра лічильника команд) і динамічно створювані ядерні стеки.
Наведене короткий обговорення поняття нитки здається достатнім для того, щоб зрозуміти, що впровадження в ОС механізму легковагих процесів вимагає істотних переробок ядра системи. (Завжди важко впровадити до програми кошти, для підтримки яких вона не була спочатку пристосована.)
3.2.1 Підходи до організації ниток і управління ними в різних варіантах ОС UNIX
Хоча концептуально реалізації механізму ниток в різних сучасних варіантах практично еквівалентні (та й що особливе можна придумати з приводу легковагих процесів?), Технічно і, на жаль, щодо інтерфейсів ці реалізації розрізняються. Ми не ставимо тут перед собою цілі описати в деталях будь-яку реалізацію, однак постараємося в загальних рисах охарактеризувати різні підходи.
Почнемо з того, що різноманітність механізмів ниток у сучасних варіантах ОС UNIX саме по собі представляє проблему. Зараз досить важко говорити про можливість мобільного паралельного програмування в середовищі UNIX-орієнтованих операційних систем. Якщо програміст хоче домогтися граничної ефективності (а він повинен цього хотіти, якщо для цілей його проекту придбаний дорогий мультипроцесор), то він змушений використовувати всі унікальні можливості використовуваної ним операційної системи.
Для всіх очевидно, що сьогоднішня ситуація далека від ідеальної. Однак, мабуть, її було неможливо уникнути, оскільки постачальники симетричних мультипроцесорних архітектур повинні були якомога раніше надати своїм покупцям можливості ефективного програмування, і часу на злагоди
