Конспект лекций по дисциплине " Операционные системы"

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

Конспект

Содержание Микроядерная архитектура Преимущества микроядерной архитектуры Недостатки микроядерной архитектуры Дополнительная литература Пространство состояний Функция действия P имеющий две переменные x Реализация процессов. Другой путь Общение между процессами. Синхронизация процессов. Синхронизация с помощью элементарных приемов нижнего уровня. Begin Переключатель_1:=False; Переключатель_2:=False; parbegin Алгоритм Деккера Проверка и установка. Алгоритм проверки и установки V(S), S увеличивается на единицу и Если S>0 S=0 –один процесс находится в своем критическом участке. Если S=-1 Заполн := 0 S становится отрицательным, это значит, что очереди, связанной с S ... Полное содержание

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

• Конспект лекций по дисциплине «Операционные системы и среды», 618.94kb.
• Методические указания для выполнения Курсовой работы по дисциплине «Операционные системы», 72.86kb.
• Программа по дисциплине «Технологии программирования и операционные системы», 42.87kb.
• Ые системы", "Операционные системы, среды и оболочки" и "Операционные системы и системное, 1294.27kb.
• Конспект лекций по дисциплине «Маркетинг», 487.79kb.
• Конспект лекций по дисциплине «Информационные системы в экономике», 1286.5kb.
• Рабочая программа По дисциплине «Операционные системы» По специальности 230102., 376.29kb.
• В. Ф. Панин Конспект лекций по учебной дисциплине "Теоретические основы защиты окружающей, 1559.17kb.
• Рабочая программа по учебной дисциплине Операционные системы, среды и оболочки наименование, 623.3kb.
• Тема лекции «Многозадачные многопользовательские операционные системы. Операционные, 154.91kb.

Микроядерная архитектура

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

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





В состав микроядра входят

1. Машинно-зависимые модули;
   
2. Модули, выполняющие основные базовые функции ядра по управлению процессами;
   
3. Обработка прерываний;
   
4. Управлению виртуальной памятью;
   
5. Пересылка сообщений и управление вводом-выводом
   

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

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

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

Преимущества микроядерной архитектуры

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

Недостатки микроядерной архитектуры

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

Вывод:

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

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

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

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

Микроядерную концепцию используют такие ОС, как Windows NT и некоторые версии ОС UNIX.


Дополнительная литература:

Андрей Рабаневский “Операционная система UNIX” Спб.: БХВ – Санкт-Петербург, 1999.

Процессы.

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

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

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

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

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

Понятие процесса – формализация идеи “независимой работы”.

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

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

Эти параллельно выполняемые задания вообще не должны учитывать существование друг друга. Когда какое либо задание отдает приказ “печатать”, его не касается то, что другое в это время осуществляет запись на диск и т.д.

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

Пусть задан процесс P имеющий две переменные x и y. Работу процесса Р можно описать последовательностью состояний: .

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

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

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

В ряде ОС кроме понятия процесс выделяется еще более мелкая единица, которая называется поток.

В чем же разница?

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

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

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


Реализация процессов.

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

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

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

Очень важно различать абстрактный и программный процессы.

Программный процесс – это и абстрактный процесс, а обратное не всегда верно.

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

Есть два подхода к образованию программных процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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




У такой структурированной системы есть преимущества:

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

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


Общение между процессами.

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

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

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

Для снижения потерь из-за неэффективного использования программного оборудования можно также и здесь воспользоваться разделением.

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

Заметим, что у аппаратных и программных ресурсов есть общие свойства.

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

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

Физические устройства называются физическими или естественными ресурсами.

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

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

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


Синхронизация процессов.

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

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

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

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

Рассмотрим два независимых процесса:


parbegin

Процесс_1: do while (true)

begin

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

end;

Оставшаяся часть процесса 1;

end;

Процесс_2: do while (true)

begin

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

end;

Оставшаяся часть процесса 2;

end;


Конструкция вида:

parbegin

Оператор 1;

Оператор 1;

...

Оператор 1;

parend.


Означает, что операторы 1N выполняются параллельно.

Кстати, записи, приведенные выше, называются записями на псевдокоде.

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

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

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

У процессов возникает не только проблема синхронизации, но и необходимость в обмене информацией.

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

Эти порции информации можно рассматривать как сообщения.

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

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

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

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

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

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

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

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

Остановимся на решении проблем синхронизации и отношений типа “Поставщик – Потребитель”.


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

1. Блокировка памяти.
   

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

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

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

Казалось бы, ничего проще нет, как предложить следующее решение:

Boolean : Переключатель_1, Переключатель_2;

Begin

Переключатель_1:=False;

Переключатель_2:=False;

parbegin

Процесс_1: do while (True);

Цикл_1: do while (Переключатель_2);

end;

Переключатель_1:=True;

/* Критический участок 1 */

Переключатель_1:=False;

/* Оставшаяся часть процесса 1*/

end;

Процесс_2: do while (True);

Цикл_2: do while (Переключатель_1);

end;

Переключатель_2:=True;

/* Критический участок 2 */

Переключатель_2:=False;

/* Оставшаяся часть процесса 2*/

end;

parend;

End.


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

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

Мы же приведем вариант решения, предложенного Деккером.

Алгоритм Деккера:

integer: C1,C2,Очередь;

begin

C1:=0;

C2:=0;

Очередь:=1;

parbegin

Процесс_1: begin C1:=1;

do while (C2=1);

if Очередь=2 then

begin

C1:=0;

do while (Очередь=2);

end;

C1:=1;

end;

end;

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

C1:=0;

Очередь:=2;

Оставшаяся часть Процесса 1;

end;

Процесс_2: begin C2:=1;

do while (C1=1);

if Очередь=1 then

begin

C2:=0;

do while (Очередь=1);

end;

C2:=1;

end;

end;

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

C2:=0;

Очередь:=1;

Оставшаяся часть Процесса 2;

end;

parend;

end.


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

2. Проверка и установка.
   

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

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

Главное свойство этой операции – ее неделимость. Когда процесс выполняет операцию “проверка и установка” никаких действий не может произойти между ее началом и концом.

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

Если “общий” = 1, это значит, что какой-то процесс находится в своем критическом участке. Начальное значение переменной “общий” = 0.

Приведем решение проблемы методом “проверка и установка”. В этом решени предпологается, что в машине предусмотрена блокировка памяти, т.е. операция “общий” := 0 неделима.


Алгоритм проверки и установки:

integer: ОБЩИЙ;

begin

ОБЩИЙ:=0;

parbegin

integer: ЛОКАЛЬНЫЙ1;

Процесс_1: begin do while (True);

ЛОКАЛЬНЫЙ1:=1;

do while (ЛОКАЛЬНЫЙ1=1)

Проверка и установка(ЛОКАЛЬНЫЙ1,ОБЩИЙ)

end;

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

ОБЩИЙ:=0;

Оставшаяся часть Процесса 1;

end;

end;

integer: ЛОКАЛЬНЫЙ2;

Процесс_2: begin do while (True);

ЛОКАЛЬНЫЙ2:=1;

do while (ЛОКАЛЬНЫЙ2=1)

Проверка и установка(ЛОКАЛЬНЫЙ2,ОБЩИЙ)

end;

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

ОБЩИЙ:=0;

Оставшаяся часть Процесса 2;

end;

end;


parend;

end.


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

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

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

3. Семафоры.
   

Семафор – целая переменная, значения которой могут менять только операции P и V. Пусть S – семафор. Когда процесс выполняет операцию P(S), S уменьшается на единицу и

1. Если S0, то процесс продолжает работу.
   
2. Если S<0, то процесс останавливается и становится в очередь ожидания, связанную с S. Он остается заблокированным до тех пор, пока операция V(S), выполненная другим процессом, не освободит его.
   

Когда процесс выполняет V(S), S увеличивается на единицу и

1. Если S>0, процесс продолжает работу.
   
2. Если S0, то один процесс изымается из очереди ожидания и получает разрешение продожить работу. Процесс, который обратился к операции V(S), тоже может продолжать работу.
   

Кроме того, операции P и V – неделимы. В каждый момент времени только один процесс может выполнять операцию P или V над данным семафором. Поэтому если, S=1 и два процесса одновременно попытаются выполнить операцию P(S), то только одному из них будет позволено продолжить работу. Другой процесс будет заблокирован и поставлен в очередь к семафору S.

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

Семафор, максимальное значение которого равно единице, называется двоичным семафором.

С помощью двоичного семафора процессы могут организовать взаимное исключение с помощью операций P(S) и V(S).

Пример:


integer: СВОБОДНЫЙ;

begin

СВОБОДНЫЙ:=1;

parbegin

Процесс_1: begin do while (True);

Начало Процесса 1;

P(СВОБОДНЫЙ);

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

V(СВОБОДНЫЙ);

Оставшаяся часть Процесса 1;

end;

end;

Процесс_2: begin do while (True);

Начало Процесса 2;

P(СВОБОДНЫЙ);

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

V(СВОБОДНЫЙ);

Оставшаяся часть Процесса 2;

end;

end;

parend;

end.


Здесь S принимает значения 1, 0, -1. Если S=1, это значит, что ни один процесс не находится в своем критическом участке. Если S=0 –один процесс находится в своем критическом участке. Если S=-1 – один процесс находится в своем критическом участке, а второй – в очереди ожидания.

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

С помощью общих семафоров легко решается проблема “Поставщик–Потребитель”.

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

Переменная “заполн” – семафор, значение которого равно числу заполненных буферов, которые были отосланы потребителю.

Семафор “взаиск” (взаимное исключение) – двоичный. Он гарантирует, что в каждый момент только один процесс сможет работать с буферными стрелками.


integer: НАЛИЧИЕ,ЗАПОЛН,ВЗАИСК;

begin

НАЛИЧИЕ:= количество свободных буферов;

ЗАПОЛН := 0;

ВЗАИСК := 1;

parbegin

ПОСТАВЩИК: begin do while (True);

Приготовить сообщение;

P(НАЛИЧИЕ);

P(ВЗАИСК);

Послать сообщение;

V(ЗАПОЛН);

V(ВЗАИСК);

end;

end;

ПОТРЕБИТЕЛЬ: begin do while (True);

P(ЗАПОЛН);

P(ВЗАИСК);

Получить сообщение;

V(НАЛИЧИЕ);

V(ВЗАИСК);

Обработать сообщение;

end;

end;

parend;

end.


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

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

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

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

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

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

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


Элементарные приемы синхронизации на верхнем уровне.

1. Почтовые ящики.
   

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


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

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

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


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


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


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

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


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

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

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

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

Рассмотрим, например, ресурс, который распределяет некоторая программа – планировщик.

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

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

Следует подчеркнуть, что монитор – это пассивный объект, как комната. Это не процесс. Монитор оживает только тогда, когда какой-либо процесс решает воспользоваться его услугами. Особенностью программы-монитора состоит в том, что в любой момент ее может выполнить только один процесс.

Использование монитора иллюстрирует Пример 1, на котором изображена реализация операций P и V над семафором S. Выражение вида ИМЯ УСЛОВИЯ.ЖДАТЬ и ИМЯ УСЛОВИЯ.СИГНАЛ относятся к операциям “ждать” и ”сигнал”, связанным с условием ИМЯ УСЛОВИЯ.


Пример 1.

ДВОИЧНЫЙ_СЕМАФОР : monitor;

S: integer;

begin

condition СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ;

Procedure P;

begin

if S<1 then СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ.ЖДАТЬ;

S:=S-1;

end;

Procedure V;

begin

S:=S+1;

if S=1 then СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ.СИГНАЛ;

end;

end.

Обращение к операциям P и V записываются как ДВОИЧНЫЙ СЕМАФОР.Р и ДВОИЧНЫЙ СЕМАФОР.V. Условие СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ указывает, когда заблокированный процесс может безопасно продолжать работу. На примере два процесса взаимно исключаются из критического участка с помощью двоичного семафора, реализованного в мониторе.


Begin

parbegin

P1: begin do while (True);

call ДВОИЧНЫЙ СЕМАФОР.P;

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

call ДВОИЧНЫЙ СЕМАФОР.V;

Оставшаяся часть P1;

end;

end;

P2: begin do while (True);

call ДВОИЧНЫЙ СЕМАФОР.P;

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

call ДВОИЧНЫЙ СЕМАФОР.V;

Оставшаяся часть P2;

end;

end;

parend;

end.


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

По сравнению с семафорами мониторы имеют преимущества в том, что

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

Тупики.

Ситуация, когда процессы ждут друг друга неопределенно долго, называется тупиком или дедлоком (deadlock).

Существует три основных направления политики избежания тупиков:

• предотвращение тупиков;
  
• автоматическое обнаружение;
  
• обнаружение при участии оператора.
  

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

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

Алгоритм предотвращения тупиковых ситуаций.

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

Рассмотрим пример:

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

Представим фрагмент двух програм:





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

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

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

На рисунке а) изображено некоторое состояние системы:

	Имя процесса	Максимальная потребность	Выделено	Остаток
a)	A	4	2	2
	B	6	3	3
	C	8	2	6