30513
Разделение ресурса
Доклад
Математика и математический анализ
Способы решения проблемы гонок: Локальная копия Синхронизация Метод блокирующей переменной Метод строгого чередования Алгоритм Деккера Алгоритм Петерсона Комбинированный способ Локальная копия Самый простой способ решения копирование переменной x в локальную переменную. В общем виде алгоритм выглядит следующим образом: Поток: while stop { synchronizedSomeObject { {criticl_section} } } Метод блокирующей переменной Суть метода состоит в том что если значение этой переменной равно например 1 то ресурс занят другим...
Русский
2013-08-24
68.3 KB
5 чел.
Доска.
Разделяемый ресурс
Поток 1
Поток 2
Поток 3
Выступление.
Разделение ресурса совместное использование несколькими процессами ресурса вычислительной системы, когда каждый из процессов некоторое время владеет ресурсом.
Разделению подлежат как аппаратные, так программные ресурсы.
Разделяемые ресурсы, которые должны быть доступны в текущий момент времени только одному процессу это так называемые критические ресурсы. Таковыми ресурсами могут быть как внешнее устройство, так и некая переменная, значение которой может изменяться разными процессами.
Необходимо уметь решать две важнейшие задачи:
Важнейшим требованием мультипрограммирования с точки зрения распределения ресурсов является следующее: результат выполнения процесса не должен зависеть от порядка переключения выполнения между процессами, т.е. от соотношения скорости выполнения процесса со скоростями выполнения других процессов.
Рассмотрим пример,
int x; // общая переменная
// Поток 1 while (!stop) { x++; } |
// Поток 2 while (!stop) { if (x%2 == 0) print("x=" + x); } |
Пусть x=0. Предположим, что выполнение программы происходит в таком порядке:
Такие ситуации называются гонками (race conditions) между процессами, а процессы конкурирующими.
Часть программы (фактически набор операций), в которой осуществляется работа с критическим ресурсом, называется критической секцией.
Способы решения проблемы гонок:
Локальная копия
Самый простой способ решения копирование переменной 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; } |
Недостаток метода - заблокированный процесс постоянно находится в цикле, проверяя, не изменилась ли переменная.
Алгоритм Деккера
Алгоритм Деккера программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм Деккера усовершенствован Петерсоном.
Алгоритм имеет следующие ограничения.
Принцип работы - если два процесса попытаются попасть в критическую секцию одновременно, алгоритм позволит войти только одному процессу, номер которого соответствует числу в переменной 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 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера.
Алгоритм имеет следующие ограничения.
Алгоритм Петерсона учитывает отсутствие атомарности в операциях чтения и записи переменных и может применяться без использования команд управления прерываниями.
Алгоритм работает на использовании двух переменных: у каждого процесса есть собственная переменная 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); … } |
Очевидных способов выявления и исправления состояний гонки не существует. Лучший способ избавиться от гонок правильное проектирование многозадачной системы.
А также другие работы, которые могут Вас заинтересовать | |||
34395. | Прогнозирование и планирование объема и структуры промышленного производства | 33 KB | |
На заключительном этапе формируются плановый объем и структура выпуска промышленной продукции с учетом спроса возможностей производства и обеспечения производственными ресурсами. Обосновывается и устанавливается заказ на поставку важнейших видов продукции для государственных нужд. Для прогнозирования спроса и объема производства конкретных видов продукции хорошие результаты дает метод Дельфи . Путем анкетного опроса группы ученых и специалистов по данной проблеме формируется информация по выпуску каждого вида продукции по годам которая... | |||
34396. | Сущность и содержание прогнозирования. Роль и характер прогнозов | 44.5 KB | |
Прогнозирование это процесс разработки прогноза построенный на вероятностном научно обоснованном суждении о перспективах развития объекта в будущем его возможном состоянии и альтернативных путях его достижения. Социальноэкономическое прогнозирование является способом предвидения представления о будущем обусловленном закономерностями общественного развития и действием разнообразных и разнонаправленных факторов в прогнозируемом периоде. В соответствии с Законом О государственном прогнозировании и программах социальноэкономического... | |||
34397. | Сущность планирования. Директивное, индикативное, стратегическое планирование, их характеристика | 47 KB | |
При формировании рыночных отношений в Республике Беларусь необходимо видение перспектив ее экономического и социального развития. Планирование это процесс принятия управленческого решения основанный на обработке исходной информации и включающий в себя определение и научную постановку целей средств и путей их достижения посредством сравнительной оценки альтернативных вариантов и выбора наиболее приемлемого из них в ожидаемых условиях развития. Суть планирования состоит не в разработке и доведении многочисленных показателей до... | |||
34398. | Предмет курса, его место в системе экономических наук | 27 KB | |
Пип наука изучающая экие теории и законы применительно к конкретным условиям производства их специфические проявления в важнейших процессах прва закономерностях темпов и пропорциях с тем чтобы в результате этого изучения с учетом достижений НТП передового опыта обосновать объемы темпы и пропорции общественного производства в целях наиболее эффективного развития экономики. Задача курса состоит в рассмотрении комплекса теоретических методологических организационных вопросов пип экономики на современном этапе. Теория пип является... | |||
34399. | Исторический аспект развития прогнозирования и планирования | 26 KB | |
Экономическая мысль совершая поиск путей становления системы планирования испытывала колебания вступала в противоборство допуская ошибки и избавляясь от них под влиянием реальных явлений хозяйственной жизни. Рассмотрим становление и совершенствование прогнозирования и планирования в бывшем СССР и развитых зарубежных странах. Первый долгосрочный план который представляет интерес с точки зрения общей методологии планирования это план ГОЭЛРО государственный план электрификации России разработанный в 1920 г. | |||
34400. | Развитие и особенности ПИП в зарубежных странах (США, Япония, Франция и др.) | 45.5 KB | |
Для США характерно стратегическое планирование суть которого состоит в выборе главных приоритетов развития национальной экономики ведущую роль в реализации которых играет государство. Основным источником займов на цели разработки и освоения новой технологии является Японский банк развития. Направления стратегического развития разрабатываются в виде целевых государственных программ и сопровождаются комплексом различных финансовых льгот и преференций стимулирующих их реализацию. Она представляет собой модель будущего развития экономики... | |||
34401. | Научные основы методологии прогнозирования и планирования | 30.5 KB | |
Вторая является основой планирования и прогнозирования в странах с рыночной экономикой. Методология прогнозирования и планирования развития экономики определяет основные принципы подходы и методы проведения прогнозных и плановых расчетов раскрывает и характеризует логику формирования прогнозов планов и их осуществления. Принципы это основополагающие правила прогнозирования и планирования т. | |||
34402. | Система показателей планов-прогнозов | 30.5 KB | |
Нормативы показатели в относительном выражении. Лимиты ресурсные показатели представляющие предельно допустимую величину затрат ресурса для достижения установленных конечных результатов. Основными блоками показателей прогнозирования и планирования экономических и социальных процессов являются: показатели производства трудовых ресурсов основных и оборотных фондов капитальных вложений природных ресурсов научнотехнического прогресса финансов и денежного обращения социального развития и уровня жизни населения внешнеэкономических... | |||
34403. | Система прогнозов и планов. Методологические основы их сопряжения | 32 KB | |
Для формирования стратегии и тактики развития экономики разрабатывается система прогнозов включающая прогнозы временного аспекта и по уровням управления а также частные и комплексные прогнозы экономического и социального развития страны и регионов. По масштабу прогнозирования выделяют: макроэкономические прогнозы межотраслевые и межрегиональные прогнозы развития народнохозяйственных комплексов отраслевые и региональные прогнозы прогнозы звеньев экономики: предприятий объединений отдельных производств и продуктов. Во временном аспекте... | |||