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

 

}

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


 

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

34155. Главный фактор потребности выбора 16.57 KB
  Потребляя те или иные блага люди тем самым как бы оценивают их полезность для себя. Главный фактор потребности выбора полезность того или иного товара это категория применяемая для характеристики результатов эффективности экономических решений или деятельности. В более ограниченном смысле полезность определяется как субъективная польза извлекаемая индивидом из потребления товара или услуги. Полезность означает способность экономического блага товара услуги удовлетворять определенные потребности людей.
34156. ПОТРЕБИТЕЛЬСКИЙ ВЫБОР 22.98 KB
  Изменение цены какоголибо товара влияет на объем спроса через эффект дохода и эффект замещения. Эффект дохода возникает поскольку изменение цены данного товара увеличивает при снижении цены или уменьшает при повышении цены реальный доход или покупательную способность потребителя. Эффект замещения замены возникает в результате относительного изменения цен. Эффект замещения способствует росту потребления относительно подешевевшего товара тогда как эффект дохода может стимулировать и увеличение и сокращение потребления товара или быть...
34157. Инфраструктура рынка 15.91 KB
  Основные элементы инфраструктуры рынка. Условно рыночную инфраструктуру можно подразделить по видам объединений баз субъектов инфраструктуры главная задача которых обеспечение функционирования рынка. Среди таких объединений выделяют: 1 организационные объединения рыночной инфраструктуры биржи оптовые брокерские дилерские и другие посреднические организации коммерческие структуры крупных промышленных объединений комбинатов концернов предприятия мелкооптовой и розничной торговли; 2 материальную базу рыночной инфраструктуры...
34158. Фирма 14.37 KB
  Фирма может быть огромной и небольшой но в любом объеме обладает определенными преимуществами: а сокращение трансакционных издержек; б сокращение средних издержек производства; в эффект организованного процесса. В процессе производства товаров и услуг затрачивается живой и прошлый труд. издержки производства. Влиять на ход и результативность производства она может лишь путем изменения интенсивности использования своих мощностей.
34159. Издержки производства в долгосрочном периоде 21.87 KB
  Особенность изменения затрат и издержек производства в долгосрочном периоде рождает необходимость анализа этих затрат и издержек на основе долгосрочных средних и предельных издержек. Закономерностью изменения долгосрочных средних издержек является их первоначальное снижение с расширением производственных мощностей и ростом объема производства. Однако в итоге ввод все больших и больших мощностей приведет к увеличению долгосрочных средних издержек. Графическим выражением связи между издержками производства единицы продукции и объемом выпуска в...
34160. Монополистическая конкуренция 17.96 KB
  Понятие чистой монополии обычно является абстрактным. Цель монополии получение сверхприбыли посредством контроля за ценой и объемом производства на монополизированном рынке. Основные черты чистой монополии: 1 единственный продавецпроизводитель; 2 товарная дифференциация отсутствует отсутствие товаровзаменителей; 3 продавец осуществляет практически полный контроль над ценами; 4 очень трудные условия вхождения в отрасль новых предприятий. Искусственные монополии.
34161. Причины государственного регулирования 17.87 KB
  А неоправданно высокие цены сводят на нет социальный эффект экономии от масштаба. Стремление к извлечению экономической прибыли и назначение цены выше предельных издержек в случае установления единой цены на товар для различных групп потребителей приводит к сокращению объёма производства относительно конкурентного уровня и появлению DWL потерь мёртвого груза . Поскольку цены на продукцию монополий велики то бывает так что предприятия продают свои товары и услуги в кредит. Но чего государство может добиться управляя фирмами...
34162. Рынок капиталов 20.33 KB
  На спрос воздействуют рыночные факторы прежде всего цена на средства производства. Чем выше цена средств производства тем меньше спрос на них со стороны покупателя. Среди них важную роль играет цена на средства производства. Чем выше цена средств производства тем выше предложение на них со стороны продавцов.
34163. Движение капитала и его структура 14.25 KB
  Движение капитала и его структура. Движение капитала – миграция капиталов между странами приносящее доход их собственникам. В свою очередь международная миграция капитала включает экспорт импорт капитала и его функционирование за рубежом. Мировое движение капитала в современных условиях служит фактором усиления интернационализации производства увеличения темпов экономического роста и уровня занятости развития передовых отраслей промышленности и превращает финансовые рынки в важнейший стимул развития мирового хозяйства.