Реферати

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

Разноуровневое навчання в ході учнівського експерименту. Уляновський інститут підвищення кваліфікації і перепідготовки працівників утворення Кафедра природознавства Випускна робота (авторська робота)

Деревина в'яза як матеріал для столярно-меблевого виробництва. Зміст: Деревина в'яза як матеріал для столярно-меблевого виробництва" 1. Фізичні властивості деревини 3 1.1. Зовнішній вигляд деревини 3 1.2. Вологість деревини і властивості, зв'язані з її зміною 4

Полеміка Сократа із софістами. Сократ Сократ (469-399 до Р. Х.) - давньогрецький філософ. Був сином каменотеса і сповитухи. Одержав різнобічне утворення. Брав активну участь у громадському житті Афін. У 399 р. До Р. Х. йому було пред'явлене обвинувачення в тім, "що він не шанує богів, яких шанує місто, а вводить нові божества, і винний у тім, що розбещує юнацтво".

Деякі додатки фінансової математики. Деякі додатки фінансової математики. Конверсія валюти і нарахування відсотків. Розглянемо сполучення конверсії (обміну) валюти і нарощення простих відсотків, порівняємо результати від безпосереднього розміщення наявних коштів у чи депозити після попереднього обміну на іншу валюту.

Взаємодія підприємства і навколишнього середовища. Взаємодія підприємства і навколишнього середовища ЗМІСТ ЕКОЛОГІЧНИЙ ПАСПОРТ ПІДПРИЄМСТВА ВПЛИВ НАВКОЛИШНЬОГО СЕРЕДОВИЩА НА ЕКОНОМІЧНИЙ РІСТ ПРОМИСЛОВІСТЬ

Московський державний інститут радіотехніки, електроніки і автоматики (Технічний Університет)

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

"Обчислювальні комплекси, системи і мережі ЕОМ"

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

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

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

Москва

1998

1. Загальна частина

1.1 Зміст

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 < k < M-1, а M число слів в одному банку). Можна досягнути в N раз більшої швидкості доступу до пам'яті загалом, чому у окремого її банку, якщо забезпечити при кожному доступі звернення до даних в кожному з банків. Є різні способи реалізації таких расслоенних структур. Більшість з них нагадують конвейєри, що забезпечують розсилку адрес в різні банки і мультиплексирующие поступаючі з банків дані. Таким чином, міра або коефіцієнт розшарування визначають розподіл адрес по банках пам'яті. Такі системи оптимізують звертання за послідовними адресами пам'яті, що є характерним при подкачке інформації в кеш-пам'ять при читанні, а також при записі, у разі використання кеш-пам'яттю механізмів зворотного копіювання. Однак, якщо потрібно доступ до непослідовно розташованих слів пам'яті, продуктивність расслоенной пам'яті може значно знижуватися.

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

Якщо система пам'яті розроблена для підтримки безлічі незалежних запитів (як це має місце при роботі з кеш-пам'яттю, при реалізації многопроцессорной і векторної обробки), ефективність системи буде значною мірою залежати від частоти надходження незалежних запитів до різних банків. Звертання за послідовними адресами, або, в більш загальному випадку, звертання за адресами, відмінними на непарне число, добре обробляються традиційними схемами расслоенной пам'яті. Проблеми виникають, якщо різниця в адресах послідовних звертань парна. Одне з рішень, що використовується у великих комп'ютерах, полягає в тому, щоб статистично зменшити імовірність подібних звертань шляхом значного збільшення кількості банків пам'яті. Наприклад, в суперкомп'ютері NEC SX/3 використовуються 128 банків пам'яті.

Подібні проблеми можуть бути вирішені як програмними, так і апаратними коштами.

2.3.2 Застосування коду Хеммінга в модулях пам'яті

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

Оскільки більшість сучасних високопродуктивних мікропроцесорів мають розрядність 64 біта, необхідно забезпечити розрядність пам'яті не менше за 64 біт. Цій розрядності відповідає код Хеммінга (72, 64), що означає наявність 64 інформаційних розрядів і 8 контрольних. Можна розрахувати ефект від застосування коректуючого кодування:

Нехай імовірність відмови одиночного модуля пам'яті розрядністю 1 біт за деякий час P1=10-5, тоді імовірність відмови однієї з необхідних 64 модулів пам'яті за той же час Робщ=64*P1=6.4*10-4. У разі застосування коду Хеммінга для втрати інформації необхідні дві помилки в 72-х розрядах: Робщ=(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-орієнтованих операційних систем. Якщо програміст хоче добитися граничної ефективності (а він повинен цього хотіти, якщо для цілей його проекту придбаний мультипроцессор, що дорого коштує ), то він вимушений використати всі унікальні можливості операційної системи, що використовується ним.

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

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

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

У системі Solaris (правильніше говорити SunOS 4.x, оскільки Solaris в термінології Sun являє собою не операційну систему, а розширену операційну середу) прийнятий наступний підхід. При запуску будь-якого процесу можна зажадати резервування одного або декількох процесорів мультипроцессорной системи. Це означає, що операційна система не надасть ніякому іншому процесу можливості виконання на зарезервованому (их) процесорі (ах). Незалежно від того, чи готова до виконання хоч би одна нитка такого процесу, зарезервовані процесори не будуть використовуватися ні для чого іншого.

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

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

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

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

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

3.3 Семафори

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

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

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

/* операція перевірки */

виконувати поки (блокування встановлене)

{

припинитися (до зняття блокування);

};

встановити блокування;

Механізм зняття блокування:

зняти блокування;

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

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

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

3.3.1 Визначення семафорів

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

- Ініціалізація семафора, внаслідок якої семафору привласнюється ненегативне значення;

- Операція типу Р, що зменшує значення семафора. Якщо значення семафора опускається нижче нульової відмітки, виконуючий операцію процес припиняє свою роботу;

- Операція типу V, що збільшує значення семафора. Якщо значення семафора внаслідок операції стає більше або дорівнює 0, один з процесів, припинених під час виконання операції Р, виходить з стану приостанова;

- Умовна операція типу Р, скорочено CP (conditional Р), що зменшує значення семафора і повертаюче логічне значення "істину" в тому випадку, коли значення семафора залишається позитивним. Якщо внаслідок операції значення семафора повинне стати негативним або нульовим, ніяких дій над ним не проводиться і операція повертає логічне значення "брехня".

Певним таким чином семафори, безумовно, ніяк не пов'язані з семафорами призначеного для користувача рівня.

3.3.2 Реалізація семафорів

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

struct semaphore

{

int val[NUMPROCS]; /* замок - 1 елемент на кожний процесор */

int lastid; /* ідентифікатор процесора, що отримав семафор останнім */

};

int procid; /* унікальний ідентифікатор процесора */

int lastid; /* ідентифікатор процесора, що отримав семафор останнім */

Init(semaphore)

struct semaphore semaphore;

{

int i;

for (i = 0; i < NUMPROCS; i++)

semaphore.val[i] = 0;

}

Pprim(semaphore)

struct semaphore semaphore;

{

int i, first;

loop:

first = lastid;

semaphore.val[procid] = 1;

forloop:

for (i = first; i < NUMPROCS; i++)

{

if (i == procid)

{

semaphore.val[i] = 2;

for (i = 1; i < NUMPROCS; i++)

if (i != 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&Т 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 можна реалізувати більш складний набір семафорних операцій, відповідний тому складу, який визначений в розділі "Визначення семафорів". Для початку дамо визначення семафора як структури, що складається з поля блокування (керівника доступом до семафора), значення семафора і черги процесів, припиненого по семафору. Поле блокування містить інформацію, що відкриває під час виконання операцій типу Р і V доступ до інших полів структури тільки одному процесу. По завершенні операції значення поля скидається. Це значення визначає, чи дозволений процесу доступ до критичної дільниці, що захищається семафором.

Алгоритм операції Р:

/*

Операція над семафором типу Р

вхідна інформація:

(1) семафор;

(2) пріоритет;

вихідна інформація:

0 - у разі нормального завершення;

1 - у разі аварійного виходу з стану приостанова по сигналу, прийнятому в режимі ядра;

*/

{

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);

}

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

Алгоритм V

/*

Операція над семафором типу V

вхідна інформація: адреса семафора

вихідна інформація: відсутній

*/

{

Pprim(semaphore.lock);

збільшити (semaphore.value);

якщо (semaphore.value < 0)

{

видалити з списку процесів, припинених по семафору, перший по рахунку процес;

перевести його в стан готовності до запуску;

}

Vprim(semaphore.lock);

}

Операція V отримує винятковий доступ до семафора через функцію Pprim і збільшує значення семафора. Якщо черга припинених по семафору процесів непуста, ядро вибирає з неї перший процес і переводить його в стан "готовності до запуску". Операції Р і V по своїй дії схожі на функції sleep і wakeup. Головна відмінність між ними складається в тому, що семафор є структурою даних, тоді як що використовується функціями sleep і wakeup адреса являє собою усього лише число. Якщо початкове значення семафора - нульове, при виконанні операції Р над семафором процес завжди припиняється, тому операція Р може замінювати функцію sleep. Операція V, проте, виводить з стану приостанова тільки один процес, тоді як однопроцесорний функція wakeup поновлює всі процеси, припинені за адресою, пов'язаній з подією. З точки зору семантики використання функції wakeup означає: дана системна умова більш не задовольняється, отже, всі припинені по умові процеси повинні вийти з стану приостанова. Так, наприклад, процеси, припинені в зв'язку із зайнятістю буфера, не повинні далі перебувати в цьому стані, якщо буфер більше не використовується, тому вони поновлюються ядром. Ще один приклад: якщо декілька процесів виводять дані на термінал за допомогою функції write, термінальний драйвер може перевести їх в стан приостанова в зв'язку з неможливістю обробки великих обсягів інформації. Пізніше, коли драйвер буде готовий до прийому наступної порції даних, він відновить всі припинені ним процеси. Використання операцій Р і V в тих випадках, коли встановлюючі блокування процеси отримують доступ до ресурсу по черзі, а всі інші процеси - в порядку надходження запитів, є більш переважним. У порівнянні з однопроцесорний процедурою блокування (sleep-lock) дана схема звичайно виграє, оскільки якщо при настанні події всі процеси поновлюються, більшість з них може знову наштрикатися на блокування і знов перейти в стан приостанова. З іншого боку, в тих випадках, коли потрібно вивести з стану приостанова всі процеси одночасно, використання операцій Р і V представляє відому складність. Якщо операція повертає значення семафора, чи є вона еквівалентної функції wakeup?

while (value(semaphore) <)

{

V(semaphore);

};

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

Процес А продовжить своє виконання, думаючи, що ним відновлені всі припинені по семафору процеси. Таким чином, цикл виконання операції не дає гарантії поновлення всіх припинених процесів, оскільки він не є елементарним. Розглянемо ще один феномен, пов'язаний з використанням семафорів в однопроцесорний системі. Передбачимо, що два процеси, А і В, конкурують за семафор. Процес А виявляє, що семафор вільний і що процес В припинений; значення семафора дорівнює -1. Коли за допомогою операції V процес А звільняє семафор, він виводить тим самим процес В з стану приостанова і знову робить значення семафора нульовим. Тепер передбачимо, що процес А, як і раніше виконуючись в режимі ядра, намагається знов заблокувати семафор. Проводячи операцію Р, процес припиниться, оскільки семафор має нульове значення, незважаючи на те, що ресурс поки вільний. Системі доведеться "розщедритися" на додаткове перемикання контексту. З іншого боку, якби блокування було реалізоване на основі однопроцесорний схеми (sleep-lock), процес А дістав би право на повторне використання ресурсу, оскільки за цей час жоден з процесів не зміг би заблокувати його. Для цього випадку схема sleep-lock більш підходить, ніж схема з використанням семафорів. Коли блокуються відразу декілька семафорів, черговість блокування повинна виключати виникнення тупикових ситуацій. Як приклад розглянемо два семафори, А і В, і два алгоритми, вимагаючого одночасного блокування семафорів. Якби алгоритми встановлювали блокування на семафори в зворотному порядку, як випливає з малюнка,

пішло б виникнення тупикової ситуації; процес А на однойменному процесорі захоплює семафор SA, в той час як процес В на своєму процесорі захоплює семафор SB. Процес А намагається захопити і семафор SB, але внаслідок операції Р переходить в стан приостанова, оскільки значення семафора SB не перевищує 0. Те ж саме відбувається з процесом В, коли останній намагається захопити семафор SA. Ні той, ні інший процеси продовжуватися вже не можуть. Для запобігання виникненню подібних ситуацій використовуються відповідні алгоритми виявлення небезпеки взаємного блокування, що встановлюють наявність небезпечної ситуації і що ліквідовують її. Проте, використання таких алгоритмів "обважнювати" ядро. Оскільки число ситуацій, в яких процес повинен одночасно захоплювати декілька семафорів, досить обмежене, легше було б реалізовувати алгоритми, застережливі виникнення тупикових ситуацій ще до того, як вони будуть мати місце. Якщо, наприклад, якийсь набір семафорів завжди блокується в одному і тому ж порядку, тупикова ситуація ніколи не виникне. Але в тому випадку, коли захвата семафорів в зворотному порядку уникнути не вдається, операція CP запобіжить виникненню тупикової ситуації:

якщо операція завершиться невдало, процес В звільнить свої ресурси, щоб уникнути взаємного блокування, і пізніше запустить алгоритм на виконання повторно, швидше усього, тоді, коли процес А завершить роботу з ресурсом. Щоб попередити одночасне звертання процесів до ресурсу, програма обробки переривань, здавалося б, могла скористатися семафором, але через те, що вона не може припиняти свою роботу (див. розділ 6), використати операцію Р в цій програмі не можна. Замість цього можна використати "циклічне блокування" (spin lock) і не перейти в стан приостанова, як в наступному прикладі:

while (! CP(semaphore));

Операція повторюється в цикле доти, поки значення семафора не перевищить 0; програма обробки переривань не припиняється і цикл завершується тільки тоді, коли значення семафора стане позитивним, після чого це значення буде зменшене операцією CP. Щоб запобігти ситуації взаємного блокування, ядру треба заборонити всі переривання, що виконують "циклічне блокування". Інакше виконання процесу, що захопив семафор, буде перервано ще до того, як він зможе звільнити семафор; якщо програма обробки переривань спробує захопити цей семафор, використовуючи "циклічне блокування", ядро заблокує саме себе. Як приклад звернемося до малюнка:

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

3.4 Тупикові ситуації

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

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

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

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

Проблема тупиків включає в себе наступні задачі:

- запобігання тупикам,

- розпізнавання тупиків,

- відновлення системи після тупиків.

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

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

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

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

3.5 Запобігання тупиковим ситуаціям

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

3.5.1 Лінійне упорядкування ресурсів

Нехай всі ресурси повністю впорядковані від 1 до r. Ми можемо накласти наступне обмеження: процес не може запитувати ресурс Rk, якщо він втримує ресурс Rhи при цьому k < h.

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

Приведемо приклад того, як застосовується це правило. Нехай є процес, який використовує ресурси, впорядковані як А, В, З, D, Е, наступним способом:

Тоді процес може робити наступне:

захопити (А); захопити (В); захопити (З);

використати З;

використати А, З;

використати А, В, З;

звільнити (А); звільнити (В); захопити (Е);

використати З і Е;

звільнити (З); звільнити (Е); захопити (D);

використати D;

звільнити (D);

Стратегія цього типу може використовуватися, коли ми маємо декілька ресурсів. Цю стратегію просто застосовувати, при цьому міра параллелизма меншає не дуже сильно.

3.5.2 Ієрархічне упорядкування ресурсів

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

Тоді якщо процес хоче використати ресурси е, f, i, k ондолжен використати команди в наступній послідовності:

блокування (a);

блокування (b);

блокування (h);

звільнення (a);

блокування (d);

звільнення (b);

блокування (i);

блокування (j);

звільнення (h);

блокування (k);

звільнення (j);

блокування (е);

блокування (f);

звільнення (d);

3.5.3 Алгоритм банкіра

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

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

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

Алгоритм симулює надання запитаного ресурсу і потім переглядає виникаюче внаслідок виконання запиту стан системи.

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

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

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

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

3.6 Захист інформації

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

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

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

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

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

Найбільш важливі вимоги до підсистеми безпеки такі:

- Власник ресурсу повинен мати можливість управляти доступом до ресурсу.

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

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

- Адміністратор системи повинен мати можливість контролю пов'язаних з безпекою подій. Доступ до цих контрольних даних повинен бути обмежений адміністратором.

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

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

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

4Литература

1. "Обчислювальні комплекси, системи і мережі"

А. М. Ларіонов, С. А. Майоров, Г. І. Новіков

Ленінград, ЕНЕРГОАТОМИЗДАТ, 1987

(до розділу "Структурна схема МПВК")

2. "The design of the UNIX operating system"

Maurice J. Bach

Prentice-Hall, 1986, ISBN 0-13-201757-1 025

(до розділу "Семафори")

3. "Мережеві операційні системи"

Н. А. Оліфер, В. Г. Оліфер,

Інформаційно-аналітичні матеріали Центра Інформаційних Технологій

(до розділу "Тупики")

4. Курс лекцій "Introduction to Distributed Systems and Networks" (CIS 307)

Giorgio Ingargiola, Associate Professor of Computer and Information Science Department.

Університет м. Темпль (шт. Філадельфія, США)

(до розділу "Запобігання тупикам")

5. "Операційна система UNIX"

С. Д. Кузнецов

Інформаційно-аналітичні матеріали Центра Інформаційних Технологій

(до розділу "Нитці")

6. "Мережеві ОС для SMP-платформ"

Е. Ленгрен

"Відкриті Системи" № 2(10)/95 стор. 16

(до розділу "Симетрична многопроцессорная обробка")

7. "Специфікація многопроцессорних систем компанії Intel"

А. А. Мячев

"Відкриті Системи" № 3(11)/95 стор. 56

(до розділу "Симетрична многопроцессорная обробка")

8. "Ресурси Windows NT Server і Workstation версія 3.5"

Microsoft Press, 1995

(до розділу "Захист інформації")