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

 

}

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


 

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

22671. Досліди Франка і Герца по визначенню потенціалів іонізації 536 KB
  Докази квантування рівнів енергії електронів в атомі були отримані в дослідах Франка і Герца 1913. Порція енергії 49 еВ передається атому ртуті а енергія електрона зменшується на ту ж величину. При подальшому збільшенні потенціалу U зона зіткнень електронів з атомами ртуті зсувалась до катода К і електрони вже встигали набрати достатньо енергії після зіткнення для подолання UЗ ділянка CD. Знаючи початкову і кінцеву енергію електрона тобто його енергію до і після непружнього співудару можна вирахувати положення збуджених рівнів...
22672. Методи реєстрації і спектрометрії ядерних випромінювань 196.5 KB
  Під ядерним випромінюванням розуміють частинки що утворюються в наслідок ядерних перетворень. Частинки випромінення поділяють на 3 групи: 1. Заряджені частинкиер альфачастинки осколки ділення. Нейтральні частинкинейтрони.
22673. Нелінійна поляризованість. Явище генерації гармонік 50.5 KB
  Теорія лінійної поляризованості всановлює залежність показника заломлення від частоти. Нелінійна квадратична поляризованість вміщує різні комбінаційні частоти початкових електромагнітних хвиль. Отже породжені єю вторинні хвилі мають тіж самі різні комбінаційні частоти і росповсюджуються з різними швидкостями в відповідності до закону дисперсії. Інтерференція може відбуватися лише між хвилями однакової частоти випроміненими в різних точках середовища.
22674. Хвильові властивості частинок. Хвилі де Бройля 46 KB
  Експериментально доведено, що частинки такі як електрон нейтрон і т.д. проявляють хвильові властивості. Ефект Рамзауера (коли електрони налітають на шар атомів і спостерігалось зменшення ефективного перерізу розсіяння при малій шв.) був першим, хоч і не зразу усвідомленим експериментальним фактом, в якому проявлялись хвильові властивості
22675. Рівняння Шредінгера. Інтерпретація хвильової функції 65.5 KB
  В квантовій механіці рівняння Шредінгера відіграє ту ж роль що і рівняння руху Ньютона в класичній механіці і рівняння Максвела в електродинаміці.Розглянемо тримірне хвильове рівняння і застосуємо його до хвиль де Броля. Найбільш важливим частковим випадком рішення хвильового рівняння є рішення виду: 2. Оскільки [потенціальна енергія ] рівняння 3 набуває вигляду стаціонарне рівняння Шреденгера оскільки вважалося що а значить і не залежать від часу.
22676. Співвідношення невизначеності Гейзенберга та приклади його проявів 63.5 KB
  Дві фізичні величини не можуть мати одночасно певні значення в жодному стані якщо їх оператори не комутують. В довільному стані фізичні величини відповідні цим операторам мають середнє значення визначені інтегралами: . З цієї формули випливає що якщо в деякому стані імпульс має певне значення =0 то координата х в цьому стані невизначена зовсім і навпаки. Згідно отриманій нерівності мікрочастинка не може знаходитись у стані строгого спокою який характеризується значеннями .
22677. Енергетичний спектр атома водню. Правила відбору 67 KB
  Сукупність спектральних ліній спектральні серії. Пізніше були досліджені серії в ультрафіолетовій і інфракрасній обл. Перша лінія кожної серії відповідає мінімальному значеню n і має мінімальну частоту. По мірі збільшення n лінії кожної спектральної серії згущуються частота їх зростає.
22678. Хвильові функції. Системи тотожних частинок. Принцип Паули 65.5 KB
  Системи тотожних частинок. Вони тотожні є симетрія: при перестановці місцями частинок не змінюється. Нехай оператор перестановки частинок: ; Т. Для N частинок N парних перестановок; оператор перестановок .
22679. Розподіл Фермі-Дірака і Бозе-Ейнштейна 132 KB
  Бозони частинки з цілим або або нульовим спіном можуть знаходитись в межах даної системи в однаковому стані і в обмеженій кількості. Тоді енергія системи ; число част в му стані. що знаходяться в стані. Нехай номер енергетичного рівня; кратність його виродження число станів на му рівні що мають одне значення енергії тоді ; позначимосереднє число частинок в одному стані.