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

 

}

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


 

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

51258. ІСТОРІЯ ЕКОНОМІКИ ТА ЕКОНОМІЧНОЇ ДУМКИ 84.42 KB
  У методичних рекомендаціях викладено загальні положення та тематичний зміст практичних занять з нормативної навчальної дисципліни циклу природничо-наукової та загальноекономічної підготовки «Економічна історія». Наведено перелік питань для обговорення з кожної теми, тести для відповідей, перелік рекомендованої літератури.
51259. БОЛЬНИЧНАЯ ГИГИЕНА (РУКОВОДСТВО К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ) 790.5 KB
  Вопросы гигиены лечебно-профилактических учреждений являются одними из самых существенных в курсе гигиены для студентов лечебного и педиатрического факультетов.
51260. Расчет математического ожидания, среднего квадратического отклонения, дисперсии, с помощью программы Microsoft Excel 33.5 KB
  Так как функция математического ожидания это т оже самое что и функция среднего арифметического то: в пустой ячейке вводим = далее нажимаем fx выбираем функцию СРЗНАЧ выделяем числовые данные нашей исходной таблицы. Вычислить дисперсию: Вводим = далее fx Статистические ДИСП выделить числовые данные...
51261. Финансы - сложная экономическая категория 409.5 KB
  Расширенное воспроизводство включает непрерывное возобновление и расширение производственных фондов, рост валового внутреннего продукта (ВВП) и его главной части – национального дохода, воспроизводство рабочей силы и производственных отношений. Оно осуществляется с использованием товарно-денежных, финансовых и кредитных отношений
51262. Оценка вероятностей, с помощью компьютерных программ Microsoft Excel и Калькулятор 26.5 KB
  Задача работы: оценить вероятность безошибочного написания СМС, которое состоит из 10 символов со 100 нажиманий клавиш, если в 30 случаях нажимания клавиш есть ошибка.
51263. Оценка парных связей между случайными переменными 31 KB
  Просчитать коэффициент корреляции в программе Microsoft Excel: = нажать fx выбрать в поиске всех формул КОРРЕЛ массив1 числа соответствующие обменному пункту №1 массив2 пункту №2.
51265. Построение графа состояний P-схемы 157 KB
  Задание 1. Построить граф состояний P-схемы. Смысл кодировки состояний раскрыть (время до выдачи заявки, число заявок в накопителе и т.д.). На схеме условно обозначены:
51266. Система тонких линз и определение их основных характеристик 91 KB
  Определение фокусных расстояний собирающей и рассеивающей линз и основных характеристик оптических систем составленных из этих линз. Приборы и принадлежности: источник света со щелью в виде стрелки; экран; рейтер и масштабная линейка; набор линз две собирающих и одна рассеивающая; два штатива для установки линз. Теоретические сведения Оптическая сила линзы D величина обратная фокусному расстоянию.