Основні функції та компоненти ядра ОС UNIX

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

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

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

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

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

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

Згадайте хоча б 16-розрядний комп'ютер PDP-11/70, до якого можна було підключити до 2 Мбайт основної пам'яті. Іншим прикладом може служити видатна вітчизняна ЕОМ БЕСМ-6, в якій при 15-розрядної адресації 6-байтових (48-розрядних) машинних слів обсяг основної пам'яті був доведений до 256 Кбайт. Операційні системи цих комп'ютерів тим не менше підтримували віртуальну пам'ять, основним змістом якої було забезпечення захисту користувача програм однієї від одної та надання операційній системі можливості динамічно гнучко перерозподіляти основну пам'ять між одночасно підтримуваними користувацькими процесами.

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

У найбільш простому і найбільш часто використовується випадку сторінкової віртуальної пам'яті кожна віртуальна пам'ять (віртуальна пам'ять кожного процесу) і фізична основна пам'ять представляються що складаються з наборів блоків або сторінок однакового розміру. Для зручності реалізації розмір сторінки завжди вибирається дорівнює кількості, що є ступенем 2. Тоді, якщо загальна довжина віртуального адреси є N (в останні роки це теж завжди деяка ступінь 2 - 16, 32, 64), а розмір сторінки є 2M), то віртуальний адреса розглядається як структура, що складається з двох полів: перше поле займає (N-M +1) розрядів адреси і задає номер сторінки віртуальної пам'яті, друге поле займає (M-1) розрядів і задає зміщення всередині сторінки до адресується елемента пам'яті (у більшості випадків - байти). Апаратна інтерпретація віртуального адреси показана на малюнку 3.1.

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

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

Рис. 3.1. Схема сторінкової організації віртуальної пам'яті

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

Рис. 3.2. Схема сегментно-сторінкової організації віртуальної пам'яті

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

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

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

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

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

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

Найбільш поширеними традиційними алгоритмами (як у глобальному, так в локальному варіантах) є алгоритми FIFO (First In First Out) і LRU (Least Recently Used). При використанні алгоритму FIFO для заміщення вибирається сторінка, яка найдовше залишається приписаний до віртуальної пам'яті. Алгоритм LRU припускає, що заміщати слід ту сторінку, до якої найдовше не відбувалися звернення. Хоча інтуїтивно здається, що критерій алгоритму LRU є більш правильним, відомі ситуації, в яких алгоритм FIFO працює краще (і, крім того, він набагато дешевше реалізується).

Зауважимо ще, що при використанні глобальних алгоритмів, незалежно від конкретного вживаного алгоритму, можливі й теоретично неминучі критичні ситуації, які називаються по-англійськи thrashing (незважаючи на безліч спроб, гарного російського еквівалента так і не вдалося придумати). Розглянемо простий приклад. Нехай на комп'ютері в мультипрограмному режимі виконуються два процеси - П1 у віртуальній пам'яті ВП1 і П2 у віртуальній пам'яті ВП2, причому сумарний розмір ВП1 і ВП2 більше розмірів основної пам'яті. Припустимо, що в момент часу t1 в процесі П1 виникає вимога віртуальної сторінки ВС1. Операційна система обробляє відповідне переривання і вибирає для заміщення сторінку основної пам'яті С2, приписаних до віртуальної сторінці ВС2 віртуальної пам'яті ВП2 (тобто в елементі таблиці сторінок, відповідному ВС2, проставляється прапор відсутності сторінки). Для повної обробки вимоги доступу до ВС1 в загальному випадку буде потрібно два обміну із зовнішньою пам'яттю (перше, щоб записати поточний зміст С2, друге - щоб прочитати копію ВС1). Оскільки операційна система підтримує мультипрограмному режим роботи, то під час виконання обмінів доступ до процесора отримає процес П2, і він, цілком імовірно, може вимагати доступу до своєї віртуальної сторінці ВС2 (яку в нього тільки що забрали). Знову буде оброблятися переривання, і ОС може замінити деяку сторінку основної пам'яті С3, яка приписана до віртуальної сторінці ВС3 в ВП1. Коли закінчаться обміни, пов'язані з обробкою вимоги доступу до ВС1, відновиться процес П1, і він, цілком імовірно, потребують доступу до своєї віртуальної сторінці ВС3 (яку в нього тільки що відібрали). І так далі. Загальний ефект полягає в тому, що безперервно працює операційна система, виконуючи незліченні і безглузді обміни з зовнішньої пам'яттю, а призначені для користувача процеси П1 і П2 практично не просуваються.

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

Єдиним алгоритмом, теоретично гарантує відсутність thrashing, є так званий "оптимальний алгоритм Біледі" (за ім'ям що придумав його угорського математика). Алгоритм полягає в тому, що для заміщення слід вибирати сторінку, до якої в майбутньому найбільш довго не буде звернень. Зрозуміло, що в динамічному середовищі операційної системи точне знання майбутнього неможливо, і в цьому контексті алгоритм Біледі представляє тільки теоретичний інтерес (хоча він з успіхом застосовується практично, наприклад, в компіляторах для планування використання регістрів).

У 1968 році американський дослідник Пітер Деннінг сформулював принцип локальності посилань (званий принципом Деннінг) і висунув ідею алгоритму підкачки, заснованого на понятті робочого набору. У певному сенсі запропонований ним підхід є практично реалізується апроксимацією оптимального алгоритму Біледі. Принцип локальності посилань (недоведені, але підтверджується на практиці) полягає в тому, що якщо в період часу (Tt, T) програма зверталася до сторінок (С1, С2, ..., Сn), то при належному виборі t з великою ймовірністю ця програма буде звертатися до тих же сторінок в період часу (T, T + t). Іншими словами, принцип локальності стверджує, що якщо не занадто далеко заглядати в майбутнє, то можна добре його прогнозувати виходячи з минулого. Набір сторінок (С1, С2, ..., Сn) називається робочим набором програми (або, правильніше, відповідного процесу) в момент часу T. Зрозуміло, що з плином часу робочий набір процесу може змінюватися (як по складу сторінок, так і з їх числа). Ідея алгоритму підкачки Деннінг (іноді званого алгоритмом робочих наборів) полягає в тому, що операційна система в кожний момент часу повинна забезпечувати наявність в основний памяті поточних робочих наборів всіх процесів, яким дозволено конкуренція за доступ до процесора. Ми не будемо вдаватися в технічні деталі алгоритму, а лише зазначимо таке. По-перше, повна реалізація алгоритму Деннінг практично гарантує відсутність thrashing. По-друге, алгоритм реалізуємо (відома, за щонайменше, один його повна реалізація, яка однак вимагає спеціальної апаратної підтримки). По-третє, повна реалізація алгоритму Деннінг викликає дуже великі накладні витрати.

Тому на практиці застосовуються полегшені варіанти алгоритмів підкачки, заснованих на ідеї робочого набору. Один з таких варіантів застосовується і в ОС UNIX (наскільки нам відомо, у всіх версіях системи, що відносяться до галузі System V). Ми коротко опишемо цей варіант у п. 3.1.3. Апаратно-незалежний рівень управління пам'яттю

Матеріал, наведений у цьому розділі, хоча і не відображає в повному обсязі всі проблеми і рішення, пов'язані з управлінням віртуальною пам'яттю, достатній для того, щоб усвідомити важливість і складність відповідних компонентів операційної системи. У будь-якій операційній системі керування віртуальною пам'яттю займає центральне місце. Колись Ігор Сілін (основний розробник відомої операційної системи Дубна для БЕСМ-6) висунув тезу, відомий в народі як "Теза Силина": "Витрати, витрачені на управління віртуальною пам'яттю, окупаються". Я думаю, що будь-який фахівець в області операційних систем погодиться з істинністю цієї тези.

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

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

По-перше, віртуальна пам'ять кожного процесу представляється у вигляді набору сегментів (малюнок 3.3).

Рис. 3.3. Сегментна структура віртуального адресного простору

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

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

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

розділяється сегмент віртуальної пам'яті утворюється при підключенні до неї сегмента розділяється пам'яті (див. п. 3.4.1). За визначенням, такі сегменти призначені для координованого спільного використання декількома процесами. Тому розділяється сегмент повинен допускати доступ з читання та по запису і може поділятися кількома процесами.

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

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

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

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

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

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

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

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

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

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

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

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

Зауважимо, що ми описали найбільш складний алгоритм, коли б то не було що використовувався в ОС UNIX. В останній "фактично стандартної" версії ОС UNIX (System V Release 4) використовується більш спрощений алгоритм. Це глобальний алгоритм, в якому ймовірність thrashing погашається за рахунок своппінга. Використовуваний алгоритм називається NRU (Not Recently Used) або clock. Сенс алгоритму полягає в тому, що процес-stealer періодично очищає ознаки звернення всіх сторінок основної пам'яті, що входять у віртуальну пам'ять процесів (звідси назва "clock"). Якщо виникає потреба в відкачці (тобто досягнуто нижня межа розміру списку описувачів вільних сторінок), то stealer вибирає в якості кандидатів на відкачування перш за все ті сторінки, до яких не було звернень по запису після останньої "очищення" і в яких немає ознаки модифікації (тобто ті, які можна дешевше звільнити). У другу чергу вибираються сторінки, які дійсно потрібно відкачувати. Паралельно з цим працює описаний вище алгоритм своппінга, тобто якщо виникає вимога сторінки, а вільних сторінок немає, то відповідний процес стає кандидатом на своппінг.

На закінчення торкнемося ще одну важливу тему, безпосередньо пов'язану з керуванням віртуальною пам'яттю - копіювання сторінок при спробі запису (copy on write). Як ми відзначали в п. 2.1.7, під час виконання системного виклику fork () ОС UNIX утворює процес-нащадок, що є повною копією свого предка. Тим не менш, у нащадка своя власна віртуальна пам'ять, і ті сегменти, які повинні бути його приватними сегментами, в принципі повинні були б повністю скопіювати. Однак, незважаючи на те, що приватні сегменти допускають доступ і з читання, і за записом, ОС не знає, чи предок або нащадок реально робити запис в кожну сторінку таких сегментів. Тому було б нерозумно проводити повне копіювання приватних сегментів під час виконання системного виклику fork ().

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

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

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

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

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

В останні роки в зв'язку із широким поширенням так званих симетричних мультипроцесорних архітектур (Symmetric Multiprocessor Architectures - SMP) в ОС UNIX було запроваджено механізм легковагих процесів (light-weight processes), або ниток, або потоків управління (threads). Говорячи по-простому, нитка - це процес, що виконуються в вірт