- •Еволюція спз.
- •Призначення та склад операційних систем.
- •Системне програмування.
- •Загальна схема трансляції
- •Основні принципи розробки системного програмного забезпечення.
- •Умови зміни станів процесу (з Рис.1.)
- •Властивості та класифікація процесу.
- •Визначення ресурсу та класифікації.
- •2. Дисципліни диспетчеризації.
- •3. Алгоритми в диспетчеризації з витісненням та без.
- •4. Способи забезпечення гарантованого обслуговування процесів.
- •5. Критерії порівняння алгоритмів диспетчеризації.
- •6. Вплив планування на ефективність обчислювальних систем.
- •7. Використання динамічних пріоритетів.
- •2. Види задач синхронізації паралельних процесів.
- •3. Синхронізація за допомогою блокування пам’яті.
- •4. Алгоритм Деккера.
- •5. Команда “перевірка” та “встановлення”.
- •6. Використання семафорів для синхронізації та впорядкування паралельних процесів.
- •7. Монітороподібні засоби синхронізації паралельних процесів.
- •8. Поштові ящики.
- •9. Конвеєри.
- •10. Черги повідомлень.
- •Неперервний розподіл оперативної пам’яті.
- •Розподіл з перекриттям.
- •Статичний розподіл пам’яті.
- •Динамічний розподіл пам’яті.
- •Розділи пам’яті з фіксованими розмірами.
- •Розділи пам’яті зі змінними розмірами.
- •Сегментна схема організації віртуальної пам’яті.
- •Сторінкова схема організації віртуальної пам’яті.
- •Сегментно - сторінкова схема організації віртуальної пам’яті..
- •Тема 7. Архітектурні особливості мікропроцесорів Intel 80x86.
- •Мал. 3.1 Схема визначення фізичної адреси для процесора 8086.
- •2. Нові системні регістри мікропроцесорів і80x86.
- •Мал. 7.2 Основні системні регістри мікропроцесорів і80x86.
- •3. Підтримка сегментного способу організації віртуальної пам'яті.
- •Мал. 7.3 Дескриптор сегменту.
- •Мал. 7.4. Селектор сегменту.
- •Мал. 7.5 Сегмент стану задачі (tss).
- •Мал. 7.6 Процес отримання лінійної адреси команди.
- •4. Підтримка сторінкового способу організації віртуальної пам'яті.
- •Мал. 7.7 Дескриптор сторінки.
- •Мал. 7.8 Трансляція лінійної адреси в мікропроцесорах і80x86.
- •5. Режим віртуальних машин для виконання додатків реального режиму.
- •6. Захист адресного простору задач.
- •Якщо цільовий сегмент є сегментом стека, то правило перевірки має вид
- •7. Механізм шлюзів для передачі керування на сегменти коду з іншими рівнями привілеїв.
- •Мал. 7.9 Механізм шлюзів для переходу на другий рівень привілеїв.
- •Мал. 7.10 Перехід на сегмент більш привілейованого коду.
- •Мал. 7.11 Формат дескриптора шлюзу.
- •Тема 8. Організація системи переривань 32-розрядних мікропроцесорів i80х80.
- •2. Типи переривань.
- •4. Узагальнена процедура обробки переривання.
- •5. Робота системи переривань у захищеному режимі роботи процесора.
- •Обробка переривань у контексті поточної задачі.
- •7. Обробка переривань з переключенням на нову задачу.
- •Тема 9. Керування вводом/виводом даних.
- •2. Режими керування вводом/виводом.
- •3. Закріплення пристроїв, загальні пристрої вводу/виводу.
- •4. Основні системні таблиці вводу/виводу.
- •Синхронний і асинхронний ввід/вивід.
- •6. Кешування операцій вводу/виводу при роботі з накопичувачами на магнітних дисках.
- •Тема 10.Організація файлових систем.
- •Тема 11. Файлові системи fat, vfat, fat32, hpfs.
- •Тема 12.Файлова система ntfs (Mew Technology File System)
- •Можливості файлової системи ntfs по обмеженню доступу до файлів і каталогів.
- •Інтерфейс прикладного програмування арі.
- •Реалізація функцій арі на рівні операційної системи.
- •Реалізація функцій арі на рівні системи програмування.
- •Реалізація функцій арі за допомогою зовнішніх бібліотек.
- •Posix інтерфейс.
- •Віртуальна машина.
- •Типи та інтерфейс користувачів.
- •Команди та командний інтерпретатор.
- •Процеси та їх виконання.
- •Підсистема вводу/виводу.
- •Структура файлової системи.
- •Засоби захисту файлів і даних.
- •Сигнали і семафори.
- •Програмні канали та черги повідомлень.
- •Розділювана пам’ять та виклики віддалених процедур.
3. Синхронізація за допомогою блокування пам’яті.
Механізм блокування пам’яті задовольняє одночасне використання двох і більше команд, які звертаються до однієї і тієї самої комірки пам’яті. Так як в цій комірці пам’яті може зберігатися значення певної розділеної змінної, то отримати доступ до неї може тільки один процес. Механізм блокування пам’яті забороняє одночасний доступ до змінної але не забороняє чергування доступу. Якщо критична секція процесу складається тільки з однієї команди звернення до пам’яті, то блокування пам’яті може забезпечити виконання задачі взаємного виключення. Якщо критична секція складається більш ніж з однієї секції, то задача забезпечення взаємного виключення стає більш складною.
Для забезпечення задачі взаємного виключення використовують дві змінні key 1 і key 2.
Приклад на мові Pascal
var key1, key2: boolean;
begin
key1:=false, key2:=false;
par begin
PR1: white true do
begin key1:=true
while key2 do begin … end {критична секція PR1}
key1:=false
end
and
PR2: white true do
begin key2:=true
while key1 do begin … end {критична секція PR2}
key2:=false
end
par end
При виконанні цього алгоритму можлива ситуація коли два процеси встановлять одночасно свої змінні key 1 і key 2 в true і ввійдуть у безкінечний цикл. Тому для вирішення цієї проблеми був запропонований алгоритм Деккера.
4. Алгоритм Деккера.
Алгоритм Деккера базується на використанні змінних key 1, key 2, queue. Змінні key 1, key 2 використовуються як в попередньому алгоритмі з пункту 3. Значення змінної queue визначає чия черга (процесу один чи процесу два) почати виконання критичної секції при умові, якщо два процеси бажають це зробити.
Детальніше про алгоритм Деккера – самостійно!
5. Команда “перевірка” та “встановлення”.
Операція “перевірка” та “встановлення” так само як механізм блокування пам’яті є одним із апаратних засобів керування процесом входження в критичний інтервал.
Розглянемо гіпотетичну команду TS (test and set), дія якого полягає в тому, що першій змінні key 1 присвоюється значення key 2 (з прикладу питання 3), після чого другій змінні key 2 присвоюється 1. Команда TS є неподільною командою, тобто між початком виконання цієї команди і її завершенням не можуть виконуватися ніякі інші команди. Введемо змінну common, яка буде загальною змінною для двох (всіх) процесів, які використовують деякі критичні ресурси. Common=1, якщо будь – який із взаємодіючих процесів знаходиться у своїй критичній секції. Також з кожним процесом зв’яжемо локальну змінну local 1, local 2. Вони будуть дорівнювати 1, якщо певний процес бажає ввійти у свою критичну секцію.
Приклад.
var local1, local2, common: integer
begin
common:=0
par begin
PR1:
begin local1:=1
while local1=1 do TS(local1, common)
CS1:
common:=0
end
and
PR2:
begin local2:=1
while local2=1 do TS(local2,common)
CS2:
common:=0
end
par end
6. Використання семафорів для синхронізації та впорядкування паралельних процесів.
Семафор – це змінна спеціального типу, яка доступна паралельним процесам для виконання двох операцій: зайнято (P - операція); відкрито (V – операція). Семафор відіграє роль допоміжного критичного ресурсу і операції V та P є нероздільними. Крім того P і V виключають одна іншу.
Семафори працюють таки чином, що спочатку аналізують стан критичного ресурсу, який ідентифікується станом семафору, потім здійснюється допуск до критичного ресурсу або відмова від нього. При відмові в доступі до критичного ресурсу використовується режим пасивного очікування. В цьому випадку процес знаходиться в заблокованому стані. Він не перевіряє семафор безперервно, як у стані активного очікування. В той час процес може виконувати необхідну дію. Допустимими значеннями семафору є тільки цілі числа. Семафори бувають двійкові (приймають значення 0, 1), або n – значення (в іншому випадку).
Приклад:
var S: semaphore
begin
init Sem(S, 1)
parbegin
PR1: while true do
begin
P(S)
CS1
V(S)
end
and
PR2: while true do
begin
P(S)
CS2
V(S)
end
parend
Семафор S має початкове значення 1. Якщо процеси PR1, PR2 будуть намагатися виконати операцію P(S), то це зробить успішно тільки один процес. Якщо це зробив процес PR2, тоді він закриває семафор S, після чого виконується його критичний інтервал. Процес PR1 в цій ситуації буде заблокований на семафорі S. Після виконання операції V(S) процесу PR2 семафор S відкривається, показуючи можливість використання одного сумісного ресурсу. Цією операцією процес PR1 буде переведений із заблокованого стану в стан готовності.
Вирішення задачі “виробник – споживач” за допомогою семафорів.
Для вирішення цієї задачі розподілювальними змінними є лічильники вільних та зайнятих буферів пам’яті, які повинні бути захищені зі сторони обох процесів. Тобто дії по відправленні і отриманні повідомлень повинні бути синхронізовані. Семафори S – free, S – fil – в даному випадку є числовими, семафор S – exp – двійковим.
Приклад.
var S-free, S-fil, S-exp: semaphore;
begin
InitSem (s-free, N);
InitSem (s-fil, 0);
InitSem (s-exp, 1);
parbegin
PROCEDURE: while true do
begin
{підготовка повідомлень}
P(S-free);
P(S-fil);
{послати повідомлення}
V(S-fil);
V(f-exp);
end;
and
CONSUMER: while true do
P(S-fil);
P(S-exp);
{отримати повідомлення}
V(S-free);
V(S-exp);
{обробка повідомлень}
parend
end
Семафори S – free, S – fil використовуються як лічильники вільних та зайнятих областей пам’яті (буферів) відповідно. Двійковий семафор S – exp призначений для гарантії того, що в кожен момент часу тільки один процес може працювати зі своїм критичним ресурсом в своїй критичній секції. В початковий момент часу ініціалізація семафорів лічильників відбувається таким чином, що кількість вільних буферів S – free – n, кількість зайнятих = 0.
Операція P(S – free) зменшує значення S - free на одиницю. Операція V(S – free) збільшує значення лічильника S - free на одиницю.
Перед відправою повідомлення процес виробник зменшує значення S – fil на одиницю, а після відправки повідомлення збільшує значення S – fil на одиницю. Так само перед отриманням повідомленням процес споживач зменшує значення S – fil на одиницю шляхом виконання операції P(S – fil), а після отримання повідомлення збільшує значення семафору S – free в результаті виконання операції V(S – free).
Вирішення задачі читачів – письменників за допомогою семафорів – самостійно!