Область даних диска, відведену для зберігання файлів, можна представити як лінійну послідовність адресуються блоків (секторів). Розміщуючи файли в цій області, ОС повинна відвести для кожного файлу необхідну кількість блоків і зберегти інформацію про те, в яких саме блоках розміщений даний файл. Існують два основних способи використання дискового простору для розміщення файлів.
· Безперервне розміщення характеризується тим, що кожен файл займає безперервну послідовність блоків.
· Сегментоване розміщення означає, що файли можуть розміщуватися «по шматочках», тобто один файл може займати кілька несуміжних сегментів різної довжини. Обидва способи розміщення показані на рис. 3-1.
Рис. 1‑10
Безперервне розміщення має два серйозних гідності.
· Інформація про розміщення файлу дуже проста і займає мало місця. Фактично достатньо зберігати два числа: номер початкового блоку файлу і число займаних блоків (або розмір файлу в байтах, по якому легко обчислити число блоків).
· Доступ до будь-якої позиції у файлі виконується швидко, оскільки, знаючи зміщення від початку файлу, легко можна обчислити номер потрібного блоку та прочитати відразу цей блок, не читаючи попередні блоки.
На жаль, недоліки неперервного розподілу ще більш вагомі.
· При створенні файлу потрібно заздалегідь знати його розмір, щоб знайти і зарезервувати на диску область достатньої величини. Подальше можливе збільшення файлу досить утруднено, тому що після кінця файлу може не виявитися досить вільного місця. Фактично замість збільшення файлу зазвичай доводиться заново створювати файл більшого розміру в іншому місці, переписувати в нього дані і видаляти старі файли. Але таке рішення вимагає багато часу на читання і запис даних і, крім того, знижує надійність зберігання даних, оскільки помилка при читанні або запису набагато більш ймовірна, ніж псування даних, «спокійно лежать» на диску.
· В ході звичайної експлуатації файлової системи, після багаторазового створення і видалення файлів різної довжини, вільний простір на диску виявляється розбитим на невеликі шматочки. Сумарний обсяг вільного місця на диску може бути достатньо великим, але створити файл пристойного розміру не вдається, для нього немає безперервній області потрібної довжини. Це явище носить назву фрагментації диска. Для боротьби з ним доводиться використовувати спеціальну процедуру дефрагментації, яка переміщує всі файли, розміщуючи їх упритул один до одного від початку області даних диска. Але така процедура вимагає багато часу, знижує, як сказано вище, надійність і посилює проблеми у випадку, якщо пізніше потрібно буде збільшити файл.
Сегментоване розміщення позбавлене першого з недоліків безперервного: при створенні файлу йому зазвичай взагалі не виділяють пам'ять, а потім, у міру зростання розміру файлу, йому можуть бути виділені будь-які вільні сегменти на диску, незалежно від їх довжини.
Не так просто з фрагментацією. Звичайно, на відміну від безперервного розміщення, при сегментованому ніяка фрагментація не завадить системі використовувати всі блоки, наявні на диску. Однак послідовне читання з сегментованого файлу може виконуватися істотно повільніше за рахунок необхідності переходити від сегмента до сегмента. Уповільнення особливо помітно, якщо файл виявився розкиданий маленькими шматочками по декількох циліндрах диска. В результаті, час від часу доцільно виконувати дефрагментацію диска, щоб підвищити швидкість доступу до даних. При сегментованому розміщенні дефрагментація означає не тільки об'єднання всіх вільних ділянок диска, але і, головним чином, об'єднання сегментів кожного файлу. Ця процедура виконується значно складніше, ніж дефрагментація при безперервному розміщенні.
Чи можете ви запропонувати хороший алгоритм дефрагментації? Врахуйте, що він повинен ефективно працювати, навіть якщо на диску залишилося всього декілька вільних блоків.
Недоліком сегментованого розміщення є те, що інформація про розміщення файлу в цьому випадку набагато складніше, ніж для безперервного випадку і, що найбільш неприємно, обсяг цієї інформації змінний: чим більше число сегментів займає файл, тим більше потрібно інформації, бо треба перерахувати всі сегменти. Є майже стільки ж способів вирішення цієї проблеми, скільки взагалі придумано різних файлових систем.
Щоб зменшити вплив сегментації на швидкість доступу до даних файлу, в ОС, що використовують сегментоване розміщення, застосовуються різні алгоритми вибору місця для файлу. Їх метою є розмістити файл по можливості в одному сегменті, і лише в крайньому випадку розбивати файл на кілька сегментів.
У сучасних ОС для файлових систем на магнітних дисках практично завжди використовують сегментоване розміщення. Інша річ файлові системи на дисках, призначених тільки для читання (наприклад, CD ROM). Неважко зрозуміти, що в цьому випадку недоліки безперервного розміщення не мають ніякого значення, а його гідності зберігаються.
Ще однією важливою характеристикою розміщення файлів є ступінь його «дробности». До цих пір ми припускали, що файл може займати будь-яке ціле число блоків, а під блоком фактично розуміли сектор диска. Проблема в тому, що для дисків великого об'єму число блоків може бути занадто великим. Припустимо, у деякій файловій системі розмір блоку дорівнює 512 байт, а для зберігання номерів блоків файлу використовуються 16-розрядні числа. У цьому випадку розмір області даних диска не зможе перевищити 512 * 216 = 32 Мб, що нині смішно. Звичайно, можна перейти до використання 32-розрядних номерів блоків, але тоді сумарний розмір інформації про розміщення всіх файлів на диску стає занадто великим. Звичайний вихід з цієї скрути полягає в тому, що мінімальною одиницею розміщення файлів вважають кластер (званий в деяких системах блоком або логічним блоком), який приймається рівним 2k секторів, тобто, наприклад, 1, 2, 4, 8, 16, 32 сектора, рідко більше. Кожному файлу відводиться ціле число кластерів, і в інформації про розміщення файлу зберігаються номери кластерів, а не секторів. Збільшення розміру кластерів дозволяє скоротити кількість даних про розміщення файлів «і в довжину і в ширину»: по-перше, для кожного файлу потрібно зберігати інформацію про меншому числі кластерів, а по-друге, зменшується число двійкових розрядів, використовуваних для створення номера кластера ( або при тієї ж розрядності можна використовувати більший диск). Так, при кластері розміром 32 сектора і 16-розрядних номерах можна адресувати до 1 Гб дискової пам'яті.
Використання великих кластерів має свою погану сторону. Оскільки розмір файлу можна вважати випадковою величиною (принаймні, цей розмір ніяк не пов'язана з розміром кластера), то можна приблизно вважати, що в середньому половина останнього кластера кожного файлу залишається незайнятою. Це явище іноді називають внутрішньою фрагментацією (на відміну від описаної вище фрагментації вільного простору диска, яку називають також зовнішньої фрагментацією). Крім того, якщо хоча б один із секторів, що входять в кластер, відзначений як дефектний, то і весь кластер вважається дефектним, тобто не може бути використаний. Очевидно, що при збільшенні розміру кластера зростає і число невикористовуваних секторів диска.
Оптимальний розмір кластера або обчислюється автоматично при форматуванні диска, або задається вручну.
Для нормальної роботи файлової системи потрібно, щоб, крім інформації про розміщення файлів, система зберігала у зручному для використання вигляді інформацію про наявні вільні кластерах диска. Ця інформація необхідна при створенні нових або збільшення існуючих файлів.
Використовуються різні способи подання інформації про вільне місце, деякі з них перераховані нижче.
· Можна зберігати всі вільні кластери як пов'язаний лінійний список, тобто на початку кожного вільного кластера зберігати номер наступного за списком. Недолік такого способу в тому, що утруднюється пошук вільного безперервного фрагмента потрібного розміру, тому складніше оптимізувати розміщення файлів.
· Названий недолік можна перебороти, якщо зберігати список не з окремих кластерів, а з безперервних вільних фрагментів диска. Правда, працювати з таким списком дещо складніше.
· У системах з безперервним розміщенням часто кожен безперервний фрагмент диска описують так само, як файл, але відзначають його прапорцем «вільний».
· Зручний і простий спосіб полягає у використанні бітової карти (bitmap) вільних кластерів. Вона являє собою масив, що містить по одному біту на кожний кластер, причому значення 1 означає «кластер зайнятий», а 0 - «кластер вільний». Для пошуку вільного безперервного фрагмента потрібного розміру система повинна буде переглянути весь масив.