Синхронизирующие примитивные системы.

Может находится в одном из двух состояний. Процессы могут останавливаться (засыпать) процессы могут останавливаться засыпать в ожидании освобождения какого-либо системного ресурса. Объектов ядра используют индексы, семафоры, кроме того используются такие программные механизмы как мониторы. Синхронизация с объектом вида происходит через дескриптор является объект и позволяет синхронизировать выполнение потоков принадлежащих разным процессам. Представляет собой двоичный бинарный симофор, который может находится в состоянии СИГНАЛ не СИГНАЛ.

Если ориентированный граф не имеет цикла, то существует линейное упорядочивание вершин такое что: если существует путь от вершины i к вершине j, то i появляется перед j в этом упорядочивании. Это утверждение базируется на теореме из теории графов, которая гласит: две вершины в ориентированном графе взаимносвязанны тогда и только тогда, когда не связанны маршрутом из ориентированных-циклических маршрутах. В таких случаях можно выявить тупиковую ситуацию с помощью приведения графов в соответствии со следующими правилами:

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

2. Граф называется полностью проводимым, если после приведения он не содержит не одной дуги.

3. В системе представленной такой моделью отсутствуют тупиковые ситуации, если соответствующей ей граф полностью проводим.

Пример:

R1 и R2 — ресурсы.

Р1 и Р2 — процессы.

Сети Петри.

Любые системы должны иметь формальное описание для определенного класса систем описание при помощи классической теории автоматов невозможно в частности к таким относятся системы с параллельно функционирующими и асинхронно функционирующими процессами, для моделирования таких систем в 1962г Карлом Петри была предложена специальная сетевая методология(набор сущностей/примитивов, способов их соединения и методов описания различных ситуаций). В теорию разработки ПО сети Петри введены как средство описания одновременного исполнения операций в универсальных системах. При помощи сетей Петри описываются параллельные вычисления.

Сеть Петри это — помеченный ориентированный граф с двумя типами вершин именуемых позициями и переходами, каждая дуга соединяет позицию с переходом или переход с позицией. Компоненты системы и их действия представляются абстрактными событиями: выполнение оператора программ генерация прерывания и т.д. Событие может произойти один раз или многократно. Совокупность действий возникающих при реализации событий дискретной системы образует собой процесс порождаемой системой. События в системе представляются как элементарные(атомарные/неделимые). Обозначение взаимодействий производится при помощи локальных операций называемых условиями реализации событий, каждое условие имеет емкость(количество выполнений) емкость условие: 0— не выполнено, 1—единократное выполнение, n—выполнено n раз.

Определенные состояния условий(предусловия) разрешают реализовываться событию а реализация события изменяет методы условия(постуловия события). События и условия предоставляют из себя пересекающиеся алфавиты, которые называются множеством переходов и множеством мест. Условия (места) и события (переходы) связанны отношением непосредственной зависимости, которое отображается в виде направленных дуг, места из которых ведут дуги на данный переход называется входными местами данного перехода, места на которые приходят дуги данного перехода называются выходными местами. Выполнение условия отображается разметкой сети, т.е помещением в данное место n фишек, где n это емкость условия.

Примеры сетей Петри:

Б) для реализации которой необходимой условии наличие фишек сразу в двух местах, т.е выполнение логического условия И.

В) представляет собой д параллельно выполняющихся синхронизированных процессов в которых синхронизация произведена на первом переходе.

Для моделирования ситуации когда вычислительный процесс попадает в ловушку, которая называется клинч/deadlock.

Ловушка.

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

Число 11.12.12. Продолжение.

Сети петри смотреть в юпад.

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

Програмный канал или пайп, это последовательный файл разделяемый двумя или более процессами который позволяет передавать данные между ними в порядке поступления(FiFo) а также синхронизировать выполнение процессов при условии реализации задачи через потоки. Фактически канал является псевдофайлом поскольку представляет собой буферную память помещение данных в которую осуществляется не записями(как в файл) а потоком байт. Существую именованные и не именованные каналы. Именованные отличаются от не именованных наличием символьного имени, которое позволяет независимым процессам видеть один и тот же канал и взаимодействовать через него. Работа через не именованный канал может осуществляться только связанными процессами, к таким относятся родительские и дочерние процессы связь у которых устанавливается через общие составляющие контекста(см лекцию 2-3). Для именованных и не именованных каналов существую общие принципы механизма их работы:

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

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

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

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

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

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

Очереди сообщений.

Это достаточно старая но все еще актуальная(за счет модернизации) технология. Данный механизм позволяет обмениваться структурированными данными имеющие следующие атрибуты:

1. Тип сообщения.

2. Длина сообщения.

3. Содержимое сообщение.

В Виндоус каждое приложение имеет свою собственность очередь сообщений{при запуске приложения создается объект ядра}. Обрабатываются сообщения при помощи оконной процедуры, код этой процедуры исполняется создавшим окно потоком вплоть до 32х битных систем очередь была реализована как однонаправленный список и максимум 8-мь сообщений. В 32х битных приложениях очередь реализована как двунаправленый список и неограниченной длины. Возможны два варианта обработки сообщений из очереди синхронная и асинхронная. Синхронная обработка сообщений подозревает что прцоедура передачи сообщений посылает сообщения в процедуру обработки сообщений находящуюся в программе приемнике и блокируется до тех пор пока сообщение не будет обработано, если обработка прошла успешно, то процедура обработчик освобождается и принимает новое (следующее сообщение). Асинхронная обработка сообщений, сообщения помещаются в очередь программы приемника после чего процедура отправившая сообщение возвращается(деблокируется) и продолжает свое исполнение, проблемы в этом случае возникают тогда, когда отправленное сообщение не может быть обработано в программе приемнике.

Запирая ресурс при помощи симафора.

Клиент производит чтение данных из разделяемой памяти и освобождает ее при помощи симофора.

Механизм разделяемой памяти очень похож на механизм проецирования файлов в памяти, который буде рассмотрен чуть позже, однако имеет преимущества: непосредственная работа сервера и клиента с областями ВАП.

Продолжении лекции.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: