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

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

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

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

Σ= {ω₁, ω₂, … ω _n } есть множество объектов в системе, а N = { P ₁, P ₂, … P_n } есть множество процессов в системе. Для определенности считается, что множества конечны. Каждый объект определен как

ω _i ={ U, S }, i =1,2,..., n, где U – имя объекта, S – состояние объекта.

Состояния образуют множества, называемые фрагментами состояний. Каждый фрагмент имеет собственное имя. Доступ к фрагменту осуществляется по имени. Фрагменты состояний некоего объекта представляются ориентированным графом. Доступ к каждому ресурсу осуществляется по имени. Отображение F: N →Σ есть однозначное соответствие, т.е. имя фрагмента можно определить как отображение во множестве фрагментов состояний. В соответствии с этим можно определить операцию в ОС как изменение состояний:

U:= S → n (установить значение S фрагмента n). Если процесс P ₁ отображает состояние S в подмножество Σ, содержащее состояние T, S → T (процесс P ₁ переводит состояние S в состояние T), то смена состояний из S в T есть операция процесса P_i. Любая последовательность операций может быть объявлена новой операцией. Процесс характеризуется информацией, показывающей принадлежность его к определенной ступени иерархии, и его возможностями в ОС, выраженными в дескрипторе процесса, включающего в себя

- ступень иерархии, на которой находится процесс;

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

- область доступности данного процесса (ресурсы, предоставленные процессу, и вид доступа к этим ресурсам);

- область сохранения состояния самого процесса.

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

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

Можно представить структуру иерархической ОС, построенной в виде совокупности вложенных уровней, где П₁ (L_i), …, П _k (L_i ) – процессы, реализующие системные функции на i -м уровне вычислений (i =1, 2, 3). На уровне (L ₄ ) выполняются процессы П₁ (L ₄ ), …., П _k (L ₄ ), реализующие вычислительные функции прикладной задачи.

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

На аппаратном уровне происходит выполнение машинных команд.

На уровне L ₁ (см. рис. 5.1) осуществляются функции управления прохождением процессов, выполняемых в привилегированном режиме работы ЦП процессами П₁ (L ₁ ), …, П _k (L ₁ ).

Рис. 5.1. Структура планировщика в иерархической системе

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

На уровне ядра L ₂ процессы П₁ (L ₂ ), …, П_k (L ₂ ) выполняют функции управления ресурсами системы. На этом уровне вычислений осуществляется предоставление задачам (системным и прикладным) ресурсов системы (оперативной и внешней памяти, файлов последовательного доступа, внешних объектов и т.д.), отбор ресурсов, проверка системы на возникновение тупиковой ситуации, которая может возникнуть при распределении ресурсов.

На уровне L ₃ выполняются системные процессы мониторов П₁ (L ₃ ), …, П _k (L ₃ ), реализующие режимы работ в соответствии с функциональным назначением мониторов.

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

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

Механизм планирования

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

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

Общий вид дерева выбора процесса в уровневой ОС представлен на рис. 5.1. Дерево планирования рассматривается в виде цепочки планировщиков PP (L_i), где i =1,2,3. Локальный планировщик i -го уровня PP (L_i ) выбирает один из процессов своего уровня или активный процесс следующего уровня i +1. Запуск планировщика PP (L_i) происходит на уровне i –1. Планировщик PP (L_i) в зависимости от складывающейся ситуации может либо запустить процесс своего же уровня (или уровня i +1), либо передать управление процессу PP (L_{i –1} ).

Процессы внутри уровня, из которых выбираются активные процессы на представление им: П₁ (L_i), …П _k (L_i), выполняют системные функции в зависимости от функционального назначения уровня.

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

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

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

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

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

На уровне ядра планировщик PP (L ₂ ) проверяет процессы следующего внешнего уровня для предоставления им ЦП. Процессы от задач различных мониторов могут претендовать на решение. Активным процессам (имеющим ресурсы) назначается приоритет и они ставятся в очередь. В качестве основного критерия берется крайний срок решения задачи, т.е. момент времени, к которому задача должна быть решена в системе. Этот критерий учитывает ряд факторов, присущих задачам в системе: момент поступления задачи j в систему (t_nj), заказываемое (t_закj) и фактическое время решения (t_решj) задачи j в ЦП на момент перепланирования задач, время нахождения задачи j в системе (t_нj), заказываемое количество ресурсов R_i , статус задач, определяемый постоянной времени класса K_j. На основании этих факторов вычисляется крайний срок решения для задачи. Первыми ставятся в очередь задачи, имеющие наименьший крайний срок решения задачи.

На уровне мониторов планирующие процессы PP (L ₃ ) выбирают из подчиненных задач задачи на предоставление им ЦП. В каждом из мониторов свой планировщик, который планирует решение подчиненных ему задач. При назначении приоритетов планировщики учитывают статус монитора. Первыми в очереди оказываются задачи, которые раньше других поступили в систему. В мониторе коллективного пользования планирующий процесс вычисляет приоритет на основании критерия МИНРЕС (минимально заказываемое количество ресурсов системы). Учитывается количество заказываемых листов памяти (оперативной и внешней), возможное время решения задачи ЦП, предполагаемое количество листов выдачи на выводные устройства, возможность работы с файловой системой. Первыми в очереди оказываются задачи, которые меньше других заказывают ресурсов системы. На уровне вычисления прикладной задачи планирующего процесса нет. Требования процессов на предоставление им ЦП учитываются планировщиком, находящимся на уровне монитора.

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

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