Iванов Юрій Олександрович

Факультет: Обчислювальної техніки інформатики
Спеціальність: Системне програмування

Тема випускної роботи:

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

Науковий керівник: Святний Володимир Андрійович

Реферат з теми випускної роботи

ВСТУП

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

АКТУАЛЬНІСТЬ

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

ЦІЛЬ, ЗАВДАННЯ, ОБ'ЄКТ ДОСЛІДЖЕННЯ

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

НАУКОВА НОВИЗНА

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

ОГЛЯД ЛІТЕРАТУРИ

Основні поняття планування процесів. Планування - забезпечення почергового доступу процесів до одного процесора [3]. Планувальник - відповідальна за це частина операційної системи. Алгоритм планування - використовуваний алгоритм для планування. Алгоритм планування без перемикань (непріоритетний) - не вимагає переривання по апаратному таймері, процес зупиняється тільки коли блокується або завершує роботу. Алгоритм планування з перемиканнями (пріоритетний) - вимагає переривання по апаратному таймері, процес працює тільки відведений період часу, після цього він припиняється по таймері, щоб передати керування   планувальникові. Необхідність алгоритму планування залежить від завдань, для яких буде використатися операційна система. Основні три системи: системи пакетної обробки - можуть використати непріоритетний і пріоритетний алгоритм (наприклад: для розрахункових програм); інтерактивні системи - можуть використати тільки пріоритетний алгоритм, не можна допустити щоб один процес зайняв надовго процесор (наприклад: сервер загального доступу або персональний комп'ютер); системи реального часу - можуть використати непріоритетний і пріоритетний алгоритм (наприклад: система керування автомобілем). У роботі розглядаються саме системи реального часу. Стандартні алгоритми планування [4]:

• "Перший прийшов - першим обслужений" (FIFO - First In Fist Out)

Процеси ставляться в чергу в міру надходження.

Переваги:

• Простота
• Справедливість (як у черзі покупців, хто останній прийшов, той виявився наприкінці черги)

Недоліки:

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

• "Найкоротше завдання - перша" [5]

Переваги:

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

Недоліки:

• Довгий процес процесор, що зайняв, не пустить більше нові короткі процеси, які прийшли пізніше.

• Найменший час, що залишився, виконання

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

• Трехуровневое планування

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

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

• Циклічне планування

Найпростіший алгоритм планування й часто використовуваний.

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

Переваги:

• Простота
• Справедливість (як у черзі покупців, кожному тільки по кілограму)

Недоліки:

• Якщо часті перемикання (квант - 4мс, а час перемикання дорівнює 1мс), то відбувається зменшення продуктивності.
• Якщо рідкі перемикання (квант - 100мс, а час перемикання дорівнює 1мс), то відбувається збільшення часу відповіді на запит.

• Пріоритетне планування [6,7]

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

Пріоритет може бути динамічний і статичний.

Динамічний пріоритет може встановлюватися так:

П=1/Т, де Т- частина використаного востаннє кванта

Якщо використано 1/50 кванта, то пріоритет 50.

Якщо використано весь квант, то пріоритет 1.

Т.е. процеси, обмежені уведенням/виводу, будуть мати пріоритет над процесами обмеженими процесором.

Часто процеси поєднують по пріоритетах у групи, і використають пріоритетне планування серед груп, але усередині групи використають циклічне планування.

• Групи з різним квантом часу[8]

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

• Групи з різним призначенням процесів

 Такий механізм дозволяє підвищити пріоритет роботи із клієнтом. 

• Гарантоване планування

У системі з n-процесами, кожному процесу буде надано 1/n часу процесора.

• Лотерейне планування

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

• Справедливе планування

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

• Планування в системах реального часу [9]

Системи реального часу діляться на:

• тверді (тверді строки для кожного завдання) - керування рухом
• гнучкі (порушення тимчасового графіка не бажані, але припустимі) - керування відео й аудио

Зовнішні події, на які система повинна реагувати, діляться:

• періодичні - потокове відео й аудио
• неперіодичні (непередбачені) - сигнал про пожежу

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

m - число періодичних подій

i - номер події

P(i) - період надходження події

T(i) - час, що йде на обробку події

Т. е. перевантажена система реального часу є не планованою. 

• Планування однорідних процесів

Як однорідні процеси можна розглянути відео сервер з декількома відео потоками (трохи користувачів дивляться фільм).

Т.к. всі процеси важливі, можна використати циклічне планування.

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

• Загальне планування реального часу

Використається модель, коли кожен процес бореться за процесор зі своїм завданням і графіком його виконання.

Планувальник повинен знати:

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

Розглянемо приклад із трьох процесів.

Процес А запускається кожні 30мс, обробка кадру 10мс

Процес У частота 25 кадрів, тобто кожні 40мс, обробка кадру 15мс

Процес Із частота 20 кадрів, тобто кожні 50мс, обробка кадру 5мс

Перевіряємо, чи можна планувати ці процеси.

10/30+15/40+5/50=0.808<1

Умова виконується, планувати можна.

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

• Статичний алгоритм планування RMS (Rate Monotonic Scheduling)[10]

Процеси повинні задовольняти умовам:

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

Пріоритет у цьому алгоритмі пропорційний частоті.

Процесу А він дорівнює 33 (частота кадрів)

Процесу У він дорівнює 25

Процесу З він дорівнює 20

Процеси виконуються по пріоритеті.

• Динамічний алгоритм планування EDF (Earliest Deadline First)

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

При більших завантаженнях системи EDF має переваги.

Розглянемо приклад, коли процесу А потрібно для обробки кадру - 15мс.

Перевіряємо, чи можна планувати ці процеси.

15/30+15/40+5/50=0.975<1

Завантаження системи 97.5%

ВИСНОВОК 

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

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Святний В.А. Стан та перспективи розробок паралельних моделюючих середовищ для складних динамічних систем з розподіленими та зосередженими параметрами / В.А Святний, О.В. Молдованова, А.М. Чут // «Паралельне моделювання 2008».

2. Huang W. A parallel computing framework for dynamic power balancing in adaptive mesh refinement applications proceedings of Parallel Computational Fluid Dynamics / W. Huang, D.K. Tafti. – Wiiliamsburg.: VA, 1999. – 670 p.

3. Таненбаум Э. Современные операционные системы. 2-е изд / Э. Танненбаум. – СПб.: Питер, 2002. – 1040 с.: ил.

4. Олифер В.Г. Сетевые операционные системы / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2002. – 504 с.: ил.

5. Информационно аналитический центр о параллельных вычислениях и суперЭВМ [Электронный ресурс] http://parallel.ru

6. Таненбаум Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум, М. ван Стеен. – СПб.: Питер, 2003. – 887 с.: ил.

7. Бовет Д. Ядро Linux / Д. Бовет, М. Чезати. – СПб.: БХВ-Петербург, 2007. – 1104 с.: ил.

8.  Martello S. Knapsack Problems / S. Martello, P. Toth – NY.: Wilies, 2006. – 275 p.

9. Pochet Y. Production Planning by Mixed Integer Programming / Y. Pochet, Laurence A. Wolsey – NY.: Springer, 2000. – 260 p.

10. Курс лекций о теории планирования [Электронный ресурс] http://www.intuit.ru/department/os/osintro/3/