Материал: Сущность и обзор методов и стратегий диспетчеризации процессов

Введение

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

Диспетчирезация различных процессов и их действий - это часть управления процессами, выполняемого операционной системой. При разработке операционной системы, необходимо определить порядок (политику) диспетчеризации процессов. Политика диспетчеризации предназначена для управления взаимодействием процессов друг с другом. Различные операционные системы могут использовать различные варианты диспетчеризации (по сути, алгоритмы управления разделением процессорного времени). Как было сказано ранее, различные процессы имеют различные уровни приоритета (прерывания), которые учитываются при распределении процессорного времени. Операционная система создает и удаляет процессы по мере необходимости, меняет их состояние (готов, заблокирован, выполняется). Она также контролирует взаимные блокировки (deadlock) процессов, пытающихся использовать одни и те же ресурсы.

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

Одним из примеров взаимной блокировки может быть ситуация, когда процесс A использует ресурс 1 и нуждается в ресурсе 2 для выполнения своих задач, но процесс В использует ресурс 2 и нуждается в ресурсе 1, чтобы закончить свою работу. Таким образом, оба процесса находятся в состоянии взаимной блокировки, поскольку у них нет ресурсов, которые им необходимы, чтобы завершить уже начатую работу. Такие ситуации происходят все реже по мере совершенствования технологий программирования. Кроме того, операционные системы теперь имеют специальные функции, обнаруживающие такие ситуации и освобождающие используемый ресурс, либо контролирующие надлежащее распределение ресурсов между процессами. Операционные системы используют различные методы для работы с запросами ресурсов и их освобождением, чтобы решать возможные ситуации с взаимными блокировками. В некоторых системах, если запрашиваемый ресурс недоступен в течение определенного периода времени, операционная система уничтожает процесс, который «держит» этот ресурс. При этом ресурс освобождается и становится доступен для использования другими приложениями, а уничтоженный процесс перезапускается. Другие операционные системы могут требовать от запускающейся программы заранее запрашивать все ресурсы, которые ей понадобятся для работы, прежде чем она фактически начнет выполняться, либо требовать, чтобы программа освобождала все использующиеся ресурсы перед тем, как запрашивать другие ресурсы.

Сущность и обзор методов и стратегий диспетчеризации процессов в ОС

Сущность и обзор методов диспетчеризации процессов в ОС

Одной из основных задач операционных и сложных вычислительных систем и комплексов является рациональное распределение (планирование) ресурсов вычислителей между пользователями и выполняемыми вычислительными процессами (задачами). При построении управляющих программ (планировщиков, диспетчеров) используется целый ряд различных методов диспетчеризации вычислений. Управляющие программы при любом из методов диспетчеризации вычислений решают задачу минимизации времени ожидания и сведения к минимуму возможных потерь информации. При этом учитывается и оценивается время ожидания вычислительных процессов (заявок, задач, сообщений), и то обстоятельство, что обработка информации, особенно в диалоговых, больших коммуникационных и других вычислительных системах производится путем многократного выполнения циклов, состоящих из запроса задачи абонента-пользователя и/или реакции, ответа ЭВМ (узла сети, сервера и т.д.). Анализ существующих методов диспетчеризации вычислений в различных операционных системах показал имеющиеся ограничения применяемых методов. Методы лежащие в основе управляющих программ для решения разнообразных задач диспетчеризации вычислений реализуют, в основном, традиционные вычислительные дисциплины обслуживания "первым пришел - первым обслужен" или "последним пришел - первым обслужен", а также дисциплины обслуживания на основе очередей приоритетов. Первые из вышеуказанных методов основываются на учете только на одного параметра - времени поступления заявки на обслуживание вычислительного процесса (сообщения). Второй метод, учитывая особенности каждого конкретного процесса: размер процесса, приоритет процесса, содержащуюся в нем информацию и т.д., как правило, не учитывает время поступления запроса. В результате могут происходить значительные задержки в обслуживании других процессов и сообщений и как следствие отказы в работе систем управления при предельных нагрузках системы и/или ограниченном времени ожидания). В ряде случаев при наличии значительного количества вычислительных процессов в системе (или поступающих сообщений), при анализе подобных вычислительных систем, и выборе алгоритмов диспетчеризации вычислительных процессов пытаются использовать методы теории массового обслуживания, учитывая так или иначе известное количество входных потоков задач (сообщений) и их вероятностные характеристики. Однако, практическое решение таких задач диспетчеризации вычислений (да и др. подобных задач) является достаточно сложным и имеет неоднозначный ответ. Кроме того при диспетчеризации вычислений следует учитывать, что в подобных приоритетных вычислительных системах и сетях ЭВМ всегда имеется вероятность того, что низкоприоритетные процессы вовсе не получат вычислительных ресурсов. Поэтому дать полную практическую, адекватную реальности оценку работы подобных существующих вычислительных систем методами теории массового обслуживания .можно лишь приближенно, так как эти методы требуют учета столь многочисленных разнообразных вероятностных факторов, которые практически невозможно выразить количественно и тем более объединить в единый оценочный критерий. В этой связи задача разработки эффективных методов и алгоритмов диспетчеризации вычислений, особенно как для разнообразных задач разделения времени, так и реального времени, связанных со сбором, обработкой и передачей информации с многочисленных источников, а также задач коммуникации и маршрутизации сообщений в локальных и глобальных сетях ЭВМ, является чрезвычайно актуальной и важной.

Сущность и обзор стратегий диспетчеризации процессов в ОС

Диспетчеризация процессора - предоставление всем процессам в системе по очереди в определенном порядке квантов процессорного времени. Главной целью диспетчеризации является максимальная загрузка процессора.

Работа любого процесса в системе представляется как последовательность чередований фаз активности процессора и активности ввода-вывода. Частота периодов активности процессора обратно пропорциональна их длительности.

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

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

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

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

Стратегия диспетчеризации First-Come-First-Served (FCFS) - (обслуживание в порядке поступления) - наиболее простая стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления (ввода) в систему, независимо от потребляемых ими ресурсов, в частности, от заявленного процессом времени, требуемого для его выполнения. При рассмотрении этой и других стратегий будем использовать диаграммы Ганта (Gantt charts изображающие имена процессов и временные диапазоны их выполнения, выраженные в некоторых единицах времени.

Рассмотрим следующий пример. Пусть процессы P1, P2 и P3 введены в систему в указанном порядке со следующими периодами активности:

Тогда при использовании стратегии FCFS для их диспетчеризации первым получит процессор первый процесс, несмотря на то, что он - наиболее долгий. Распределение процессора между процессами в данном случае изображено на рис. 11.3.

Таким образом, время ожидания для P1 = 0; P2= 24; P3 = 27.

Среднее время ожидания: (0 + 24 + 27)/3 = 17.

Если порядок процессов иной: P2 , P3 , P1 (последний введенный в систему процесс - самый долгий), то результат их диспетчеризации будет совершенно иным (рис. 11.4).

Время ожидания процессов в данном случае: P1 = 6; P2 = 0; P3 = 3.

Среднее время ожидания: (6 + 0 + 3)/3 = 3

Данный результат много лучше, чем в предыдущем случае.

Эффект, продемонстрированный первым примером, носит название эффекта сопровождения (convoy effect) - увеличение среднего времени ожидания процессов в случаях, если короткий процесс обслуживается после долгого процесса.

Стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе.

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

Возможны две схемы применения данной стратегии:

• 1. Без прерывания процессов - пока процессу предоставляется процессор, он не может быть прерван, пока не истечет его квант времени.
• 2. С прерыванием процессов - если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest-Remaining-Time-First (SRTF).

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

Рассмотрим пример применения стратегии SJF без прерывания процессов. Пусть набор процессов, времен их появления в системе и времен их активности следующие:

Схема их диспетчеризации по стратегии SJF без прерывания процессов приведена на рис. 11.5.

В данном случае среднее время ожидания = (0 + 6 + 3 + 7)/4 = 4.

Теперь применим к тем же процессам стратегию SJF с прерыванием и проанализируем, как изменится среднее время ожидания. Результат применения стратегии изображен на рис. 11.6.

В данном случае принцип прерывания процесса в момент поступления в систему более короткого процесса применяется несколько раз:

в момент 2 прерывается процесс 1 и начинает исполняться более короткий процесс 2;

в момент 4 прерывается процесс 2 и начинает исполняться более короткий процесс 3.

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

В данном случае среднее время ожидания = (9 + 1 + 0 +2)/4 = 3, т.е. оно, как и следовало предполагать, оказалось меньше, чем без применения принципа прерывания процессов.

Стратегия Round Robin (RR, круговая система) - это предоставление всем процессам по очереди одинаковых квантов времени. Название стратегии происходит от названия популярной в США карточной игры.

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

Если всего имеется n процессов в очереди готовых к выполнению, и квант времени равен q, то каждый процесс получает 1/ n процессорного времени порциями самое большее по q единиц за один раз. Ни один процесс не ждет больше, чем (n-1) q единиц времени.

Производительность данной стратегии зависит от коэффициента q:

если q велико, то стратегия фактически эквивалентна стратегии FCFS;

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

Рассмотрим пример применения стратегии RR. Пусть в системе имеются следующие процессы со следующими временами активности:

Схема диспетчеризации процессора по стратегии RR с квантом времени q =20 приведена на рис. 11.8.

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

На рис. 11.9 иллюстрируется зависимость числа контекстных переключений от кванта времени: чем меньше квант, тем больше число переключений контекста.

На рис. 11.10 приведен пример зависимости времени оборота от кванта времени. В данном случае зависимость носит более сложный характер.

Стратегия Shortest-Remaining-Time-First (SRTF, обслуживание процесса с минимальным оставшимся временем выполнения) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь процессу с минимальным оставшимся временем выполнения.