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

 

}

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


 

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

82248. История как форма проявления жизни. Объективация жизни во времени. Жизнь как незавершаемая целостность.(О.Шпеннглер, Э. Гуссерль) 33.65 KB
  Объективация жизни во времени. Она может трактоваться в естественно-научном это форма движения материи психологическом это одухотворенность бытия историко-культурном это проявление жизни в разных эпохах биографическом жизнь отдельного человека и философском жизнь как благо смыслах. Она может изучаться с разных позиций например со стороны образа жизни людей стиля и манеры жизни повседневного жизненного мира человека со стороны продолжительности уровня качества жизни и т.
82249. Социальные и культурно- историческиеформы жизни:общее строение и иерархия уровней. Научные и вненаучные представления о формах жизни 41.6 KB
  Державин в своей поэме Бог весьма образно характеризовал проблему человека: Частица целой я вселенной Поставлен мнится мне в почтенной Средине естества я той Где кончил тварей ты телесных Где начал ты духов небесных И цепь существ связал всех мной. Во всех этих случаях отчетливо обнаруживаются две основные методологические тенденции в объяснении природы человека: редукционистская сводящая природу человека либо к биологической либо напротив к социальной его стороне и целостная системная понимающая природу человека как единое...
82250. Время как параметр физических событий и время как мера становления человеческого бытия (общее условие осуществления жизни) 34.6 KB
  Социальное время это продолжительность существования определенных общностей людей общественных явлений отдельных личностей а также социальных процессов. Время зависит также от самого отношения людей ко времени. В истории общества образы времени менялись так образ обратимого времени все возвращается на круги свои сменился на образ необратимого линейного времени время течет от прошлого к настоящему и от него к будущему.
82251. Объективное и субъективное время. Социальное и культурно-историческое время 32.58 KB
  Социальное и культурноисторическое время. В наст вр отмечает Микешина происходит концептуальная революция наука вновь открывает для себя время. В текстах проявляются и формируются и проявляются представления о времени социсторическое время.
82252. Переосмысление категорий пространства и времени в гуманитарном контексте (М.М. Бахтин). Введение понятия хронотопа как конкретного единства пространственно-временных характеристик 32.05 KB
  Бахтин. В гуманитарном познании Бахтина П и В проявляются как совершенно новая идея. Зная идеи о П и В Канта и Бергсона Бахтин находит свое видение этих категорий значимое для современного понимания природы темпоральности и пространственности в познании. Бахтин соединяет действующее сознание и все мыслимые пространственные и временные отношения в единый центр архетектоническое целое.
82253. Коммуникативность (общение учёных) как условие создания нового социально-гуманитарного знания и выражение социально –культурной природы научного познания 34.79 KB
  Нормальная фаза. Эта фаза в истории специальности конструируется ретроспективно только в тех случаях когда новая специальность сформировалась. Нормальная фаза часто завершается опубликованием манифеста в котором содержатся в общих чертах программа разработки проблематики и оценки ее перспективности. Фаза формированиям развития сети характеризуется интеллектуальными и организационными сдвигами приводящими к объединению исследователей в единой системе коммуникаций.
82254. Научные конвенции как необходимость и следствие коммуникативной природы познания 308.25 KB
  Проблемы общения в науке Интерес к структуре формальным моделям диалога и их содержательным возможностям возродившийся в семидесятых годах постепенно привел к формированию такого направления логико-методологических исследований которое со временем получает название...
82255. Рождение знания в процессе взаимодействия коммуницирующих индивидов. Распространение и борьба научных идей. Индоктринация 32.16 KB
  Важную роль в развитии социальногуманитарных науках играет коммуникация ученых диалог между ними. Механизмом их преодоления является постоянный диалог ученых представителей разных школ в социальногуманитарных науках. Диалог является важнейшим видом коммуникации и представляет собой попеременный обмен высказываниями репликами между двумя или более ученымигуманитариями. Диалог может представлять собой определенную дискуссию беседу диспут и т.
82256. Рациональное, объективное, истинное в социально-гуманитарных науках 28.02 KB
  Социальное познание является частным видом научного познания подчиняющимся его критериям и законам. Социальное познание неразрывно связано с предметными справедливо несправедливо добро зло субъективными установки взгляды нормы цели ценностями на основе которых осуществляется познание объекта. Таким образом социальное познание объективно так как изучение объекта общества на определенном этапе развития происходит на основе объективных критериев и законов характерных для научного познания в целом. Социальное познание рационально...