30507

Процессы и потоки. Объекты межпроцессорной синхронизации. Понятие гонок и взаимной блокировки

Доклад

Математика и математический анализ

Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы такие как память тогда как процессы не разделяют этих ресурсов. dedlock ситуация в многозадачной среде или СУБД при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов занятых самими этими процессами. Процессы в текущий момент удерживают полученные ранее ресурсы могут делать запросы на получение новых ресурсов. Условие отсутствия принудительного освобождения ресурсов англ.

Русский

2013-08-24

24.85 KB

1 чел.

Процессы и потоки. Объекты межпроцессорной синхронизации. Понятие гонок и взаимной блокировки

Потоки и процессы — это связанные понятия в вычислительной технике. Оба представляют из себя последовательность инструкций, которые должны выполняться в определенном порядке. Инструкции в отдельных потоках или процессах, однако, могут выполняться параллельно. Реализация потоков выполнения и процессов в разных операционных системах отличается друг от друга, но в большинстве случаев поток выполнения находится внутри процесса. Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы, такие как память, тогда как процессы не разделяют этих ресурсов. В частности, потоки выполнения разделяют инструкции процесса (его код) и его контекст (значения переменных, которые они имеют в любой момент времени).

На одном процессоре многопоточность обычно происходит путём временного мультиплексирования (как и в случае многозадачности): процессор переключается между разными потоками выполнения. Это переключение контекста обычно происходит достаточно часто, чтобы пользователь воспринимал выполнение потоков или задач как одновременное. В многопроцессорных и многоядерных системах потоки или задачи могут реально выполняться одновременно, при этом каждый процессор или ядро обрабатывает отдельный поток или задачу.

Потоки выполнения отличаются от традиционных процессов многозадачной операционной системы тем, что:

  1.  процессы, как правило, независимы, тогда как потоки выполнения существуют как составные элементы процессов
  2.  процессы несут значительно больше информации о состоянии, тогда как несколько потоков выполнения внутри процесса совместно используют информацию о состоянии, а также память и другие вычислительные ресурсы
  3.  процессы имеют отдельные адресные пространства, тогда как потоки выполнения совместно используют их адресное пространство
  4.  процессы взаимодействуют только через предоставляемые системой механизмы связей между процессами
  5.  переключение контекста между потоками выполнения в одном процессе, как правило, быстрее, чем переключение контекста между процессами.

Объекты межпроцессорной синхронизации:

Взаимоисключения

Объекты-взаимоисключения (мьютексы, mutex - от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу. Сигнальное состояние объекта (т.е. состояние "установлен") соответствует моменту времени, когда объект не принадлежит ни одному потоку и его можно "захватить". И наоборот, состояние "сброшен" (не сигнальное) соответствует моменту, когда какой-либо поток уже владеет этим объектом. Доступ к объекту разрешается, когда поток, владеющий объектом, освободит его.

Для того, чтобы объявить взаимоисключение принадлежащим текущему потоку, надо вызвать одну из ожидающих функций. Поток, которому принадлежит объект, может его "захватывать" повторно сколько угодно раз (это не приведет к самоблокировке), но столько же раз он должен будет его освобождать с помощью функции ReleaseMutex.

События

Объекты-события используются для уведомления ожидающих потоков о наступлении какого-либо события. Различают два вида событий - с ручным и автоматическим сбросом. Ручной сброс осуществляется функцией ResetEvent. События с ручным сбросом используются для уведомления сразу нескольких потоков. При использовании события с автосбросом уведомление получит и продолжит свое выполнение только один ожидающий поток, остальные будут ожидать дальше.

Функция CreateEvent создает объект-событие, SetEvent - устанавливает событие в сигнальное состояние, ResetEvent-сбрасывает событие. Функция PulseEvent устанавливает событие, а после возобновления ожидающих это событие потоков (всех при ручном сбросе и только одного при автоматическом), сбрасывает его. Если ожидающих потоков нет, PulseEvent просто сбрасывает событие.

Семафоры

Объект-семафор - это фактически объект-взаимоисключение со счетчиком. Данный объект позволяет "захватить" себя определенному количеству потоков. После этого "захват" будет невозможен, пока один из ранее "захвативших" семафор потоков не освободит его. Семафоры применяются для ограничения количества потоков, одновременно работающих с ресурсом. Объекту при инициализации передается максимальное число потоков, после каждого "захвата" счетчик семафора уменьшается. Сигнальному состоянию соответствует значение счетчика больше нуля. Когда счетчик равен нулю, семафор считается не установленным (сброшенным).

Критические секции

Объект-критическая секция помогает программисту выделить участок кода, где поток получает доступ к разделяемому ресурсу, и предотвратить одновременное использование ресурса. Перед использованием ресурса поток входит в критическую секцию (вызывает функцию EnterCriticalSection). Если после этого какой-либо другой поток попытается войти в ту же самую критическую секцию, его выполнение приостановится, пока первый поток не покинет секцию с помощью вызова LeaveCriticalSection. Похоже на взаимоисключение, но используется только для потоков одного процесса.

Существует также функция TryEnterCriticalSection, которая проверяет, занята ли критическая секция в данный момент. С ее помощью поток в процессе ожидания доступа к ресурсу может не блокироваться, а выполнять какие-то полезные действия.

Защищенный доступ к переменным

Существует ряд функций, позволяющих работать с глобальными переменными из всех потоков не заботясь о синхронизации, т.к. эти функции сами за ней следят. Это функции InterlockedIncrement/InterlockedDecrement, InterlockedExchange,InterlockedExchangeAdd и InterlockedCompareExchange. Например, функция InterlockedIncrement увеличивает значение 32-битной переменной на единицу - удобно использовать для различных счетчиков. Более подробно об этих функциях см. в документации.

Состояние гонки (англ. race condition) — ошибка проектирования многопоточной системы или приложения, при которой работа системы или приложения зависит от того, в каком порядке выполняются части кода.

Взаимная блокировка (англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами.

Условия возникновения взаимной блокировки

Было показано, что для возникновения ситуации взаимной блокировки, необходимо выполнение следующих четырех условий одновременно:

  1.  Условие взаимного исключения ( англ. mutual exclusion ). Каждый ресурс в текущий момент или занят ровно одним процессом или свободный. То есть, ресурсы находятся в режиме эксклюзивного пользования.
  2.  Условие удержания и ожидания ( англ. hold and wait ). Процессы, в текущий момент удерживают полученные ранее ресурсы, могут делать запросы на получение новых ресурсов.
  3.  Условие отсутствия принудительного освобождения ресурсов ( англ. no preemption ). Невозможно заставить процесс освободить ранее полученные ресурсы.Процесс, обладающий ресурсами, должен сам их увольнять.
  4.  Условие циклического ожидания ( англ. circular wait ). Должно существовать кольцевая последовательность из двух или более процессов, каждый из которых ожидает увольнение ресурса, удерживаемого следующим членом последовательности. Иными словами, должно существовать множество процессов {P0, P1,... Pn}, так, что процесс P 0 ожидает освобождения ресур процесса P 1, P 1 ожидает P 2,..., P N - 1 ожидает P N, а P N ожидает освобождения ресурсов процессом P 0.

Для возникновения ситуации взаимной блокировки, необходимо выполнение всех четырех условий одновременно. Если хотя бы одно из условий не выполняется, взаимная блокировка невозможна.

Обработка тупиковых ситуаций

Обработку и обращение с ситуациями взаимной блокировки можно условно разделить на:

Пренебрежение проблемой вообще (т. н. "Страусиный алгоритм»).

Выявление и восстановление. Позволить произойти взаимному блокированию, выявить его, и выполнить некоторые действия.

Динамическое избежание взаимной блокировки путем правильного распределения ресурсов.

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

Первый подход используется в большинстве современных операционных систем : правильное поведение в ситуации взаимной блокировки является ответственностью разработчика ПО.

Предотвращение

Как было сказано выше, для возникновения ситуации взаимной блокировки необходимо одновременное выполнение четырех условий. Если один из них не выполняется, то ситуации взаимной блокировки возникать не будут. Здесь приведены описания подходов к каждой из условий.

Взаимное исключение

Условие взаимного исключения, или эксклюзивного пользования должна выполняться для неразделимых ресурсов. Например, принтер должен использоваться экслюзивно, одним процессом. Однако, некоторые раздельные ресурсы, такие, как доступ к файлам на чтение, могут раздаваться многим процессам.

В общем случае, условие взаимного исключения невозможно обойти, поскольку некоторые из ресурсов должны использоваться только в экслюзивно режиме.

Содержание и ожидания

Для невыполнения этого условия, каждый раз, когда процесс требует новые ресурсы, он должен не содержать другие ресурсы. Возможны следующие алгоритмы:

Получать все ресурсы в начале работы процесса до выполнения остальных операций.

Получать новый ресурс при условии высвобождения занятых ресурсов. Перед запросом нового ресурса, процесс освобождает занятые им ресурсы.

Недостатком первого алгоритма является неэффективное использование и простой ресурсов. Также, существует возможность «голода»: в перегружены системе, процесс, требующий несколько популярных ресурсов, может никогда их не получить, поскольку хотя бы один из них может быть занят другим процессом.

Принудительное освобождение ресурсов

Для невыполнения условия отсутствия принудительного освобождения ресурсов, возможны следующие алгоритмы:

В случаях, когда процесс запрашивает доступ к ресурсу, который не может быть сразу предоставлено, он освобождает остальных занятых ресурсов, и передает их в очередь на запрос. Работу процесса будет возобновлено после получения доступа ко всем ресурсам в очереди (старые и новые ресурсы).

Сначала проверить возможность предоставления ресурса, если возможность предоставить ресурс отсутствует из-за использования его другим процессом, который ожидает освобождения некоторых других ресурсов, то освободить этот ресурс, и передать его процесса-заказчику. Если необходимый ресурс как недоступен, так и процесс, что его использует, не ожидает освобождения других ресурсов, то перевести процесс, подал запрос, в состоянии ожидания. Во время ожидания, некоторые содержащиеся ним ресурсы могут быть освобождены из-запросы третьих процессов. Процесс возобновляет работу после того, как получит необходимые ресурсы и ресурсы, которые были уволены во время ожидания.

Такой алгоритм используется для ресурсов, состояние которых может быть легко сохранены и воспроизведены, таких как регистры процессора или пространства памяти.

Циклическое ожидание

Избежания циклического ожидания достигается установлением порядка доступа к ресурсам различных типов.

Пусть  - множество типов ресурсов. Отождествит с каждым из них целое число, что позволит сравнивать ресурсы и устанавливать приоритеты (см. частично упорядоченное множество ).

Теперь, во избежание циклического ожидания, установим следующее правило: процесс может запрашивать ресурсы только в возрастающем порядке номеров. Как вариант, процесс должен освобождать ресурс с большим порядковым номером перед подачей запроса на ресурс с меньшим номером.

Несмотря на то, что установление и соблюдение правильного порядка получения доступа к ресурсам является ответственностью разработчика ПО, существуют специализированные инструменты для проверки соблюдения порядка и сообщения об ошибках. Одним из примеров является программа witness, работающий на операционных системах семьи BSD.

Избежание

Для избежания тупиковых сутаций, программы должны заранее предоставлять операционной системе информацию о ресурсах, которые будут использованы процессом во время работы. Имея эту информацию операционная система может решать на удовлетворение каких запросов процесс может подождать. Чтобы решить, должен процесс ждать, операционная система должна учитывать доступные ресурсы, ресурсы выделены процессам и будущие запросы, которые могут сделать процессы.


 

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

43203. Синтез и расчёт кулисного механизма 631 KB
  В механизмах привода поперечно строгальных станков используется механизм, обеспечивающий главное возвратно-поступательное движение резания. Основная масса механизмов использующихся в данных станках это кулисные механизмы. Они обеспечивают заданную скорость рабочего хода и повышенную скорость холостого хода. Расчёт и проектирование данных механизмов является важным этапом в образовании инженера. В курсе предмета «Теория машин, механизмов и манипуляторов» получаются навыки расчёта механизмов машин. Комплексным подходом к закреплению полученных знаний является выполнение курсового проекта по данному курсу. В курсовом проекте осуществляется синтез и расчёт кулисного механизма, построение и расчёт зубчатого зацепления и кулачкового механизма. При выполнении работы используются все знания, полученные за курс предмета.
43204. Разработка эскизного проекта автоматической линии 379.5 KB
  Технические требования к детали Технологичность конструкции детали с точки зрения обработки на автоматической линии. Технические требования к детали К данной детали вал-шестерня применяются следующие технические требования: 1. Масса детали 1.
43205. Разработка канала для комплексной скважинной аппаратуры 1.35 MB
  Основная погрешность канала измерения температуры Дополнительная погрешность канала измерения температуры Основная погрешность канала измерения влажности Дополнительная погрешность влагомера Влажность нефти является одним из важнейших технологических параметров. На разных этапах добычи и подготовки нефти она определяет правильность эксплуатации нефтяного пласта, интенсивность эмульгирования водо-нефтяной смеси в процессе ее перекачки, эффективность процессов деэмульсации и качество товарной нефти, поступающей на переработку. С влагосодержанием тесно связано также содержание солей, которые причиняют немалый вред оборудованию нефтеперерабатывающих заводов.
43206. АНДРЕЙ БИТОВ, ЗАХАР ПРИЛЕПИН, МИХАИЛ ЕЛИЗАРОВ: ХУДОЖЕСТВЕННЫЕ (ЛИТЕРАТУРНЫЕ) ПАРАЛЛЕЛИ 450.5 KB
  Объект нашей дипломной работы – литературный экстремизм всех трёх авторов, находящий выражение как в индивидуальных авторских стилях, так и во взаимодействии поэтических и прозаических элементов, так и в определённой философской системе, выстраиваемой в ходе повествования.
43207. Привод шаровой мельницы 2.03 MB
  Выбираем асинхронный электродвигатель закрытый обдуваемый единой серии АИР мощностью = 15 кВт и синхронной частотой вращения = 3000 об/мин
43208. Проектування привіду до стрічкового конвейєра за схемою та графіком навантаження 1.35 MB
  Закриті зубчасті передачі при коловій швидкості змащуються зануренням їх в мастило, а також за рахунок масляного туману, який утворюється за рахунок великої колової швидкості. Контактне напруження при швидкості дорівнює 475 МПа. За цими даними вибираємо необхідну в’язкість мастила і вибираємо мастило: індустріальне леговане, для зубчастих передач ИРП-150. одноступінчатого редуктора.
43209. Определение основных параметров бульдозера ДЗ-171 на базе трактора Т-170 957.5 KB
  Бульдозеры как навесное оборудование на тракторы, тягачи и другие базовые машины широко распространены, что объясняется простотой их конструкции, высокой производительностью, возможностью их использования в самых разнообразных грунтовых и климатических условиях и относитнльно низкой стоимостью выполненных работ. Применяются они в дорожном, железнодорожном, горнорудном, мелиоративном и ирригационном строительстве. Для большинства современных гусеничных бульдозеров экономически выгодная дальность дальность перемещений в настоящее время не превышает 60-80м, колесных 100-150м.
43210. Проектирование станочного приспособления 1.5 MB
  На основании этой комплексной детали будем разрабатывать и проектировать станочное приспособление. Технические характеристики для САТ630 Наибольший диаметр обрабатываемого изделия мм: над станиной 720 над суппортом 560 Расстояние между центрами мм 1 000 1 500 2 500 Максимальное перемещение суппорта мм: по оси Х 400 по оси Z 1 100 1 600 2 600 по оси Y 55 65 Максимальный вес обрабатываемой детали кг: в патроне 300 в центрах 800 Диаметр отверстия в шпинделе мм 102 166 Пределы частот вращения...
43211. Разработка автоматизированной системы анализа финансового состояния предприятия в условиях неопределенности 1.47 MB
  Основной целью проведения анализа финансового состояния организаций является получение объективной оценки их платежеспособности, финансовой устойчивости, деловой и инвестиционной активности, эффективности деятельности. Для проведения анализа финансового состояния используются следующие группы показателей, характеризующих различные аспекты деятельности организации...