Ліфтової алгоритм Лінуса – ЧАСТИНА 2

Якщо ж для запиту, який знаходиться в голові FIFO-черзі запису або FIFOочереді читання, закінчується період очікування (тобто поточний момент часу стає більшим, ніж момент часу, коли закінчується період очікування, повязаний із запитом), то deadline-планувальник починає обробляти запити з відповідної черги FIFO Таким чином планувальник з лімітом за часом намагається гарантувати, що запитом не чекатимуть довше максимального періоду очікування (рис 133)

Черга FIFO запитів читання

Черга FIFO запитів записи

Відсортована чергу

Черга диспетчеризації

Диск

Рис 133Три черги планувальника введення-виведення з лімітом за часом

Слід зауважити, що deadline-плаііровщік введення-виведення не дає суворої гарантії часу затримки запиту Однак він, загалом, дозволяє відправляти на обробку запити до або незабаром після того, як закінчився їх період очікування Це дозволяє запобігти ситуації нестачі обслуговування запитів Так як для запитів читання максимальний час очікування значно більше, ніж для запитів записи, то планувальник з лімітом за часом також позполяет гарантувати, що обслуговування запитів записи не приведе до нестачі обслуговування запитів читання Більший пріоритет запитів читання дозволяє мінімізувати час затримки при операціях читання

4 Для deadline-планувальника операція вставки в початок запиту виконується опціонально Зазвичай невиконання вставки в початок запиту не приводить до проблем, тому що в більшості випадків кількість запитів, що е можуть бути додані в початок, очен ь незначно

Код планувальника введення-виведення з лімітом за часом знаходиться у файлі drivers / block / deadline-ioschedс

Прогнозирующий планувальник вводу-виводу

Хоча планувальник з лімітом за часом введення-виведення і виконує роботу з мінімізації затримок читання, це робиться ціною зменшення глобального швидкодії Розглянемо систему з великою активністю запису Кожен раз, коли приходить запит на читання, планувальник відразу ж починає його виконувати Це призводить до того, що відразу ж запускається операція пошуку того місця на диску, де буде виконано читання і відразу після виконання читання знову здійснюється пошук того місця, де буде виконана запис, і так повторюється при кожному запиті читання Великий пріоритет запитів читання річ хороша, але дві операції пошуку на кожен запит читання (переміщення в точку читання і назад в точку записи) дуже погано позначаються на загальній дискової продуктивності Мета прогнозирующего планувальника вводу-виводу (anticipatory I / O scheduler) – забезпечення хороших характеристик по затримках читання і в той же час забезпечення відмінною загальної продуктивності

Прогнозирующий планувальник побудований на базі планувальника введення-виведення з лімітом але часу Тому він не особливо відрізняється У прогнозуючому планувальнику реалізовані три черги (плюс чергу диспетчеризації) і обробка часу очікування для кожного запиту, так само як і У разі deadline-планувальника Головна відмінність полягає в наявності додаткового евристичного прогнозування (anticipation heuristic)

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

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

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

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

Рівень блочного введення-виведення

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

Код прогнозирующего планувальника знаходиться у файлі drivers / block /

as-iosched з дерева вихідних кодів ядра

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

Планувальник вводу-виводу з повністю рівноправними чергами

Планувальник вводу-виводу з повністю рівноправними чергами (Complete Fair Queuing, CFQ) був розроблений для певного типу навантажень на систему, по на практиці він дозволяє отримати хорошу продуктивність для широкого діапазону типів навантаження Він фундаментальним чином відрізняється від усіх раніше розглянутих планувальників введення-виведення

Планіровщі до CF Q розподіляємо т все пріходяща е запит и введення-виведення з певних черг на підставі того, який процес надіслав цей запит Наприклад, запити від процесу foo йдуть в чергу foo, запити від процесу bar – в чергу bar У межах кожної черги запити обєднуються з суміжними і сортуються Таким чином черги підтримуються в відсортованому стані, так само як і у випадку інших планувальників введення-виведення Відмінність планувальника CFQ полягає в тому, що він підтримує окрему чергу для кожного процесу, який виконує операції введення-виведення

Після цього планувальник CFQ виконує запити з різних черг по круговому алгоритму, виконуючи конфігурується кількість запитів (за замовчуванням 4) з кожної черги, перед тим як перейти до наступної Це дозволяє отримати рівномірний розподіл пропускної здатності диска для кожного процесу в системі Передбачуване використання такого планувальника-мультимедійні додатки, для яких він дозволяє гарантувати, що, наприклад, аудіопрогравач завжди буде встигати вчасно заповнювати аудіобуфери з диска Проте планувальник CFQ на практиці добре працює для багатьох сценаріїв завантаженості системи

Код CFQ планувальника знаходиться у файлі drivers / block / cfq-ioschedс Цей планувальник рекомендується для офісних компютерів, хоча добре працює практично для всіх типів навантажень, за винятком, може бути, вже дуже екстремальних типів завантаженості

Планувальник вводу-виводу nоор

Четвертий, і останній, тип планувальника введення-виведення-це планувальник noop (no operation, з відсутністю операцій) Він названий так тому, що практично нічого не робить Цей планувальник НЕ виконує ніякої сортування або інших операцій для запобігання пошуку по влаштуванню Йому немає необхідності виконувати нічого, включаючи алгоритми, які мінімізують затримки і були розглянуті для попередніх планувальників

Планувальник вводу-виводу nоор виконує тільки обєднання приходять запитів із суміжними, які перебувають у черзі Крім цього, більше ніяких функцій у даного планувальника немає Він просто обслуговує чергу запитів, які передаються драйверу блокового пристрою, в режимі FIFO

Планувальник nоор не є повністю марним У тому, що він нічого не робить, є великий сенс Він розрахований на блокові пристрої, які дозволяють виконувати істинно довільний доступ, такі як плати флеш-памяті Якщо для блочного пристрою немає накладних витрат, повязаних з пошуком по пристрою, то немає і необхідності виконувати сортування і вставку знову приходять запитів, і планувальник nоор – ідеальний варіант

Код планувальника nоор знаходиться у файлі drivers / block / noop-ioschedс Він призначений тільки для пристроїв з довільним доступом

Вибір планувальника введення-виведення

У ядрах серії 26 є чотири планувальника введення-виведення Кожен з цих планувальників може бути активізований За замовчуванням всі блокові пристрої використовують прогнозирующий планувальник вводу-виводу Планувальник можна змінити, вказавши параметр ядра elevator = <плaніpoвщік> в командному рядку при завантаженні системи, де <планувальник> – Це один з підтримуваних типів планувальника, які показані в табл 132

Таблиця 132 Можливі значення параметра elevato r

Значення Тип планувальника

as cfq  deadline noop

Прогнозирующий

З повністю рівноправними чергами

З лімітом за часом

З відсутністю операцій (nоор)

Наприклад, вказівка ​​параметра elevator = cf q в командному рядку ядра при завантаженні системи означає, що для всіх блокових пристроїв буде використовуватися планувальник з повністю рівноправними чергами

Резюме

У цьому розділі були розглянуті основи роботи пристроїв блокового вводу-виводу, а також структури даних, що використовуються для роботи рівня введення-виведення блоками: структура bio, яка представляє виконувану операцію введення-виведення структура buffer_head, яка представляє відображення блоків на сторінки памяті структура request, яка представляє собою окремий запит вводу-виводу Після розгляду запитів вводу-виводу був описаний їх короткий, але важливий шлях, кульмінацією якого є проходження через планувальник вводу-виводу Були розглянуті дилеми, що виникають при плануванні операцій введення-виведення, і чотири типи планувальника, які на даний момент існують в ядрі Linux, а також планувальник введення виведення з ядра 24 – ліфтової алгоритм Лінуса

Далі ми розглянемо адресний простір процесу

Адресний простір процесу

главі 11, Управління памяттю, було розказано про те, як ядро ​​управляє фізичної намяті На додаток до того, що ядро ​​повинно керувати своєю памяттю, воно також має, управляти і адресним простором процесів-тим, як память бачиться для кожного процесу в системі Операційна система Linux – це операційна система з віртуальною памяттю (virtual memory operating system), тобто для всіх процесів виконується віртуалізація ресурсів памяті Для кожного процесу створюється ілюзія того, що він один використовує всю фізичну память в системі Ще більш важливо, що адресний простір процесів може бути навіть значно більше обсягу фізичної памяті У цій главі розповідається про те,

як ядро ​​управляє адресним простором процесу

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

32ілі 64-бітове адресний простір Термін плоске позначає, що адресний простір складається з одного діапазону адрес (наприклад, 32-розрядне адресний простір займає діапазон адрес від 0 до 429 496 729) Деякі операційні системи надають сегментированное адресний простір – адресний простір складається більше ніж з одного діапазону адрес, тобто складається з сегментів Сучасні операційні системи зазвичай надають плоске адресний простір Розмір адресного простору залежить від апаратної платформи Зазвичай для кожного процесу існує свій адресний простір Адреса памяті в адресному просторі одного процесу не має ніякого відношення до такого ж адресою памяті в адресному просторі іншого процесу Тим Проте кілька процесів можуть спільно використовувати одне загальне адресний простір Такі процеси називаються потоками

Значення адреси памяті – це задане значення з діапазону адрес адресного простору, як, наприклад, 41021f000 Це значення ідентифікує певний байт в 32-бітовому адресному просторі Важливою частиною адресного простору є інтервали адрес памяті, до яких процес має право доступу, як, наприклад, 08048000-0804с000 Такі інтервали дозволених адрес називаються  областями памяті (memory area)За допомогою ядра процес може динамічно додавати і видаляти області памяті свого адресного простору

Процес має право доступу тільки до дійсним областям памяті Більш того, на область памяті можуть бути встановлені права тільки для читання або заборону на виконання Якщо процес звертається до адресою памяті, який не перебуває у дійсній області памяті, або доступ до дійсної області виконується забороненим чином, то ядро ​​знищує процес з жахливим сполученням Segmentation Fault (Помилка сегментації)

Області памяті можуть містити таку потрібну інформацію

• Відображення виконуваного коду з виконуваного файлу в область памяті процесу, яка називається сегментом коду (text section)

Відображення ініціалізованих змінних з виконуваного файлу в область памяті процесу, яка називається сегментом даних (data section)

• Відображення сторінки памяті, заповненої нулями, в область памяті процесу, яка містить неініціалізовані глобальні змінні і називаєтьсясегментом bss1  (bss section) Нульова сторінка памяті (zero page, сторінка памяті, заповнена нулями) – це сторінка памяті, яка повністю заповнена нульовими значеннями і використовується, наприклад, для зазначеної вище цілі

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

• Додаткові сегменти коду, даних і BSS кожної спільно використовуваної бібліотеки, таких як бібліотека libc і динамічний компонувальник, які завантажуються в адресний простір процесу

• Всі файли, вміст яких відображено в память

• Всі області спільно використовуваної памяті

• Всі анонімні відображення в память, як, наприклад, повязані з функцією malloc () 2

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

1 Термін BSS склався історично і і є достаточн про старим Він означає block started by symbol (блок, що починається з символу) Неініціалізірованни е змінні е в виконуваному файлі не зберігаються, оскільки з ним і не повязане ніякого значення Проте стандарт мову а С вимагає, щоб неініціалізірованни м змінні м присвоювалося виразно е значення за замовчуванням (звичайно про всі заполняетс я нулями) Тому ядро ​​завантажує змінні е (без їх значень) з виконуваного файлу в память і відображає в цю память нульову сторінку, тим самим змінним присвоюється нульове значення без необхідності даремно витрачає ь місце в обєктних файлі на непотрібну ініціалізацію

2 У більш нових версіях бібліотеки giibc фушщіяmalloc( )   реалізована через системний виклик

ттар (),а не через викликbrk()

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*