Системні структури в пам'яті для керування файловою системою

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

Рис. 19.12. Структури ОС у пам'яті для керування файловою системою.

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

 

Лекція № 15. Віртуальні файлові системи

План

· Віртуальні файлові системи

· Реалізація директорій

· Методи розміщення файлів

· Файлові системи, засновані на розширеннях

· Посилальне розміщення файла

· Індексуєме розміщення

· Ефективність и продуктивність дискової пам'яті

· Кеширування диска

Віртуальні файлові системи (VFS) забезпечують об’єктно-орієнтований спосіб реалізації файлових систем.

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

Даний API є набором операцій над самої VFS, а не над яким-небудь специфічним типом файлових систем.

Схема організації віртуальної файлової системи зображена на рис. 20.1.

Рис. 20.1. Схема організації віртуальної файлової системи.

Реалізація директорій

Директорія - центральна системна структура у файловій системі, на якій заснований пошук файлів. Тому ефективна реалізація директорій особливо важлива.

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

Більше ефективний метод реалізації - хеш-таблица – лінійний список з хеш-оглавлением і підрозділом на (невеликі) списки елементів з тим самим значенням хеш-функции. Такий метод зменшує час пошуку в директорії.

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

Методи розміщення файлів

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

· Суміжне розміщення

· Посилальне розміщення

· Індексоване розміщення.

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

Недоліки даного методу наступні:

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

· неможливість збільшення розміру файлу.

Суміжне розміщення файлів ілюструється на рис. 20.2.

Рис. 20.2. Суміжне розміщення файлів.

Файлові системи, засновані на розширеннях

Багато сучасних файлових систем, - наприклад, Veritas File System, або Vx-FS – основна файлова система в ОС HP-UX фірми Hewlett-Packard, - використають модифіковане суміжне розміщення файлів. Дискові блоки в такій системі розміщаються в розширеннях (extents). Розширення - це суміжний блок на диску. Файл складається з одного або декількох розширень. Таким чином, якщо довжина файлу не збільшується, він зберігається у вигляді однієї суміжної області зовнішньої пам'яті, що забезпечує максимальну ефективність доступу. У випадку збільшення довжини файл представляється списком з основної частини й розширень.

Посилальне розміщення файлу

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

· Простота - необхідно зберігати тільки початкову адресу;

· Відсутність втрат дискового простору; система зберігає списки вільної пам'яті.

Недолік - відсутність довільного доступу: для доступу до даних файлу в загальному випадку необхідно виконати перегляд частини списку блоків файлу.

При посилальному розміщенні адреса по файлі представляється у вигляді (Q, R), де Q – номер блоку, до якого виконується доступ, у зв'язаному списку блоків, що представляє файл; R - cміщення в блоці.

Посилальне розміщення файлів зображене на рис. 20.3.

Рис. 20.3. Посилальне розміщення файлів.

До файлових систем, що використають посилальне розміщення, ставиться файлова система File-allocation table (FAT), використовувана в MS-DOS й OS/2 і дотепер використовувана в Windows (рис. 20.4).

Рис. 20.4. Файлова система File Allocation Table (FAT).

У системі FAT елемент директорії містить ім'я файлу й адреса його початкового блоку (кластера) на диску. Кожен блок посилається на наступний, крім останнього. Система FAT розроблена творцем корпорації Microsoft Біллом Гейтсом в 1976 р. Тепер читачеві повинне бути зрозуміло, чому операція видалення файлу в Windows не "фатальна": вона означає лише видалення елемента директорії з посиланням на початковий кластер файлу. Незважаючи на це, список кластерів, що представляє файл, можна виявити й відновити посилання з директорії на його початок, хоча й під іншим ім'ям. В MS DOS дану функцію виконувала системна утиліта unerase (скасувати видалення).

Індексування розміщення

При індексованому розміщенні, на відміну від попередні, всі покажчики на блоки файлу зібрані разом в індексний блок (i-node, superblock). Використається індексна таблиця, що посилається на блоки даних файлу. Подібна система використається в системах UNIX, Linux, Solaris.

Приклад індексуємого розміщення наведений на рис. 20.5.

Рис. 20.5. індексоване розміщення файлів.

Як видно зі схеми, при індексованому розміщенні блоки файлу можуть бути розташовані як завгодно розрізнено, але індексний блок містить всі посилання на них. Посилання на блок даних можуть бути обрані безпосередньо з індексного блоку, без якого-небудь пошуку.

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

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

При відображенні логічної адреси у фізичний, якщо обмежити максимальний розмір файлу 256 K словами, а розмір блоку - 512 слів, то для індексної таблиці потрібно тільки один блок. Логічна адреса буде мати вигляд (Q, R), де Q - зсув в індексній таблиці, R - зсув у блоці.

При відображенні логічної адреси у фізичний для файлу необмеженої довжини (при розмірі блоку - 512 слів) може використатися посилальна схема - у список зв'язуються блоки індексної таблиці. У цьому випадку логічна адреса буде мати вигляд (Q1, R1), де Q1 = номер блоку індексної таблиці; R1 = (Q2, R2), де Q2 - зсув у блоці індексної таблиці, R2 зсув у блоці файлу.

У системі UNIX використається комбінована схема індексного розміщення файлів: можлива однорівнева адресація даних через індексні блоки, дворівнева (індексні блоки адресують інші індексні блоки, а ті, у свою чергу, - блоки даних),трьох рівнева й т.д. Дана схема ілюструється на рис. 20.6.

 

Рис. 20.6. Комбінована індексна схема розміщення файлів в UNIX.