Планувальник і диспетчер процесів у системі розподілу
часу
1
Введення
1.1
Коли комп'ютер працює в багатозадачному режимі, на ньому можуть бути активними
(знаходиться в стані готовності) кілька процесів (від двох і більше),
що намагаються одночасно отримати доступ до одного процесора. Тому необхідно
вибирати, який процес запустити наступним. Відповідальна за це частина
Операційної системи (ОС) називається планувальником, а використовуваний алгоритм --
алгоритмом планування. Крім правильного вибору наступного процесу,
планувальник також повинен дбає про ефективне використання процесора,
оскільки перемикання між процесами потребує витрат.
1.2
У багатозадачному режимі процеси можуть знаходитися в одному з трьох основних
станів: виконання, готовність або очікування. Граф зміни станів
процесів проілюстровано на малюнку 1.1. У стані виконання може
знаходитися тільки один процес. У стані готовності можуть перебувати
кілька процесів. Для оперативної вибірки процесів на виконання ОС завжди
підтримує двусвязний список готових процесів. У цьому переліку завжди
знаходиться хоча б один елемент (процес, що запускається в разі «простоювання»
системи). У стані очікування також можуть знаходитися кілька процесів. Для
організації очікують процесів також використовуються двусвязние списки. Але, в
відміну від списку готових процесів, для очікують процесів використовується один
список для кожного конкретного ресурсу. Скільки поділюваних ресурсів, стільки й
списків заблокованих процесів.
Малюнок
1.1 - Граф зміни стану процесів
На
малюнку 1.1 номерами позначені ситуації, коли відбувається цей перехід: 1 --
планувальник вибирає даний процес зі списку готових процесів, 2 - квант
даного процесу минув і планувальник вибирає інший процес, 3 - процес
блокується, чекаючи вхідних даних, 4 - надійшли очікувані вхідні дані.
2
Алгоритм Round Robin
2.1
Одним з найбільш старих, простих, справедливих і часто використовуваних алгоритмів
планування є алгоритм циклічного планування або Round Robin (RR).
Він працює за наступним принципом. Кожному процесу надається деякий
інтервал часу процесора (квант часу). Якщо до кінця кванта часу
процес все ще працює, він переривається, а управління передається іншому
процесу. Якщо процес блокується або припиняє роботу раніше відведеного йому
кванта часу, то перехід управління відбувається в цей момент. Алгоритм роботи
проілюстровано на малюнку 2.1. Так як використовується пріоритетне
планування, то спочатку зі списку готових процесів вибирається процес з
найвищим пріоритетом. Якщо в списку залишилися тільки процеси з однаковим
пріоритетом, то вибирається самий перший. Після того, як новий процес потрапляє
в чергу готових процесів, він поміщається в кінець черги. Коли процес
відпрацював свій квант або вийшов зі стану блокування, він також міститься в
кінець черги.
Малюнок
2.1 - Схема роботи алгоритму RR
Самим
важливим атрибутом даного алгоритму є довжина кванта часу, відведеного
процесу. Занадто малий квант часу призведе до частого перемикання процесів
і невеликий ефективності. Занадто великий квант часу може призвести до
повільного реагування на короткі інтерактивні запити. «Значення кванта
часу близько 20-50 мс часто є розумним компромісом [1 ].»
3 Перепланування процесів
3.1
Перепланування - це процес вибору наступного запускається процесу і
перемикання на нього. Перепланування повинна відбуватися тільки в строго
певні моменти часу. Приклад вибору моментів перепланування в ОС з
відносним пріоритетом і фіксованим квантом часу представлений в таблиці
3.1.
Таблиця
3.1 - Моменти перепланування
№ п/п
Момент перепланування
1
Завершення процесом своєї роботи (системні виклики
exit (), cancel () та ін.)
2
Блокування процесу на системному виклику (операції ВВ,
семафор, в очікуванні сигналу і т.д.).
3
Добровільне блокування процесу (системний виклик wait (),
sleep () та ін.)
4
Закінчення кванта часу, відведеного процесу.
Етапи
перемикання між процесами представлені в таблиці 3.2.
Таблиця
3.2 - Етапи перемикання між процесами
№ етапу
Опис етапу
1
Переключитися з режиму користувача
в режим ядра (через переривання).
2
Зберегти контекст поточного процесу.
3
Зберегти карту пам'яті (біти-ознаки звернення до сторінок пам'яті)
поточного процесу.
4
Запустити планувальник для вибору нового процесу.
5
Завантажити контекст нового процесу.
6
Завантажити карту пам'яті нового процесу
в блок управління пам'яттю.
7
Запустити новий процес.
4 Дескриптор і контекст процесу
4.1
Для забезпечення багатозадачності в ОС використовується таблиця процесів (список), в
якої знаходяться вказівники на дескриптори процесів. Дескриптори містять
статичну інформацію про процес. Крім цього в ОС також використовується
динамічна інформація про поточний (що працює) процесі. Сукупність цієї
інформації називається контекстом процесу. Приклади дескриптора і контексту процесу
представлені в таблицях 4.1 та 4.2 відповідно.
Таблиця
4.1 - Дескриптор процесу
Назва
поля
Опис
Діапазон
допустимих
значень
Ідентифікатор процесу
Число, однозначно ідентифікує процес в ОС.
У системі не повинно бути процесів з однаковими
ідентифікаторами.
0 - 216
залишився квант часу
Призначається ГР при створенні процесу. З кожним перериванням
від таймера дане значення зменшується на єдиному цу (у активного процесу).
0 - 255
Назва
поля
Опис
Діапазон допустимих значень
Коли значення досягне 0, процес переноситься в кінець
черги готових процесів.
Пріоритет процесу
Умовне значення, за яким планувальник визначає,
який процес вибрати на обслуговування. Від 0 до 4 - пріоритети, які призначаються
ядром ОС для своїх потреб. Від 5 до 9 - пріоритети, що призначаються користувачем
для своїх потреб. 0 - найвищий пріоритет, 9 - найнижчий пріоритет.
0 - 9
Базовий адреса контексту процесу
Вміст регістра TR (містить селектор дескриптора в
GDT). Команда LTR завантажує регістр TR. Крім завантаження безпосередньо
селектора, процесор автоматично завантажує базова адреса, ліміт і атрибути
з дескриптора, що знаходиться в GDT. Команда STR зберігає вміст регістру
TR в РОН або ОЗУ.
0 - 216
Назва
поля
Опис
Діапазон допустимих значень
Інформація про ресурси
Список, що містить інформацію про відкриті файлах,
програмних каналах, іменованих каналах, загальних областях ВП і т.д.
0 - 216
Ідентифікатор батьківського процесу
Для прискореної роботи системного виклику getppid ().
0 - 216
Список ідентифікаторів процесів-нащадків
Для прискореної роботи системного виклику wait ().
0 - 216
Ідентифікатор користувача
Для забезпечення багатокористувацького режиму.
0 - 216
Таблиця
4.2 - Контекст процесу
Назва
поля
Опис
Діапазон
допустимих
значень
РОН
Вміст всіх регістри загального призначення. EAX, EBX, ECX,
EDX. Дане поле повинно тлумачитися як 4 поспіль збережених 4-байтних
значень.
4 * (0 - 232)
Селектори
Селектор кодового сегмента (CS), селектор сегменту даних
(DS), селектор сегменту стека (SS) і селектори ES, FS, GS дескрипторів в LDT.
Дане поле повинно тлумачитися як 6 програм поспіль 2-байтних значень.
6 * (0 - 216)
Регістри
зсувів
Вміст всіх регістрів зсувів. EIP, ESP, EBP, ESI і
EDI. 5 поспіль 4-байтних значень.
5 * (0 - 232)
Регістр прапорів
Вміст регістра EFLAGS.
0 - 232
Назва
поля
Опис
Діапазон
допустимих
значень
Регістр LDTR
Селектор дескриптора LDT в GDT.
0 - 247
Регістр CR3
Вміст регістра, що містить базовий адреса каталозі
сторінок.
0 - 232
Базовий адреса бітового масиву дозволених операцій
введення/виводу
Використовується для обмеження доступу до процесу
визначених портах ВВ. 0 - доступ до порту заборонений, 1 - доступ до порту
дозволений.
0 - 255
5 Спецификация на розробку програмного компонента
«Планувальник і диспетчер процесів (ПІДП)»
5.1
Загальний опис
5.1.1
ПІДП - це програмний комплекс, що викликається, коли потрібна будь-яка
дія, пов'язана з адмініструванням процесів в системі (створення/видалення
процесу, перенесення процесу з черги заблокованих в чергу готових і
т.д.). Дана програма повинна максимально швидко виконувати свої дії, так
як вона викликається досить часто.
5.2
Основні компоненти
5.2.1
Планувальник - частина комплексу ПІДП, призначена для прийняття рішення про
виборі наступного процесу на виконання і перенесення процесів між чергами.
5.2.2
Диспетчер - це частина програмного комплексу ПІДП, призначена для
реалізації рішення, обраного планувальником.
5.3
Відповідальність компонентів
5.3.1
Спочатку відбувається пошук рішення, а потім його реалізація, тобто спочатку
викликається планувальник, а потім вже диспетчер. Також може викликатися тільки
планувальник, а диспетчер - ні (наприклад, коли потрібно просто перенести процес
з черги заблокованих процесів в чергу готових, якщо він отримав дані
від ВУ). Алгоритми роботи планувальника і диспетчера процесів представлені в
додатку А.
5.4
Правила комунікації
5.4.1
Функції, що забезпечують планування процесів, обмінюються покажчиками на
дескриптори процесів. Функція, що забезпечує перемикання контексту, працює
з покажчиками на контексти процесів.
5.5
Основні структури даних
5.5.1
Дескриптор (представлений в таблиці 4.1), контекст (представлений в таблиці 4.2), список
готових процесів (організований за принципом алгоритму RR з відносними
пріоритетами), список заблокованих процесів (організований за принципом список
списків, тобто всередині списку заблокованих процесів знаходяться списки
процесів, які очікують на відповідь від НЖМД, які очікують на відповідь від НГМД, що очікують
певний семафор, які очікують на певну чергу повідомлень, що очікують
певного сигналу і т.д.).
5.5.2
Покажчик на початок списку готових процесів, вказівник на кінець списку готових
процесів.
5.5.3
Покажчик на структуру-описатель списку списків заблокованих процесів.
Дана структура зберігає в собі інформацію про початок і кінець кожної черги. У
випадку появи нового пристрою в системі необхідно лише створити нову
чергу і додати інформацію про її початку і кінці в дану структуру.
6 Системні виклики «Створити процес» і «Видалити
процес »
6.1
Системний виклик «Створити процес»
Системний
возів «Створити процес» служить для створення майже повної копії батьківського
процесу (процесу, в якому був ініційований системний виклик). Для створення
майже повної копії викликає процесу ОС повинна скопіювати деякі дані
з процесу-батька в процес-нащадок. Виконання процесів розділяється після
даного системного виклику. Назва системного виклику виклику: creat_proc. Вхідні
дані: відсутні. Вихідні дані: ідентифікатор процесу. Сам системний
виклик реалізований в ядрі ОС, до якого звертається програма-заглушка в
системної бібліотеці (через переривання). Перелік дій, що здійснюються ядром
ОС, представлений в таблиці 6.1.
Таблиця
6.1 - Системний виклик «Створити процес»
№ етапу
Опис етапу
1
Перевірити можливість створення нового процесу (кол-во
процесів <65535).
2
Виділити пам'ять в області ОС для дескриптора процесу.
3
Створити дескриптор для нового процесу.
4
Призначити новому процесу ідентифікатор.
5
Записати в полі «Ідентифікатор батьківського процесу»
ідентифікатор процесу-батька.
6
Копіювати вміст полів (пріоритет, інформація про
ресурсах і код користувача, що запустив процес) дескриптора
процесу-батька.
7
Виділити пам'ять в області користувача для процесу.
8
Виділити пам'ять в області ОС для контексту процесу.
9
Налаштувати вміст контексту нового процесу.
10
Повністю скопіювати образ пам'яті з процесу-батька.
11
Оновити інформацію у процесу-батька про нащадків.
12
Додати покажчик про новий процесі список готових
процесів.
6.2
Системний виклик «Видалити процес»
Системний
виклик «Видалити процес» служить для видалення вже існуючого процесу. Причому
видалення здійснюється самим ядром в примусовому порядку. Назва системного
виклику: kill_proc. Вхідні дані: ідентифікатор процесу. Вихідні дані:
відсутні. Сам системний виклик реалізований в ядрі ОС, до якого звертається
програма-заглушка в системній бібліотеці (через переривання). Також
програма-заглушка перевіряє допустимість вхідного параметра. Тобто
ідентифікатор процесу повинен бути беззнакові 2-байтним цілим числом. Перелік
дій, що здійснюються ядром ОС, представлений в таблиці 6.2.
Таблиця
6.2 - Системний виклик «Видалити процес»
№ етапу
Опис етапу
1
Перевірити існування даного ідентифікатора в таблиці
процесів.
2
Видалити інформацію про поточний процес з
процесу-батька.
№ етапу
Опис етапу
3
Видалити з усіх черг покажчик на дескриптор поточного
процесу.
4
Звільнити пам'ять від дескриптора, контексту та ВП рівня
користувача поточного процесу.
5
Викликати планувальник.
7 Висновок
7.1
У даному проекті була розглянута розробка програмно-апаратного комплексу
«Планувальник і диспетчер процесів в системі поділу часу» з алгоритмом
планування RR і відносним пріоритетом, а також деякі системні
виклики. Проект показав, що програму планувальник треба розробляти дуже
ретельно, тому що вона є основою будь-якої багатозадачного ОС. У підсумку
вийшло, що для нормальної роботи планувальника і диспетчера процесів
необхідно мати в області ОП ОС як мінімум дескриптор і контекст для кожного
процесу, список готових і заблокованих процесів. Також з'ясувалося, що
перемикання процесів - це тривала операція, тому що доводиться
перемикатися з режиму користувача в режим ядра, запускати процес
планування, потім диспетчеризації, а потім знову перемикатися назад, на
рівень користувача. Системні виклики створення та вилучення процесу також
потребують часу на обробку, так як їм теж потрібно маніпулювати даними в
області ОЗУ ОС, для чого потрібно також перемикатися на рівень ядра.
Додаток
А
Графічні
матеріали
Малюнок
А.1 - Блок-схема алгоритму роботи планувальника
з
чергою гот?? вих процесів
Малюнок
А.2 - Блок-схема алгоритму роботи планувальника
з
чергою заблокованих процесів
Малюнок
А.3 - Блок-схема алгоритму роботи планувальника
Малюнок
А.4 - Блок-схема алгоритму диспетчеризації
Малюнок
А.5 - Структурно-функціональна схема
планувальника
й диспетчера процесів
Список літератури
Таненбаум
ЕС Сучасні операційні системи. 2-е изд. - М.: ПИТЕР, 2006.
Embedded X86 Programming: Protected
Mode by Jean Gareau
Керівництво
по процесора Intel i80486.
http://www.brokensword.narod.ru/
http://asmdev.narod.ru/asmos/asmos.html
http://lowlevel.ru/
http://xkernel.excode.ru/
Вихідний
код ядра ОС Linux версії 0.01
http://www.citforum.ru/operating_systems/bach/contents.shtml
Для
підготовки даної роботи були використані матеріали з сайту http://referat.ru
