Відмінності між версіями «Тема 11. Багатопроцесорні системи.»
(→Планування у багатопроцесорних системах) |
|||
| (не показано 9 проміжних версій цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | + | Багатозадачність в операційній системі призначена для спільного використання процесора кількома процесами. У випадку, коли в комп'ютері встановлено більш ніж один процесор, ядро містить додатковий планувальник процесорів, що відслідковує їх завантаженість, розподіляє виконувальні процеси між наявними процесорами для максимально ефективного використання обчислювальної системи. Залежно від способу використовування процесорів, операційні системи з підтримкою мультипроцесорності поділяють на групи з симетричним або асиметричним опрацюванням даних. | |
При асиметричному опрацюванні даних один процесор вибирається для виконання операційної системи, а інші виконують тільки завдання. | При асиметричному опрацюванні даних один процесор вибирається для виконання операційної системи, а інші виконують тільки завдання. | ||
| − | При симетричному опрацюванні даних, система виконується на будь-якому вільному процесорі або на всіх процесорах одночасно. Такий підхід дозволяє оптимально використовувати потужність кількох процесорів, тому що сама система часом виявляється досить завантаженою. До того ж, в асиметричній системі збільшення числа процесорів та навантаження на кожний з них приводить до затримок з обчисленнями, що стримує збільшення продуктивності. Іншим недоліком асиметричної схеми є нерівномірна завантаженість процесорів або, зупинка деяких з них при повному завантаженні інших. | + | При симетричному опрацюванні даних, система виконується на будь-якому вільному процесорі або на всіх процесорах одночасно. Такий підхід дозволяє оптимально використовувати потужність кількох процесорів, тому що сама система часом виявляється досить завантаженою. До того ж, в асиметричній системі збільшення числа процесорів та навантаження на кожний з них приводить до затримок з обчисленнями, що стримує збільшення продуктивності. Іншим недоліком асиметричної схеми є нерівномірна завантаженість процесорів або, зупинка деяких з них при повному завантаженні інших. |
| − | Для отримання максимальної потужності у сучасних ЕОМ використовуються як найновіші досягнення розвитку елементної бази, так і нові рішення в архітектурі комп'ютерів. Втілюючи ідею одночасного виконання кількох дій, розглядають дві реалізації: конвеєрність і власне паралельність. | + | Для отримання максимальної потужності у сучасних ЕОМ використовуються як найновіші досягнення розвитку елементної бази, так і нові рішення в архітектурі комп'ютерів. Втілюючи ідею одночасного виконання кількох дій, розглядають дві реалізації: конвеєрність і власне паралельність. |
| − | + | '''Паралельне опрацювання.''' Якщо певний пристрій виконує одну операцію за одиницю часу, то тисячу операцій він виконає за тисячу одиниць. Якщо припустити, що є п'ять таких незалежних пристроїв, які працюють одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту ж роботу виконає за 1000/N одиниць часу. | |
| − | + | '''Конвеєрне опрацювання.''' Ідея конвеєрного опрацювання полягає у виділенні окремих етапів виконання загальної операції, причому кожен етап, виконавши свою роботу, передавав би результат наступному, одночасно приймаючи нову порцію вхідних даних. Одержуємо очевидний виграш у швидкості обробки за рахунок сполучення раніше рознесених у часі операцій. | |
| − | ' | + | Припустимо, що в операції можна виділити п'ять мікрооперацій, кожна з яких виконується за одну одиницю часу. Якщо є один неподільний послідовний пристрій, то 100 пар аргументів він опрацює за 500 одиниць, якщо кожну мікрооперацію виконати в окремому конвеєрному пристрої, то на п'ятій одиниці часу на різній стадії обробки такого пристрою будуть знаходиться перші п'ять пар аргументів, а весь набір зі ста пар буде опрацьований за 5+99=104 одиниці часу — прискорення в порівнянні з послідовним пристроєм майже в п'ять разів (відповідно кількості ступенів конвеєра). |
| − | + | Усі сучасні мікропроцесори, Athlon XP 2700+, Athlon XP 2800+, Athlon 64 FX, Athlon 64 Х2, в діапазоні від 3800+ до 6000+ використовують той або інший метод паралельного опрацювання, хоча ці ідеї з'явилися досить давно і були реалізовані у деяких комп'ютерах у 60-70 роках. Після належного відпрацьовування технології і здешевлення виробництва ідеї паралельного опрацювання даних почали використовуватися в комп'ютерах середнього класу, а сьогодні все це в повному обсязі втілюється в робочих станціях і персональних комп'ютерах. | |
| − | + | ||
| − | Усі сучасні мікропроцесори, | + | |
Сьогодні розвиток високопродуктивної обчислювальної техніки проводиться у чотирьох напрямках: | Сьогодні розвиток високопродуктивної обчислювальної техніки проводиться у чотирьох напрямках: | ||
| − | |||
| − | |||
| − | ''' | + | '''Векторно-конвейєрні комп'ютери.''' Особливістю таких машин є конвеєрні функціональні пристрої, які містять набір векторних інструкцій у системі команд. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри. Типовим представником даного напрямку є лінія векторно-конвеєрних комп'ютерів CRAY компанії Cray Research. |
| − | + | ||
| − | ''' | + | '''Масивно-паралельні комп'ютери з розподіленою пам'яттю.''' Ідея побудови комп'ютерів цього класу досить проста, реалізується з серійних мікропроцесорів з локальною пам'яттю, об'єднаних за допомогою комунікаційного середовища, наприклад, мережі. Серед переваг виділяють простий підбір оптимальної конфігурації, якщо потрібна висока продуктивність — додаються процесори, якщо ні — вилучаються. Недоліком є мала швидкість міжпроцесорної взаємодія відносно локального опрацювання даних самими процесорами. Написати ефективну програму для таких комп'ютерів досить складно, а для деяких алгоритмів іноді просто неможливо. |
| + | До даного класу належать комп'ютери Intel Paragon, IBM SP1, Parsytec, до певної міри IBM SP2 і CRAY T3D/T3E, хоча в цих комп'ютерах вплив зазначеного недоліку намагаються зробити мінімальним. До цього ж класу можна віднести і мережі комп'ютерів, що досить часто розглядають як дешеву альтернативу дорогим суперкомп'ютерам. | ||
| − | + | '''Паралельні комп'ютери з загальною пам'яттю.''' Вся оперативна пам'ять таких комп'ютерів розподіляється між кількома однаковими процесорами. Це знімає проблеми попереднього класу, але додає нові -число процесорів, що мають доступ до загальної пам'яті з технічних причинах не можна зробити великим. До даного напрямку входять багато сучасних багатопроцесорних SMP-комп'ютерів, сервер HP Т600 або Sun Ultra Enterprise 5000. | |
| − | + | Останній напрямок не є самостійним, а скоріше являє собою комбінації попередніх трьох. З кількох процесорів, традиційних або векторно-конвеєрних і загальної для них пам'яті формується обчислювальний вузол. Якщо обчислювальної потужності отриманого вузла не досить, то об'єднують кілька вузлів високошвидкісними каналами. Подібну архітектуру називають кластерною, по такому принципу побудовані CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 і інші. Саме цей напрямок на сьогодні є найбільш перспективним. | |
| − | == '''Підтримка багатопроцесорності в операційних системах''' == | + | Продуктивність багатопроцесорних систем не зростає пропорційно числу використовуваних процесорів. Відповідно приципу Амдала максимальний виграш, що можна отримати, незалежить від кількості використовуваних процесорів у системі і не перевищуватиме 10-кратного прискорення виконання програми. 10 - це теоретична верхня оцінка найкращого випадку, коли ніяких інших негативних факторів немає. |
| + | |||
| + | =='''Підтримка багатопроцесорності в операційних системах'''== | ||
'''''Асиметрична багатопроцесорність'''''<br> | '''''Асиметрична багатопроцесорність'''''<br> | ||
| Рядок 36: | Рядок 34: | ||
У разі використання асиметричної багатопроцесорності кожен процесор виконує код операційної системи незалежно від інших процесорів. Кожна копія ОС може бути завантажена в окрему ділянку пам'яті, можливе також спільне використання коду ОС різними процесорами з виділенням окремих ділянок пам'яті для даних.<br> | У разі використання асиметричної багатопроцесорності кожен процесор виконує код операційної системи незалежно від інших процесорів. Кожна копія ОС може бути завантажена в окрему ділянку пам'яті, можливе також спільне використання коду ОС різними процесорами з виділенням окремих ділянок пам'яті для даних.<br> | ||
Цей підхід було використано на ранніх стадіях розвитку підтримки багато процесорних архітектур в ОС. Наведемо його недоліки. | Цей підхід було використано на ранніх стадіях розвитку підтримки багато процесорних архітектур в ОС. Наведемо його недоліки. | ||
| − | |||
| − | • Усі процеси користувача деякої копії ОС виконуються на тому самому процесорі, що й сама копія. Немає можливості організувати паралельне виконання коду в рамках окремого процесу, не можна вирівнювати навантаження на окремі процесори і на пам'ять. | + | • Усі процеси користувача деякої копії ОС виконуються на тому самому процесорі, що й сама копія. Немає можливості організувати паралельне виконання коду в рамках окремого процесу, не можна вирівнювати навантаження на окремі процесори і на пам'ять. |
| − | • Неможливо організувати дисковий кеш через те, що копії ОС різних процесорів кешуватимуть дискові блоки окремо. Якщо різні процесори одночасно модифікують один і той самий дисковий блок у кеші, а потім спробують зберегти ці зміни на диск, втратиться інформація, оскільки тільки одна з цих змін буде справді записана на диск. | + | • Неможливо організувати дисковий кеш через те, що копії ОС різних процесорів кешуватимуть дискові блоки окремо. Якщо різні процесори одночасно модифікують один і той самий дисковий блок у кеші, а потім спробують зберегти ці зміни на диск, втратиться інформація, оскільки тільки одна з цих змін буде справді записана на диск. |
'''''Симетрична багатопроцесорність''''' | '''''Симетрична багатопроцесорність''''' | ||
| Рядок 46: | Рядок 43: | ||
Основним підходом, який застосовують нині для підтримки UMA-архітектур, є симетрична багатопроцесорність(SMP). У даному разі у спільну пам'ять завантажують єдину копію операційної системи і всіх її даних, при цьому її код може бути виконаний кожним із процесорів або кількома процесорами одночасно. | Основним підходом, який застосовують нині для підтримки UMA-архітектур, є симетрична багатопроцесорність(SMP). У даному разі у спільну пам'ять завантажують єдину копію операційної системи і всіх її даних, при цьому її код може бути виконаний кожним із процесорів або кількома процесорами одночасно. | ||
| − | == '''Особливості SMP-систем'''== | + | =='''Особливості SMP-систем'''== |
•Усі процесори системи доступні з коду ОС. Планувальник ОС може організувати виконання її коду або коду потоку користувача на будь-якому процесорі. | •Усі процесори системи доступні з коду ОС. Планувальник ОС може організувати виконання її коду або коду потоку користувача на будь-якому процесорі. | ||
| Рядок 68: | Рядок 65: | ||
'''Масштабування навантаження''' | '''Масштабування навантаження''' | ||
| + | |||
Під масштабуванням навантаження (workload scalability) у SMP-системах розуміють вплив додавання нових процесорів на продуктивність системи. У реальних умовах воно залежить від багатьох факторів. | Під масштабуванням навантаження (workload scalability) у SMP-системах розуміють вплив додавання нових процесорів на продуктивність системи. У реальних умовах воно залежить від багатьох факторів. | ||
Поточна версія на 13:34, 24 квітня 2013
Багатозадачність в операційній системі призначена для спільного використання процесора кількома процесами. У випадку, коли в комп'ютері встановлено більш ніж один процесор, ядро містить додатковий планувальник процесорів, що відслідковує їх завантаженість, розподіляє виконувальні процеси між наявними процесорами для максимально ефективного використання обчислювальної системи. Залежно від способу використовування процесорів, операційні системи з підтримкою мультипроцесорності поділяють на групи з симетричним або асиметричним опрацюванням даних.
При асиметричному опрацюванні даних один процесор вибирається для виконання операційної системи, а інші виконують тільки завдання.
При симетричному опрацюванні даних, система виконується на будь-якому вільному процесорі або на всіх процесорах одночасно. Такий підхід дозволяє оптимально використовувати потужність кількох процесорів, тому що сама система часом виявляється досить завантаженою. До того ж, в асиметричній системі збільшення числа процесорів та навантаження на кожний з них приводить до затримок з обчисленнями, що стримує збільшення продуктивності. Іншим недоліком асиметричної схеми є нерівномірна завантаженість процесорів або, зупинка деяких з них при повному завантаженні інших.
Для отримання максимальної потужності у сучасних ЕОМ використовуються як найновіші досягнення розвитку елементної бази, так і нові рішення в архітектурі комп'ютерів. Втілюючи ідею одночасного виконання кількох дій, розглядають дві реалізації: конвеєрність і власне паралельність.
Паралельне опрацювання. Якщо певний пристрій виконує одну операцію за одиницю часу, то тисячу операцій він виконає за тисячу одиниць. Якщо припустити, що є п'ять таких незалежних пристроїв, які працюють одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту ж роботу виконає за 1000/N одиниць часу.
Конвеєрне опрацювання. Ідея конвеєрного опрацювання полягає у виділенні окремих етапів виконання загальної операції, причому кожен етап, виконавши свою роботу, передавав би результат наступному, одночасно приймаючи нову порцію вхідних даних. Одержуємо очевидний виграш у швидкості обробки за рахунок сполучення раніше рознесених у часі операцій.
Припустимо, що в операції можна виділити п'ять мікрооперацій, кожна з яких виконується за одну одиницю часу. Якщо є один неподільний послідовний пристрій, то 100 пар аргументів він опрацює за 500 одиниць, якщо кожну мікрооперацію виконати в окремому конвеєрному пристрої, то на п'ятій одиниці часу на різній стадії обробки такого пристрою будуть знаходиться перші п'ять пар аргументів, а весь набір зі ста пар буде опрацьований за 5+99=104 одиниці часу — прискорення в порівнянні з послідовним пристроєм майже в п'ять разів (відповідно кількості ступенів конвеєра).
Усі сучасні мікропроцесори, Athlon XP 2700+, Athlon XP 2800+, Athlon 64 FX, Athlon 64 Х2, в діапазоні від 3800+ до 6000+ використовують той або інший метод паралельного опрацювання, хоча ці ідеї з'явилися досить давно і були реалізовані у деяких комп'ютерах у 60-70 роках. Після належного відпрацьовування технології і здешевлення виробництва ідеї паралельного опрацювання даних почали використовуватися в комп'ютерах середнього класу, а сьогодні все це в повному обсязі втілюється в робочих станціях і персональних комп'ютерах.
Сьогодні розвиток високопродуктивної обчислювальної техніки проводиться у чотирьох напрямках:
Векторно-конвейєрні комп'ютери. Особливістю таких машин є конвеєрні функціональні пристрої, які містять набір векторних інструкцій у системі команд. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри. Типовим представником даного напрямку є лінія векторно-конвеєрних комп'ютерів CRAY компанії Cray Research.
Масивно-паралельні комп'ютери з розподіленою пам'яттю. Ідея побудови комп'ютерів цього класу досить проста, реалізується з серійних мікропроцесорів з локальною пам'яттю, об'єднаних за допомогою комунікаційного середовища, наприклад, мережі. Серед переваг виділяють простий підбір оптимальної конфігурації, якщо потрібна висока продуктивність — додаються процесори, якщо ні — вилучаються. Недоліком є мала швидкість міжпроцесорної взаємодія відносно локального опрацювання даних самими процесорами. Написати ефективну програму для таких комп'ютерів досить складно, а для деяких алгоритмів іноді просто неможливо. До даного класу належать комп'ютери Intel Paragon, IBM SP1, Parsytec, до певної міри IBM SP2 і CRAY T3D/T3E, хоча в цих комп'ютерах вплив зазначеного недоліку намагаються зробити мінімальним. До цього ж класу можна віднести і мережі комп'ютерів, що досить часто розглядають як дешеву альтернативу дорогим суперкомп'ютерам.
Паралельні комп'ютери з загальною пам'яттю. Вся оперативна пам'ять таких комп'ютерів розподіляється між кількома однаковими процесорами. Це знімає проблеми попереднього класу, але додає нові -число процесорів, що мають доступ до загальної пам'яті з технічних причинах не можна зробити великим. До даного напрямку входять багато сучасних багатопроцесорних SMP-комп'ютерів, сервер HP Т600 або Sun Ultra Enterprise 5000.
Останній напрямок не є самостійним, а скоріше являє собою комбінації попередніх трьох. З кількох процесорів, традиційних або векторно-конвеєрних і загальної для них пам'яті формується обчислювальний вузол. Якщо обчислювальної потужності отриманого вузла не досить, то об'єднують кілька вузлів високошвидкісними каналами. Подібну архітектуру називають кластерною, по такому принципу побудовані CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 і інші. Саме цей напрямок на сьогодні є найбільш перспективним.
Продуктивність багатопроцесорних систем не зростає пропорційно числу використовуваних процесорів. Відповідно приципу Амдала максимальний виграш, що можна отримати, незалежить від кількості використовуваних процесорів у системі і не перевищуватиме 10-кратного прискорення виконання програми. 10 - це теоретична верхня оцінка найкращого випадку, коли ніяких інших негативних факторів немає.
Зміст
Підтримка багатопроцесорності в операційних системах
Асиметрична багатопроцесорність
У разі використання асиметричної багатопроцесорності кожен процесор виконує код операційної системи незалежно від інших процесорів. Кожна копія ОС може бути завантажена в окрему ділянку пам'яті, можливе також спільне використання коду ОС різними процесорами з виділенням окремих ділянок пам'яті для даних.
Цей підхід було використано на ранніх стадіях розвитку підтримки багато процесорних архітектур в ОС. Наведемо його недоліки.
• Усі процеси користувача деякої копії ОС виконуються на тому самому процесорі, що й сама копія. Немає можливості організувати паралельне виконання коду в рамках окремого процесу, не можна вирівнювати навантаження на окремі процесори і на пам'ять.
• Неможливо організувати дисковий кеш через те, що копії ОС різних процесорів кешуватимуть дискові блоки окремо. Якщо різні процесори одночасно модифікують один і той самий дисковий блок у кеші, а потім спробують зберегти ці зміни на диск, втратиться інформація, оскільки тільки одна з цих змін буде справді записана на диск.
Симетрична багатопроцесорність
Основним підходом, який застосовують нині для підтримки UMA-архітектур, є симетрична багатопроцесорність(SMP). У даному разі у спільну пам'ять завантажують єдину копію операційної системи і всіх її даних, при цьому її код може бути виконаний кожним із процесорів або кількома процесорами одночасно.
Особливості SMP-систем
•Усі процесори системи доступні з коду ОС. Планувальник ОС може організувати виконання її коду або коду потоку користувача на будь-якому процесорі.
•Для всіх процесорів доступні спільні дані, при цьому когерентність кеша підтримується апаратно.
•Потоки користувача і потоки ядра можуть виконуватися паралельно на різних процесорах. Під час виконання потік може мігрувати із процесора на процесор.
•Спроба повторного читання одних і тих самих даних процесором CPUA може дати інший результат внаслідок того, що ці дані були змінені процесором CPUB.
•У системі можливе вирівнювання навантаження між процесорами, для чого планувальник ОС може передавати новий потік для виконання найменш завантаженому процесору.
Додавання нового процесора у систему автоматично робить його доступним для виконання коду ОС або процесів користувача. При цьому навантаження на інші процесори автоматично знижується.
Для того, щоб скористатися перевагами багатопроцесорної архітектури, код ОС має бути багатопотоковим і реентерабельним. При цьому необхідна підтримка синхронізації на рівні ядра. Найпримітивнішим підходом до забезпечення синхронізації є велике блокування ядра (big kernellock). При цьому кожен процесор перед виконанням будь-якого коду ОС займає глобальний м'ютекс. Цей підхід неефективний, оскільки в конкретний момент часу код ОС може бути виконаний тільки на одному процесорі.
Сучасні ОС реалізують гнучкіший підхід, у якому код ядра розбивають на незалежні критичні ділянки, із кожною з яких пов'язують окремий м'ютекс.
Продуктивність багатопроцесорних систем
Масштабування навантаження
Під масштабуванням навантаження (workload scalability) у SMP-системах розуміють вплив додавання нових процесорів на продуктивність системи. У реальних умовах воно залежить від багатьох факторів.
•У разі збільшення кількості процесорів зростає навантаження на системну шину та пам'ять і , як наслідок, ціна промаху кеша.
•Кількість промахів кеша при цьому теж збільшується внаслідок того, що в системі збільшено кількість потоків, які потрібно планувати.
•Що більше процесорів, то більше зусиль потрібно докладати для забезпечення когерентності кеша.
Кількість блокувань у системі зростає із ростом кількості процесорів.
Найбільший рівень масштабування навантаження досягають для потоків, обмежених можливостями процесора, найменший — для потоків, обмежених можливостями пристроїв введення-виведення.
Продуктивність окремих застосувань
Розглянемо, яким чином впливає наявність кількох процесорів на час виконання програмного коду. Багатопроцесорність дає змогу поліпшити характеристики програми тільки тоді, коли в ній наявний паралелізм. При цьому для того, щоб ОС мала можливість організувати такий паралелізм, код програми має бути багатопотоковим. Якщо програма не використовує багатопотоковість, її виконання у багатопроцесорній системі може спричинити зниження продуктивності через очікування на додаткових блокуваннях і міграцію між процесорами.
Планування у багатопроцесорних системах
Головною особливістю планування у багатопроцесорних системах є його двовимірність. Крім прийняття рішення проте, який потік потрібно поставити на виконання наступним, необхідно визначити, на якому процесорі він має виконуватися. Крім того, важливо виділяти взаємозалежні потоки, що їх доцільно виконувати паралельно на кількох процесорах, аби їм було простіше взаємодіяти один із одним. У цьому розділі розглянемо деякі підходи до організації планування, які враховують ці фактори, а у наступному - важливе поняття спорідненості процесора, що впливає на організацію планування у багатопроцесорних системах.
Планування з розподілом часу
Найпростішим способом організації багатопроцесорного планування незалежних потоків є використання структурних даних для готових потоків, спільної для всіх процесорів. Прикладом такої структури може бути багаторівнева черга, яка використовується під час планування із пріоритетами. Коли потік на одному з процесорів завершує роботу або призупиняється, цей процесор починає виконувати код планувальника ОС. Планувальник при цьому блокує чергу готових потоків, ставить на виконання потік із найвищим пріоритетом і вилучає його керуючий блок із черги. Наступний за пріоритетом потік почне виконуватися на наступному звільненому процесорі. Такий підхід називають плануванням із розподілом часу, оскільки, як і у традиційних системах із розподілом часу, щоразу приймають рішення щодо використання одного процесора і виконання одного потоку. Головним недоліком цього підходу є високий ступінь паралелізму доступу до черги готових потоків, що може стати «вузьким місцем» системи. Є ймовірність того, що більшу частину часу потоки проводитимуть в очікуванні на м'ютексі, який захищає чергу. Крім того, немає можливості уникнути перемикання контексту в разі призупинення потоку і подальшої його міграції на інший процесор.
Планування з розподілом простору
Планування з розподілом часу не пристосоване до організації виконання потоків, пов'язаних між собою, оскільки кожен потік розглядають окремо. Для організації виконання пов'язаних потоків необхідно одночасно розглядати кілька процесорів і розподіляти по них набір потоків. Цей підхід називають плануванням із розподілом простору. Найефективнішим алгоритмом планування із розподілом простору є бригадне планування(gang scheduling). Цей алгоритм працює так. 1.Пов'язані потоки (наприклад, потоки одного процесу) одночасно запускають на виконання на максимально можливій кількості процесорів. Такі потоки становлять бригаду. 2.Усі потоки бригади виконуються впродовж однакового для всіх кванта часу. 3.Після вичерпання кванта часу відбувається повне перепланування для всіх процесорів. Виконання починають потоки іншої бригади.
