Оптимізація пошуку циліндру
Цільові характеристики принципів планування
Для розділення принципів планування на категорії існують і деякі інші критерії:
1) Пропускна здатність.
2) Середній час відповіді.
3) Розкид, або дисперсія відповіді в часі (тобто передбачуваність).
Ці критерії направлені на покращення загальних швидкісних характеристик, можливо і за рахунок деяких індивідуальних запитів. Плануванння часто поліпшує загальну картину, хоча і дещо знижує швидкість обслуговування певних запитів.
Одним з важливих кількісних показників для оцінки цього явища може служити розкид, або дисперсія відповідей в часі.
Дисперсія – це міра того, наскільки далеко значення індивідуальних елементів може відхилятись від середнього значення цих елементів.
В зв’язку з чим ми використовуємо дисперсію, як показник передбачуваності – чим менша дисперсія, тим більша передбачуваність.
Нам необхідна така стратегія планування, яка б мінімізувала дисперсію. Інакше може статися таке, що час обслуговування певних запитів просто не можна буде передбачити. (Неприпустимо, наприклад, в системі резервування авіаквитків). Якби стратегія планування була направлена тільки на досягнення максимальної пропускної здатності без одночасної мінімізації дисперсії, система обробляла би тільки зручні для обслуговування запити, а деякі ігнорувала би повністю.
Найбільш поширені стратегії оптимізації.
1. FCFS – запити обслуговуються в порядку надходження.
2. SSTF – (Shortest Seek Time First) („з найменшим часом пошуку - першим”).
Рис. __
При позиціонуванні каретки з магнітними головками наступним вибирається запит, для якого необхідне мінімальне переміщення каретки. Першим обслуговується запит з найменшим часом пошуку циліндра, якщо навіть цей запит не є першим в черзі.
Має місце різка дискримінація певних запитів. Звернення до диску виявляють тенденцію концентруватись, в результаті запити до самих внутрішніх, або самих зовнішніх доріжок можуть обслуговуватись значно гірше, ніж до середніх доріжок.
Краща пропускна здатність, ніж FCFS, і найкращий середній час відповіді при помірних навантаженнях.
Велика дисперсія, тобто погана передбачуваність, не підходить для інтегрованих систем, але добра в пакетних системах, де основне – пропускна здатність.
3. SCAN (сканування). Каретка з головками рухається туди і назад над поверхнею, обслуговуючи всі запити, що зустрічаються на шляху. Каретка змінює напрям руху, якщо в біжучому напрямку більше немає запитів для обслуговування.
Рис. __
Стратегія розроблена для зменшення дискримінації крайніх доріжок.
Аналогічна SSTF за винятком того, що вона вибирає для обслуговування той запит, для якого є характерною мінімальна відстань пошуку в привілейованому напрямку.
Цей принцип (SCAN) є основою більшості практично реалізованих стратегій планування роботи з дисковою пам’яттю.
На крайніх доріжках головки бувають не так часто, як на середніх, але це краще, ніж дискримінація в SSTF.
4. N-Step SCAN (N - крокове сканування). Модифікація SCAN.
Каретка з головками рухається туди і назад, але всі запити, що поступають під час ходу в одному напрямку, групуються та перешиковуються таким чином, щоб їх можна було найбільш ефективно обслуговувати під час зворотнього ходу.
Рис. __
Найважливіша риса - невелика дисперсія часу відповіді в порівнянні з принципом SSTF або звичайним варіантом SCAN.
Ця стратегія виключає можливість безмежного відкладання, яке звичайно виникає у випадку надходження великої кількості запитів на звертання до біжучого циліндра. Вона передбачає запам’ятовування тих запитів, що надійшли при зворотному ході каретки.
5. С-SCAN (циклічне сканування).
Каретка рухається в напрямку до внутрішньої доріжки. Якщо попереду більше нема запитів для обслуговування, каретка стрибком повертає до початку, обслуговує запит, найближчий до зовнішньої доріжки, а потім обслуговує рух до середини.
Рис. __
Ця стратегія виключає дискримінацію у відношенні до внутрішніх або зовнішніх циліндрів. При просуванні від зовнішнього циліндру до внутрішнього, обслуговування запитів виконується за найкоротшим часу пошуку.
Запити, що надходять під час біжучого прямого ходу, обслуговується при наступному проході. Маємо дуже малу дисперсію відповідей в часі.
Найбільш ефективна стратегія планування роботи дискової пам’яті мала б мати два режими:
- при малих навантаженнях – SCAN;
- при середніх і великих і навантаженнях - С-SCAN.
С-SCAN з оптимізацією за часом очікування записів найбільш ефективна при дуже великих навантаженнях.
6. Схема Еменбака.
Каретка рухається циклічно, як в способі С-SCAN. Але при обслуговуванні кожного циліндру виконується доступ тільки до одної повної доріжки інформації незалежно від наявності іще запитів для цього циліндра.
Передбачається перешиковування запитів для обслування в рамках одного циліндру з врахуванням кутового положення записів, але якщо два запити відносяться до секторів одного циліндру, що перекриваються, то тільки один з них обслуговується при біжучому ході каретки.
Схема С-SCAN з оптимізацією за часом очікування запитів більш ефективна в умовах дуже великих навантажень.