- •1.1. Поняття операційної системи, її призначення та функції
- •1.1.1. Поняття операційної системи
- •1.1.2. Призначення операційної системи
- •1.1.3. Операційна система як розширена машина
- •1.1.4. Операційна система як розподілювач ресурсів
- •1.2. Історія розвитку операційних систем
- •1.3. Класифікація сучасних операційних систем
- •1.4. Функціональні компоненти операційних систем
- •1.4.1. Керування процесами й потоками
- •1.4.2. Керування пам'яттю
- •1.4.3. Керування введенням-виведенням
- •1.4.4. Керування файлами та файлові системи
- •1.4.5. Мережна підтримка
- •1.4.6. Безпека даних
- •1.4.7. Інтерфейс користувача
- •2.1. Базові поняття архітектури операційних систем
- •2.1.1. Механізми і політика
- •2.1.2. Ядро системи. Привілейований режим і
- •2.2. Реалізація архітектури операційних систем
- •2.2.1. Монолітні системи
- •2.2.2. Багаторівневі системи
- •2.2.3. Системи з мікроядром
- •2.2.4. Концепція віртуальних машин
- •2.3.1. Взаємодія ос і апаратного забезпечення
- •2.3.2. Взаємодія ос і виконуваного програмного коду
- •2.4.1. Базова архітектура unix
- •2.4.2. Архітектура Linux
- •2.5. Особливості архітектури: Windows хр
- •2.5.1. Компоненти режиму ядра
- •2.5.2. Компоненти режиму користувача
- •2.5.3. Об'єктна архітектура Windows хр
- •3.1. Базові поняття процесів і потоків
- •3.1.1. Процеси і потоки в сучасних ос
- •3.1.2. Моделі процесів і потоків
- •3.1.3. Складові елементи процесів і потоків
- •3.2. Багатопотоковість та її реалізація
- •3.2.1. Поняття паралелізму
- •3.2.2. Види паралелізму
- •3.2.3. Переваги і недоліки багатопотоковості
- •3.2.4. Способи реалізації моделі потоків
- •3.3. Стани процесів і потоків
- •3.4. Опис процесів і потоків
- •3.4.1. Керуючі блоки процесів і потоків
- •3.4.2. Образи процесу і потоку
- •3.5. Перемикання контексту й обробка переривань
- •3.5.1. Організація перемикання контексту
- •3.5.2. Обробка переривань
- •3.6. Створення і завершення процесів і потоків
- •3.6.1.Створення процесів
- •3.6.2.Ієрархія процесів
- •3.6.3.Керування адресним простором під час створення процесів
- •3.6.4. Особливості завершення процесів
- •3.6.5. Синхронне й асинхронне виконання процесів
- •3.6.6. Створення і завершення потоків
- •4.1. Загальні принципи планування
- •4.1.1. Особливості виконання потоків
- •4.1.2. Механізми і політика планування
- •4.1.3. Застосовність принципів планування
- •4.2. Види планування
- •4.2.1. Довготермінове планування
- •4.2.2. Середньотермінове планування
- •4.2.3. Короткотермінове планування
- •4.3. Стратегії планування. Витісняльна і невитісняльна багатозадачність
- •4.4. Алгоритми планування
- •4.4.1. Планування за принципом fifo
- •4.4.2. Кругове планування
- •4.4.3. Планування із пріоритетами
- •4.4.4. Планування на підставі характеристик подальшого виконання
- •4.4.5. Багаторівневі черги зі зворотним зв'язком
- •4.4.6. Лотерейне планування
- •4.5. Реалізація планування в Linux
- •4.5.1. Планування процесів реального часу в ядрі
- •6.1. Види міжпроцесової взаємодії
- •6.1.1.Методи розподілюваної пам'яті
- •6.1.2.Методи передавання повідомлень
- •6.1.3.Технологія відображуваної пам'яті
- •6.1.4.Особливості міжпроцесової взаємодії
- •6.2. Базові механізми міжпроцесової взаємодії
- •6.2.1. Міжпроцесова взаємодія на базі спільної пам'яті
- •6.2.2. Основи передавання повідомлень
- •6.2.3. Технології передавання повідомлень
- •8.1. Основи технології віртуальної пам'яті
- •8.1.1. Поняття віртуальної пам'яті
- •8.1.2. Проблеми реалізації віртуальної пам'яті. Фрагментація пам'яті
- •8.1.4. Підхід базового і межового регістрів
- •8.2. Сегментація пам'яті
- •8.2.1. Особливості сегментації пам'яті
- •8.2.2. Реалізація сегментації в архітектурі іа-32
- •8.3. Сторінкова організація пам'яті
- •8.3.1. Базові принципи сторінкової організації пам'яті
- •8.3.2. Порівняльний аналіз сторінкової організації пам'яті та сегментації
- •8.3.3. Багаторівневі таблиці сторінок
- •8.3.4. Реалізація таблиць сторінок в архітектурі іа-32
- •8.3.5. Асоціативна пам'ять
- •8.4. Сторінково-сегментна організація пам'яті
- •8.5. Реалізація керування основною пам'яттю: Linux
- •8.5.1. Використання сегментації в Linux. Формування логічних адрес
- •8.5.2. Сторінкова адресація в Linux
- •8.5.3. Розташування ядра у фізичній пам'яті
- •8.5.4.Особливості адресації процесів і ядра
- •8.5.5.Використання асоціативної пам'яті
- •8.6. Реалізація керування основною пам'яттю: Windows хр
- •8.6.1.Сегментація у Windows хр
- •8.6.2.Сторінкова адресація у Windows хр
- •8.6.3.Особливості адресації процесів і ядра
- •8.6.4. Структура адресного простору процесів і ядра
- •11.1. Поняття файла і файлової системи
- •11.1.1. Поняття файла
- •11.1.2.Поняття файлової системи
- •11.1.3.Типи файлів
- •11.1.4. Імена файлів
- •11.2. Організація інформації у файловій системі
- •11.2.1. Розділи
- •11.2.2. Каталоги
- •11.2.3. Зв'язок розділів і структури каталогів
- •11.3. Зв'язки
- •11.3.1. Жорсткі зв'язки
- •11.3.2. Символічні зв'язки
- •11.4. Атрибути файлів
- •11.5. Операції над файлами і каталогами
- •11.5.1. Підходи до використання файлів процесами
- •12.1. Базові відомості про дискові пристрої
- •12.1.1. Принцип дії жорсткого диска
- •12.1.2. Ефективність операцій доступу до диска
- •12.2. Розміщення інформації у файлових системах
- •12.2.1. Фізична організація розділів на диску
- •12.2.2. Основні вимоги до фізичної організації файлових систем
- •12.2.3. Неперервне розміщення файлів
- •12.2.4. Розміщення файлів зв'язними списками
- •12.2.5. Індексоване розміщення файлів
- •12.2.6. Організація каталогів
- •15.1. Завдання підсистеми введення-виведення
- •15.1.1. Забезпечення ефективності доступу до пристроїв
- •15.1.2. Забезпечення спільного використання зовнішніх пристроїв
- •15.1.3. Універсальність інтерфейсу прикладного програмування
- •15.1.4. Універсальність інтерфейсу драйверів пристроїв
- •15.2. Організація підсистеми введення-виведення
- •15.2.1. Символьні, блокові та мережні драйвери пристроїв
- •15.2.2. Відокремлення механізму від політики за допомогою
- •15.3. Способи виконання операцій введення-виведення
- •15.3.1. Опитування пристроїв
- •15.3.2. Введення-виведення, кероване перериваннями
- •15.3.3. Прямий доступ до пам'яті
- •15.4. Підсистема введення-виведення ядра
- •15.4.1. Планування операцій введення-виведення
- •15.4.2. Буферизація
- •15.7. Керування введенням-виведенням: unix і Linux
- •15.7.1. Інтерфейс файлової системи
- •15.7.2. Передавання параметрів драйверу
- •15.7.3. Структура драйвера
- •15.7.4. Виконання операції введення-виведення для пристрою
- •15.8. Керування введенням-виведенням: Windows хр
- •15.8.1. Основні компоненти підсистеми введення-виведення
- •15.8.2. Виконання операції введення-виведення для пристрою
- •15.8.3. Передавання параметрів драйверу пристрою
- •17.1. Термінальне введення-виведення
- •17.1.1. Організація термінального введення-виведення
- •17.1.3. Термінальне введення-виведення у Win32 api
- •17.2. Командний інтерфейс користувача 17.2.1.
- •17.2.2. Переспрямування потоків введення-виведення
- •17.2.3. Використання каналів
- •17.3. Графічний інтерфейс користувача
- •17.3.1. Інтерфейс віконної та графічної підсистеми Windows хр
- •17.3.2. Система X Window
- •17.4. Процеси без взаємодії із користувачем
- •17.4.1. Фонові процеси на основі posix
- •17.4.2. Служби Windows хр
- •16.1. Загальні принципи мережної підтримки
- •16.1.1. Рівні мережної архітектури і мережні сервіси
- •16.1.2. Мережні протоколи
- •16.2. Реалізація стека протоколів Інтернету
- •16.2.1. Рівні мережної архітектури tcp/ip
- •16.2.2. Канальний рівень
- •16.2.3. Мережний рівень
- •16.2.4. Транспортний рівень
- •16.2.5. Передавання даних стеком протоколів Інтернету
- •16.3. Система імен dns
- •16.3.1. Загальна характеристика dns
- •16.3.2. Простір імен dns
- •16.3.3. Розподіл відповідальності
- •16.3.4. Отримання ір-адрес
- •16.3.5. Кешування ір-адрес
- •16.3.6. Типи dns-ресурсів
- •16.4. Програмний інтерфейс сокетів Берклі
- •16.4.1. Особливості роботи з адресами
- •16.4.2. Створення сокетів
- •16.4.3. Робота з потоковими сонетами
- •16.4.4. Введення-виведення з повідомленням
- •19.1. Загальні принципи завантаження ос
- •19.1.1. Апаратна ініціалізація комп'ютера
- •19.1.2. Завантажувач ос
- •19.1.3. Двоетапне завантаження
- •19.1.4. Завантаження та ініціалізація ядра
- •19.1.5. Завантаження компонентів системи
- •19.2. Завантаження Linux
- •19.2.1. Особливості завантажувача Linux
- •19.2.2. Ініціалізація ядра
- •19.2.3. Виконання процесу init
- •19.3. Завантаження Windows хр
- •20.1. Багатопроцесорні системи
- •20.1.1. Типи багатопроцесорних систем
- •20.1.2. Підтримка багатопроцесорності в операційних системах
- •20.1.3. Продуктивність багатопроцесорних систем
- •20.1.4. Планування у багатопроцесорних системах
- •20.1.5. Спорідненість процесора
- •20.1.6. Підтримка багатопроцесорності в Linux
- •20.1.7. Підтримка багатопроцесорності у Windows хр
- •20.2. Принципи розробки розподілених систем
- •20.2.1. Віддалені виклики процедур
- •20.2.2. Використання Sun rpc
- •20.2.3. Використання Microsoft rpc
- •20.2.4. Обробка помилок і координація в розподілених системах
- •20.3. Розподілені файлові системи
- •20.3.1. Організація розподілених файлових систем
- •20.3.2. Файлова система nfs
- •20.3.3. Файлова система Microsoft dfs
- •20.4. Сучасні архітектури розподілених систем
- •20.4.1. Кластеры системи
- •20.4.2. Grid-системи
- •18.1. Основні завдання забезпечення безпеки
- •18.2. Базові поняття криптографії
- •18.2.1. Поняття криптографічного алгоритму і протоколу
- •18.2.2. Криптосистеми з секретним ключем
- •18.2.3. Криптосистеми із відкритим ключем
- •18.2.4. Гібридні криптосистеми
- •18.2.5. Цифрові підписи
- •18.2.6. Сертифікати
- •18.3. Принципи аутентифікаціїі керування доступом
- •18.3.1. Основи аутентифікації
- •18.3.2. Основи керування доступом
- •18.4. Аутентифікація та керування доступом в unix
- •18.4.1. Облікові записи користувачів
- •18.4.2. Аутентифікація
- •18.4.3. Керування доступом
- •18.5. Аутентифікація і керування доступом у Windows xp
- •18.5.1. Загальна архітектура безпеки
- •18.5.2. Аутентифікація
- •18.5.3. Керування доступом
- •18.6. Аудит
- •18.6.1. Загальні принципи організації аудиту
- •18.6.2. Робота із системним журналом unix
- •18.6.3. Журнал подій Windows xp
- •18.7. Локальна безпека даних
- •18.7.1. Принципи шифрування даних на файлових системах
- •18.7.2. Підтримка шифрувальних файлових систем у Linux
- •18.7.3. Шифрувальна файлова система Windows xp
- •18.8. Мережна безпека даних
- •18.8.1. Шифрування каналів зв'язку
- •18.8.2. Захист інформації на мережному рівні
- •18.8.3. Захист інформації на транспортному рівні
- •18.9. Атаки і боротьба з ними
- •18.9.1. Переповнення буфера
- •18.9.2. Відмова від обслуговування
- •18.9.3. Квоти дискового простору
- •18.9.4. Зміна кореневого каталогу застосування
20.2.4. Обробка помилок і координація в розподілених системах
Як бачимо, технологія RPC - це прозорий для користувача спосіб перетворення локальних програм у розподілені. Деякі реалізації RPC дають змогу для розв'язання цієї задачі обмежитися мінімальними змінами програмного коду. Виникає запитання: чи завжди коректний такий «автоматичний» підхід? Під час вивчення цього розділу побачимо, що це далеко не так. Можна сказати, що рівень абстракції, наданий RPC, не завжди відповідає специфіці розподілених систем.
Це пов'язано з тим, що структура застосувань, розроблених із використанням RPC, розрахована на роботу за умов успішного функціонування мережі, при цьому обробку помилок виконують майже так само, як і для локальних застосувань. Віддалена процедура, подібно до локальної, повертає простий код помилки («ме-режна помилка», «немає зв'язку» тощо), при цьому немає можливості дослідити, які компоненти розподіленої системи виявилися джерелом проблеми.
Насправді помилки в розподілених системах значно відрізняються за своїм характером від локальних помилок, оскільки їхнім джерелом є взаємодія цілого набору ненадійних компонентів (мережних з'єднань, проміжних вузлів тощо). Крім того, можлива поява часткових помилок, за яких деяку частину дій виконують коректно, а якусь - ні.
Сформулюємо головне правило обробки помилок у розподіленій системі, що не виконується у разі використання RPC: поведінка розподіленої системи при виникненні помилок має бути досліджена так само ретельно, як і коректна поведінка системи. У цьому пункті розглянемо деякі особливості такої поведінки і способи її дослідження. Докладніше про це питання у [45].
Задача розподіленої координації
Цю задачу формулюють так: чи можливо надійно скоординувати дії на двох різних комп'ютерах (наприклад, виконання деякого коду в один і той самий час, виконання дії тільки один раз, атомарну зміну стану на двох різних машинах тощо)?
До дій, що вимагають такої синхронізації, належать, наприклад:
♦ атомарне переміщення файла із сервера S{ на сервер S<i,
♦ атомарне переміщення суми грошей із рахунку в одному банку на рахунок в іншому.
Головна проблема, що виникає при цьому, пов'язана з тим, що мережа, яка зв'язує ці комп'ютери, є ненадійною:
♦ повідомлення можуть бути втрачені;
♦ комп'ютери можуть бути вимкнені або вийти з ладу.
З урахуванням ненадійності мережі можна уточнити формулювання цієї задачі.
Чи можна використати обмін повідомленнями через ненадійну мережу для надійної синхронізації двох комп'ютерів (щоб вони гарантовано могли виконувати ту саму операцію одночасно)?
Відповідь на це запитання є однозначно негативною навіть тоді, коли всі повідомлення будуть доставлені й жоден комп'ютер не вийде з ладу.
Цю проблему звичайно ілюструють парадоксом візантійських генералів. Припустимо, що два генерали на чолі армій перебувають на деякій відстані один від одного, тому вони можуть обмінюватися повідомленнями тільки через посильних, причому під час доставлення повідомлення посильних можуть полонити. Задачею є погодити час одночасної атаки на ворога (спільних сил достатньо для перемоги, сил кожної армії окремо - ні). Розглянемо протокол обміну повідомленнями, який можна використати в даному випадку.
1. Генерал GA відсилає повідомлення Мм із точним часом атаки.
2. Генерал GB отримує МАІ, відсилає своє повідомлення МВІ із висловленням згоди і починає очікувати підтвердження отримання МВІ.
3. Генерал GA отримує МВІ, відсилає підтвердження його отримання (МА2) і починає очікувати підтвердження отримання МА2.
Подібний обмін повідомленнями може тривати нескінченно. Очевидно, що погодити час атаки генералам не вдасться (останнє повідомлення увесь час залишатиметься непідтвердженим). Доведено, що розв'язків ця задача не має.
Далі в цьому пункті розглянемо протоколи розподіленої координації, що не потребують одночасного виконання операцій різними сторонами.
Протокол запиту-квітування
Проаналізуємо особливості обміну повідомленнями в мережі за наявності помилок. Припустимо, що трапляються тільки помилки передавання даних (втрати повідомлень), учасники протоколу не виходять із ладу.
Для обміну повідомленнями за таких умов із гарантією одноразового доставлення призначений протокол запиту-квітування (request/acknowledge protocol).
1. Відправник пересилає одержувачеві повідомлення і встановлює таймер.
2. Одержувач отримує повідомлення і відсилає підтвердження отримання.
3. Відправник отримує підтвердження і скидає значення таймера.
4. У разі вичерпання часу, заданого таймером, кроки протоколу повторюють.
Цей протокол гарантує, що повідомлення буде доставлене хоча б один раз за
умови, що учасники не виходять із ладу. При цьому одержувач може отримати повідомлення кілька разів (у разі втрати підтвердження). Щоб мати можливість відкидати дублікати, повідомлення можна супроводжувати унікальними номерами.
Протокол запиту-квітування мало пристосований до роботи за умов виходу з ладу його учасників. Наприклад, у разі краху відправника після відновлення він не може отримати інформацію про те, отримав одержувач повідомлення чи ні (підтвердження до нього дійти не зможе). У разі краху одержувача значно ускладнюється робота із дублікатами.
Для координації взаємодії ненадійних учасників потрібні більш складні протоколи. Одним із них є протокол двофазового підтвердження.
Двофазове підтвердження
Оскільки одночасного виконання дій на віддалених комп'ютерах відповідно до парадоксу генералів домогтися неможливо, для розподіленої координації дій використовують методи, у яких допустиме виконання дій у різний час. Розглянемо один із них - двофазове підтвердження (two-phase commit, 2РС) [4].
У цьому разі дві сторони виконують дії, оформлені у вигляді транзакцій -атомарних операцій, які виконуються повністю (підтверджуються, commit) або не виконуються зовсім (відкочуються, rollback).
Прикладом розподіленої транзакції може бути перенесення файла із сервера Si на сервер S2. Якщо виконання цієї дії переривається, за відсутності атомарності може виявитися, що файл був вилучений із сервера 5Ь але при цьому не був перенесений на сервер S2.
Для виконання протоколу двофазового підтвердження необхідно на кожному комп'ютері підтримувати журнал транзакцій (transaction log), у якому відстежу-вати, відбулося підтвердження чи ні. Крім того, один із вузлів мережі має відігравати роль координатора транзакцій. Основним завданням такого координатора є збереження атомарності кожної транзакції у розподіленій системі.
Першим етапом протоколу є етап запитів координатора.
1. Координатор відсилає всім учасникам запит. Він містить опис дії, яка має виконуватися, наприклад «вилучити файл a.txt із кореневого каталогу». Перед відсиланням запиту інформацію про нього зберігають у журналі транзакцій координатора.
2. Учасники отримують запит і виконують транзакцію локально (наприклад, намагаються вилучити файл). Інформацію про результат цієї дії відображають у вигляді повідомлення (Мок - успіх, МАВ0КГ - невдача), яке зберігають у журналі транзакцій кожного учасника і відсилають координаторові. Цей етап завершений, коли координатор отримає повідомлення від всіх учасників (або мине максимальний час очікування). Зазначимо, що для жодної транзакції в конкретний момент ще не було виконано ні підтвердження, ні відкату (наприклад, інформацію про вилучення файла зберігають лише у пам'яті). Другим етапом є етап ухвалення рішення координатором.
3. Спочатку координатор ухвалює рішення щодо підтвердження або відкату розподіленої транзакції. На цьому кроці можуть виникнути дві ситуації:
♦ координатор отримує повідомлення MAB0RT хоча б від одного учасника. Після цього він створює повідомлення MGL0BAL rollback зберігає його в журналі та відсилає всім учасникам;
♦ координатор отримує повідомлення Мок від кожного учасника. Після цього він створює повідомлення MGL0BALC0MMIT, зберігає його в журналі та відсилає всім учасникам.
4. Після отримання повідомлення від координатора кожен учасник зберігає його у своєму журналі та виконує відкат або підтвердження транзакції залежно від типу повідомлення. Для цього прикладу відкат може зводитися до повного скасування операції вилучення файла, підтвердження - до вилучення файла з диска.
Розглянемо виконання цього протоколу за умов мережних помилок. Спочатку зупинимося на випадках виходу з ладу учасників протоколу.
♦ Якщо учасник вийде з ладу на кроці 2 (під час виконання транзакції), координатор не отримає повідомлення про завершення транзакції упродовж максимального часу очікування і відкотить транзакцію, відіславши учасникам повідомлення MGL0BAL_R0LLBACK -
♦ Якщо координатор вийде з ладу на кроці 3, після відновлення він має звернутися до свого журналу транзакцій. Коли в ньому немає жодного повідомлення Mglobal_xxx або є повідомлення MGL0BAL_ rollback, то всім учасникам відсилають повідомлення про відкат. Коли в журналі є MGL0BAL_commit, учасникам відсилають повідомлення про підтвердження.
♦ У разі виходу учасника з ладу на кроці 4 після відновлення він має звернутися до координатора за інформацією і виконати відповідно підтвердження або відкат.
До недоліків протоколу 2РС належать високі вимоги до надійності координатора. Якщо він вийде з ладу на кроці 3 і не відновить свою роботу, всі учасники можуть бути заблоковані.
Це, однак, відбувається не завжди. У разі отримання деякими учасниками повідомлення від координатора на кроці 4, а деякими — ні, часом є можливість завершити транзакцію, звернувшись за інформацією до інших учасників.
♦ Коли хоча б один із учасників отримав Mglobal_xxx, необхідно виконати дію, що відповідає цьому повідомленню.
♦ Коли хоча б один із учасників відіслав MAB0RT, транзакцію необхідно відкотити.
Якщо ж всі учасники відіслали Мок, але ніхто з них не отримав Mglobal _xxx, рішення не може бути прийнято, оскільки координатор міг зберегти в журналі (але не встиг відіслати) Mglobal_ rollback через свою внутрішню помилку. Така ситуація і спричиняє блокування всіх уч асників. Під час реалізації 2РС потрібно завжди враховувати можливість такого блокування.