рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Информатика
- /
- Алгоритм Деккера
Реферат Курсовая Конспект
Алгоритм Деккера
Алгоритм Деккера - раздел Информатика, Программное обеспечение можно разделить на две группы: системное программное обеспечение СПО и прикладное программное обеспечение ППО Алгоритм Деккера Основан На Использовании Трех Переменных (Листинг 6.4): Пере...
Алгоритм Деккера основан на использовании трех переменных (листинг 6.4): перекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1=true тогда, когда процесс ПР1 хочет войти в свой критический интервал (для ПР2 аналогично), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интервалы.
Листинг 6.4. Алгоритм Деккера
label 1, 2;
var перекл1, перекл2: boolean;
ОЧЕРЕДЬ : integer;
begin пepeкл1:=false;
перекл2:=false;
ОЧЕРЕДЬ:=1;
parbegin
while true do
begin перекл1:=true;
1: if перекл2=true then
if ОЧЕРЕДЬ=1 then go to 1
else begin перекл1:=false;
while ОЧЕРЕДЬ=2 do
begin end
end
else begin
CS1; { Критический интервал ПР1 }
ОЧЕРЕДЬ:=2;
перекл1:=faIse;
end
end
and
while true do
begin перекл2:=true;
2: if перекл1=truе then
if ОЧЕРЕДЬ=2 then go to 2
else begin перекл2:=false;
while ОЧЕРЕДЬ=1 do
begin end
end
else begin
CS2; { Критический интервал ПР2 }
ОЧЕРЕДЬ:=1;
перекл2:=false
end
end
parend
end.
Если перекл2=true и перекл1=false, то выполняется критический интервал процесса ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл2=false и перекл1=tгue.
Если же оба процесса хотят выполнить свои критические интервалы, то есть перекл2=true и перекл1=true, то выполняется критический интервал того процесса, на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов. Использование переменной ОЧЕРЕДЬ совместно с перекл1 и перекл2 в алгоритме Деккера позволяет гарантированно решать проблему критических интервалов. Переменные перекл1 и перекл2 обеспечивают, что взаимное выполнение не может иметь места; переменная ОЧЕРЕДЬ гарантирует от взаимного блокирования. Взаимное блокирование невозможно, так как переменная не изменяет своего значения во время выполнения программы принятия решения о том, кому же сейчас проходить свой критический интервал.
Тем не менее, реализация критических интервалов на основе описанного алгоритма практически не используется из-за чрезмерной сложности, особенно в случаях, когда алгоритм Деккера обобщается с двух до N процессов.
Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»
Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой IBM 360 (370) эта команда называлась TS (test and set). Команда TS является двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.
Чтобы использовать команду TS для решения проблемы критического интервала, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная, которая принимает значение, равное единице, если данный процесс хочет войти в свой критический интервал. Операция TS будет присваивать значение common локальной переменной и устанавливать common в единицу. Программа решения проблемы критического интервала на примере двух параллельных процессов приведена в листинге 6.5.
Листинг 6.5. Взаимное исключение с помощью операции «ПРОВЕРКА И УСТАНОВКА»
var common, local1. local2 : integer;
begin
common:=0;
parbegin
ПР1: while true do
begin
local1:=1;
while local1=l do TS(local1, common);
CS1; { Критический интервал npoueca ПР1 }
common:=0:
PR1; { ПР1 после критического интервала }
end
and
ПР2: while true do
begin
local2:=l;
while local2=l do TS(local2, common);
CS2; { Критический интервал процеса ПР2 }
common:=0;
PR2; { ПР2 после критического интервала }
end
parend
end.
Предположим, что первым захочет войти в свой критический интервал процесс ПР1. В этом случае значение local1 сначала установится в единицу, а после цикла проверки с помощью команды TS(local1, common) — в ноль. При этом значение common станет равным единице. Процесс ПР1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свой критический интервал.
Безусловно, мы предполагаем, что в компьютере предусмотрена блокировка памяти, то есть операция common:=0 неделима. Команда «ПРОВЕРКА И УСТАНОВКА» значительно упрощает решение проблемы критических интервалов. Главное свойство этой команды — ее неделимость.
Основной недостаток использования операций типа «ПРОВЕРКА И УСТАНОВКА» состоит в следующем: находясь в цикле проверки переменной common, процессы впустую потребляют время центрального процессора и другие ресурсы. Действительно, если предположить, что произошло прерывание процесса ПР1 во время выполнения своего критического интервала в соответствии с некоторой дисциплиной обслуживания и начал выполняться процесс ПР2, то он войдет в цикл проверки, впустую тратя процессорное время. В этом случае до тех пор, пока диспетчер супервизора не поставит на выполнение процесс ПР1 и не даст ему закончиться, процесс ПР2 не сможет войти в свой критический интервал.
В микропроцессорах i80386 и старше, с которыми мы теперь сталкиваемся постоянно, есть специальные команды: ВТС, BTS, ВТК, которые как раз и являются вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА».
Несмотря на то, что и алгоритм Деккера, основанный только на блокировке памяти, и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой процесс, который пытается войти в свою критическую секцию, попадает в цикл проверки соответствующих переменных-флагов, регламентирующих доступ к критическим переменным. При таком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время, поскольку процесс имеет доступ к тем общим переменным, которые и определяют возможность или невозможность входа в критическую секцию. При этом процесс занимает ценное время центрального процессора, на самом деле ничего реально не выполняя. Как результат, мы имеем общее замедление вычислительной системы процессами, которые реально не выполняют никакой полезной работы.
До тех пор, пока процесс, занимающий в данный момент критический ресурс, не решит его уступить, все другие процессы, ожидающие этого ресурса, могли бы вообще не конкурировать за процессорное время. Для этого их нужно перевести в состояние ожидания (заблокировать их выполнение). Когда вход в критическую секцию снова будет свободен, можно будет опять перевести заблокированный процесс в состояние готовности к выполнению и дать ему возможность получить процессорное время. Самый простой способ предоставить процессорное время только одному вычислительному процессу — это отключить систему прерываний, поскольку тогда никакое внешнее событие не сможет прервать выполняющийся процесс. Однако это, как мы уже знаем, приведет к тому, что система не сможет реагировать на внешние события.
Вместо того чтобы связывать с каждым процессом свою собственную переменную, как это было в рассмотренных нами решениях, можно со всем множеством конкурирующих критических секций связать одну переменную, которую и рассматривать как некоторый ключ. Вначале доступ к критической секции открыт. Однако перед входом в свой критический интервал процесс забирает «ключ» и тем самым блокирует другие процессы. Покидая критическую секцию, процесс открывает доступ, возвращая «ключ» на место. Если процесс, который хочет войти в свою критическую секцию, обнаруживает, что ключ «отсутствует», то он должен быть переведен в состояние блокирования до тех пор, пока процесс, имеющий ключ, не вернет его. Таким образом, каждый процесс, входящий в критический интервал, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным является то, что эти два действия должны быть неделимыми, чтобы два или более процессов не могли одновременно получить доступ к ключу. Более того, проверку того, можно ли войти в критический интервал, лучше всего выполнять не самим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию на операционную систему. Таким образом, мы подошли к одному из самых главных механизмов решения проблемы взаимного исключения — семафорам Дейкстры.
– Конец работы –
Эта тема принадлежит разделу:
Программное обеспечение можно разделить на две группы: системное программное обеспечение СПО и прикладное программное обеспечение ППО
Программное обеспечение это общий термин для обозначения quot неосязаемых quot в отличие от физических составных частей компьютерной системы... Программное обеспечение можно разделить на две группы системное программное... СПО управляет ресурсами компьютерной системы и позволяет пользователям программировать в более выразительных языках...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм Деккера
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.022 сек.
Новости и инфо для студентов