АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Управление заданиями

Читайте также:
  1. S: Управление риском или как повысить уровень безопасности
  2. Supply Chain Management (SCM) — управление цепями поставок.
  3. VIII. Управление персоналом
  4. Анонимное управление
  5. Антикризисное управление
  6. Антикризисное управление конфликтами
  7. Антикризисное управление неплатежеспособным хозяйствующим субъектом
  8. Блок: «Управление персоналом»
  9. ВКЛЮЧЕНИЕ ДАУ АРС ПРИ ПЕРЕХОДЕ НА РЕЗЕРВНОЕ УПРАВЛЕНИЕ.
  10. Власть, управление и социальные регуляторы в первобытном обществе
  11. Внешнее управление
  12. Внутрифирменное управление и управление фирмой как субъектом рынка

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

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

Таблица 3. Разновидности системных событий

Наименование типа событий Обозначения Смысловое значение событий
Тип событий Конкретные экземпляры событий
Возникновение задания (job arrival) e воз(t i) e воз(jt i) Возникновение необходимости выполнения задачи t i
Регистрация задания (job release) e рег(t i) e рег(jt i) Выполнение действий по учету задания типа t i в системе планирования
Начальная активизация e акт(t i) e акт(jt i) Первое предоставление ресурса процессора заданию типа t i
Запрос (request) ресурса e зап(t i, g) e зап(jt i, g) Запрос заданием типа t i аппаратного или информационного ресурса g (например, ресурса памяти)
Предоставление (allocation) ресурса e выд(t i, g) e выд (jt i, g) Выделение заданию типа t i затребованного им ресурса g
Освобождение (reject) ресурса e осв(t i, g) e осв(jt i, g) Возврат заданием типа t i выделявшегося ему ресурса g
Завершение задания (job termination) e зав(t i) e зав(jt i) Прекращается существование t i, его ресурсы освобождаются

 

В табл. 3 приведены примеры некоторых типов системных событий. При рассмотрении различных вопросов управления заданиями этот перечень будет расширяться. Диаграмма рис. 7 представляет порядок, в котором могут следовать системные события в рамках интервала существования некоего задания kt i.

 
 

 

 


 

Рис. 7. Пример структуры интервала существования задания

 

Символы D i и J i, являющиеся параметрами задачи t i, представлены на рис. 7 выше оси времени:

· D i – относительный предельных срок выполнения задачи t i,

· J i – максимальное для t i значение задержки регистрации.

Ниже оси времени указаны параметры задания kt i (k j i – фактическая задержка регистрации задания kt i; k d i – абсолютное значение предельного срока выполнения задания kt i). Вертикальными стрелками отмечены системные события представленных в табл.3 типов.

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

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

· заданию предоставлены все требуемые ресурсы,

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

На диаграмме рис. 7 такие переключения CPU на обслуживание задания kt i происходят в моменты времени возникновения событий e акт(kt i), e выд(kt i, gx) и e выд(kt i, gy).

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

 

 
 

 

 


Рис. 8. Диаграмма переходов между системными состояниями задания kt i

 

Если в момент регистрации задания kt i оказывается, что ресурс процессора может быть предоставлен ему немедленно, то КС немедленно приступает к выполнению соответствующих вычислений – в этом случае задание минует состояние “ожидание активизации”. Обратим внимание, что в рамках интервала существования задания переходы типа e воз(t i) (переход задания kt i из небытия в состояние ожидания регистрации), e рег(t i) и e акт(t i) происходят однократно, а переходы e зап(t i, g) e выд(t i, g) могут происходить произвольное число раз.

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

 
 

 


Рис. 9. Три варианта дисциплины обслуживания заданий процессором КС

 

Даже в случае использования многопроцессорных КС число задач обычно существенно число превосходит число используемых процессоров и в ходе работы КС типичны ситуации, в которых количество действующих заданий превышает количество процессоров. В этом случае истинный параллелизм невозможен: по крайней мере один из процессоров должен работать в квазипараллельном режиме, попеременно переключаясь с исполнения одной из задач на исполнение другой. Примеры диаграмм, иллюстрирующих варианты таких переключений, приведены на рис. 9. В однопроцессорной системе в конкретный момент времени t лишь одно из действующих заданий, может находиться в системном состоянии “исполнение вычислений” (это задание называют текущим заданием на момент t). Другие действующие задания находятся либо в одном из состояний, приведенных на рис.8 (кроме состояния “исполнение вычислений”), либо в состоянии “ожидание CPU”.

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

На каждой из трех диаграмм объемы ресурса процессорного времени, требуемого для выполнения заданий it 1, jt 2 и kt 3 задаются величинами:

ic 1 = 23, jc 2 = 14, kc 3 = 18.

Моменты регистрации заданий it 1, kt 2, kt 3 на всех трех диаграммах распределяются одинаково:

t (e рег(jt 2)) – t (e рег(it 1)) = 12, t (e рег(kt 3)) – t (e рег(jt 2)) = 8.

Это означает, что для всех трех диаграмм внешние условия выполнения заданий совпадают it 1, kt 2, kt 3. Приведенные диаграммы различаются лишь в отношении используемых дисциплин планирования. Диаграмма рис. 9 а, представляет порядок системных событий в случае применения метода обслуживания заданий “в порядке поступления” – чем раньше зарегистрировано задание, тем выше его приоритет (FIFO дисциплина планирования). Диаграмма рис. 9 б, соответствует методу с диаметрально противоположными принципами назначения приоритетов: чем позже зарегистрировано задание, тем выше его приоритет (LIFO дисциплина планирования). Порядок системных событий на диаграмме рис. 9 в, соответствует назначению приоритетов заданий в зависимости от требуемых объемов процессорного времени: чем меньше процессорного времени требуется заданию, тем выше его приоритет (SPTF дисциплина планирования).

В табл. 4 приведены различия во времени отклика заданий it 1, jt 2 и kt 3 при использовании различных дисциплин планирования. Анализ данных, приведенных в табл. 4, показывает что если предельное значение относительного срока выполнения каждого из заданий установлено равным 33 единицам времени, то ни один из рассмотренных методов не обеспечивает своевременного выполнения всех заданий.

Таблица 4. Изменения времени отклика заданий при различных дисциплинах планирования

Дисциплина планирования Время отклика задания Своевременность выполнения при D=33
it 1 jt 2 kt 3 it 1 jt 2 kt 3
FIFO – очередь задач       да да нет
LIFO – стек задач       нет да да
SPT – короткие вперед       нет да да

 

Отметим, что если к задачам t 2 и t 3 на рис. 9 предъявляются требования жесткого реального времени, а к задаче t 1 – требования мягкого реального времени, то для системы, возможно, подойдет вариант применения LIFO дисциплины планирования. Если же мягкие требования реального времени относятся к задаче t 3, то подходящей может оказаться FIFO дисциплина.

5.4. Вытеснение/возобновление заданий. На рис. 9 б (и на рис. 9 в) в рамках интервала существования задания it 1 его системное состояние изменяется дважды: в момент регистрации задания jt 2 и в момент завершения jt 2 (на рис.9 в в момент завершения задания kt 3).

На интервале от регистрации it 1 до регистрации jt 2 единственным претендентом на использование процессорного времени является задание it 1, ему и предоставляется процессорное время. В момент регистрации jt 2 таких претендентов становится двое – it 1 и jt 2. Причем в соответствии с используемой дисциплиной планирования LIFO (равно как и в соответствии с дисциплиной SPTF на рис. 9 в) приоритет jt 2, выше чем приоритет it 1, поэтому процессор переключается с обслуживания it 1 на обслуживание jt 2. Это явление называется вытеснением (preemption): владеющее ресурсом процессора задание it 1 вытесняется только что зарегистрированным более приоритетным jt 2, которому и передается ресурс процессора.

 

 
 

 


Рис. 10. Переходы между системными состояниями заданий в случае квазипараллельных вычислений

 

В момент вытеснения задание it 1 переводится в пассивное системное состояние “ожидание CPU” (исполнение вычислений по программе, соответствующей it 1, приостанавливается). В этом состоянии it 1 пребывает до тех пор, пока среди действующих заданий не останется заданий с более высоким приоритетом, чем приоритет it 1. При LIFO дисциплине планирования (как и при дисциплине SPTF, рис. 9 в) оба конкурента (jt 2 и kt 3) задания it 1 на использование процессорного времени являются более приоритетными, чем it 1, поэтому it 1 остается в состоянии “ожидание CPU” до тех пор, пока хотя бы одно из более приоритетных заданий jt 2 или kt 3 остается претендентом на использование процессора.

Отметим различие между переходами заданий в пассивное состояние на диаграммах рис. 8 и рис. 10. На рис. 8 системные события e зап(kt i, gu) и e зап(kt i, gv) переводят задание kt i в пассивное состояние по логике развития самого задания kt i: задание запрашивает ресурс, ресурс занят и пока он не освободится, задание kt i не может использовать процессор. На рис. 10 вытеснение задания it 1 происходит по причинам, внешним по отношению к логике развития самого задания it 1, момент вытеснения никак не привязан к выполнению какой-либо из инструкций программы, реализующей задание it 1.

Задание переходит из состояния “ожидание CPU” в активное состояние в момент, когда оно становится наиболее приоритетным изо всех действующих заданий, готовых использовать ресурс процессора. Перевод задания из состояния “ожидание CPU” в состояние “исполнение вычислений” называется “возобновлением” (resuming). Процессор продолжает исполнение программы, соответствующей заданию, с того места, где это исполнение было прервано в момент вытеснения.

Для случая квазипараллельных вычислений диаграмма изменения системных состояний задания kt i в сравнении с рис. 8 пополняется системным состоянием “ожидание CPU” и дугами, связывающими его с другими системными состояниями задания kt i (рис. 10). Заметим, что диаграмма рис. 10 представляет переходы между состояниями заданий типа t i, а дуги “вытеснение” и “возобновление” помечены типами событий, относящихся к заданиям типа t j. То есть, задание kt i попадает в состояние “ожидание CPU” из состояния “исполнение вычислений” в результате системных событий, относящихся не к заданию kt i, а к заданиям других типов.

5.5. Внешние и внутренние источники заданий. Системные события e воз(kt i), e рег(kt i) и e акт(kt i) составляют подготовительную стадию интервала существования задания kt i. Формирование задания kt i начинается системным событием e воз(kt i), означающим возникновение необходимости в k ый раз выполнить задачу t i. Такая необходимость может быть обусловлена либо ходом развития внешних по отношению к КС процессов (внешними источниками), либо ходом исполнения программ (внутренними источниками). В обоих случаях активизация задания (событие e акт(kt i)) может выполняться либо чисто программными средствами, либо путем использования системы прерываний. Таким образом, существуют четыре варианта возникновения заданий (табл. 5).

Вариант табл. 5 а соответствует ситуации, в которой причиной возникновения нового задания kt i является достижение (по ходу исполнения текущей программы) оператора обращения к ОС с очередным запросом на выполнение задачи t i. Регистрация задания kt i. выполняется операционной системой. Величина задержки регистрации определяется объемом вычислений, выполняемых ОС для формирования исходного состояния контекста задания kt i и для необходимой модификации системных структур (в частности, пополнения списка действующих заданий и перепланирования порядка использования ресурса процессора в связи с появлением kt i). Если kt i оказывается наиболее приоритетным из действующих заданий, то длина временного интервала между системными событиями e рег(kt i) и e акт(kt i) незначительна – она определяется объемом действий, необходимых для переключения процессора с текущей программы на обслуживание kt i; в противном случае длина этого временного интервала определяется составом действующих заданий и применяемой дисциплиной планирования.

 

Таблица 5. Варианты возникновения и активизации заданий

 

Источники заданий Механизмы активизации заданий
Программные Система прерываний
Внутренние а) Задание возникает по программе текущих вычислений путем вызова соответствующей функции операционной системы б) Аппаратно активизируемое задание (обработчик прерываний) возникает по программе текущих вычислений путем выполнения инструкции командного прерывания
Внешние в) Задание возникает путем формирования периферийным блоком условного кода (флага) в соответствующем интерфейсном регистре г) Аппаратно активизируемое задание (обработчик прерываний) возникает внешними по отношению к КС процессами

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

В варианте табл. 5 в причиной возникновения нового задания kt i является возникновение во внешней среде такой ситуации, которая требует очередного выполнения задачи t i. Необходимость выполнения t i фиксируется внешней аппаратурой, эта аппаратура и является источником заданий типа t i. С источником заданий типа t i связан периферийный блок КС, который выполняет первый этап регистрации нового задания kt i – устанавливает условный код (флаг) в определенном интерфейсном регистре. Интерфейсный регистр опрашивается операционной системой с определенной периодичностью и в случае появления в нем условного кода ОС приступает к выполнению тех же действий, что и в варианте а). Эти действия вносят вклад в величину задержки регистрации, но более существенным фактором, определяющим возможную величину задержки регистрации, является частота опроса интерфейсного регистра операционной системой. Длина временного интервала между системными событиями e рег(kt i) и e акт(kt i) определяется теми же факторами, что и для варианта а).

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

На задания, активизируемые системой прерываний (т.е., на процессы исполнения обработчиков прерываний), накладывается существенное ограничение: они должны действовать безостановочно в том смысле, что им запрещено попадать в состояние “ожидание ресурса” (см. рис. 8 и рис. 10). Система должна строиться таким образом, чтобы все ресурсы, требуемые любому обработчику прерываний, были доступны к моменту его активизации. Таким образом, обработке прерываний соответствует упрощенная диаграмма состояний заданий (рис. 11).

 

 
 

 


Рис. 11. Состояния заданий по обработке прерываний

 

Вытеснение задания xt i по обработке прерываний может произойти только по причине активизации более приоритетного обработчика прерываний типа t j с более высоким уровнем приоритета процессора. Задание yt j, в свою очередь, реализуется без попадания в состояние ожидания ресурса – поэтому возобновление xt i может произойти только в момент завершения yt j, то есть, оно не может произойти в результате события типа e зап(t j, g) из-за отказа со стороны yt j от использования CPU по причине занятости ресурса g.

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

На рис. 12 приведен вариант состава атрибутов дескриптора задачи. Структура “дескриптор задачи” содержит здесь два поля для уровня приоритета задачи: уровень приоритета активизации и уровень приоритет исполнения. Это означает, что

· активизация заданий типа t i происходит в случае, когда задание jt i уже зарегистрировано и среди действующих заданий, нет более приоритетных претендентов на ресурс процессора,

· при получении ресурса процессора текущий уровень приоритета задания jt i повышается до значения, указанного в поле “приоритет исполнения”.

 
 

 

 


Рис.12. Атрибуты задач и заданий

 

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

Текстовое представление имени задачи может потребоваться при протоколировании работы приложения, при выдаче на пульт оператора статистической информации, сообщений об особенностях исполнения задач. Указатель кода программы выполнения задачи t i используется ядром ОС при активизации заданий jt i для загрузки регистра (счетчика команд) CPU. Информация о требуемом для выполнения задачи t i объеме стека используется ядром ОС при регистрации заданий jt i.

Требования к конкретному классу приложений реального времени могут привести к пополнению состава атрибутов дескриптора задач. Как отмечено в подразделе 2.2, особое место в ряду системных характеристик задач занимают модельные характеристики, используемые в ходе разработки СРВ, в частности, для определения наиболее эффективной дисциплины планирования, приоритетных уровней заданий, для анализа выполнимости. Некоторые из этих характеристик могут потребоваться и в ходе исполнения программных приложений. В таком случае для размещения значений этих характеристик расширяется состав атрибутов дескриптора задач. Так, например, значение периода Pi выполнения задачи t i может использоваться при регистрации задания jt i для определения момента времени возникновения задания j +1 t i. Нарушение предельных значений относительного срокавыполнения, объема использованного заданием процессорного времени, других модельных параметров могут использоваться для принудительного завершения заданий.

Какие-то из элементов формата дескриптора задач, представленных на рис. 12, могут не потребоваться для реализации конкретного класса приложений. Единственным абсолютно необходимым атрибутом дескриптора задачи является указатель кода программы ее выполнения. Требования эффективности использования аппаратных ресурсов может привести к использованию нескольких форматов дескриптора задач в одной СРВ. Так, для большинства систем типично использование различных форматов дескрипторов для задач с программным и аппаратным механизмами активизации. Формат дескрипторов задач с аппаратным механизмом активизации – это формат вектора прерываний (определяется архитектурой аппаратной части КС), формат дескрипторов задач с программным механизмом активизации (определяется архитектурой ОС) содержит, как правило, больше атрибутов, чем векторы прерываний.

Все поля дескриптора задачи являются константами, поэтому ввиду предъявляемых к СРВ требований (в частности, требований повышенной надежности и автономности по питанию) дескрипторы задач размещаются блоках постоянной памяти КС.

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

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

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

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

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

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

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

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

5.7. Контексты заданий. Множество информационных объектов, имеющих отношение к конкретному заданию, разделено на рис. 12 горизонтальной пунктирной линией на две части. В верхней части рис. 12 размещены системные объекты – объекты, формируемые и используемые ядром ОС. Существование системных объектов (например, дескрипторов задач и заданий) никак не представлено в алгоритмах прикладных задач. Такие системные объекты, как дескрипторы задач и заданий имеют отношение лишь к способу реализации комплекса прикладных задач. Содержание же действий, соответствующих конкретной задаче, полностью задается алгоритмом выполнения задачи, в котором никак не представлены атрибуты дескрипторов задач и заданий – эти атрибуты должны быть доступны только компонентам ОС. Архитектура развитых КС предусматривает средства, полностью исключающие доступ прикладных заданий к системным объектам.

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

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

а) в отношении формальных текстов, которые конструируются или анализируются специалистами (например, текстов программ на языке высокого уровня),

б) в отношении хода исполнения компонент программных систем процессором КС.

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

В контексте задания выделяются две области:

· область кода программы и констант (содержит данные, не изменяющиеся в ходе работы системы, предпочтительно размещается в ПЗУ),

· область переменных, размещаемый в ОЗУ (для активного задания в раздел переменных входят и регистры CPU).

Все элементы постоянной части контекста задания jt i (раздел кода программы и констант) доступны как самому jt i, так и любому другому экземпляру задачи t i. Глобальные константы доступны не только заданиям типа t i, но и заданиям других типов.

В область переменных компонент контекста (размещаемых в ОЗУ) выделяется локальный контекст задания. Особенность локального контекста задания jt i состоит в том, что непосредственный доступ к содержащимся в нем данным открыт только для самого задания jt i. Для размещения локального контекста задания jt i используются:

· комплект рабочих регистров CPU,

· стек задания.

В процессорах с классической архитектурой корнем контекста задания является комплект рабочих регистров процессора (см. пример рис. 13) и, в первую очередь, два регистра в составе этого комплекта: указатель текущей команды (Instruction Pointer – IP) и указатель текущего положения вершины стека (Stack Pointer – SP). Регистр IP реализует (непосредственно) связь процессора с последовательностью выполняемых команд и косвенно – с другими элементами контекста задания, размещаемыми в постоянной и оперативной памяти; регистр SP отслеживает размещение локального контекста задания в стековом разделе оперативной памяти.

 

 
 

 

 


Рис. 13. Вариант комплекта рабочих регистров 16-ти разрядного CPU

 

Исполнение вычислений по программе активного задания jt i сводится к пошаговому изменению переменных компонент контекста jt i. Рабочие регистры CPU играют роль корня контекста для задания в том смысле, что на каждом шаге вычислений изменяются те компоненты контекста jt i , которые указываются содержимым рабочих регистров.

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

На рис.14 связи регистров IP и SP c разделами контекста задания указаны пунктирными линиями, потому, что в интервалах пассивного состояния задания в комплекте рабочих регистров CPU размещается информация, относящаяся к контекстам других заданий.

 

 

 
 

 


Рис.14. Состав контекста задания

 

Действительно, в однопроцессорной системе в каждый момент времени лишь одно из действующих заданий является активным – комплект рабочих регистров настроен на обслуживание этого задания (содержит корневые компоненты его контекста). В момент смены активного задания xt i на вновь активируемое (или возобновляемое) задание yt j комплект рабочих регистров CPU перенастраивается на обслуживание yt j – в частности, в регистр IP помещается адрес текущей инструкции программы t j, в регистр SP помещается адрес текущей вершины стека задания yt j.

Место в оперативной памяти для стекового пространства заданий отводится либо статически (на этапе конструирования многозадачного приложения), либо динамически, в ходе работы СРВ. Стек вновь активизируемого задания yt j можно размещать в свободной части стека вытесняемого задания xt i если алгоритм задачи t j не содержит операторов ожидания и текущий приоритет yt j на интервале существования yt j не смещается ниже приоритета активизации yt j (рис. 15 а). Такая практика является обычной для размещения стеков обработчиков прерываний, поскольку, как отмечено в подразделе 5.5, обработчикам прерываний соответствует упрощенная диаграмма состояний заданий рис. 11.

На диаграмме рис. 15 а в момент t 1 при вытеснении задания 1 t 1 заданием 1 t 2 стековое пространство для 1 t 2 отводится непосредственно над занятой частью стека вытесняемого задания; аналогично в моменты t 2 и t 6 непосредственно над занятой частью стека для 1 t 2 размещаются стеки для активизируемых экземпляров высокоприоритетной задачи t 4.

 
 

 

 


а) б)

Рис.15. Варианты размещения стеков заданий

Возникающее в момент t 3 задание 1 t 3, попадает в состояние ожидания активизации, поскольку процессор занят более приоритетным заданием 1 t 4; задание 1 t 3 активизируется в момент t 4 завершения 1 t 4. На диаграмме показано, как на интервалах между отмеченными моментами времени изменяется (растет и уменьшается) объем стекового пространства используемого для размещения локального контекста текущего задания.

В рассмотренном случае использование общего стека корректно, оно не приводит к повреждению локальных контекстов пассивных заданий. Действительно, при возобновлении в моменты времени t 5, t 7 и t 8 ранее вытесненные задания получают свой локальный контекст в том же состоянии, в котором он был при их вытеснении соответственно в моменты времени t 2, t 5 и t 1. Сохранность локальных контекстов гарантируется тем, что вытесняющие задания не попадают в состояние ожидания запрашиваемого ресурса.

Если же вытесняющее задание может попасть в состояние ожидания ресурса, то при использовании общего стека сохранность его локального контекста не гарантируется. Предположим, например, что в момент времени t 5 задание 1 t 3 не завершается, а запрашивает занятый ресурс. Это означает, что локальный контекст 1 t 3 должен быть сохранен с момента времени t 5 до получения заданием запрашиваемого ресурса. Но, как видно из диаграммы, контекст будет разрушен уже на интервале (t 5, t 6) заданием 1 t 3 и на интервале (t 6, t 7) это разрушение будет продолжено заданием 2 t 4.

Рассмотренный пример показывает, что в общем случае для размещения локального контекста различных заданий, которые могут попасть в состояние ожидания, необходимо выделение независимых участков стекового пространства. Рис. 15 б демонстрирует выделение таких независимых участков стекового пространства для размещения локальных контекстов заданий типа t nt n +3. Задание типа t n +2 выделено на рис. 15 как активное задание (жирная стрелка означает изменение объема локального контекста задания); задания типа t n, t n +1 и t n +3. пассивны, их локальные контексты законсервированы. Объем стекового пространства для локальных контекстов заданий типа t n +2 должен быть достаточным, чтобы гарантировалась сохранность локальных контекстов заданий типа t n +3. При выделении независимых участков стекового пространства для отдельных заданий может требоваться больше оперативной памяти, чем при использовании заданиями общего стекового пространства..

5.8. Переключение контекста. В ходе работы однопроцессорной системы процессор эпизодически перенастраивается с обслуживания одного задания на обслуживание другого, поскольку в каждый момент времени лишь одно из действующих заданий активно (использует CPU), остальные пассивны – находятся в состояниях ожидания (рис. 8, 10, 11).. Такая перенастройка, называемая переключением контекстов, сводится к перезагрузке рабочих регистров процессора – происходит переключение комплекта рабочих регистров процессора из контекста задания, освобождающего CPU, в контекст возобновляемого или активизируемого задания. Можно указать три разновидности ситуаций, требующих переключения контекстов:

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

б) перевод задания в состояние ожидания затребованного ресурса,

в) естественное завершение текущего задания.

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

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

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

Аппаратно сохраняемая часть локального контекста вытесняемого задания размещается в стеке и называется фреймом прерывания. На рис. 16 приведен самый распространенный вариант формата фрейма прерывания. В представленном варианте фрейм прерывания содержит лишь минимально необходимую часть содержимого комплекта рабочих регистров CPU – код состояния процессора и адрес текущей команды (регистр IP). Если обработчик прерываний использует другие рабочие регистры CPU, то сохранение их значений производится в ходе исполнения самого обработчика прерываний. Так, на рис. 17 приведен сценарий исполнения обработчика прерываний, который использует рабочие регистры A и B и оставляет неизменными значения других рабочих регистров CPU.

 

 
 

 


Рис.17. Сохранение элементов локального контекста

в стековом пространстве вытесняемого задания

 

С целью освобождения обработчика прерываний от необходимости программно сохранять элементы локального контекста вытесненного задания архитектура некоторых МК предусматривает использование развернутых форматов фрейма прерываний. Так, расширенный фрейм прерывания (см. рис. 18) позволяет аппаратно сохранять весь комплект рабочих регистров 16-ти разрядного CPU приведенный на рис. 13. Если обработчик прерываний в ходе своей работы модифицирует все рабочие регистры CPU (и, следовательно, их значения должны быть сохранены для возобновления вытесненного задания), то использование расширенных форматов фрейма прерывания позволяет сократить время реакции СРВ на внешние события (повысить реактивность СРВ).

Консервация задания, переводимого в пассивное состояние (в ситуациях а и б) или ликвидация завершившегося задания (в ситуации в) составляет первый этап переключения контекста. Второй этап включает настройку локального контекста активизируемого (или восстанавливаемого) задания и полей дескриптора этого задания. При программной активизации задания первоначальная информация о настраиваемом локальном контексте извлекается ядром ОС из дескриптора задачи. При аппаратном переключении контекста роль дескриптора задачи играет вектор прерывания: адрес точки входа в программу обработки прерывания заносится в регистр IP, код уровня прерывания заносится в соответствующие разряды слова состояния процессора (на рис. 13 это разряды I2, I1, I0). Слово состояния CPU (или специальное поле вектора прерываний) может содержать код типа фрейма прерываний, то есть, указывать, в каком формате системе прерываний следует сохранять в текущем стеке содержимое рабочих регистров CPU.

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

interrupt Application_ISR () {

EnterISR(); // Системный вызов: вход в обработчик прерываний

... // Действия по обработке прерывания

LeaveISR(); // Системный вызов: выход из обработчика прерываний

}

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

Если число действующих заданий превышает число имеющихся комплектов рабочих регистров CPU, то комплект, занимаемый прерванным заданием (или каким-либо из других действующих заданий) должен быть предоставлен для обработки возникшего прерывания. Для этого в рамках выполнения системного вызова EnterISR() производится (программно) сохранение значений рабочих регистров CPU. Для программного сохранения значений регистров может быть использовано стековое пространство вытесняемого задания таким же образом, как это выполняется аппаратным способом (см. рис. 18). Альтернативный вариант – сохранение значений регистров в дескрипторе задания. Подобный альтернативный вариант может использоваться и в системах с единственным комплектом рабочих регистров CPU – на рис. 19 приведен формат расширенного дескриптора задания с дополнительными полями для сохранения рабочих регистров CPU, обеспечивающими реализацию такого альтернативного варианта. При этом доступ по записи в дополнительные поля осуществляется в ходе выполнения системного вызова EnterISR(); доступ по считыванию из дополнительных полей осуществляется в ходе выполнения системного вызова LeaveISR().

 

 
 

 


Рис.19. Сохранение рабочих регистров CPU в дескрипторе задания

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

 
 

 

 


а) б)

Рис.20. Размещение локальных контекстов обработчиков прерываний

Простейший способ поддержки многоуровневых прерываний предусматривает размещение локальных контекстов обработчиков прерываний в стековом пространстве программно контролируемых заданий (рис. 20 а). В этом случае все действия по сохранению и восстановлению локальных контекстов вытесняемых заданий (как программно контролируемых, так и обработчиков прерываний) выполняются аппаратно. Если нет каких-то дополнительных причин, то в этом случае отпадает необходимость обрамления тела программы обработки прерываний системными вызовами EnterISR() и LeaveISR(). Вместе с тем, для каждой задачи с состояниями ожидания ресурса (рис. 15 б) приходится выделять такой резерв стекового пространства, который мог бы вместить максимально высокую пирамиду локальных контекстов вложенных обработчиков прерываний. В случае большого числа задач с состояниями ожидания ресурса такой максимальный резерв должен быть выделен многократно.

Более экономный (в отношении требуемых объемов стекового пространства) способ поддержки многоуровневых прерываний состоит в выделении специального стекового пространства для обработчиков прерываний (рис. 20 б). При этом для размещения локальных контекстов обработчиков прерываний не требуется выделять дополнительный резерв ОЗУ в стековых пространствах задач с состояниями ожидания ресурса. Все локальные контексты обработчиков прерываний размещаются в предусматриваемом для этого специальном стеке обработчиков прерываний. Для реализации такого способа распределения стековой памяти необходимо:

· включать в тело программы обработчиков прерываний системные вызовы EnterISR() и LeaveISR(),

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

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

Контрольные вопросы.

1. Дать определение понятию «системное событие». Какую роль играют системные события в ходе работы СРВ?

2. Привести примеры разновидностей системных событий.

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

4. Как системные события влияют на формирование структуры интервала существования задания? Какие разновидности структурных фрагментов составляют интервал существования задания?

5. В чем смысл термина «квазипараллельное исполнение задач»? В каких ситуациях исполнение задач осуществляется в квазипараллельном режиме?

6. Могут ли пересекаться интервалы существования различных заданий? Какие задания считаются действующими заданиями в текущий момент времени? Чем ограничивается число действующих заданий? Какие из действующих заданий считаются активными в текущий момент времени?

7. Дать определение термину «вытеснение задания».

8. Привести примеры разновидностей системных состояний задания.

9. Привести диаграммы переходов между системными состояниями невытесняемых заданий, вытесняемых заданий, заданий с состояниями ожидания.

10. Привести примеры различных дисциплин планирования порядка исполнения для квазипараллельных заданий. Как выбор дисциплины планирования влияет на время отклика заданий?

11. В чем различие механизмов регистрации и порождения заданий от внешних и внутренних источников?

12. В какие моменты времени формируются дескрипторы задач и заданий?

13. Какое из полей обязательно присутствует в дескрипторах задач любой СРВ?

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

15. Какие разновидности заданий исполняются без формирования соответствующих дескрипторов заданий?

16. Какие типы системных событий приводят к формированию структур типа дескриптора задания? В каких ситуациях, каким образом ОС использует информацию, размещенную в полях дескриптора задания?

17. В каких случаях в состав полей дескриптора задачи следует включать поле со значением периода активизации этой задачи?

18. В чем смысл введения различных значений для приоритета активизации и приоритета исполнения задания?

19. В каких случаях в формате дескриптора задания следует включать поле с указателем дескриптора соответствующей задачи?

20. Что понимается под контекстом задания? В каком смысле текущие значения рабочих регистров процессора являются корнем контекста активного задания?

21. Перечислить основные компоненты контекста задания. В какой области памяти размещается локальный контекст задания? Как выполняется консервация контекста задания при его вытеснении?

22. Почему локальные контексты заданий без состояний ожидания могут размещаются в едином стеке?

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

24. В каких ситуациях выполняется и в чем состоит операция переключения контекста?

25. В чем специфика переключения контекста при активизации обработчика прерываний?

26. Какую структуру называют фреймом прерывания? Где размещается вновь формируемый фрейм прерывания? Привести варианты состава фрейма прерывания.

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Поиск по сайту:



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