Презентація на тему «Керування процесами та потоками»

content: Лекція 5-6. Керування процесами та потоками.Викладач:Карчевська Ольга Ігорівна,асистент кафедри інформаційних систем та технологій,Інститут підприємництва та перспективних технологійНаціонального університету “Львівська політехніка”

content: Лекція 5-6. Керування процесами та потоками.План лекції.1. Архітектура процесора.2. Поняття процесу. Контекст процесу.3. Стани процесу. Переходи між станами.4. Створення та завершення процесів.5. Поняття потоку.6. Алгоритми планування процесів.7. Планування процесів у UNIX.8. Планування процесів у Windows.

content: 1. Архітектура процесора (загальна схема)Арифметико-логічний пристрій(arithmetic-logicunit, ALU)БЛОККЕРУВАННЯ(Control unit, CU)пам”ятьрегістр станупроцесора (PSW)шинакеруванняшина адресишина данихрегістри данихрегістри адреси

content: Архітектура процесора (складові)Найпростіший процесор складається з наступних елементів:арифметико-логічний пристрій (ALU):здійснює виконання команд;блок управління:визначає тип операції та кількість операндів;декодує адреси для ALU;шина адресина цій шині встановлюється розрахована блоком управління адреса даних, котрі мають бути зчитані з зовнішньої пам'яті.шина данихконтролер пам'яті зчитує адресу з шини адреси та розміщує одержані за цією адресою на шині данихшина управлінняпісля розміщення даних на шині даних контролер встановлює сигнал готовності на шині управління. Процесор перевіряє наявність цього сигналу і, якщо сигнал встановлено, зчитує дані для опрацювання.регістри – ділянки високошвидкісної пам'яті для зберігання даних в процесорі:регістри загального призначеннярегістри стану та управлінняіндексні регістрисегментні регістриВажливі регістри:лічильник команд (instruction pointer) – містить адресу комірки пам'яті з наступною командою, котра має виконуватись.вказівник стеку (stack pointer) – вказує на вершину поточного стеку в пам'яті. Стек містить вхідні параметри для процедур, а також інші локальні змінні, які не містяться у регістрах.слово стану програми (Program Status Word, PSW) – в цьому регістрі містяться біти управління пріоритетом процесора, режимом (користувацький чи ядра) та інші службові біти. Зазвичай, програми режиму користувача можуть зчитувати весь регістр PSW, але записувати можуть тільки в деякі з його полів.таймер:виробляє тактові імпульси для роботи процесора та синхронізації цієї роботи з роботою інших пристроїв – від таймера залежить тактова частота процесора (ГГц).

content: Цикл виконання команди процесором.Є три основні операції, котрі виконує процесор:1. Вибірка команди – блок управління вибирає команди, копіює їх з пам'яті в чергу команд та збільшує на одиницю програмний лічильник.2. Декодування – блок управління визначає тип команди, котра має виконуватись. Якщо необхідно ще отримати операнди з пам'яті, блок управління зчитує необхідні операнди та завантажує їх в арифметико-логічний пристрій і повідомляє йому, який тип операції має бути виконаний.3. Виконання – арифметико-логічний пристрій виконує команду, повертає результат та оновлює слово стану процесора.Послідовне виконання цих операцій за один раз є неефективним у зв'язку із низькою швидкістю та нераціональним розподілом часу. Тому було запроваджено конвеєрну модель роботи процесора, а згодом розроблено суперскалярну модель процесора.

content: Конвеєрна модель роботи процесора.Конвеєрна модель полягає у тому, що одночасно процесор виконує більше ніж одну команду, оскільки має окремі блоки для вибірки, декодування та виконання команд. Схематично це можна зобразити у таблиці:ЧасIFIDEXMEMWBкоманда 11команда 2команда 12команда 3команда 2команда 13команда 4команда 3команда 2команда 14команда 5команда 4команда 3команда 2команда 15команда 6команда 5команда 4команда 3команда 2Кількість стадій конвеєра - число елементарних задач на які розбивається виконання команди.Позначення у таблиці стадій конвеєра:IF (Instruction Fetch) - одержання команди,ID (Instruction Decode) - декодування команди,EX (Execute) - виконання,MEM (Memory access) - доступ до пам'яті,WB (Register write back) - запис в регістр.В кожен момент часу одна команда знаходиться на стадії виконання, тоді як інша – тільки одержання.Складністю у використанні конвеєрної моделі є виконання програм з розгалуженнями: як тільки зустрінеться команда розгалуження весь конвеєр має зупинитися поки ця команда не виконається і не буде відома наступна команда.Для таких випадків з метою підвищення ефективності роботи процесора використовують алгоритми динамічного виконання команд: 1) прогнозування розгалужень (branch prediction); 2) аналіз потоку команд (out-of-order execution); 3) попереднє виконання (data forwarding).

content: Суперскалярний процесор має декілька виконавчих блоків:1) для цілочисельної арифметики2) для арифметики з плаваючою крапкою3) для логічних операцій.Одночасно вибираються декілька команд, котрі декодуються та поміщаються в буфер, де очікують можливості свого виконання. Коли виконавчий блок вивільняється, він звертається до буфера за наступною командою, яку він може виконати.Суперскалярна модель роботи процесора.БлоквибіркиБлокдекодуванняБуферкомандВиконавчийблокБлоквибіркиБлокдекодуванняВиконавчийблокВиконавчийблок

content: 2. Поняття процесу. Контекст процесу.Процес – програма в режимі виконання.З кожним процесом пов'язаний адресний простір, котрий міститькод програмидані до програмистек програмиЗ кожним процесом також пов'язаний набір регістрів.Кожному процесу відповідає контекст, котрий включає:користувацький контекствміст адресного просторувміст сегментів коду, даних, стекурегістровий контекствміст апаратних регістрів (лічильника команд, стану процесу, вказівника стеку, регістрів загального призначення)контекст системного рівняідентифікатор процесуідентифікатор батьківського процесустан процесупріоритет процесуідентифікатор користувача

content: 3. Стани процесу. Переходи між станами.Можливі стани процесу:1. Виконання (процес використовує процесор).2. Готовність (процес тимчасово припинений, щоб дозволити виконуватися іншому процесу).3. Блокування (процес не може бути запущений перш, ніж відбудеться деяка зовнішня подія).ОчікуванняГотовністьВиконання1423ЗавершенняСтворенняПереходи між процесами:Процес заблокований в очікуванні введення данихДиспетчер процесів вибрав інший процесДиспетчер вибрав даний процесВхідні дані стали доступні для даного процесуВ операційній системі UNIX також є особливий стан процесу - зомбі. Процес переходить у цей стан якщо він завершився раніше, ніж цього очікував батьківський процес.

content: Існують чотири основні події, що призводять до створення процесів:Ініціалізація системи. (winload.exe, winresume.exe, ntoskrnl.exe, smss.exe, hal.dll, wininit.exe, services.exe; init, rc, ttytab, getty)Виконання запущеним процесом системного виклику створення процесу.Запит користувача на створення процесу.Ініціалізація пакетного завдання.В UNIX для створення процесу використовується системний виклик fork(), у Windows - CreateProcess().Після створення нового процесу обидва процеси мають власний адресний простір.Початковий стан дочірнього процесу є точною копією батьківського процесу.4. Створення та завершення процесів.

content: Завершення процесів.Процес завершується одним з наступних чотирьох способів:Нормальне завершення (добровільне).Завершення внаслідок помилки (добровільне).відсутність файлузаборона доступуЗавершення внаслідок фатальної помилки (примусове).неправильно написана програмаділення на нульпосилання на неіснуючу чи заборонену область пам'яті.Знищення іншим процесом (примусове).Виконання системного виклику exit() у UNIX чи ExitProcess() у Windows

content: 5. Поняття потоку.Потік (thread) – окрема послідовність інструкцій в рамках одного процесу.З кожним потоком пов'язується:лічиньник команд;регістри;стек;стан (готовність, виконання, блокування).Спільним для усіх потоків конкретного процесу є:адресний простірглобальні зміннівідкриті файлиТаймеристатистична інформація.Переваги використання потоків замість багатьох процесів є:Спрощення програми.Створення потоку є швидшим за створення процесу приблизно у 100 разів.Підвищення продуктивності програми, оскільки є можливість одночасного виконання різних дій.Приклад: текстовий редактор з трьома потоками може одночасно взаємодіяти з користувачем, форматувати текст та записувати на диск резервну копію.

content: 6. Алгоритми планування процесів.Планування - забезпечення почергового доступу процесів до одного процесору.Планувальник - відповідальна за це частина операційної системи.Алгоритм планування - використовуваний алгоритм для планування.Ситуації, коли необхідно планування:створення процесузавершення роботи процесублокування процесу на операції введення/виведення, семафорі, тощо.при перериванні введення/виведення.Є дві основні стратегії планування:Алгоритм невитісняльної багатозадачності (непріоритетний) – потоки можуть виконуватись упродовж необмеженого часу і не можкть бути перервані операційною системою. Потоки самі передають керування системі коли завершують роботу або переходять у стан очікування.(можна використати у системах реального часу, системах пакетної обробки)Алгоритм витісняльної багатозадачності (пріоритетний) – потоки можуть бути перервані планувальником операційної системи для передачі керування іншим потокам. Процес працює тільки відведений період часу, після цього він припиняється по таймеру, щоб передати керування планувальнику.(однозначно має бути реалізований у інтерактивних системах).Завдання алгоритмів планування:1. Ефективне використання ресурсів,2. Скорочення часу даремного навантаження,3. Справедливість - кожному процесу справедливу частку процесорного часу.

content: Планування за принципом FCFSАлгоритм називається від абревіатури First Come – First Served (першим надійшов – першим обслужений).Суть: процеси, котрі переходять у стан готовності заносяться у чергу. Як тільки процесор звільняється, він завантажує перший у черзі процес.Процес1Процес2Процес3Процес4Процес5Процесорчерга+-1) легкість реалізації;середній час очікування залежить від взаємного розташування процесів,є невитісняльним, може призвести до “зависання системи” при монопольному заволодінні процесором окремим потоком.

content: Кругове планування (Round robin)Суть: кожному потоку виділяють однаковий квант часу, упродовж якого цьому потоку дозволено виконуватись. Після вичерпання кванту його переривають і перемикають процесор на виконання інструкцій іншого потоку.ПроцесорПроцес1Процес2Процес3Процес4Процес5+-легкість реалізації;справедливість (всі потоки рівні).потрібно ретельно підбирати довжину кванту, оскільки для короткого кванту буде багато часу витрачатись на перемикання, для довгого – окремий користувач, який останнім запустив процес, може досить довго чекати своєї черги.

content: Планування з пріоритетамиСуть: кожному потоку ставиться у відповідність пріоритет. На виконання ставиться потік із найвищим пріоритетом із черги готових потоків.Пріоритети можуть надаватись статично або динамічно.ПроцесорПроцес1Процес2Процес8Процес3Процес5Процес7Процес10Процес12Процес15Процес11Процес14Процес16Процес17пріоритет 1пріоритет 2найвищийпріоритет+-насамперед виконуються найважливіші завдання;Процеси з дуже низьким пріоритетом можуть не дочекатися своєї черги.

content: Планування на підставі характеристик подальшого виконання.Найпоширеніший алгоритм цього класу: “перший – з найкоротшим часом виконання” (Shortest time to completion, STCF).Суть: з кожним потоком пов'язують час виконання і вибирають потік з найкоротшим часом.+-теоретично є оптимальним за критерієм середнього часу очікування;важко передбачити час виконання потоків,несправедливий до потоків з довшим часом виконання.ПроцесорПроцес 42 мсПроцес 53 мсПроцес 26 мсПроцес 310 мсПроцес 115 мсПроцес 115 мсПроцес 26 мсПроцес 310 мсПроцес 42 мсПроцес 53 мсПочаткова черга:

content: Багаторівневі черги зі зворотнім зв'язком.Суть: є кілька черг готових потоків із різним пріоритетом, при цьому потоки із нижчим пріоритетом виконуються тільки коли верхні черги порожні. При цьомупотокам дозволено переходити з рівня на рівень,в кожній черзі потоки об'єднуються за довжиною інтервалу використання процесора.+-є найуніверсальнішим алгоритмом, за певного налаштування параметрів його можна звести до попередніх;важко передбачити час виконання потоків,несправедливий до потоків з довшим часом виконання.пріоритетЧерга алгоритму FIFOДовжина квантаПотік не вичерпав квантаПотік вичерпав квантПотік давно не одержував керування

content: Лотерейне планування.кожен процес отримує певну кількість лотерейних квитків, кожен дає право використовувати процесор певний час Т;через проміжок часу Т планувальником випадково вибирається лотерейний квиток;потік з квитком, який “виграв”, дістає керування.ПОТІК 1квиток Аквиток M…ПОТІК iквиток Nквиток X………ПЛАНУВАЛЬНИК:“виграшний” – квиток Хотримує процесор на час ТЗа допомогою лотерейного планування можна емулювати кругове планування, планування з пріоритетами, забезпечувати розподіл процесорного часу між потоками.

content: 7. Планування процесів у UNIX.Створення процесу викликом функції fork().ПРОЦЕСPID 11дані з областейпам”яті процесувиконувана програма,відкриті файли і т.д.ПРОЦЕСPID 28дані з областейпам”яті процесувиконувана програма,відкриті файли і т.д.fork()PID нащадкакопіякопіядії...дії...Контекст процесу:Користувацький (вміст віртуального адресного простору, сегментів програмного коду, даних, стеку, сегментів файлів)регістровий (вміст апаратних регістрів)структури даних ядраСтатична частина контексту процесу:ідентифікатор процесу (PID)ідентифікатор батьківського процесу (PPID)стан процесуідентифікатори користувача (для визначення меж доступу процесу)пріоритет процесу (змінюється динамічно за допомогою системного виклику nice)таблиця дескрипторів відкритих файлівДинамічна частина контексту процесу – стеки, що використовуються процесом при виконанні в режимі ядра і в режимі користувачаПланування процесів здійснюється на основі схеми з кільцевою чергою та пріоритетами. На основі значення пріоритету визначаються можливість процесу перебувати в оперативній пам'яті і конкурувати за процесор, квант часу для роботи з процесором, місце в загальній черзі.

content: Планування процесів у Linux.Процеси в системі:реального часу із плануванням за принципом FIFOреального часу із круговим плануваннямзвичайніПроцеси реального часу:Мають пріоритет над звичайними процесамиПроцес із плануванням за схемою FIFO виконується доти, доки він сам не віддасть процесор, або поки не витісниться процесом реального часу з вищим пріоритетомАналогічно для процесів з круговим плануванням, крім того, вони витісняються при вичерпанні кванту часуАлгоритм планування звичайних процесів.Процесорний час поділяється на епохи.Кожен процес в межах епохи має певний квант часу.Кожен процес виконується лише один раз впродовж епохи.Епоха завершується після вичерпування квантів всіх готових до виконання процесів.

content: 8. Планування процесів у Windows.Планування процесів передбачає розв'язання таких задач:Облік відносних пріоритетів потоківМінімізація часу відгуку інтерактивних програмОдиниця планування – потік.Значення пріоритету – в межах від 1 до 31;16 – 31 - пріоритет реального часу (для дій, час виконання яких є критичним чинником)1 – 15 - динамічні пріоритети (для потоків застосувань користувача)Присвоєння пріоритетуПРОЦЕСреального часу (real-time, 24)високий (high, 13)нормальний (normal, 8)невикористовуваний (idle, 4)потік 1потік n…присвоєння класунайвищий (+2)вище за нормальний (+1)нормальний (+0)нижче за нормальний (-1)найнижчий (-2)відносні пріоритети

content: Планування процесів у Windows.Новий потік для виконання вибирається коли:минув квант часу для потокупотік перейшов у стан очікування подіїпотік перейшов у стан готовності до виконанняПотік може бути витіснений коли:Потік перейшов у стан очікуванняМинув квант часу потокуПотік з вищим пріоритетом перейшов у стан готовності до виконанняЗмінився пріоритет потоку або пріоритет іншого потокуДинамічна зміна пріоритету.Завершення операції введення-виведення підвищує пріоритет (дискові операції - +1, введення з клавіатури, обробка події миші - +6)Для потоків інтерактивних застосувань вихід із стану очікування - +2Перехід в стан готовності потоків, пов'язних з відображенням інтерфейсу користувача - +2Потоки, які не виконувались впродовж тривалого часу, підвищують пріоритет.

content: Висновки:Найпростіший процесор складається з наступних елементів: арифметико-логічний пристрій (ALU), блок управління, шина адреси, шина даних, шина управління, регістрів, таймеру.2. Процес – програма в режимі виконання. З кожним процесом пов'язаний адресний простір, котрий містить код програми, дані до програми, стек програми.3. Можливі стани процесу: виконання, готовність, блокування.4. Потік (thread) – окрема послідовність інструкцій в рамках одного процесу.5. Алгоритми планування процесів: планування за принципом FCFS, кругове планування (Round robin), планування з пріоритетами, планування на підставі характеристик подальшого виконання, багаторівневі черги зі зворотнім зв'язком, лотерейне планування.

content: Література:Шеховцов В. А. Операційні системи. – К.: BHV, 2005 . -576 с.Таненбаум. Э. Современные операционные системы.2-е изд. – СПб.: Питер, 2002. – 1040 с.