Управліня зовнішньою пам'яттю

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

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

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

Усі ЕОМ використовують, у загальному випадку, два типи пам’яті: зовнішню — як правило, це дискові накопичувачі, і внутрішню — оперативну

Відповідно управління пам’яттю здійснюється на основі:

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

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

  • метод суміжного розміщення;
  • метод несуміжного розміщення.

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

Методи розподілу пам'яті без використання дискового простору

Розподіл пам'яті фіксованими розділами

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

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

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

При очевидній перевазі - простоті реалізації - даний метод має істотний недолік — неефективне використання наявної оперативної пам’яті: в кожному розділі може виконуватися тільки одна програма, рівень мультипрограмування заздалегідь обмежений числом розділів, не залежно від того, який розмір мають програми. Навіть якщо програма має невеликий обсяг, вона буде займати весь розділ, що приводить до неефективного використання пам'яті. З іншого боку, навіть якщо обсяг оперативної пам'яті машини дозволяє виконати деяку програму, розбивка пам'яті на розділи не дозволяє зробити цього. Розподіл пам'яті розділами змінного розміру У цьому випадку пам'ять машини не поділяється заздалегідь на розділи. При завантаженні задачі виділяється необхідна їй пам'ять при умові, що вистачає місця в пам'яті, інакше задача не приймається на виконання і очікує у черзі вивільнення пам’яті. Після завершення задачі пам'ять звільняється, і на це місце може бути завантажена інша задача. Таким чином, у довільний момент часу оперативна пам'ять являє собою випадкову послідовність зайнятих і вільних ділянок (розділів) довільного розміру.

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

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

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

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

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

Методи розподілу пам'яті з використанням дискового простору. Поняття віртуальної пам'яті

Збільшення функціональності прикладного програмного забезпечення, при обмежених ресурсах оперативної пам’яті, поставило перед розробниками ОС проблему: розміщення в пам'яті програм, розмір яких перевищує вільну пам'ять. Одним із шляхів вирішення цієї проблеми був поділ програм на частини — оверлеї (логічно завершенні блоки програми): 0-ий оверлей починав виконуватися першим, коли він закінчував своє виконання, завантажувався інший оверлей. Всі оверлеї зберігалися на диску і переміщалися між пам'яттю і диском засобами операційної системи, однак поділ програми на частини і планування черговості їх завантаження в оперативну пам'ять здійснювався програмістом. Такий підхід зменшує надійність виконання програми та операційної системи. Розвиток методів організації обчислювального процесу в цьому напрямку привів до появи методу, відомого як віртуальна пам'ять. Віртуальний ресурс — ресурс, що надається користувачу чи програмі користувача таким, що має певні властивості, якими він у дійсності не володіє. Наприклад:

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

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

Операційна система при використанні віртуальної пам'яті повинна вирішувати задачі:

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

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

Сторінковий розподіл Віртуальний адресний простір кожного процесу поділяється на частини однакового, фіксованого для даної системи розміру, що називають віртуальними сторінками. Вся оперативна пам'ять обчислювальної машини також поділяється на частини такого ж розміру, що називають фізичними сторінками (чи блоками). Розмір сторінки вибирається рівним степеням двійки: 512, 1024 і т.д., з метою спрощення алгоритму перетворення адрес. При завантаженні процесу частина його віртуальних сторінок розміщається в оперативній пам'яті, а інші - у дисковій. Суміжні віртуальні сторінки не обов'язково розташовуються в суміжних фізичних сторінках. Сторінкова організація пам'яті — апаратно підтримується процесорами, починаючи з i80386. В оперативній пам'яті знаходяться тільки активні сторінки, а інші розташовані на диску, віртуальній пам’яті. При доступу процесу до пам'яті віртуальна адреса перетворюється модулем управління пам'яттю операційної системи у фізичну адресу сторінки. Доступ здійснюється відразу, якщо сторінка знаходиться в оперативній пам'яті. Якщо дана сторінка знаходиться на диску, то вона спочатку завантажується в оперативну пам'ять. При цьому одна з активних сторінок витісняється на диск. При завантаженні операційна система створює для кожного процесу інформаційну структуру — таблицю сторінок, у якій встановлюється відповідність між номерами віртуальних і фізичних сторінок, завантажених в оперативну пам'ять, або вказується, що віртуальна сторінка вивантажена на диск. Крім того, у таблиці сторінок міститься управляюча інформація: ознака модифікації сторінки; ознака заборони вивантаження (вивантаження певних сторінок може бути заборонене); ознака звертання до сторінки (використовується для підрахунку числа звертань за визначений період часу) та інші дані, що використовуються механізмом віртуальної пам'яті.

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

  1. сторінка, яка найдовше не використовувалася;
  2. перша сторінка, що трапилася;
  3. сторінка, до якої останнім часом було найменше звертань.

У деяких системах використовується поняття робочої множини сторінок. Робоча множина визначається для кожного процесу і являє собою перелік найбільш часто використовуваних сторінок, що повинні постійно знаходитися в оперативній пам'яті і тому не підлягають вивантаженню. Рішення про вивантаження сторінки на диск приймається на основі аналізу атрибуту модифікації обраної сторінки. Якщо сторінка, що вивантажується, з моменту завантаження була модифікована, то її нова версія повинна бути переписана на диск. Якщо ні, то вона може бути просто знищена, тобто відповідна фізична сторінка стає вільною. На продуктивність системи зі сторінковою організацією пам'яті впливають часові витрати, пов'язані з опрацюванням сторінкових переривань і перетворенням віртуальної адреси у фізичну. Якщо сторінкові переривання виникають часто, то система може витрачати велику кількість часу на свопінг сторінок. Щоб зменшити частоту сторінкових переривань, доцільно збільшувати розмір сторінки. Крім того, збільшення розміру сторінки зменшує розмір таблиці сторінок, а значить зменшує витрати пам'яті. З іншого боку, якщо сторінка велика, значить велика і фіктивна область в останній віртуальній сторінці кожної програми, у середньому для кожної програми втрачається половина обсягу сторінки, тому сумарний обсяг, при великій сторінці, може скласти значну величину. Час перетворення віртуальної адреси у фізичну у значній мірі визначається часом доступу до таблиці сторінок. У зв'язку з цим таблицю сторінок розміщають в „швидких” запам’ятовуючих пристроях: це може бути, наприклад, набір спеціальних регістрів чи пам'ять з асоціативним пошуком та кешуванням. Сторінковий розподіл пам'яті може бути реалізований у спрощеному варіанті, без вивантаження сторінок на диск. У цьому випадку всі віртуальні сторінки всіх процесів постійно знаходяться в оперативній пам'яті. Такий варіант сторінкової організації хоча і не надає користувачу віртуальної пам'яті, але майже виключає фрагментацію за рахунок того, що програма може завантажуватися в несуміжні області, а також того, що при завантаженні віртуальних сторінок ніколи не утворяться залишки. Сегментний розподіл При сторінковій організації віртуальний адресний простір процесу поділяється механічно на рівні частини, що не дозволяє диференціювати способи доступу до різних частин програми (сегментів). Наприклад, можна заборонити звертатися з операціями запису і читання в кодовий сегмент програми, а для сегменту даних дозволити тільки читання. Крім того, розбивка програми на "осмислені" частини робить принципово можливим спільне використання одного сегмента кількома процесами. Наприклад: якщо два процеси використовують одну математичну підпрограму, то в оперативну пам'ять може бути завантажена тільки одна копія цієї підпрограми. Віртуальний адресний простір процесу поділяється на сегменти (рис.16), розмір яких визначається програмістом.

Свопінг

Залежно від характеру виконуваних задач одна частина процесів може потребувати досить часто процесорного часу, а інша частина періодично, при настанні певних подій, наприклад виконання сервера для відправлення чи отримання електронної пошти. Одним із методів вивільнення оперативної пам'яті, для процесів, що потребують негайного виконання є свопінг. Свопінг — тимчасове повне вивантаження процесу, що знаходяться в стані чекання, у зовнішню пам’ять. Планувальник операційної системи не виключає перенесені процесу у зовнішню пам’ять із свого розгляду, і при настанні умов активізації процесу, що знаходиться в області свопінга на диску, цей процес переміщається в оперативну пам'ять. Якщо вільного місця в оперативній пам'яті не вистачає, то вивантажується інший процес. При свопінгу, на відміну від розглянутих раніше методів реалізації віртуальної пам'яті, процес переміщається між пам'яттю і диском, і протягом деякого часу процес може бути відсутнім у оперативній пам'яті. Ієрархія запам'ятовуючих пристроїв. Кешування даних Всю пам'ять обчислювальної машини можна представити у вигляді дерева запам'ятовуючих пристроїв рис. 17, що відрізняються середнім часом доступу і вартістю збереження даних у розрахунку на один біт. Для ефективного використання обчислювальних ресурсів необхідна наявність швидкої пам'яті, одночасно з доступною вартістю. Кеш-пам'ять представляє деяке компромісне вирішення цієї проблеми.

Пам'ять обчислювальної машини

  1. внутрішні регістри процесора,
  2. надоперативна пам'ять
  3. оперативна пам'ять
  4. пам’ять на дискових накопичувачах

Зовнішня пам'ять - це сукупність запам'ятовуючих пристроїв і носіїв інформації, використовується для довгострокового зберігання даних і має властивості:

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

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

  1. підвести зчитуючий/записуючий елемент до вказаного місця (сектора);
  2. прочитати дані з вказаного місця (сектора);
  3. записати дані у вказане місце (сектор).

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

  1. Сектор — найменша фізична одиниця збереження даних. Кожний сектор має свою адресу, номер. Нумерація проводиться послідовно.
  2. Доріжка — сектори, що належать одній поверхні і знаходяться на однаковій відстані від осі обертання.
  3. Циліндр — сукупність усіх доріжок, що належать різним поверхням, і знаходяться на однаковій відстані від осі обертання.


Фізичне збереження і доступ до даних на зовнішньому носієві забезпечується:

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

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

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

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

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

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

Типи файлових систем

Файлова система

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

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

Файли ідентифікуються іменами. Користувачі дають файлів символьні імена, при цьому враховуються обмеження ОС як на використовувані символи, так і на довжину імені. До недавнього часу ці межі були досить вузькими. Однак користувачеві набагато зручніше працювати з довгими іменами, оскільки вони дозволяють дати файлу дійсно мнемонічне назву, за яким навіть через досить великий проміжок часу можна буде згадати, що містить цей файл. Тому сучасні файлові системи, як правило, підтримують довгі символьні імена файлів. Наприклад, Windows NT у своїй новій файловій системі NTFS встановлює, що ім'я файлу може містити до 255 символів, не рахуючи завершального нульового символу.

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

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

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

Файли бувають різних типів: звичайні файли, спеціальні файли, файли-каталоги.

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

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

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

У різних файлових системах можуть використовуватися в якості атрибутів різні характеристики, наприклад:

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

Слід зазначити, що не існує єдиного стандарту на файлову систему. Для кожної ОС, відповідно до виконуваних задач, існують “свої” реалізації логічного рівня для роботи з даними, що розрізняються способами організації структур даних. FAT (File Allocation Table) або FAT16 — файлова система операційної системи Dos. Розділ (volume) FAT займає цілу дискету або розділ жорсткого диску. VFat, Fat32 — модифіковані версії FAT16, для операційних систем сімейства Windows 9x/ME. NTFS файлова система для Wіndоws NT, розроблялася як надійна, стійка до апаратних помилок файлова системи. UFS (Unix File System) — перша файлова система для операційної системи UNIX, всі сучасні версії походять від неї. Ext2 — достатньо функціонально розвинена файлова система з сімейства сумісних з Linux. На даний момент вважається найбільш популярною системою. Вона розроблена з врахуванням сумісності з наступними версіями, тому для установки нової версії коду системи не потрібно встановлювати її заново. Sysv — файлові системи System V/386, Coherent і Xenix. Iso9660 — стандартна файлова система для CD-ROM. Досить популярне розширення стандарту CD-ROM, для автоматичної підтримки імен файлів нестандартної довжини. Nfs — мережева файлова система, що забезпечує спільне використання однієї файлової системи кількома комп'ютерами. Hpfs — файлова система, розроблена для OS/2. Minix — одна з перших файлових систем, досить обмежена за своїми можливостями (відсутні деякі параметри, довжина імені файлу обмежена 30-ма символами) і доступних об'ємом (максимум 64 Мб на одну файлову систему). Виконання операцій з файлами Для виконання операцій з файлами, копіювання, вилучення, перейменування, навігації тощо, усі операційні системи забезпечують необхідний мінімум команд .

Деякі команди для роботи з файловою системою

DOS, ОС Windows ХХ (командний рядок), Linux Windows 95 Linux запуск програми на виконання file name file name копіювати copy cp перенести move rn вилучити del mv пошук файлу (файлів) find find створити каталог md mk вилучити каталог del rm ініціалізація файлової системи format mkfs

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

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


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

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

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

Програміст має справу з логічною організацією файлу, представляючи файл у вигляді певним чином організованих логічних записів. Логічна запис - це найменший елемент даних, яким може оперувати програміст при обміні із зовнішнім пристроєм. Навіть якщо фізичний обмін із пристроєм здійснюється великими одиницями, операційна система забезпечує програмістові доступ до окремої логічної запису. На малюнку 2,33 показані кілька схем логічної організації файлу. Записи можуть бути фіксованої довжини або змінної довжини. Записи можуть бути розташовані у файлі послідовно (послідовна організація) або в більш складному порядку, з використанням так званих індексних таблиць, що дозволяють забезпечити швидкий доступ до окремої логічної запису (індексно-послідовна організація). Для ідентифікації запису може бути використано спеціальне поле запису, зване ключем. У файлових системах ОС UNIX і MS-DOS файл має найпростішу логічну структуру - послідовність однобайтових записів.

Фізична організація і адреса файлу

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

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


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

На закінчення розглянемо завдання фізичного розташування файлу шляхом простого перерахування номерів блоків, займаних цим файлом. ОС UNIX використовує варіант даного способу, що дозволяє забезпечити фіксовану довжину адреси, незалежно від розміру файлу. Для зберігання адреси файлу виділено 13 полів. Якщо розмір файлу менше або дорівнює 10 блокам, то номери цих блоків безпосередньо перераховані в перших десяти полях адреси. Якщо розмір файлу більше 10 блоків, то наступне 11-е поле містить адресу блоку, в якому можуть бути розташовані ще 128 номерів наступних блоків файлу. Якщо файл більше, ніж 10 +128 блоків, то використовується 12-е поле, в якому знаходиться номер блоку, що містить 128 номерів блоків, які містять по 128 номерів блоків даного файлу. І, нарешті, якщо файл більше 10 +128 +128 (128, то використовується останніх 13-е поле для потрійний непрямої адресації, що дозволяє задати адресу файлу, який має розмір максимум 10 + 128 + 128 (128 + 128 (128 (128.

Права доступу до файлу

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

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

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

Розрізняють два основних підходи до визначення прав доступу:

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

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

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

  1. переглядається вміст кеш-пам'яті з метою визначення, чи не знаходяться потрібні дані в кеш-пам'яті; кеш-пам'ять не адресується, тому пошук потрібних даних здійснюється по вмісту - значенню поля "адреси в оперативній пам'яті", узятому з запиту;
  2. якщо дані виявляються в кеш-пам'яті, то вони зчитуються з неї, результат передається процесору;
  3. якщо потрібних даних немає, то вони копіюються з оперативної пам'яті в кеш-пам'ять, і результат виконання запиту передається процесору;

При копіюванні даних може виявитися, що в кеш-пам'яті відсутнє вільне місце, тоді, для витіснення з кеш-пам'яті обираються дані, до яких в останній період було найменше звертань. Якщо витіснені дані були модифіковані за час перебування в кеш-пам'яті, то вони переміщаються в оперативну пам'ять. Якщо ж ці дані не були модифіковані, то їх місце в кеш-пам'яті звільняється. На практиці у кеш-пам'ять зчитується не один елемент даних, до якого відбулося звертання, а цілий блок даних, це збільшує ймовірність так званого “влучання у кеш”, тобто перебування потрібних даних у кеш-пам'яті. Покажемо, як середній час доступу до даних залежить від ймовірності влучання у кеш. Нехай маємо основний запам'ятовуючий пристрій із середнім часом доступу до даних t1 і кеш-пам'ять, що має час доступу t2, відповідно t2<t1. Позначимо через t середній час доступу до даних у системі з кеш-пам'яттю, а через p - імовірність влучання у кеш. Відповідно до формули повної імовірності: t = t1((1 - p) + t2(1-p) З неї видно, що середній час доступу до даних у системі з кеш-пам'яттю лінійно залежить від імовірності влучання у кеш і змінюється від середнього часу доступу до основного запам’ятовуючого пристрою (при р=0) до середнього часу доступу безпосередньо до кеш-пам'яті (при р=1). У реальних системах імовірність влучання у кеш складає приблизно 0,9. Високе значення імовірності перебування даних у кеш-пам'яті пов'язано з наявністю в даних об'єктивних властивостей: просторової і часової локальності. Просторова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що найближчим часом відбудеться звертання до сусідніх адрес. Часова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що наступне звертання до цієї ж адреси відбудеться найближчим часом.

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

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

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

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

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

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

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

Вихідні дані:

V - розмір блоку
N - номер першого блоку файлу
S - зміщення логічної запису у файлі

Потрібно визначити на фізичному рівні:

N - номер блоку, що містить необхідну логічну запис
S - зміщення логічної запису в межах блоку
N = N + [S / V], де [S / V] - ціла частина числа S / V
S = R [S / V] - дробова частина числа S / V

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

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

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

Припустимо, наприклад, що файл F має довжину 64 К і відображається на область віртуального адресного простору з початковим адресою 512 К. Після цього будь-яка машинна команда, яка читає вміст байта за адресою 512 К, отримує 0-ій байт цього файлу і т.д. Очевидно, що запис за адресою 512 До + 1100 змінює 1100 байт файлу. При завершенні процесу на диску залишається модифікована версія файлу, як якби він був змінений комбінацією викликів SEEK і WRITE.

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

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

З цього моменту процес може копіювати сегмент-джерело в сегмент-приймач за допомогою звичайного програмного циклу, що використовує команди пересилання в пам'яті типу MOV. Ніякі виклики READ або WRITE не потрібні. Після виконання копіювання процес може виконати виклик Unmap для видалення файлу з адресного простору, а потім завершитися. Вихідний файл DDD буде існувати на диску, як якщо б він був створений звичайним способом.

Хоча відображення файлів виключає потреба у виконанні вводу-виводу і тим самим полегшує програмування, цей спосіб породжує і деякі нові проблеми. По-перше, для системи складно дізнатися точну довжину вихідного файлу, в даному прикладі DDD. Простіше вказати найбільший номер записаної сторінки, але немає способу дізнатися, скільки байт в цій сторінці було записано. Припустимо, що програма використовує тільки сторінку номер 0, і після виконання всі байти все ще встановлені в значення 0 (їх початкове значення). Бути може, файл складається з 10 нулів. А може бути, він складається з 100 нулів. Як це визначити? Операційна система не може це повідомити. Все, що вона може зробити, так це створити файл, довжина якого дорівнює розміру сторінки.

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

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

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

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

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

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

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

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

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