30507

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

Доклад

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

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

Русский

2013-08-24

24.85 KB

7 чел.

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

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

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

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

  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.

Избежание

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


 

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

21364. Аппаратура АПОА: приемоиндикатор Р-381Т1-3 25.68 KB
  Вопрос№1 Назначение и технические данные ПИ Р381Т13 при работе в составе АПОА предназначен для автоматического определения направления пеленга на источники радиоизлучений. Состав: трёхканальное радиоприёмное устройство РПУ; блок индикации пеленга ИП; блок управления; два блока питания для РПУ и ИП. Для уменьшения ошибок пеленгования предусмотрено автоматическое выравнивание характеристик каналов и поддержание их идентичности. Для слухового контроля радиопередач в ПИ имеется слуховой тракт...
21365. Аппаратура АПОА: анализатор спектра Р-399Т 20.22 KB
  В составе АПОА анализатор работает с РПУ ПИ Р381Т13 на промежуточной частоте 215 кГц значение частоты выбирается переключателем ВХ. ЧАСТОТА кГц. В режиме ОБЗОР обеспечивается частотный анализ спектров сигналов в полосе обзора 025 кГц; 1кГц; 3кГц; 12кГц и 48кГц выбирается переключателем ОБЗОР кГц. ЧАСТОТА кГц включается соответствующий гетеродин 488; 575; 825 или 860 кГц.
21366. Аппаратура передающего тракта : устройство модулирующих сигналов 59.19 KB
  В состав блока входят: ячейки ЧТ1; ячейки ЧТ2; ячейка ХИП; ячейка преобразователя кода. Сдвиговые частоты с шагом 10 Гц вверх и вниз от несущей частоты 128000 Гц формируются в ячейках ЧТ1 и ЧТ2. Сформированные в ячейках ЧТ1 напряжения частотой 128 F кГц и в ячейках ЧТ2 128 F кГц поступают в ячейку ХИП. В ячейках ХИП формируется напряжение представляющее собой хаотическую последовательность импульсов.
21367. Аппаратура передающего тракта : возбудитель «ЛАЗУРЬ 50.33 KB
  Время настройки по коду частоты не более 03 сек. Устройство и принцип работы Возбудитель построен по принципу супергетеродина с автоматической настройкой по коду частоты с тройным в КВ диапазоне и двойным в УКВ диапазоне преобразованием частоты с использованием в качестве гетеродинов синтезаторов частот. Для переноса сигнала помехи с поднесущей частоты 128 кГц поступающей с УМС в диапазон рабочих частот 15 30 МГц используются три преобразования поднесущей частоты с помощью эталонных колебаний трёх гетеродинов формируемых в...
21368. Аппаратура передающего тракта : усилитель мощности АСП Р378А,Б 52.83 KB
  УРУ построен по двухтактной схеме на 12 лампах ГУ74Б. Один низковольтный: питает предварительный усилитель накалы ламп цепи смещения управления сигнализации и защиты. Два высоковольтных питают анодные и экранные цепи ламп УРУ. Выполнен по двухтактной схеме на 12ти лампах ГУ74Б по схеме усилителя бегущей волны для чего в цепи управляющих сеток ламп включены сеточные линии индуктивности и ёмкости с волновым сопротивлением 100 Ом.
21369. Аппаратура передающего тракта : усилитель мощности АСП Р325У 121.71 KB
  Устройство и принцип работы АСП Р 325У и Р378АБ Занятие №11Аппаратура передающего тракта : усилитель мощности АСП Р325У ВНИМАНИЕ: В зависимости от времени изготовления изделия названия блоков и некоторые обозначения в функциопальных и принципиальных схемах технической документации могут отличаться от приведённых в пособии; имеют место некоторые разночтения в эксплуатационной документации по причине недостаточно тщательной её проработки изготовителем Пользуйтесь конкретной...
21370. Антенно- фидерные системы АСП Р325У и Р378А,Б 736.89 KB
  ПЕРЕДАЮЩАЯ АФС СТАНЦИИ Р325У Передающая АФС состоит из одной широкодиапазонной антенны ГУ107 которая обеспечивает секторное излучение земных волн во всём диапазоне частот. У опорных стоек и у основания мачты к проводам антенны подключаются нагрузочные сопротивления кабельного типа длиной по 100м. Для согласования двухпроводного фидера антенны с несимметричным выходом передатчика служит согласующесимметрирующий трансформатор блок ГУ462. У опорных стоек и у основания мачты к проводам антенны...
21371. Устройство управления станцией Р325У и Р378А,Б 44.95 KB
  Назначение ТД состав УУС. УУС предназначено для автоматизированного управления приёмоанализирующей и передающей аппаратурой в соответствии с выбранным способом управления и режимом работы станции. УУС формирует команды с помощью которых устройства входящие в состав станции обмениваются информацией по заданному алгоритму. УУС выполняет следующие основные операции: формирование команд ПУСК панорамного обнаружителя; приём команд снятия пеленга и точной настройки; считывание информации с панорамного...
21372. Аппаратура передачи данных и связи 103.36 KB
  Устройство и принцип работы АСП Р 325У и Р378АБ Занятие №14Аппаратура передачи данных и связи Состав и назначение РРС Р 415В предназначена для обмена телекодовой информацией с АПУ Р330К и организации служебной связи при централизованном режиме управления. В режиме КОНТРОЛЬ предусмотрена возможность ручного контроля узлов. В режиме РАБОТА обеспечивается индикация уровня входных сигналов ПРМ по прибору БКУ которая осуществляется схемой формирования уровней...