 |
Асинхронные параллельные процессы.
|
|
|
|
Процессы называются параллельными, если они существуют одновременно. Параллельные процессы могут работать совершенно независимо друг от друга или они могут быть асинхронными – им необходимо периодически синхронизироваться или взаимодействовать.
Ag a
Par begin
Оператор1; оператор2; …; операторN;
Par end.
X:=(–b+(b^2–4*a*c)^0,5)/(2*a)
Par begin
R1:= –b;
R2:=b^2;
R3:=4*a;
R4:=2*a;
Par end
R5:=R3*c;
R5:=R2–R5;
R5:=R5^0,5;
R5:=R1+R5;
X:=R5/R4;
При параллельном вычислении процессам приходится обращаться к общим данным (ресурсам). Ситуации, при которых конечный результат одновременной работы с общими данными зависит оттого, кто из них был первым, называются состояниями состязания. Подобные ситуации необходимо исключать путем введения определенных правил обращения к разделяемым данным.
Если во время обращения одного процесса к совместно-используемым данным всем другим процессам это запрещается, то такой способ взаимодействия называется взаимным исключением.
Если процесс обращается к разделяемым данным, то говорят, что он находится в своем критическом участке, а часть программы, в которой есть обращение к разделяемым данным, называется критической секцией или областью. Впервые программа реализации взаимного исключения была разработана Деккером. Свойства этого алгоритма:
- не требует специальных аппаратных команд
- процесс, работающий вне своего критического участка, не может помешать другому процессу войти в его критический участок
- процесс, желающий войти в свой критический участок, получает эту возможность без бесконечного откладывания.
Var N: integer;
Procedure Процесс1;
Begin
While true do
Begin
While N=2 do;
КритическийУчасток1;
N:=2;
ПрочиеОператоры1;
end;
end;
procedure Процесс2;
|
|
|
begin
while true do
begin
while N=1 do;
КритическийУчасток2;
N:=1;
ПрочиеОператоры2;
End; end;
BEGIN
N:=1;
Par begin
Процесс1; Процесс2;
Par end
END.
Примитив «вход взаимного исключения» реализуется как один цикл while, который повторяется до тех пор, пока переменная «номер процесса» не станет равной номеру данного процесса. Примитив «выход» реализуется как одна команда, который устанавливает для переменной N значение, равное номеру другого процесса. Алгоритм Деккера реализует взаимного исключения для двух процессов.
1981 год – алгоритм Петерсона.
Кроме программных, существуют и аппаратные способы решения проблемы взаимоисключения. Кроме алгоритмов существуют семафоры.
Семафоры.
Концепция семафоров была предложена Дейкстра. Семафор представляет собой целочисленную переменную S, с которой ассоциирована очередь ожидающих процессов. Пытаясь пройти через семафор, процесс одновременно вычитает из S единицу. Если S>=1 (семафор открыт), то процесс проходит сквозь семафор, если S=0 (семафор закрыт), то процесс останавливается и ставится в очередь.
Закрытие семафора соответствует захвату объекта или ресурса, доступ к которому контролируется этим семафором. Если объект захвачен, остальные процессы вынуждены ждать его освобождения. Закончив работу с объектом, процесс увеличивает значения семафора на единицу, открывая его. В простейшем случае работает двоичный семафор, который может быть либо нулем, либо единицей. Есть семафоры общего вида, принимающие любые целочисленные значения, соответствуют случаю, когда с объектом могут работать несколько процессов, разрешается добавлять и отнимать у S любое значение, есть реализации, у которых S<0, значение семафора можно читать и менять с помощью специальных операций, которые обозначаются Р и V, а также операцией инициализации Init Sem (Имя семафора, начальное значение). P(S): if S>0 then S:=S–1; else остановка процесса и помещение его в очередь ожидания. V(S): S:=S+1; активация одного из ожидающих процессов.
|
|
|
- К переменной S нет доступа других процессов во время выполнения.
- Выборка, наращивание и запоминание не могут быть прерваны.
- Никакие прерывания во время выполнения примитивов Р и V недопустимы.
При отказе доступа к критическому ресурсу используется режим пассивного ожидания. Поэтому в состав механизма семафоров включаются средства формирования и обслуживания очередей. Эти средства реализуются супервизором ОС. Семафоры также можно использовать для реализации механизма синхронизации процессов путем блокирования возобновления: один процесс блокирует себя (выполняя операцию P(S) до начального значения S), чтобы подождать наступления некоторого события, другой процесс обнаруживает, что ожидаемое событие произошло, и возобновляет заблокированный процесс (с помощью V(S)).
Участки взаимоисключения обрамляются операциями P и V. Если одновременно несколько процессов попытаются выполнить V, то это будет разрешено только одному из них.
Program BinSemaphore
Var S: semaphore;
Procedure процесс1;
Begin
While true do
begin
P(S);
КритическийУчасток1;
V(S);
End; end;
Procedure процесс2;
Begin
While true do
Begin
P(S);
КритическийУчасток2;
V(S);
End; end;
BEGIN
Init Sem (S,1);
Par begin
Процесс1; процесс2;
Par end
END.
Пример считающих семафоров – взаимодействие двух, выполняющихся в режиме мультипрограммирования, потоков или процессов, один из которых пишет данные в буфер, а другой считывает их.
20 марта 2012 г.
Мониторы.
Рассмотренный алгоритм Деккера имеет некоторые недостатки. Чтобы от них избавиться создали мониторы.
Хоар 1974 год. Монитор – это механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для динамического распределения общего ресурса или группы общих ресурсов. Чтобы обеспечить выделение нужного ресурса, процесс должен обратиться к конкретной процедуре монитора. Монитор находится под жестким контролем, здесь осуществляется взаимное исключение, так что в каждый момент времени только одному процессу разрешается войти в монитор. Процессы, которые хотят войти в монитор, переходят в режим ожидания, причем время и режим ожидания определяет сам монитор. Внутренние данные могут быть либо глобальные, либо локальные, но ко всем этим данным можно обращаться только изнутри монитора. Если процесс обращается к монитору за ресурсом, и обнаруживается, что этот ресурс уже занят, то монитор выдает команду WAIT (имя условия). Переменные-условия совсем не похожи на обычные переменные. Если определяется такая переменная, то заводится очередь, в которую включаются ожидающие процессы, причем для каждой отдельно взятой причины назначается собственное имя переменной-условия. Со временем процесс, который занимал данный ресурс, для возврата ресурса обращается к монитору. Если уже имеются процессы, ожидающие ресурса, то монитор применяет примитив SIGNAL (имя условия). В противном случае монитор вносит ресурс в список свободных. Примером монитора является кольцевой буфер – структура данных, широко применяемая в ОС для буферизации обменов между процессом-производителем и процессом-потребителем. Производитель, обнаруживший, что буфер заполнен, вызывает команду ожидания wait (буфер не заполнен). Потребитель, обнаруживший, что буфер пуст, вызывает wait (буфер не пуст). Производитель, помещающий данные в буфер, выдает signal (буфер не пуст). Потребитель, извлекающий данные, выдает signal (буфер не заполнен).
|
|
|
Тупики.
Говорят, что в мультипрограммной системе процесс находится в состоянии тупика (дедлока (клинча)), если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация (зависание) – это ситуация, когда один или более процесс попадают в состояние тупика. Пример – два или более процесса могут попасть в тупик, при котором каждый процесс будет удерживать ресурсы, запрашиваемые другими процессами в то время, как ему самому требуются ресурсы, удерживаемые другими. для возникновения тупика должны существовать 4 условия:
- Взаимное исключение – означает, что процессы заявляют исключительные права на управление своими ресурсами.
- Ожидание дополнительных ресурсов – это означает, что процессы могут удерживать за собой ресурсы, ожидая выделения им дополнительных запрошенных ресурсов.
- Неперераспределяемость – означает, что ресурсы нельзя принудительно отнимать у процесса.
- Круговое ожидание – означает, что существует цепочка процессов, в которой каждый процесс удерживает ресурс, запрашиваемый другим процессом, который в свою очередь удерживает другой ресурс и т.д.
Основные направления научных исследований в области тупиков – это предотвращение тупиков, обход тупиков, обнаружение тупиков, восстановление после тупиков.
|
|
|
Предотвращение тупиков.
Полностью исключить любую возможность возникновения тупика, если обеспечить нарушение любого из условий возникновения тупика. Только условие взаимного исключения нарушать нельзя, поскольку необходимо предусматривать взаимоисключающее использование многих видов ресурсов. Второе условие можно нарушить, если потребовать, чтобы пользователи заблаговременно запрашивали все необходимые ресурсы: система либо удовлетворяет такой запрос в целом, либо отвергает его и заставляет пользователя ждать. Третье условие можно нарушить, если потребовать, чтобы пользователь, который удерживает ресурсы и не получает удовлетворения запроса вначале освободил все удерживаемые ресурсы, а потом запросил их все сразу. Четвертое условие можно не допустить, если потребовать, чтобы пользователи запрашивали ресурсы в некотором, установленном системой порядке.
Обход тупиков.
Реализация основывается на алгоритме банкира, предложенный Дейкстрой, который как бы имитирует действия банкира (на месте ОС), выдает ссуды клиентам (выделяет ресурсы) и принимает платежи (возвращает ресурсы). Банкир, выдавая ссуды, оценивает свой капитал. Если капитал приближается к минимуму, то банкир откладывает выдачу ссуды и ждет возврата ссуды от других клиентов. А чтобы понять, является ли его состояние безопасным, банкир проверяет, может ли он предоставить достаточно ресурсов для завершения работы какого-либо клиента и возврата ссуды.
Согласно этому алгоритму считается, что состояние системы надежно, если имеется возможность завершить выполнение всех пользовательских программ и возвратить ресурсы системе, и состояние ненадежно в противном случае.
Обнаружение тупиков.
Возникающие тупики могут быть локализованы с выдачей соответствующей информации для привлечения внимания оператора и системы. Анализ может быть выполнен с помощью направленных графов распределения ресурсов, которые позволяют видеть состояние ресурсов системы.
Восстановление после тупиков.
Выход из тупиковых ситуаций можно обеспечить, хотя почти всегда с некоторой потерей результатов текущей работы. Восстановление после обнаружения обычно осуществляется путем вывода из системы одного или нескольких процессов, вовлеченных в тупик. При этом их ресурсы освобождаются с тем, чтобы их предоставить другим процессам. Восстановление в современных системах производится довольно сложно и не всегда эффективно.
|
|
|
Тупики в современных системах рассматриваются как достаточно редкая неприятность. В будущих системах тупики могут стать гораздо более критическим фактором, поскольку эти системы будут работать при гораздо более динамичном распределении ресурсов и большем количестве одновременно выполняемых процессов.
28 марта 2012 г.
Управление памятью.
Физическая память.
Внешняя память (storage)
Основная память (оперативная)
Быстродействующая память
Регистры процессора
Для выполнения программы необходимо, чтобы данные размещались в основной памяти.
Организация памяти – способ представления и использования основной памяти, включающий в себя решение 5 задач:
- Помещать в основную память только одну программу или несколько одновременно
- Предоставлять каждой программе одинаковое количество ячеек или разбить её на части (разделы) различных размеров
- Разбивать память на разделы жестким образом на длительное время или предусмотреть динамическое разбиение в зависимости от потребностей программы
- Выполнять программы только в конкретном разделе памяти, либо предусмотреть возможность выполнения их с занятием любых подходящих для них разделов
- Размещать каждую программу в одном непрерывном блоке памяти, либо разрешить разбивать программу на блоки, размещенные в отдельных участках памяти (дырах).
1. однопрограммные системы
2. системы со свопингом
3. мультипрограммные системы с фиксированными и переменными разделами
4. системы с загрузкой программирования модулей в абсолютных адресах или в виде перемещенных модулей.
Часть ОС, отвечающая за управление памятью, называется модулем управления или менеджером памяти.
Управление памятью реализует определенные стратегии управления, определяющие работу памяти в различных условиях. Стратегии нацелены на то, чтобы обеспечить наилучшее использование ресурсов с целью получения наивысших скоростных характеристик. Стратегии делятся на:
· Стратегии выборки (вталкивания) – ставят цель определить, когда следует «втолкнуть» очередной блок данных в основную память. Существуют стратегии выборки по запросу и с упреждающей выборкой
· Стратегии размещения – ставят цель определить, куда следует помещать поступающую программу. Существуют стратегии размещения, реализующие принципы занятия «первого подходящего», «наиболее подходящего» и «наименее подходящего» размера свободного участка памяти. Выбор первого подходящего предполагает размещение в первый найденный свободный участок, реализуется с малыми издержками. Выбор наиболее подходящего предусматривает помещение программы в «самый тесный» подходящий участок, то есть в минимальный из имеющихся участков памяти, где может поместиться программа. Третья стратегия предусматривает помещение блока программы или данных в имеющийся свободный участок максимального размера. Стратегия имеет преимущество, что она не оставляет минимальных дыр.
· Стратегии замещения – какой блок программы следует «вытолкнуть» из основной памяти, чтобы освободить место для новых записей. При этом решаются вопросы вывода из памяти следующих видов программ: которые находятся в памяти дольше других; которые используются наименее часто; которые дольше всего не использовались.
|
|
|
