Описание рабочих структур

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

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

Дескриптор - это указатель на процесс; он содержит:

- уникальный идентификатор процесса,

- информацию о состоянии процесса,

- данные о степени привилегированности процесса (приоритет),

- место нахождения кодового сегмента,

- ссылка на контекст процесса,

- другую оперативную информацию, необходимую для принятия решения о возобновлении прерванного процесса.

Контекст - подробное описание процесса, которое отражает состояние операционной среды в момент прерывания; он содержит состояние операционной среды, отображаемое:

- состоянием регистров и программного счетчика,

- режимом работы процессора, указателями на открытые файлы,

- информацией о незавершенных операциях ввода-вывода,

- кодами ошибок выполняемых данным процессом системных вызовов и т.д.

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

- создание информационной структуры, описывающей процесс (дескриптор и контекст процесса).

- включение дескриптора процесса в очередь готовых процессов;

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

Формирование системой информационной структуры, соответствующей процессу, является очень важным этапом в жизненном цикле процесса. Наиболее существенным моментом здесь является уникальное именование процесса в системе, поскольку именно по этому уникальному системному имени (идентификатору) процесс будет распознаваться в любой ситуации. Наиболее простой и надежный способ формирования уникального идентификатора – пересчет процессов в момент инициализации (порождения) очередного процесса. Так в операционных системах семейства UNIX каждый порождаемый процесс получает свой собственный уникальный идентификационный номер PID (Process IDentificator). При создании нового процесса операционная система пытается присвоить ему свободный номер больший, чем у процесса, созданного перед ним. Если таких свободных номеров не оказывается (например, мы достигли максимально возможного номера для процесса), то операционная система выбирает минимальный из всех свободных номеров.

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

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

Подсистема планирования – планировщик задач

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

Диспетчеризация процессов сводится к следующему:

- сохранение контекста текущего процесса;

- загрузка контекста нового процесса, выбранного в результате планирования;

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

Функции планировщика:

- Постановка процессов в очередь на выполнение и управление этой очередью

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

- Распознавание системных событий и запуск соответствующих процессов-обработчиков

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

Передача управления от одного процесса другому включает в себя решение следующих задач:

- определение момента времени для смены выполняемого процесса;

- выбор процесса на выполнение из очереди готовых процессов;

- переключение контекстов "старого" и "нового" процессов.

При этом необходимо отметить, что сам планировщик не может отнять управление у одного процесса и передать другому. Если процесс по какой-то причине сам отдает управление, то управление переходит к планировщику, который выбирает из очереди готовых следующий процесс. Для того чтобы отнять управление у процесса принудительно, необходимо организовать некоторое системное событие, прерывающее выполнение процесса. Управление при этом также передается планировщику; планировщик определяет тип события и запускает соответствующий обработчик «переключением контекста». Если системное событие связано с окончанием времени обслуживания прерванного процесса – планировщик сохраняет текущий контекст для прерванного процесса, определяет следующий процесс на исполнение и запускает его опять же переключением контекста.

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

Квант – это временной интервал, в течение которого процессу разрешено занимать процессор, т.е. разрешено находиться в состоянии ВЫПОЛНЕНИЯ. Понятие кванта основывается на периоде таймера, который называется тиком (~ 45мс). Квант равен целому числу тиков из промежутка [1,255].

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

- процесс покинул систему, поскольку завершился или произошла ошибка,

- процесс перешел в состояние ОЖИДАНИЕ,

- исчерпан квант процессорного времени, отведенный данному процессу.

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Кванты, выделяемые разным процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании.

Другая группа алгоритмов использует понятие "приоритет" процесса.

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

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

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

Первые четыре цикла работы планировщика, приведенные на рисунке, были инициированы прерываниями от таймера по истечении квантов времени (эти события обозначены на рисунке как Т).

Следующая передача управления планировщику была осуществлена в результате выполнения процессом системного запроса на ввод-вывод (событие I/O). Планировщик перевел этот процесс в состояние ожидания, а затем переключил процессор на процесс 2. Процесс 2 полностью использовал свой квант, произошло прерывание от таймера, и планировщик активизировал процесс 1.

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