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);

 

}

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


 

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

34395. Прогнозирование и планирование объема и структуры промышленного производства 33 KB
  На заключительном этапе формируются плановый объем и структура выпуска промышленной продукции с учетом спроса возможностей производства и обеспечения производственными ресурсами. Обосновывается и устанавливается заказ на поставку важнейших видов продукции для государственных нужд. Для прогнозирования спроса и объема производства конкретных видов продукции хорошие результаты дает метод Дельфи . Путем анкетного опроса группы ученых и специалистов по данной проблеме формируется информация по выпуску каждого вида продукции по годам которая...
34396. Сущность и содержание прогнозирования. Роль и характер прогнозов 44.5 KB
  Прогнозирование это процесс разработки прогноза построенный на вероятностном научно обоснованном суждении о перспективах развития объекта в будущем его возможном состоянии и альтернативных путях его достижения. Социальноэкономическое прогнозирование является способом предвидения представления о будущем обусловленном закономерностями общественного развития и действием разнообразных и разнонаправленных факторов в прогнозируемом периоде. В соответствии с Законом О государственном прогнозировании и программах социальноэкономического...
34397. Сущность планирования. Директивное, индикативное, стратегическое планирование, их характеристика 47 KB
  При формировании рыночных отношений в Республике Беларусь необходимо видение перспектив ее экономического и социального развития. Планирование это процесс принятия управленческого решения основанный на обработке исходной информации и включающий в себя определение и научную постановку целей средств и путей их достижения посредством сравнительной оценки альтернативных вариантов и выбора наиболее приемлемого из них в ожидаемых условиях развития. Суть планирования состоит не в разработке и доведении многочисленных показателей до...
34398. Предмет курса, его место в системе экономических наук 27 KB
  Пип наука изучающая экие теории и законы применительно к конкретным условиям производства их специфические проявления в важнейших процессах прва закономерностях темпов и пропорциях с тем чтобы в результате этого изучения с учетом достижений НТП передового опыта обосновать объемы темпы и пропорции общественного производства в целях наиболее эффективного развития экономики. Задача курса состоит в рассмотрении комплекса теоретических методологических организационных вопросов пип экономики на современном этапе. Теория пип является...
34399. Исторический аспект развития прогнозирования и планирования 26 KB
  Экономическая мысль совершая поиск путей становления системы планирования испытывала колебания вступала в противоборство допуская ошибки и избавляясь от них под влиянием реальных явлений хозяйственной жизни. Рассмотрим становление и совершенствование прогнозирования и планирования в бывшем СССР и развитых зарубежных странах. Первый долгосрочный план который представляет интерес с точки зрения общей методологии планирования это план ГОЭЛРО государственный план электрификации России разработанный в 1920 г.
34400. Развитие и особенности ПИП в зарубежных странах (США, Япония, Франция и др.) 45.5 KB
  Для США характерно стратегическое планирование суть которого состоит в выборе главных приоритетов развития национальной экономики ведущую роль в реализации которых играет государство. Основным источником займов на цели разработки и освоения новой технологии является Японский банк развития. Направления стратегического развития разрабатываются в виде целевых государственных программ и сопровождаются комплексом различных финансовых льгот и преференций стимулирующих их реализацию. Она представляет собой модель будущего развития экономики...
34401. Научные основы методологии прогнозирования и планирования 30.5 KB
  Вторая является основой планирования и прогнозирования в странах с рыночной экономикой. Методология прогнозирования и планирования развития экономики определяет основные принципы подходы и методы проведения прогнозных и плановых расчетов раскрывает и характеризует логику формирования прогнозов планов и их осуществления. Принципы это основополагающие правила прогнозирования и планирования т.
34402. Система показателей планов-прогнозов 30.5 KB
  Нормативы показатели в относительном выражении. Лимиты ресурсные показатели представляющие предельно допустимую величину затрат ресурса для достижения установленных конечных результатов. Основными блоками показателей прогнозирования и планирования экономических и социальных процессов являются: показатели производства трудовых ресурсов основных и оборотных фондов капитальных вложений природных ресурсов научнотехнического прогресса финансов и денежного обращения социального развития и уровня жизни населения внешнеэкономических...
34403. Система прогнозов и планов. Методологические основы их сопряжения 32 KB
  Для формирования стратегии и тактики развития экономики разрабатывается система прогнозов включающая прогнозы временного аспекта и по уровням управления а также частные и комплексные прогнозы экономического и социального развития страны и регионов. По масштабу прогнозирования выделяют: макроэкономические прогнозы межотраслевые и межрегиональные прогнозы развития народнохозяйственных комплексов отраслевые и региональные прогнозы прогнозы звеньев экономики: предприятий объединений отдельных производств и продуктов. Во временном аспекте...