Прості зв'язні списки

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

Розміщення файлів з використанням зв'язних списків надає такі переваги:

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

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

· можливість динамічної зміни розміру файла;

· простота реалізації керування вільними блоками, яке принципово не відрізня­ється від керування розміщенням файлів. Цей підхід, однак, не позбавлений і серйозних недоліків:

· відсутність ефективної реалізації випадкового доступу до файла: для того щоб одержати доступ до кластера з номером n, потрібно прочитати всі кластери файла з номерами від 1 до n-1;

· зниження продуктивності тих застосувань, які зчитують дані блоками, за роз­міром рівними степеню числа 2 (а таких застосувань досить багато): частина будь-якого кластера повинна містити номер наступного, тому корисна інфор­мація в кластері займає обсяг, не кратний його розміру (цей обсяг навіть не є степенем числа 2);

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

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

з них є використання таблиці розміщення файлів.

Зв'язні списки з таблицею розміщення файлів

Цей підхід (рис. 12.4) полягає в тому, що всі посилання, які формують списки кластерів файла, зберігаються в окремій ділянці файлової системи фіксованого розміру, формуючи таблицю розміщення файлів (File Allocation Table, FAT). Еле­мент такої таблиці відповідає кластеру на диску і може містити:

· номер наступного кластера, якщо цей кластер належить файлу і не є його ос­таннім кластером;

· індикатор кінця файла, якщо цей кластер є останнім кластером файла;

· індикатор, який показує, що цей кластер вільний.

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

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

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

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

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

Також руйнування обох копій FAT (внаслідок апаратного збою або дії програми-зловмисника, наприклад, комп'ютерного вірусу) робить відновлення даних дуже складною задачею, яку не завжди можна розв'язати.

Лекція №3.

Тема: Індексоване розміщення файлів

План:

1. Індексоване розміщення файлів (Л1 ст.290-291).

2. Структура індексних дескрипторів,розріджені файли (Л1 ст.291-293).

3. Організація каталогів (Л1 ст. 293-294).

4. Облік вільних кластерів (Л1 ст.294).

1.

Базовою ідеєю ще одного підходу до розміщення файлів є перелік адрес всіх кла­стерів файла в його заголовку. Такий заголовок файла дістав назву індексного де­скриптора, або і-вузла (іnode), а сам підхід - індексованого розміщення файлів.

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

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

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

2.

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

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

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

Одне з компромісних розв'язань цієї задачі, яке застосовується вже багато ро­ків у UNIX-системах, зображене на рис. 12.6. Під час його опису замість терміна «кластер» вживатимемо його синонім «дисковий блок».

У цьому разі індексний дескриптор містить елементи різного призначення.

· Частина елементів (зазвичай перші 12) безпосередньо вказує на дискові бло­ки, які називають прямими (direct blocks). Отже, якщо файл може вміститися у 12 дискових блоках (за розміру блоку 4 Кбайт максимальний розмір такого файла становитиме 4096 х 12 = 49 152 байти), усі ці блоки будуть прямо адре­совані його індексним дескриптором і жодних додаткових структур даних не буде потрібно.

· Якщо файлу необхідно для розміщення даних більше, ніж 12 дискових блоків, використовують непряму адресацію першого рівня. У цьому разі 13-й елемент індексного дескриптора вказує не на блок із даними, а на спеціальний непря­мий блок першого рівня (single indirect block). Він містить масив адрес на­ступних блоків файла (за розміру блоку 4 Кбайт, а адреси - 4 байти в ньому міститимуться адреси 1024 блоків, при цьому максимальний розмір файла бу­де 4096 х (12 + 1024) = 4 234 456 байт).

· Якщо файлу потрібно для розміщення більше ніж 1024 + 12 = 1036 дискових блоків, використовують непряму адресацію другого рівня. 14-й елемент ін­дексного дескриптора в цьому разі вказуватиме на непрямий блок другого рівня (double indirect block). Такий блок містить масив з 1024 адрес непрямих блоків першого рівня, кожен із них, як зазначалося, містить масив адрес дис­кових блоків файла. Тому за допомогою такого блоку можна адресувати 1024² додаткових блоків.

· Нарешті, якщо файлу потрібно більше ніж 1036 + 1024² дискових блоків, ви­користовують непряму адресацію третього рівня. Останній 15-й елемент ін­дексного дескриптора вказуватиме на непрямий блок третього рівня (triple in­direct block), що містить масив з 1024 адрес непрямих блоків другого рівня, даючи змогу адресувати додатково 1024³ дискових блоків.

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

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

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

Розріджені файли

Багато операційних систем не зберігають покажчики на дискові блоки файлів у їхніх індексних дескрипторах, поки до них не було доступу для записування. Фрагменти, до яких цього доступу не було з моменту створення файла, назива­ють «дірами» (holes), дисковий простір під них не виділяють, але під час розра­хунку довжини файла їх враховують. У разі читання вмісту «діри» повертають блоки, заповнені нулями, звертання до диска не відбувається.

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

3.

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

Елементи каталогу.

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

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

Організація списку елементів каталогу.

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

Організація підтримки довгих імен файлів

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

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

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

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

4.

Окрім урахування кластерів, виділених під файли, файлові системи повинні вести облік вільних кластерів. Це необхідно для того щоб система могла ефективно виділяти дисковий простір під нові файли. Найчастіше використовують два способи керування вільним дисковим простором:

· Бітовий масив - бітова карта кластерів, у якій кожен біт відповідає одному кластеру на диску. Якщо відповідний кластер вільний, біт дорівнює 1, якщо зайнятий-0. Головна перевага цього підходу в можливості його апаратної реалізації за рахунок простого алгоритму (пошук першого ненульового біта), що дає змогу досягти максимальної швидкості.

· Зв’язний список вільних кластерів – використовують тоді, коли зв’язний список застосовується для розміщення файлів. До цього списку заносяться адреси вільних кластерів на диску. Елементами списку є кластери з адресами(номерами) вільних кластерів.

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

Лекція №4.

Тема: Надійність файлових ситем.

План:

1. Оптимізація продуктивності під час розробки файлових систем (Л1 ст.295-296).

2. Надійність файлових систем (Л1 ст. 303-304).

3. Резервне копіювання (Л1 ст. 304-305).

4. Фізичне та логічне архівування. (Л1 ст. 305).

5. Системне відновлення у Windows XP (Л1 ст. 305).

6. Журнальні файлові системи (Л1 ст. 309-310).

1.

Розглянемо, яким чином можна оптимізувати продуктивність файлової системи зміною структур даних і алгоритмів, які в ній застосовують. У викладі використо­вуватимемо класичний приклад оптимізації традиційної файлової системи вихід­ної версії UNIX під час розроблення системи Fast File System (FFS) для BSD UNIX (у наш час ця файлова система також відома як ufs).

Традиційна файлова система UNIX складається із суперблока (що містить номери блоків файлової системи, поточну кількість файлів, покажчик на список вільних блоків), ділянки індексних дескрипторів і блоків даних (рис. 12.7). Розмір блока фіксований і становить 512 байт. Вільні блоки об'єднані у список.

Супер-блок

Індексні дескриптори

Блоки даних (по 512 байт)

Рис. 12.7. Традиційна файлова система UNIX

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

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

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

До розв'язання цих проблем під час розробки файлової системи FFS були за­пропоновані декілька підходів.

Насамперед, у цій системі було збільшено розмір дискового блока (у FFS використовували два розміри блока: 4 і 8 Кбайт). Для того щоб уникнути внутрішньої фрагментації (яка завжди зростає зі збільшенням розміру блока), було запропоновано в разі необхідності розбивати невикористані блоки на части­ни меншого розміру - фрагменти, які можна використати для розміщення неве­ликих файлів. Мінімальний розмір фрагмента дорівнює розміру сектора диска, тому було використано фрагменти на 1 Кбайт.

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

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

Внаслідок реалізації цих і деяких інших рішень пропускна здатність файлової системи зросла в 10-20 разів (до 40 % можливостей диска). На підставі цього прикладу можна зробити такі висновки:

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

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

· використання бітової карти вільних блоків теж спричиняє підвищення про­дуктивності.

Ідеї, що лежать в основі FFS, вплинули на особливості проектування файло­вої системи ext2fs - основної файлової системи Linux.

2.

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

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

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

Щоб забезпечити відновлення після системного збою, можна

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

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

· зберегти інформацію про останні виконані операції і під час першого заванта­ження після збою повторити ці операції.

3.

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

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

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

· Крім того, у разі регулярного створення резервних копій є сенс організувати інкрементне архівування (increment backup), коли зберігаються тільки ті дані, які змінились із часу створення останньої копії. Є різні підходи до організації інкрементних архівів. Можна робити повну резервну копію через більший проміжок часу (наприклад, через тиждень), а інкрементні копії - додатково із меншим інтервалом (наприклад, через добу); можна зробити повну копію один раз, а далі обмежуватися тільки інкрементними копіями. Основною пробле­мою тут є ускладнення процедури відновлення даних.

У момент створення резервної копії важливим є забезпечення несуперечливості файлової системи. В ідеалі резервну копію треба створювати, коли дані фай­лової системи не змінюються (з нею не працюють інші процеси). На практиці цього домогтися складно, тому використовують спеціальні засоби, які «фіксують» стан системи на деякий момент часу.

4.

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

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

5.

Розглянемо приклад організації резервного копіювання на рівні ОС. Служба сис­темного відновлення (System Restore) Windows ХР дає змогу повертати систему в точку відновлення (restore point) - заздалегідь відомий стан, у якому вона пере­бувала в минулому. За замовчуванням точку відновлення створюють кожні 24 го­дини роботи системи, крім того, можна задавати такі точки явно (наприклад, під час встановлення програмного забезпечення).

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

Під час виконання операції відновлення (Restore) системні файли копіюють із каталогу точки відновлення у системний каталог Windows, після чого відновлю­ють змінені файли користувача на підставі інформації із журналу відновлення.

6.

Великий обсяг дисків робить виконання програми перевірки і відновлення під час завантаження після збою досить тривалим процесом (для диска розміром у десятки Гбайтів така перевірка може тривати кілька годин). У деяких ситуаціях (наприклад, на серверах баз даних з оперативною інформацією) подібні затримки із відновленням роботоздатності системи після кожного збою можуть бути недо­пустимими. Необхідно організувати збереження інформації таким чином, щоб відновлення після збою не вимагало перевірки всіх структур даних на диску. Спроби розв'язати цю проблему привели до виникнення журнальних файлових систем (logging file systems).

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

Основна ідея таких файлових систем - виконання будь-якої операції зміни даних на диску у два етапи.

1. Спочатку інформацію зберігають у журналі (у ньому створюють новий запис). Таку операцію називають випереджувальним записуванням (write-ahead) або веденням журналу (journaling).

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

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

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

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

Є різні підходи до того, яка інформація має зберігатися в журналі.

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

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

Програма відновлення файлів має розрізняти дві ситуації.

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

· Збій відбувся після підтвердження зміни журналу. За цієї ситуації потрібно відновити дані на підставі інформації журналу (такий процес ще називають відкатом уперед — rolling forward).

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

Сучасні операційні системи все більше переходять до використання журнальних файлових систем; наприклад, для Linux є декілька їх реалізацій (ext3fs, ReiserFS, XFS). Файлова система NTFS також підтримує ведення журналу.

Розділ 7. Керування пристроями вводу-виведення.

(аудиторних-8/6г., самостійних- 10/6г.)

Лекція №1.

Тема: Основні функції підсистеми вводу-виведення.

План:

1. Завдання підсистеми введення-виведення (Л1 ст. 358).

2. Забезпечення ефективності доступу до пристроїв (Л1 ст. 359).

3. Забезпечення спільного використання зовнішніх пристроїв (Л1 ст. 359).

4. Універсальність інтерфейсу прикладного програмування (Л1 ст. 359-360).

5. Універсальність інтерфейсу драйверів пристроїв (Л1 ст. 360-361).

6. Організація підсистеми введення –виведення (Л1 ст. 361-362).

1.

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

· ефективність (можливість використання ОС всіх засобів оптимізації, які на­дає апаратне забезпечення), спільне використання і захист зовнішніх при­строїв за умов багатозадачності;

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

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

2.

Забезпечення ефективності вимагає розв'язання кількох важливих задач.

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

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

3.

Під час спільного використання зовнішніх пристроїв мають виконуватися певні умови.

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

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

· У разі спільного використання пристрою треба розподілити операції введен­ня-виведення різних процесів, для того щоб уникнути «накладок» даних одних процесів на дані інших (наприклад, під час спільного використання принтера важливо відрізняти одні задачі від інших і не переходити до друкування ре­зультатів наступної задачі до того, як завершилося виведення попередньої).

4.

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

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

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

2. Надати прикладним програмам можливість взаємодіяти із драйвером при­строю безпосередньо. Для цього звичайно пропонують універсальний систем­ний виклик (в UNIX його називають ioctl), у Windows ХР - DeviceIoControl (), параметри якого задають необхідний драйвер, команду, яку потрібно виконати, і дані для неї.

5.

Як відомо, драйвер пристрою - це програмний модуль, що керує взає­модією ОС із конкретним зовнішнім пристроєм.

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

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

Зручність середовища розробки драйверів визначає набір функцій і шаблонів, наданих програмістові. Часто набір засобів, призначений для розробки драйверів під конкретну операційну систему, постачають розробники цієї ОС у вигляді ок­ремого продукту, який називають DDK (Driver Development Kit). У нього вхо­дять заголовні файли, бібліотеки, можливо, спеціальні версії компіляторів і налагоджувачів, а також документація.

6.

Загальна структура підсистеми введення-виведення показана на рис. 15.1.

Розглянемо особливості організації такої підсистеми.

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

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

♦ Драйвери пристроїв теж розглядають на кількох рівнях. Поряд із низькорівневими апаратними драйверами для керування конкретними пристроями є драй­вери вищого рівня. Вони взаємодіють із апаратними драйверами і на підставі отриманих від них даних виконують складніші завдання. Так, над драйвером відеокарти можна розмістити драйвери, які реалізовуватимуть складні гра­фічні примітиви (наприклад, аналогічні рівню GDI у Windows-системах), а над апаратними драйверами дискових пристроїв - драйвери файлових систем. Як наслідок, код драйверів кожного рівня спрощується, кожен із них тепер роз­в'язує меншу кількість завдань.

Лекція №3.

Тема: Способи виконання операцій введення-виведення.

План:

1. Символьні, блокові та мережні драйвери пристроїв (Л1 ст. 362).

2. Відокремлення механізму від політики за допомогою драйверів пристроїв (Л1 ст. 363).

3. Способи виконання операцій введення-виведення (Л1 ст.363).

4. Опитування пристроїв (Л1 ст. 363-364).

5. Введення-виведення, кероване перериваннями (Л1 ст. 364-366).

6. Прямий доступ до пам`яті (Л1 ст. 366-367).

1.

Ще одна важлива класифікація драйверів уперше з'явилася в UNIX і відтоді її широко використовують, оскільки вона добре відображає специфіку різних при­строїв. Пристрої та драйвери відповідно до цієї класифікації розділяються на три категорії: блокові або блок-орієнтовані (block-oriented, block), символьні або байт-орієнтовані (character-oriented, character) і мережні (network).

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

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

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

2.

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

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

3.

Зовнішній пристрій взаємодіє із комп'ютерною системою через точку зв'язку, яку називають портом (port). Якщо кілька пристроїв з'єднані між собою і можуть об­мінюватися повідомленнями відповідно до заздалегідь визначеного протоколу, то кажуть, що вони використовують шину (bus).

Як відомо, пристрої зв'язуються із комп'ютером через контролери. Є два базо­ві способи зв'язку із контролером: через порт введення-виведення (I/O port) і ві­дображувану пам'ять (memory-mapped I/O). У першому випадку дані пересила­ють за допомогою спеціальних інструкцій, у другому - робота із певною ділян­кою пам'яті спричиняє взаємодію із контролером.

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

Спілкування із контролером через порт звичайно зводиться до використання чотирьох регістрів. Команди записують у керуючий регістр (control), дані - у ре­гістр виведення (data-out), інформація про стан контролера може бути зчитана із регістра статусу (status), дані від контролера - із регістра введення (data-in). Ядро ОС має реєструвати всі порти введення-виведення і діапазони відображува­ної пам'яті, а також інформацію про використання пристроєм порту і діапазону.

4.

Припустимо, що контролер може повідомити, що він зайнятий, увімкнувши біт busy регістра статусу. Застосування повідомляє про команду записування вми­канням біта wrіte командного регістра, а про те, що є команда - за допомогою біта сгеасіу того самого регістра. Послідовність кроків базового протоколу взаємодії з контролером (квітування, handshaking), наведено нижче.

1. Застосування у циклі зчитує біт busy, поки він не буде вимкнутий.

2. Застосування вмикає біт write керуючого регістра і відсилає байт у регістр ви­ведення.

3. Застосування вмикає біт сгеасіу.

4. Коли контролер зауважує, що біт сгеасіу увімкнутий, то вмикає біт busy.

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

6. Контролер очищує біти сгеасіу і busy, показуючи, що операція завершена.

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

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

5.

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

Рівні переривань

Насамперед необхідно мати можливість скасовувати або відкладати обробку пе­реривань під час виконання важливих дій.

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

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

Встановлення оброблювачів переривань

Контролер переривань здійснює роботу з перериваннями на апаратному рівні. Він є спеціальною мікросхемою, що дає змогу відсилати сигнал процесору різними лініями. Процесор вибирає оброблювач переривання, на який потрібно перейти, на підставі номера лінії, що нею прийшов сигнал. її називають лінією запиту перериван­ня або просто лінією переривання (IRQ line). У старих архітектурах застосовували­сяконтролери переривань, розраховані на 15-16 ліній переривання і на один проце­сор, сучасні системи мають спеціальні розширені програмовані контролери переривань (Advanced Programmable Interrupt Controllers, APIC), які реалізують багато ліній пе­реривання (наприклад, для стандартного АРІС фірми Intel таких ліній 255) і корект­но розподіляють переривання між процесорами за умов багатопроцесорних систем.

Ядро ОС зберігає інформацію про всі лінії переривань, доступні у системі. Драй­вер пристрою дає запит каналу переривання (ÎRQ) перед використанням (вста­новленням оброблювача) і вивільняє після використання. Крім того, різні драй­вери можуть спільно використовувати лінії переривань.

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

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

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

· Драйвер може використати ці номери прямо, оскільки для деяких стандарт­них пристроїв номер лінії переривання документований і незмінний (або, як для паралельного порту, однозначно залежить від базової адреси відображу­ваної пам'яті). Але так можна робити далеко не для всіх пристроїв.

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

· І, нарешті, найкращим є підхід, за якого пристрій сам «повідомляє», який но­мер переривання він використає. У цьому разі завданням драйвера є просте визначення цього номера, наприклад, читанням регістра статусу одного із пор­тів введення-виведення пристрою або спеціальної ділянки відображуваної па­м'яті. Більшість сучасних пристроїв допускають таке визначення конфігурації. До них належать, наприклад, усі пристрої шини РСІ (для них це визначено специфікацією, інформацію зберігають у спеціальному просторі конфігура­ції), а також ISA-пристрої, що підтримують специфікацію Plug and Play.

6.

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

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

Усе це спонукало до розробки контролерів прямого доступу до пам'яті (direct memory access, DMA). Такий контролер сам керує пересиланням блоків даних від пристрою безпосередньо у пам'ять, не залучаючи до цього процесора. Блоки да­них, які пересилають, завжди набагато більші, ніж розрядність процесора, на­приклад вони можуть бути завдовжки 4 Кбайт. Схема введення-виведення при цьому наприклад, буде такою:

· процесор дає команду DMA-контролеру виконати читання блоку від прист­рою, разом із командою він відсилає контролеру адресу буфера для введен­ня-виведення (такий буфер має бути у фізичній пам'яті);

· DMA-контролер починає пересилання, процесор у цей час може виконувати інші інструкції;

· після завершення пересилання всього блоку DMA-контролер генерує перери­вання;

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

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

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

Лекція №3.

Тема: Введення-виведення в режимі ядра та користувача.

План:

1. Планування операцій введення-виведення ядра (Л1 ст.367-368).

2. Буферизація пристроїв В/В в режимі ядра (Л1 ст.368-370).

3. Використання спулінгу в режимі ядра (Л1 ст.371-372).

4. Синхронне введення-виведення в режимі кристувача (Л1 ст.373).

5. Асинхронне введення-виведення (Л1 ст.377-378).

1.

Планування введення-виведення реалізоване як середньотермінове плану­вання. Як відомо, з кож­ним пристроєм пов'язують чергу очікування, під час виконання блокувального виклику (такого як read() або fcntl ()) потік поміщають у чергу для відповідного пристрою, з якої його звичайно вивільняє оброблювач переривання. Різним пристроям можуть присвоювати різні пріоритети.

Ще одним прикладом планування введення-виведення є дискове планування.

2.

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

Необхідність реалізації буферизації

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

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

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

· Необхідність підтримки для застосування семантики копіювання (copy se­mantics). Вона полягає в тому, що інформація, записана на диск процесом, має зберігатися в тому вигляді, у якому вона перебувала у пам'яті в момент запи­сування, незалежно від змін, зроблених після цього.

Способи реалізації буферизації

Розглянемо різні способи реалізації буферизації (рис. 15.2).

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

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

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

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

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

Буферизація і кешування

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

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

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

3.

Спулінг (spooling) - технологія виведення даних із використанням буфера, що працює за принципом FIFO. Такий буфер називають спулом (spool) або ділянкою спула (spool area).

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

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

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

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

4.

У більшості випадків введення-виведення на рівні апаратного забезпечення керо­ва

Дата добавления: 2014-10-23