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

Розглянемо деякі планувальники введення-виведення, що застосовуються в реальному житті Перший планувальник вводу-виводу, який ми розглянемо,називається Linus Elevator (ліфтової алгоритм Лінуса) Це не помилка, дійсно існує ліфтової планувальник, розроблений Лісусом Торвальдсом і названий на його честь Це основний планувальник вводу-виводу в ядрі 24 У ядрі 26 його замінили іншими планировщиками, які ми нижче розглянемо Однак оскільки цей алгоритм значно простіше нових і в той же час дозволяє виконувати майже ті ж функції, то він заслуговує на увагу

Ліфтово ї алгоритм Лінуса дозволяє виконувати як обєднання, так і сортування запитів Коли запит додається в чергу, спочатку він порівнюється з усіма чекаючими запитами, щоб виявити всі можливі кандидати па обєднання Алгоритм Лінуса виконує два типи обєднання: додавання в початок

запиту (front merging) і додавання в кінець запиту (back merging) Тип обєднання відповідає тому, з якого боку знайдено сусідство Якщо новий запит слід перед існуючим, то виконується вставка в початок запиту Якщо новий запит слід відразу за існуючим – додавання виконується в кінець черги У звязку з тим, що сектори, в яких зберігається файл, розташовані в міру збільшення номера сектора і операції введення-виведення найчастіше виконуються від початку файлу до кінця, а не навпаки, то при звичайній роботі вставка в початок запиту зустрічається значно рідше, ніж вставка в кінець Проте алгоритм Лінуса перевіряє і виконує обидва типу обєднання,

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

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

• Якщо запит до сусіднього сектору перебуває у черзі, то існуючий запит і новий обєднуються в один

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

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

• І нарешті, якщо така позиція не знайдена, то запит поміщається в кінець черги

Планувальник вводу-виводу з лімітом за часом

Планувальник вводу-виподят з лімітом за часом (Deadline I / O scheduler, deadline-планувальник вводу-виводу) розроблений з метою запобігання затримок обслуговування, які можуть виникати для алгоритму Лінуса Якщо задатися метою тільки мінімізувати кількість операцій пошуку, то при великій кількості операцій введення-виведення з однієї області диска можуть виникати затримки обслуговування для операцій з іншими областями диска, причому на невизначений час Більш того, потік запитів до однієї і тієї ж області диска може призвести до того,

Глава 13

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

Гірше того, загальна проблема затримки обслуговування запитів призводить до приватної проблемі затримки обслуговування читання при обслуговуванні запису (writes-starving-reads) Зазвичай операції записи можуть бути відправлені на обробку диском в будь-який момент, коли ядру це необхідно, причому це виконується повністю асинхронно по відношенню до користувача програмі, яка згенерувала запит запису Обробка ж операцій читання досить сильно відрізняється Зазвичай, коли користувальницький додаток відправляє запит на читання, це додаток блокується до тих пір, поки запит не виконаний, тобто запити читання виникають синхронно по відношенню до додатка, яке ці запити генерує У звязку з цим час реакції системи, в основному, не залежить від латентності записи (часу затримки, яке необхідно на виконання запиту записи), а затримки читання (час, який необхідно на виконання операції читання) дуже важливо мінімізувати Латентність записи мало впливає на продуктивність користувальницьких программ3, але ці програми повинні з тремтячими руками чекати завершення кожного запиту читання Отже, затримки читання дуже важливі для продуктивності системи

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

Слід звернути увагу, що зменшення часу затримки в обслуговуванні може бути виконано тільки за рахунок зменшення загального швидкодії системи Навіть для алгоритму Лінуса такий компроміс існує, хоча і в більш мякій формі Алгоритм Лінуса міг би забезпечити і велику загальну пропускну спроможність (шляхом зменшення кількості операцій пошуку), якби запити завжди поміщалися в чергу відповідно з номерами секторів і не виконувалася перевірка на наявність старих запитів і вставка в кінець черги Хоча мінімізація кількості операцій пошуку і важлива, тим не менш невизначений час затримки теж не дуже хороша річ Тому deadline-планувальник і виконує багато роботи для зменшення затримок в обслуговуванні Досить складно одночасно забезпечити равнодоступность і максимізувати загальну пропускну здатність

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

У планувальнику введення-виведення, з лімітом за часом із запитом повязано граничний час очікування (expiration time) За умовчанням цей момент часу дорівнює

500 мілісекунд в майбутньому для запитів читання і 5 секунд в майбутньому для запитів запису Планувальник вводу-виводу з лімітом за часом працює аналогічно планировщику Лінуса – він також підтримує черга запитів в відсортованому стані відповідно до фізичним розташуванням сектора на диску Ця черга називається відсортованій (sorted queue) Коли запит поміщається в відсортовану чергу, то deadlme-планувальник вводу-виводу виконує обєднання і вставку запитів так само, як це робиться в ліфтовому алгоритмі Лінуса4 Крім того, планувальник з лімітом за часом поміщає кожен запит і в другу чергу, в залежності від типу запиту Запити читання поміщаються в спеціальну чергу FIFO запитів читання, а запити записи-в чергу FIFO запитів запису У той час як звичайна черга відсортована за номером сектора на диску, дві черги FIFO (first-in first-out-першим надійшов, першим обслужений) упорядковано часу надходження запиту, так як нові запити завжди додаються в кінець черги При нормальній роботі deadline-планувальник вводу-виводу отримує запити з голови відсортованій черги і поміщає їх у чергу диспетчеризації Черга диспетчеризації відправляє запити жорсткого диску Це призводить до мінімізації кількості операцій пошуку

Джерело: Лав, Роберт Розробка ядра 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>

*

*