Лекция3-2017. Процессы и их поддержка в операционной системе Понятие процесса Уточнение терминологии
 Скачать 4.26 Mb.
|
Процессы и их поддержка в операционной системеПонятие процесса Уточнение терминологииТермин «программа» Термин «задание» Термин «процесс» – не может использоваться для описания происходящего внутри ОС. – не может использоваться для описания происходящего внутри ОС. Для статических объектов Для динамических объектов Понятие процесса Процесс и программаТермин «процесс» характеризует совокупность
Процесс ≠ программа, которая исполняется: для исполнения одной программы может организовываться несколько процессов в рамках одного процесса может исполняться несколько программ в рамках процесса может исполняться код, отсутствующий в программе находящуюся под управлением ОС Состояния процессадопуск к планированию процесс не исполняется исполнение вход выход приостановка ожидание готовность выбран для исполнения ожидание события прерывание событие произошло рождение закончил исполнение завершение работы Набор операцийсоздание процесса – завершение процесса запуск процесса – приостановка процесса блокирование процесса – разблокирование процесса (изменение приоритета) одноразовые многоразовые Process Control Block и контекст процессасостояние процесса программный счетчик содержимое регистров данные для планирования использования процессора и управления памятью учетная информация сведения об устройствах ввода-вывода, связанные с процессом Регистровый контекст Системный контекст PCB Код и данные в адресном пространстве Пользовательский контекст Контекст процесса Процесс 1 Процесс 2 Процесс 12 Процесс 255 Процесс 3 Процесс 14 Процесс 15 Процесс 128 Процесс 4 Процесс 23 Процесс 192 Создание процессаПорождение нового PCB с состоянием процесса рождение Присвоение идентификационного номера Выделение ресурсов Занесение в адресное пространство кода и установка значения программного счетчика Окончание заполнения PCB Изменение состояния процесса на готовность из ресурсов родителя из ресурсов ОС дубликат родителя из файла Завершение процессаИзменение состояния процесса на закончил исполнение Освобождение ресурсов Очистка соответствующих элементов в PCB Сохранение в PCB информации о причинах завершения Процесс 1 Процесс 2 Процесс 12 Процесс 255 Процесс 3 Процесс 14 Процесс 15 Процесс 128 Процесс 4 Процесс 23 Процесс 192 (Parent – 255) ? Запуск процессаВыбор одного из процессов, находящихся в состоянии готовность Изменение состояния выбранного процесса на исполнение Обеспечение наличия в оперативной памяти информации, необходимой для его выполнения Восстановление значений регистров Передача управления по адресу, на который указывает программный счетчик Приостановка процессаАвтоматическое сохранение программного счетчика и части регистров (работа hardware) Передача управления по специальному адресу (работа hardware) Сохранение динамической части регистрового и системного контекстов в PCB Изменение состояния процесса на готовность Обработка прерывания Блокирование процессаОбработка системного вызова Сохранение контекста процесса в PCB Перевод процесса в состояние ожидание Разблокирование процессаУточнение того, какое именно событие произошло Проверка наличия процесса, ожидающего этого события Перевод ожидающего процесса в состояние готовность Обработка произошедшего события Процесс 1 Процесс 2 Ожидание Исполнение Прерывание Выполнение кода пользователя Выполнение кода ОС Работа hardware Сохранение контекста Обработка прерывания Готовность Исполнение Готовность Планирование Работа hardware Выполнение кода ОС Выполнение кода пользователя Восстановление контекста Пример цепочки операций Уровни планирования процессовДолгосрочное планирование – планирование заданий. Среднесрочное планирование – swapping. Краткосрочное планирование – планирование использования процессора. Цели планированияСправедливость Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение времени ожидания (waiting time) Сокращение времени отклика (response time) Желаемые свойства алгоритмов планированияПредсказуемость Минимизация накладных расходов. Равномерность загрузки вычислительной системы. Масштабируемость. Параметры планированияСтатические параметры вычислительной системы – например, предельные значения ее ресурсов. Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное время, какие требуются ресурсы и т.д. Динамические параметры вычислительной системы – например, количество свободных ресурсов в данный момент. Динамические параметры процесса – текущий приоритет, размер занимаемой оперативной памяти, использованное процессорное время и т.д. статические динамические CPU burst и I/O burstВажные динамические параметры процесса a=1 b=2 read c Ожидание окончания ввода a=a+c∗b print a Ожидание окончания вывода CPU burst CPU burst I/O burst I/O burst Вытесняющее и невытесняющее планированиеПеревод процесса из состояния исполнение в состояние закончил исполнение Перевод процесса из состояния исполнение в состояние ожидание Принятие только вынужденных решений – невытесняющее планирование Перевод процесса из состояния исполнение в состояние готовность Перевод процесса из состояния ожидание в состояние готовность Принятие вынужденных и невынужденных решений –вытесняющее планирование Вынужденное принятие решения Невынужденное принятие решения Алгоритмы планирования
FCFS (First Come – First Served) t 18 17 13 0 P0 P1 P2 исполнение готовность готовность исполнение исполнение
исполнение готовность готовность 1 исполнение 5 исполнение 18 Алгоритмы планированияRR (Round Robin) Процесс 1 Процесс 2 Процесс 3 Процесс 4 готовность готовность готовность исполнение Процессор Процесс 3 Процесс 3 Процесс 4 исполнение готовность готовность готовность Процесс 1 Процесс 2 готовность Процесс 4 готовность Процесс 2 исполнение готовность Алгоритмы планированияRR (Round Robin) Процесс 1 Процесс 3 готовность готовность готовность исполнение Процессор Процесс 3 исполнение готовность готовность готовность Процесс 4 Процесс 3 исполнение готовность Процесс 4 готовность Процесс 3 Процесс 1 Процесс 2 Процесс 1 Процесс 2 Алгоритмы планированияОстаток времени CPU burst <= кванта времени:
на исполнение выбираем новый процесс из начала очереди готовых; Остаток времени CPU burst >= кванта времени: По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов; на исполнение выбираем новый процесс из начала очереди готовых. RR (Round Robin) Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 4 И И И И Г Г Г Г Г Г Г Г P0 P1 P2 Очередь готовых P0 исполнение P1 P2 P0 P1 P2 P0 И И И И Г Г Г Г Г Г Г Г P2 P0 И Г P0 И И И И И И И И И Алгоритмы планирования
RR (Round Robin) Величина кванта времени – 1 И Г Г P0 P1 P2 Очередь готовых P0 исполнение P1 P2 P0 P2 P0 P0 P1 И Г Г P1 P2 P1 И Г Г P0 P1 И Г P1 И Г И Г И Г И Г И Г И И И И И И И И И Алгоритмы планированияSJF (Shortest Job First)
невытесняющий
И Г Г Г И И И Г Г Г Г Г Г И И И И И Г Г Г Г Г И И И И И И И P0 P1 P2 готовность P3 исполнение P3 P1 P0 P2 Алгоритмы планирования
SJF (Shortest Job First) вытесняющий И Г P0 P1 P2 готовность P3 исполнение P3 P1 P0 P2
Г И И И Г Г Г Г И И Г Г И Г Г И И И И И Г Г Г Г Г И И И И И И Алгоритмы планированияτ(n) – величина n-го CPU burst T(n+1) – предсказание для n+1-го CPU burst α – параметр от 0 до 1 T(n+1)= α τ(n) + (1 – α)T(n), T(0) – произвольно Если α = 0, то T(n+1) = T(n) =…= T(0), нет учета последнего поведения Если α = 1, то T(n+1) = τ(n), нет учета предыстории SJF (Shortest Job First) приближение Алгоритмы планированияВ системе разделения времени N пользователей: Ti – время нахождения i-го пользователя в системе τi – суммарное процессорное время процессов i-го пользователя τi ‹‹ Ti /N τi ›› Ti /N (τi N) / Ti – коэффициент справедливости. На исполнение выбираются готовые процессы пользователя с наименьшим коэффициентом справедливости Гарантированное планирование – пользователь обделен – пользователю благоволят Алгоритмы планированияПриоритетное планирование Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением - приоритетом Параметры для назначения приоритета бывают: -внешние -внутренние Политика изменения приоритета: -статический приоритет -динамический приоритет Алгоритмы планирования
Приоритетное планирование невытесняющий И Г P0 P1 P2 готовность P3 исполнение P3 P1 P0 P2 Г И И И Г Г И И Г Г И Г И И И И И Г Г Г Г Г И И И И И И Г Г Г Г Алгоритмы планированияP3 P2 P1 P0 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 время Приоритетное планирование вытесняющий И Г P0 P1 P2 готовность P3 исполнение P3 P1 P0 P2 Г И И И Г Г И И Г Г И Г И И И И И Г Г Г Г Г И И И И И И
Г Г Г Г Г Г Г Г Алгоритмы планированияМногоуровневые очереди (Multilevel Queue) Системные процессы приоритет 0 Процессы ректората приоритет 1 Процессы преподавателей приоритет 2 Фоновые процессы приоритет 3 Процессы студентов приоритет 4 FCFS RR RR RR RR Алгоритмы планированияМногоуровневые очереди с обратной связью (Multilevel Feedback Queue) Очередь 0 – Приоритет 0 Очередь 1 – Приоритет 1 Очередь 2 – Приоритет 2 Очередь 3 – Приоритет 3 RR с квантом времени 8 RR с квантом времени 16 RR с квантом времени 32 FCFS Клавиатурный ввод Дисковый I/O Алгоритмы планированияМногоуровневые очереди с обратной связью (Multilevel Feedback Queue) Для полного описания необходимо задать - количество очередей в состоянии готовность - алгоритм планирования между очередями - алгоритмы планирования внутри очередей - куда помещается родившийся процесс - правила перевода процессов из одной очереди в другую Основные причины для объединения усилий процессовПовышение скорости решения задач Совместное использование данных Модульная конструкция какой-либо системы Для удобства работы пользователя Кооперативные или взаимодействующие процессы - это процессы, которые влияют на поведение друг друга путем обмена информацией Категории средств обмена информациейСигнальные Канальные Разделяемая память Нужна или не нужна инициализация? Способы адресации
непрямая или косвенная адресация Как устанавливается связь Сколько процессов может быть ассоциировано с конкретным средством связи? Сколько идентичных средств связи может быть задействовано между двумя процессами? Направленность связи
Информационная валентность процессов и средств связи Буфера нет (нулевая емкость) процесс-передатчик всегда обязан ждать приема Буфер конечной емкости процесс-передатчик обязан ждать освобождения места в буфере, если буфер заполнен Буфер неограниченной емкости (нереализуемо!) процесс-передатчик никогда не ждет Особенности канальных средств связи Буферизация Потоковая модель
Модель сообщений на передаваемые данные накладывается определенная структура Особенности канальных средств связи Модели передачи данных Особенности канальных средств связи Потоковая модель - pipe P0 P1 P2 15 байт 10 байт 5 байт 5 байт 25 байт начало конец Потоковая модель - FIFO Особенности канальных средств связи Модель сообщений m1 m2 m3 P0 P1 P2 m1 m1 m2 m2 m3 m3 m3 m2 m3 Нет потери информации Нет повреждения информации Нет нарушения порядка поступления информации Не появляется лишняя информация Надежность средств связи Средство связи считается надежным, если: Нужны ли специальные действия для прекращения использования средства связи? Как влияет прекращение использования средства связи одним процессом на поведение других участников взаимодействия? Как завершается связь A=A+B C=A+C Ожидание ввода A Ожидание ввода B Ожидание ввода C Вывести массив C Ожидание вывода C Ввести массив C Ввести массив B Ввести массив A Ввести массив A Ввести массив C A=A+B C=A+C Ожидание ввода A Ввести массив B Ожидание ввода B Ожидание ввода C Процесс 1 Процесс 2 Ожидание ввода A и B Создание процесса 2 Создание общей памяти Создание общей памяти Переключение контекста Переключение контекста Переключение контекста Переключение контекста Вывести массив C Ожидание вывода C Системный контекст Регистровый контекст Код Данные вне стека Процесс Стек Системный контекст нити Системный контекст Код Данные вне стека Стек Нить исполнения Нить исполнения Системный контекст нити Регистровый контекст Стек parent child Процесс Готовность Готовность Исполнение Готовность Ожидание Закончила исполнение Готовность Исполнение Ожидание Ожидание Ожидание Ожидание Ожидание Закончила исполнение Закончила исполнение Закончила исполнение Закончила исполнение Закончила исполнение Закончил исполнение Ввести массив A Ввести массив C A=A+B C=A+C Ожидание ввода A Ввести массив B Ожидание ввода B Ожидание ввода C Нить 1 Нить 2 Ожидание ввода A и B Создание нити 2 Переключение контекста Переключение контекста Переключение контекста Переключение контекста Вывести массив C Ожидание вывода C Алгоритмы синхронизацииАктивности и атомарные операцииОтрезать ломтик хлеба Отрезать ломтик колбасы Намазать хлеб маслом Положить колбасу на хлеб Активность - последовательное выполнение ряда действий, направленных на достижение определенной цели Активность : приготовление бутерброда Атомарные или неделимые операции InterleavingАктивность P: a b c Активность Q: d e f Последовательное выполнение PQ: a b c d e f Псевдопараллельное выполнение (режим разделения времени) : ? a b c d e f a b d c e f a b d e c f a b d e f c . . . d e f a b c Детерминированные и недетерминированные наборы активностейНедетерминированный набор – при одинаковых начальных данных возможны разные результаты Детерминированный набор – при одинаковых начальных данных всегда один результат P: x=2 y=x-1 Q: x=3 y=x+1 (x, y): (2, 1) (3, 4) (2, 3) (2, 1) Условия Бернстайна (Bernstain)P: 1) x=u+v 2) y=x*w Входные переменные R1 = {u, v} R2 = {x, w} Выходные переменные W1 = {x} W2 = {y} R(P)={u, v, x, w} W(P)={x, y} Если: W(P) ∩ W(Q) = {ø} 2) W(P) ∩ R(Q) = {ø} 3) R(P) ∩ W(Q) = {ø} то набор активностей {P, Q} является детерминированным Состояние гонки (race condition) и взаимоисключение (mutual exclusion)P: x=2 y=x-1 Q: x=3 z=x+1 Набор недетерминирован – состязание процессов за использование переменной x В недетерминированных наборах всегда встречается race condition (состояние гонки, состояние состязания) Избежать недетерминированного поведения при неважности очередности доступа можно с помощью взаимоисключения (mutual exclusion) Критическая секция
Приходит в комнату Приходит в комнату Приходит в комнату Уходит за пивом Уходит за пивом Уходит за пивом Покупает 6 бут. пива Покупает 6 бут. пива Покупает 6 бут. пива Приносит пиво Приносит пиво Приносит пиво Достает 6 бут. пива Приходит в комнату Приходит в комнату Структура процесса, участвующего во взимодействииwhile (some condition) { entry section critical section exit section remainder section } Требования, предъявляемые к алгоритмам Программный алгоритм должен быть программным Нет предположений об относительных скоростях выполнения и числе процессоров Выполняется условие взаимоисключения (mutual exclusion) для критических участков Выполняется условие прогресса (progress) Выполняется условие ограниченного ожидания (bound waiting) Запрет прерываний while (some condition) { запретить все прерывания critical section разрешить все прерывания remainder section } Обычно используется внутри ОС Переменная-замок while (some condition) { while (lock); critical section lock = 0; remainder section } Нарушается условие взаимоисключения Shared int lock = 0; lock = 1; while (some condition) { while (lock); critical section lock = 0; remainder section } lock = 1; | Строгое чередование while (some condition) { while (turn != i); critical section turn = 1-i; remainder section } Нарушается условие прогресса Shared int turn = 0; while (some condition) { while (turn != 1); critical section turn = 0; remainder section } while (turn != 0); turn = 1; Pi P1 P0 Shared int turn = 1; Условие взаимоисключения выполняется Флаги готовности while (some condition) { while (ready[1-i]); critical section ready[i] = 0; remainder section } 1-я часть условия прогресса выполняется Shared int ready[2] = {0, 0}; while (ready [1]); ready[0] = 0; Pi P1 P0 Условие взаимоисключения выполняется ready[i] = 1; 2-я часть условия прогресса нарушается while (some condition) { critical section remainder section } while (ready [0]); ready[1] = 0; ready[1] = 1; ready[0] = 1; Shared int ready[2] = {1, 0}; Shared int ready[2] = {1, 1}; |