Відмінності між версіями «Тема 3. Дискове планування.»

Версія за 03:06, 9 січня 2012 (переглянути вихідний код) Nopasha (обговорення • внесок) ← Попереднє редагування		Поточна версія на 11:29, 9 січня 2012 (переглянути вихідний код) Nopasha (обговорення • внесок)
(не показано 17 проміжних версій цього учасника)
Рядок 1:		Рядок 1:
−	==Сучасний Linux- сервер: як планувати дискові ресурси==	+	==Дискове планування==
		+	===Діаграми часу дискової операції===
		+	{| border="1" class="standard"
		+	! Чекання пристрою
		+	! Чекання каналу
		+	! Пошук
		+	! Затримка
		+	! Передача даних
		+	|}
		+	===Позиціювання===
		+	Для того щоб виконати читання або запис, картридж спочатку розташовується над шуканою доріжкою, потім над початком шуканого сектору но цій доріжці.
−	''Від того, наскільки правильно буде врахований і cпрогнозирован зростання даних, розміщених на створюваному сервері, залежить в найпрямішому сенсі термін "життя" самого сервера! Але можна не займатися математичним пророцтвом збільшення об'єму інформації в мережі, а використати технології зберігання, що допускають оперативне масштабування і резервування.''	+	Час доступу - це час необхідний для позиціювання читання або запису.
−	===Постановка завдання===	+	* Для жорстких дисків:
		+	швидкість обертання: від 5400 до 10000 об/хв.
		+	затримка обертання: від 6мс до 10 мс.
		+	===Час обертання===
		+	<math>\Tau=\frac{b}{r*N}</math>
−	По-перше, що таке цикл експлуатації сервера. Вважатимемо таким термін від введення сервера в лад до його демонтажу, або до модернізації(upgrade) операційної системи або апаратного забезпечення. Перше зрозуміло, друге обгрунтую. Оскільки все, що далі описується, відноситься до області професійної діяльності, то всяка робота має грошовий еквівалент, і економія коштів приймається одним з головних критеріїв будь-якої професійної діяльності. Так і тут. Модернізація робиться не із-за раптом виниклої тяги системного адміністратора до новизни, а тому що в старій версії або на старому устаткуванні сервер далі працювати не може. Тобто невідповідність стала такою істотною, що вирішено витратити засоби на модернізацію. Ну а якщо так, то істотні зміни дозволяють рахувати сервер після модернізації вже іншим і відповідно до цього почати відлік нового циклу, тим більше що і операційна система, і устаткування сервера самі по собі мають життєвий цикл, який недоцільно перевищувати.	+	<math>\Tau </math>- час передачі даних
−	По-друге, навіщо треба збільшення відмовостійкості? Чому при вводі сервера в дію це не вважали необхідним, а ось з часом раптом стурбувалися? Вважатимемо, що зі збільшенням терміну експлуатації зростає об'єм внутрішніх даних сервера і тим самим збільшується його інформаційна і абсолютна цінність.	+	b - кількість байтівб що передаються
−	По-третє, після вищесказаного абсолютно очевидно, що зростання внутрішніх даних приводить до необхідності збільшення місткості зберігання рано чи пізно.	+	r - швидкість обертання
−	Перерахувавши позитивні якості, не забудемо згадати і негативні - ті, що позначені у формулюванні як "надмірні ресурси". Надмірним рахуватимемо все, що притягується лише для здійснення самої операції збільшення, поліпшення або модернізації. Наприклад, якщо для збільшення дискового простору потрібно буде не лише підключити новий диск, але ще і доведеться викинути старий, то такий обмін, що не компенсується, потрібно вважати "надмірним ресурсом". Також надмірними рахуватимемо усі витрати на подібні операції. Наприклад, якщо модифікацію можна здійснити без перерви в роботі, то це ідеал, інакше - ні. А на практиці там, де обговорюються не ідеальні, але реальні умови, чим менше ресурсів знадобиться для проведення операції, тим краще.	+	N - кількість байтів в доріжці
		+	===Середній час доступу===
−	Резюмуємо вищесказане. У усіх технологічних виборах слід віддавати перевагу тим способам і методам, які понизять вартість подальших перетворень і модифікацій.	+	<math>\Tau=\Tau +\frac{1}{2*r}+\frac{b}{r*N}</math>
		+	===Планування роботи з дисковими запам’ятовуючими пристроями===
		+	Для того, щоб отримати можливість доступу до конкретного запису даних, які розташовані на диску з головками, які переміщуються, в загальному випадку треба виконати декілька операцій:
		+	*Коретку треба встановити на відповідний циліндр і це є час пошуку циліндра;
		+	*Треба зачекати коли під головками опиниться та точка на диску з якої починається запис. Це час очікування запису;
		+	*Сам запис, який може мати довільний розмір, до повної доріжки повинен пройти під головкою і це час доступу або час передачі.
		+	Кожна з цих операцій пов’язана з механічним рухом і тому загальний час доступу до конкретного запису до 10 мс. І це все досить повільно в порівнчнні з роботою ЦП.
−	===Ієрархія рівнів представлення дискових даних===	+	[[Файл:0000001.png|frame]]
−	Сучасний Linux- сервер є багатофункціональним пристроєм, працюючим в мережі. Якщо абстрагуватися від його прикладного призначення і спробувати представити увесь спектр можливих рівнів і способів доступу до даних, то вийде велика схема, що нагадує багатошаровий пиріг. Ієрархію мережевого доступу до даних теж прийнято зображувати у вигляді багаторівневої схеми інкапсуляції. Тільки якщо мережева модель вже давно канонізована, то схема вкладеності рівнів доступу до дискових даних не має звичного вигляду, що допускає вільності в її уявленні. Отже, якщо усі доступні в SuSE Linux 10.0 технологій спробувати укласти в єдину схему, взаємозв'язок, що відбиває їх, і взаємодію, то вийде щось на зразок зображеного на мал. 1.	+	===Для чого потрібне планування роботи з дисками.===
−	[[Файл:1 image001.gif|frame|Малюнок 1. Схема ієрархії рівнів представлення дискових даних]]	+	В багатопрограмних системах одночасно виконується багато процесів, які можуть генерувати запити до дисків. Оскільки ці процеси роблять запити швидше ніж їх обслуговують дискові пристрої, то до кожного такого пристрою формується черга запитів. Можна ці запити обслуговувати в порядку їх надходження (FCFS). Це справедливий метод надання послуг, але коли частота запитів велика такий метод може призвести до затримок. Щоб звести до мінімуму цей час пошуку доцільно навести порядок в запитах до диску за яким небуть іншим принципом ніж FCFS. Цей порядок і називається плануванням роботи з диском. Планування вимагає аналізу запитів, які очікують в черзі для того щоб визначити найбільшефективний порядок їх обслуговування. Планування дискової пам’яті повинен аналізувати позиційні взаємозв’язки між запитами які очікують в черзі. Після чого черга запитів перебдовується таким чином, що їх використання виконується при мінімальних механічний переміщеннях.
−	Прокоментую цю схему. Хоча усі абревіатури і позначення є традиційними в Linux, розшифрую їх:	+	Маємо 2 найбільш поширений види планувань:
		+	#оптимізація планування за часом пошуку циліндра;
		+	#оптимізація планування за часом очікування запису.
−	n DISK - фізичний дисковий пристрій;	+	Оскільки час пошуку циліндрів перевищує час очікування записів, як правило на порядок, більшість алгоритмів планувань ставить своює метою мінімізацію часу пошуку циліндрів для деякої множини записів. А мінімізація часу очікування запису дає позитивний ефект при дуже великих навантаженнях.
−	n MD - так званий multiple device або програмний RAID;	+	===Цільові характеристики принципів планування.===
−	n LVM - віртуальний диск за технологією Logical Volume Manager;	+	При створенні алгоритмів планувань враховуються такі критерії:
		+	*пропускна здатність;
		+	*середній час відповіді;
		+	*розкид (дисперсія) відповіді в часі – це є характеристикою передбачувагості.
−	n DRB/iSCSI - мережевий диск за відповідною технологією;	+	Ці критерії направлені на покращення загальних швидкісних характеристик. Планування часто політшує загальну картину хоча і може дещо знизити швидкість обслуговування дейких запитів. Одним із важливих кількісних показників для оцінки цього явища може служити розкид відповіді в часі. Дисперсія – це міра того на скільки далеко значення індивідкальних елементів може відхилитись від середнього значення для цих елеметів. В зв’язку з цим ми використовуємо дисперсію, як показник передбаченості. Чим менша диперсія, тим краще передбачення. Необхідна така стратегія плануванняяка б мінімізувала дисперсію, інакше може виникнути та ситуація, що час обслуговування певних запитів н еможн абуде передбачити. Якби стратегія планування була направлена тільки  на досягнення максимальної пропускної здатності без одночасної мінімізації дисперсії, то система обробляла би тільки зручні для обслуговування записи, а деякі запити ігнорувала б повністю.
−	n EXT3... - рівень представлення, що відповідає файловим системам;	+	===Найбільш поширені стратегії оптимізації.===
−	n NFS... - рівень представлення, що відповідає мережевим файловим системам і протоколам, використовуваним для організації мережевого доступу до файлів.	+	====FCFS: Запити ослуговуються в порядку надходження.====
−	Кожен забарвлений прямокутник відділяє регіон, що включає технології відповідної категорії. Їх три:	+	[[Файл:0000002.png|frame]]
−	n SAS - пристрої, що фізично підключаються до сервера;	+	====SSTF: З найменшим часом пошуку обслуговується першим.====
−	n SAN - блокові пристрої, що підключаються по мережевих інтерфейсах;	+	[[Файл:0000003.png|frame]]
−	n NAS - файлові системи, доступні через мережу.	+	При переміщення головки наступним вибирається той запим, для якого необхідне мінімальне переміщення коретки. Прешим обслуговується запит з найменшим часом пошуку циліндра, якщо цей запит і не є першим в черзі. Тобто має місце дискримінація певних запитів. Звертання до диску виявляє тенденцію концентруватись. В результаті запити на самих внутрішніх або на самих зовнішніх доріжках можуть обслуговуватись значно гірше, ніж на середніх доріжках. Така стратегія має кращу пропускну здатність ніж 1-а і найкоротший час відповіді при помірних навантаженнях. Але має місце велика дисперсія і це не підходить для інтерактивних систем.
−	Усі перераховані на схемі технології можуть бути задіяні в межах одного серверного блоку або, точніше, одного хоста. Безумовно, необхідність їх використання повинна диктуватися сферою застосування. І ось тут для нашого обговорення буде важливо те, яку гнучкість в налаштуванні і модернізації забезпечують усі зображені елементи. Для цього розглянемо детальніше ту ж схему, але з точки зору операцій і їх взаємодії шляхом ескалації технологічних рівнів.	+	====SCAN – метод сканування====
−	Далі виходитимемо з припущення, що усі використовувані технології застосовуються до одного фізичного дискового пристрою. Це не виключає надалі використання додаткових дисків, але задає жорсткіші рамки варіантів вибору. Наприклад, під MD надалі розумітиметься виключно RAID1.	+	Каретка рухається над поверхнею диска, обслуговуючи всі запити, які зустрічаються на шляху. Каретка міняє напрям руху, якщо в біжучому напрямку більше нема запитів для обслуговування. Ця стратегія була розроблена спеціально для зменшення дискримінації крайніх доріг. Характеристики даної стратегії аналогічні попередній стратегії за винятком того, що вона обирає для обслуговування той запит, для якого має місце мінімальна відстань пошуку у вибраному напрямку. Ця стратегія є основою більшості практично-реалізованих стратегій планування дискової пам’яті. І хоча крайні доріжки обслуговуються не так часто, це краще, ніж метод SSTF.
−	===Діаграми переходів===	+	[[Файл:0000004.png|frame]]
−	Для того, щоб визначити ключові, або, в нашій термінології, " дорогі" технологічні елементи, побудуємо діаграму переходів в процесі можливих налаштувань від самого нижнього рівня DISK до самого верхнього NFS... Отримана діаграма представлена на мал. 2.	+	====N-Step SCAN – N-крокове сканування====
−	[[Файл:1 image002.gif|frame|Малюнок 2. Діаграма налаштувань]]	+	Каретка рухається над поверхнею в прямому і зворотному напрямках, але всі запити, які надійшли під час руху в одному напрямку, групуються і перешиковуються таким чином, щоб їх можна було якомога ефективніше обслуговувати під час зворотного ходу. Ця стратегія дає невелику дисперсію часу відповіді у порівнянні з іншими стратегіями. Вона виключає можливість безмежного відкладання обслуговування запитів, яке може виникнути у випадку надходження великої кількості запитів до біжучого циліндра. Ця стратегія передбачає запам’ятовування таких запитів для обслуговування при зворотному ході каретки.
−	Вузли відповідають технологічним рівням представлення даних, а стрілки означають можливі напрями в процесі налаштування сервера. Нумерація вузлів проставлена в порядку щонайдовшого маршруту налаштувань. Все очевидно і не потребує пояснень. А ось тепер повернемо стрілки у зворотному напрямі! Уявимо, що деякий крок налаштування виявився помилковим, але рішення про його відміну прийшло лише в процесі експлуатації, через деякий час. Наприклад, в процесі установки були послідовно пройдені етапи 1 DISK, 5 EXT3..., 6 NFS.... І через деякий час з'явилася необхідність перевести працюючу систему під LVM. Тобто потрібно послідовно перевести сервер по діаграмі налаштувань 6 NFS..., 5 EXT3... і потім у вузол 3 LVM. Після чого знову в поступальній ході по діаграмі налаштувань повернутися у вузол 6 NFS..., який відповідає повністю працездатному серверу. Другу діаграму назвемо діаграмою переробок. У ній все вектору змінили напрям на протилежне, і поряд з кожним з них додався коментар, що оцінює вартість переробки. Результат зображений на рис 3.	+	====C-SCAN – циклічне сканування====
−		+
−	[[Файл:1 image003.gif|frame|Малюнок 3. Діаграма переробок]]	+
−		+
−		+
−	Отже, усі можливі вартості переробок уклалися в чотири градації: втрата сервісу, відключення сервісу, умовно можливо, втрата даних. Наприклад, розглянемо можливі переробки для вузла файлових систем EXT3... По-перше, можна переразметить диск, на якому розміщена файлова система, - це умовно можлива операція, оскільки на диску повинне залишатися вільне місце для таких маніпуляцій. По-друге, можна перевести використовуваний диск в статус RAID1 - це умовно можлива операція, оскільки у разі наявності вільного місця у файловій системі для розміщення суперблоку операцію можна провести "на льоту". По-третє, можна перевести файлову систему під управління LVM - ця операція проводиться з втратою даних,  оскільки LVM використовує розміщення суперблоків в тілі робочих розділів так, що не представляється можливим виділити для цього єдиний простір. Ну і, нарешті, можна відключити від використовуваної файлової системи мережевий блоковий пристрій - ця операція призводить тільки до відключення самого сервісу і ні до чого серйознішому.	+
−		+
−	Таким чином, найсерйозніша ситуація складається навколо переробок, що вимагають установки LVM. Якщо підключення RAID або переразметка диска можуть бути проведені без резервного копіювання усіх даних в деяких випадках, то приміщення томів з даними під управління LVM зажадає 100% збереження усієї задіяної інформації. Тут можна зробити висновок, що саме LVM є тією критичною технологією, рішення про використання якої потрібно приймати на самому ранньому етапі планування дискових ресурсів.	+
−		+
−	===Таблиця операцій===	+
−		+
−	Спробуємо помістити усі дані з діаграм в таблицю 1. Ліворуч в стовпці 1 - початковий стан, згори у ряді 1 - кінцеве, в осередку на перетині відповідних станів вказана операція, що переводить початковий стан в кінцевий. Таким чином, в осередки лівої нижньої частини таблиці, розділеної діагоналлю, потраплять операції переробок і їх вартості, а в осередки правої верхньої частини потраплять операції налаштувань.	+
−		+
−	Тепер в цій таблиці помаранчевим кольором по вертикалі, тобто в цільових стовпцях, виділимо технології, що допускають оперативне масштабування, і салатним, також по вертикалі, - ті технології, що дозволяють організувати гаряче резервування за схемою RAID.	+
−		+
−	Таблиця 1. Операції і вартості	+
−		+
−		+
−	{| border="1" class="standard"	+
−	!	+
−	!DISK	+
−	!style="background:#CCFF00"|MD	+
−	!style="background:#FFCC00"|LVM	+
−	!style="background:#CCFF00"|DRB/iSCSI	+
−	!EXT3...	+
−	!NFS...	+
−	|-	+
−	!DISK	+
−	|Розбиття диска	+
−	|style="background:#CCFF00"|Створення MD і підключення	+
−	|style="background:#FFCC00"|Створення LVM і підключення	+
−	|style="background:#CCFF00"|Запуск drbd/ iscsid	+
−	|Розмітка fs і монтування	+
−	|	+
−	|-	+
−	!MD	+
−	|Умовно можлива міграція MD на інший розділ диска	+
−	|style="background:#CCFF00"|	+
−	|style="background:#FFCC00"|Створення LVM і підключення	+
−	|style="background:#CCFF00"|Запуск drbd/ iscsid	+
−	|Розмітка fs і монтування	+
−	|	+
−	|-	+
−	!LVM	+
−	|Умовно можлива міграція PV	+
−	|style="background:#CCFF00"|Умовно можливе переміщення PV всередину MD	+
−	|style="background:#FFCC00"|	+
−	|style="background:#CCFF00"|Запуск drbd/ iscsid	+
−	|Розмітка fs і монтування	+
−	|	+
−	|-	+
−	!DRB/iSCSI	+
−	|Умовно можлива міграція розділу DRB/iSCSI	+
−	|style="background:#CCFF00"|Умовно можливе переміщення розділу всередину MD	+
−	|style="background:#FFCC00"|Неможливо без повного резервного копіювання	+
−	|style="background:#CCFF00"|	+
−	|Розмітка fs і монтування	+
−	|	+
−	|-	+
−	!EXT3...	+
−	|Умовно можлива міграція FS	+
−	|style="background:#CCFF00"|Умовно можливе переміщення FS всередину MD	+
−	|style="background:#FFCC00"|Неможливо без повного резервного копіювання	+
−	|style="background:#CCFF00"|Відключення від мережевого блокового пристрою	+
−	|	+
−	|Запуск nfsd/ smbd	+
−	|-	+
−	!NFS...	+
−	|	+
−	|style="background:#CCFF00"|	+
−	|style="background:#FFCC00"|	+
−	|style="background:#CCFF00"|	+
−	|Відключення усіх споживачів і зупинка сервісу	+
−	|	+
−	|}	+
−	Якщо виходити з умови, що необхідно забезпечити масштабування місткостей в оперативному порядку, то вибір однозначний. Оскільки в попередньому розділі вже був зроблений висновок про те, що технологія LVM єдина, яка вимагає рішення про її застосування на самому ранньому етапі, то можна сказати, вибір зроблений - LVM неодмінно потрібно використати.	+	Каретка рухається в напрямку до внутрішньої доріжки. Якщо попереду більше нема запитів для обслуговування, каретка стрибком повертається до початку, обслуговує запит найближчий до зовнішньої доріжки, а потім знову рухається до внутрішньої доріжки. Ця стратегія виключає дискримінацію внутрішніх і зовнішніх доріжок. При просуванні від зовнішнього циліндра до внутрішнього, обслуговування запитів проводиться за стратегією найменшого часу пошуку. Записи, що надійшли під час біжучого прямого ходу, обслуговуються протягом наступного проходу. В результаті маємо дуже малу дисперсію часу відповіді.
−	Далі, у нас два кандидати для можливого збільшення відмовостійкості шляхом гарячого резервування. Безумовно, порівнювати RAID і мережеві блокові пристрої просто некоректно. Але у рамках даної моделі ми не враховуємо нічого, окрім можливості перенастроювати потрібний рівень представлення даних і наслідків такого перенастроювання. І наслідуючи цей принцип, виходить, що створення мережевого блокового пристрою на основі локального - це лише запуск відповідного сервісу, а перемикання локально підмонтованого диска на мережевий режим роботи без зміни його об'єму або розміщення теж не представляє особливої проблеми. Отже, з двох технологічних підходів, MD і DRB/iSCSI, будемо самими незручними в модифікації, і тому " найдорожчим", рахувати MD.	+	''Найбільш ефективна стратегія планування роботи дискового простору мала б мати два режими:''
		+	#при малих навантаженнях – SCAN;
		+	#при середніх і великих навантаженнях – C-SCAN.
		+	Стратегія C-SCAN з оптимізацією за часом очікування запитів найбільш ефективна при дуже великих навантаженнях.
−	На цьому етапі можна сформулювати перші принципи планування дискових ресурсів.	+	====Схема Ешенбаха (оптимізація за часом пошуку циліндра)====
−	Принцип 1. Слідує, по можливості, перемкнути усі розмічені розділи жорсткого диска в режим роботи програмного RAID, хай і неповного, що дозволить надалі при необхідності перевести їх в режим гарячого резервування.	+	В схемі Ешенбаха каретка рухається як в способі C-SCAN, але при обслуговуванні кожного циліндра виконується доступ лише до одної повної доріжки, не зважаючи на наявність ще запитів до цього циліндра.
		+	Передбачається перешикування запитів для обслуговування в рамках одного циліндра з врахуванням кутового положення запитів, але якщо 2 (два) запити відносяться до таких секторів одного циліндра, що перекриваються (зверху і знизу), то тільки один з них обслуговується при біжучому ході каретки.
−	Принцип 2. Слідує, по можливості, об'єднати усі створені фізичні томи під управлінням LVM - для того, щоб надалі, при необхідності, легко маніпулювати об'ємом використовуваних логічних томів.	+	[[Файл:0000005.png|frame]]
−	Звертаю увагу на уточнення "по можливості". Обговорення цих " можливостей", а також все, що стосується стратегії розбиття на розділи, залишимо для другої частини цієї статті. Зараз просто врахуємо цю обмовку і просто спробуємо оцінити ефект від наслідування заявлених виведень, як принципам планування дискових ресурсів.	+	====Оптимізація за часом очікування записів====
−	оригінальне джерело і продовження статті [http://www.opennet.ru/docs/RUS/disk_plan/ тут]	+	В умовах великих навантажень ймовірність декількох одночасних звертань до конкретного циліндра зростає, тому робиться доцільним виконувати оптимізацію і за часом очікування запитів. Як правило, використовується одна стратегія SLTF – за найменшим часом очікування обслуговується перший (аналог SSTF).
		+	Коли каретка підводиться на конкретний циліндр, може виявитись, що багато запитів очікують звертання до різних доріжок цього циліндра. Стратегія SLTF аналізує всі ці запити і першим обслуговується запит з мінімальним часом очікування.
		+	Ця стратегія дуже близька до теоретично оптимальної і при цьому її досить легко реалізувати. Запити будуть обслуговуватись у вказаній послідовності незалежно від того, в якому порядку вони надійшли.

---

Поточна версія на 11:29, 9 січня 2012

Дискове планування

Діаграми часу дискової операції

Чекання пристрою	Чекання каналу	Пошук	Затримка	Передача даних

Позиціювання

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

Час доступу - це час необхідний для позиціювання читання або запису.

• Для жорстких дисків:

швидкість обертання: від 5400 до 10000 об/хв.
затримка обертання: від 6мс до 10 мс.

Час обертання

Неможливо розібрати вираз (невідома помилка): \Tau=\frac{b}{r*N}

Неможливо розібрати вираз (невідома помилка): \Tau - час передачі даних

b - кількість байтівб що передаються

r - швидкість обертання

N - кількість байтів в доріжці

Середній час доступу

Неможливо розібрати вираз (невідома помилка): \Tau=\Tau +\frac{1}{2*r}+\frac{b}{r*N}

Планування роботи з дисковими запам’ятовуючими пристроями

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

• Коретку треба встановити на відповідний циліндр і це є час пошуку циліндра;
• Треба зачекати коли під головками опиниться та точка на диску з якої починається запис. Це час очікування запису;
• Сам запис, який може мати довільний розмір, до повної доріжки повинен пройти під головкою і це час доступу або час передачі.

Кожна з цих операцій пов’язана з механічним рухом і тому загальний час доступу до конкретного запису до 10 мс. І це все досить повільно в порівнчнні з роботою ЦП.

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

В багатопрограмних системах одночасно виконується багато процесів, які можуть генерувати запити до дисків. Оскільки ці процеси роблять запити швидше ніж їх обслуговують дискові пристрої, то до кожного такого пристрою формується черга запитів. Можна ці запити обслуговувати в порядку їх надходження (FCFS). Це справедливий метод надання послуг, але коли частота запитів велика такий метод може призвести до затримок. Щоб звести до мінімуму цей час пошуку доцільно навести порядок в запитах до диску за яким небуть іншим принципом ніж FCFS. Цей порядок і називається плануванням роботи з диском. Планування вимагає аналізу запитів, які очікують в черзі для того щоб визначити найбільшефективний порядок їх обслуговування. Планування дискової пам’яті повинен аналізувати позиційні взаємозв’язки між запитами які очікують в черзі. Після чого черга запитів перебдовується таким чином, що їх використання виконується при мінімальних механічний переміщеннях.

Маємо 2 найбільш поширений види планувань:

1. оптимізація планування за часом пошуку циліндра;
2. оптимізація планування за часом очікування запису.

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

Цільові характеристики принципів планування.

При створенні алгоритмів планувань враховуються такі критерії:

• пропускна здатність;
• середній час відповіді;
• розкид (дисперсія) відповіді в часі – це є характеристикою передбачувагості.

Ці критерії направлені на покращення загальних швидкісних характеристик. Планування часто політшує загальну картину хоча і може дещо знизити швидкість обслуговування дейких запитів. Одним із важливих кількісних показників для оцінки цього явища може служити розкид відповіді в часі. Дисперсія – це міра того на скільки далеко значення індивідкальних елементів може відхилитись від середнього значення для цих елеметів. В зв’язку з цим ми використовуємо дисперсію, як показник передбаченості. Чим менша диперсія, тим краще передбачення. Необхідна така стратегія плануванняяка б мінімізувала дисперсію, інакше може виникнути та ситуація, що час обслуговування певних запитів н еможн абуде передбачити. Якби стратегія планування була направлена тільки на досягнення максимальної пропускної здатності без одночасної мінімізації дисперсії, то система обробляла би тільки зручні для обслуговування записи, а деякі запити ігнорувала б повністю.

Найбільш поширені стратегії оптимізації.

FCFS: Запити ослуговуються в порядку надходження.

SSTF: З найменшим часом пошуку обслуговується першим.

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

SCAN – метод сканування

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

N-Step SCAN – N-крокове сканування

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

C-SCAN – циклічне сканування

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

Найбільш ефективна стратегія планування роботи дискового простору мала б мати два режими:

1. при малих навантаженнях – SCAN;
2. при середніх і великих навантаженнях – C-SCAN.

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

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

В схемі Ешенбаха каретка рухається як в способі C-SCAN, але при обслуговуванні кожного циліндра виконується доступ лише до одної повної доріжки, не зважаючи на наявність ще запитів до цього циліндра. Передбачається перешикування запитів для обслуговування в рамках одного циліндра з врахуванням кутового положення запитів, але якщо 2 (два) запити відносяться до таких секторів одного циліндра, що перекриваються (зверху і знизу), то тільки один з них обслуговується при біжучому ході каретки.

Оптимізація за часом очікування записів

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