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

Планування і диспетчеризація процесів і задач в ОС

Стратегії планування

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

По можливості закінчувати обчислення в тому ж порядку, в якому вони були отримані;

Надавати перевагу більш коротким процесам;

Надавати усім користувачам (процесам) однакові послуги, в тому числі однаковий час очікування.

Дисципліни диспетчеризації

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

Існуючі дисципліни диспетчеризації процесів можуть бути розбиті на два класи — витісняючі (preemtive) і невитісняючі (non-preemptive).

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

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

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

Найпростіший у реалізації є дисципліна FCFS (first come — firsi served), відповідно до якої задачі обслуговуються «у порядку черги», тобто в порядку їх появи. Ті задачі, що були заблоковані в процесі роботи (потрапили в яке-небудь зі станів очікування, наприклад, через операції введення/виведення), після переходу в стан готовності ставляться в цю чергу готовності перед тими задачами, що ще не виконувалися. Іншими словами, утворяться дві черги, одна черга утвориться з нових задач, а друга черга - з тих, що раніше виконувалися, але, потрапили в стан очікування. Такий підхід дозволяє реалізувати стратегію обслуговування «по можливості закінчувати обчислення в порядку їхньої появи». Ця дисципліна обслуговування не вимагає зовнішнього втручання в хід обчислень, при ній не відбувається перерозподіл процесорного часу.

Виконані задачі

 

 

Дисципліна обслуговування SJN (shortest job next) вимагає, щоб для кожного завдання була відома оцінка в потребах машинного часу. Необхідність повідомляти ОС характеристики задач, у яких описувалися би потреби в ресурсах обчислювальної системи, привела до того, що були розроблені відповідні мовні засоби. Зокрема, мова JCL (job control language) була однією з найбільш відомих. Користувачі змушені були вказувати передбачуваний час виконання, і для того, щоб вони не зловживали можливістю вказати свідомо менший час виконання (з метою одержати результати раніше від інших), ввели підрахунок реальних потреб. Диспетчер задач порівнював замовлений час і час виконання, і у випадку перевищення зазначеної оцінки в даному ресурсі ставив дане завдання не в початок, а в кінець черги.

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

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

Для усунення цього недоліку і була запропонована дисципліна SRT (shortest remaining time, наступне завдання вимагає менше всього часу для свого завершення).

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

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

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

Виконані задачі

 

 

 

Хеш-функція і хеш-адресація

Хеш-функціею F називається деяке відображення множини вхідних елементів R на множину цілих невід’ємних чисел Z: F(r) = n, r Î R, n Î Z. Сам термін «Хеш-функція» походить від англійського терміна «hash function» (hash — «заважати», «змішувати», «плутати»).

Множина припустимих вхідних елементів R називається областю визначення хеш-функції. Множиною значень хеш-функції F називається підмножина М з множини цілих невід’ємних чисел Z: M Í Z (M є підмножиною Z, М вкючене в Z), що містить усі можливі значення, які повертаються функцією F: "r Î R: F(r) ÎМ (Для всіх r, які належ R; F(r) належ M.)

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

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

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

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

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

 

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

(реферат)

1. Поняття обчислювального процесу і ресурсу

 

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

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

І ще одне поняття є основним при розгляді ОС. Це “ресурс”.

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

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

Існують наступні режими організації обчислювального процесу:

пакетний режим;

режим розподілу часу (РРЧ);

режим реального часу.

Пакетний режим.

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

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

Характеризується максимальною пропускною здатністю та максимальною завантаженістю процесора та оперативної пам’яті. В цьому режимі користувач не має безпосереднього доступу до ЕОМ (саме під час виконання пакету програм).

Режим розподілу часу (РРЧ). В цьому режимі кожен користувач (а їх декілька) має безпосередній доступ до ЕОМ через свій термінал. Мета цього режиму – обслужити кожного користувача, забезпечивши йому допустимий час реакції ЕОМ на його запити.

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

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

Режим реального часу

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

Критерій ефективності – здатність витримати наперед задані інтервали часу між запуском програми та отриманням результатів).

Цей час називають реакцією системи, а відповідну властивість системи – реактивністю.

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

Деякі ОС можуть суміщати властивості систем різних типів, тоді один з режимів буде називатися фоновим.

Діаграма станів процесу

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

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

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

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

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

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

 

 

 

Рис. 1 Граф станів процесу

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

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

при виборі з черги планувальником (характерно для ОС, які працюють в пакетному режимі);

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

по перериванню від зовнішнього ініціативного пристрою;

при настанні запланованого часу запуску програми.

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

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

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

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

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

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

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

 

Планування і диспетчеризація процесів і задач в ОС

Стратегії планування

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

По можливості закінчувати обчислення в тому ж порядку, в якому вони були отримані;

Надавати перевагу більш коротким процесам;

Надавати усім користувачам (процесам) однакові послуги, в тому числі однаковий час очікування.

Дисципліни диспетчеризації

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

Існуючі дисципліни диспетчеризації процесів можуть бути розбиті на два класи — витісняючі (preemtive) і невитісняючі (non-preemptive).

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

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

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

Найпростіший у реалізації є дисципліна FCFS (first come — firsi served), відповідно до якої задачі обслуговуються «у порядку черги», тобто в порядку їх появи. Ті задачі, що були заблоковані в процесі роботи (потрапили в яке-небудь зі станів очікування, наприклад, через операції введення/виведення), після переходу в стан готовності ставляться в цю чергу готовності перед тими задачами, що ще не виконувалися. Іншими словами, утворяться дві черги, одна черга утвориться з нових задач, а друга черга - з тих, що раніше виконувалися, але, потрапили в стан очікування. Такий підхід дозволяє реалізувати стратегію обслуговування «по можливості закінчувати обчислення в порядку їхньої появи». Ця дисципліна обслуговування не вимагає зовнішнього втручання в хід обчислень, при ній не відбувається перерозподіл процесорного часу.

Виконані задачі

 

 

Дисципліна обслуговування SJN (shortest job next) вимагає, щоб для кожного завдання була відома оцінка в потребах машинного часу. Необхідність повідомляти ОС характеристики задач, у яких описувалися би потреби в ресурсах обчислювальної системи, привела до того, що були розроблені відповідні мовні засоби. Зокрема, мова JCL (job control language) була однією з найбільш відомих. Користувачі змушені були вказувати передбачуваний час виконання, і для того, щоб вони не зловживали можливістю вказати свідомо менший час виконання (з метою одержати результати раніше від інших), ввели підрахунок реальних потреб. Диспетчер задач порівнював замовлений час і час виконання, і у випадку перевищення зазначеної оцінки в даному ресурсі ставив дане завдання не в початок, а в кінець черги.

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

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

Для усунення цього недоліку і була запропонована дисципліна SRT (shortest remaining time, наступне завдання вимагає менше всього часу для свого завершення).

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

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

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

Виконані задачі