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.

Избежание

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


 

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

42210. АНАЛИЗ ТОЧНОСТИ СИСТЕМ УПРАВЛЕНИЯ 334.3 KB
  Теоретические сведения. Точность работы любой системы управления наиболее полно характеризуется мгновенным значением ошибки слежения, равной разности между требуемым и действительным значениями регулируемой переменной Однако в большинстве задач управления реальными объектами задающие и возмущающие воздействия заранее точно неизвестны и, следовательно, определить заранее величину для всех моментов времени не представляется возможным.
42211. ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА ДЛЯ СОСТАВЛЕНИЯ ПЛАНА ПРОИЗВОДСТВА (НА ПРИМЕРЕ НЭРЗ) 349 KB
  Всякая модель реального процесса предполагает идеализацию и абстракцию, но они не должны уходить слишком далеко от содержания задачи, чтобы построенная модель не утратила существенных черт моделируемого объекта, т. е. была ему адекватна.
42212. Система математических расчётов Mathcad 508 KB
  Методические указания предназначены для самостоятельного освоения работы с современным математическим пакетом Mathcad, входящим в программу курса. Предлагаемое пособие позволит не только освоить основные операции пакета Mathcad, но и познакомит с основными методами математического анализа.
42213. Облік кредитних операцій 124.5 KB
  Чинним банківським законодавством України кредит (кредитні операції) визначаються як вид активних операцій, пов’язаних з наданням клієнтам коштів у тимчасове користування або прийняттям зобов’язань про надання коштів у тимчасове користування за певних умов
42214. ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ПЬЕЗОЭЛЕКТРИЧЕСКОГО ИСПОЛНИТЕЛЬНОГО УСТРОЙСТВА 1.9 MB
  Целью работы является изучение математических моделей и исследование характеристик исполнительного устройства построенного на основе пьезоэлектрического двигателя микроперемещений. Исполнительные устройства на основе пьезоэлектрических двигателей ПД позволяют получить субмикронную 107108м точность позиционирования в диапазоне перемещения до 103м и при этом обеспечить полосу пропускания свыше 1кГц. На основании приведенных выше уравнений может быть составлена структурная схема пьезоэлектрического исполнительного устройства см.
42215. ИЗУЧЕНИЕ КОНСТРУКЦИИ И ПРИНЦИПА ДЕЙСТВИЯ УГОЛЬНОГО МИКРОФОНА И ЭЛЕКТРОМАГНИТНОГО ТЕЛЕФОНА 106 KB
  Действие угольных микрофонов основано на изменении угольного порошка под влиянием звуковых колебаний воздействующих на мембрану микрофона. Устройство микрофона в упрощенном виде и способ его включения в электрическую цепь показаны на рис. Постоянная составляющая этого тока i0 является током питания микрофона; переменная составляющая разговорным током i .
42216. Огляд систем керування базами даних (СКБД) 80 KB
  Завдання Відповідно до варіанту з таблиці 1 знайти в періодичній літературі та мережі Інтернет інформацію про СКБД. У додатках наводяться формули таблиці схеми якщо вони суттєво полегшують розуміння роботи. Якщо в роботі є рисунки і таблиці які розташовані на окремих аркушах їх слід включати до загальної нумерації. Таблиці Цифровий матеріал доцільно подавати у вигляді таблиць.
42217. Нейросетевое прогнозирование. Методические указания 204 KB
  В наиболее распространенном случае ИНС обучается прогнозу на 1 отсчет времени вперед используя предыдущих значений. Другими словами на вход ИНС предъявляется вектор и требуется чтобы на выходе ИНС появилось значение: . Обучение ИНС производится по известному временному ряду .
42218. Моделирование источника заявок в системе массового обслуживания в среде Simulink 23.5 KB
  Источник генерирует последовательность однородных заявок отличающихся моментами времени появления. Интервалы времени между моментами появления заявок являются случайными величинами с известным законом распределения параметры которого остаются постоянными в течение моделируемого интервала времени . Результатом работы источника заявок является последовательность значений в пределах от нуля до .