Шпаргалка по "Программированию и компьютерам"

Как информационная структура канал  описывается идентификатором, размером и двумя указателями. Конвейеры представляют собой системный ресурс.

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

Работа с очередями сообщений  имеет много отличий от работы с конвейерами:

1)Очереди сообщений представляют возможность использовать несколько дисциплин обработки сообщений: FIFO, LIFO, приоритетный, произвольный доступ.

2)В очередях присутствуют не  непосредственно сами сообщения,  а только их адреса в памяти  и размер. Эта информация размещается  системой в сегменте памяти, доступном для всех задач, общающихся с помощью данной очереди.

 

22. Тупики, повторно  используемые и потребляемые  ресурсы

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

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

Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами:

•число единиц ресурса постоянно;

•каждая единица ресурса или  доступна, или распределена одному и только одному процессу

•процесс может освободить единицу  ресурса, только если он ранее получил  эту единицу.

Расходуемый ресурс (CR) отличается от ресурса типа SR следующим:

•число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются и освобождаются отдельные их элементы выполняющимися процессами, и такое число единиц ресурса является неограниченным; процесс-производитель увеличивает число единиц ресурса, освобождая одну или более единиц, которые он создал;

•процесс-потребитель уменьшает  число единиц ресурса, сначала запрашивая и затем приобретая одну или более единиц. Единицы ресурса, которые приобретены не возвращаются ресурсу, а потребляются.

 

23. Примеры тупиков  на повторно используемые ресурсах, примеры тупиков на потребляемых ресурсах

Пример тупика на ресурсах типа CR

Пусть имеются процессы Пр1, Пр2 и ПрЗ, вырабатывающие сообщения Ml, M2 и МЗ. Эти сообщения представляют собой ресурсы типа CR. Пр1 является потребителем сообщения МЗ, процесс Пр2 должен получить сообщение Ml, ПрЗ ожидает сообщение М2 от Пр2. Каждый из процессов является и поставщиком, и потребителем одновременно, они образуют кольцевую систему  передачи сообщений через почтовые ящики (ПЯ).

Пример тупика на ресурсах типа SR

Предположим, что существуют два  процесса Пр1 и Пр2, разделяющих два ресурса типа SR: R1 и R2. Пусть взаимное исключение доступов к этим ресурсам реализует-ся с помощью семафоров S1 и S2 соответственно.

Процесс Пр 1 Процесс Пр 2

1: P(S2); (5): P(S1);

2: P(S1); (6): P(S2);

3: V(S1); (7): V(S1);

4: V(S2); (8): V(S2);

оба семафора первоначально установлены  в единицу. Данная последовательность вызовов приведет к тупику.

 

24. Необходимые  условия возникновения тупиков

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

• Условие взаимоисключения – когда процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются.

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

• Условие неперераспределяемости – когда ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы.

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

Борьба с возникновением тупиков  может вестись по четырем основным направлением: предотвращение тупиков; обход тупиков; обнаружение тупиков; восстановление после тупиков.

 

25. Модели вычислительных  процессов для изучения проблемы  тупиков:  модель Холта

разработана для исследования параллельных процессов и проблемы тупиков. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причем каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса. Дуга, указывающая из «процесса» на «ресурс», означает запрос одной единицы этого ресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выделение ресурса процессу. Поскольку каждая единица любого ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг, исходящих из ресурса к различным процессам, не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов.

26. Модели вычислительных  процессов для изучения проблемы  тупиков:  модель пространства состояний. Пусть состояние ОС будет сводиться к состоянию различных ресурсов в системе. Состояние системы изменяются процессами, когда они либо запрашивают, либо освобождают ресурс. Пусть эти два состояния будут единственными. Если процесс не блокирован в денном состоянии, он может изменить его на новое. Новое состояние может быть любым из конечного числа возможных. Введенные ограничения приводят к следующим формальным определениям:

- система есть пара значений, где первое значение – множество состояний системы; второе – множество процессов;

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

- процесс заблокирован в состоянии,  если не существует ни одного  состояния, такого что оно равно  текущему;

- состояние S называется тупиковым,  если существует процесс P находящийся в тупике в состоянии S;

- состояние S является безопасным, если для всех состояний оно  не тупиковым.

27. Модели вычислительных  процессов для изучения проблемы  тупиков: вычислительные схемы. Вычислительная схема - это представление в графической форме асинхронной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистров» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления.  Граф потока данных (информационный граф) определяет входные и выходные данные для каждого оператора. Дуга (Ri Sk) от регистра Ri к оператору Sk означает, что данные Riявляются элементом входных данных этого оператора; дуга (Sk Rj) определяет данные Rjкак выходные для Sk. Некоторые данные R могут являться выходными для оператора Si и входными для оператора Sj. Пример графа потока данных для некоторой вычислительной схемы представлен на рисунке 5.1 а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.

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

28. Теоретико-множественное  определение сетей Петри, графовое определение сетей Петри. Пусть мультимножество это множество, допускающее вхождение нескольких экземпляров одного и того же элемента.

Сеть Петри является четверкой , где - конечное множество позиций, ;

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

Позиция называется входом для перехода , если . Позиция называется выходом для перехода , если . Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример. Сеть Петри ,

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

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

29. Маркировка сетей Петри, правила выполнения сетей Петри. Маркировка - это размещение по позициям сети Петри фишек, изображаемых на графе сети Петри точками. Фишки используются для определения выполнения сети Петри. Количество фишек в позиции при выполнении сети Петри может изменяться от 0 до бесконечности. Маркировка сети Петри есть функция, отображающая множество позиций во множество неотрицательных целых чисел. Маркировка , может быть также определена как — вектор , где – число позиций в сети Петри и для каждого – количество фишек в позиции . Маркированная сеть Петри определяется совокупностью структуры сети Петри и маркировки . На рисунке представлена маркированная сеть Петри . Множество всех маркировок сети Петри бесконечно.

 

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

Сеть Петри до запуска перехода (рис. 4.3, а). Сеть Петри после запуска перехода (рис. 4.3, б).

 

                  а                   б 

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

 

30. Моделирование  систем на основе сетей Петри

Представление системы сетью Петри  основано на двух основополагающих понятиях: событиях и условиях. Возникновением событий управляет состояние системы, которое может быть описано множеством условий. Условие может принимать либо значение «истина», либо значение «ложь». Возникновение события в системе возможно, если выполняются определённые условия – предусловия события. Возникновение события может привести к выполнению других условий – постусловий события. В качестве примера рассмотрим следующую ниже задачу моделирования.

Пример 4.2. Моделирование последовательной обработки запросов сервером базы данных. Сервер находится в состоянии ожидания до тех пор, пока от пользователя не поступит запрос клиента, который он обрабатывает и отправляет результат такой обработки пользователю.

Условиями для рассматриваемой  системы являются: а) сервер ждет; б) запрос поступил и ждет; в) сервер обрабатывает запрос; г) запрос обработан.

Событиями для этой системы являются: 1.Запрос поступил. 2. Сервер начинает обработку запроса.  3. Сервер заканчивает обработку запроса. 4. Результат обработки отправляется клиенту. Для перечисленных событий можно составить следующую таблицу их пред- и постусловий

Событие	Предусловия	Постусловия
1 2 3 4	нет а, б в г	б в г, а нет

Такое представление системы легко  моделировать сетью Петри. В сети Петри условия моделируются позициями, события — переходами. При этом входы перехода являются предусловиями соответствующего события; выходы — постусловиями.

На рисунке 4.4. предусловие выполняется  для события 2.

 

 

 

 

Одновременность и конфликт