Процесс не может сам перейти из одного состояния в другое. Изменением состояния процессов занимается операционная система, совершая операции над ними. Удобно объединить их в три пары:

Создание процесса -- завершение процесса;

Приостановка процесса (перевод из состояния исполнение в состояние готовность) -- запуск процесса (перевод из состояния готовность в состояние исполнение);

Блокирование процесса (перевод из состояния исполнение в состояние ожидание) -- разблокирование процесса (перевод из состояния ожидание в состояние готовность);

Операции создания и завершения процесса являются одноразовыми, так как применяются к процессу не более одного раза (некоторые системные процессы никогда не завершаются при работе вычислительной системы). Все остальные операции, связанные с изменением состояния процессов, будь то запуск или блокировка, как правило, являются многоразовыми.

Мультипрограммирование, или многозадачность (multitasking), -- это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько программ. Эти программы совместно используют не только процессор, но и другие ресурсы компьютера: оперативную внешнюю память, устройства ввода-вывода, данные.

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования - используемый алгоритм для планирования.

Ситуации когда необходимо планирование:

Когда создается процесс

Когда процесс завершает работу

Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.

При прерывании ввода/вывода.

Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны).

Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик может выступать следующая информация:

Сколько времени прошло со времени выгрузки процесса на диск или его загрузки в оперативную память.

Сколько оперативной памяти занимает процесс.

Сколько процессорного времени было уже предоставлено процессу.

Алгоритм планирования без переключений (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу..

Алгоритм планирования с переключениями (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Необходимость алгоритма планирования зависит от задач, для которых будет использоваться операционная система.

Различают основные три системы:

Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ).

Интерактивные системы - могут использовать только приоритетный алгоритм, нельзя допустить чтобы один процесс занял надолго процессор (например: сервер общего доступа или персональный компьютер).

Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Задачи алгоритмов планирования:

Для всех систем Справедливость - каждому процессу справедливую долю процессорного времени. Контроль за выполнением принятой политики. Баланс - поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)

Системы пакетной обработки Пропускная способность - количество задач в час. Оборотное время - минимизация времени на ожидание обслуживания и обработку задач. Использование процесса - чтобы процессор всегда был занят.

Интерактивные системы Время отклика - быстрая реакция на запросы. Соразмерность - выполнение ожиданий пользователя (например: пользователь не готов к долгой загрузке системы)

Системы реального времени Окончание работы к сроку - предотвращение потери данных. Предсказуемость - предотвращение деградации качества в мультимедийных системах (например: потерь качества звука должно быть меньше чем видео).

2. Системы пакетной обработки

Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени.

Суть: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается "выгодное" задание. Следовательно, в вычислительных системах, работающих под управлением пакетных ОС, невозможно гарантировать выполнение того или иного задания в течение определенного периода времени.

Алгоритмы:

1. "Первый пришел - первым обслужен" (FIFO - First In Fist Out)

Процессы ставятся в очередь по мере поступления.

Преимущества

Простата

Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)

Недостатки

Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.

2. "Кратчайшая задача - первая" (рис.1)

Преимущества

Уменьшение оборотного времени

Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)

Недостатки

Длинный процесс, занявший процессор, не пустит более новые краткие процессы, которые пришли позже.

3. Наименьшее оставшееся время выполнение

Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.

4. Трехуровневое планирование

Планировщик доступа выбирает задачи оптимальным образом (например: процессы ограниченные процессором и вводом/выводом) (рис.2).

Если процессов в памяти слишком много, планировщик памяти выгружает и загружает некоторые процессы на диск. Количество процессов находящихся в памяти, называется степенью многозадачности.

3. Интерактивные системы

Цель: Повышение удобства и эффективности работы пользователя. В системах разделения времени пользователям (или одному пользователю) предоставляется возможность интерактивной работы сразу с несколькими приложениями. Для этого каждое приложение должно регулярно получать возможность "общения" с пользователем. Понятно, что в пакетных системах возможности диалога пользователя с приложением весьма ограничены.

Суть. В системах разделения времени эта проблема решается за счет того, что ОС принудительно периодически приостанавливает приложения, не дожидаясь, когда они добровольно освободят процессор. Всем приложениям попеременно выделяется квант процессорного времени, таким образом пользователи, запустившие программы на выполнение, получают возможность поддерживать с ними диалог.

Если квант выбран достаточно небольшим, то у всех пользователей, одновременно работающих на одной и той же машине, складывается впечатление, что каждый из них единолично использует машину.

Достоинство: простота работы пользователя.

Недостаток: небольшая пропускная способность.

Алгоритмы:

1. Циклическое планирование

Самый простой алгоритм планирования и часто используемый (рис.3).

Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.

Преимущества

Простата

Справедливость (как в очереди покупателей, каждому только по килограмму)

Недостатки

Если частые переключения (малый квант - 4мс, а время переключения равно 1мс), то происходит уменьшение производительности.

Если редкие переключения (малый квант - 100мс), то происходит увеличение времени ответа на запрос.

2. Приоритетное планирование

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом (рис.4).

Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться так:

П=1/Т,

где Т- часть использованного кванта

Если использовано 1/50 кванта, то приоритет 50.

Если использован весь квант, то приоритет 1.

Т.е. процессы ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

Часто процессы объединяют по приоритетам в группы, и используют приоритетное планирование среди групп, но внутри группы используют циклическое планирование.

3. Методы разделения процессов на группы

Группы с разным квантом времени (рис.5)

Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т.д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.

Процесс либо заканчивает работу, либо переходит в другую группу

Этот метод напоминает алгоритм - "Кратчайшая задача - первая".

Группы с разным назначением процессов (рис.6)

Процесс отвечающий на запрос, переходит в группу с наивысшим приоритетом.

Такой механизм позволяет повысить приоритет работы с клиентом.

4. Гарантированное планирование

В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.

5. Лотерейное планирование

Процессам раздаются "лотерейные билеты" на доступ к ресурсам. Планировщик может выбрать любой билет, случайным образом. Чем больше билетов у процесса, тем больше у него шансов захватить ресурс.

6. Справедливое планирование

Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.

4. Системы реального времени

Еще одна разновидность мультипрограммирования используется в системах реального времени, предназначенных для управления от компьютера различными техническими объектами (например, станком, спутником, научной экспериментальной установкой и т. д.) или технологическими процессами (например, гальванической линией, доменным процессом и т. п.). Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная управляющая объектом программа. В противном случае может произойти авария: спутник выйдет из зоны видимости, экспериментальные данные, поступающие с датчиков, будут потеряны, толщина гальванического покрытия не будет соответствовать норме.

Системы реального времени делятся на:

жесткие (жесткие сроки для каждой задачи) - управление движением

гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио

Внешние события на которые система должна реагировать, делятся:

периодические - потоковое видео и аудио

непериодические (непредсказуемые) - сигнал о пожаре

Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

m - число периодических событий

i - номер события

P(i) - период поступления события

T(i) - время, которое уходит на обработку события

Т.е. перегруженная система реального времени является не планируемой.

Алгоритмы:

1. Планирование однородных процессов

В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).

Т.к. все процессы важны можно использовать циклическое планирование.

Но так как количество пользователей и размеры кадров могут меняться, для реальных сстем он не подходит.

2. Общее планирование реального времени

Используется модель, когда каждый процесс борется за процессор со своим заданием и графиком его выполнения.

Планировщик должен знать:

частота, с которой должен работать каждый процесс

объем работ, который ему предстоит выполнить

ближайший срок выполнения очередной порции задания.