Раздел 3. Параллельное выполнение программ

3.1. Концепция процесса

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

Процессор простаивал в ожидании завершения ввода/вывода, поэтому появилось естественное желание занять его на это время другими задачами.

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

Существует принцип, аналогичный принципу дуальности в электротехнике (L <-> 1/C), согласно которому в вычислительной управляющей ЭВМ должно протекать, выполняться столько же вычислительных процессов, сколько их протекает в объекте, управляемом этой ЭВМ.

Существует два пути реализации такой системы в зависимости от архитектуры компьютера.

Пусть N - число процессов, а М - число процессоров.

1.      Если М >= N, то можно говорить о подлинной параллельности.

2.      Если M < N, а чаще всего, М = 1, то можно говорить о временном разделении.

Представим это графически.

1) Компьютер - многопроцессорная машина:

2) Компьютер - однопроцессорная машина:

В этом случае используется временное разделение (time-sharing) и говорят о псевдопараллельности.

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

Как пример можно привести коллективное использование машины PDP-11.

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

Например, необходимо, чтобы процесс 1 прошел через точку A в своей программе раньше, чем процесс 3 пройдет через точку B в своей программе. (Процесс 1 записывает данные в буфер в точке A, а процесс 3 читает данные из этого буфера в точке B, а читать данные можно только после того, как они записаны).

Так вот решение такой задачи не зависит от того, по какой схеме выполняются процессы - по схеме 1 или по схеме 2.

Учитывая два приведенных фактора:

1.      высокая частота переключений процессов, которая позволяет пренебречь ею и свести схему 2 к схеме 1,

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

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

Здесь как бы вводятся понятия аппаратного и логического параллелизма.

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

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

Существует несколько определений понятия ПРОЦЕСС, некоторые из которых приведены ниже:

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

2.      Процесс - это программа в состоянии выполнения.

3.      Процесс - это пара <процессор, программа> при выполнении.

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

Для процесса есть другое название - задача.

Целесообразно выделить два аспекта понятия ПРОЦЕСС - практический и теоретический.

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

Теоретический аспект - математические модели понятия процесс.

Практический аспект понятия ПРОЦЕСС

Понятие «процесс» существует во всех современных многозадачных операционных системах, особенно связанных с сетевыми приложениями - IBM OS/2, Microsoft Windows XP, Novell UnixWare, Novell NetWare. Различаются лишь программные интерфейсы для загрузки или порождения процессов.

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

1.      На самом высоком уровне находится понятие СЕАНС. Это запуск прикладной EXE-программы. Сеансов может быть несколько, но только один из них активный, захватывающий экран и клавиатуру. Остальные фоновые, но выполняющиеся. Над сеансами стоит МЕНЕДЖЕР СЕАНСОВ.

2.      Следующий уровень - ПРОЦЕСС. Это запуск одного EXE-файла из другого. Между ними существует отношение РОДИТЕЛЬ/ПОТОМОК с определенным протоколом заимствования ресурсов.

3.      Нижний уровень - НИТЬ или МИНИЗАДАЧА. Это параллельно выполняющиеся процедуры в рамках одного процесса.

Графически эти уровни сопоставляются следующим образом.

                Нить 1

                                                                           Процесс 2       

           Создать процесс

                                                               Нить 1                                

                                                            Создать нить            Нить 2  

                                                               Выход          

                                                                                                                        Процесс 3

           Создать процесс                                                                                               

                                                                                                                           Нить 1

       Уничтожить процесс

                   Выход

Интересно сопоставить эту архитектуру с архитектурой DOS, в которой мы тренируемся. 

В DOS один сеанс, хотя есть средство, которое называется TaskManager, позволяющее запускать сразу несколько приложений. Одно приложение активно, другие - приостановлены.

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

Минизадача - это те средства, которые мы с вами создаем на лабораторных работах по данному курсу. Они есть в Аде и Модуле-2 как стандартные, но могут быть созданы для Паскаля и Си вручную.

Теоретические аспекты понятия ПРОЦЕСС

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

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

Вводится понятие СОБЫТИЕ. Это первичное понятие, поэтому ему не дается определения. Но даются имена событиям X, Y и т.д.

Вводится понятие ПРОЦЕСС, как объект, реагирующий на события. Процессам тоже даются имена, например, P, Q и т.д.

Вводится формальная запись вида:

X -> P,

означающая, что событие воздействует на процесс.

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

Для описания такой последовательности используется рекурсия:

P = ( X -> P ).

В таком рекурсивном уравнении могут быть выполнены формальные подстановки:

P = (X->(X->P)) = (X->(X->(X->P)))

и так до бесконечности.

Например, ЧАСЫ - это объект, генерирующий событие ТИК, и после этого ведущий себя опять так же:

ЧАСЫ = (ТИК->ЧАСЫ).

Используя рекурсию, получаем описание потенциально бесконечного поведения объекта ЧАСЫ:

ТИК->ТИК->ТИК->ТИК->ТИК->ТИК->...

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

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

Более практичным является следующее определение понятия ПРОЦЕСС.

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

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

Факт изменения состояния машины называется событием.

Если есть неделимое действие А, то НАЧ(А) и КОН(А) – это события. При этом,

ТНАЧ(А) < ТКОН(А)

Выполнение программы представляется последовательностью действий

А1 , А2 , ... , Аi , ... ,

для которой

ТКОН (Аi) < ТНАЧ(Аi+1)

Такая последовательность действий называется последовательным процессом или просто процессом.

Далее рассмотрим совокупность двух (для простоты) последовательных процессов.

Может быть три варианта выполнения совокупности процессов:

 

 

 

 

 

 

 

Для схем 2) и 3):

ТКОН (p) > ТНАЧ(q)

Cхемы 1), 2), 3) - это:

1.      последовательное выполнение;

2.      псевдопараллельное выполнение;

3.      параллельное выполнение - нужно два процессора.

Различие между схемами определяется уровнем наблюдения. Если в качестве интервала наблюдения взять очень большой интервал, то схема 1) не будет отличаться от схем 2) и 3), т.к. оба процесса закончат выполнение внутри этого интервала.

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

3.2. Средства описания параллелизма

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

3.2.1. Графические средства

Графические средства представлены ГОСТ 19701.90, который называется "Схемы алгоритмов, программ, данных и систем". В этом ГОСТе есть пункт п. 3.2.2.5, называемый "Параллельные действия".

В этом пункте есть следующие примеры:

1)                                                       Синхронизация двух или более параллельных операций

2)

В данной схеме C, D, E начинаются только после завершения A, а F начинается только после завершения B, C, D.

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

3.2.2. SDL – диаграммы

Еще одним средством описания процессов являются SDL-диаграммы. SDL - это "specification and description language". Этот язык широко применяется для описания процессов в системах реального времени. Сам язык описан в Международных Рекомендациях МККТТ Z.101 - Z.104.

Следующие символы могут быть использованы:

               state

"state" - состояние, в котором действие процесса приостановлено в ожидании ввода;

              внешний ввод (external input)

              внутренний ввод (internal input)

"input" - входящий сигнал, который распознается процессом;

               внешний вывод (external output)

               внутренний вывод (internal output)

"output" - действие, которое генерирует сигнал, который в свою очередь действует в другом месте как ввод;

решение (decision)

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

             задача (task)

"task" - любое действие, которое не является ни решением, ни выводом.

Рассмотрим пример использования SDL диаграммы для описания процессов.

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

Пусть передача информации выполняется по следующему алгоритму.

В определенные моменты времени система ожидает прием блока информации и отвечает передачей квитанции.

Если система неправильно принимает несколько блоков подряд или в течение некоторого времени не принимает их вообще, то она отключается.

Если система принимает ожидаемый блок, то она выдает квитанцию и снова переходит к ожиданию.

Временная диаграмма алгоритма может выглядеть следующим образом:

Фрагмент SDL-диаграммы, описывающей приведенный выше алгоритм, может выглядеть следующим образом:

                                               да            «достигнут ли порог по числу ошибочно принятых подряд блоков»

                                       нет

Временные соотношения в системе поддерживает система прерываний.

3.2.3. Языковые средства описания параллелизма

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

В языке АДА существует следующее средство - если описать некоторые программные единицы как задачи - TASK, то с момента начала выполнения всей программы эти единицы начнут выполняться параллельно. Т.е. обработчик прерываний и средства замены контекста зашиты в АДЕ на уровне языка. Кроме того, АДА предлагает некоторый механизм взаимодействия задач, который называется РАНДЕВУ, тоже существующий на уровне языка.

В языке МОДУЛА-2, который весь построен на библиотечных модулях в соответствие со своим названием, есть модуль Process, который реализует временное разделение с помощью обработчика прерываний и содержит протокол и набор процедур-примитивов, позволяющий создавать из процедур параллельно выполняемые процессы и организовывать их взаимодействие. Модуль Process предлагает следующие возможные действия:

1.      StartProcess:              создать процесс;

2.      StartScheduler:          запуск планировщика задач с временным разделением;

3.      StopScheduler:          останов планировщика задач;

4.      WAIT:                       ждать сигнал;

5.      SEND:                       послать сигнал.

Процессы в Модуле-2 создаются из сопрограмм аналогично рассматриваемым в лабораторных работах.

Современные операционные системы предоставляют примитивы - API, позволяющие реализовывать многозадачность. Эти примитивы отличаются синтаксисом в зависимости от среды и могут трактоваться как расширения языка программирования, в точности соответствуя понятию ВЫЗОВ СУПЕРВИЗОРА.

Примеры

Unix

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

2.      Sleep(sec)   приостанов процесса на sec секунд.

3.      Exit            завершение вызывающего процесса.

Windows

1.      CreateProcess            создание процесса.

2.      ExitProcess                завершение текущего процесса.

3.      CreateThread             запуск экземпляра нити.

4.      ExitThread                 завершение работы нити.

5.      Sleep(ms)                  приостанов процесса на ms миллисекунд.

OS/2

1.      DosExecPgm             создание процесса.

2.      DosExit                     завершение процесса.

3.      DosCreateThread       создание нити.

4.      DosSleep(ms)            приостанов процесса.

NetWare

1.      spawnlp                     загрузка выполняемого файла (NLM NetWare loadable Module) и инициализация его выполнения.

2.      delay(ms)                  приостанов процесса.

3.      BeginThread              создать нить и поместить ее в очередь выполнения.

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

5.      ExitThread                 завершение выполнения нити или NLM.

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

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

1.      Нотация "and" позволяет программисту указывать предложения, которые выполняются параллельно.

             Например,

2.      (Уже не Вирт) "fork w" команда, выполненная процессом p, вызывает начало развития нового процесса q с команды, помеченной w. Далее процессы p и q развиваются одновременно.

3.      "quit" - завершение процесса.

4.      "join t, w" вызывает следующие действия:

---------------------

t := t - 1;

if t = 0 then goto w;

---------------------

Цель этой команды - обеспечить синхронизацию процессов, т.е. начать выполнение с метки w только после того как несколько процессов (их число определяет, в какое начальное значение инициализируется t) выполнят команду join. После нее обычно ставится команда quit. Только последний из перечисленных процессов пойдет на метку, остальные завершатся.

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

Иллюстрация

Обозначение по ГОСТ

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

Введем переменные Т1 и Т2.

Т1 := 2;       w1: P1;        join T2, w5;

T2 := 2;       join T1, w4;   quit;

P0;            quit;          w4: P4;

fork w1;       w2: P2;        join T2, w5;

fork w2;       join T1, w4;   quit;

fork w3;       quit;          w5: P5;

quit;          w3: P3;        quit;

 

Обратим внимание на требование неделимости действий в команде join. Посмотрим, как правильно должна выполняться эта команда.

 

Предположим, что t = 2 и оба процесса подошли к выполнению этой команды.

---------------------          ---------------------

t := t - 1;                    t := t - 1;

if t = 0 then goto w;          if t = 0 then goto w;

---------------------          ---------------------

quit;                          quit;

Если первым подойдет процесс 1, то t станет равным 1 и первый процесс перейдет к выполнению оператора quit без перехода на метку. Второй процесс сделает t, равным 0, и пойдет на метку w. Это так надо, чтобы выполнялось.

Что может произойти, если команда join не будет неделимой. Это значит, что когда первый процесс уменьшит t на 1, управление может передаться второму процессу, который тоже уменьшит t на единицу. После этого первый процесс пойдет на метку w и второй процесс пойдет на метку w, т.к. t = 0 для обоих процессов перед условным оператором. Это неправильно.

3.2.4. Описание процессов средствами UML

3.2.4.1.   Общая характеристика UML

UML – это язык для выражения конструкций и отношений сложных систем..

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

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

3.2.4.2.   Контекстные диаграммы

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

3.2.4.3.   Варианты использования

Диаграммы вариантов использования представляют собой одно из средств описания реакции системы на определенные внешние события и являются детализацией контекстных диаграмм, рассмотренных выше.

3.2.4.4.   Сценарии

               Дальнейшей детализацией вариантов использования являются сценарии. Любой отдельный вариант использования порождает множество сценариев.

 

3.2.4.4.1.                Описание сценариев последовательными диаграммами

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

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

3.2.4.4.2.                Описание сценариев временными диаграммами

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

3.2.4.4.3.                Описание сценариев диаграммами сотрудничества

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

 

3.2.4.5.   Диаграммы объектов

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

3.2.4.6.   Диаграммы классов

Объекты, которые идентичны по структуре и поведению, должны быть объединены в классы.

3.2.4.6.   Диаграммы состояний

Самым важным средством описания поведения системы является описание с помощью диаграмм состояний.

3.2.4.7.   Диаграммы активности

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

3.2.4.8.   Диаграммы развертывания

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

3.3. Организация ЯДРА ОС

3.3.1. Ядро как средство организации виртуальной машины

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

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

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

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

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

1.      увеличение числа виртуальных машин, реализованных на одной физической машине, ухудшает их качество;

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

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

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

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

Ядро организует и координирует предоставление ресурсов различным процессам. Самый первый из совместно используемых ресурсов - это процессор. Детальный анализ взаимодействия процесса и процессора приводит к появлению понятия СОСТОЯНИЕ ПРОЦЕССА. Рассмотрим это понятие более подробно.

3.3.2. Состояния процесса и структура ядра

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

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

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

Ядро переводит процессы из одного состояния в другое.

Рассмотрим подробнее причины блокирования процессов. Их два класса:

1.      техническая причина, состоящая в том, что процессор один, а процессов много;

2.      логические причины.

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

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

Блокированными, строго говоря, называются процессы, приостановленные по второй логической причине.

Т.е. схема состояний процесса уточняется следующим образом:

Если процессов много, готовых или блокированных, то необходимо некоторое средство, которое бы их как-то упорядочивало. В качестве такого средства выступает ОЧЕРЕДЬ процессов.

Из готовых процессов создается очередь готовых процессов.

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

               После проведенных рассуждений станет понятной следующая структура ядра - ядро - это набор очередей процессов и средств перевода процессов из одних очередей в другие и в активное состояние:

Средства ядра делятся на два вида:

1.      Д - диспетчер - это обработчик прерываний от таймера, который переводит активный процесс в очередь готовых, а из очереди готовых выбирает новый активный процесс;

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

Вызов процедуры планировщика - это вызов супервизора по нашей классификации способов переключения контекста.

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

1.      по времени - с помощью диспетчера;

2.      по событию - с помощью планировщика.

Графически это может быть представлено следующим образом:

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

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

Деление средств ядра на планировщик и диспетчер можно обобщить и говорить об уровнях планирования загрузки процессора, которые мы рассмотрим после знакомства с понятием ДЕСКРИПТОР ПРОЦЕССА и ОЧЕРЕДИ ПРОЦЕССОВ.

3.3.3. Дескрипторы процессов

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

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

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

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

Type

        Process = ^Descriptor;

        Descriptor = Object

               ssreg     : Word;

               spreg     : Word;

               StackAddr : Pointer;

               StackSize : Word;

               Priority  : Word;

               Next      : Process;

               Queue     : Process;

               Constructor Init(...);

               Destructor  Done; Virtual;

        End {Descriptor};

Var

        P : Process;

Begin

        P := New(Process, Init(...));

        ...

        Dispose(P, Done);

End.

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

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

Пример 3. Структура типа jmp_buf в СИ, которую мы тоже рассматривали раньше - это тоже дескриптор.

В общем случае дескриптор процесса содержит следующие данные:

1.      имя - уникальный идентификатор;

2.      состояние виртуальной и реальной машины:

1.                процессор (регистры, флаги);

2.                память;

3.                списки созданных ресурсов.

3.      состояние:

1.                активный;

2.                готовый;

3.                блокированный.

4.      родственные связи:

1.                родитель;

2.                потомки.

5.      данные для планирования:

1.                приоритет;

2.                указатели на следующий и предыдущий в очереди;

3.                указатель на очередь, в которой находится.

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

3.3.4. Очереди процессов в ядре

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

Очередь процессов в ядре - это фактически очередь дескрипторов процессов.

Из программирования известны списковые структуры данных. На этих структурах и основаны очереди процессов.

Три варианта построения очереди можно предложить.

1.      Классический вариант, когда в структуру дескриптора включено поле - указатель на следующий процесс:

2.      Более универсальный вариант

3.      Коллекции - объект, который совмещает в себе достоинства списковой структуры - динамическое изменение размеров и массива - индексный доступ.

Объект - отсортированные коллекции позволяет учитывать приоритеты процессов.

Список - как объект может иметь следующее минимальное описание:

Type

        PList = ^TList;

        TList = Object

               First : Process;

               Constructor Init;

               Destructor  Done; Virtual;

               Procedure   Insert(P : Process);

               Procedure   Remove(P : Process);

        End {TList};

Здесь перечислен минимальный набор методов объекта “список”. При необходимости это набор легко может быть расширен.

Списки процессов используются для организации планирования загрузки процессора.

3.4. Общая характеристика примитивов ЯДРА

Итак, основными объектами ядра являются очереди процессов.

Ядро управляет процессами путем управления очередями.

Управление осуществляется двумя способами:

1.     вызовом диспетчера по прерываниям;

2.     вызовами процедур планировщика ядра.

Эти процедуры называются примитивами ядра. Напомню, что примитивами называются базовые операции некоторого уровня ОС.

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

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

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

Обобщенная структура примитива имеет следующий вид (здесь будем использовать Паскале-подобную запись):

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <Тело примитива>

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End;

Краткая характеристика отдельных частей примитива:

1.     ПРОЛОГ

сохранение контекста активного процесса, который вызывает примитив;

вход в критический участок.

2.     КОНТРОЛЬ

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

3.     ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР - это фрагмент диспетчера, заключающийся в выборе нового активного процесса из очереди готовых процессов и передаче ему управления с выходом из критического участка (ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР - это аналог процедуры Transfer(...)).

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

Procedure Dispatcher; Interrupt;

Begin

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End;

Раскроем понятие КРИТИЧЕСКИЙ УЧАСТОК.

Один пример, относящийся этому понятию, мы уже рассматривали. Это пример с неделимостью примитива join T,W.

Рассмотрим еще один пример.

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

1.     считать ее в свою локальную область;

2.     изменить ее значение;

3.     переслать назад.

Например, N := N + 1; Как это делают процессы:

Р1                                     Р2

mov ax, N              ┌─────────────> mov ax, N

           ────────────┘

add ax, 1                              add ax, 1

mov N, ax                              mov N, ax

Конечная цель - это увеличить N на 2, по 1 от каждого процесса.

Пусть сначала Р1 выполнит все три инструкции, а затем - Р2. Тогда результат будет такой, какой и требуется.

Пусть теперь прерывание и передача управления от Р1 к Р2 произойдет после инструкции mov ax, N.

Тогда Р2 считает в свой регистр ax то же самое значение N, что и Р1, и конечный результат окажется неправильным.

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

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

Разнообразие видов критических ресурсов бесконечно. Например, распределенные базы данных. Узловой проблемой распределенных баз данных является то, что эти базы являются критическим ресурсом.

Переменная Т в операторе join T, W - это критический ресурс.

Участок программы, на котором процесс работает с критическим ресурсом, называется критическим участком.

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

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

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

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

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

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

Какой у них общий ресурс? Это очереди процессов.

Основные примитивы ядра

Классификация примитивов выглядит следующим образом:

Рассмотрим по очереди приведенные классы примитивов.

Примитивы управления процессами

К примитивам управления процессами отнесем два примитива:

1.     примитив создания процесса;

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

3.5. Примитивы создания и уничтожения процессов

Создание процесса

Конкретная реализация примитива зависит от реализации ядра.

Паскале-подобная запись примитива создания процесса может выглядеть следующим образом:

Procedure Создать_Процесс(Var P : Process; Данные);

{Данные - приоритет, точка входа, размер стека и др.}

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Создать дескриптор;

               Заполнить поля дескриптора;

               Ввести процесс в очередь готовых процессов;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Создать_Процесс};

Активный процесс создает новый процесс вызовом:

Создать_Процесс(P, Д);

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

Уничтожение процесса

Для уничтожения процесса логично выполнить действия, обратные созданию процесса:

Procedure Уничтожить_Процесс(P : Process);

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Вывести процесс из очереди, в которой он находится;

               Разрушить дескриптор процесса;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Уничтожить_Процесс};

Такой вид примитива Уничтожить_Процесс допустим, если некоторый выполняющийся процесс Р, хочет уничтожить некоторый процесс Q.

Хотя и здесь есть проблемы, а именно:

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

Поэтому уничтожение процесса должно сопровождаться освобождением ресурсов, выделенных ему.

Может быть по протоколу ядра должны быть уничтожены и процессы-наследники.

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

Т.е. реальный примитив Уничтожить_Процесс может оказаться гораздо сложнее.

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

Предположим, что выполняющийся процесс вызывает примитив Уничтожить_Процесс(Self).

В соответствие с кодом примитива сначала разрушается дескриптор, а затем вызывается примитив ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР.

Т.к. примитиву ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР передаются указатели на дескрипторы процессов: "от кого" и "кому" , а дескриптор "от кого" уже разрушен, то вызов примитива ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР окажется некорректным. Т.е. разрушен дескриптор процесса, который еще выполняется.

Поэтому уничтожение процессов выполняется несколько иначе.

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

2.     Примитив Уничтожить_Процесс в действительности не уничтожает процесс, а переводит его в эту очередь уничтожаемых процессов. Т.е. примитив Уничтожить_Процесс имеет следующий вид:

Procedure Уничтожить_Процесс(P : Process);

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Вывести процесс из очереди, в которой он находится;

               Ввести процесс в очередь уничтожаемых процессов;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Уничтожить_Процесс};

При каждом вызове процедуры Диспетчера осуществляется очистка очереди уничтожаемых процессов с фактическим их уничтожением. Таким образом диспетчер модифицируется следующим образом:

Procedure Dispatcher; Interrupt;

Begin

        ОЧИСТИТЬ_ОЧЕРЕДЬ_УНИЧТОЖАЕМЫХ_ПРОЦЕССОВ;

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End;

Выводы по параграфу 3.5

1.     Процесс-процедура никогда не заканчивает свое выполнение переходом к оператору END, а только вызовом примитива Уничтожить_Процесс.

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

3.6. Примитивы синхронизации процессов

3.6.1. Простейшие примитивы, не учтенные в классификации

Это примитивы Приостановить_Процесс и Возобновить_Процесс. Для описания этих примитивов вспомним 2-й вывод предыдущего параграфа об очередях.

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

Procedure Приостановить_Процесс(P : Process);

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Вывести процесс Р из очереди, в которой он находится;

               Ввести процесс Р в очередь приостановленных процессов;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Приостановить_Процесс};

Procedure Возобновить_Процесс(P : Process);

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Вывести процесс Р из очереди приостановленных процессов;

               Ввести процесс Р в очередь готовых процессов;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Возобновить_Процесс};

Замечания

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

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

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

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

5.      Приведенные примитивы можно рассматривать как первую попытку синхронизации действий нескольких процессов.

3.6.2. Примитивы временной синхронизации

При временной синхронизации ВРЕМЯ выступает в качестве меры длительности явлений. Забегая вперед, скажем, что в других случаях не важна абсолютная длительность явлений, а важны только соотношения РАНЬШЕ/ПОЗЖЕ.

Проблемы временной синхронизации решаются с помощью примитива

Задержать_Процесс(Р : Process; T : Integer)

Здесь Т рассматривается как целое число, т.к. время в машине измеряется количеством "тиков" - интервалов времени между прерываниями от таймера.

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

…                                        …

Delay(T);                                For k := 0 To N Do ;

…                                        …

Вопрос состоит только в выборе подходящего значения N.

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

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

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

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

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

Если процесс ставится в очередь в текущий момент времени Тт, и время, на которое он ставится в очередь, равно Т, то активизировать его надо в текущий момент времени Та = Тн + Т.

На схеме Т = 7.

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

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

Время активизации процесса вычисляется по формуле Та := Тт+Т в момент постановки в очередь задержанных на время процессов и записывается в специальное поле в дескрипторе процесса.

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

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

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

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

Procedure Задержать_Процесс(P : Process; T : Integer);

Begin

        ПРОЛОГ;

        КОНТРОЛЬ;

        <

               Вывести процесс Р из очереди, в которой он находится;

               Ввести процесс Р в очередь задержанных на время процессов;

               Установить поле дескриптора процесса Р в соответствие с

               формулой Та := Тт + Т;

        >

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {Задержать_Процесс};

Procedure АКТИВИЗАЦИЯ_ЗАДЕРЖАННЫХ_НА_ВРЕМЯ_ПРОЦЕССОВ;

Begin

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

               Если Время активизации процесса равно текущему времени, то

               1) Вывести процесс из очереди задержанных на время процессов;

               2) Ввести процесс в очередь готовых процессов;

End {АКТИВИЗАЦИЯ_ЗАДЕРЖАННЫХ_НА_ВРЕМЯ_ПРОЦЕССОВ};

Процедуру АКТИВИЗАЦИЯ_ЗАДЕРЖАННЫХ_НА_ВРЕМЯ_ПРОЦЕССОВ необходимо поместить в Диспетчер:

Procedure Dispatcher; Interrupt;

Begin

        АКТИВИЗАЦИЯ_ЗАДЕРЖАННЫХ_НА_ВРЕМЯ_ПРОЦЕССОВ;

        ОЧИСТИТЬ_ОЧЕРЕДЬ_УНИЧТОЖАЕМЫХ_ПРОЦЕССОВ;

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End;

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

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

Мы уже знаем, что существуют следующие понятия:

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

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

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

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

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

Ожидаем результат:            N = N + S1 + S2;

Можем получить:                N = N + S1; или N = N + S2.

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

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

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

Существуют аппаратные и программные способы решения этой проблемы в зависимости от логического уровня, на котором рассматривается эта проблема.

Дадим их краткий обзор.

1.      Первое средство, которое напрашивается само собой - запрет прерываний на входе критического участка и разрешение прерываний на выходе из него.

P1:                       P2:

cli                       cli

Критический участок;      Критический участок;

sti                       sti

Этот способ имеет следующие недостатки:

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

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

2.     Второй способ. Запрет не всех прерываний, а маскирование прерываний только от таймера.

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

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

3.     Третий способ. Устанавливается флаг занятости ресурса.

Например:

Flag = 0 - ресурс свободен;

Flag = 1 - ресурс занят.

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

При выходе из критического участка процесс устанавливает флаг в состояние 0 (свободен).

                                                      Вариант без метки:

M: If Flag = 1 Then GoTo M;                           While Flag = 1 Do ;

   Flag := 1;

      Критический участок;

   Flag := 0;

Оказывается, что этот способ не снимает проблемы. "Откомпилируем" предыдущий код:

M: cmp Flag,1

   jz M

   mov Flag, 1

       Критический участок;

   mov Flag, 0

Предположим, что Flag = 0 и передача управления происходит сразу же за инструкцией

cmp Flag,1

и второй процесс выполняет инструкцию cmp Flag,1. Для обоих процессов Flag окажется равным нулю и они оба войдут в критический участок.

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

M1 : cli                или    M1 : sti

     cmp Flag,1                     cli

     jnz M2                         cmp Flag,1

     sti                            jz M1

     jmp M1                         mov Flag,1

M2 : mov Flag,1                     sti

     sti                              Критический участок;

        Критический участок;        mov Flag,0

     mov Flag,0

Третий вариант с инструкцией "обменять" - xchg:

    mov  ax,1

 M: xchg ax,Flag

    Cmp  ax,1

    jz   M

       Критический участок;

    mov  Flag,0

Если Flag = 0, то Flag установится в 1, а ax установится в 0, и процесс войдет в критический участок.

Если Flag = 1, то он останется в 1 и ax останется в 1, и процесс перейдет на метку М, т.е. будет ждать установки Flag в 0.

Чтение и установка флага производятся за одну инструкцию, а это - неделимое действие по определению.

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

Вводя в программе префикс LOCK, можно обеспечить блокировку магистрали при выполнении некоторых других инструкций: INC, DEC, ADD, SUB, AND, OR.

Загрузка TSS осуществляется при блокировке магистрали.

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

1.     Способ имеет достоинство, состоящее в том, что критический участок с флагом имеет маленькую и фиксированную длину.

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

3.     Способ не избавляет от "активного ожидания" – цикла опроса флага до его освобождения.

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

Вход;

        Критический участок;

Выход;

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

Семафоры как примитивы ядра и средство синхронизации

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

Так появились двоичный и общий семафор Дейкстры.

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

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

Вход:

Запрет_прерываний;

If Flag = Занят Then Begin

        Встать в очередь;

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {If};

Flag := Занят;

Разрешение_прерываний;

Выход:

Запрет_прерываний;

Flag := Свободен;

If Очередь не пуста Then Begin

        Перевести первый процесс из этой очереди

        в очередь готовых процессов;

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

End {If};

Разрешение_прерываний;

Особенности семафора:

1.     вставая в очередь семафора до освобождения ресурса, процесс разгружает процессор;

2.     на каждый ресурс нужен свой семафор, а значит, своя очередь, поэтому в ядре и много очередей;

3.     семафор - это тоже разделяемый ресурс, а значит действия с ним должны выполняться в режиме взаимного исключения; более того, если рассматривать семафор как примитив ядра, вместо операции Запрет_прерываний необходимо ставить операции ПРОЛОГ, КОНТРОЛЬ.

3.7. Общий семафор как средство событийной синхронизации

Семафор, который был рассмотрен в предыдущем разделе, называется двоичным семафором.

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

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

Дадим формальное объектно-ориентированное описание семафора.

Type

        PSemaphore = ^TSemaphore;

        TSemaphore = Object

               Count : Integer;

               List  : PList;

               Constructor Init;

               Destructor  Done; Virtual;

               Procedure   P;

               Procedure   V;

        End {TSemaphore};

Constructor TSemaphore.Init;

Begin

        Count := 1;

        List  := New(PList, Init);

End {TSemaphore.Init};

Destructor TSemaphore.Done;

Begin

        Dispose(List, Done);

End {TSemaphore.Done};

Procedure TSemaphore.P;

Begin

        Запрет_Прерываний;

        Dec(Count);

        If Count < 0 Then Begin

               List^.Insert(Текущий_процесс);

               ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

        End {If};

        Разрешение_Прерываний;

End {TSemaphore.P};

Procedure TSemaphore.V;

Begin

        Запрет_Прерываний;

        Inc(Count);

        If Count <= 0 Then Begin

               List^.Remove(Первый_процесс);

               Очередь_готовых^.Insert(Текущий_процесс);

               ПЕРЕДАТЬ_УПРАВЛЕНИЕ(Текущий_процесс,Первый_процесс);

        End {If};

        Разрешение_Прерываний;

End {TSemaphore.P};

Var

        Semaphore : PSemaphore;

Begin

        Semaphore := New(PSemaphore, Init);

        ...

        Dispose(Semaphore, Done);

End.

Процесс:

Semaphore^.P;

        Критический участок;

Semaphore^.V;

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

Функционирование семафора

Два класса задач могут быть решены с использованием семафора.

1.     Безразлично, какой из процессов первым подойдет к критическому участку.

Примеры мы рассматривали. Все равно, какой процесс первым инкрементирует переменную N в примере предыдущей лекции.

2.     Небезразлично, какой из процессов первым подойдет к критическому участку.

Пример с обменом данными через ячейку памяти.

Процесс 1:           Процесс 2:

...                  ...

Запись в ЯП;         Чтение из ЯП;

...                  ...

Ясно, что операцию чтения можно проводить только после операции записи.

Рассмотрим сначала первую задачу.

        S := New(PSemaphore,Init);

Процесс 1           Процесс 2             Процесс 3

...                 ...                   ...

S^.P;               S^.P;                 S^.P;

Кр. уч-к;           Кр. уч-к;             Кр. уч-к;

S^.V;               S^.V;                 S^.V;

...                 ...                   ...

        Dispose(S,Done);

Пусть П1 первым подошел к критическому участку. Count = 1.

Dec(Count);           Count = 0;

Входит в критический участок, т.к. условие блокировки Count < 0.

Пусть П2 вторым подошел к критическому участку. Count = 0.

Dec(Count);           Count = -1;

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

Пусть П3 третьим подошел к критическому участку. Count = -1.

Dec(Count);           Count = -2;

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

Теперь П1 выходит из критического участка. Count = -2.

Inc(Count);             Count = -1;

Активизирует процесс П2, как первый в очереди, т.к. выполняется условие активизации

Count <= 0.

Процесс П2 входит в критический участок.

Теперь П2 выходит из критического участка. Count = -1.

Inc(Count);             Count = 0;

Активизирует процесс П3, как первый в очереди, т.к. выполняется условие активизации

Count <= 0.

Процесс П3 входит в критический участок.

Теперь П3 выходит из критического участка. Count = 0.

Inc(Count);             Count = 1;

Активизировать некого и не выполняется условие активизации Count <= 0.

Семафор приходит в исходное состояние.

Свойство семафора: Если Count < 0, то |Сount| равен числу процессов, стоящих в очереди семафора.

Рассмотрим теперь вторую задачу.

Рассматривая вторую задачу, мы подбираемся к изучению методов обмена сообщениями в ядре.

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

Процесс 1                      Процесс 2

...                            ...

Записать в ЯП;                 Если не записано, то ЖДАТЬ;

Сообщить, что записал;         Прочитать из ЯП;

...                            ...

Решим указанную задачу с помощью семафоров.

Инициализируем семафор S в 0, т.е. S^.Count := 0.

П1                             П2

...                            ...

Записать в ЯП;                 S^.P;

S^.V;                          Прочитать из ЯП;

...                            ...

Пусть процесс П1 записал в ЯП данные и первым подошел к выполнению операции S^.V .

Inc(Count);             Count = 1;

Т.к. условие активизации процессов в операции S^.V - Count <= 0, то активизировать некого.

Пусть теперь к выполнению операции S^.P подошел процесс П2.

Dec(Count);           Count = 0;

Т.к. условие блокировки в операции S^.P - Сount < 0, то процесс П2 не блокируется и переходит к чтению ЯП.

Таким образом, чтение произошло после записи.

Пусть теперь первым подошел к выполнению операции S^.P процесс П2.

Dec(Count); Count = -1;

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

Теперь процесс П1 пишет в ЯП и подходит к выполнению операции S^.V.

Inc(Count);             Count = 0;

Т.к. условие активизации Count <= 0 выполняется, то происходит активизация процесса П2 и чтение ЯП.

Таким образом, чтение опять произошло после записи.

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

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

пока процесс П2 не подошел к операции чтения, процесс П1 может выполнить несколько операций записи, возвращаясь к ней в цикле. Т.е. может произойти потеря данных.

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

Следующая схема позволяет это сделать.

П1                               П2

While True Do Begin              While True Do Begin

   ...                              ...

   Запись в ЯП;                     S^.P;

   S^.V;                            Чтение из ЯП;

   A^.P;                            A^.V;

   ...                              ...

End {While};                     End {While};

Первый процесс пишет в ЯП, активизирует П2, если тот уже блокирован в очереди первого семафора, а сам блокируется в очереди второго семафора.

Активизация П1 выполняется процессом П2 после чтения ЯП. Первый семафор используется как подтверждение записи, а второй - как подтверждение чтения.

Последний пример фактически является примером буфера на одну ячейку.

Замечания

1.      Наличие очереди в семафоре - это, вообще говоря, вопрос реализации. Вместо очереди может быть организовано "активное ожидание".

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

Неблокирующие семафорные операции

 

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

При запросе занятого ресурса процесс ставится в очередь и задерживается до тех пор, пока другой процесс не закончит свой критический участок.

Затем процесс исключается из очереди и активизируется, когда ресурс освобождается.

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

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

Тогда возможно поддерживать согласованность данных без использования семафоров.

Такой способ синхронизации называется неявной синхронизацией.

 

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

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

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

               Если читатель читает сообщение и в это время писатель начал писать новую версию сообщения, то читаемое сообщение будет несогласованно и должно быть отброшено.

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

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

               Этот процесс должен сходиться, т.е. число попыток чтения должно быть конечно.

               Протокол требует использования специального управляющего флага CF (Control Flag), работа с которым выполняется в режиме взаимного исключения.

               CF инициализируется значением 0 и инкрементируется писателем перед началом операции записи.

               После завершения операции записи CF опять инкрементируется.

Читатель начинает чтение данных с чтения CF. Если CF нечетное, то читатель повторяет попытку чтения сразу, поскольку ясно, что выполняется операция записи.

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

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

 

Инициализация: CF := 0;
Писатель:	Читатель:
CF_old := CF; CF := CF_old + 1; <пишет в структуру данных> CF := CF_old + 2;	start: CF_begin := CF; If CF_begin = odd Then goto start;             <читает структуру данных> CF_end := CF; If CF_end <> CF_begin Then goto start;

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

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

3.8. Средства синхронизации в существующих операционных средах

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

Рассмотрим примеры семафоров в различных средах.

NOVELL NETWARE

В NetWare существует два класса семафоров - локальные и сетевые.

Для открытия семафора выполняется функция OpenLocalSemaphore(). Эта функция инициализирует счетчик семафора и возвращает ссылку на семафор, которая используется в остальных операциях.

Для закрытия используется функция CloseLocalSemaphore().

Аналог операции P - WaitOnLocalSemaphore(), аналог операции V - SignalLocalSemaphore().

Можно прочитать состояние счетчика семафора функцией ExamineLocalSemaphore().

Функция TimedWaitOnLocalSemaphore() обеспечивает блокировку процесса не только до активизации его операцией SignalLocalSemaphore(), но до истечения таймаута.

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

EnterCritSec() - вход в критическую секцию. Но при вызове этой функции приостанавливаются все нити, даже не связанные с критической секцией.

ExitCritSec() - выход из критической секции.

MICROSOFT 2000, ХР

В Windows существует 4 основных объекта синхронизации - критическая секция, событие, Mutex, семафор.

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

1.      IntializeCriticalSection() - инициализация специальных структур, создаваемых для доступа к критическим секциям.

2.      EnterCriticalSection() - вход в критическую секцию.

3.      LeaveCriticalSection() - выход из критической секции.

4.      DeleteCriticalSection() - удаление структур данных, созданных для доступа к критическим секциям.

Для работы с событиями имеются следующие функции.

1.      CreateEvent() - создание семафора событий.

2.      OpenEvent() - открытие существующего семафора событий.

3.      SetEvent() - сигнализация о наступлении события.

4.      WaitForSingleObject() - ожидание события.

5.      CloseHandle() - закрытие объекта.

Для объекта Mutex существуют следующие операции.

1.      CreateMutex() - создание объекта.

2.      OpenMutex() - получение доступа к ранее созданному объекту.

3.      RequestMutex() - аналог операции P.

4.      ReleaseMutex() - аналог операции V.

5.      CloseHandle() - закрытие объекта.

Семафор - более сложный объект синхронизации. Для работы с ним используются следующие функции.

1.      CreateSemaphore() - создание семафора.

2.      OpenSemaphore() - открытие семафора.

3.      WaitForSingleObject() - ожидание на семафоре.

4.      ReleaseSemaphore() - освобождение семафора.

5.      CloseHandle() - закрытие объекта.

IBM OS/2

В OS/2 имеется три типа семафоров - Mutex – классический семафор; Событие - используется для передачи управляющих сигналов между процессами; MuxWait - средство для ожидания на нескольких семафорах сразу.

Для доступа к критическим участкам используется семафор Mutex.

1.      DosCreateMutexSem() - создание семафора.

2.      DosOpenMutexSem() - открытие семафора.

3.      DosRequestMutexSem() - запрос доступа к критической области.

4.      DosReleaseMutexSem() - освобождение семафора.

5.      DosQueryMutexSem() - проверка состояния семафора.

6.      DosCloseMutexSem() - закрытие семафора.

Для синхронизации событий (запись, чтение) используются семафоры событий.

1.      DosCreateEventSem() - создание семафора события.

2.      DosOpenEventSem() - открытие семафора события.

3.      DosPostEventSem() - сигнализация события.

4.      DosWaitEventSem() - ожидание события.

5.      DosCloseEventSem() - закрытие семафора события.

Для работы с критическими секциями существуют специальные функции.

1.      DosEnterCritSec() - запрещает переключение нитей.

2.      DosExitCritSec() - сигнализация о выходе из критической секции.

NOVELL UNIXWARE

UnixWare также имеет полный набор семафорных операций.

1.      Semget() - создание семафора.

2.      Semop() - используется как для V-операции, так и для P-операции в зависимости от передаваемых параметров.

3.      Semctl() - чтение состояния семафора.

Система Модула-2

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

С переменной S типа SIGNAL могут выполняться следующие операции:

1.      WAIT(S) - ждать сигнала, которая аналогична Р-операции;

2.      SEND(S) - послать сигнал, которая аналогична V-операции.

 

 

3.9. Монитор как средство реализации взаимного исключения

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

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

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

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

Свойства монитора, перечисленные выше, могут быть реализованы как в модуле, так и в объекте. Шаблон модуля, который может рассматриваться как монитор, представлен ниже.

Unit Monitor;

Interface

Procedure M1; {точки входа в монитор}

Procedure M2;

Implementation

Type

Const

 ... {данные, не доступные пользователю}

Var

 ...

Procedure DisableInterrupt; {внутренние процедуры монитора}

Begin

    asm cli end;

End;

Procedure EnableInterrupt;

Begin

    asm sti end;

End;

{внутренних процедур может быть сколько угодно}

Procedure M1; {процедура, связанная с входом в критический}

Begin {участок}

    DisableInterrupt;

    ...

    EnableInterrupt;

End;

Procedure M2; {процедура, связанная с выходом из критического}

Begin {участка}

    DisableInterrupt;

    ...

    EnableInterrupt;

End;

Begin

 {Инициализация данных монитора}

End.

Использование монитора выглядит следующим образом:

Program Example;

Uses Monitor;

Procedure P1;

Begin

    While True Do Begin

        ...

        M1;

        Критический участок;

        M2;

        ...

    End;

End;

Procedure P2;

Begin

    While True Do Begin

        ...

        M1;

        Критический участок;

        M2;

        ...

    End;

End;

Begin

 {Инициализация ядра}

End.

Процедура М1 монитора, анализируя данные, выполняет следующие действия:

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

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

Процедура М2 монитора выполняет следующие действия:

1.      устанавливает необходимые значения данных монитора при выходе из критического участка;

2.      проверяет условия возможной активизации ждущих процессов и активизирует их при выполнении этих условий.

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

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

Реальным примером монитора служат библиотечные модули Модулы-2, которым присвоен приоритет. В Модуле-2 существуют два вида модулей - программные и библиотечные, аналоги Program и Unit в Паскале.

Структура программы на Модуле-2 выглядит следующим образом.

MODULE Name;

IMPORT LIB_MODULE;

...

BEGIN

 ...

END Name.

Библиотечный модуль имеет следующее описание.

DEFINITION MODULE LIB_MODULE; {модуль определений}

Procedure M1; {аналог части INTERFACE }

Procedure M2;

END LIB_MODULE.

IMPLEMENTATION MODULE LIB_MODULE; {модуль реализации}

{реализация всех процедур модуля} {аналог части IMPLEMENTATION}

END LIB_MODULE.

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

Важно, что с библиотечным модулем можно связать ПРИОРИТЕТ. Это делается следующим образом.

IMPLEMENTATION MODULE LIB_MODULE[Pr];

За именем модуля в модуле реализации в квадратных скобках может стоять число. Это число определяет приоритет модуля. Интерпретация приоритета зависит от системы.

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

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

В системе Модула-2 фирмы JPI приоритет модуля трактуется компилятором как маска прерываний. Т.е., если приоритет 1, то маскируется первый вход контроллера прерываний - вход от таймера, если приоритет 2, то маскируются прерывания от клавиатуры, если приоритет 3, то т.к. в двоичном виде это число 11, то маскируются как прерывания от таймера, так и от клавиатуры. Т.е. используется по возможности более тонкий вариант, чем просто запрет прерываний.

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

Указанные задачи относятся к задачам двух типов: 

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

2.      задачи, которые моделируют параллельными вычислительными процессами некоторые реальные ситуации, что соответствует названию дисциплины "Системы реального времени.

К первому классу задач относятся:

1.      задача назначения однородных ресурсов;

2.      задача с процессами "читателями" и "писателями".

Ко второму классу задач относятся:

1.      модель железнодорожного перегона;

2.      модель дорожного перекрестка;

3.      модель обедающих философов;

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

5.      модель функционирования лифта;

6.      модель парикмахерской.

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

Задача назначения однородных ресурсов

Задача назначения однородных ресурсов формулируется следующим образом.

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

Посмотрим, как может выглядеть монитор в этом случае. Опишем его в Паскале-подобной объектно-ориентированной структуре.

Type

    PMonitor = ^TMonitor;

    TMonitor = Object

        N    : Integer; {количество единиц ресурсов}

        Nf   : Integer; {текущее количество свободных ресурсов}

        List : PList; {очередь, в которой процессы ждут ресурсы}

        Constructor Init(AN : Integer);

        Destructor  Done;

        Procedure   Request(R : Integer);

        Procedure   Release;

    End {TMonitor};

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

Использование монитора внешне выглядит следующим образом:

Var

   M : PMonitor;

Begin

    M := New(PMonitor, Init(10));

    ...

    Dispose(M, Done);

End.

Procedure Proc1;

Begin

    While True Do Begin

        ...

        M^.Request(случайное число от 1 до N);

        ...

        M^.Release;

        ...

    End {While};

End {Proc1};

Раскроем содержание методов монитора.

Constructor TMonitor.Init(AN : Integer);

Begin

    N    := AN;

    Nf   := N;

    List := New(PList, Init);

End {TMonitor.Init};

Destructor TMonitor.Done;

Begin

    Dispose(List, Done)

End {TMonitor.Done};

Procedure TMonitor.Request(R : Integer);

Begin

    Запрет_прерываний;

    Записать в дескриптор значение R;

    If R > Nf Then Begin

        List^.Insert(Текущий_процесс);

        ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

    End {If};

    Nf := Nf - R;

    Разрешение_прерываний;

End {TMonitor.Request};

Условие предоставления ресурсов процессу мы записали следующим образом:

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

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

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

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

Как устранить этот недостаток?

Например, усложнить условие блокировки процесса, добавив в него следующее:

If R > Nf ИЛИ Есть процессы в очереди монитора Then Begin

       ...

End {If};

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

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

Аналогичные ситуации могут иметь место при освобождении ресурсов.

Запишем вариант метода TMonitor.Release.

Procedure TMonitor.Release;

Begin

    Запрет_прерываний;

    Nf := Nf + R;

    Перевести в очередь готовых все процессы, для которых сумма

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

    ресурсов, не зависимо от их места в очереди;

    Разрешение_прерываний;

End {TMonitor.Release};

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

Чтобы устранить указанный недостаток, можно правило активизации процессов записать следующим образом:

While очередь не пустая Do Begin

    If первому в очереди процессу хватит свободных ресурсов,

        Then

            перевести этот процесс в очередь готовых процессов

        Else

            Break

End {While};

Т.е. активизацию в любом случае следует начинать с первого процесса.

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

Задача с процессами "читателями" и "писателями"

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

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

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

Type

    PMOnitor = ^TMonitor;

    TMonitor = Object

        Nr, {количество читателей и писателей,}

        Nw : Integer; {работающих с файлом}

        RList : PList;

        WList : PList;

        Constructor Init;

        Destructor  Done;

        Procedure   Enter_R;

        Procedure   Enter_W;

        Procedure   Exit_R;

        Procedure   Exit_W;

    End {TMonitor};

Инициализация данного монитора аналогична инициализации предыдущего монитора.

Procedure Reader;                    Procedure Writer;

Begin                                Begin

     While True Do Begin                  While True Do Begin

         ...                                  ...

         M^.Enter_R;                          M^.Enter_W;

         ...                                  ...

         M^.Exit_R;                           M^.Exit_W;

         ...                                  ...

     End {While};                          End {While};

End {Reader};                        End {Writer};

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

Условие доступа к файлу писателя:

Если файл занят писателем или читателями, то блокировка;

Данное условие формализуется следующим образом:

If Nw > 0 OR Nr > 0 Then ... .

Условие доступа к файлу читателя:

Если файл занят писателем, то {читателей может быть несколько} блокировка;

Данное условие формализуется следующим образом:

If Nw > 0 Then ... .

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

Ограничить доступ читателей к файлу можно, усложнив условие доступа:

Если файл занят писателем ИЛИ есть писатели в очереди, то блокировка;

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

Читатель:

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

Писатель:

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

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

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

3.10. Примитивы ядра для обмена сообщениями

Напомню, что мы классифицировали примитивы ядра на три группы:

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

2.      примитивы синхронизации процессов;

3.      примитивы обмена данными.

Синхронизация и обмен данными вместе называются обобщенно взаимодействием.

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

Обмен данными

─────────────

Синхронизация

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

Обмен данными не может быть реализован без синхронизации.

При этом средства синхронизации "встраиваются" в средства обмена данными таким образом, что они оказываются скрытыми от пользователя.

Пользователю предоставляется пара примитивов типа: SEND, RECEIVE или READ, WRITE.

Обмен данными может рассматриваться в двух аспектах.

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

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

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

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

3.10.1. Буфер как средство коммуникации между процессами

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

Спецификация буфера как средства связи выглядит следующим образом:

1.      сообщения в буфере имеют фиксированный размер;

2.      размер буфера ограничен, буфер - кольцевой;

3.      посылка сообщения в полный буфер недопустима;

4.      чтение сообщения из пустого буфера также недопустима.

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

Type

    PBuffer = ^TBuffer;

    TBuffer = Object

      N   : [0..N]; {текущее количество сообщений в буфере}

      in  : [0..N-1]; {индекс ячейки, в которую производится текущая запись}

      out : [0..N-1]; {индекс ячейки, из которой производится текущее чтение}

      Buf : Array[0..N-1] Of TMessage;

      RList : PList; {очередь процессов, ждущих чтения}

      WList : PList; {очередь процессов, ждущих записи}

      Constructor Init;

      Destructor  Done;

      Procedure   Write(M : TMessage);

      Procedure   Read(Var M : TMessage);

    End {TBuffer};

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

Var

    B : PBuffer;

Begin

    B := New(PBuffer, Init);

    ...

    Dispose(B, Done);

End.

Процесс 1:                            Процесс 2:

Procedure Производитель;                  Procedure Потребитель;

Var                                       Var

    Message : TMessage;                       Message : TMessage;

Begin                                     Begin

    While True Do Begin                       While True Do Begin

        ...                                       ...

        Сформировать(Message);                    B^.Read(Message);

        B^.Write(Message);                        Обработать(Message);

        ...                                       ...

    End {While};                              End {While};

End {Производитель};                      End {Потребитель};

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

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

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

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

Распишем теперь методы монитора БУФЕР.

Constructor TBuffer.Init;

Begin

    N   := 0;

    in  := 0;

    out := 0;

    RList := New(PList, Init);

    WList := New(PList, Init);

End {TBuffer.Init};

Destructor TBuffer.Done;

Begin

    Dispose(RList, Done);

    Dispose(WList, Done);

End {TBuffer.Done};

Procedure TBuffer.Write(M : TMessage);

Begin

    Запрет прерываний;

    If n = N Then Begin {буфер полон}

        WList^.Insert(Текущий процесс); {ждем записи}

        ПЕРЕНАЗНАЧИТЬ ПРОЦЕССОР;

    End {If};

    Inc(n);

    Buf[in] := M;

    in := (in + 1) MOD N;

    If RList не пустая Then Begin {активизация ждущего чтения}

        Очередь_готовых.Insert(Текущий процесс);

        RList^.Remove(Первый процесс);

        Передать управление(Текущий процесс, Первый процесс);

    End {If};

    Разрешение прерываний;

End {TBuffer.Write};

Procedure TBuffer.Read(Var M : TMessage);

Begin

    Запрещение прерываний;

    If n = 0 Then Begin

        RList^.Insert(Текущий процесс); {ждем чтения}

        ПЕРЕНАЗНАЧИТЬ ПРОЦЕССОР;

    End {If};

    Dec(n);

    M   := Buf[out];

    out := (out + 1) MOD N;

    If WList не пустая Then Begin {активизация ждущего записи}

        Очередь_готовых.Insert(Текущий процесс);

        WList^.Remove(Первый процесс);

        Передать управление(Текущий процесс, Первый процесс);

    End {If};

    Разрешение прерываний;

End {TBuffer.Read};

Выводы

1.      Внешне работа с буфером напоминает работу с файлом:

Создать; Записать; Прочитать; Разрушить;

Работа любых средств обмена данными похожа на эти действия.

2.      Две очереди процессов используются в качестве средств синхронизации записи и чтения.

Вместо прямого использования очередей могут использоваться семафоры.

В этом случае нужна пара семафоров, которые имеют смысл "НЕ_ПУСТ" и "НЕ_ПОЛОН".

Когда процесс пишет сообщение в буфер, а он оказывается полным, процесс выполняет операцию НЕ_ПОЛОН.Р.

Если буфер не полон и операция записи прошла успешно, то процесс выполняет операцию НЕ_ПУСТ.V, активизируя читающий процесс, ждущий записи.

Когда процесс читает сообщение из буфера, а он оказывается пустым, процесс выполняет операцию НЕ_ПУСТ.Р.

Если буфер не пуст и операция чтения прошла успешно, то процесс выполняет операцию НЕ_ПОЛОН_V, активизируя пишущий процесс, ждущий чтения.

3.      Недостатками буфера являются:

фиксированный размер;

реальная перезапись данных в буфер и из буфера.

Следующий метод обмена данными устраняет недостатки буфера.

3.10.2. Почтовый ящик с очередью сообщений

Устранения недостатка буфера, заключающегося в фиксированном его размере, устраняется путем использования динамического объекта - очереди сообщений.

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

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

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

Type

    TPostBox = ^TPostBox;

    TPostBox = Object

        TList : PList; {очередь процессов, пославших сообщение}

        RList : PList; {очередь процессов, ждущих сообщения}

        MList : PList; {очередь указателей на сообщения}

        Constructor Init;

        Destructor  Done;

        Procedure   PutMsg(M : Pointer);

        Procedure   GetMsg(Var M : Pointer);

    End {TPostBox};

Замечания

1.      Схема использования почтового ящика в прикладной программе аналогична схеме использования буфера.

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

3.      Процессы, естественно, знают тип сообщений как тип данных.

Сonstructor TPostBox.Init;

Begin

    RList := New(PList, Init);

    TList := New(PList, Init);

    MList := New(PList, Init);

End {TPOstBox.Init};

Destructor TPostBox.Done;

Begin

    Dispose(RList, Done);

    Dispose(TList, Done);

    Dispose(MList, Done);

End {TPostBox.Done};

Procedure TPostBox.PutMsg(M : Pointer);

Begin

    Запрет прерываний;

    MList^.Insert(M);

    TList^.Insert(Текущий процесс);

    If RList не пуста Then

        RList^.Remove(Первый процесс)

    Else

        Очередь_готовых.Remove(Первый процесс);

    Передать управление(Текущий процесс, Первый процесс);

    Разрешение прерываний;

End {TPostBox.PutMsg};

Procedure TPostBox.GetMsg(Var M : Pointer);

Begin

    Запрещение прерываний;

    If MList пуста Then Begin

        RList^.Insert(Текущий процесс); {ждем записи}

        ПЕРЕНАЗНАЧИТЬ ПРОЦЕССОР;

    End {If};

    MList^.Remove(Первое сообщение);

    M := Первое сообщение;

    Tlist^.Remove(Первый процесс);

    Очередь_готовых.Insert(Текущий процесс);

    Передать управление(Текущий процесс, Первый процесс);

    Разрешение прерываний;

End {TPostBox.GetMsg};

Приведенные примитивы работают следующим образом.

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

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

Такой способ обмена сообщениями, когда передающий процесс блокируется, пока его сообщение не будет принято принимающим процессом, называется РАНДЕВУ. Этот механизм реализован в языке АДА.

3.10.3. Средства коммуникаций в существующих ОС

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

1.      Программные каналы.

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

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

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

2.      Сообщения.

Обеспечивают базовые примитивы для приема и передачи данных между процессами.

3.      Семафоры.

Используются для координации доступа между процессами и подробно обсуждены.

4.      Разделяемая память.

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

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

Программные каналы

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

Unix

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

pipe(fileDescriptor[2]).

При создании возвращается дескриптор fd файла для записи и чтения. Запись в fd[0] позволяет считывать данные из fd[1] и наоборот. Операции с каналами осуществляются с помощью обычных команд файловой системы:

read(), getmsg(), write(), putmsg().

Чтобы поток стал именованным, он должен подключиться к узлу файловой системы командой fattach(fileDescriptor, path). Эта команды выполняется на сервере сети. Клиенты выполняют команду open(path) и затем могут связываться друг с другом через данный канал. Отсоединение имени осуществляется командой fdetach(path).

Windows

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

1.      неименованный однонаправленный;

2.      именованный двунаправленный.

CreatePipe(readHandle,writeHandle,security,numBytes) - создается неименованный канал c размером, буфера - numBytes. readHandle, writeHandle - дескрипторы для чтения и записи; security - структура для описания прав доступа.

Для чтения и записи могут использоваться вызовы WriteFile() и ReadFile().

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

ConnectNamedPipe() - ожидание процессом сервером запроса на открытие канала (вызова функции CallNamePipe процессом-клиентом).

DisconnectNamedPipe() - разъединение канала.

PeekNamedPipe() - копирование данных из буфера канала без удаления.

TransactNamePipe() - выполнение операции чтения из канала или записи в канал.

GetNamedPipeHandleState(), GetNamedPipeInfo() – получение информации о канале.

SetNamedPipeHandleState() - изменение параметров канала. 

OS/2

В OS/2 и Windows интерфейсы, использующие именованные программные каналы, практически совпадают.

Встречаются лишь различия в именах, например, CreateNamedPipe в Windows и DOSCreateNPipe в OS/2.

Novell NetWare не имеет механизмов программных каналов.

Очереди сообщений

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

Все платформы, кроме NetWare, имеют механизмы коммуникаций на базе очередей сообщений.

Интерфейсы UnixWare

1.      msgget() - создание очереди сообщений;

2.      msgsnd() - занесение данных в очередь сообщений;

3.      msgrcv() - извлечение сообщений из очереди;

4.      msgctl() - управляющие операции с очередью, например, опрос состояния или удаление.

Интерфейсы Windows

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

CreateMailSlot - создание почтовой ячейки на серверном компьютере.

Клиент получает доступ к ячейке вызовом CreateFile.

GetMailSlotInfo - запрос информации о почтовой ячейке.

SetMailSlotInfo - установка параметров, в основном таймаута.

Интерфейсы OS/2

OS/2 для работы с очередями сообщений на одной ЭВМ предоставляет очень мощный и гибкий интерфейс.

1.      DosCreateQueue - создание очереди в текущем процессе.

2.      DosOpenQueue - получение доступа к уже существующей очереди.

3.      DosPeekQueue - анализ элемента в очереди без изменения ее состояния.

4.      DosPurgeQueue - удаление из очереди всех ее элементов.

5.      DosQueryQueue - запрос числа элементов в очереди.

6.      DosReadQueue - чтение элемента из очереди.

7.      DosWriteQueue - занесение элемента в очередь.

8.      DosCloseQueue - закрытие очереди.

3.11. Проблема тупиков при взаимодействии процессов

Рассмотрим пример.

Есть два процесса Р1 и Р2, два ресурса R1 и R2 и два семафора S1 и S2. Пусть имеют место следующие последовательности выполнения процессов:

P1                                 P2

...                                ...

S1.P; Захват R1;                   S2.P; Захват R2;

...                                ...

S2.P; Ожидание R2;                 S1.P; Ожидание R1;

...                                ...

S2.V;                              S1.V;

...                                ...

S1.V;                              S2.V;

...                             ...

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

Другой пример.

Процесс 1 захватил ресурс, а процесс 2 приостановил процесс 1 и перешел к ожиданию этого же ресурса. Снова оба процесса будут заблокированы на неопределенное время.

Третий пример.

Бесконечное ожидание процесса из-за непродуманных алгоритмов блокировки и активизации процессов. Перечисленные ситуации являются примерами тупиков. Но, строго говоря, к тупикам относят ситуации, похожие на ситуацию первого примера. Т.е. взаимные блокировки процессов при ожидании ресурсов.

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

В системах со статическим распределением ресурсов тупики не возникают.

Динамическое распределение ресурсов способствует возникновению тупиков.

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

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

В общем виде проблема тупиков формулируется следующим образом.

Процесс 1                                                                Процесс 2

Захватил R1;                                                            Захватил R2;

Ждет R2;                                                                  Ждет R1;

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

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

1.      Взаимное исключение - монопольное владение ресурсом. (мы все время добивались обеспечения этого)

2.      Ожидание ресурсов - процессы ждут новых ресурсов, не освобождая уже выделенные.

3.      Неперераспределяемость - процессы сами возвращают ресурсы после использования.

4.      Круговое ожидание - существует кольцевая цепь процессов, от 1 до N, такая что, процесс i захватил ресурс i и ожидает ресурс i+1, занятый процессом i+1.

Существуют два основных направления решения проблемы тупиков.

1.      Предотвращение тупиков, при котором обеспечиваются такие условия функционирования системы, что тупики не возникают вообще.

Это, как правило, обеспечивается за счет нерационального использования ресурсов.

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

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

2.      Обнаружение и исправление.

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

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

Предотвращение тупиков

Методы предотвращения тупиков делятся на:

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

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

Методы априорного предотвращения тупиков

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

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

Требование взаимного исключения остается всегда!

1.      Метод глобального предотвращения снимает условие возникновения тупиков.

Каждый процесс заранее запрашивает все необходимые ресурсы и не запускается до тех пор, пока эти ресурсы не будут ему предоставлены.

Затем, когда процесс выполняется, он уже не ждет ресурсов.

Это очень жесткое требование, которое на практике может исключить вообще всякий параллелизм выполнения процессов.

2.      Нарушение условия неперераспределяемости.

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

Данный способ тоже является чрезвычайно жестким.

3.      Метод упорядоченных ресурсов устраняет условие кругового ожидания.

Ресурсы делятся на классы К1, К2,..., Кк.

Порядок запроса ресурсов всеми процессами определяется классами.

Процесс может запросить и получить ресурс из класса Кi, если он освободил ресурс из класса Кi-1.

Таким образом разрывается цикл кругового ожидания.

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

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

Алгоритм банкира - алгоритм обхода тупиков

Алгоритм банкира предложен Дейкстрой и имитирует работу банка по выдаче займов и приему платежей.

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

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

Если выдача ресурсов может привести систему к тупику, то ресурс не выдается, а процесс переходит в состояние ожидания.

Если тупик возникнуть не может, то ресурс выдается процессу.

Вводятся понятия надежного и ненадежного состояния.

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

Состояние ненадежно, если из него можно оказаться в тупике.

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

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

Пример надежного состояния.

Всего ресурсов - 12. Остаток - 2.

Почему это состояние является надежным?

Предположим, что процесс 1 запросил 2 ресурса.

Дать их ему или нет?

Предположим, что дать.

Тогда ситуация сложится следующим образом. Всего ресурсов - 12. Остаток - 0.

2)

Каждый из процессов еще может запросить ресурсы по своему протоколу, а свободных ресурсов нет в наличии. Это может привести к тупиковой ситуации. Поэтому запрос процесса 1 на 2 ресурса будет отложен. Предположим, что процесс 2 запросил 2 ресурса. Дать их ему или нет?

Условие функционирования процессов следующее. После получения максимального количества ресурсов они все ресурсы отдают системе и завершают свою работу. Это означает, что получив 6 ресурсов, процесс 2 успешно завершится и вернет их системе. Свободных ресурсов будет 6 и их хватит процессам 1 и 3, чтобы завершить работу. Т.е. все три процесса могут успешно завершить работу. Поэтому такое состояние является надежным.

Пример ненадежного состояния.

Всего ресурсов - 12. Остаток - 1.

3)

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

Отметим, что это не обязательно тупик. Это – опасность возникновения тупика при определенном варианте появления запросов.

Таблица 2 - тоже пример ненадежного состояния.

Очевидно, что из надежного состояния можно попасть в ненадежное, если раздавать ресурсы беспорядочно.

Например, при первой таблице удовлетворить запрос процесса 1 на 2 ресурса.

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

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

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

Если в прогнозе на определенном этапе выявляется ненадежное состояние, т.е. появляются процессы, которые не смогут завершиться, то запрос откладывается, а процесс блокируется.

Если в прогнозе все процессы смогут завершиться, то запрос удовлетворяется.

Замечания по алгоритму банкира

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

2.      Алгоритм обладает рядом ограничений:

1.    алгоритм исходит из фиксированного количества ресурсов, хотя на самом деле оно может меняться;

2.    алгоритм исходит из фиксированного количества процессов, хотя оно тоже может меняться на самом деле;

3.    алгоритм требует возвращения ресурсов процессами в конечное, но не определенное, время;

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

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

6.    сам просчет надежности состояния приводит к затратам времени.

Алгоритм Габермана обхода тупиков

Алгоритм Габермана отличается от алгоритма банкира исходными условиями функционирования процессов.

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

Данные условия представляются в виде следующей матрицы:

Процессы        Ресурсы

                A B C D E

Р1              1 1

Р2              1 1 1

Р3                1 1 1

Р4                  1 1 1

При каждом запросе ресурса строится граф следующего вида:

Вершины - процессы;

Дуга jk между вершинами j и k существует, если процесс j использует ресурс, который может запросить процесс k.

Например, Р4 использует ресурс С:

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

Обнаружение тупиков

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

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

Стратегии распознавания тупиков основаны на моделировании развития каждого незаблокированного процесса.

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

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

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

Если таковые остались, то система находится в состоянии тупика.

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

Завершение работы процесса и возвращение всех ресурсов системе эквивалентно тому, что вершина процесса становится изолированной.

Такая операция называется редукцией графа на процесс.

Если граф можно редуцировать на все процессы, то это означает, что тупиковой ситуации нет.

А если остались нередуцированные процессы, то они и составляют группу процессов, вовлеченных в тупик.

Для обнаружения тупика может быть использован алгоритм банкира.

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

Заметим, что оба метода - редуцирование графа состояний системы и алгоритм банкира - это одно и то же.

Различие состоит в форме представления состояния системы.

Восстановление после тупиков 

Самый эффективный способ восстановления после тупиков – это использование механизмов приостановки/возобновления процессов.

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

Перечислим методы восстановления по степени уменьшения их "грубости".

1.    Перезапуск всех процессов - перезагрузка.

2.    Принудительное завершение процессов, находящихся в тупике.

3.    Принудительное завершение процессов, находящихся в тупике, но - по одному. Возможно, на определенном этапе тупик рассосется.

4.    Перезапуск процессов с контрольных точек.

5.    Нормальное завершение незаблокированных процессов.

3.12. Планирование загрузки процессора в ядре

3.12.1. Классификация алгоритмов планирования

Каждому процессу необходимы вычислительные ресурсы и ресурсы данных для выполнения.

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

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

 

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

 

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

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

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

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

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

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

               Классификацию алгоритмов планирования дает следующая диаграмма:

                    Алгоритмы планирования

 

 

      Динамические                       Статические

 

 

Вытесняющие   Невытесняющие       Вытесняющие       Невытесняющие

 

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

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

При этом затраты ресурсов (времени) на принятие решений могут быть существенными.

 

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

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

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

 

 

 

Например, максимальные времена выполнения, ограничения предшествования, ограничения взаимного исключения и предельные задержки.

 

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

Затраты времени на выполнение такого диспетчера малы по сравнению с динамическим планировщиком.

 

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

 

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

 

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

               Например, Unix, Windows и OS/2 относятся к классу систем с вытеснением, поэтому алгоритмы планирования в них сложны и включают в себя сложную логику и большое число инструкций.

               Novell NetWare 3 и 4 являются ОС без вытеснения и поэтому имеют значительно более быстрые алгоритмы планирования. Но для переключения задач сам разработчик должен включать в задачи вызов ThreadSwitch(), обеспечивающий явное переключение задач.

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

1.      после каждого прерывания перепрограммировать таймер на новый интервал времени до следующего прерывания;

2.      делать переключение на другие задачи не после каждого прерывания.

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

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

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

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

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

 

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

 

 

(децентрализованное) планирование. Такая классификация может относиться к распределенным вычислительным системам.

 

В распределенной системе можно принимать планирующие решения:

 

1. или в одном центральном узле
2. или создавать какие-то совместные (распределенные) алгоритмы для решения проблемы планирования.

 

Централизованный планировщик в распределенной системе – это место, критичное с точки зрения сбоев.

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

 

3.12.2. Тесты планируемости задач и классификация задач

 

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

 

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

 

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

 

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

 

            Эти свойства отображаются следующей диаграммой:

	Если достаточный тест планируемости положительный, эти задачи определенно планируемы							Если необходимый тест планируемости отрицательный, эти задачи определенно непланируемы

 

 

 

 

 

 

 

 

 

                                                                                                                             Возрастающая сложность множества задач

 

Классификация задач с точки зрения планируемости

 

            Задачи делятся на периодические, спорадические и апериодические.

 

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

 

            Обозначим через pi период i-й задачи, через ci – время выполнения i-й задачи. Тогда необходимый тест планируемости формулируется следующим образом:

 

 

 

 

Множество периодических задач планируемо, если

 

m = S mi = S ci/pi <= 1

 

            Отношение mi = ci/pi называется фактором полезности i-й задачи и обозначает долю времени, которую i-я задача требует сервиса от процессора.

 

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

 

1. di – предельный интервал завершения – разность между предельным сроком завершения и временем запроса;

 

2. li – неопределенность задачи – разность между di и ci.

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

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

 

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

 

            Для решения проблемы планирования чрезвычайно важно знание будущего поведения задач.

            Если планировщик не имеет сведений о будущих моментах запросов спорадической задачи, то проблема планирования не разрешима.

            Т.е. для разрешения проблемы планирования должны быть сделаны предположения о будущих моментах запросов.

 

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

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

 

 

            Рассмотрим пример работы идеального планировщика.

 

	Т1: c=2, d=4, p=4. периодическая Т2: с=1, d=1, p=4, спорадическая Т1 и Т2 взаимно исключающие   Идеальный планировщик сдвигает задачу Т1

 

Т2

Т2

Конфликт                                                  Конфликт

	Т1

 

 

 

 

 

 

 

 

      0             1         2          3         4          5         6          7          8            t

 

 

 

Рассмотрим две задачи с взаимным исключением, задачу Т1 периодическую и другую задачу Т2 спорадическую, с параметрами данными на рисунке. Необходимый тест планируемости, введенный выше, удовлетворяется с запасом, поскольку

 

2/4 + 1/4 = 3/4 < 1.

Всякий раз, когда выполняется периодическая задача, запрашивает сервис спорадическая задача.

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

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

 

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

 

3.12.3. Динамическое планирование

 

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

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

 

3.11.3.1. Планирование независимых задач

 

Алгоритмы без использования приоритетов

1.      Планирование по принципу FIFO. Это простейшая дисциплина обслуживания без вытеснения.

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

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

2.      Циклическое или круговое планирование (RR – round robin).

Сочетание принципа FIFO с time-sharing-ом.

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

      Такой вариант планирования может использоваться и без time-sharing-га.

      В этом случае процесс снимается с процессора и ставится в конец очереди при обращении к примитивам ядра или при добровольной передаче управления.

      Так реализовано планирование в NetWare 3 и оно очень эффективно.

               Такая дисциплина может быть использована с интерактивными процессами.

3.      Многоуровневое планирование.

Процесс входит в сеть очередей с самого верхнего уровня.

Перемещается по очереди, пока не достигнет процессора.

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

И т.д.

На самом низу - циклическое обслуживание до завершения.

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

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

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

И количество таких циклов растет с переходом на более низкие уровни.

Многоуровневые очереди - идеальный механизм планирования.

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

Алгоритмы приоритетного планирования

 

1. Алгоритм монотонной скорости.

 

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

 

Алгоритм монотонной скорости – это динамический вытесняющий алгоритм, основанный на статических приоритетах задач.

 

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

    1.   Запросы всех задач периодические.

 

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

 

    3.   Предельный интервал завершения di каждой задачи Тi равен ее периоду рi.

 

    4.   Длительность каждой задачи сi известна априори и постоянна.

 

    5.   Временем, требуемым для переключения контекста, можно пренебречь.

 

    6.   Сумма m факторов mi полезности n задач определяется:

 

m = S mi = S ci/pi <= n(2^1/n - 1).

 

Выражение n(2^1/n - 1) близко к ln2, т.е. около 0.7, когда n стремится к бесконечности.

 

Алгоритм монотонной скорости назначает задачам статические приоритеты, основанные на периодах.

Задача с кратчайшим периодом получает высочайший статический приоритет, а задача с длиннейшим периодом получает наименьший статический приоритет.

Во время выполнения диспетчер выбирает запрос задачи с высочайшим статическим приоритетом.

 

Если все предположения выполнены, то алгоритм монотонной скорости гарантирует, что все задачи завершатся в свой предельный срок завершения.

Алгоритм оптимален для однопроцессорной системы.

Доказательство этого алгоритма основано на анализе поведения множества задач в критический момент.

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

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

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

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

 

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

 

 

 

В этом случае фактор m полезности n задач:

 

m = S ci/pi <= 1,

 

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

 

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

 

2. Алгоритм “задача с минимальным предельным сроком завершения - первая”

 

Динамический вытесняющий алгоритм для однопроцессорных систем, который основан на динамических приоритетах.

Должны выполняться предположения с (1) по (5) алгоритма монотонной скорости.

Полезность m может подняться до 1, даже когда периоды задач не кратны наименьшему периоду.

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

 

У этого алгоритма есть недостатки:

 

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

2.      не всегда самые короткие задания являются самыми важными.

3. Алгоритм минимальной неопределенности

 

Этот алгоритм также ориентирован на однопроцессорные системы.

Он использует те же самые (1) – (5) предположения.

В любой момент планирующего решения, задаче с минимальной неопределенностью l, т.е. разностью между предельным интервалом завершения d и временем выполнения c

 

d – c = l

 

назначается высочайший динамический приоритет.

 

Т.о. существуют алгоритмы планирования, которые дают высочайший приоритет задаче, у которой минимален определенный параметр:

 

1. d – предельный срок завершения (EDF - earliest deadline);
2. l – неопределенность (LL - least laxity) (минимальной неопределенности);
3. c – длительность (SJF – shortest job) (кратчайшее задание - первым);
4. d – t – срок, оставшийся до завершения (t- текущее время) (SRT – shortest remaining time) (задача с кратчайшим сроком завершения – первая)

 

 

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

При этом, существуют системы как со статическими приоритетами (алгоритм монотонной скорости), так и с динамическими приоритетами (все остальные).

 

Системы со статическими и динамическими приоритетами характеризуются следующими особенностями:

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

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

Вот пример планирования с динамическими приоритетами, вычисляемыми по формуле:

            Время ожидания + Время выполнения

Приоритет = ───────────────────────────────────

                    Время выполнения

Уменьшает недостатки варианта планирования SJF.

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

Т.к. время ожидания есть в числителе, то приоритет задачи растет, если она более длительная и долгое время ждет.

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

3.12.3.2. Планирование зависимых задач

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

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

Таким образом, наличие ограничений предшествования и взаимного исключения скорее являются нормой, чем исключением.

 

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

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

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

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

Существуют следующие пути выхода из этого трудного положения:

 

    1.   Использование мощных вычислительных ресурсов (например, многопроцессорность).

 

    2.   Деление проблемы планирования на две части.
Одна часть может быть решена неоперативно (до выполнения),
а вторая часть должна решаться во время выполнения.

 

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

 

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

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

Kernelized Monitor (монитор в роли ядра)

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

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

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

Пример иллюстрирует проблемы этого алгоритма.

Пример.

               Представим две задачи, Т1 и Т2 с параметрами, данными на рисунке.

               Вторая часть Т2 - Т22 относительно Т1 должна выполняться в режиме взаимного исключения.

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

               EDF-планировщик будет планировать задачи в соответствие с рисунком.

               В момент 4 единственная задача, которая сделала запрос на выполнение, это Т22, так что EDF планировщик спланирует Т22, которая не может быть вытеснена Т1 в течение следующих двух единиц времени.

               В момент 5 происходит конфликт, Т22 еще не закончилась, а Т1, которая строго периодическая и находится относительно Т22 в режиме взаимного исключения, должна быть выполнена немедленно, поскольку она имеет нулевую задержку.

			EDF-планировщик

 

                                    Т21            Т22

 

                    Т1       Конфликт                  Т1

 

          0        1       2        3       4        5        6       7        8        9       Время

 

  

 
 

  

  

  

   

    

    

    
Т1: с = 2, d = 2, p = 5, периодическая
    
Т2: c21 = 2, c22 = 2, d = 10, p = 10, периодическая
    
Т22 и Т1 - взаимное исключение
    
    
   
  
   
 


 

Более тонкий планирующий алгоритм мог бы решить эту проблему, конструируя план, показанный ниже.

Критической секции второй задачи, задаче Т22, не разрешается начаться в течение двух временных квантов перед вторым выполнением Т1.

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

 

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

Все запрещенные области должны быть определены и переданы диспетчеру заранее.

Так что диспетчер не будет планировать нежелательные критические секции в запрещенной области.

 

                                     Т21                                          Т22

 

                   Т1                                            Т1

 

          0        1       2        3       4        5        6       7        8       9      Время

 

                                                                                              Запрещенная область

 

Priority Ceiling Protocol (Протокол предельного приоритета)

 

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

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

 

            Известно явление, называемое инверсией приоритета.

            На примере его можно иллюстрировать следующим образом.

Есть 3 задачи Т1, Т2 и Т3 (Т1 имеет высший приоритет, а Т3 имеет низший приоритет), которые планируются алгоритмом монотонной скорости.

Т1 и Т3 требуют исключительного доступа к общему ресурсу, защищенному семафором С.

 

 

 

Пусть в какой-то момент времени низкоприоритетная задача Т3 владеет критическим ресурсом.

Пусть в этот момент высокоприоритетная задача Т1 запрашивает сервис.

Т1 должна ждать, пока Т3 не пройдет свой критический участок и не освободит семафор С.

 

Если в течение этого времени сервис запрашивает задача Т2, то он будет ей отдан, поскольку Т2 имеет более высокий приоритет, чем Т3.

 

Таким образом задача Т2 со средним приоритетом задерживает задачу Т3 и, следовательно, задачу Т1, задачу с высоким приоритетом.

Такое явление и называется инверсией приоритета.

 

Было предложено поднять приоритет низкоприоритетной задачи Т3, пока она находится в критической секции, до высокого приоритета блокированной задачи Т1, и следовательно, устранить возможность того, что среднеприоритетная задача Т2 вмешается в течение критической секции низкоприоритетной задачи.

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

Чтобы решить эти проблемы и был разработан протокол предельного приоритета.

 

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

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

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

Если она блокирует задачи, то она наследует приоритет самой высокоприоритетной задачи, которую она блокирует.

Когда она выходит из критической секции, она восстанавливает приоритет, который она имела в момент входа в критическую секцию.

 

Следующий пример иллюстрирует работу протокола предельного приоритета.

Система состоит из 3-х задач, Т1 (высший приоритет), Т2 (средний приоритет) и Т3 (низший приоритет) конкурируют за три критических ресурса, защищенных семафорами С1, С2 и С3.

Последователь-ность команд, выполняемая задачами	Т1:	…,Р(С1),…,V(C1),…,P(C2),…,V(C2),…	Высший приоритет
	Т2:	…,Р(С3),…,V(C3),…	Средний приоритет
	Т3:	…,Р(С3),…,P(C2),…,V(C2),…,V(C3),…	Низший приоритет

Т1

 

Т2

 

Т3

 

 

           1   2    3    4    5  6    7     8       9   10   11    12     13     14        15     16 Время

 

Критическая секция, защищенная:

                                                      С1 (высокий) С2 (высокий) С3 (средний)

 

 

Со-бы-тие	Действие
1	Т3 начинает выполнение
2	Т3 захватывает С3
3	Т2 начинается и вытесняет Т3
4	Т2 становится блокированной, когда пытается захватить С3, захваченный Т3. Т3 возобновляет выполнение своей критической секции при наследуемом приоритете Т2
5	Т3 позволено войти в свой вложенный критический участок, захватывая С2
6	Т1 инициируется и вытесняет Т3. Это возможно, поскольку Т1 имеет более высокий приоритет, чем наследованный приоритет Т3
7	Т1 блокируется, когда пытается захватить С1, поскольку приоритет Т1 не выше, чем предельный приоритет захваченного семафора С2. Т3 возобновляет свое выполнение с приоритетом задачи Т1.
8	Т3 освобождает С2 и получает назначенный приоритет назад. Т1 пробуждается и вытесняет Т3. Теперь Т1 может захватить С1, поскольку С2 освобожден.
9	Т1 освобождает С1
10	Т1 захватывает С2
11	Т1 освобождает С2
12	Т1 завершается. Т3 возобновляет свои действия с наследуемым приоритетом Т2
13	Т3 освобождает С3 и возвращается к назначенному приоритету. Т2 вытесняет Т3 и захватывает С3
14	Т2 освобождает С3
15	Т2 завершается. Т3 возобновляет свои действия
16	Т3 завершается

 

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

            Достаточный тест выглядит следующим образом:

Множество n периодических задач {Ti} может быть планируемо, если следующее множество неравенств выдерживается:

 

"i, 1 <= i <= n: (c1/p1 + c2/p2 + … + ci/pi + Bi/pi) <= i(2^1/i - 1)

 

Здесь Bi – это максимальное время блокировки задачи Ti задачами более низкого приоритета.

Эффект вытеснений задачи Ti более высокоприоритетными задачами рассматривается в первых i слагаемых (по аналогии с алгоритмом монотонной скорости).

Наихудший случай блокирования из-за всех задач более низкого приоритета представлен в выражении Bi/pi.

Выражение Bi/pi может стать очень значительным, если задача с малым периодом (т.е. малым pi), блокируется на значительное время.

 

Замечания по динамическому планированию в распределенных системах

 

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

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

Работы ведутся только путем расширения алгоритма монотонной скорости на распределенные системы.

 

 

 

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

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

 

3.12.4. Статическое  планирование

 

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

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

Конструирование такого плана может рассматриваться как поиск теста планируемости.

 

 

Отношения предшествования между задачами часто представляют в виде графа предшествования.

            Пример графа предшествования для пары узлов распределенной системы представлен на рисунке.

 

                               Стимул

 

                                                                                       Узел В

 

                                                    Сообщения

 

                                                         М1

 

                                                         М2

 

                       Узел А

 

                                                                                                Отклик

 

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

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

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

 

Статический план – это периодический план.

Существует только одно прерывание в системе - периодическое прерывание от таймера.

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

Каждая транзакция выполняется периодически.

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

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

 

 

 

 

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

 

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

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

 

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

Для этого применяют стратегии поиска.

Пример простого дерева поиска для предыдущего графа представлен на рисунке.

Каждый уровень дерева поиска соответствует одной единице времени.

Глубина дерева поиска соответствует периоду плана.

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

Ветви указывают на возможные альтернативы, которые существуют в узлах.

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

Цель поиска – найти полный план, который обеспечивает все ограничения предшествования, взаимного исключения и предельные сроки завершения.

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

 

1                                                             Т0

2                                  Т1                                                           Т2

3                                  Т2                                                       М1&T1

4                             M1&T3                                                    T3&T4

5                             M2&T4                                                   M2&T6

6                T5                              T6                                           T5

7                T6                              T5                                           T7

8                T7                              T7

 

Поиск пути ведется с помощью некоторого критерия.

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

В качестве стоимости часто выступает время.

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

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

 

Повышение гибкости статических планов

 

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

Хотя обычно большинство задач это периодические задачи, существуют также и спорадические запросы на обслуживание, которые имеют жесткие требования к предельному сроку завершения.

Пример такого запроса – какая-нибудь авария.

Это редкое событие, но если оно произошло, то должно быть обслужено в очень короткий интервал времени.

 

 

Существуют следующие методы повышения гибкости статического планирования:

 

1.      Трансформация спорадических запросов в периодические запросы.

2.      Введение периодической серверной задачи.

3.      Изменение режима.

 

Трансформация спорадических запросов в периодические запросы

 

Моменты времени запросов периодической задачи известны заранее.

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

Фактические моменты времени, когда спорадическая задача запрашивает сервис, не известны до самого запроса.

Эта ограниченная информация затрудняет статическое планирование спорадических запросов.

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

 

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

 

Периодическая серверная задача

 

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

Пока запроса нет, приоритет этой задачи-сервера растет.

Когда появляется спорадический запрос, для его обслуживания динамически планируется периодическая задача-сервер.

Из-за ее высокого приоритета она сразу запускается на выполнение.

После выполнения запроса ее приоритет резко падает и она практически не участвует в борьбе за процессор.

 

Изменения режима

 

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

 

Таковы, например, фазы полета самолета.

1. Выруливание на земле.
2. Взлет.
3. Набор высоты.
4. Устойчивый полет на высоте.
5. Снижение высоты.
6. Посадка.
7. Выруливание на земле.

 

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

Поэтому есть смысл не планировать выполнение всех процессов в одном плане с учетом того, что некоторые процессы не активны в некоторые интервалы времени.

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

 

 

Каждый из подпланов создается статическими методами.

 

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

 

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

 

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

 

 

 

3.11.5 Приоритеты в существующих ОС

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

Например, в Unix используется три класса приоритетов:

1.     реального времени;

2.     системный;

3.     разделения времени.

Внутри каждого класса приоритеты также могут меняться. Все приоритеты конфигурируются.

В Windows (имеется в виду NT и ее последователи 2000, ХР) имеется шесть классов приоритетов для процессов:

1.       IDLE_PRIORITY_CLASS

2.       BELOW_NORMAL_PRIORITY_CLASS

3.       NORMAL_PRIORITY_CLASS

4.       ABOVE_NORMAL_PRIORITY_CLASS

5.       HIGH_PRIORITY_CLASS

6.       REALTIME_PRIORITY_CLASS

Также есть градации внутри классов для потоков процесса.

1.       THREAD_PRIORITY_IDLE

2.       THREAD_PRIORITY_LOWEST

3.       THREAD_PRIORITY_BELOW_NORMAL

4.       THREAD_PRIORITY_NORMAL

5.       THREAD_PRIORITY_ABOVE_NORMAL

6.       THREAD_PRIORITY_HIGHEST

7.       THREAD_PRIORITY_TIME_CRITICAL

Всего вариантов приоритетов от 0 до 31.

В OS/2 имеется 4 уровня приоритета:

1.     критические по времени;

2.     с фиксированным высоким приоритетом;

3.     обычные;

4.     бездействующие.

Каждый класс имеет 32 градации, от 0 до 31.

B NetWare имеется схема приоритетов с 6 уровнями:

1.     прерывания;

2.     рабочие нити;

3.     нити;

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

5.     перманентно приостановленные нити - регулируются системой для предотвращения перегрузки;

6.     нити с низшим приоритетом.

Заключение по разделу 3

В разделе 3 рассмотрены вопросы параллельного выполнения программ.

1.      Введено понятие ПРОЦЕСС как модель выполнения программы, независимая от техники переключения контекстов.

2.      Введено понятие ЯДРА, как средства организации процессов.

3.      Рассмотрены примитивы ядра для создания/уничтожения процессов, синхронизации процессов и обмена данными между процессами.

4.      Рассмотрены причины и методы устранения тупиковых ситуаций, возникающих при доступе процессов к совместно разделяемым ресурсам.

5.      Рассмотрены проблемы планирования процессов в ядре.