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

 

}

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


 

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

29594. Критерии характеристики медианосителя 19.63 KB
  Селективность аудитории избирательность ЦА udience selectivity свойство медианосителя доводить информацию до определенного сегмента потребителей при минимальном охвате незаданного сегмента потребителейт. Потенциал охвата rech potentil способность медианосителя собрать аккумулировать максимальное количество людей в качестве своей аудитории. Скорость аккумулирования аудитории speed of udience ccumultion показатель количества выходов или количества времени необходимых медианосителю для того чтобы охватить всю свою...
29595. Медиапланирование 12.03 KB
  Медианоситель конкретный представитель медиаканала где размещается рекламное сообщение. Медианоситель отбирается по качественным и количественным показателям. Медиамикс размещение рекламных материалов сразу в нескольких СМИ и как правило под типовым набором смеси из СМИ медиамикс понимается комбинация ТВ Радио Пресса Наружка. Долю охваченной и неохваченной аудитории при медиамиксе вычисляем формулам теории вероятности: 1Pb = 1P 1Pb где Pb охваченная медиамиксом аудитория P аудитория охваченная первым медиа Pb...
29596. Технологии нейро-лингвистического программирования (НЛП) 20.25 KB
  Технологии нейролингвистического программирования НЛП Изначально задумывалась как технология совершенствования личности. 5 моделей жизненных стратегий: иметь действовать знать относится к какомуто классу обществу принадлежать к быть кемто Техники НЛП: Мозг лучше справляется с позитивными целями негативные: не упади не пролей не проходите мимо Ярка творческая визуализации поставленной цели визуально запах звук Принцип уподобления приобщиться к карте реальности достичь целей как какойто человек которым...
29597. Психология памяти в медиапланировании. Исследования памяти в рекламе 15.49 KB
  При поступлении новых элементовстарые вытесняются последниезапоминаютсяэффект давности Во и Норман: Первичная система кратковременного хранения обладающая ограниченным объемом где инфо теряется за счет вытеснения старых элементов. Виды хранения: Акустическая Сенсорноеосуществление на этапе без участия сознания фотографичинфо сохраняется с фотографической точностью и не поддается контролю со стороны субъекта. 2 Для долговремен памяти характерно обращение к прошлому опыту поиска там инфо необходимой для понимания настоящего....
29598. Возникновение коммуникации. Социально-экономические факторы развития коммуникации 14.74 KB
  Возникновение коммуникации. Социальноэкономические факторы развития коммуникации. Выделяют два подхода к коммуникации: механистический однонаправленный процесс кодирования и передачи информации от источника и приема информации и получателем сообщения и деятельностныйсовместная деятельность участников коммуникации в ходе которой вырабатывается общий взгляд на вещи и действия с ними. Целями коммуникации являются: обмен и передача информации; формирование умений и навыков развитие профессиональных качеств; формирование отношения к себе к...
29599. Схема и сущность коммуникативного процесса. Виды шумов в коммуникации 44.59 KB
  Схемы Большое распространение получила линейная модель коммуникации разработанная Лассуэлом и включающая 5 элементов: Кто передает сообщение коммуникатор Что передается сообщение Как осуществляется передача канал Кому направлено сообщение аудитория С каким эффектом эффективность Р. К функциональным элементам относятся: источник информации продуцирующий сообщение; отправитель кодирующий сообщение в сигналы; канал проводящий это сообщение; получатель; цель или место назначения. Преимущество данной схемы состоит в...
29600. Виды и уровни коммуникации. Особенности массовой коммуникации 17.78 KB
  декодирование кодированиеобратная связь и тп особенности публичный характер открытость ограниченный и контролируемый доступ к средствам передачи опосредованность контактов множество реципиентов влияние институциональных предписаний особенности смк рассредоточение в пространстве многоконачльность СМК делятся на СМИ слухи и наружную рекламу 1. Слухи оказывают большое влияние на формирование общественного мнения благодаря обсуждению в малых приватных группах без освещения в СМИ. СМИ являются основным видом массовых...
29601. Массовая коммуникация в современном обществе: функциональный подход 15.29 KB
  Если это осуществляется в деятельности СМИ то таким образом ими реализуется важнейшая социальная функция интеграционная.фии МК: 1 обозрение окружающего мира: медиа расширяют горизонты познания индивида информационная функция; 2 корреляция с социальной структурой и ответственностью общества воздействие на него и его познание через обратную связь корреляционная функция проявляющаяся также в объяснении и интерпретации информационных сообщений в обеспечении поддержки существующим властям и господствующим нормам; 3 трансмиссия...
29602. Массовая коммуникация в современном обществе 17.28 KB
  Информационная функция: информирование о событиях и условиях жизни в обществе и мире; информационное обеспечение инновационных процессов; II. Функция социальной связи: интерпретация происходящего; поддержка существующих норм и властных отношений; социализация; координация разнонаправленной социальной активности формирование общественного согласия; III. Функция обеспечения преемственности: выражение образцов доминирующей культуры узнавание субкультур новых культурных направлений; поддержание общности социальных ценностей; IV....