Відмінності між версіями «Тема 3. Дискове планування.»
Nopasha (обговорення • внесок) |
Nopasha (обговорення • внесок) |
||
| (не показано 19 проміжних версій цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | == | + | ==Дискове планування== |
| + | ===Діаграми часу дискової операції=== | ||
| + | {| border="1" class="standard" | ||
| + | ! Чекання пристрою | ||
| + | ! Чекання каналу | ||
| + | ! Пошук | ||
| + | ! Затримка | ||
| + | ! Передача даних | ||
| + | |} | ||
| + | ===Позиціювання=== | ||
| + | Для того щоб виконати читання або запис, картридж спочатку розташовується над шуканою доріжкою, потім над початком шуканого сектору но цій доріжці. | ||
| − | + | Час доступу - це час необхідний для позиціювання читання або запису. | |
| − | === | + | * Для жорстких дисків: |
| + | швидкість обертання: від 5400 до 10000 об/хв. | ||
| + | затримка обертання: від 6мс до 10 мс. | ||
| + | ===Час обертання=== | ||
| + | <math>\Tau=\frac{b}{r*N}</math> | ||
| − | + | <math>\Tau </math>- час передачі даних | |
| − | + | b - кількість байтівб що передаються | |
| − | + | r - швидкість обертання | |
| − | + | N - кількість байтів в доріжці | |
| + | ===Середній час доступу=== | ||
| − | + | <math>\Tau=\Tau +\frac{1}{2*r}+\frac{b}{r*N}</math> | |
| + | ===Планування роботи з дисковими запам’ятовуючими пристроями=== | ||
| + | Для того, щоб отримати можливість доступу до конкретного запису даних, які розташовані на диску з головками, які переміщуються, в загальному випадку треба виконати декілька операцій: | ||
| + | *Коретку треба встановити на відповідний циліндр і це є час пошуку циліндра; | ||
| + | *Треба зачекати коли під головками опиниться та точка на диску з якої починається запис. Це час очікування запису; | ||
| + | *Сам запис, який може мати довільний розмір, до повної доріжки повинен пройти під головкою і це час доступу або час передачі. | ||
| + | Кожна з цих операцій пов’язана з механічним рухом і тому загальний час доступу до конкретного запису до 10 мс. І це все досить повільно в порівнчнні з роботою ЦП. | ||
| − | + | [[Файл:0000001.png|frame]] | |
| − | + | ===Для чого потрібне планування роботи з дисками.=== | |
| − | + | В багатопрограмних системах одночасно виконується багато процесів, які можуть генерувати запити до дисків. Оскільки ці процеси роблять запити швидше ніж їх обслуговують дискові пристрої, то до кожного такого пристрою формується черга запитів. Можна ці запити обслуговувати в порядку їх надходження (FCFS). Це справедливий метод надання послуг, але коли частота запитів велика такий метод може призвести до затримок. Щоб звести до мінімуму цей час пошуку доцільно навести порядок в запитах до диску за яким небуть іншим принципом ніж FCFS. Цей порядок і називається плануванням роботи з диском. Планування вимагає аналізу запитів, які очікують в черзі для того щоб визначити найбільшефективний порядок їх обслуговування. Планування дискової пам’яті повинен аналізувати позиційні взаємозв’язки між запитами які очікують в черзі. Після чого черга запитів перебдовується таким чином, що їх використання виконується при мінімальних механічний переміщеннях. | |
| − | + | Маємо 2 найбільш поширений види планувань: | |
| + | #оптимізація планування за часом пошуку циліндра; | ||
| + | #оптимізація планування за часом очікування запису. | ||
| − | + | Оскільки час пошуку циліндрів перевищує час очікування записів, як правило на порядок, більшість алгоритмів планувань ставить своює метою мінімізацію часу пошуку циліндрів для деякої множини записів. А мінімізація часу очікування запису дає позитивний ефект при дуже великих навантаженнях. | |
| − | + | ===Цільові характеристики принципів планування.=== | |
| − | + | При створенні алгоритмів планувань враховуються такі критерії: | |
| + | *пропускна здатність; | ||
| + | *середній час відповіді; | ||
| + | *розкид (дисперсія) відповіді в часі – це є характеристикою передбачувагості. | ||
| − | + | Ці критерії направлені на покращення загальних швидкісних характеристик. Планування часто політшує загальну картину хоча і може дещо знизити швидкість обслуговування дейких запитів. Одним із важливих кількісних показників для оцінки цього явища може служити розкид відповіді в часі. Дисперсія – це міра того на скільки далеко значення індивідкальних елементів може відхилитись від середнього значення для цих елеметів. В зв’язку з цим ми використовуємо дисперсію, як показник передбаченості. Чим менша диперсія, тим краще передбачення. Необхідна така стратегія плануванняяка б мінімізувала дисперсію, інакше може виникнути та ситуація, що час обслуговування певних запитів н еможн абуде передбачити. Якби стратегія планування була направлена тільки на досягнення максимальної пропускної здатності без одночасної мінімізації дисперсії, то система обробляла би тільки зручні для обслуговування записи, а деякі запити ігнорувала б повністю. | |
| − | + | ===Найбільш поширені стратегії оптимізації.=== | |
| − | + | ====FCFS: Запити ослуговуються в порядку надходження.==== | |
| − | + | [[Файл:0000002.png|frame]] | |
| − | + | ====SSTF: З найменшим часом пошуку обслуговується першим.==== | |
| − | + | [[Файл:0000003.png|frame]] | |
| − | + | При переміщення головки наступним вибирається той запим, для якого необхідне мінімальне переміщення коретки. Прешим обслуговується запит з найменшим часом пошуку циліндра, якщо цей запит і не є першим в черзі. Тобто має місце дискримінація певних запитів. Звертання до диску виявляє тенденцію концентруватись. В результаті запити на самих внутрішніх або на самих зовнішніх доріжках можуть обслуговуватись значно гірше, ніж на середніх доріжках. Така стратегія має кращу пропускну здатність ніж 1-а і найкоротший час відповіді при помірних навантаженнях. Але має місце велика дисперсія і це не підходить для інтерактивних систем. | |
| − | + | ====SCAN – метод сканування==== | |
| − | + | Каретка рухається над поверхнею диска, обслуговуючи всі запити, які зустрічаються на шляху. Каретка міняє напрям руху, якщо в біжучому напрямку більше нема запитів для обслуговування. Ця стратегія була розроблена спеціально для зменшення дискримінації крайніх доріг. Характеристики даної стратегії аналогічні попередній стратегії за винятком того, що вона обирає для обслуговування той запит, для якого має місце мінімальна відстань пошуку у вибраному напрямку. Ця стратегія є основою більшості практично-реалізованих стратегій планування дискової пам’яті. І хоча крайні доріжки обслуговуються не так часто, це краще, ніж метод SSTF. | |
| − | + | [[Файл:0000004.png|frame]] | |
| − | + | ====N-Step SCAN – N-крокове сканування==== | |
| − | + | Каретка рухається над поверхнею в прямому і зворотному напрямках, але всі запити, які надійшли під час руху в одному напрямку, групуються і перешиковуються таким чином, щоб їх можна було якомога ефективніше обслуговувати під час зворотного ходу. Ця стратегія дає невелику дисперсію часу відповіді у порівнянні з іншими стратегіями. Вона виключає можливість безмежного відкладання обслуговування запитів, яке може виникнути у випадку надходження великої кількості запитів до біжучого циліндра. Ця стратегія передбачає запам’ятовування таких запитів для обслуговування при зворотному ході каретки. | |
| − | + | ====C-SCAN – циклічне сканування==== | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | === | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | Якщо | + | Каретка рухається в напрямку до внутрішньої доріжки. Якщо попереду більше нема запитів для обслуговування, каретка стрибком повертається до початку, обслуговує запит найближчий до зовнішньої доріжки, а потім знову рухається до внутрішньої доріжки. Ця стратегія виключає дискримінацію внутрішніх і зовнішніх доріжок. При просуванні від зовнішнього циліндра до внутрішнього, обслуговування запитів проводиться за стратегією найменшого часу пошуку. Записи, що надійшли під час біжучого прямого ходу, обслуговуються протягом наступного проходу. В результаті маємо дуже малу дисперсію часу відповіді. |
| − | + | ''Найбільш ефективна стратегія планування роботи дискового простору мала б мати два режими:'' | |
| + | #при малих навантаженнях – SCAN; | ||
| + | #при середніх і великих навантаженнях – C-SCAN. | ||
| + | Стратегія C-SCAN з оптимізацією за часом очікування запитів найбільш ефективна при дуже великих навантаженнях. | ||
| − | + | ====Схема Ешенбаха (оптимізація за часом пошуку циліндра)==== | |
| − | + | В схемі Ешенбаха каретка рухається як в способі C-SCAN, але при обслуговуванні кожного циліндра виконується доступ лише до одної повної доріжки, не зважаючи на наявність ще запитів до цього циліндра. | |
| + | Передбачається перешикування запитів для обслуговування в рамках одного циліндра з врахуванням кутового положення запитів, але якщо 2 (два) запити відносяться до таких секторів одного циліндра, що перекриваються (зверху і знизу), то тільки один з них обслуговується при біжучому ході каретки. | ||
| − | + | [[Файл:0000005.png|frame]] | |
| − | + | ====Оптимізація за часом очікування записів==== | |
| − | + | В умовах великих навантажень ймовірність декількох одночасних звертань до конкретного циліндра зростає, тому робиться доцільним виконувати оптимізацію і за часом очікування запитів. Як правило, використовується одна стратегія SLTF – за найменшим часом очікування обслуговується перший (аналог SSTF). | |
| + | Коли каретка підводиться на конкретний циліндр, може виявитись, що багато запитів очікують звертання до різних доріжок цього циліндра. Стратегія SLTF аналізує всі ці запити і першим обслуговується запит з мінімальним часом очікування. | ||
| + | Ця стратегія дуже близька до теоретично оптимальної і при цьому її досить легко реалізувати. Запити будуть обслуговуватись у вказаній послідовності незалежно від того, в якому порядку вони надійшли. | ||
Поточна версія на 11:29, 9 січня 2012
Зміст
- 1 Дискове планування
- 1.1 Діаграми часу дискової операції
- 1.2 Позиціювання
- 1.3 Час обертання
- 1.4 Середній час доступу
- 1.5 Планування роботи з дисковими запам’ятовуючими пристроями
- 1.6 Для чого потрібне планування роботи з дисками.
- 1.7 Цільові характеристики принципів планування.
- 1.8 Найбільш поширені стратегії оптимізації.
- 1.8.1 FCFS: Запити ослуговуються в порядку надходження.
- 1.8.2 SSTF: З найменшим часом пошуку обслуговується першим.
- 1.8.3 SCAN – метод сканування
- 1.8.4 N-Step SCAN – N-крокове сканування
- 1.8.5 C-SCAN – циклічне сканування
- 1.8.6 Схема Ешенбаха (оптимізація за часом пошуку циліндра)
- 1.8.7 Оптимізація за часом очікування записів
Дискове планування
Діаграми часу дискової операції
| Чекання пристрою | Чекання каналу | Пошук | Затримка | Передача даних |
|---|
Позиціювання
Для того щоб виконати читання або запис, картридж спочатку розташовується над шуканою доріжкою, потім над початком шуканого сектору но цій доріжці.
Час доступу - це час необхідний для позиціювання читання або запису.
- Для жорстких дисків:
швидкість обертання: від 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 найбільш поширений види планувань:
- оптимізація планування за часом пошуку циліндра;
- оптимізація планування за часом очікування запису.
Оскільки час пошуку циліндрів перевищує час очікування записів, як правило на порядок, більшість алгоритмів планувань ставить своює метою мінімізацію часу пошуку циліндрів для деякої множини записів. А мінімізація часу очікування запису дає позитивний ефект при дуже великих навантаженнях.
Цільові характеристики принципів планування.
При створенні алгоритмів планувань враховуються такі критерії:
- пропускна здатність;
- середній час відповіді;
- розкид (дисперсія) відповіді в часі – це є характеристикою передбачувагості.
Ці критерії направлені на покращення загальних швидкісних характеристик. Планування часто політшує загальну картину хоча і може дещо знизити швидкість обслуговування дейких запитів. Одним із важливих кількісних показників для оцінки цього явища може служити розкид відповіді в часі. Дисперсія – це міра того на скільки далеко значення індивідкальних елементів може відхилитись від середнього значення для цих елеметів. В зв’язку з цим ми використовуємо дисперсію, як показник передбаченості. Чим менша диперсія, тим краще передбачення. Необхідна така стратегія плануванняяка б мінімізувала дисперсію, інакше може виникнути та ситуація, що час обслуговування певних запитів н еможн абуде передбачити. Якби стратегія планування була направлена тільки на досягнення максимальної пропускної здатності без одночасної мінімізації дисперсії, то система обробляла би тільки зручні для обслуговування записи, а деякі запити ігнорувала б повністю.
Найбільш поширені стратегії оптимізації.
FCFS: Запити ослуговуються в порядку надходження.
SSTF: З найменшим часом пошуку обслуговується першим.
При переміщення головки наступним вибирається той запим, для якого необхідне мінімальне переміщення коретки. Прешим обслуговується запит з найменшим часом пошуку циліндра, якщо цей запит і не є першим в черзі. Тобто має місце дискримінація певних запитів. Звертання до диску виявляє тенденцію концентруватись. В результаті запити на самих внутрішніх або на самих зовнішніх доріжках можуть обслуговуватись значно гірше, ніж на середніх доріжках. Така стратегія має кращу пропускну здатність ніж 1-а і найкоротший час відповіді при помірних навантаженнях. Але має місце велика дисперсія і це не підходить для інтерактивних систем.
SCAN – метод сканування
Каретка рухається над поверхнею диска, обслуговуючи всі запити, які зустрічаються на шляху. Каретка міняє напрям руху, якщо в біжучому напрямку більше нема запитів для обслуговування. Ця стратегія була розроблена спеціально для зменшення дискримінації крайніх доріг. Характеристики даної стратегії аналогічні попередній стратегії за винятком того, що вона обирає для обслуговування той запит, для якого має місце мінімальна відстань пошуку у вибраному напрямку. Ця стратегія є основою більшості практично-реалізованих стратегій планування дискової пам’яті. І хоча крайні доріжки обслуговуються не так часто, це краще, ніж метод SSTF.
N-Step SCAN – N-крокове сканування
Каретка рухається над поверхнею в прямому і зворотному напрямках, але всі запити, які надійшли під час руху в одному напрямку, групуються і перешиковуються таким чином, щоб їх можна було якомога ефективніше обслуговувати під час зворотного ходу. Ця стратегія дає невелику дисперсію часу відповіді у порівнянні з іншими стратегіями. Вона виключає можливість безмежного відкладання обслуговування запитів, яке може виникнути у випадку надходження великої кількості запитів до біжучого циліндра. Ця стратегія передбачає запам’ятовування таких запитів для обслуговування при зворотному ході каретки.
C-SCAN – циклічне сканування
Каретка рухається в напрямку до внутрішньої доріжки. Якщо попереду більше нема запитів для обслуговування, каретка стрибком повертається до початку, обслуговує запит найближчий до зовнішньої доріжки, а потім знову рухається до внутрішньої доріжки. Ця стратегія виключає дискримінацію внутрішніх і зовнішніх доріжок. При просуванні від зовнішнього циліндра до внутрішнього, обслуговування запитів проводиться за стратегією найменшого часу пошуку. Записи, що надійшли під час біжучого прямого ходу, обслуговуються протягом наступного проходу. В результаті маємо дуже малу дисперсію часу відповіді.
Найбільш ефективна стратегія планування роботи дискового простору мала б мати два режими:
- при малих навантаженнях – SCAN;
- при середніх і великих навантаженнях – C-SCAN.
Стратегія C-SCAN з оптимізацією за часом очікування запитів найбільш ефективна при дуже великих навантаженнях.
Схема Ешенбаха (оптимізація за часом пошуку циліндра)
В схемі Ешенбаха каретка рухається як в способі C-SCAN, але при обслуговуванні кожного циліндра виконується доступ лише до одної повної доріжки, не зважаючи на наявність ще запитів до цього циліндра. Передбачається перешикування запитів для обслуговування в рамках одного циліндра з врахуванням кутового положення запитів, але якщо 2 (два) запити відносяться до таких секторів одного циліндра, що перекриваються (зверху і знизу), то тільки один з них обслуговується при біжучому ході каретки.
Оптимізація за часом очікування записів
В умовах великих навантажень ймовірність декількох одночасних звертань до конкретного циліндра зростає, тому робиться доцільним виконувати оптимізацію і за часом очікування запитів. Як правило, використовується одна стратегія SLTF – за найменшим часом очікування обслуговується перший (аналог SSTF). Коли каретка підводиться на конкретний циліндр, може виявитись, що багато запитів очікують звертання до різних доріжок цього циліндра. Стратегія SLTF аналізує всі ці запити і першим обслуговується запит з мінімальним часом очікування. Ця стратегія дуже близька до теоретично оптимальної і при цьому її досить легко реалізувати. Запити будуть обслуговуватись у вказаній послідовності незалежно від того, в якому порядку вони надійшли.
