Ноу Інти, лекція, підсистема вводу-виводу

7.12. Архітектура файлової системи

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

Класична схема організації програмного забезпечення файлової системи представлена ​​на рис. 7.6.

Мал. 7.6. Організація програмного забезпечення файлової системи

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

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

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

Логічний ввод- висновок надає додаткам і користувачам доступ до записів. Він забезпечує можливості загального призначення по введенню-висновку записів і підтримує інформацію про файлах. Найбільш близький до користувача рівень ФС часто називається методом доступу. Він забезпечує стандартний інтерфейс між додатками і файловими системами і пристроями, що містять дані. Різні методи доступу відображають різні структури файлів і різні шляхи доступу і обробки даних.

7.13. Організація файлів і доступ до них

Типи, іменування і атрибути файлів

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

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

Спеціальні файли - це фіктивні файли, асоційовані з пристроями введення-виведення, які використовуються для уніфікації механізму доступу до послідовним пристроїв введення-виведення, таким як термінали, принтери і ін. (Наприклад, MS- DOS розглядає монітор і клавіатуру як файли зі стандартним ім'ям con - консоль. а принтер - як файл prn). Блокові спеціальні файли використовуються для моделювання дисків.

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

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

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

У багатьох операційних системах ім'я файлу складається з двох частин, між якими ставиться крапка. Частина імені після точки називається розширенням файлу і зазвичай означає його тип. Так, в MS- DOS ім'я файлу може містити від 1 до 8 символів, а розширення від 0 (відсутній) до 3.

У деяких ОС, наприклад, Windows. розширення вказує на програму, що створила файл. Інші ОС, наприклад, UNIX. не примушують користувача строго дотримуватися розширень. Деякі типові розширення файлів наведені нижче.

В ієрархічно організованих файлових системах зазвичай використовуються три типи імен файлів: прості, складові і відносні.

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

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

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

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

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

Мал. 7.7. Атрибути файлів MS DOS

Логічна організація файлу

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

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

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

Інша модель файлу - структурований файл. В цьому випадку підтримання структури файлу доручається файлової системи. Файлова система бачить файл як упорядковану послідовність логічних записів. ФС надає додатком доступ до запису, а вся подальша обробка даних, що містяться в цьому записі, виконується додатком!

Відомо п'ять фундаментальних способів організації файлів [10]:

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

При виборі способу організації файлу потрібно враховувати кілька критеріїв:

• швидкість доступу,
• легкість оновлення,
• економність зберігання,
• простота обслуговування,
• надійність.

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

Мал. 7.8. змішаний файл

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

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

Мал. 7.9. послідовний файл

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

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

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

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

Мал. 7.10. Індексного-послідовний файл

Для пошуку потрібного запису по її ключу спочатку виконується пошук в індексному файлі. Після того як в ньому знайдено найбільше значення ключа, яке не перевищує шукане, триває пошук в головному файлі. Наприклад, нехай послідовний файл (головний) містить 1 млн записів. Для пошуку певного ключового значення необхідно в середньому 0,5 млн операцій доступу до записів. Якщо створити індексний файл. що містить 1000 елементів, то потрібно в середньому 500 операцій доступу до індексного файлу, після чого ще потрібно в середньому 500 операцій доступу до головного файлу. В результаті середня довжина пошуку зменшилася з 0,5 млн до 1000. Ще кращого результату можна досягти, використовуючи багаторівневу індексацію. При цьому нижній рівень індексного файлу розглядається як послідовний файл. для якого створюється індексний файл верхнього рівня.

Доповнення до файлу обробляються наступним чином. У кожного запису головного файлу міститься додаткове поле. невидиме для додатка і є покажчиком на файл переповнення. Якщо у файлі проводиться вставка нового запису, вона додається в файл переповнення. Запис в головному файлі, безпосередньо передує новому записі в логічній послідовності, оновлюється і вказує на новий запис у файлі переповнення. Час від часу виконується злиття індексного послідовного файлу з файлом переповнення.

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

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

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

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