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.

Избежание

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


 

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

695. Кавказская война 1817-1864 годов 102.5 KB
  Деятельность А.П. Ермолова на Кавказе и формирование идеологии мюридизма. Основные этапы войны, имамат: военно-теократическое государство Шамиля. Завершающий этап Кавказской войны.
696. Заселение Северного Кавказа и политика Российской колонизации 103 KB
  Заселение земель Северного Кавказа калмыками и туркменами в 16-18 веках. Состояние горских обществ накануне российской колонизации: особенности феодальных отношений. Взаимоотношения народов Северного Кавказа с Россией в 16-17 веках, первые русские поселения. Политика России на Северном Кавказе в 18-первой половине 19 веков, возведение оборонительных линий и заселение казачеством северокавказских земель. Становление российской администрации на Северном Кавказе и добровольное присоединение северокавказских народов к России.
697. Использование графики в приложениях Windows Forms 108 KB
  Разработать приложение с графическим интерфейсом пользователя, которое позволяет рисовать заданную геометрическую фигуру в клиентской области главного окна, строит и отображает график заданной функции
698. Международная экономическая интеграция 66.5 KB
  Предпосылки и цели международной интеграции. Этапы международной интеграции. Типы интеграционных объединений. Результаты интеграции. Процесс экономического взаимодействия стран, приводящий к сближению хозяйственных механизмов, принимающий форму межгосударственных соглашений.
699. Получение запросов и отчетов в базе данных MS Access 52 KB
  освоение приемов работы с готовой базой данных по созданию простых и сложных запросов и отчетов. Использование связей между таблицами для получения информации из двух и более таблиц.
700. Общая характеристика WWW 124.5 KB
  История возникновения WWW, понятие гипертекста. Интерфейс Web-приложений при работе в сети Internet. Гипертекстовая информационная система World Wide Web. Базы данных Gopher и поисковая система Veronica.
701. Моделирование прохождения сигнала через некогерентный и когерентный приемные тракты 64.5 KB
  Формирование сигнала на выходе приемника с линейным детектором и с фазовым детектором. Наблюдение интерференции сигналов от целей, разделенных интервалом меньше длительности импульса. Оценка влияния длительности зондирующего импульса на разрешение сигналов по времени.
702. Технология составления интерактивного кроссворда средствами Excel 83 KB
  Набор названия или заголовка кроссворда. Заполнение скелета кроссворда. Создание рамочки клеток кроссворда.(вкладка Главная. Панель Шрифт). Проверки правильности результатов.
703. Реализация модели Ханойские башни 56.5 KB
  Разработать программу на языке C#, реализующую модель игры Ханойские башни. В данной курсовой работе спроектирована и разработана программа на языке C#, которая на основе запрошенных у пользователя входных данных моделирует Ханойские башни или позволяет разложить их вручную.