Операционные системы

УПРАВЛЕНИЕ ПРОЦЕССОРАМИ И ЗАДАНИЯМИ В ОДНОПРОЦЕССОРНОМ ВЫЧИСЛИТЕЛЬНОМ КОМПЛЕКСЕ


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

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

Подсистема управления заданиями управляет прохождением заданий в ВС и выполняет следующие функции:

1.Предоставление языковых средств управления работами в вычислительной системе (Job Control Language (JCL) в ОС ЕС ЭВМ, Shell в UNIX).

2.Ввод и интерпретация заданий/команд.

3.Выделение и освобождение необходимых ресурсов.

4.Планирование заданий на выполнение.

5.Сбор и предоставление информации о состоянии заданий.

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

1.Планирование на верхнем уровне или планирование заданий.

На этом уровне осуществляется выбор заданий пользователем для выполнения и их запуск. Выбранные задания становятся готовыми процессами. Эту работу выполняет системный компонент - планировщик заданий.

2.Планирование на нижнем уровне или диспетчирование процессов.

Здесь осуществляется выбор готового процесса для выполнения, то есть предоставление ему ЦП. Выбранный процесс становится активным. Эту работу выполняет системный компонент - диспетчер.



3.Планирование на промежуточном уровне.

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

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

Типичная двухуровневая система планирования представлена на рис.8.1.


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

Целью построения мультипроцессорных вычислительных систем является:

-

повышение производительности вычислительных систем;

-       повышение надежности и коэффициента готовности вычислительной системы.

Существует два вида мультипроцессорных вычислительных систем:

1.     Мультипроцессорные вычислительные системы со слабо связанными процессорами, называемые многомашинными комплексами, которые предусматривают соединение двух или более вычислительных машин при помощи канала связи и/или внешней памяти (рис.9.1).

Рис. 9.1. Системы со слабо связанными процессорами

2.     Мультипроцессорные системы с сильно связанными процессорами, называющиеся многопроцессорными вычислительными комплексами, которые имеют единую ОП, коллективно используемую несколькими ЦП (рис.9.2).

Рис.9.2. Мультипроцессорная система

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

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

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

-         организацию взаимодействия центральных процессоров (синхронизация);

-         управление загрузкой процессоров (диспетчирование).






Рис.8.1.  Двухуровневая процедура планирования

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

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



Рис. 8.2. Трехуровневая система планирования

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

-

cправедливость;

-         максимальная пропускная способность;

-         приемлемое время ответа для максимального числа интерактивных пользователей;

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

-         минимум накладных расходов на выполнение планирования;

-         сбалансированность использования ресурсов;

-         исключение бесконечного откладывания;

-         учет приоритетов;

-         отдавать предпочтение процессам, занимающим ключевые ресурсы;

-         плавная деградация при увеличении нагрузок.

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

-         является ли процесс обменным (активно использующим операции ввода/вывода) или вычислительным (активно использующим процессор);

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



-         уровень реактивности интерактивного процесса;

-         приоритетность процесса;

-         частоту прерываний по отсутствию нужной страницы;

-         частоту прерывания с низкого приоритета на высокий;

-         длительность периода ожиданий ЦП процесса;

-         суммарное использование времени ЦП и оценочное время, необходимое для завершения.

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

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

1)процесс завершился и покинул систему;

2)произошла ошибка;

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

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

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

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


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

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

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

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

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

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



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

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

2.     Планирование по принципу FIFO, где ЦП предоставляется  процессам в порядке готовности, и они выполняются до завершения или блокировки. Это самая простая дисциплина планирования - фактически без переключения ЦП. Формально - справедливый принцип, но фактически не справедлив, так как длинные задания заставляют ждать короткие. Менее важные - заставляют ждать более важные. Характеризуется небольшим колебанием времени выполнения и большей предсказуемостью, нежели другие дисциплины. Используется только в пакетных системах, обычно в комбинации с другими дисциплинами и не гарантирует реактивности системы.

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

4.     Планирование по принципу - "кратчайшее задание - первым" или "по наименьшему оставшемуся времени выполнения". Максимальный приоритет назначается процессу либо заданию с минимальным оценочным временем до завершения. Недостаток: время ожидания на большие задания растет; большие издержки на регистрацию истекшего времени обслуживания.


Достоинство:  сокращение очередей заданий и ожидающих процессов; стремится к минимальному времени ожиданий для заданий.

5.     Планирование по времени нахождения в системе, в которой приоритет есть функция времени обслуживания и времени ожидания.

Приоритет =


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

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

-         определяет характер процессов и разделяет на соответствующие категории;

-         отдает предпочтение коротким процессам;

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



Рис. 8.3. Сеть многоуровневых очередей

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

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

В ОС OS/2, UNIX приоритеты устанавливаются с помощью класса приоритета и уровня приоритета в классе.Есть три класса приоритета и 32 различных уровня приоритета для класса.

Существует три класса приоритета:

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

обыкновенный - для большинства программ пользователя;

запасной или низкий - задачи и процессы из этого класса выполняются, если в очереди нет критических или обыкновенных задач.



Существует несколько способов взаимодействия ЦП:

1.     Вычислительный комплекс и ОС с подчиненными процессорами

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

2.     Вычислительный комплекс и ОС с равноправными процессорами.

3.     Вычислительный комплекс и ОС с симметричной организацией - симметричное мультипроцессирование.

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

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

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

В любой момент времени любой готовый процесс может выполняться на любом готовом процессоре.


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

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

Разные процессоры могут в какой-то момент времени выполнять как разные, так и одинаковые модули общей ОС. Для этого программные модули ОС должны обладать свойством повторной входимости – реентерабельности. ОС полностью децентрализована. Освободившийся процессор сам запускает планировщик задач, который выбирает из общей системной очереди задачу для выполнения. Все ресурсы выделяются для задачи по мере потребности и не закрепляются за процессором. При таком подходе все процессоры работают с одной и той же динамически выравниваемой загрузкой. В решении одной задачи могут участвовать сразу несколько процессоров, если она допускает распараллеливание, например, путем предоставления нескольких нитей (потоков для WINDOWS NT фирмы Microsoft, UNIX - SOLARIS компании Sun, базирующийся на UNIX System V Release 4).

Достоинства этой организации:

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

-         сбалансированная загрузка ЦП;

-         лучшее использование ресурсов.

Недостаток - возрастает число конфликтов по системному обслуживанию, так как ОС имеется только в одном экземпляре.

Фирма COMPAQ, сотрудничая с NOVELL, выпустила OS-NETWARE from COMPAQ.

SCO UNIX оптимизирована под серверы COMPAQ и поддерживает многопроцессорность с помощью утилиты SCO MPX, которая эффективно использует симметричную многопроцессорную архитектуру.



Рассмотрим архитектуру двухпроцессорной вычислительной системы фирмы COMPAQ. В основу решения положены два принципа:

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

-         как следствие, компонента, готовая передать данные, не должна ждать.

Первое - за счет наращивания разрядности шин. Второе - за счет кэширования. Первоначально IBM PC/XT/AT имели один 8/16 - разрядный канал передачи данных, к которому посредством шины подключались все основные компоненты системы: процессор, память, устройство  ввода/вывода  (рис. 9.3)



Рис.9.3 Архитектура однопроцессорной системы

По сути, канал представляет собой расширение шины процессора, и повышение производительности канала за счет применения новых, более быстродействующих процессоров оказалось невозможным из-за сохранения совместимости с существующими устройствами, рассчитанными на работу с 8 МГц шиной ISA. Шина стала «узким местом» и ограничивала скорость доступа ЦП к памяти.


Содержание раздела