Московський державний інститут радіотехніки, електроніки та автоматики
(Технічний Університет)
Проект по курсу
"Обчислювальні комплекси, системи і мережі ЕОМ"
Багатопроцесорний обчислювальний комплекс на основі комутаційної матриці з симетричною обробкою завдань усіма процесорами
Група: АВ-33-93
Студент: Ліпін В.В.
Москва
1998
1. Загальна частина
1.1 Зміст
1. Загальна частина
1. Зміст
2. Завдання
3. Введення
2. Апаратна організація МПВК
1. Структурна схема МПВК
2. Функціональна схема елемента комутаційної матриці
3. Організація оперативної пам'яті
1. Пам'ять з розшаруванням
2. Застосування коду Хеммінга в модулях пам'яті
4. Організація резервування та відновлення при відмові будь-якого компоненту МПВК
3. Організація функціонування ОС на МПВК
1. Симетрична багатопроцесорна обробка (SMP)
2. Нитки
1. Підходи до організації ниток і управління ними в різних варіантах
ОС UNIX
3. Семафори
1. Визначення семафорів
2. Реалізація семафорів
4. Статті без ситуації
5. Запобігання тупикових ситуацій
4 Лінійне впорядкування ресурсів
1 Ієрархічне впорядкування ресурсів
2 Алгоритм банкіра
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 -орієнтованих операційних систем. Якщо програміст хоче домогтисяграничної ефективності (а він повинен цього хотіти, якщо для цілей йогопроекту придбаний дорогий мультипроцесор), то він змушенийвикористовувати всі унікальні можливості використовуваної ним операційноїсистеми.
Для всіх очевидно, що сьогоднішня ситуація далека від ідеал
