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


 

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

39615. Изучение рекламной деятельности в предприятии розничной торговли ЗАО «Торговый дом «Центробувь» и ее эффективности 968.5 KB
  Не одна современная фирма не сможет обойтись без хорошей рекламы. Эффективность рекламы выражается в изучении знакомства целевой аудитории с информацией об исследуемой фирме и ее товарах а также о том что именно о них известно какой образ фирмы и товаров сформировался и каково отношение к ним. Для достижения поставленной цели необходимо решить ряд задач: изучить виды рекламы и ее эффективность; определить сущность управления рекламной деятельностью на торговом предприятии; рассмотреть организацию взаимоотношений участников рекламного...
39616. Разработка web-сайта интернет-магазина для аптеки 4.74 MB
  В дипломном проекте описывается разработка web-сайта интернет-магазина для аптеки. Определяются методы и средства разработки сайта. Выбрана система управления содержимым сайта Wordpress. Описаны результаты дипломного проекта и содержание созданного web-сайта. Разработано руководство пользователя. Рассчитаны затраты на проектирование web-сайта. Рассмотрены разделы по безопасности жизнедеятельности и охране природопользования. В приложениях приведены коды страниц созданного web-сайта интернет-магазина.
39617. Разработка основных принципов по совершенствованию работы пункта коммерческого осмотра 333 KB
  Высокий уровень грузовой и коммерческой работы зависит прежде всего от ее организации в основной линейной производственно-хозяйственной единице железнодорожного транспорта на станции где выполняется основная часть операций связанных с обеспечением плана перевозок грузов а именно2: прием к перевозке погрузка выгрузка выдача и хранение грузов с обеспечением полной их сохранности; подготовка вагонов к погрузке; взвешивание грузов; сортировка мелких отправок; оформление перевозочных документов; подача вагонов на примыкающие к станции...
39618. Междисциплинарный курсовой проект 406 KB
  65 Автоматизированные системы обработки информации и управления Волгоград 2011 ББК УДК Рецензент Издается по решению редакционноиздательского совета Волгоградского государственного технического университета Междисциплинарный курсовой проект: метод.65 Автоматизированные системы обработки информации и управления всех форм обучения. Выполнение междисциплинарного проекта основано на материале ранее изученных дисциплин: Информационные технологии Сети ЭВМ и телекоммуникации Маркетинг и менеджмент программных систем Технология...
39619. СТРУКТУРА И ОРГАНИЗАЦИЯ РАБОТЫ АКУШЕРСКОГО СТАЦИОНАРА САНИТАРНО - ПРОТИВОЭПИДЕМИЧЕСКИЙ РЕЖИМ В АКУШЕРСКОМ СТАЦИОНАРЕ 64.5 KB
  АС имеет следующие основные подразделения: приемнопропускной блок; физиологическое I акушерское отделение 5055 от общего числа акушерских коек; отделение палаты патологии беременности 2530; отделение палаты новорожденных в I и II акушерских отделениях; обсервационное II акушерское отделение 2025; гинекологическое отделение 2530. ПЕРВОЕ ФИЗИОЛОГИЧЕСКОЕ АКУШЕРСКОЕ ОТДЕЛЕНИЕ Первое физиологическое акушерское отделение включает в себя приемнопропускной блок родовой блок послеродовые палаты отделение...
39620. Модернизация локальной вычислительной сети административного здания ЗАО «ПромСвязь-Инвест» 2.11 MB
  1 Техническое задание Полное наименование проекта Модернизация локальной вычислительной сети административного здания ЗАО ПромСвязьИнвест. Цель создания системы Модернизация локальной вычислительной сети и создание базы данных принятия заявлений от абонентов на подключение или устранение неисправностей. Назначение системы ЛВС обеспечивает связь компьютеров для обмена информацией совместного использования сетевого оборудования информационных ресурсов устройств хранения информации и обеспечения контроля доступа на предприятии обеспечивает...
39621. Основные направления совершенствования налоговой политики государства 1.87 MB
  Cоциальноэкономическая сущность налогов и налоговой политики.3 Зарубежный опыт организации налоговой политики. Методологические принципы налоговой политики.1 Тенденции современной налоговой политики РФ: элементы состав и эволюция в условиях рыночных отношений.
39622. Приемы измерения социальной установки 141.5 KB
  Это наиболее простой вид шкалы измерения установки. При конструировании шкалы самооценки в форме €œтрадиционного€ вопроса её позиции обязательно располагаются симметрично и состоят из равного числа положительных и отрицательных оценок разделённых €œнейтральной€ позицией. Наиболее простой приём измерения установок по правилам такой шкалы ранжирование респондентами тех объектов отношение к которым с их стороны интересует исследователя. Более сложный вариант измерения установок при помощи ранговой шкалы метод парных сравнений.
39623. Разработка типового проекта «дублирующего» родильного дома 748.5 KB
  В рамках своего дипломного проекта я рассматриваю актуальные проблемы существующей системы учреждений родовспоможения в г. Цель 1 создать условия при которых здоровые беременные женщины и роженицы могли гарантировано получать медицинскую помощь в учреждениях родовспоможения обслуживающих район их места жительства; 2 улучшить условия получения медицинской помощи беременными женщинами и роженицами с патологиями. Таким образом деятельность перинатального центра не разгружает основной поток рожениц приходящийся на учреждения родовспоможения...