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

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процесс	Период активности
P1	24
P2	3
P3	3

Тогда при использовании стратегии 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 без прерывания процессов. Пусть набор процессов, времен их появления в системе и времен их активности следующие:

Процесс	Время появления	Время активности
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

Схема их диспетчеризации по стратегии 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. Пусть в системе имеются следующие процессы со следующими временами активности:

Процесc	Время активности
P1	53
P2	17
P3	68
P4	24

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

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

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

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

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

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

Многозадачность может быть либо кооперативной (cooperative multitasking), либо вытесняющей (preemptive multitasking).

В кооперативных системах за передачу управления другим задачам отвечает исполняющаяся в данный момент программа. Это управление может передаваться явным или косвенным образом. Для явной (explicitly) передачи управления используются специально предназначенные для этой цели программные вызовы операционной системы. Косвенная (implicitly) передача управления происходит при вызове определенных функций операционной системы, которые подразумевают переход к выполнению других задач на время осуществления операций, соответствующих этим функциям (например, при выполнении обмена с дисками). Примеры ОС: Windows 3.x (однако при работе в расширенном режиме для всех DOS-приложений, запущенных в этой системе, применяется вытесняющая многозадачность) и Novell NetWare.

В системах с вытесняющей многозадачностью ОС может самостоятельно передать управление процессором от одной активной задачи к другой, готовой к выполнению задаче. Следовательно, работающие в режиме вытесняющей мультизадачности приложения могут не беспокоиться о том, что они могут “захватить” все время процессора, так как ОС сама распределяет время процессора между всеми существующими в системе задачами. Примеры ОС: OS/2, Unix, Windows 95 и Windows NT.

Планирование выделения времени центрального процессора в таких системах выполняется в соответствии с приоритетами.

2. Планировщики, выполняющие диспетчеризацию процессов и предсказание длины следующего периода активности

2.1 Планировщики, выполняющие диспетчеризацию процессов

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

Долговременный планировщик (планировщик заданий) определяет, какие процессы должны быть перемещены в очередь готовых процессов.

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

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

Особенности планировщиков и процессов.Каждый планировщик имеет свои особенности поведения, как и каждый процесс.

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

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

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

Сами процессы также могут вести себя по-разному, с точки зрения их диспетчеризации. Процессы могут быть:

ЃE Ориентированными на ввод-вывод (I/O-bound) - процессы, которые тратят больше времени на ввод-вывод, чем на вычисления. Такие процессы обычно расходуют много коротких квантов процессорного времени.

ЃE Ориентированные на использование процессора (CPU-bound) - процессы, которые тратят основное время на вычисления. Такие процессы расходуют небольшое число долговременных квантов процессорного времени.

Переключение контекста

Когда процессор переключается на другой процесс, система должна сохранить состояние старого процесса и загрузить сохраненное состояние для нового процесса. Такое действие системы называется переключением контекста (context switch).

Переключение контекста относится к накладным расходам (overhead), так как система не выполняет никаких полезных действий при переключении с одного процесса на другой.

Время переключения контекста зависит от аппаратной поддержки. Выше мы рассматривали необходимые действия системы в таких случаях - сохранение состояния приостанавливаемого процесса в его PCB и восстановление состояния возобновляемого процесса из его PCB.

Например, в системе "Эльбрус" контекстное переключение выполнялось всего одной аппаратной командой - СМСТЕК (сменить стек, т.е. переключиться с одного облегченного процесса на другой). Однако следует отметить, что такая аппаратная оптимизация была возможна, так как понятие процесса в "Эльбрусе" было фактически сведено к понятию облегченного процесса (lightweight process).

Создание процесса - одна из основных операций над процессами

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

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

Разделение ресурсов. Возможны следующие подходы:

ЃE Процесс-родитель и дочерние процессы разделяют все ресурсы;

ЃE Дочерние процессы разделяют подмножество ресурсов процесса-родителя;

ЃE Процесс-родитель и дочерний процесс не имеют общих ресурсов.

Исполнение. Возможны следующие подходы:

ЃE Процесс-родитель и дочерние процессы исполняются совместно;

ЃE Процесс-родитель ожидает завершения дочерних процессов.

Адресация и использование памяти.Возможны следующие подходы:

ЃE Адресное пространство дочернего процесса копирует адресное пространство процесса-родителя; у дочернего процесса имеется программа, загруженная в него;

ЃE Дочерний процесс исполняется в том же пространстве памяти, что и процесс-родитель (облегченный процесс).

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

При запуске системы создается корневой процесс root.Он, в свою очередь, создает три дочерних процесса: init- инициализация системы; pagedaemon - процесс-демон (процесс, постоянно находящийся в системе до ее перезапуска), управляющей страничной организацией памяти; swapper - процесс, управляющий откачкой и подкачкой. Процесс init после инициализации системы запускает пользовательские процессы. Последние, в свою очередь, могут запускать новые и т.д.

Уничтожение процесса

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

ЃE Дочерний процесс превысил выделенные ему ресурсы;

ЃE Решения задачи, порученной дочернему процессу, больше не требуется;

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

2.2 Предсказание длины следующего периода активности

Попытаемся теперь предложить и применить формулы для предсказания следующего периода активности процесса. Подобные оценки помогли бы разработчикам ОС реализовать оптимальную стратегию диспетчеризации. Используем уже известные фактические длины предыдущих периодов активности и принцип экспоненциального усреднения. Пусть:

фактическая длина n- го периода активности процесса;

предсказанная длина n- го периода активности процесса.

Будем искать значение для предсказания следующего периода активности процесса как следующую линейную комбинацию tn и :

где - число между 0 и1. Коэффициент характеризует, в какой степени при предсказании учитывается недавняя история вычислений.

Пример предсказания следующего периода активности по приведенной формуле приведен на рис. 11.7.

При т.е. недавняя история не учитывается.

При т.е. учитывается только фактическая длина последнего периода активности.

Если обобщить приведенную формулу, получим:

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

Диспетчеризация по приоритетам

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

Данная стратегия, как и предыдущая, имеет варианты с прерыванием и без прерывания.

Более того, стратегию SJF можно рассматривать как диспетчеризацию по приоритетам, в которой приоритетом является очередное время активности.

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

Традиционным способом решение данной проблемы в операционных системах является учет возраста процесса (aging): c течением времени приоритет процесса повышается системой.

диспетчеризация вычислительный дескриптор

2.3 Дескриптор и контекст процесса

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

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

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

Точный состав дескриптора и контекста сильно зависят от конкретной ОС.

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

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

Реентерабельность системных функций

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

Проблема заключается в том, что новый текущий процесс может вызвать ту же самую системную функцию. Возникает вопрос: возможно ли корректное выполнение второго вызова функции, если к этому моменту не закончено выполнение первого вызова той же функции?

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

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

Проблема реентерабельности функций возникает в программировании и по совершенно другому поводу, не связанному с реализацией ОС. Речь идет о рекурсивных функциях, т.е. функциях, которые могут прямо или косвенно вызывать сами себя. Давно известна и основная причина нереентерабельности функций. Она заключается в использовании одних и тех же ячеек памяти для формальных параметров и локальных переменных при разных вызовах функции. Действительно, если при первом вызове функции в ячейку локальной переменной X будет занесено, например, число 10, а при втором -- число 20, то после возобновления выполнения первого вызова значение X будет неверным.

Лекарство от этой формы нереентерабельности также давно известно и встроено во все уважающие себя языки программирования, начиная с C и Pascal. Оно заключается в том, что память для формальных параметров и локальных переменных должна выделяться в стеке программы, при этом каждый новый вложенный вызов получает свой набор ячеек для переменных.

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

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

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

При переходе от невытесняющей Windows 3.x к вытесняющей Windows 95 одна из серьезных проблем состояла в сохранении кода большого количества нереентерабельных системных функций. Проблему «решили» путем введения семафора, блокирующего повторный вызов для большого числа функций. Неприятным следствием этого стало взаимное тормозящее влияние процессов. В Windows NT этой проблемы нет, все функции реализованы реентерабельно.

Дисциплины диспетчеризации и приоритеты процессов

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

Одной из самых очевидных дисциплин является простая круговая диспетчеризация (round robin scheduling). Ее суть в следующем. Все активные процессы считаются равноправными и образуют круговую очередь. Каждый процесс получает от системы квант времени, по истечении которого планировщик выбирает для выполнения следующий процесс из очереди. Таким образом, если все процессы остаются активными, то система обеспечивает их равномерное продвижение, имитирующее параллельное выполнение всех процессов. Если текущий процесс блокируется, он выпадает из круга и попадает в список спящих процессов. Когда система активизирует один из спящих процессов, он включается в круговую очередь.

В некотором смысле противоположной дисциплиной является фоново-оперативная диспетчеризация (foreground/background scheduling) -- одна из самых старых форм организации многозадачной работы. В простейшем случае она включает два процесса: фоновый процесс и оперативный процесс (процесс переднего плана). Фоновый процесс выполняется только тогда, когда спит оперативный процесс. При активизации оперативного процесса происходит немедленное вытеснение фонового, т.е. оперативный процесс имеет более высокий абсолютный приоритет. Обычно при такой дисциплине предполагается, что активизация оперативного процесса не потребует много процессорного времени, так что выполнение фонового процесса будет скоро возобновлено. Одним из примеров эффективного использования фоново-оперативной диспетчеризации является так называемая «фоновая печать», которую позволяет выполнить даже однозадачная MS-DOS. При этом процесс вывода файла на принтер рассматривается как процесс переднего плана, а обычная диалоговая работа с ОС -- как фоновый процесс. Поскольку обслуживание прерываний от принтера занимает лишь доли процента процессорного времени, пользователь не ощущает никакого замедления работы.

Между описанными двумя крайностями лежит большое разнообразие дисциплин приоритетной диспетчеризации. Все они основаны на приписывании каждому процессу при его создании некоторого числа -- приоритета. Более высокий приоритет должен давать процессу определенные преимущества перед низкоприоритетными процессами при работе планировщика.

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

важность, ответственность данного процесса либо привилегированное положение запускающего процесс пользователя;

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

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

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

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

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

Проблемы взаимодействия процессов

Изоляция процессов и их взаимодействие

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

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

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

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

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

Понятие взаимодействия процессов включает в себя несколько видов взаимодействия, основными из которых являются:

синхронизация процессов, т.е., упрощенно говоря, ожидание одним процессом каких-либо событий, связанных с работой других процессов;

обмен данными между процессами.

Набор средств, предназначенных для взаимодействия процессов, часто обозначают аббревиатурой IPC (InterProcess Communication). Состав функций и методов обусловлен многолетним опытом как программистов-практиков, так и теоретиков, рассматривающих проблемы взаимодействия параллельных процессов.

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

Проблема взаимного исключения процессов

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

Проблему часто поясняют на таком, немного условном, примере. Пусть имеется система резервирования авиабилетов, в которой одновременно работают два процесса. Процесс A обеспечивает продажу билетов, процесс B -- возврат билетов. Не углубляясь в детали, будем считать, что оба процесса работают с переменной N -- числом оставшихся билетов, причем соответствующие фрагменты программ на псевдокоде выглядят примерно так:

Процесс A:	Процесс B:
R1 := N; R1 := R1 - 1; N := R1;	R2 := N; R2 := R2 + 1; N := R2;

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

1) R1 := N; R2 := N; R2 := R2 + 1; N := R2; R1 := R1 - 1; N := R1;

2) R2 := N; R2 := R2 + 1; R1 := N; R1 := R1 - 1; N := R1; N := R2;

3) R1 := N; R1 := R1 - 1; N := R1; R2 := N; R2 := R2 + 1; N := R2;

Ну и что? А то, что в случае 1 значение N в результате окажется уменьшенным на 1, в случае 2 -- увеличенным на 1, и только в случае 3 значение N, как и положено, не изменится.

Можно привести менее экзотические примеры.

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

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

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

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

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

Задолго до создания многозадачных систем разработчики средств автоматики столкнулись с неприятным эффектом зависимости результата операции от случайного и непредсказуемого соотношения скоростей распространения разных сигналов в электронных схемах. Этот эффект они назвали «гонками». Мы здесь ведем речь, в сущности, о том же.

Для более четкого описания ситуации было введено понятие критической секции.

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

А как им это запретить?

На первый взгляд кажется, что эта проблема (ее называют проблемой взаимного исключения процессов) решается просто. Например, можно ввести булеву переменную Free, доступную обоим процессам и имеющую смысл «критическая область свободна». Каждый процесс перед входом в свою критическую область должен ожидать, пока эта переменная не станет истинной, как показано ниже:

Процесс A:	Процесс B:
while not Free do ; Free := false; (критическая секция A) Free := true;	while not Free do ; Free := false; (критическая секция B) Free := true;

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

А не нужно ли было что-нибудь сделать с переменной Free еще до запуска процессов A и B?

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

Беда в том, что такое решение ничего не решает. Если реализовать его на практике, то «неприятности» станут реже, но не исчезнут. В первом, бесхитростном варианте программы угрожаемыми участками были критические секции обоих процессов. Теперь же уязвимый участок сузился до одной точки, отмеченной в программе каждого процесса штриховой линией. Это точка между проверкой переменной Free и изменением этой переменной. Если переключение процессов произойдет, когда вытесняемый процесс будет находиться именно в этой точке, то сначала в критическую секцию войдет (с полным правом на это) другой процесс, а потом, когда управление вернется к первому процессу, он без дополнительной проверки тоже войдет в свою критическую секцию.

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

в любой момент времени не более, чем один процесс может находиться в критической секции;

если критическая секция свободна, то процесс может беспрепятственно войти в нее;

все процессы равноправны.

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

Для любознательных приводим решение Питерсона. В нем используются булевы переменные flagA, flagB, изначально равные false, и переменная перечисляемого типа turn: A..B.

Процесс A:	Процесс B:
flagA := true; turn := B; while flagB and turn = B do ; (критическая секция A) flagA := false;	flagB := true; turn := A; while flagA and turn = A do ; (критическая секция B) flagB := false;

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

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

Краткие итоги

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

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

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

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

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

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

При создании процессов процессы-родители создают дочерние процессы, которые затем создают свои дочерние процессы, и т.д. В результате формируется дерево процессов в системе. При создании процесса процесс-родитель и дочерний процесс могут разделять все ресурсы, разделять подмножество ресурсов или не иметь общих ресурсов. Процесс-родитель может исполняться совместно с дочерним процессом или ожидать завершения дочернего процесса. При создании дочернего процесса может создаваться новое адресное пространство, копируемое с процесса-родителя; облегченный дочерний процесс работает в том же адресном пространстве, что и процесс-родитель. В системе UNIX эти действия реализуются системными вызовами forkи exec.

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

Размещено на Allbest.ru

...