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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Алгоритм Деккера

Информация:

Тип работы: курсовая работа. Добавлен: 02.11.2012. Сдан: 2011. Страниц: 7. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Оглавление
Введение……………………………………………………………………...
Принцип взаимоисключения ……………………………………………….
Примитив взаимоисключения………………………………………………
Взаимодействие  и взаимоисключение процессов…………………………
Варианты программного решения проблемы взаимоисключения……….
Правильное решение  проблемы  взаимоисключения……………………..
Алгоритм Деккера…………………………………………………………...
Доказательство правильности алгоритма Деккера......................................
Заключение…………………………………………………………………..
Список используемой  литературы………………………………………... 
 
 
 
 
 
 
 
 
 

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

рис.1, процессы в информационных сетях
Критический раздел - объект, к которому должен обратиться поток перед получением эксклюзивного доступа к каким-либо общим данным. Среди синхронизирующих объектов критические разделы наиболее просты, но применимы для синхронизации потоков лишь принадлежащих одному процессу. Они дают возможность сделать так, чтобы одновременно только один поток получал доступ к определенному региону данных. Критический раздел анализирует значение специальной переменной процесса, которая используется как флаг, предотвращающий исполнение некоторого участка кода несколькими потоками одновременно.
Механизм критических  разделов основан на принципе взаимного  исключения (mutual exclusion). Этот термин нам еще встретится при дальнейшем рассмотрении синхронизации потоков. Только один поток может быть владельцем критического раздела в каждый конкретный момент времени. Следовательно, один поток может войти в критический раздел, установить значения полей структуры и выйти из критического раздела. Другой поток, использующий эту структуру, также мог бы войти в критический раздел перед осуществлением доступа к полям структуры, а затем выйти из критического раздела.
Обратите внимание, что возможно определение нескольких объектов типа критический раздел, например, cs1 и cs2. Если в программе имеется четыре потока, и два первых из них разделяют некоторые данные, то они могут использовать первый объект критический раздел, а два других потока, также разделяющих другие данные, могут использовать второй объект критический раздел.
Обратите внимание, что надо быть весьма осторожным при  использовании критического раздела  в главном потоке. Если вторичный  поток проводит слишком много  времени в его собственном  критическом разделе, то это может  привести к "зависанию" главного потока на слишком большой период времени. 
 
 
 

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

Примитивы взаимоисключения.
Общим подходом к построению механизмов синхронизации  с использованием концепции критических  участков является применение примитивов взаимоисключения.
     Примитивами  взаимоисключения называется программная  конструкция, обеспечивающая реализацию  взаимоисключений для параллельных  процессов. В обобщенном виде  можно указать два примитива  взаимоисключений:
     1) примитив вход_взаимоисключения – с его помощью фиксируется захват критического ресурса данным процессом и
устанавливается запрет на использование его другими  процессами;
     2) примитив выход_взаимоисключения – с его помощью процесс сообщает об освобождении им критического ресурса.
     Простейший  алгоритм синхронизации с применением  примитивов взаимоисключения состоит в следующем. Главный
процесс запускает  в работу два параллельных процесса П1 и П2, после чего он может закончить свою работу. Каждый из параллельных процессов в своем теле имеет области работы с критическим ресурсом. Эти области обязательно обрамляются примитивами вход_взаимоисключения и выход_взаимоисключения.
     В  рассматриваемом случае двух  процессов эти примитивы работают  следующим образом. Когда процесс  П1 выполняет
примитив вход_взаимоисключения и если при этом процесс П2 находится вне своего критического участка, то П1 входит в свой критический участок, выполняет работу с критическим ресурсом, а затем выполняет примитив вы-
ход_взаимоисключения, показывая тем самым, что он вышел из своего критического участка. Если П1 выполняет вход_взаимоисключения, в то время как П2 находится на своем критическом участке, то процесс П1 переводится в состояние ожидания, пока процесс П2 не выполнит выход_взаимоисключения. Только после этого процесс П1 может выйти из состояния ожидания и войти в свой критический участок.
     Если  процессы П1 и П2 выполняют вход_взаимоисключения одновременно, то одному из них операционная система раз-
решает продолжить работу, а другой переводит в состояние ожидания. 

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

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

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

Первая  попытка

Как упоминалось  ранее, любая попытка взаимного  исключения должна опираться на некий  фундаментальный механизм исключений аппаратного обеспечения. Наиболее общим механизмом может служить  ограничение, согласно которому к некоторой  ячейке памяти в определенный момент времени может осуществляться только одно обращение. Воспользовавшись этим ограничением, зарезервируем глобальную ячейку памяти, которую назовем turn. Процесс (Р0 или Р1), который намерен выполнить критический раздел, сначала проверяет содержимое ячейки памяти turn. Если значение turn равно номеру процесса, то процесс может войти в критический раздел; в противном случае он должен ждать, постоянно опрашивая значение turn до тех пор, пока оно не позволит процессу войти в критический раздел. Такая процедура известна как пережидание занятости (busy waiting), поскольку процесс вынужден, по сути, не делать ничего полезного до тех пор, пока не получит разрешение на вход в критический раздел. Более того, он
постоянно опрашивает значение переменной и тем самым  потребляет процессорное время. 
После того как процесс, получивший право на вход в критический раздел, выходит из него по завершении работы, он должен обновить значение turn, присвоив ему номер другого процесса.

Говоря формально, имеется глобальная переменная
int turn = 0;
На рис. 5.1,а  показана программа для двух процессов. Это решение гарантирует корректную работу взаимоисключения, однако имеет  два недостатка. Во-первых, при входе  в критический раздел процессы должны строго чередоваться; тем самым скорость работы диктуется более медленным из двух процессов. Если процессу Р0 вход в критический раздел требуется раз в час, а процессору Р1 — 1000 раз в час, то темп работы Р1 будет таким же, как и у процесса Р0. Во-вторых, гораздо более серьезная ситуация возникает в случае сбоя одного из процессов — при этом второй процесс оказывается заблокирован (при этом неважно, происходит ли сбой процесса в критическом разделе или нет). 
Описанная конструкция представляет собой сопрограмму (coroutine). Сопрограммы разрабатываются таким образом, чтобы быть способными передавать управление друг другу. Однако хотя эта технология структурирования и весьма полезна для отдельно взятого процесса, для поддержки параллельных вычислений она не подходит.

 
/* Процесс 0 */ 

 
while (turn != 0) 
/* Ничего не делаем */; 
/* Критический раздел */; 
turn = 1; 


/* Процесс 1 */ 

  
while (turn != 1) 
/* Ничего не делаем */; 
/* Критический раздел */; 
turn = 0; 


(а)         Первая попытка
/* Процесс 0 */ 

 
    while (flag[l])  
    /* Ничего не делаем */; 
    flag[0] = true;  
    /* Критический раздел */; 
    flag[0] = false;     


/* Процесс 1 */  

while (flag[0])  
/* Ничего не делаем */; 
flag[1] = true;  
/* Критический раздел */; 
flag[0] = false;     


(б)       Вторая попытка
/* Процесс 0 */ 

flag[0] = true; 
while (flag[l]) 
/* Ничего не делаем */; 
/* Критический раздел */; 
flag[0] = false;     


/* Процесс 1 */ 

flag[1] = true;  
while (flag[0])  
/* Ничего не делаем */; 
/* Критический раздел */; 
flag[1] = false;     


 (в)       Третья попытка
 /* Процесс 0 */
    *
flag[0] = true; 
while (flag[l]) 

flag[O] = false; 
/* Задержка */ 
flag[O] = true; 

/* Критический раздел */; 
flag[O] = false;     


 /* Процесс 1 */
    *
flag[1] = true; 
while (flag[0]) 

flag[1] = false; 
/* Задержка */ 
flag[1] = true; 

/* Критический раздел */; 
flag[1] = false;     


 (г)       Четвертая попытка
Рис. 5.1. Попытки взаимных исключений

Вторая  попытка

Проблема при  первой попытке заключается в  том, что в ней хранилось имя  процесса, который имел право входа  в критический раздел, в то время как в действительности нам требуется информация об обоих процессах. По сути, каждый процесс должен иметь собственный ключ к критическому разделу, так что если даже произойдет сбой одного процесса, второй все равно сможет получить доступ к критическому разделу. Для удовлетворения этого условия определен логический вектор flag, в котором flag[0] соответствует процессу Р0, a flag[l] — процессу P1. Каждый процесс может ознакомиться с флагом другого процесса, но не может его изменить. Когда процессу требуется войти в критический раздел, он периодически проверяет состояние флага другого процесса до тех пор, пока тот не примет значение false, указывающее, что другой процесс покинул критический раздел. Процесс немедленно устанавливает значение своего собственного флага равным true и входит в критический раздел. По выходе из критического раздела процесс сбрасывает свой флаг, присваивая ему значение true. 
Теперь разделяемые переменные выглядят следующим образом:

enum boolean { false = 0, true = 1; }; 
boolean flag[2] = { false, false };

Этот алгоритм показан на рис. 5.1,b. Теперь если произойдет сбой одного из процессов вне критического раздела (включая код установки  значения флага), то второй процесс  заблокирован не будет. Этот второй процесс  в таком случае сможет входить  в критический раздел всякий раз, как только это потребуется, поскольку флаг другого процесса всегда будет иметь значение false. Однако если сбой произойдет в критическом разделе (или перед входом в критический раздел, но после установки значения флага равным true), то другой процесс окажется навсегда заблокированным.
Описанное решение, по сути, оказывается еще хуже предложенного  ранее, поскольку даже не гарантирует  взаимного исключения. Рассмотрим такую  последовательность действий:
Р0 выполняет инструкцию while и находит, что значение flag[l] равно false; 
P1 выполняет инструкцию while и находит, что значение flag[0] равно false; 
Р0 устанавливает значение flag [0] равным true и входит в критический раздел;  
Р1 устанавливает значение flag [1] равным true и входит в критический раздел.

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

Третья  попытка

Поскольку процесс  может изменить свое состояние после  того, как другой процесс ознакомится  с ним, но до того, как этот другой процесс войдет в критический  раздел, вторая попытка также оказалась  неудачной. Возможно, нам удастся  выправить ситуацию внесением в  код небольшого изменения, показанного  на рис. 5.1,в.
Как и ранее, если происходит сбой одного процесса в критическом разделе, включая  код установки значения флага, то второй процесс окажется заблокированным (и соответственно, если сбой произойдет вне критического раздела, то второй процесс блокирован не будет).
Далее проверим гарантированность взаимоисключения, проследив за процессом Р0. После того как процесс Р0 установит flag[0] равным true, P1 не может войти в критический раздел до тех пор, пока туда не войдет и затем не покинет его процесс Р0. Может оказаться так, что процесс Р1 уже находится в критическом разделе в тот момент, когда Р0 устанавливает свой флаг. В этом случае процесс Р0 будет заблокирован инструкцией while до тех пор, пока Р1 не покинет критический раздел. Аналогичные действия происходят при рассмотрении процесса Р1. 
Тем самым гарантируется взаимное исключение; однако третья попытка порождает еще одну проблему. Если оба процесса установят значения флагов равными true до того, как один из них выполнит инструкцию while, то каждый из процессов будет считать, что другой находится в критическом разделе, и тем самым осуществится взаимоблокировка.  

Четвертая попытка

В третьей попытке  установка процессом флага состояния  выполнялась без учета информации о состоянии другого процесса. Взаимоблокировка возникала по той  причине, что каждый процесс мог добиваться своих прав на вход в критический раздел и отсутствовала возможность отступить назад из имеющегося положения. Можно попытаться исправить ситуацию, делая процессы более "уступчивыми": каждый процесс, устанавливая свой флаг равным true, указывает о своем желании войти в критический раздел, но готов отложить свой вход, уступая другому процессу, как показано на рис. 5.1,г.
Это уже совсем близко к корректному решению, хотя все еще и неверно, Взаимоисключение гарантируется (в чем можно убедиться, применяя те же рассуждения, что и  при третьей попытке), однако рассмотрим возможную последовательность событий:
Р0 устанавливает  значение flag[0] равным true; 
P1 устанавливает значение flag[l] равным true; 
Р0 проверяет f lag [ 1 ]; 
P1 проверяет flag [0]; 
Р0 устанавливает значение flag[0] равным false; 
P1 устанавливает значение flag[l] равным false; 
Р1 устанавливает значение flag[0] равным true; 
P1 устанавливает значение flag[l] равным true.

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

Правильное  решение

У нас должна быть возможность следить за состоянием обоих процессов, что обеспечивается массивом flag. Но, как показала четвертая попытка, этого недостаточно. Мы должны навязать определенный порядок действий двум процессам, чтобы избежать проблемы "взаимной вежливости", с которой только что столкнулись. С этой целью можно использовать переменную turn из первой попытки. В нашем случае эта переменная указывает, какой из процессов имеет право на вход в критический раздел.
Мы можем описать  это решение следующим образом. Когда процесс Р0 намерен войти в критический раздел, он устанавливает свой флаг равным true,-а затем проверяет состояние флага процесса Р1. Если он равен false, Р0 может немедленно входить в критический раздел; в противном случае Р0 обращается к переменной turn. Если turn = 0, это означает, что сейчас — очередь процесса Р0 на вход в критический раздел, и Р0 периодически проверяет состояние флага процесса Р1. Этот процесс, в свою очередь, в некоторый момент времени обнаруживает, что сейчас не его очередь для входа в критический раздел, и устанавливает свой флаг равным false, давая возможность процессу Р0 войти в критический раздел. После того как Р0 выйдет из критического раздела, он установит свой флаг равным false для освобождения критического раздела и присвоит переменной turn значение 1 для передачи прав на вход в критический раздел процессу Р1. 

boolean flag [2] ; 
int turn; 
void Р0 () 

while(true) 

flag[0] = true; 
while(flag[l]) 
if (turn == 1) 

flag[0] = false; 
while(turn == 1) 
/* Ничего не делать */; 
flag[0] = true; 

/* Критический раздел */; 
turn = 1; 
flag[0] = false;  
/* Остальной код */; 


void P1() 

while(true) 

flag[l] = true; 
while(flag[0]) 
if (turn == 0) 

flag[l] = false; 
while(turn == 0) 
/* Ничего не делать */; 
flag[l] = true; 

/* Критический раздел */; 
turn = 0; 
flagfl] = false;  
/* Остальной код */; 


void main() 

flag[0] = false; 
flagfl] = false; 
turn = 1;  
parbegin(PO,PI);

} 

Межпроцессное взаимодействие — набор способов обмена данными между множеством потоков в одном или более процессах. Процессы могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена  сообщениямисинхронизации, разделяемой памяти и удаленных вызовов (RPC). ) Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации. 

Алгоритм Деккера гарантирует взаимное исключение, невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо последнее свойство. Предположим, что p0 остался внутри цикла «while flag[1]» навсегда. Поскольку взаимная блокировка произойти не может, рано или поздно p1 достигнет своей критической секции и установит turn = 0 (значение turn будет оставаться постоянным пока p0 не продвигается). p0 выйдет из внутреннего цикла «while turn ? 0» (если он там находился). После этого он присвоит flag[0] значение true и будет ждать, пока flag[1] примет значение false (так как turn = 0, он никогда не выполняет действия в цикле «while»). В следующий раз когда p1 попытается войти в критическую секцию, он будет вынужден исполнить действия в цикле «while flag[0]». В частности, он присвоит flag[1] значение falsи будет исполнять цикл «while turn ? 1» (так как turn остаётся равной 0). Когда в следующий раз управление перейдёт к p0, он выйдет из цикла «while flag[1]» и войдёт в критическую секцию.
Если модифицировать алгоритм так, чтобы действия в цикле  «while flag[1]» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.
Одним из преимуществ  алгоритма является то, что он не требует специальных Test-and-set инструкций (атомарная операция чтения, модификации и записи) и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).
Алгоритм  Деккера  гарантирует корректное решение проблемы  взаимоисключения  для двух  потоков.  Управляющие переменные  ResourceThread1,  ResourceThread1  обеспечивают  взаимоисключение,  переменная ThreadNum исключает возможность бесконечного откладывания. Если оба потока пытаются получить доступ к ресурсу, то поток, номер которого указан  в ThreadNum,  продолжает  проверку  возможности доступа к ресурсу (внешний цикл ожидания ресурса). Другой же поток в этом случае снимает свой запрос на ресурс, ожидает своей очереди доступа к ресурсу (внутренний цикл ожидания) и возобновляет свой запрос на ресурс.
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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