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. Дисковий кеш на основі відображуваної пам'яті.


 

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

32783. ОПРЕДЕЛЕНИЕ УНИВЕРСАЛЬНОЙ ГАЗОВОЙ ПОСТОЯННОЙ 532 KB
  ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ На базе экспериментальных законов БойляМариотта ГейЛюссака Шарля Клапейрон установил что для разреженных газов выполняется соотношение 1 где P – давление газа Па V – объем газа м3 T – абсолютная температура К C – газовая постоянная зависящая от массы газа.=1013105 Па и T=273 К один моль любого газа занимает один и тот же объем равный =224 литра=224102 м3 поэтому для одного моля газа из соотношения 1 получаем: или 2 где величина R=831 одинакова для всех...
32784. ОПРЕДЕЛЕНИЕ ОТНОШЕНИЯ ТЕПЛОЁМКОСТЕЙ ДЛЯ ВОЗДУХА 256.5 KB
  Избыток давления воздуха в Рис. Пусть при состоянии 1 в баллоне объемом V масса воздуха равна m. Масса воздуха m занимала перед открытием крана К2 объем V1 где V1 V.
32785. Определение ускорения свободного падения при помощи машины Атвуда 569.5 KB
  Северодвинске Факультет: № 4 Кафедра: № 12 Лабораторная работа Определение ускорения свободного падения при помощи машины Атвуда г. Северодвинск 2007 Лабораторная работа ФМ 11 Определение ускорения свободного падения при помощи машины Атвуда 1. Цель и метод: С помощью машины Атвуда исследовать законы кинематики и научиться экспериментально определять ускорение свободного падения. Законы свободного падения тел открыл итальянский физик Галилео Галилей 1564 ― 1642.
32786. Изучение законов колебания математического и физического маятников 251.5 KB
  Определить положение центра масс физического маятника. Отклонение маятника от положения равновесия будем характеризовать углом образованным нитью с вертикалью рис. При отклонении маятника от положения равновесия возникает вращательный момент силы тяжести равный по модулю произведению силы mg на её плечо = l sin : M = mgl sin где m масса; l длина маятника. 1 Напишем для маятника уравнение динамики вращательного движения обозначив угловое...
32787. Происхождение, сущность и социальные функции науки 15.93 KB
  Наука – исторически сложившаяся форма духовнопрактического освоения мира направленная на познание и преобразование объективной действительности. Понятие наука имеет несколько аспектов: 1 система знаний 2 их духовное производство 3 практическая деятельность на их основе4 социальный институт. Этот аспект подчеркивает социальную сущность науки: наука как социальный институт представляет собой систему взаимосвязей между научными коллективами организациями членами научных сообществ а также систему норм и ценностей. Наука прошла...
32788. Особенности научного познания 14.79 KB
  Особенности научного познания. Цель научного познания – открытие объективных законов природы общества мышления постижение сущности изучаемых явлений. Объективность – адекватное отражение действительности не зависящее от субъекта познания. Наличие методологии познания.
32789. Уровни и методы научного познания 14.54 KB
  Уровни и методы научного познания. В научном познании используются разнообразные методы. Метод греч. Учение о методах – методология ее предметом является обоснование методов исследование их эффективности особенностей применения в различных областях знания.
32790. Диалектика, её исторические формы. Диалектика и метафизика 15.42 KB
  Диалектика и метафизика. диалектика – это учение о всеобщих связях и закономерностях развития природы общества и мышления а также основанный на этом учении метод познания. Диалектика как теория и метод познания в своем историческом развитии прошла несколько этапов. Наивная или стихийная диалектика античности.
32791. Общее понятие о философии. Исторические основания возникновения философии. Дофилософские мировоззренческие системы и их роль в формировании философии 15.71 KB
  Философия зародилась около 25 тыс. Термин философия был введен Пифагором и дословно означал любовь к мудрости phileo – любовь sophi – мудрость. Философия все больше превращалась в обобщенную систему знаний о мире задачей которой являлось дать ответы на наиболее общие глубинные вопросы о природе обществе человеке. Философия – это форма духовной деятельности человека форма общественного сознания направленная на осмысление коренных мировоззренческих вопросов.