Системне програмне забезпечення

System Software – означає програми та комплекси програм, які є спільними для всіх, хто використовує технічні засоби комп’ютера і які застосовуються, як для автоматизації розробки (створення) нових програм, так і для організації виконання існуючих програм. З цих позицій системне програмне забезпечення (СПЗ ) може бути розділене на такі групи:

1. Операційні системи.

2. Системи програмування.

3. Утиліти.

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

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

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

Утиліти. Це спеціальні системні програми за допомогою яких можна як обслуговувати саму ОС, так і готувати для роботи носії даних, виконувати перекодування даних, оптимізацію розміщення даних на носії та виконувати деякі інші роботи, пов’язані із обслуговуванням обчислювальних систем. Зрозуміло, що утиліти можуть працювати тільки під відповідною операційною системою.

Таким чином, типова структура СПЗ має такий вигляд (Рис. __)

Основними функціями ОС є:

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

2. Завантаження, запуск, призупинення, зупинка програм.

Керування файловими системами та системами управління базами даних.

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

4. Забезпечення функцій з організації та керування усіма операціями вводу/виводу.

5. Забезпечення виконання обмежень на час відповіді в режимі реального часу (для ОС відповідного типу).

6. Розподіл пам’яті (як основної, так і зовнішньої), та організація віртуальної пам’яті.

7. Планування та диспетчеризація задач у відповідності із заданими стратегією та дисципліною обслуговування.

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

9. Забезпечення роботи систем програмування.

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

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

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

Наприклад: користування вводом/виводом.

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

Типи операційних систем

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

1. Класифікація, за кількістю користувачів, які одночасно обслуговуються ОС:

Одно програмна — забезпечує роботу одної задачі одного користувача.

Мульти (багато) програмна — дозволяє одночасно виконувати декілька програм одного користувача.

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

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

2. Класифікація за типами доступу, який надається інтерфейсом користувача.

Сиситеми пакетної обробки – обробляють потік завдань. Все керування з читання та виконання завданнями бере на себе ОС. Зараз втратили актуальність.

Діалоговий або інтерактивний доступ – забезпечується для деякої кількості користувачів одночасно системами розподілу часу.

ОС виконує директиви користувачів в темпі надходження та намагається дати відповідь на кожну команду користувача за найкоротший час.

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

Досить часто всі ознаки класифікації реалізуються в одній системі.

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

Операційне оточення може включати декілька інтерфейсів: користувацькі і програмні:

Linux – має інтерфейс командного рядка (shell);

інтерфейс Midnight Commander (типу NC);

графічні інтерфейси – Х-Window з різними менеджерами вікон (KDE, Gnome)

Програмні інтерфейси – в Linux програми можуть звертатись як до ОС за відповідними сервісами і функціями, так і до графічної підсистеми (якщо вона використовується).

З точки зору процесора комп’ютера, як і всього комп’ютера в цілому, двійкова програма, створена для роботи в середовищі Linux, використовує ті самі команди і формати даних, що і програма, створена для роботи в середовищі Windows NT.

Але в першому випадку ми маємо звертання до одного операційного середовища, а в другому випадку – а в другому випадку – до другого. Програма, створена під Windows безпосередньо, не буде виконуватись в Linux. Але якщо в ОС Linux створити повноцінне операційне середовище Windows, то Windows-програма може бути виконана.

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

Тема 2: Процеси.

Керування процесами

Поняття „обчислювальний процес” є одним із основних при вивченні операційних систем. Притримуємось такого визначення: Процес (або задача) – це програма під час виконання на процесорі із послідовним виконанням команд. Сам процесор розглядається в двох аспектах:

1. Він є носієм даних;

2. Виконує операції, пов’язані з обробкою цих даних.

Процесом може бути:

- виконання утиліти;

- виконання прикладної програми;

- трансляція вихідної програми (одної програми – один процес, іншої програми – інший процес).

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

За період свого існування процес приймає ряд дискретних станів. Зміну станів процесу можуть викликати різні події.

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

Процес знаходиться в стані готовності, якщо він міг би одразу використати CPU, який знаходиться в його розпорядженні.

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

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

Тому створюються:

- список процесів, готових до виконання;

- список заблокованих процесів.

Перший список впорядкований за пріоритетом. Таким чином наступний процес, що отримує в своє розпорядження CPU, буде першим з цього списку.

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

В ОС, як правило, процес з’являється при запуску довільної програми. Коли процес створено, він займає місце в кінці списку готових процесів. Він поступово просувається до початку списку – у відповідності з тим, як завершується виконання попередніх процесів.

Коли процес буде першим у списку готових процесів, і коли звільниться CPU, цьому процесу виділяється CPU і кажуть, що відбувається зміна станів процесу. Він переходить від стану готовності до стану виконання.

Вибір процесу для виконання називається „Пуском”, і це виконується за допомогою програми ОС, яка називається диспетчером.

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

Після закінчення кванту часу таймер виробить сигнал переривання, за яким керування буде передано ОС.

Після цього ОС переводить процес, що перед цим виконувався, в стан готовності, а перший процес із списку готових – в стан виконання.

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

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

Таким чином маємо чотири можливі зміни станів процесу. Єдина зміна станів, що викликається самим процесом користувача – блокування. Інші три зміни викликаються об’єктами, що є зовнішніми по відношенню до біжучого процесу.

Процес із пасивного стану може перейти в стан готовності в таких випадках:

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

2. При виборі з черги планувальником процесів.

3. За викликом із іншої задачі (один процес може створити, ініціювати, призупинити, зупинити, знищити інший процес).

4. За перериванням від зовнішнього пристрою (сигнал від виконання деякої події може запустити відповідну задачу).

5. При надходженні запланованого часу запуску програми.

Із стану виконання процес може вийти з таких причин:

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

2. Процес переводиться ОС в стан готовності у зв’язку з виникненням задачі з вищим пріоритетом або через завершення виділеного кванту часу.

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

Таким чином, силою, яка міняє стани процесів, є події. Один із основних видів подій - переривання.

Блок керування процесом

Для того, щоби ОС могла керувати процесами, вона повинна володіти всією необхідною інформацією. Для цього для кожного процесу створюється спеціальна інформаційна структура, яка називається – блоком керування процесом (Program Control Block, PCB), або дескриптором процесу, або описувачем задачі. В загальному випадку РСВ вміщує таку інформацію:

1. Ідентифікатор процесу (PID – process identifier).

2. Тип (або клас) процесу, який визначає для ОС деякі правила надання ресурсів.

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

4. Змінну стану, яка визначає, в якому стані знаходиться процес (стані готовності, стані виконання, стані блокування).

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

6. Інформація про ресурси, якими володіє процес або має право користуватись.

7. Адреса місця для організації спілкування з іншими процесами.

8. Параметри часу запуску (момент часу, коли процес повинен активізуватись та періодичність цієї процедури).

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

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

Таким чином, РСВ – це об’єкт, який визначає процес для ОС.

Операції над процесами

Підсистема керування процесами повинна виконувати наступні операції над ними:

- створення;

- знищення;

- відновлення;

- зміна пріоритету;

- блокування;

- розблокування;

- запуск (або вибір).

Створення процесу. При створенні процесу передбачаються наступні дії:

- присвоєння процесові імені;

- включення цього імені в список імен процесів, що відомі системі;

- визначення початкового пріоритету процесу;

- формування блоку керування процесом (PCB);

- виділення процесові початкових ресурсів.

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

Знищення процесу. Вилучення процесу зі системи. Ресурси, що були виділені процесові звільняються та повертаються системі. Ім’я процесу витирається в системних списках та таблицях. Блок PCB, знищується.

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

З врахуванням призупинення та відновлення діаграма станів процесів має наступний вигляд показаний на рис. __.

Призупинка та відновлення процесу відіграють важливу роль з декількох причин:

1. Якщо система працює ненадійно, та є ознаки, що вона може відмовити, то біжучі процеси можна призупинити для того, щоб знову активізувати при відновленні працездатності системи;

2. Користувач, у якого окремі проміжні результати роботи програми викликали сумніви, може призупинити (а не припинити) її виконання для уточнення достовірності роботи програми (процесу);

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

Виникає питання, чи переводити заблокований процес в стан призупинення?

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

- або припинити заблокований процес;

- або передбачити механізм, який дозволяв би переводити процес зі стану блокування в стан призупинення до завершення операції вводу/виводу, або до виникнення очікуваної події.

Так як, призупинення є операцією з найвищим пріоритетом, вона виконується негайно.

Обробка переривань

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

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

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

Для коректного повернення з переривання до перерваної програми перед передачею керування обробнику система запам’ятовує вміст регістрів процесора або у пам’яті з прямим доступом, або у системному стеку. (system stack).

Таким чином, якщо відбулося переривання:

1. Керування передається ОС;

2. ОС запам’ятовує стан перерваного процесу, як правило, ця інформація запам’ятовується в його блоці керування процесом (PCB);

3. ОС аналізує тип переривання та передає керування відповідному обробнику.

Переривання, що виникають при роботі обчислювальної системи, можна поділити на такі основні групи:

1. Зовнішні (або асинхронні). Викликаються асинхронними подіями, які відбуваються поза процесом, що виконується і відповідно переривається:

- переривання від таймера;

- переривання від зовнішніх пристроїв;

- переривання при збоях у живлення;

- переривання з пульта оператора обчислювальної системи;

- переривання від іншого процесора або обчислювальної системи.

2. Внутрішні. Викликаються подіями, що пов’язані з роботою процесу, що виконується і є синхронними з його операціями. Такі переривання виникають:

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

- при наявності в полі коду операції, неіснуючої команди;

- при діленні на нуль;

- при переповненні, або пропаданні порядку в числах з плаваючою крапкою;

- при виявленні порушення паритету парності, а також помилок в роботі різних пристроїв апаратури комп’ютера засобами контролю;

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

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

За рінями пріоритету переривання розподіляються наступним чином:

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

Перемикання контексту. Для обробки кожного з видів переривань в складі ОС передбачені програми, що називаються обробниками переривань (IH – Interrupt Handler). Коли відбувається переривання, ОС запам’ятовує стан перерваних процесів та передає керування відповідним обробникам переривань. Ця процедура називається перемиканням контексту. При її реалізації використовуються слова стану програми (Program Status Word, PSW), які керують напрямком виконання команд і містять різну інформацію про відносно стану процесу.

Існує три типи PSW: біжуче, нове та старе.

Адреса наступної команди, що має виконуватися, міститься в біжучому PSW, у ньому вказані також типи переривань, що дозволені заборонені на даний час.

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

В одно процесорній машині є тільки одне біжуче PSW, але N нових та N старих (по одному на кожен тип переривань).

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

1) Біжуче PSW стає старим PSW для переривань цього типу;

2) Нове PSW для переривань цього типу стає біжучим PSW.

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

Лекція 4:

Ядро операційної системи

Усі операції, що пов’язані з процесами, виконуються під керуванням ядра. Ядро – невелика частина ОС, але вона відноситься до найбільш інтенсивно використовуваних компонентів ОС.

З цієї причини ядро, зазвичай, резидентно розміщено в оперативній пам’яті, в той час як інші частини ОС переміщаються у зовнішню пам’ять та назад за необхідністю.

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

Основні функції ядра

Ядро, як правило, містить програми для реалізації наступних функцій:

- обробка переривань;

- створення та знищення процесів;

- перемикання процесів зі стану в стан;

- диспетчеризація;

- припинення та активізація процесів;

- синхронізація процесів;

- організація взаємодії між процесами;

- маніпуляція блоками керування процесами (PCB);

- підтримка операцій вводу-виводу;

- підтримка розподілу та перерозподілу пам’яті;

- підтримка механізму виклику-повернення при звертанні до процедур;

- підтримка функцій з обліку роботи машини.

Функції, що реалізовані в ядрі є примітивними.

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

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

Асинхронні паралельні процеси

Процеси називаються паралельними, якщо вини існують (працюють) одночасно.

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

Паралельні процеси можуть бути повністю незалежними або взаємодіючими. Останні можуть бути конкуруючими, або такими, що сумісно виконують спільну роботу.

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

Керуючі конструкції організації паралелізму.

У багатьох сучасних мовах програмування передбачено спеціальні конструкції для організації паралелізму, зокрема в „Ада”, це пара операторів parbegin / parend. Як правило, це парні оператори:

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

- Другий оператор, вказує, що зазначені послідовності, що виконувалися паралельно, повинні злитися в один потік і повинно відновитися послідовне виконання команд.

Приклад розпаралелювання виконання команд.

Пари операторів, що забезпечують розпаралелення на рівні алгоритму:

parbegin / parend – початок – завершення блоку паралельного виконання;

cobegin / coend – початок – завершення блоку суміщеного виконання;

Приклад. Обчислити вираз x := (-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a).

Цей вираз обчислюється за допомогою послідовного процесора наступним чином:

1 b ** 2

2 4 * a

3 (4 * a) * c

4 (b ** 2) – (4 * a * c)

5 (b ** 2 – 4 * a * c) ** 0.5

6 -b

7 (-b) + ((b ** 2 – 4 * a * c) ** 0.5)

8 2 * a

9 (-b + (b ** 2 – 4 * a * c) ** 0.5) / (2 * a).

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

У системі з паралельною обробкою, матимемо:

1 parbegin

temp1 := -b

temp2 := b ** 2

temp3 := 4 * a

temp4 := 2 * a

parnd

2 temp5 := temp3 * c

3 temp5 := temp2 – temp5

4 temp5 := temp5 ** 0.5

5 temp5 := temp1 + temp5

6 x := temp5 / temp4

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

Взаємо-виключення

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

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

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

Для прикладу розглянемо задачу.

Програма друкування файлів. Програма повинна надрукувати всі файли, імена яких послідовно (у порядку надходження) розміщені у загальнодоступному файлі „замовлень”, іншими програмами.

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

Припустимо, що в деякий момент процес R вирішив роздрукувати свій файл. (Див. Рис. __). Для цього він прочитав значення змінної Next (допустимо, що воно рівне 4). Процес запам’ятав це значення, але розмістити імені файлу не встиг, так як його виконання було перерване (вичерпався квант часу).

Рис. __

Черговий процес S, який хоче роздрукувати свій файл, прочитав те саме значення змінної , розмістив свій файл у вказаній позиції (4) та наростив значення змінної на одиницю.

Коли керування буде передано процесові R, то він продовжить своє виконання з розміщення імені свого файлу в позицію 4 файлу „замовлень”, так як цю позицію він запам’ятав підчас попереднього кванту часу, підмінивши таким чином назву файлу, що записана процесом S.

Таким чином процес S ніколи не побачить свого файлу роздрукованим.

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

Для вирішення проблеми, що описана прикладом друкування файлів, необхідно реалізувати задачу із взаємо-виключення із забезпеченням наступних чотирьох обмежень:

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

Причому: - кожна машинна команда виконується як операція, що не може бути поділена;

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

2. Не повинно бути ніяких припущень щодо відносних швидкостей виконання асинхронних паралельних процесів.

3. Процеси, що знаходяться поза своїми критичними секціями, не можуть заважати іншим процесам заходити у свої власні критичні ділянки.

4. Не повинно бути безмежного відкладання часу входу процесів у свої критичні ділянки.

Програмну реалізації цієї задачі запропонував голландський математик Дейкстра.

Алгоритм Дейкстри.

Процес 1. (П1). Процес 2. (П2).

program Алгоритм Дейкстри

var вибранийпроцес : цілий; { перший, другий }

П1хочезайти, П2хочезайти: логічний;

procedure Процес1

Begin

while правда do begin

П1хочезайти := правда;

while П2хочезайти do begin { зовнішній цикл очікування }

if вибранийпроцес = другий then begin

П1хочезайти := неправда;

while вибранийпроцес = другий do

П1хочезайти := правда; { внутрішній цикл очікування }

end;

end;

{ початок критичної ділянки П1}

вибранийпроцес := другий;

П1хочезайти := неправда;

... { оператори критичної ділянки П1}

{ кінець критичної ділянки П1}

end;

end;

procedure Процес2

Begin

while правда do begin

П2хочезайти := правда;

while П1хочезайти do begin { зовнішній цикл очікування }

if вибранийпроцес = другий then begin

П2хочезайти := неправда;

while вибранийпроцес = перший do

П2хочезайти := правда; { внутрішній цикл очікування }

end;

end;

{ початок критичної ділянки П2}

вибранийпроцес := перший;

П2хочезайти := неправда;

... { оператори критичної ділянки П2}

{ кінець критичної ділянки П2}

end;

end;

{ основна програма }

Begin

П1хочезайти := неправда;

П2хочезайти := неправда;

вибранийпроцес := перший;

Parbegin

Процес1;

Процес2;

Parend

end;

1. Процес П1 повідомляє про бажання увійти в свою критичну ділянку. Встановлює свій прапорець.

2. Процес П1 переходить до циклу, в якому перевіряє чи процес П2 не хоче також увійти у свою критичну ділянку коду.

3. Якщо, прапорець процесу П2 не встановлений, то П1 пропускає тіло циклу очікування та заходить у свою критичну ділянку.

4. Допускаємо, що П1 при виконанні циклу перевірки виявив, що прапорець П2 встановлено. Це примушує П1 увійти в тіло циклу очікування.

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

6. Якщо, „вибраний процес” – П1, то він повторно виконує тіло свого циклу очікування моменту коли П2 скине свій прапорець.

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

8. З часом П2 вийде із своєї критичної ділянки і виконає оператор „вихід із взаємо-виключення”. Цей оператор забезпечує повернення права переваги процесу П1 і скидання прапорця П2.

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

10. Якщо П2 одразу ж намагається знову увійти в критичну ділянку, то його прапорець буде