Планирование процессов вытесняющее и невытесняющее планирование; политики планирования; процессы и нити

Вид материала

Лекция

Содержание Критерии эффективности организации вычислительных процессов 2. Среднее взвешенное время обращения Связь между процессами и ресурсами вычислительной системы P и протекающие в вычислительных ресурсах R Модель процесса Information, Resource, Acknowledge 1.Операционная система как система управления ресурсами Управление ресурсами включает решение двух общих, не зависящих от типа ресурса задач Особенности управления заданиями Таблица 3.1. Таблица задания Job Control Block (JCB) 4.1 Введение в ДО Планирование заданий Таблица 6.1.Частость планирования в вычислительной системе Уровни планирования в операционной среде Системные задачи ОС - распределяет ресурсы между работами пользователей.SV

Подобный материал:

• Планирование и диспетчеризация процессов. Приоритеты. Алгоритмы планирования. Коммуникация, 148.83kb.
• Лекция: Планирование процессов, 482.91kb.
• Вопросы к зачету по дисциплине «Корпоративное планирование», 48.25kb.
• Планирование налога на доходы физических лиц, 83.85kb.
• Магистратура направления 220700 «Автоматизация технологических процессов и производств», 87.73kb.
• Понятие внутрифирменного планирования. Планирование как экономическая категория, 35.27kb.
• Курс лекций тема Предмет, метод и задачи бизнес- планирования, 23.47kb.
• Планирование и контроль рабочих процессов в логистике требуют точной оценки тех объемов, 700.59kb.
• Планирование показателей деятельности турфирмы. Процесс стратегического планирования, 228.81kb.
• Планирование деятельности предприятия, 396.29kb.

Лекция CSOS02. вычислительный процесс и его реализация с помощью ОС;


Планирование процессов

вытесняющее и невытесняющее планирование;

политики планирования;

процессы и нити;

планирование в системах реального времени.

Взаимодействие процессов: модели и механизмы;

сигналы; сообщения, очереди сообщений;

файлы, именованные каналы, сокеты;

почтовые ящики; разделяемая память.

ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС (calculation process). Процесс решения задач на ЭВМ

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

Алгоритм - одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. А. являются, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком. Вообще, под А. понимается всякое точное предписание, которое задаёт вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного А. исходных данных) и направленный на получение полностью определяемого этим исходным данным результата; например, в упомянутых А. арифметических действий возможными результатами могут быть натуральные числа, записанные в десятичной системе, а возможными исходными данными упорядоченные пары таких чисел, и содержание предписания, т. о., помимо инструкции по развёртыванию алгоритмического процесса, должно входить также: 1) указание совокупности возможных исходных данных (в. и. д.) и 2) правило, по которому процесс признается закончившимся ввиду достижения результата. Не предполагается, что результат будет обязательно получен: процесс применения А. к конкретному в. и. д. (т.е. алгоритмический процесс, развёртывающийся начиная с этого данного) может также оборваться безрезультатно или не закончиться вовсе. В случае, если процесс заканчивается (соответственно не заканчивается) получением результата, говорят, что А. применим (соответственно неприменим) к рассматриваемому в. и. д. (Можно построить такой А. Á, для которого не существует А., распознающего по произвольному возможному для Á исходному данному, применим к нему Á или нет; такой А. Á можно, в частности, построить так, чтобы совокупностью его в. и. д. служил натуральный ряд.)

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

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

Критерии эффективности организации вычислительных процессов

Показатель эффективности - это производительность ЭВМ.

Производительность ЭВМ характеризуется параметрами:

• пропускная способность - объем работы в единицу времени;
  
• время ответа - промежуток от момента приема задания пользователя до получения ответа;
  
• коэффициент готовности - степень готовности обработать запрос на вычисление.
  

Соотношение перечисленных факторов и назначения системы:

• система реального времени - МIN t_ответа;
  
• пакетная обработка - MAX пропускная способность;
  
• система разделения времени (СРВ) - МАХ пропускной способности при соответствующих (разумных) ограничениях на t_ответа.
  

Критерии эффективности вычислительного процесса

1. Среднее время ответа - время пребывания работ в системе (среднее время обращения).



где n - число заданий tзi - время завершения i-ой работы;tni - время поступления i-ой работы.

2. Среднее взвешенное время обращения



где i - трудоемкость i-ой работы (время нахождения на цикле)


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


ссылка скрыта

История параллелизма насчитывает уже не один десяток лет. За это время были разработаны, использованы и забыты разнообразные языки параллельного программирования (ЯПП), а также архитектуры параллельных вычислительных систем (ПВС). Можно вспомнить транспьютеры, векторные и матричные процессоры, процессоры потока данных и многие другие. Во многом их уход был обусловлен не столь архитектурными недостатками, сколь ограничениями микроэлектронной технологии, не позволившими, в свое время, осуществить реализацию на едином кристалле, чтобы составить конкуренцию RISC архитектурам. Даже CISC архитектуры смогли выжить только благодаря стараниям корпорации Intel. Так или иначе, в настоящее время на вершине популярности находятся кластерные вычислительные системы, построенные на базе процессоров с традиционной архитектурой. Вполне возможно, что интерес к нетрадиционным параллельным системам со временем вновь возродится, так как современные технологии уже сейчас позволяют реализовать на одном кристалле множество одновременно работающих модулей. Это, в какой-то мере, подтверждается последними разработками ряда компаний, переходящих к производству процессоров, реально поддерживающих многопоточность внутри кристалла.

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

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

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

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

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

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

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

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

Модель вычислительного процесса

Связь между процессами и ресурсами вычислительной системы

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

Определим вычисления, определяющие процесс P и протекающие в вычислительных ресурсах R как обработку операционного пакета I_in, в результате чего формируется выходной пакет I_out. Пусть момент начала вычислений определяется входным управляющим воздействием C_in, а их завершение фиксируется по выдаче вычислительным ресурсом управляющего сигнала C_out. Графическое обозначение этих вычислений представлено на рис. 1. Иерархическая организация вычислений позволяет говорить о том, что процесс можно разделить на более мелкие подпроцессы, каждый из которых может выполняться в отведенной для этого части общих ресурсов. При этом, одни и те же ресурсы могут повторно использоваться при выполнении различных вычислений, разделяясь подпроцессами во времени.



Рис. 1. Процесс как вычисления, протекающие в ресурсе

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

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

подсистему хранения данных, получаемых в ходе вычислений;

подсистему хранения исходной программы;

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

подсистему управления ресурсами, коими являются все выше перечисленные подсистемы.



Рис. 2. Потоки, определяющие протекание процессов в вычислительной системе

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

Модель процесса

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

P = (I, R, C),

где I = (Iin, Iout) - информационные пакеты, определяющие функцию обработки, ее аргументы и результаты, R - ресурсы вычислительной системы, предоставленные для выполнения процесса обработки данных, C = (C_in,C_out) - сигналы управления, определяющие последовательность действий по обеспечению корректного выполнения процесса и определяющие причинно-следственную или временную привязку. На рис. 3. представлено графическое изображение процесса в соответствии с описанной интерпретацией.



Рис. 3. Потоки, определяющие протекание процессов в вычислительной системе

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

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

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

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

Декомпозиция процесса, определяющего поведения программы, не является безграничной. На самом нижнем уровне можно выделить элементарный вычислительный процесс, который имеет один управляющему вход и один управляющий выход. Поступление сигнала на вход определяет момент запуска процесса. Завершение обработки сопровождается выдачей управляющего сигнала, информирующего о готовности данных. В ходе вычислений элементарный процесс не выдает и не принимает никаких управляющих сигналов. Попытка повторно запустить его в этот момент приведет к ошибке в вычислениях. Подобную ситуацию следует считать запрещенной. Реакция на нее специально не оговаривается. Можно, в этом случае, блокировать повторный доступ, прерывать работу всей системы с указанием причины или повторно инициировать запуск. Предположим также, что каждый элементарный процесс выполняет конкретную операцию F_i, которую можно будет записывать внутри прямоугольника вместо общего обозначения процесса (P). Вместо рисования подсистемы управления ресурсов будем оставлять один конец ресурсной связи свободным. Графическое обозначение элементарного процесса представлено на рис. 4. Подобные процессы далее будем также называть функциональными.



Рис. 4. Элементарный (функциональный) процесс

Моделирование и изучение динамики процессов можно осуществлять на основе механизма продвижения фишек. Этот механизм широко используется в различных моделях вычислений [Деннис, Котов]. Описание различных состояний элементарного процесса показано на рис. 5.



Рис. 5. Продвижение фишек, моделирующее выполнение элементарного процесса

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



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

ICR-сеть

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



Рис. 7. ICR-сеть, описывающая поведение процессов в ресурсах вычислительной системы

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

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

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

Стратегии управления процессами

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

1. Условие готовности данных (Information - условие). Перед запуском процесса на его информационных входах должны присутствовать все необходимые аргументы и функции, составляющие операционный пакет. Отсутствие каких-либо данных к моменту запуска процесса ведет к получению неправильного результата. То есть, если существуют процессы, результаты которых являются аргументами рассматриваемого процесса, то они должны завершиться к моменту запуска текущего процесса.
   
2. Условие выделения ресурсов (Resource - условие). Выполнение процесса протекает в соответствующих ресурсах, поэтому, перед его запуском, эти ресурсы должны быть определены и предоставлены. Ресурсный вход должен содержать информацию, подтверждающую выделение ресурсов, необходимых для успешного выполнения процесса. В противном случае его запуск просто невозможен.
   
3. Условия подтверждения использования результатов (Acknowledge - условие). Ресурсы, занимаемые процессом, могут освобождаться или повторно использоваться только после того, как результаты вычислений будут использованы всеми процессами, являющихся приемниками этих результатов в качестве аргументов. В противном случае данные будут потеряны, что приведет к неправильным вычислениям. Необходимость задержки в освобождении ресурсов мотивируется тем, что память, используемая для хранения операндов, является разделяемым ресурсом. В нее записываются результаты вычислений элементарного процесса. Из нее же происходит чтение аргументов, необходимых другим процессам.
   

Информация о выполнении условий готовности в рассматриваемой модели подтверждается наборами соответствующих управляющих сигналов:

сигналами готовности элементов операционного пакета;

сигналами готовности необходимых вычислительных ресурсов;

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

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

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

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

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

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

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

( Information, Resource, Acknowledge),

Каждое из условий готовности процесса может принимать одно из трех допустимых значений:

(Subjective, Automatic, Empty).

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

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

Заключение

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

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

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

Литература

[Деннис] Деннис Д.Б., Фоссин Д.Б., Линдерман Д.П. Схемы потока данных. / Теория программирования. Часть 1. Новосибирск: ВЦ СО АН СССР. 1972. С. 7 - 43.

[Джоунз] Джоунз Г. Программирование на языке Оккам: Пер. с англ. - М.: Мир, 1989. - 208 с.

[Ершов] Ершов А. П. Введение в теоретическое программирование (беседы о методе). - М.: Наука. Главная редакция физико-математической литературы, 1977. - 288 с.

[Котов] Котов В. Е. Сети Петри. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 160 с.

[Хоар] Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. - М.: Мир, 1989. - 264 с.



PS

Размышления о стратегиях управления имеют долгую историю. Впервые к этой теме я обратился в начале 80-х, когда занимался анализом различий между процессорами потока данных (ППД) и прочими параллельными вычислительными системами. Да и внутри ППД существовало большое разнообразие решений, проявляющееся как на уровне моделей вычислений, так и на уровне структур. Тогда же появилась и первые публикации по этому поводу, кратко характеризующая 16 основных стратегий [1-2]. После этого был длительный период, связанный с другими работами. Окончательная версия классификации сформировалась в начале 90-х. Она была апробирована в лекциях по "Архитектуре вычислительных и программных систем", читавшихся мною в Ярославском государственном университете. В печатном виде появилась и слегка уточнилась только в 1994 [3-4].

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

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

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

PS-Литература

Водяхо А.И., Легалов А.И. Организация асинхронных вычислений в высокопроизводительных спецпроцессорах. - Изв. ЛЭТИ. Науч. тр./ Ленингр. Электротехн. ин-т им. В.И. Ульянова (Ленина), 1984, вып. 343. Проектирование и применение микропроцессорных систем. с. 20-23.

Водяхо А.И., Емелин В.П., Легалов А.И. Стратегии управления вычислительными процессами и их модели. - В кн.: Математическое и программное обеспечение САПР сетевых систем, Йошкар-Ола, 1985, с. 135-142.

Легалов А.И. Стратегии управления вычислениями. - В кн.: Проблемы техники и технологий XXI века. Материалы научной конференции. Красноярск, КГТУ, 1994, с. 122-126.

Легалов А.И. Управление в вычислительных системах и языках программирования. - В кн.: Проблемы информатизации города: Материалы конференции. Красноярск, 1994, с. 198-202.

1.Операционная система как система управления ресурсами

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

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

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

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

Особенности управления заданиями

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

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

В таблице 3.1 и 3.2 представляет собой данных из таблице заданий Job Control Block (JCB) и таблице задач Task Control Block (TCB)



Таблица 3.1. Таблица задания Job Control Block (JCB)


Таблица 3.2. Таблица задач Task Control Block (TCB)

На рисунке 3.1 приведена последовательность исполнения заданий в вычислительной системе.


Рис.3.1. Блок-схема последовательности исполнения заданий в вычислительной системе

На рисунке 3.2 представлена схема функционирования операционной системы


Рис. 3.2. Схема функционирования операционной системы

Представление - это этап считывания информации.

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

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

Выполнение - процесс получает процессор.

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

Завершение - все ресурсы у процесса забраны (ликвидированы).

Дисциплины обслуживания (ДО) очередей

4.1 Введение в ДО

1. На каждый из планировщиков поступает поток работ (заявок).

2. Формируются очереди работ.

3. Имеется ресурс, способный выполнить соответствующую работу.

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

5. Заявки имеют параметры:

-время обслуживания (трудоемкость);

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

На рисунке 4.1 представлена схема одноканальной системы без отказов


Рис. 4.1.Схема одноканальной системы без отказов

Замечание: Обслуживание заявок из очереди носит в общем случае стохастический характер, т.е. время обслуживания различно.

t_нахождения_в_системе = t_выпол. + t_ожид.

Планирование работ в вычислительной системе

Планирование заданий - это верхний уровень планирования использования ресурса - центрального процессора.

Причины сложности планирования.

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

В таблице 6.1 приведена частость планирования в вычислительной системе


Таблица 6.1.Частость планирования в вычислительной системе

Уровни планирования в операционной среде

1. Задание ожидает ввода в систему
   Ввод заданий
   
2. Задание ожидает запуска.
   Запуск заданий
   
3. Приостановленные процессы, ожидающие активизации
   Активизировать Приостановить
   
4. Активные процессы
   Блокирование Пуск
   
5. Исполняющие процессы
   Завершение
   
6. Завершенные процессы
   

2-3 - планирование верхнего уровня

3-4 - планирование промежуточного уровня

4-5 - планирование нижнего уровня

3 – Ожидание

4 - Выполнение Жизненный цикл задачи

5 - Готовность

На рисунке 7.1 приведена блок-схема жизненного цикла задачи.


Рис.7.1. Блок-схема жизненного цикла задачи


На рисунке 7.2 приведена схема управления работами в вычислительной среде.


Рис.7.2. Схема управления работами в вычислительной среде

Пояснения.
1. Управление заданиями - это часть ОС, которая организует задания из входного потока, осуществляет их подготовку, запуск и контроль.

Функции.
1.1. Анализ входного потока (определение начала задания, контроль правильности операторов, порядка их следования, определение конца задания).

1.2. Запись входной информации на устройство с прямым доступом.

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

1.4. Распределение устройств ввода/вывода (т.е. индивидуальное или коллективное пользование ресурсами).

1.5. Подготовка к запуску с контрольной точки.

1.6. Общее планирование порядка выполнения работ.

2. Управление задачами - это часть ОС, которая динамически распределяет ресурсы системы между задачами их управления.

Функции.
2.1. Обработка прерываний.

2.2. Управление оперативной памятью.

2.3. Загрузка программ в ОП для выполнения.

2.4. Обработка окончания программы.

2.5. Управление службой времени.

2.6. Управление возобновлением программы с контрольной точки (по окончании части программы, либо после команды, либо внутри команды).

2.7. Защита памяти.

2.8. Управление одновременным выполнением задач.

3. Управление данными - это часть ОС, которая представляет стандартные процедуры управления данными.

На рисунках 7.3 и 7.4 приведены блок-схемы выполнения задания пользователя и задачи в системе соответственно.


Рис.7.3. Блок-схемы выполнения обработки задания пользователя


Рис.7.4. Блок схема выполнения задачи в системе

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

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

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

Выполнение - процесс j получает процессор.

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

Завершение - все ресурсы освобождаются.

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

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

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

Системные задачи

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

SV выполняет различной сложности макрокоманды. На уровне макрокоманды оформляется системная задача.

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

Системная задача - это ресурс:

• к ней может быть сформирована очередь;
  
• она может быть прервана.
  

Пример системных задач.

1. Передать управление программе с возвратом ("Соединить", "Создать цепочку").Функции:

• поиск модуля;
  
• выделение памяти;
  
• загрузка;
  
• настройка;
  
• передача управления;
  
• подготовка возврата управления но следующую команду;
  
• освободить ОП.
  

2. Загрузка системной задачи.

• проверка наличия в ОП;
  
• поиск модуля;
  
• выделение ОП;
  
• загрузка;
  
• настройка;
  
• возврат.
  

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

ATTACH - активизировать (создать задачу);
DETACH - деактивизировать (уничтожить задачу);
GETMAIN - занять ОП;
FREEMAIN - освободить ОП;
EXCP - активизировать работу канала I/O;
STIME - установить интервальный таймер и другие.

Ядро операционной системы

Ядро непосредственно ведет распределение ресурсов между процессами (задачами).

ОС - распределяет ресурсы между работами пользователей.

SV - распределяет ресурсы между задачами пользователей.

Ядро ОС - распределяет ресурсы между задачами (процессами) пользователей и системными процессами.

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

Состав ядра ОС:

• SV прерываний;
  
• SV ввода-вывода;
  
• SV задач;
  
• SV ОП;
  
• SV времени;
  
• диспетчер.
  

Функции ядра ОС.

1. Порождение процессов.
   
2. Уничтожение процессов (завершение).
   
3. Реализация механизмов связи между процессами.
   
4. Реализация основных функций распределения ресурсов (CPU,
   ВУ, ОП, таймер и т.д.).
   

На рисунке 10.1 приведены блок схема взаимодействия ядра и задач(системных и проблемных): общая схема (а), непосредственно диспетчер(b).



a)


Рис.10.1. Блок схема взаимодействия ядра и задач(системных и проблемных): общая схема (а), непосредственно диспетчер(b)

На рисунке 10.2 приведена временная диаграмма взаимодействия ядра и задач.


Рис.10.2. Временная диаграмма взаимодействия ядра и задач

ссылка скрыта