30513

Разделение ресурса

Доклад

Математика и математический анализ

Способы решения проблемы гонок: Локальная копия Синхронизация Метод блокирующей переменной Метод строгого чередования Алгоритм Деккера Алгоритм Петерсона Комбинированный способ Локальная копия Самый простой способ решения копирование переменной x в локальную переменную. В общем виде алгоритм выглядит следующим образом: Поток: while stop { synchronizedSomeObject { {criticl_section} } } Метод блокирующей переменной Суть метода состоит в том что если значение этой переменной равно например 1 то ресурс занят другим...

Русский

2013-08-24

68.3 KB

5 чел.

Доска.

Разделяемый ресурс

Поток 1

Поток 2

Поток 3

Выступление.

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

Разделению подлежат как аппаратные, так программные ресурсы.

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

Необходимо уметь решать две важнейшие задачи:

  1. Распределение ресурсов между процессами.
  2. Организация защиты адресного пространства и других ресурсов, выделенных определенному процессу, от неконтролируемого доступа со стороны других процессов.

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

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

 int x; // общая переменная

// Поток 1

while (!stop)

{

 x++;

}

// Поток 2

while (!stop)

{

 if (x%2 == 0)

   print("x=" + x);

}

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

  1. if в потоке 2 проверяет x на чётность.
  2. Оператор «x++» в потоке 1 увеличивает x на единицу.
  3. Оператор вывода в потоке 2 выводит «x=1», хотя, казалось бы, переменная проверена на чётность.

Такие ситуации называются гонками (race conditions) между процессами, а процессы – конкурирующими.

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

Способы решения проблемы гонок:

  1. Локальная копия
  2. Синхронизация
  3. Метод блокирующей переменной
  4. Метод строгого чередования
  5. Алгоритм Деккера
  6. Алгоритм Петерсона
  7. Комбинированный способ

Локальная копия

Самый простой способ решения — копирование переменной x в локальную переменную.

// Поток 2:

while (!stop)

{

 int cached_x = x;

 if (cached_x%2 == 0)

   print("x=" + cached_x);

}

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

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

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

// Поток:

while (!stop)

{

 synchronized(SomeObject)

 {

   {critical_section}

 }

 …

}

Метод блокирующей переменной

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

// Поток:

while (!stop)

{

 while(i==1)

 {}

 i=1;

 {critical_section}

 i=0;

}

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

Метод строгого чередования

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

//Поток1

while (!stop)

{

 while(i!=0)

 {}

 {critical_section}

 i=1;

}

//Поток2

while (!stop)

{

 while(i!=1)

 {}

 {critical_section}

 i=0;

}

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

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

Алгоритм Деккера – программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм Деккера усовершенствован Петерсоном.

Алгоритм имеет следующие ограничения.

  1. Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).
  2. При ожидании ресурса, процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

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

f0 := false

f1 := false

turn := 0   // or 1

//Поток1

f0 = true

while f1

{

  if (turn !=  0)

  {

     f0 = false;

     while (turn != 0) {}

     f0 = true;

  }

}

Critical_section;

turn = 1;

f0 = false;

//Поток2

f1 = true

while f0

{

  if (turn !=  1)

  {

     f1 = false;

     while (turn != 1) {}

     f1 = true;

  }

}

Critical_section;

turn = 0;

f1 = false;

Алгоритм Петерсона

Алгоритм Петерсона – программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм Петерсона имеет смысл в системах на базе модели вычислений Фон-Неймана. Алгоритм Петерсона предложен в 1981 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера.

Алгоритм имеет следующие ограничения.

  1. Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).
  2. При ожидании ресурса процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

Алгоритм работает на использовании двух переменных: у каждого процесса есть собственная переменная flag[i] и общая переменная turn. Все переменные хранятся в общей для обоих процессов памяти. В переменной flag запоминается факт захвата ресурса, в переменной turn – номер захватившего ресурс процесса.

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

flag[0] = 0

flag[1] = 0

turn = 0

//Поток1

flag[0] = 1;

turn = 1;    

while( flag[1] && turn == 1 ){}

critical_section;

flag[0] = 0;

//Поток2

flag[1] = 1;

turn = 0;    

while( flag[0] && turn == 0 ){}

critical_section;

flag[1] = 0;

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

Комбинированный способ

Предположим, что переменная x имеет тип не int, а long (на 32-битных ЭВМ её копирование выполняется за две машинных команды), а во втором потоке вместо System.out.println стоит более сложная обработка. В этом случае оба метода неудовлетворительны: первый — потому что x может измениться, пока идет копирование; второй — потому что засинхронизирован слишком большой объём кода.

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

long x;

// Поток 1:

while (!stop)

{

 synchronized(SomeObject)

 {

   x++;

 }

 …

}

while (!stop)

{

 long cached_x;

 synchronized (SomeObject)

 {

   cached_x = x;

 }

 if (cached_x%2 == 0)

   DoSomethingComplicated(cached_x);

 

}

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


 

А также другие работы, которые могут Вас заинтересовать

44503. Самай сүйек өзектері, олардың маңызы 15.31 KB
  Гуманисты были творцами новой системы знания в центре которого стояла проблема человека его земного предназначения термин humnist полагает П. Мишле выдвинул принципиально отличное от средневекового решения проблемы отношения человека к миру. Бурдаха где он писал что новое понимание искусства литературы науки новая концепция человека не вступали в противоречие в христианской религией ибо были предопределены ее пышным цветением в XIII в. Наиболее значительной для Тоффанина была идея божественности человека.
44504. Дабыл қуысы, қабырғалары, құрамы, қатынастары, отит кезіндегі асқынулар 16.68 KB
  Отит-құлақтың қабынуы. қөбіне ортаңғы құлақтың қабыну кездеседі-лабиринтит. Ортаңғы отит қоздырғышы кокктар-пнвмококк, стафилококк, гемофильді таяқшалар. Көбіне жоғары тыныс алу жолдарының асқынуларынан кейн п. б
44505. Көзұясы, қабырғаларының құрылысы, тесіктері, олардың маңызы 15.81 KB
  Начинается серия войн с Византией велись они с переменным успехом но в целом удачно для Болгарии. престиж Болгарии как международной державы был высок. Послов Болгарии за императорским столом сажали выше чем послов германского императора Оттона I. в Болгарии появилось богомильское движение дуализм.
44506. Қанат-таңдай шұңқыры, оның қабырғалары, тесіктері, қатынастары. Самай шұңқыры. Самайасты шұңқыры 15.81 KB
  Медиальды қабырғасы-төбе сүйегінің сыртқы бетінің сыналық бұрышының маңындағы төменгң бөлігінен, самай сүйектің қабықшалы бөлгінің сыртқы бетінен, сына сүйектің улкен қанатының саай шұңқырына қараған бетінен құралған
44507. Ми сауыты негізінің сыртқы беткейі 16.56 KB
  Шүйде сүйегі-os occipitale, ми саутының артқы қапталында орн. сыртқа беті-дөңестеу, ішкі беті-ойыстау келген тақ сүйек. Шүйде сүйектің артқы жағында ми сауытын омыртқа өзекшесімен жалғастырушы шүйделік үлкен тесік-foramen magnum, бүйір қапталында сигма тәрізді қойнаудың жүлгесі-sulcus sinus sigmoideus, орналасқан.
44508. Ми сауыты негізінің ішкі беткейі, тесіктері, маңызы 16.32 KB
  Түрік ершігінің бүйір бөлігінде-нервтік өрім жүлгесі-sulcus coroticus, орн. алд немесе мұрын қуысына қараған бетінде-сына сүйек қырқасы-crista sphenoidalis, ол кеңсірік сүйегінің қанатымен-ala vomeris, беттесіп кеңсірік-ілмектік өзекшені-canalis vomeroorastralis, құрайды. Сына сүйек қойнауы-sinus sphenoidalis
44509. Биотехнические системы 5.73 MB
  Биотехнические системы – особый класс больших систем, в которых биологические и технические элементы связаны в едином контуре управления, причем роль управляющего звена в них могут играть как технические, так и биологические звенья. Создание таких систем является сложной задачей, использующей целый арсенал отдельных приемов, методов и подходов
44510. ОСНОВЫ ТЕОРИИ ГОСУДАРСТВА И ПРАВА 1.58 MB
  Общество выступает как система разнообразных общественных связей и общественных отношений. Общество — это сложнейшая, естественным путем сложившаяся социальная система, которая, в свою очередь, состоит из социальных сообществ.
44511. Биотехнологические основы приготовления хлеба 1.22 MB
  В учебном пособии представлены основные положения биотехнологии хлебопекарного производства, рассмотрены свойства нишевых веществ зерна, описаны разнообразные типы брожения и микроорганизмы, их вызывающие, приведены практические разработки и теоретическое обоснование применения различных заквасок для переработки ржаной и пшеничной муки, биотехнологические методы интенсификации процесса приготовления теста и улучшения качества готовых изделий.