Лекция 2: Процессы в среде
операционных систем
Что такое процесс?
Процесс — это выполняющаяся программа со всем своим окружением.
Программа
Процесс
Статичный код и данные на диске
Динамический объект в памяти
Не выполняется самостоятельно
Активно работает в процессе выполнения
Не занимает ресурсы системы
Использует CPU, память, файлы и другие ресурсы
Компоненты процесса:
Контекст процесса — это совокупность всех значений, необходимых для его выполнения. Окружение процесса называется Контекстом процесса.
Контекст и дескриптор процесса
Контекст процесса
Набор значений, необходимых для выполнения процесса в любой момент времени:
Значение счетчика команд — какую инструкцию выполнять следующей
Значения в регистрах процессора — данные, адреса, состояние
Данные в оперативной памяти
Исполняемый программный код
Контекст процесса полностью определяет состояние системы в момент времени его выполнения.
Дескриптор процесса
Структура данных в ядре ОС, которая хранит всю информацию о процессе:
Идентификатор процесса (PID)
Уникальный номер процесса в системе
Состояние процесса
Выполняется, готов, ожидает
Степень привилегированности
Уровень доступа к ресурсам системы
Адрес кодового сегмента
Расположение кода в памяти
Указатели на выделенные ресурсы
Файлы, память, устройства и другие ресурсы
Состояния процесса
Исполнение
Процесс выполняется центральным процессором
Готовность
Процесс готов к выполнению и ждет, когда планировщик выделит ему процессор
Блокировка/Ожидание
Процесс приостановлен и ждет наступления внешнего события (например, завершения операции ввода-вывода)
Планировщик
Прерывание
Событие
Важно: Процесс может перейти в состояние "Исполнение" только из состояния "Готовность".
Управление процессами. Планировщик.
Планировщик (Scheduler) — подсистема ОС, которая управляет процессами и распределяет процессорное время между ними.
Очередь готовности
Планировщик
CPU
Задачи планировщика
Решать, какой процесс из состояния "Готовность" будет выполняться следующим
Определять, сколько процессорного времени выделить каждому процессу
Управлять очередями процессов в состояниях "Готовность" и "Ожидание"
Цели планирования
Максимальная загрузка CPU
Высокая пропускная способность (больше задач в единицу времени)
Минимальное время обработки для каждого процесса
Минимальное время отклика для интерактивных приложений
Уровни планирования
В операционных системах выделяют три уровня планирования процессов:
Долгосрочное планирование
Краткосрочное планирование
Среднесрочное планирование
Параметры и временные характеристики процесса
Параметры процесса
Статические параметры
Динамические параметры
Временные характеристики
CPU Burst
|
I/O Burst
CPU Burst: период активного использования процессором для вычислений
I/O Burst: период ожидания завершения операции ввода-вывода
Характер процесса (вычислительный или ориентированный на ввод-вывод) определяется соотношением этих фаз
Стратегии планирования: Классификация
Вытесняющие стратегии
ОС может приостановить выполнение текущего процесса и передать CPU другому.
Невытесняющие стратегии
Процесс выполняется, пока сам не завершится или не перейдет в состояние ожидания.
Области применения:
Вытесняющие: Интерактивные системы, системы реального времени, многозадачные ОС
Невытесняющие: Системы пакетной обработки, простые встроенные системы, задачи с известным временем выполнения
Базовые алгоритмы планирования (1)
FIFO / FCFS
Процессы выполняются в том порядке, в котором они поступили в очередь готовности.
Характеристики:
Прост в реализации
Тип: Невытесняющий
Плюсы и минусы:
Простая логика работы
"С convoy-эффект" — если первым в очереди стоит долгий процесс, короткие процессы вынуждены долго ждать
Round Robin
Каждому процессу выделяется фиксированный квант времени (Time Quantum). Если процесс не завершился за квант, он прерывается и помещается в конец очереди.
Характеристики:
Обеспечивает справедливость
Тип: Вытесняющий
Плюсы и минусы:
Хорошее время отклика для интерактивных приложений
Длительность кванта времени влияет на производительность системы
Базовые алгоритмы планирования (2)
SJF (Shortest Job First)
Описание: Выбирается процесс с наименьшим CPU Burst.
Временная линия выполнения:
P1
P2
P3
P4
Характеристики:
Тип: Может быть как вытесняющим, так и невытесняющим
SRTF (Shortest Remaining Time First)
Описание: Вытесняющая версия SJF. При появлении нового процесса с меньшим оставшимся временем выполнения, текущий процесс вытесняется.
Временная линия выполнения:
P1
P3
P1
P2
P4
Характеристики:
Тип: Обычно вытесняющий
Сравнение:
SRTF всегда обеспечивает лучшее среднее время ожидания, чем SJF, но требует более сложной реализации и может иметь большее число вытеснений процессов.
Базовые алгоритмы планирования (3)
HPF (Наивысший приоритет первый)
Каждому процессу назначается приоритет. Процесс с наивысшим приоритетом выполняется первым.
Обычно вытесняющий алгоритм.
Проблема:
Голодание — процессы с низким приоритетом могут никогда не получить CPU.
Решение:
Динамическое старение — постепенное увеличение приоритета процессов, которые долго ждут.
Гарантированное планирование
Система гарантирует, что каждому из N пользователей достанется ~1/N процессорного времени.
Обеспечивает справедливое распределение ресурсов между пользователями.
Коэффициент справедливости:
K = (ti * N) / Ti
Где ti — полученное время, Ti — время в системе.
Принцип работы:
Процессы с малым K (долго ждут) получают приоритет.
Высокий приоритет
Средний приоритет
Время ожидания
Приоритет
Многоуровневые очереди
Multilevel Queue
Очередь 1 (высокий приоритет)
P1
P2
Очередь 2 (средний приоритет)
P3
P4
P5
Очередь 3 (низкий приоритет)
P6
P7
Процессы разделяются на несколько групп по типу или приоритету.
Multilevel Feedback Queue
Очередь 1 (высокий приоритет)
P1
P2
Очередь 2 (средний приоритет)
P3
P4
Очередь 3 (низкий приоритет)
P5
Процесс не закреплен за одной очередью и может мигрировать между ними в зависимости от поведения.
Сравнение
Multilevel Queue: Простая и предсказуемая работа, но menos гибкость.
Multilevel Feedback Queue: Более сложный, но обеспечивает лучшую адаптивность к различным типам процессов.
Итоги
Концепция процесса
Процесс
Единица работы в ОС, обладающая контекстом
Контекст процесса
Значения счетчика команд, регистров, памяти
Дескриптор процесса
Структура в ядре, хранящая info о процессе
Состояния и управление
Состояния процесса
Исполнение, готовность, блокировка
Планировщик
Подсистема ОС, управляющая процессами
Уровни планирования
Долгосрочное, краткосрочное, среднесрочное
Стратегии планирования
Типы стратегий
Невытесняющие и вытесняющие
Временные характеристики
CPU Burst, I/O Burst, соотношение
Параметры оценки
Загрузка CPU, пропускная способность
Алгоритмы планирования
Базовые алгоритмы
FIFO, RR, SJF, SRTF, приоритетный
Многоуровневые очереди
Multilevel Queue, Multilevel Feedback
Цели алгоритмов
Справедливость, скорость отклика