Копитко М.Ф. Основи інформаційних технологій (на укр. языке)

Подождите немного. Документ загружается.

• Недолік: не може оптимізувати час виконання засто-

сувань типу (ІІ), де режим використання диска неперед-

бачений.

Використання декількох дискових пристроїв:

• Перевага: збільшує швидкість обслуговування запитів

на читання/запис дискових даних для застосувань обох

типів.

• Проблема: запити на читання/запис даних, які

передбачають звернення до одного і того ж диска, не

можна виконати водночас, отож коефіцієнт підвищення

продуктивності може виявитися нижчим, ніж кількість

дисків.

• Недолік: вартість декількох дискових пристрої вища,

ніж вартість одного пристрою тієї ж сумарної місткості.

Створення дзеркальних копій дисків:

• Перевага: збільшує швидкість обслуговування запитів

на читання/запис дискових даних для застосувань обох

типів; не спричинює проблеми зниження продуктив-

ності, притаманної для використання декількох «звичай-

них» (не «дзеркальних») дисків.

• Перевага: забезпечує підвищення ступеня надійності

зберігання даних.

• Недолік: при підвищеній вартості декількох дискових

пристроїв фактично використовується об’єм одного з

них.

Впорядкування дискових операцій за допомогою

алгоритму ліфта:

• Перевага: скорочує середній час зчитування/запису

блоків у ситуаціях, коли порядок запитів до диска непе-

редбачуваний.

• Проблема: алгоритм проявляє найбільшу ефективність у

тих випадках, коли існує безліч неопрацьованих запитів;

однак у цьому випадку зростає середній час очікування

на обслуговування кожного запиту.

Попереднє зчитування і крупномаштабна буферезація

даних:

• Перевага: зменшує загальний час виконання дискових

операцій, якщо порядок зчитування/запису даних

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

від властивостей самих даних (як при виконанні другої

фази алгоритму TPMMS).

• Недолік: вимагає нарощування об’єму оперативної

пам’яті для створення додаткових буферів; не надає

суттєвої вигоди, якщо потік запитів до диска

випадковий.

Вправи для опрацювання

Вправа 8. Припустимо, що необхідно впорядкувати процес

обробки запитів (перелічених на рис. 13) до дискового приводу

моделі «Soaring 747» за умови, що у початковий момент часу блок

головок розміщений навпроти циліндра з номером 8 000.

Побудуйте розклад обслуговування запитів:

а) згідно з алгоритмом ліфта (початковим напрямом

переміщення блока головок можна обрати будь-який);

б) за стратегією «першим прийшов − першим обслуго-

вується».

Вправа 9. Нехай два дискових приводи «Soaring 747» вико-

ристовують для зберігання дзеркальних копій даних. Припустимо,

що замість того, щоб блоки даних могли зчитуватися з будь-якого

диска, головки першого диска переміщаються тільки внутрішньою

половиною циліндрів, а головки другого диска − зовнішньою.

Зважаючи на те, що запити на читання адресовані до випадкових

блоків, дайте відповіді на такі запитання:

1. Яким є середній час опрацювання одного запиту?

2. Наскільки відрізняється середній час читання блока

у випадку, коли зазначене обмеження, що стосується

можливості переміщення блоків головок дзеркальних

дисків, зняте?

3. Які недоліки, зумовлені накладанням обмеження,

Ви можете назвати?

Номер циліндра Момент надходження (мс)

2000 0

12000 1

1000 10

10000 20

Рис. 13. Дані до вправи 8

Вправа 10. Якщо необхідно опрацювати запити на читання k

блоків, які випадково розподілені в межах деякого циліндра, то

який середній час обертання, необхідний для зчитування цих

блоків?

Тема 6. Відмови дискових пристроїв

У цій і наступній темах ми розглянемо ситуації, пов’язані з

відмовами дискових приводів, і способи подолання можливих

наслідків. Нижче перелічені різні критерії відмов, класифіковані у

порядку зростання ступеня їхньої важкості.

1. Періодична відмова – виникає періодично і виражається в

тому, що одна спроба читання/запису сектора виявляється

безуспішною, проте за умови її повторення операцію

вдається виконати.

2. Відмова запису – часто виникає унаслідок збою енер-

гоживлення в момент виконання операції запису сектора і

проявляється у неможливості запису інформації та

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

3. Руйнування носія – частина сектора стає непридатною, отож

операцію зчитування даних із сектора не можна виконати за

жодних умов і незалежно від кількості спроб.

4. Цілковита відмова диска – раптова поломка, унаслідок якої

подальша експлуатація пристрою стає неможливою.

Отож зупинимося на простій моделі відмов дисків, розглянемо

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

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

які застерігають від можливості втрати даних під час відмови

запису і руйнування носія.

6.1. Періодичні відмови

Сектори диска, зазвичай, містять додаткові надлишкові біти.

Їхні значення дають змогу визначити коректність інформації,

зчитаної з сектора або записаної в сектор.

За однією зі зручних моделей операцій зчитування дискових

даних вважають, що функція читання повертає пару (w, s) значень,

де w – власне дані, а s – біт індикації стану (status bit), який

засвідчує, чи успішний результат операції, тобто чи w правильно

відображає сектор. У випадку періодичних відмов функція читання

може повертати «хибний» біт індикації стану декілька разів. Якщо

ж повторювати операцію тривалий час (звичайна межа – до 100

разів), ймовірно, що функція все-таки поверне «істинний» біт, який

підтвердить коректність зчитаних даних. Хоча можлива ситуація,

коли біт індикації містить значення «істина», а зчитані дані

насправді погані. Прийнявши відповідні міри, які полягають у

використанні у межах сектора додаткових надлишкових бітів,

можна знизити ймовірність виникнення такої події настільки,

наскільки це необхідно.

Біт індикації стану корисний і у випадку виконання операції

запису. Адже для перевірки коректності результату запису

інформації в сектори можна здійснити повторне читання і

порівняти зчитаний блок з записаним. Однак замість здійснення

такої перевірки контролер дисків після читання може перевірити

лише біт індикації стану: значення «істина» засвідчує, що запис

виконано успішно; в іншому випадку записування необхідно

повторити.

Зазначимо, що як і під час виконання операції читання,

«істинне» значення біта індикації стану ще не є цілковитою

гарантією правильності результату запису. З метою зниження

ймовірності виникнення подібних явищ необхідно застосовувати

адекватні міри, про які розкажемо нижче.

6.2. Контрольні суми

На перший погляд, завдання перевірки «якості» даних у секторі

при виконанні їхнього читання виглядає нерозв’язним. Однак

справа є значно простішою: у сучасних дискових пристроях

кожному секторові носія відповідають декілька додаткових бітів,

які називають контрольною сумою (check sum). Їхнє значення

встановлюється залежно від змісту даних, які зберігаються у

секторі. Якщо функція читання виявляє невідповідність даних

контрольній сумі, то вона повертає стан «хибна», а в протилежному

випадку – «істина». Проте існує мала ймовірність виникнення такої

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

збігається з тією, яка відповідає коректним бітам. Цю ймовірність

вдається знизити до будь-якого припустимого значення шляхом

збільшення кількості бітів контрольної суми.

Контрольна сума в своїй простій формі ґрунтується на

властивості парності (parity) усіх бітів сектора. Якщо в наборі бітів

даних є непарна (odd) кількість одиниць, то біт парності має

значення 1. Якщо ж кількість одиниць парна (even), то бітові

парності присвоюється 0. Існує таке правило:

• кількість одиниць у наборі бітів даних, у тім числі біт

парності, завжди парна.

Виконуючи записування даних у сектор, контролер дисків

здатний обчислити значення біта парності і додати його до послі-

довності бітів, які записуються. Отже, кожен сектор міститиме

парну кількість бітів з одиничками.

Приклад 17. Припустимо, що в секторі необхідно зберегти

послідовність бітів даних 01101000. Кількість одиниць є непарною,

тому біту парності треба присвоїти значення 1. Отримаємо

011010001. Якщо початкова послідовність набуде вигляду

11101110, то біт парності буде нульовим: 111011100. Зверніть

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

кількість одиниць.

Довільна помилка, яка виникає під час спотворення одного біта

послідовності даних, зумовлює отримання набору даних з

непарною кількістю одиниць. Контролер диска одразу виявляє, що

результат читання неправильний.

Очевидно, що пошкодженими можуть виявитися і декілька бітів

сектора водночас. У цьому випадку з імовірністю 50% кількість

одиниць у секторі виявиться парною і помилку не виявлять. Для

того, щоб виявити помилку, яка охоплює декілька бітів, набір бітів

парності необхідно розширити. Наприклад, якщо передбачити

8 бітів парності (по одному на один біт кожного байта), то

ймовірність того, що жоден з бітів парності не зможе підтвердити

помилку, оцінюється величиною 1/256. Якщо ж використовувати n

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

незауваженої помилки становитиме 1/2

. Наприклад, якщо

виокремити під контрольну суму 4 байти, то помилка залишиться

невиявленою тільки в одному з 4 млрд випадків.

6.3. Стійкі сховища

Хоча механізм контрольних сум завжди дає змогу виявити

збійні ділянки носія і помилки операцій читання/запису, він не в

змозі забезпечити можливість виправлення помилок. Можлива

ситуація, коли після виконання спроби запису виявляється, що

попередній вміст сектора вже втрачено, а новий зчитати повторно

вже не можна. Уявіть, в яку проблему все це може обернутися,

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

виявляються втраченими обидва значення залишку, старе і нове. З

метою уникнення такої ситуації на базі одного чи декількох дисків

можна організувати так зване стійке сховище (stable storage).

Загальна ідея полягає в тому, що сектори диска (дисків) об’єдную-

ться в пари, і кожна пара представляє вміст Х одного сектора. Ми

посилатимемось на сектори пари як на «лівий» (X

) і «правий»(X

і вважатимемо, що обидва сектори містять достатню кількість бітів

парності. Отож вважатимемо, що w відображається вірно, якщо для

сектора X

або X

функція читання повертає значення w і

«істинний» біт індикації стану.

Алгоритм запису даних у стійке сховище можна представити

так:

1. Зберегти X в X

. Перевірити, чи біт індикації стану містить

«істина», тобто біти збереженої копії даних вірні. Якщо ні,

то повторити операцію. Якщо після декількох спроб

зберегти X в X

не вдається, то вважати, що сектор

пошкоджений, і замінити сектор X

іншим.

2. Повторити дії п.1 для сектора X

Процедура читання даних зі стійкого сховища така:

1. Зчитати значення X з X

. Якщо функція читання повертає

«хибне» значення біта індикації стану, то декілька разів

повторити операцію. Якщо на деякій ітерації повертається

«істинний» біт індикації стану, то вважати, що зчитані дані

є значеннями Х.

2. Якщо спроби читання з X

виявилися невдалими, то

повторити дії п.1 стосовно сектора X

6.4. Подолання наслідків помилок

Використання ступенів захисту інформації (стійких сховищ) дає

змогу відновити інформацію у таких випадках.

1. Руйнування носія (media decay). Якщо після збереження

даних Х у секторах X

і X

один із них стає

непридатним через руйнування носія і стає

нечитабельним, то відновити значення Х вдається

завжди, звернувшись до іншого – вцілілого – сектора.

Якщо сектор X

зіпсутий, а X

– ні, то, згідно з

алгоритмом читання, дані беруться з X

, навіть не

звертаючись до X

. Факт виходу з ладу X

буде

виявлено під час наступної спроби запису нового

значення Х. Якщо ж, навпаки, зруйнований тільки

сектор X

, то необхідно зчитати Х з X

. Якщо ж

водночас зруйновані обидва сектори, то значення Х

буде втрачено, проте ймовірність виникнення такої

події дуже мала.

2. Відмова запису (write failure). Припустимо, що в момент

запису значення Х стався короткочасний збій системи

(втрата електроживлення тощо). Імовірна ситуація, коли

значення Х в ОП відсутнє, а його копія пошкоджена в

момент збереження на диску: наприклад, у половині

сектора є вже частина нового значення Х, а в іншій

половині – попереднє значення. Після запуску системи

ми зможемо відновити або старе, або нове значення Х.

Можливі такі ситуації:

а) збій відбувся під час запису X

, отож значення біта

індикації стану для X

буде «хибний»; оскільки до

моменту збою нові дані Х у сектор X

ще не

записувались, тому із X

можна взяти старе

значення Х (для відновлення стану сектора X

нього треба скопіювати дані з X

);

б) збій системи стався після завершення запису X

отож X

містить нове значення Х, яке за

необхідності можна успішно зчитати; незалежно від

стану сектора X

, у нього треба скопіювати вміст

Вправи для опрацювання

Вправа 11. Обчисліть значення біта парності для таких бітових

послідовностей:

1) 00111011;

2) 00000000;

3) 10101101.

Вправа 12. Для кожної з бітових послідовностей визначте

значення двох бітів парності, перший з яких відповідає бітам на

непарних позиціях послідовності, а другий − бітам на парних

позиціях:

1) 00111011;

2) 00000000;

3) 10101101.

Тема 7. Відновлення даних за цілковитої відмови диска

У цій темі ми розглянемо найсерйозніший різновид відмов, коли

дисковий пристрій стає непридатним, наприклад, унаслідок

доторкання головки до поверхні пластини. Якщо інформацію

попередньо не скопійовано на інший носій – наприклад, резервну

магнітну стрічку чи дзеркальний диск, – то її безнадійно втрачено.

Для багатьох застосувань СКБД (таких як банківські та інші

фінансові системи, системи керування польотами, бронювання

квитків, ведення складського обліку і т. п.) це означає цілковитий

крах.

Сьогодні існує чимало стратегій, покликаних знизити загрозу

втрати даних через ламання дискових приводів. Усі вони, зазвичай,

передбачають використання тієї чи іншої моделі надлишку і

позначаються спільним терміном RAID (від Redundant Array of

Independent Disks – резервований масив незалежних дисків).

7.1. Модель відмови дискових пристроїв

Розглянемо статистику цілковитої відмови дискових приводів.

Проста одиниця вимірювання частоти виникнення цих явищ відома

як середній час напрацювання на відмову (mean time to failure). Це

проміжок часу, протягом якого 50% дискових пристроїв певної

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

магнітних дисків середній час напрацювання на відмову становить

приблизно 10 років.

Щоб спростити сприйняття цього параметра, можна вважати,

що одна десята всіх дискових пристроїв стає непридатною

протягом одного року, і в цьому випадку відсоток працездатності

(survival) задають як експоненту спадаючої функції. На практиці

крива працездатності більше подібна на ту, яку зображено на

рис. 14.

Відсоток

працездатності

Час

Рис. 14. Крива працездатності дискових пристроїв

Як і для більшості різновидів електронного обладнання, значна

частина відмов дискових пристроїв трапляється на самому початку

періоду їхньої експлуатації внаслідок незначних технологічних

дефектів. Здебільшого, вироби з тими чи іншими порушеннями

відбраковують ще на стадії технічного контролю і тестування.

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

проміжок часу. Втішає одне: диск, який не вийшов з ладу на

початку експлуатації, найімовірніше прослужить успішно ще

багато років. Однак ближче до кінця життєвого циклу пристрою

починають проявлятися негативні впливи таких чинників, як

старіння матеріалів, стирання частин, які труться, і накопичення

найдрібніших частинок пороху, що збільшує ймовірність виник-

нення несправності.

Середній час напрацювання на відмову – це, однак, не те саме,

що середній час виникнення події втрати даних, оскільки

використання схем RAID дає змогу зберігати інформацію цілою

навіть за умови виходу дисків з ладу. Всі схеми RAID передба-

чають використання одного або декількох дисків даних у сукупно-

сті з одним або декількома резервними дисками, призначеними для

зберігання службової інформації, склад якої цілковито визнача-

ється вмістом дисків даних. За умови поломки диска даних або

резервного диска для відновлення інформації використовують

вміст решти дисків масиву, так що непоправної втрати даних

вдається уникнути.

7.2. Дзеркальні диски як засіб резервування

Простий підхід до розв’язання задачі підвищення ступеня

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

дисків, які містять дзеркальні копії дисків даних. У цьому випадку

диски даних і резервні диски цілковито взаємозамінні. Технологія

використання дзеркальних дисків як засобу запобігання втрати

даних, яку часто називають схемою RAID рівня 1, забезпечує

значно вище значення середнього часу виникнення події втрати

даних порівняно з середнім часом напрацювання на відмову, і

наступний приклад це ілюструє. Зауважимо, що єдиною ситуацією,

яка може спричинити до втрати даних при використанні дзер-

кальних дисків і деяких інших варіантів схем RAID, може