Реалізація файлової системи

1.

ТЕМА 4.2
РЕАЛІЗАЦІЯ ФАЙЛОВОЇ СИСТЕМИ
ПЛАН
1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА
ФАЙЛОВОЇ СИСТЕМИ НА ДИСКУ
2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
3 HАДІЙНІСТЬ ФАЙЛОВОЇ СИСТЕМИ

2.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
Система зберігання даних на дисках може бути
структурована таким чином.
Нижній рівень - обладнання.
Безпосередньо з пристроями (дисками) взаємодіє
частина ОС, звана системою вводу-виводу. Система
вводу-виводу надає в розпорядження більш
високорівневого компонента ОС - файлової системи
- використовуваний дисковий простір у вигляді
безперервної послідовності блоків фіксованого
розміру. Система вводу-виводу має справу з
фізичними блоками диска, які характеризуються
адресою, наприклад диск 2, циліндр 75, сектор 11.
Файлова система має справу з логічними блоками,
кожен з яких має номер (від 0 або 1 до N). Розмір
логічних блоків файлу співпадає або є кратним
розміру фізичного блоку диска і може бути заданий
рівним розміру сторінки віртуальної пам'яті,
підтримуваною апаратурою комп'ютера спільно з
операційною системою.

3.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
У структурі системи управління файлами можна виділити базисну підсистему, яка
відповідає за виділення дискового простору конкретним файлам, і більш високорівневу
логічну підсистему, яка використовує структуру дерева директорій для надання
модулю базисної підсистеми необхідної їй інформації, виходячи з символічного імені
файлу. Вона також відповідальна за авторизацію доступу до файлів.
Стандартний запит на відкриття (open) або створення (create) файлу поступає від
прикладної програми до логічної підсистеми. Логічна підсистема, використовуючи
структуру директорій, перевіряє права доступу і викликає базову підсистему для
отримання доступу до блоків файлу. Після цього файл вважається відкритим, він
міститься в таблиці відкритих файлів, і прикладна програма отримує у своє
розпорядження дескриптор цього файлу. Дескриптор файлу є посиланням на файл в
таблиці відкритих файлів і використовується в запитах прикладної програми на
читання-запис з цього файлу. Запис в таблиці відкритих файлів вказує через систему
виділення блоків диска на блоки цього файлу. Якщо до моменту відкриття файл вже
використовується іншим процесом, тобто міститься в таблиці відкритих файлів, то після
перевірки прав доступу до файлу може бути організований спільний доступ. При цьому
новому процесу також повертається дескриптор - посилання на файл в таблиці
відкритих файлів.

4.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
Методи виділення дискового простору. Ключовим, безумовно, являється
питання, який тип структур використовується для обліку окремих блоків файлу,
тобто спосіб зв'язування файлів з блоками диска. У ОС використовується
декілька методів виділення файлу дискового простору.
а) метод виділення безперервною послідовністю блоків;
Кожен файл зберігається як безперервна послідовність блоків диска. При
безперервному розташуванні файл характеризується адресою і довжиною (у
блоках). Файл, що стартує з блоку b, займає потім блоки b+1, b+2, .. b+n - 1.
Переваги. 1 Схему легко реалізувати, оскільки з'ясування місцезнаходження
файлу зводиться до питання, де знаходиться перший блок.
2 Схема забезпечує хорошу продуктивність, оскільки цілий файл може бути
зчитаний за одну дискову операцію.

5.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
а) метод виділення безперервною послідовністю блоків;
Недоліки. 1 Не завжди є відповідний за розміром вільний фрагмент для
нового файлу.
2 Безперервний розподіл зовнішньої пам'яті непридатний до тих пір, поки
невідомий максимальний розмір файлу.
Таким чином, коли вміст диска постійно змінюється, цей метод
нераціональний. Проте для стаціонарних файлових систем, наприклад для
файлових систем компакт-дисків, він цілком придатний.

6.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
б) метод зв'язного списку;
Зовнішня фрагментація - основна
проблема розглянутого вище методу може бути усунена за рахунок
подання файлу у вигляді зв'язного
списку блоків диска. Запис в
директорії містить покажчик на
перший і останній блоки файлу (іноді
як варіант використовується
спеціальний знак кінця файлу - EOF).
Кожен блок містить покажчик на
наступний блок (рисунок 2).

7.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
б) метод зв'язного списку;
Переваги. 1 Зовнішня фрагментація для цього методу відсутня. Будь-який вільний
блок може бути використаний для збереження даних.
2 Немає необхідності декларувати розмір файлу у момент створення. Файл може
рости необмежено.
Недоліки. 1 При прямому доступі до файлу для пошуку i-го блоку треба здійснити
декілька звернень до диска, послідовно зчитуючи блоки від 1 до i - 1, тобто вибірка
логічно суміжних записів, які займають фізично несуміжні сектори, може вимагати
багато часу.
2 Спосіб не дуже надійний. Наявність дефектного блоку в списку призводить до
втрати інформації в частині файлу, що залишилася, і потенційно до втрати дискового
простору, відведеного під цей файл.
3 Для покажчика на наступний блок усередині блоку треба виділити місце, що не
завжди зручно. Місткість блоку, що традиційно є мірою двійки, таким чином, перестає
бути мірою двійки, оскільки покажчик відбирає декілька байтів.
Тому метод зв'язного списку зазвичай в чистому вигляді не використовується.

8.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
в) таблиця відображення файлів;
Одним з варіантів попереднього способу, що усуває наведені вище недоліки,
є зберігання покажчиків не в дискових блоках, а в індексній таблиці в пам'яті,
яка називається таблицею відображення файлів (File Allocation Table FAT)(рисунок 3). Цієї схеми дотримується багато ОС (MS-DOS, OS/2, MS Windows
та ін.)
Як і раніше істотно, що запис в директорії містить тільки посилання на
перший блок. Далі за допомогою таблиці FAT можна локалізувати блоки файлу
незалежно від його розміру. У тих рядках таблиці, які відповідають останнім
блокам файлів, зазвичай записується деяке граничне значення, наприклад EOF.

9.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
в) таблиця відображення файлів;
Рисунок 3 - Метод зв'язного списку з використанням
таблиці в оперативній пам'яті

10.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
в) таблиця відображення файлів;
Переваги. 1По таблиці відображення можна судити про фізичне сусідство
блоків, розташованих на диску, і при виділенні нового блоку можна легко
знайти вільний блок диска, що знаходиться поблизу від інших блоків цього
файлу.
Недоліки. 1 Необхідність зберігання в пам'яті цієї досить великої таблиці.

11.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
г) метод індексних вузлів.
Найбільш поширений
метод виділення файлу блоків
диска - зв'язати з кожним
файлом невелику таблицю,
звану індексним вузлом (inode), яка перераховує
атрибути і дискові адреси
блоків файлу (рисунок 4).
Рисунок 4.2.4 - Структура індексного вузла

12.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
г) метод індексних вузлів.
Запис в директорії, що відноситься до файлу, містить адресу індексного блоку. У
міру заповнення файлу покажчики на блоки диска в індексному вузлі набувають
осмислених значень.
Індексування підтримує прямий доступ до файлу, без збитку від зовнішньої
фрагментації. Індексоване розміщення широко поширене і підтримує як
послідовний, так і прямий доступ до файлу.
Зазвичай застосовується комбінація однорівневого і багаторівневих індексів.
Перші декілька адрес блоків файлу зберігаються безпосередньо в індексному вузлі,
таким чином, для маленьких файлів індексний вузол зберігає усю необхідну
інформацію про адреси блоків диска. Для великих файлів одна з адрес індексного
вузла вказує на блок непрямої адресації. Цей блок містить адреси додаткових
блоків диска. Якщо цього недостатньо, використовується блок подвійної непрямої
адресації, який містить адреси блоків непрямої адресації. Якщо і цього не вистачає,
використовується блок потрійної непрямої адресації.

13.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
г) метод індексних вузлів.
Цю схему використовують файлові системи Unix (а також файлові системи HPFS,
NTFS та ін.). Такий підхід дозволяє при фіксованому, відносно невеликому розмірі
індексного вузла підтримувати роботу з файлами, розмір яких може мінятися від
декількох байт до декількох гігабайтів. Істотно, що для маленьких файлів
використовується тільки пряма адресація, що забезпечує максимальну
продуктивність.

14.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
г) метод індексних вузлів.
Цю схему використовують файлові системи Unix (а також файлові системи HPFS,
NTFS та ін.). Такий підхід дозволяє при фіксованому, відносно невеликому розмірі
індексного вузла підтримувати роботу з файлами, розмір яких може мінятися від
декількох байт до декількох гігабайтів. Істотно, що для маленьких файлів
використовується тільки пряма адресація, що забезпечує максимальну
продуктивність.

15.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
Управління вільним і зайнятим дисковим простором. Дисковий простір, не
виділений жодному файлу, також має бути керованим. У сучасних ОС використовується
декілька способів обліку використовуваного місця на диску. Розглянемо найбільш
поширені:
а) облік за допомогою організації бітового вектора;
Список вільних блоків диска реалізований у вигляді бітового вектора (bit map або
bit vector). Кожен блок представлений одним бітом, що набуває значення 0 або 1,
залежно від того, зайнятий він або вільний. Наприклад, 00111100111100011000001 ..
.
Головна перевага цього підходу полягає в тому, що він відносно простий і
ефективний при знаходженні першого вільного блоку або n послідовних блоків на
диску.
Недоліки. Незважаючи на те, що розмір описаного бітового вектора найменший з
усіх можливих структур, навіть такий вектор може виявитися великого розміру. Тому
цей метод ефективний, тільки якщо бітовий вектор поміщається в пам'яті цілком, що
можливо лише для відносно невеликих дисків. Наприклад, диск розміром 4 Гбайт з
блоками по 4 Кбайт потребує таблиці розміром 128 Кбайт для управління вільними
блоками.

16.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
Управління вільним і зайнятим дисковим простором.
б) облік за допомогою організації зв'язного списку.
Інший підхід - зв'язати в список усі вільні блоки, розміщуючи покажчик на
перший вільний блок в спеціально відведеному місці диска, попутно кешючи в
пам'яті цю інформацію.
Подібна схема не завжди ефективна. Для трасування списку треба виконати
багато звернень до диска.
Іноді удаються до модифікації підходу зв'язного списку, організовуючи
зберігання адрес n вільних блоків в першому вільному блоці. Перші n - 1 цих
блоків дійсно використовуються. Останній блок містить адреси інших n блоків і
т. д.

17.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
Структура файлової системи на диску. Розгляд методів роботи з дисковим
простором дає загальне уявлення про сукупність службових даних, необхідних
для опису файлової системи. Структура службових даних типової файлової
системи, наприклад Unix, на одному з розділів диска, таким чином, може
складатися з чотирьох основних частин (рисунок 5).
Рисунок 5 - Типова структура файлової системи на диску

18.

1 ЗАГАЛЬНА СТРУКТУРА ФАЙЛОВОЇ СИСТЕМИ. СТРУКТУРА ФАЙЛОВОЇ
СИСТЕМИ НА ДИСКУ
На початку розділу знаходиться суперблок, що містить загальний опис
файлової системи, наприклад:
тип файлової системи;
розмір файлової системи в блоках;
розмір масиву індексних вузлів;
розмір логічного блоку.
У файлових системах сучасних ОС для підвищення стійкості підтримується
декілька копій суперблоку.
Масив індексних вузлів (ilist) містить список індексів, відповідних файлам цієї
файлової системи.
У блоках даних зберігаються реальні дані файлів. Розмір логічного блоку
даних може задаватися при форматуванні файлової системи. Заповнення диска
змістовною інформацією припускає використання блоків зберігання даних для
файлів директорій і звичайних файлів і є слідством модифікації масиву
індексних вузлів і даних, таких, що описують простір диска. Окремо взятий блок
даних може належати одному і тільки одному файлу у файловій системі.

19.

2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
Директорія або каталог - це файл, що має вигляд таблиці і зберігаючий
список файлів, що входять в нього, або каталогів.
Коли система відкриває файл, вона шукає його ім'я в директорії. Потім із
запису в директорії або із структури, на яку запис в директорії вказує,
витягаються атрибути і адреси блоків файлу на диску. Ця інформація
поміщається в системну таблицю в головній пам'яті. Усі наступні посилання на
цей файл використовують цю інформацію. Атрибути файлу можна зберігати
безпосередньо в записі в директорії. Проте для організації спільного доступу до
файлів зручніше зберігати атрибути в індексному вузлі, як це робиться в Unix.

20.

2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
Розглянемо декілька конкретних прикладів реалізації директорій в деяких
ОС.
Директорії в ОС MS-DOS. У ОС MS-DOS типовий запис в директорії має
вигляд, показаний на рисунку 6.
Рисунок 6 - Варіант запису в директорії MS-DOS
У ОС MS - DOS, як і в більшості сучасних ОС, директорії можуть містити
піддиректорії (що специфікуються бітом атрибуту), що дозволяє конструювати
довільне дерево директорій файлової системи.
Номер першого блоку використовується як індекс в таблиці FAT. Далі по
ланцюжку в цій таблиці можуть бути знайдені інші блоки.

21.

2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
Розглянемо декілька конкретних прикладів реалізації директорій в деяких
ОС.
Директорії в ОС Unix. Кожен запис містить ім'я файлу і номер його
індексного вузла (рисунок 7). Уся інша інформація про файл (тип, розмір, час
модифікації, власник і т. д. і номери дискових блоків) знаходиться в індексному
вузлі.
Рисунок 7 - Варіант запису в директорії Unix

22.

2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
Пошук в директорії. Список файлів в директорії зазвичай не є
впорядкованим по іменах файлів. Тому правильний вибір алгоритму пошуку
імені файлу в директорії має великий вплив на ефективність і надійність
файлових систем.
а) лінійний пошук;
Директорія проглядається із самого початку, поки не зустрінеться потрібне
ім'я файлу. Хоча це найменш ефективний спосіб пошуку, виявляється, що в
більшості випадків він працює з прийнятною продуктивністю.
Метод простий, але вимагає часових витрат. Для створення нового файлу
спочатку треба перевірити директорію на наявність такого ж імені. Потім ім'я
нового файлу вставляється в кінець директорії (якщо, зрозуміло, файл з таким
же ім'ям в директорії не існує, інакше треба інформувати користувача). Для
видалення файлу треба також виконати пошук його імені в списку і помітити
запис як невживаний.
Недолік цього методу - послідовний пошук файлу.

23.

2 РЕАЛІЗАЦІЯ ДИРЕКТОРІЙ. ПОШУК В ДИРЕКТОРІЇ
Пошук в директорії.
б) хеш-таблиця.
Хешування - інший спосіб, який може використовуватися для розміщення і
наступного пошуку імені файлу в директорії. У цьому методі імена файлів також
зберігаються в каталозі у вигляді лінійного списку, але додатково
використовується хеш-таблиця. Хеш-таблиця, точніше побудована на її основі
хеш-функція, дозволяє по імені файлу отримати покажчик на ім'я файлу в
списку. Таким чином, можна істотно зменшити час пошуку.

24.

3 HАДІЙНІСТЬ ФАЙЛОВОЇ СИСТЕМИ
Важливий аспект надійної роботи файлової системи - контроль її цілісності.
У сучасних ОС передбачені заходи, які дозволяють звести до мінімуму збиток
від псування файлової системи і потім повністю або частково відновити її
цілісність.
Журналювання є засобом підтримки цілісності, що запозичений з систем
управління базами даних. Послідовність дій з об'єктами під час файлової
операції протоколюється, і якщо сталась зупинка системи, то, маючи в наявності
протокол, можна здійснити відкат системи назад в початковий цілісний стан, в
якому вона перебувала до початку операції. У разі відмови дозволяє
реконструювати втрачені дані.
Для відкату необхідно, щоб для кожної протокольованої в журналі операції
існувала зворотна. З цієї причини, на відміну від СУБД, у файлових системах
протоколюються не усі зміни, а лише зміни метаданих (індексних вузлів, записів
в каталогах та ін.). Зміни в даних користувача в протокол не заносяться. Крім
того, якщо протоколювати зміни призначених для користувача даних, то цим
буде завдано серйозного збитку продуктивності системи, оскільки кешування
втратить сенс.

25.

3 HАДІЙНІСТЬ ФАЙЛОВОЇ СИСТЕМИ
Журналізація реалізована в NTFS, Ext3FS, ReiserFS і інших системах. Щоб
підкреслити складність завдання, треба відмітити, що існують не цілком
очевидні проблеми, пов'язані з процедурою відкату. Наприклад, відміна одних
змін може зачіпати дані, вже використані іншими файловими операціями. Це
означає, що такі операції також мають бути скасовані. Ця проблема дістала
назву каскадного відкату транзакцій.

26.

УЗАГАЛЬНЕННЯ ВИВЧЕНОГО МАТЕРІАЛУ:
Усно дайте відповіді на питання.
1 У ОС використовується декілька методів виділення файлу дискового простору.
В чому полягає суть методу «Виділення безперервною послідовністю блоків»?
2 У ОС використовується декілька методів виділення файлу дискового простору.
В чому полягає суть методу індексних вузлів?
3 У ОС використовується декілька методів виділення файлу дискового простору.
В чому полягає суть методу «Таблиця відображення файлів»?
4 У ОС використовується декілька методів виділення файлу дискового простору.
В чому полягає суть методу зв’язного списку?
5 Які переваги методу виділення блоків диска безперервною послідовністю?
6 Які недоліки методу виділення блоків диска безперервною послідовністю?
7 Які недоліки методу зв’язного списку?
8 Які недоліки методу «Таблиця відображення файлів»?
9 Які переваги методу «Таблиця відображення файлів»?
10Які переваги методу індексних вузлів?
11Поясніть принцип операції журналювання?

27.

ДОМАШНЄ ЗАВДАННЯ
В Moodle пройти Тест до теми 4.2.