69761

Продуктивність файлових систем

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-10-09

87 KB

3 чел.

Тема 9. Продуктивність файлових систем

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

  •  До першої належать різні підходи, які можуть бути впроваджені на етапі проектування і розробки файлової системи: керування розміром блоку, оптимізація розміщення даних, застосування продуктивніших алгоритмів і структур даних. Приклад їхнього застосування наведено у розділі 12.3.1.
  •  До другої належать низькорівневі універсальні підходи, прозорі для файлової системи (їхнє впровадження може підвищити продуктивність файлової системи без її модифікації). До них належать реалізація дискового кеша і планування переміщення голівок диска.

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

Розглянемо, яким чином можна оптимізувати продуктивність файлової системи зміною структур даних і алгоритмів, які в ній застосовують. У викладі використовуватимемо класичний приклад оптимізації традиційної файлової системи вихідної версії UNIX під час розроблення системи Fast File System (FFS) для BSD UNIX (у наш час ця файлова система також відома як ufs).

Традиційна файлова система UNIX [33, 59] складається із суперблока (що містить номери блоків файлової системи, поточну кількість файлів, покажчик на список вільних блоків), ділянки індексних дескрипторів і блоків даних (рис. 12.7). Розмір блока фіксований і становить 512 байт. Вільні блоки об'єднані у список.

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

  •  Розмір дискового блоку виявився недостатнім, внаслідок чого для розміщення даних файла була потрібна велика кількість блоків; індексні дескриптори навіть для невеликих файлів потребували кількох рівнів непрямої адресації, перехід між якими сповільнював доступ; пересилання даних одним блоком призводила до зниження пропускної здатності.
  •  Пов'язані об'єкти часто виявлялися віддаленими один від одного і не могли бути зчитані разом, зокрема, індексні дескриптори були розташовані далеко від блоків даних і для каталогу не перебували разом; послідовні блоки для файла також не містилися разом (це траплялося тому, що протягом експлуатації системи через вилучення файлів список вільних блоків ставав «розкиданим» по диску, внаслідок чого файли під час створення отримували блоки, віддалені один від одного).

До розв'язання цих проблем під час розробки файлової системи FFS були запропоновані декілька підходів [82].

Насамперед, у цій системі було збільшено розмір дискового блока (у FFS звичайно використовували два розміри блока: 4 і 8 Кбайт). Для того щоб уникнути внутрішньої фрагментації (яка завжди зростає зі збільшенням розміру блока), було запропоновано в разі необхідності розбивати невикористані блоки на частини меншого розміру — фрагменти, які можна використати для розміщення невеликих файлів. Мінімальний розмір фрагмента дорівнює розміру сектора диска, звичайно було використано фрагменти на 1 Кбайт.

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

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

Внаслідок реалізації цих і деяких інших рішень пропускна здатність файлової системи зросла в 10-20 разів (до 40 % можливостей диска).

На підставі цього прикладу можна зробити такі висновки:

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

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

використання бітової карти вільних блоків теж спричиняє підвищення продуктивності.

9.2. Кешування доступу до диска

Найважливішим засобом підвищення продуктивності файлових систем є організація дискового кеша (disk cache). Зупинимося докладніше на цьому найважливішому компоненті операційної системи.

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

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

Загальний принцип організації дискового кеша показано на рис. 12.8. Для прискорення пошуку потрібного блоку звичайно використовують хеш-функцію, що переводить номер блока у хеш-код. У пам'яті зберігають хеш-таблицю, елементи якої відповідають окремим значенням хеш-коду. Усі блоки з однаковим значенням хеш-коду об'єднують у зв'язні списки. Для пошуку в кеші блока із конкретним номером досить обчислити значення хеш-функції та переглянути відповідний список.

Рис. 12.8. Дисковий кеш

Під час реалізації керування дисковим кешем необхідно отримати відповіді на такі запитання.

  •  Якого розміру має бути кеш?
  •  Як має бути організоване заміщення блоків у кеші?
  •  Як організувати збереження модифікованої інформації із кеша на диск?
  •  Яким чином оптимізувати завантаження блоків у кеш?

Розмір дискового кеша

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

Є два різновиди кеша з погляду керування його розміром: кеш фіксованого розміру і кеш змінного розміру.

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

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

Заміщення інформації в кеші

Організація заміщення блоків у дисковому кеші багато в чому подібна до реалізації заміщення віртуальної пам'яті. Фактично для визначення заміщуваного блока можна використати більшість алгоритмів заміщення сторінок, про які йшлося в розділі 9, такі як FIFO, LRU, годинниковий алгоритм. Зазначимо, що в цьому разі LRU-алгоритм реалізувати простіше, оскільки звертання до дискового кеша відбувається значно рідше, ніж звертання до пам'яті, і за тривалістю інтервал між такими звертаннями значно перевищує той час, який потрібно затратити на фіксування моменту звертання. Для реалізації LRU-алгоритму можна підтримувати список усіх блоків кеша, упорядкований за часом використання (найстаріший блок — на початку, найновіший — наприкінці), переміщуючи блоки у кінець списку під час звертання до них.

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

Не рекомендують також використовувати алгоритм LRU у численних ситуаціях, коли розмір файла, який зчитують послідовно, перевищує розмір блока. У цьому разі найоптимальнішою є саме зворотна стратегія — MRU (Most Recently Used), коли витісняють блок, що був використаний останнім.

Розглянемо приклад. Нехай файл містить 4 дискові блоки, а в кеші є місце для трьох. Файл зчитують послідовно, при цьому отримують рядок посилань 1234. Якщо використати LRU-алгоритм, то при зчитуванні блоку 4 він заміщує в пам'яті блок 1. Якщо тепер прочитати файл іще раз (отримавши рядок посилань 12341234), побачимо, що першим потрібним блоком буде саме блок 1, який щойно витиснули. Доведеться його зчитувати ще раз, при цьому буде заміщено блок 2, який відразу ж виявиться потрібним знову і т. д. У MRU-алгоритмі блок 4 під час першого читання заміщує блок 3, блоки 1,2 і 4 під час другого читання перебуватимуть у кеші.

На практиці застосовуються модифіковані схеми LRU, які беруть до уваги категорії важливості блоків, а в разі послідовного доступу до файлів, більших за розміром, ніж блок, зводяться до схеми MRU.

Наскрізне і відкладене записування

З погляду реалізації записування модифікованих даних на диск розрізняють два основні типи дискових кешів: із наскрізним (write through cache) і з відкладеним записом (write back cache).

Для кеша із наскрізним записом у разі будь-якої модифікації блоку, що перебуває в кеші, його негайно зберігають на диску. Основною перевагою такого підходу (широко розповсюдженого в часи персональних ОС і реалізованого, наприклад, в MS-DOS) є те, що файлова система завжди перебуватиме в несуперечливому стані. Головний недолік цього підходу полягає у значному зниженні продуктивності під час записування даних.

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

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

Відокремлюють чотири випадки, коли зміни в кеші зберігаються на диску:

  •  модифікований блок витісняють з кеша відповідно до алгоритму заміщення (аналогічно до того, як це реалізовано для віртуальної пам'яті);
  •  закривають файл;
  •  явно видають команду зберегти всі зміни із кеша на диск; в UNIX-системах таку команду звичайно називають sync, вона зводиться до виконання системного виклику із тим самим ім'ям:

#inc1ude <unistd.h>

sync();  // скидання всіх даних з кеша на диск

  •  проходить заданий проміжок часу (в UNIX-системах за цим стежить спеціальний фоновий процес, який називають update; за замовчуванням такий інтервал для нього становить 30 хвилин).

Системний виклик sync() зберігає всі зміни із кеша на диск. Гнучкішим підходом є збереження змін для конкретних файлів. Для цього у POSIX передбачено системний виклик fsync(). Він блокує виконання процесу до повного збереження всіх буферів відкритого файла із пам'яті на диск.

include <um'std.h>

#include <fcntl,h>

int fdl - openCmyfile.txt". 0_RDWR | 0_CREAT, 0644):

write(fdl. "hello", sizeofC'hello")):

fsync(fdl):        // скидання всіх даних файла з кеша на диск

Аналогом fsync() у Win32 АРІ є функція FlushFileBuffersO:

HANDLE fh - CreateFileCmyfile.txt", GENERIC_WRITE.   ...);

WriteFileCfh, "hello", sizeofC"hello"),  ...);

FlushFileBuffers(fh);    // скидання всіх даних файла з кеша на диск

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

Для застосувань, які працюють із важливими даними, рекомендовано час від часу робити явне збереження змін на диску (наприклад, виконувати системні виклики sync(), fsync() або їхні аналоги). Для таких застосувань, як СУБД, найкращим вирішенням в основному є повна відмова від дискового кеша (використання прямого режиму доступу до диска) і реалізація свого власного кешування. Уже згадувалося про те, що часто такі застосування зовсім відмовляються від послуг файлової системи.

Для реалізації прямого доступу до диска в Linux необхідно під час відкриття файла увімкнути спеціальний прапорець 0_DIRECT:

1nt fdl = open ("myfile.txt". 0_RDWR | 0_DIRECT. 0644):

Аналогом 0_DIRECT у Win32 API є FILE_FLAG_WRITE_THROUGH:

HANDLE fh = CreateFileCmyfile.txt".   …

FILE_ATTRIBUTE_NORMAL  |  FILE_FLAG_WRITE_THROUGH.  NULL);

Випереджувальне читання даних

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

У реальності, як неодноразово було наголошено, знання про майбутнє немає, але можна спробувати його передбачити на підставі аналізу минулого. Таке пророкування може задати стратегію випереджувального читання даних (data prefetching, read-ahead).

Під час реалізації випереджувального читання намагаються визначити дискові блоки, які, швидше за все, використовуватимуться разом. Найчастіше при цьому застосовують принцип просторової локальності (spatial locality), за яким імовірність спільного використання вища для кластерів, що належать до одного файла і розташовані на диску поруч. При цьому під час випереджувального читання файлова система після читання кластера із номером п перевіряє, чи є в кеші кластер із номером я+1, і, якщо він там відсутній, його зчитують у пам'ять заздалегідь, до використання.

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

Дисковий кеш на основі відображуваної пам'яті

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

Зупинимося на особливостях реалізації кеша із використанням цієї технології. У цьому разі в системному адресному просторі резервують спеціальну ділянку, призначену для відображення даних усіх відкритих файлів. При спробі доступу до файла його відображають у цю ділянку (на практиці відображають не весь файл, а деяке його «вікно» фіксованого розміру).

Подальше обслуговування системних викликів доступу до диска здійснюють засобами реалізації відображуваної пам'яті. Під час першого доступу до файла із прикладної програми відбувається спроба скопіювати дані файла із відображеної ділянки у буфер режиму користувача. Оскільки пам'ять у системній ділянці в конкретний момент не виділена, виникають сторінкові переривання, і сторінки починають завантажувати із файла у пам'ять, а потім їхні дані копіюють у буфер користувача. Під час наступних спроб доступу нове відображення не створюється: якщо запит потрапляє у «вікно», використовують уже виділені сторінки (які в цьому разі і є кешем), а якщо запиту немає - нові сторінки завантажують у кеш під час обробки сторінкових переривань.

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

Контрольні питання:

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

2. Кешування доступу до диска.

3. Розмір дискового кеша.

4. Заміщення інформації в кеші.

5. Наскрізне і відкладене записування.

6. Випереджувальне читання даних.

7. Дисковий кеш на основі відображуваної пам'яті.


 

А также другие работы, которые могут Вас заинтересовать

33203. Кожные ощущения и восприятия 13.83 KB
  Возникают при непосредственном контакте предмета с кожей подразделяются на 4 вида: тактильные вибрационные температурные и болевые. Наибольшее значение для компенсации слуха имеют вибрационные т. Вибрационные ощущения возникают при воздействии меньшей силы чем слуховые. Для того чтобы вибрационные ощущения смогли использовать как средство познания для детей необходимо проводить специальную работу.
33204. Особенности развития внимания 15.43 KB
  Устойчивость внимания с возрастом меняется. Для детей с нарушениями слуха характерно более позднее становление высшей формы внимания т. произвольного и опосредствованного что обусловлено более поздним формированием умений использовать средства организации внимания управление им а также отставанием в развитии речи способствующей организации и управлению собственным поведением.
33205. Память как хранитель информации 15.52 KB
  Глухие дети раньше познают в объектах специфическое чем особое и общее отмечают несущественные детали в ущерб главным но менее заметным. Значительно больше глухие отстают в запоминании слов обозначающие звуковые явления. Глухие запоминают больше слов обозначающих качество предметов воспринимаемых тактильно. Часто глухие школьники заменяют слова глаголы из области слуховых представлений словами глаголами связанными со зрительной вибрационной и тактильной сферами.
33206. РАЗВИТИЕ СЛОВЕСНОЙ ПАМЯТИ 17.46 KB
  На успешность запоминания слов оказывает влияние к какой грамматической категории относятся слова. РАЗВИТИЕ СЛОВЕСНОЙ ПАМЯТИ глухих детей проходит ряд стадий: 13 класс характеризуется распространяющимся типом запоминания при котором используется повторение. 46 классы охватывающий тип запоминания. Часто наблюдается сочетание осмысленного и механического запоминания.
33207. УСЛОВИЯ РАЗВИТИЯ ПОНЯТИЙНОГО МЫШЛЕНИЯ У ГЛУХИХ ДЕТЕЙ 16.36 KB
  УСЛОВИЯ РАЗВИТИЯ ПОНЯТИЙНОГО МЫШЛЕНИЯ У ГЛУХИХ ДЕТЕЙ Экспериментальные психологические исследования большинства ученых показали что мышление у детей с нарушениями слуха имеет целый ряд особенностей которые обусловлены вопервых более медленным и своеобразным развитием речи у этих детей и вовторых недостаточным вниманием которое уделяется формированию мыслительной деятельности детей в практике дошкольного и школьного воспитания и обучения. Исследования свидетельствуют о том что наибольшие трудности возникают у глухих детей при...
33208. ПРЕДМЕТ И ЗАДАЧИ СУРДОПСИХОЛОГИИ 13.38 KB
  Предметом сурдопсихологии являются изучение своеобразия психического развития людей с недостатками слуховой функции и установление возможностей и путей компенсации нарушений различной сложности. Задачи сурдопсихологии заключаются в следующем: выявить общие и специфические закономерности психического развития людей с нарушенным слухом по сравнению с людьми имеющими сохранный слух; изучить особенности развития отдельных видов познавательной деятельности людей с нарушенным слухом; изучить закономерности развития их личности; ...
33209. СУРДОПСИХОЛОГИЯ В РОССИИ (Краткий исторический обзор) 20.51 KB
  Лаговский писал о наличии у глухих детей остатков слуха которые могут быть активизированы и развиты. Отечественная сурдопедагогика на всех этапах своего развития придавала большое значение изучению психологических особенностей детей с нарушениями слуха для обоснования методов педагогического воздействия.Выготский столкнулся с проблемами обучения детей имеющих различные нарушения глухоту слепоту умственную отсталость; с необходимостью выявления их потенциальных возможностей и оказания им помощи. статья Принципы социального воспитания...
33210. Причины нарушений слуха 15.39 KB
  Нарушения слуха возникают в результате заболеваний поражающих наружное среднее или внутреннее ухо слуховой нерв. Если поражено внутреннее ухо и стволовая часть слухового нерва в большинстве случаев наступает глухота если же среднее ухо то чаще наблюдается частичная потеря слуха. Большую роль в возникновении нарушений слуха у ребенка играет неблагополучное протекание беременности прежде всего вирусные заболевания матери в первом триместре беременности такие как краснуха корь грипп герпес.
33211. Педагогические классификации подходов к обучению детей с нарушениями слуха 14.69 KB
  Боскис предложила новые критерии учитывающие своеобразие развития детей с нарушениями слуха: степень потери слуха; время возникновения нарушения слуха; уровень развития речи. К этой группе относят детей с такой степенью потери слуха которая лишает их возможности естественного восприятия речи и самостоятельного овладения ею. У них может быть разная степень нарушения слуха и разный уровень сохранности речи поскольку при возникновении нарушения слуха без специальной педагогической поддержки речь начинает распадаться.