Зв’язаний розподіл пам’яті

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

Позитивним в такому розподілі є те, що послідовні логічні записи розміщуються, як правило, фізично поруч. Це підвищує швидкість доступу.

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

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

Незв’язаний розподіл пам’яті

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

1) Розподіл за допомогою списків секторів

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

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

Цей метод має певні недоліки:

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

2. Також маємо накладні витрати машинного часу для обробки посилок–покажчиків.

3. Зберігання покажчиків в елементах списків веде до зменшення об’єму пам’яті, що надається для зберігання даних.

2) Поблочний розподіл

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

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

Існує декілька способів реалізації систем поблочного розподілення: за допомогою:

- ланцюжків блоків;

- ланцюжків індексних блоків;

- таблиць відображення.

а) Схема з ланцюжками блоків.

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

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

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

б) Схема з ланцюжками індексів.

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

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

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

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

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

в) Схема з таблицями поблочного відображення.

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

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

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

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

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

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

Коли з’являється необхідність виділення нового блоку, відносно легко знайти вільний блок пам’яті, який знаходиться досить близько від інших блоків даного файлу.

Ця схема спрощує операції по установці та вилученню записів.