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

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

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

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

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

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

Конвеєрна модель роботи процесора.
Конвеєрна модель полягає у тому, що одночасно процесор виконує більше ніж одну команду, оскільки має окремі блоки для вибірки, декодування та виконання команд. Схематично це можна зобразити у таблиці:
Час
IF
ID
EX
MEM
WB
команда 1
1
команда 2
команда 1
2
команда 3
команда 2
команда 1
3
команда 4
команда 3
команда 2
команда 1
4
команда 5
команда 4
команда 3
команда 2
команда 1
5
команда 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).

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

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

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

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

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

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

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

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

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

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

Планування на підставі характеристик подальшого виконання.
Найпоширеніший алгоритм цього класу: “перший – з найкоротшим часом виконання” (Shortest time to completion, STCF).
Суть: з кожним потоком пов'язують час виконання і вибирають потік з найкоротшим часом.
+
-
теоретично є оптимальним за критерієм середнього часу очікування;
важко передбачити час виконання потоків,
несправедливий до потоків з довшим часом виконання.
Процесор
Процес 4
2 мс
Процес 5
3 мс
Процес 2
6 мс
Процес 3
10 мс
Процес 1
15 мс
Процес 1
15 мс
Процес 2
6 мс
Процес 3
10 мс
Процес 4
2 мс
Процес 5
3 мс
Початкова черга:

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

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

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

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

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

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

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

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