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

Московський державна інституція радіотехніки, електроніки і автоматики.

(Технічний Университет).

Проект по курсу.

«Обчислювальні комплекси, системи та мережі ЭВМ».

Многопроцессорный обчислювальний комплекс з урахуванням комутаційної матриці з симетричній обробкою завдань усіма процессорами.

Група: АВ-33−93.

Студент: Ліпін В.В.

Москва.

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+1, i+2,. .. , i+N-1 припадали на N різних банків. У i-том банку пам’яті знаходяться тільки слова, адреси яких мають вигляд k*N + і (де 0 < k < M-1, а M число слів щодо одного банку). Можна досягти в N раз більшої швидкості доступу до пам’яті загалом, ніж в окремого її банку, якщо забезпечити при кожному доступі звернення до даних у кожному з банків. Є різні способи реалізації таких расслоенных структур. Більшість їх нагадують конвеєри, щоб забезпечити розсилку адрес у різні банки і мультиплексирующие які з банків дані. Отже, ступінь чи коефіцієнт розшарування визначають розподіл адрес по банкам пам’яті. Такі системи оптимізують звернення з послідовним адресами пам’яті, що характерним при підкачуванню інформацією кешпам’ять під час читання, і навіть під час запису, у разі використання кешпам’яттю механізмів зворотного копіювання. Проте, якщо потрібно доступом до непослідовно розташованим словами пам’яті, продуктивність расслоенной пам’яті може значно знижуватися. Узагальненням ідеї розшарування пам’яті є можливість кількох незалежних звернень, коли кілька людей контролерів пам’яті дозволяють банкам пам’яті (чи групам расслоенных банків пам’яті) працювати незалежно. Якщо цю систему пам’яті розроблена на підтримку безлічі незалежних запитів (як це має місце під час роботи з кэш-памятью, при реалізації многопроцессорной і векторної обробки), ефективність системи буде зацікавлений у значною мірою залежати від частоти надходження незалежних запитів до різним банкам. Звернення по послідовним адресами, чи, на більш загальному разі, звернення з адресами, який вирізняється на парне число, добре обробляються традиційними схемами расслоенной пам’яті. Проблеми виникають, якщо різниця у адреси послідовних звернень парна. Один із рішень, використовуване у великих комп’ютерах, залежить від тому, щоб статистично зменшити ймовірність подібних звернень шляхом значного збільшення кількості банків пам’яті. Наприклад, в суперкомп’ютері 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 ОС доцільно використовувати метод взаимоблокировки керувати перериваннями між процесорами. Власне, взаимоблокировка є програмної процедурою, яка доступ другого процесора до зайнятому ресурсу. Наприклад, коли ядро хоче доступом до захищеної області, а саме чергу відкладених викликів процедур, він повинен «придбати «замок, який із чергою. Якщо замок перебуває у розпорядженні будь-якого процесора, то інший процесор намагається отримати замок до того часу, поки його звільнить інший процесор. Такий метод дозволяє запобігти псування процесорами глобальних структур даних лише на рівні ядра. Проте за непродуманої реалізації, може призвести до з того що процесори будуть бути бездіяльними протягом тривалого періоду, очікуючи звільнений замок. Цей метод добре працює, коли виконуються невеликі фрагменти коду. Такий код найчастіше використовується у функціях ядра, які викликають зовнішні процедури, не витісняються з пам’яті і генерують переривань. Отже, у часто взаимоблокировка не діє, тоді як ядро має синхронізувати нитки між процесорами. Ядро він може управляти ниткою, призначаючи їй 1 із 3 станів: готова, виконується чи чекає. Коли нитку чекає результатів запиту, ядро змінює стан нитки з «виконується «на «чекає «і видаляє їх із черги виконання. Коли нитку отримала очікувану нею інформацію, ядро змінює стан нитки з «чекає «на «готова «і повертає їх у чергу. Нитка виконується, коли можливість. Хоча це пояснення поверхово, він усе-таки показує, наскільки складним для ОС виявляється управління синхронізацією кількох процесів. Принаймні додавання нових процесорів до системи накладні витрати управління конфліктами зростають, і це зменшує віддачу від ОС, орієнтованих симметрично-многопроцессорную обработку.

3.2 Нитки (threads) Поняття «легковагого процесу «(light-weight process), чи, як сьогодні називати їх у сучасних варіантах ОС, «thread «(нитку, потік управління) давно відомо у сфері операційними системами. Інтуїтивно зрозуміло, що концепції віртуальної пам’яті і потоку команд, выполняющегося у цій віртуальної пам’яті, у принципі, ортогональны. Ні із чого годі було, що однієї віртуальної пам’яті має відповідати сам і лише одне потік управління. Тому, наприклад, в ОС Multics допускалося (і було прийнятої практикою) мати довільне кількість процесів, виконуваних в загальної (поділюваної) віртуальної пам’яті. Зрозуміло, що й кілька процесів спільно користуються деякими ресурсами, то, при доступі до цих ресурсів вони мають синхронізуватися (наприклад, з допомогою семафорів, див. розділ «Семафори»). Багаторічний досвід програмування з допомогою явних примітивів синхронізації показав, що це стиль «паралельного «програмування породжує серйозні проблеми під час написання, налагодженні і супроводі програм (найбільш важко виявлені помилки у програмах зазвичай пов’язані з синхронізацією). Це було одній з причин те, що в традиційних варіантах ОС поняття процесу жорстко пов’язували з поняттям окремої і недоступною й інших процесів віртуальної пам’яті. Кожен процес був захищений ядром ОС від неконтрольованого втручання інших процесів. Багато років це вважалося однією з основних достоїнств системи (втім, цю думку є сьогодні). Проте зв’язування процесу з віртуальної пам’яттю породжує, по крайньої мері, дві проблеми. Перша проблема пов’язані з так званими системами реального часу. Такі системи, зазвичай, призначені для одночасного управління кількома зовнішніми об'єктами і найбільш природно видаються як сукупності «паралельно «(чи «квазипараллельно ») виконуваних потоків команд (т. е. взаємодіючих процесів). Але якщо з кожним процесом пов’язана окрема віртуальна пам’ять, то зміна контексту процесора (т. е. його переключення з виконання процесу виконання іншого процесу) є щодо дорогої операцією. Тому традиційний підхід перешкоджав використанню системи в додатках реального часу. Другий (і може бути більш істотною) проблемою стала поява так званих симетричних мультипроцессорных комп’ютерних архітектур (SMP — Symmetric Multiprocessor Processing). У цих комп’ютерах фізично присутні кілька процесорів, які мають однакові за швидкістю можливості доступу до спільно використовуваної основний пам’яті. Поява подібних машин на світовому ринку, природно, вивело першому плані проблему їхньої ефективної використання. Зрозуміло, що з застосуванні традиційного підходу до організації процесів від наявності спільної па-м'яті не дуже велика користь (хоча за наявності можливостей поділюваної пам’яті звідси можна сперечатися). До появи SMP з’ясувалося, що технологія програмування досі неспроможна запропонувати ефективного й екологічно безпечного способу реального паралельного програмування. Тому довелося повернутися до явному рівнобіжному програмування з допомогою паралельних процесів у спільній віртуальної (а цим, і основний) пам’яті з явною синхронізацією. Що й казати розуміється під «ниткою «(thread)? Це незалежний потік управління, що здійснюється у тих деякого процесу. Фактично, поняття контексту процесу змінюється так. Усі, що ні належить до потоку управління (віртуальна пам’ять, дескриптори відкритих файлів тощо. буд.), залишається загалом контексті процесу. Речі, які притаманні потоку управління (регистровый контекст, стеки різного рівня життя та т. буд.), переходять з контексту процесу у контекст нитки. Загальна картина показано на рисунке:

Как це випливає з цього малюнка, всі нитки процесу виконуються у його контексті, але кожна нитку має власний контекст. Контекст нитки, як і контекст процесу, складається з користувальницької та регулювання ядерної складових. Користувальницька складова контексту нитки включає індивідуальний стік нитки. Оскільки нитки процесу виконуються у спільній віртуальної пам’яті, всі нитки процесу мають рівних прав доступу до будь-яких частинам віртуальної пам’яті процесу, стік (сегмент стека) будь-який нитки процесу у принципі не захищений від довільного (наприклад, через помилки) доступу із боку інших ниток. Ядерна складова контексту нитки включає її регистровый контекст (зокрема, вміст регістру лічильника команд) і динамічно створювані ядерні стеки. Наведене стисле обговорення поняття нитки здається достатнім у тому, аби зрозуміти, що почнеться впровадження в ОС механізму легковажних процесів вимагає істотних переробок ядра системи. (Завжди важко ввести програму кошти, на підтримку яких вона була спочатку приспособлена.).

3.2.1 Підходи до організації ниток й управління ними на різні варіанти ОС UNIX Хоча концептуально реалізації механізму ниток у різних сучасних варіантах практично еквівалентні (та й що особливе можна придумати по приводу легковажних процесів?), тех-нічно та, на жаль, щодо інтерфейсів ці реалізації різняться. Не ставимо перед собою мету описати докладно якусь реалізацію, проте постараємося загалом охарактеризувати різні підходи. Почати з те, що розмаїтість механізмів ниток у сприйнятті сучасних варіантах ОС UNIX саме собі становить проблему. Нині важко говорити про можливість мобільного паралельного програмування серед UNIXорієнтованих операційними системами. Якщо програміст хоче домогтися граничною ефективності (і повинен цього хотіти, для цілей його проекту придбаний дорогий мультипроцессор), він змушений використовувати усі унікальні можливості використовуваної їм операційній системи. Всім очевидно, що сьогоднішня ситуація далекою від ідеальної. Проте, повидимому, її було неможливо уникнути, оскільки постачальники симетричних мультипроцессорных архітектур мали якомога швидше надати своїм покупцям можливості ефективного програмування, і часу на узгодження рішень не було (будь-яких постачальників передусім цікавить обсяг продажу, а проблеми майбутнього оставляются у майбутнє). Застосовувані нині підходи залежить від того, наскільки уважно розробники ОС ставилися до проблем реального часу. (Повертаючись до впровадження цього розділу, вкотре відзначимо, що саме маємо у вигляді «м'яке «реальне час, т. е. програмно-апаратні системи, що забезпечують швидку реакцію на зовнішні події, але час реакції встановлено абсолютно суворо.) Типова система реального часу складається з загального монітора, який відстежує загальний стан системи та реагує на зовнішні та внутрішні події, і сукупності оброблювачів подій, які, бажано паралельно, виконують основні функції системи. Зрозуміло, що з можливостей реального розпаралелювання функцій оброблювачів залежать загальні тимчасові показники системи. Якщо, наприклад, під час проектування системи помічено, що типовою картиною є «одночасне «вступ у систему N зовнішніх подій, то бажано гарантувати наявність реальних N пристроїв обробки, у яких можуть базуватися оброблювачі. Цими спостереженнях грунтується підхід компанії Sun Microsystems. У системі Solaris (правильніше говорити SunOS 4. x, оскільки Solaris в термінології Sun є не операційну систему, а розширену операційну середу) прийнято наступний підхід. Після запуску будь-якого процесу можна зажадати резервування однієї чи кількох процесорів мультипроцессорной системи. Це означає, що операційна система має не надасть жодному іншому процесу можливості виконання на зарезервированном (ых) процессоре (ах). Незалежно від цього, готова до виконання хоча тільки нитку такого процесу, зарезервовані процесори ні використовуватися ні на чого більше. Далі, при освіті нитки можна довести її правильність за однією або кількома процесорами у складі зарезервованих. Зокрема, в такий спосіб, в принципі можна прив’язати нитку до певного фіксованому процесору. У загальному разі деяка сукупність потоків управління прив’язується до деякою сукупності процесорів те щоб середнє час реакції системи реального часу задовольняло зовнішнім критеріям. Вочевидь, що це «ассемблерный «стиль програмування (занадто багато перекладається на користувача), але він відкриває широкі можливості перед розробниками систем реального часу (які, щоправда, після цього залежать тільки від особливостей конкретної ОС, а й від конкретної конфігурації даної комп’ютерної установки). Підхід Solaris переслідує мети задовольнити розробників систем «м'якого «(а, можливо, і «жорсткого ») реального часу, і тому фактично подає до рук кошти розподілу критичних обчислювальних ресурсів. За інших підходах більшою мірою переслідується мета рівномірної балансування завантаження мультипроцессора. І тут програмісту не надаються кошти явною прив’язки процесорів до процесів чи ниткам. Система допускає явне розпаралелювання не більше загальної віртуальної пам’яті і «обіцяє «, що в міру можливостей все процесори обчислювальної системи буде завантажено рівномірно. Такий підхід забезпечує найбільш ефективне використання загальних обчислювальних ресурсів мультипроцессора, але з гарантує коректність виконання систем реального часу (а то й рахувати можливість встановлення спеціальних пріоритетів реального часу). Зазначимо існування ще з однією апаратно-програмної проблеми, що з нитками (але тільки із нею). Проблема пов’язана з тим, що у існуючих симетричних мультипроцессорах зазвичай кожен процесор має власної сверхбыстродействующей буферної пам’яттю (кэшем). Ідея кешу, загалом, у тому, щоб забезпечити процесору дуже швидкий (без необхідності виходу шину доступу до спільної оперативної пам’яті) доступом до найбільш актуальним даним. Зокрема, якщо програма виконує запис на згадку про, це дію необов’язково відразу відображається у відповідній елементі основний пам’яті; до певного часу змінений елемент даних можуть утримувати лише у локальному кэше того процесора, у якому виконується програма. Звісно, суперечить ідеї спільного використання віртуальної пам’яті нитками процесу (і навіть ідеї використання пам’яті, поділюваної між кількома процесами). Це дуже непроста проблема, належить області проблем «когерентності кэшей ». Теоретично є багато підходів до її рішенню (наприклад, апаратне розпізнавання необхідності виштовхування записи з кешу з синхронним оголошенням недійсним змісту всіх кэшей, які включають хоча б елемент даних). Проте за практиці такі складні дії не застосовуються, і звичайним прийомом є скасування режиму кэширования у цьому разі, коли різними процесорах мультипроцессорной системи виконуються нитки процесу чи процеси, використовують поділювану пам’ять. Після запровадження поняття нитки трансформується саме поняття процесу. Тепер краще (і правильніше) розуміти процес ОС UNIX як певний контекст, до складу якого віртуальну пам’ять та інші системні ресурси (включаючи відкриті файли), у якому виконується, по крайнього заходу, один потік управління (нитку), у якого власним (простішим) контекстом. Тепер ядро знає про існування цих двох рівнів контекстів здатне порівняно швидко змінювати контекст нитки (не змінюючи загального контексту процесу) і такий самий, як й раніше, змінювати контекст процесу. Останнє зауваження належить до синхронізації виконання ниток процесу (точніше було говорити про синхронізації доступу ниток до загальним ресурсів процесу — віртуальної пам’яті, відкритим файлам тощо. буд.). Звісно, можна користуватися (порівняно) традиційними засобами синхронізації (наприклад, семафорами). Проте здається, що систему може надати для синхронізації ниток процесу дешевші кошти (оскільки всі нитки працюють у загальному контексті процесу). Зазвичай це кошти ставляться до класу коштів взаємного винятку (т. е. до класу семафороподобных коштів). На жаль, й у ставлення до справжньому часу відсутня будь-яка стандартизация.

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

Механизм встановлення блокировки:

/* операція перевірки */ виконувати поки (блокування встановлено) { призупинитися (до зняття блокування); }; встановити блокировку;

Механизм зняття блокировки:

снять блокування; вивести ринок із стану приостанова всі, призупинені в результаті блокировки;

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

Припустимо, що блокування знято, І що процеси різними процесорах одночасно намагаються перевірити її наявність і встановити його. У час t вони виявляють зняття блокування, встановлюють її знову, входять у критичний ділянку та створюють небезпека тріщини структур даних ядра. У умови одночасності є відхилення: механізм не спрацює, якщо до того, як процес виконує операцію перевірки, жоден інший процес не виконав операцію встановлення блокування. Якщо, наприклад, після виявлення зняття блокування процесор A обробляє переривання і тоді момент процесор B виконує перевірку й встановлює блокування, після виходу з переривання процесор A як і встановить блокування. Щоб запобігти виникненню цій ситуації, потрібно зробити, щоб процедура блокування була неподільної: перевірку наявності блокування і його установку слід поєднати у одну операцію, щоб у кожен час з блокуванням мав справу лише одне процесс.

3.3.1 Визначення семафорів Семафор є опрацьований ядром целочисленный об'єкт, для якого визначені такі елементарні (неподільні) операции:

Инициализация семафори, у яких семафору присвоюється ненегативне значення; Операція типу P, що вчетверо-вп'ятеро зменшує значення семафори. Якщо значення семафори опускається нижче нульової позначки, виконує операцію процес призупиняє своєї роботи; Операція типу V, збільшила значення семафори. Якщо значення семафори в результаті операції прибуває або дорівнює 0, одне із процесів, призупинених під час здійснення операції P, виходить із стану приостанова; Умовна операція типу P, скорочено CP (conditional P), що вчетверо-вп'ятеро зменшує значення семафори і повертає логічне значення «істина «у разі, коли значення семафори залишається позитивним. Якщо результаті операції значення семафори має стати негативним чи нульовим, ніяких дій з нього немає і операція повертає логічне значення «брехня » .

Определенные в такий спосіб семафори, безумовно, неможливо пов’язані з семафорами користувальницького уровня.

3.3.2 Реалізація семафорів Дийкстра показав, що семафори можна реалізувати без використання спеціальних машинних інструкцій. Тут є реалізують семафори функції, написані мові Си.

struct semaphore { int val[NUMPROCS]; /* замок — 1 елемент за кожен процесор */ int lastid; /* ідентифікатор процесора, який отримав семафор останнім */.

}; int procid; /* унікальний ідентифікатор процесора */ int lastid; /* ідентифікатор процесора, який отримав семафор останнім */.

Init (semaphore) struct semaphore semaphore; { int і; for (і = 0; і < NUMPROCS; і++) semaphore. val[i] = 0;

}.

Pprim (semaphore) struct semaphore semaphore;

{ int i, first; loop: first = lastid; semaphore. val[procid] = 1; forloop: for (і = first; і < NUMPROCS; і++) { if (і == procid) { semaphore. val[i] = 2; for (і = 1; і < NUMPROCS; і++) if (і ≠ procid && semaphore. val[i] == 2) goto loop; lastid = procid; return; /* успішний розв’язок, ресурс можна використовувати */.

} else if (semaphore.val[i]) goto loop;

} first = 1; goto forloop;

}.

Vprim (semaphore) struct semaphore semaphore;

{ lastid = (procid + 1) % NUMPROCS; /* наступного року процесор */ semaphore. val[procid] = 0;

}.

Функция Pprim блокує семафор за результатами перевірки значень, які у масиві val; кожен процесор у системі управляє значенням одного елемента масиву. Перш ніж заблокувати семафор, процесор перевіряє, не заблокований вже семафор іншими процесорами (відповідні їм елементи в масиві val тоді мають значення, рівні 2), і навіть не робляться чи спроби у цей час заблокувати семафор із боку процесорів з нижчим кодом ідентифікації (відповідні їм елементи мають значення, рівні 1). Якщо будь-який з умов виконується, процесор переустановлює значення свого елемента у 1 і повторює спробу. Коли функція Pprim відкриває зовнішній цикл, змінна циклу має значення, на одиницю що перевищує код ідентифікації того процесора, який використовував ресурс останнім, цим гарантується, що жодного з процесорів неспроможна монопольно заволодіти. Функція Vprim звільняє семафор і це відкриває й інших процесорів можливість отримання виняткового доступу до ресурсу шляхом очищення відповідного поточному процесору елемента у масиві val і перенастройки значення lastid. Щоб захистити ресурс, слід виконати наступний набір команд:

Pprim (семафор); команди використання ресурсу; Vprim (семафор);

В більшості машин є набір елементарних (неподільних) інструкцій, що реалізують операцію блокування дешевшими засобами, бо цикли, що входять до функцію Pprim, працюють повільно й знижують продуктивність системи. Приміром, в машинах серії IBM 370 підтримується інструкція compare and swap (порівняти і переставити), в машині AT&T 3B20 — інструкція read and clear (прочитати і очистити). За виконання інструкції read and clear процесор зчитує вміст осередки пам’яті, очищає її (скидає в 0) і з результатів порівняння початкового вмісту з 0 встановлює код завершення інструкції. Якщо таку ж інструкцію над тієї ж осередком паралельно виконує іще одна процесор, одне із двох процесорів прочитає початкове вміст, а інший — 0: неподільність операції гарантується апаратним шляхом. Отже, з допомогою використання інструкції функцію Pprim можна було б реалізувати менш складними средствами:

struct semaphore { int lock; };

Init (semaphore) struct semaphore semaphore; { semaphore. lock = 1; }.

Pprim (semaphore) struct semaphore semaphore; { while (read_and_clear (semaphore.lock)); }.

Vprim (semaphore) struct semaphore semaphore; { semaphore. lock = 1; }.

Процесс повторює інструкцію read and clear в циклі до того часу, доки буде лічено значення, не на нуля. Початкова значення компоненти семафори, що з блокуванням, має бути одно 1. Як таку, цю семафорную конструкцію не можна реалізовувати складі ядра операційній системи, оскільки працюючий із нею процес теж не виходить з добірки, доки досягне своєї мети. Якщо семафор використовується для блокування структури даних, процес, виявивши семафор заблокованим, припиняє своє виконання, щоб ядро мав можливість переключитися на контекст іншого процесу виконати іншу корисну роботу. З допомогою функцій Pprim і Vprim можна реалізувати складніший набір семафорных операцій, відповідний тому складу, який визначено у розділі «Визначення семафорів». Спочатку дамо визначення семафори як структури, яка перебуває з поля блокування (управляючого доступом до семафору), значення семафори і черги процесів, призупинених по семафору. Поле блокування містить інформацію, що відкриває під час операцій типу P і V доступом до іншим полях структури лише процесу. Після закінчення операції значення поля скидається. Це значення визначає, чи дозволений процесу доступом до критичного ділянці, защищаемому семафором.

Алгоритм операції P: /* Операція над семафором типу P вхідні інформація: (1) семафор; (2) пріоритет; вихідна інформація: 0 — у разі нормального завершення; 1 — у разі аварійного виходу зі стану приостанова по cигналу, ухваленого режимі ядра; */ { Pprim (semaphore.lock); зменшити (semaphore.value); якщо (semaphore.value >= 0) { Vprim (semaphore.lock); повернути (0); } /* слід перейти до стану приостанова */ якщо (перевіряються сигнали) { якщо (є сигнал, прерывающий перебування у стані приостанова) увеличить (semaphore.value); якщо (сигнал прийнятий у режимі ядра) { Vprim (semaphore.lock); повернути (-1); } інакше { Vprim (semaphore.lock); longjmp; } } } поставити процес у кінець списку призупинених по семафору; Vprim (semaphore.lock); виконати переключення контексту; перевірити сигнали (див. вище); повернути (0); }.

В початку виконання алгоритму операції P ядро з допомогою функції Pprim надає процесу право виняткового доступу до семафору зменшує значення семафори. Якщо семафор має ненегативне значення, поточний процес отримує доступом до критичного ділянці. Після закінчення роботи процес скидає блокування семафори (з допомогою функції Vprim), відкриваючи доступом до семафору й інших процесів, і повертає ознака успішного завершення. Якщо у результаті зменшення значення семафори стає негативним, ядро призупиняє виконання процесу, використовуючи алгоритм, такий алгоритму sleep: виходячи з значенні пріоритету, ядро перевіряє що надійшли сигнали, включає поточний процес у список призупинених процесів, у якому ті представлені гаразд надходження, і виконує переключення контекста.

Алгоритм V /* Операція над семафором типу V вхідні інформація: адресу семафори вихідна інформація: відсутня */ { Pprim (semaphore.lock); збільшити (semaphore.value); якщо (semaphore.value.