Элементы теории вычислимости: вычислимость и разрешимость, интуитивное и точное понятие алгоритма, вычислимые функции, машина Тьюринга, массовые алгоритмические проблемы.

Вычислимость, разрешимость

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

Теоретическое программирование – это математическая дисциплина, изучающая синт. и семантические свойства программ, их структуру, преобразования и процесс их составления и исполнения. Исследования в области теоретического программирования:

1) теоретические основы программирования;

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

3) семантическая теория программ (изучает методы формального описания семантики);

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

5) прикладные задачи теоретического программирования (разработка и обоснование алгоритмов трансляции и алгоритмов автоматизации организации программ).

Вычислимые функции и алгоритмы

Все объекты строятся из символов, целых неотрицательных чисел, теоретико-множественных понятий

{x|P(x)}

x – переменная, значениями которой являются некоторые объекты;

P – свойства этих значений х, которыми являются элементами данного множества.

{(x,y)|x,y – числа, x<y}

M^n =M*M*…*M – функция, отображающая множество X во мн. Y, называется множеством F, такое что F вход в произведение этих множеств X,Y, так что для любых пар, (x,y) э F и (x’,y’) э F из x=x’—> y=y’

{x|(x,y) э F}

{y|(x,y) э F}

Если функция F определена на всем множестве X, она считается всюду определенной, иначе частично F:x—>M

Суперпозицией 2х функций F1:X—>Y, F2 : Y—>Z – F3: X—>Z, (x,z)эF3 если x э X, z э Z и существует y эY.

Предикат – функция, областью значений которой служит множество символов, цифр 0,1.

{0,1}

P: X—>{0,1}

P(x)=1, x э X

P(x)=0, x эX

Слово в алфавите – конечный объект, получаемый выписыванием оного за другим символов из V (V–алфавит).

Определение не дает информации о том, как получается аргумент ф-qq/ Необходимо переформулировать определение так, чтобы оно содержало алгоритм нахождения функции.

Идея Тьюринга: заключается в том, чтобы с помощью абстрактной теоретической машины вычислить значение функции по ее аргументам. Конкретная машина Т. дает конкретную вычислимую функцию.

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

T=(V,Q,q0, #,I), где V – алфавит; Q – конкретное непустое множество символов, называемых состоянием машины; q0 – элемент множества Q, обозначающий начальное состояние; # – специальный символ (пустой); I – программа машины.

1) Считывается символ напротив головки;

2) в списке команд ищется команда, в которой q – текущее состояние управления, a – текущий символ;

3) выполняется найденная команда:

• управление переходов в q’

• в обозреваемую ячейку вместо а записывается а’

• головка перемещается {r,l,p}=d

4) машина останавливается, если нет команд, результат – заключит слово на ленте

Машина Тьюринга перерабатывающая начальные слова в заключительные, заданную словарную функцию, для которой начинаются слова – это значения аргумента. Заключительные слова – значения функции.

Если маншина не остан-ся, то ф-я, задаваемая машиной считается неопредел-ой для этого слова. Ф-я F – вычислима (частично вычислима), если сущ-ет Маш. Т., так. что Ft=F.

Маш.Т. обл. св-ми:

1) конструктивность (предст. соб кон. объект, кот. стр-ся из баз-х объектов)

2) конечность (пр-с нах-я зн-й ф-й сост. из кон. числа шагов)

3) однозначность (рез-т работы ед-ым образом опр. нач. словом)

4) массовость (машина раб. с люб. нач. словом на ленте, состоящим из символов ее алф-та)

Массовые алгоритмические проблемы заключ. в:

н. указ. алг-м, кот. бы определял, обладает ли предъявлен. объект из некот класса объектов некоторым интересующим нас св-ом. Если сущ-ет так. частичн. алг-м, то говорят, что мн-во перечислимо, а представленная алгоритмическ. проблема частична разрешима. Если эт. алг-м определен всюду, тогда мн-во М разрешимо.

Разрешимость мн-ва М – сущ-ет всегда останавливающаяся машина Т., кот. для люб. слова из V через конечное число шагов уст-ет, принадлежит ли рассматриваемое слово рассматриваумому мн-ву М.

Перечислимость мн-ва озн., что сущ. Маш. Т., кот ост. т. в том случ., если предъявленное слово принадл. мн-ву М.

Проблемы: пуст. ленты, остановки Маш. Т., зацикливания Маш. Т.

Функцион-е Маш.Т. м. опис. с пом. протокола работы над заданным нач. словом.

#a1a2…ak…an# - слово так. вида наз. конфигурацией Маш. Т.

Посл-ть конфигураций, выпис. в том пор-ке, в кот. они след. в процессе раб. машин, наз. протоколом.

63. Математическая модель программы - схема программы, как основной инструмент исследования свойств и преобразований программ..Стандартные схемы программ, понятие стандартной схемы, стандартные схемы в линейной и графовой формах, интерпретация схем, понятие программы, основные свойства стандартных схем. Разрешимые подклассы стандартных схем программ.

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

Классы схемы программ

Стандартные

Рекурсивные

Обогащенные

Структурированные

Стадартные схемы программ - характеризуются базисом и структурой

Базис стандартный схем

Переменные - X = {x,x1...,y,y1,...,z,z1}

Функциональные символы

F={f(0), f(1), f(2),... g(0), g(1),g(2)... h(0), h(1)..}

Предикатные символы

P={p(0), p(1)..., q(0), q(1)...}

Спец. символы

{start, stop}

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

1. односимвольные слова, состоящие из переменных или констант, являются термами;

2. слово тета вида f(n)( тета 1, тета 2, ..., тета n), где тета 1, тета 2, ..., тета n - термы, является термом;

3. те и только те слова, о которых говорится в п.п. 1,2, являются термами.

Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р(n)( тета1, тета2,..., тетаn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2)(f(2)(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

1. начальный оператор - слово вида start(х1, х2...хк), где k >=0, а х1, х2...хк - переменные, называемые результатом этого оператора;

2. заключительный оператор - слово вида stop(тета1, тета 2,..., тета n), где n >= 0, а тета 1, тета 2,..., тета n - термы; вхождения переменных в термы тета называются аргументами этого оператора;

3. оператор присваивания - слово вида х := тета, где х – переменная (результат оператора), а тета - терм; вхождения переменных в термы называются аргументами этого оператора;

4. условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;

5. оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда тета - переменная, то оператор называется пересылкой (х:=у) и когда тета - константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс V1 имеет базис: {х1, х2}, {а, f(1)}, {p(1)}, {start, stop, (,),:=, ,} и множество операторов {start(х1, х2); х1:=f(x1), x2:=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop(х1, х2)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

Графовая форма стандартной схемы

Представим стандартную схему программ как размеченный граф, вершинам которого приписаны операторы из некоторого базиса В.

Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:

1. Начальная вершина (ровно одна) помечена начальным оператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.

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

3. Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.

4. Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).

5. Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.

Конечное множество переменных схемы S составляют ее память ХS.

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

Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2,...). Начальная вершина всегда помечается меткой 0.

Схема S называется правильной, если на каждой дуге заданы все переменные.

Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины.

Линейная форма стандартной схемы

Для использования линейной формы СПП множество специальных символов расширим дополнительными символами {:, goto, if, then, else}. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

1. если выходная дуга начальной вершины с оператором start(х1,..., хn) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(х1,..., хn) goto L;

2. если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=тета, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: x:= тета goto L1;

3. если вершина с меткой L - заключительная вершина с оператором stop(тета1,...тетаm), то ей соответствует инструкция:

L: stop(тета 1,..., тета m);

4. если вершина с меткой L - распознаватель с условием р(тета1,...тетаk), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция:

L: if р(тета1,...тетаk) then L1 else L0;

5. если вершина с меткой L - петля, то ей соответствует инструкция:

L: loop.

Интерпретация стандартных схем программ

ССП не является записью алгоритма, поэтому позволяет исследовать только структурные свойства программ, но не семантику вычислений. При построении «семантической» теории схем программ вводится понятие интерпретация ССП. Определим это понятие.

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

1. каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

2. каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;

3. каждому функциональному символу f (n) - всюду определенную функцию F(n) = I(f (n));

4. каждой логической константе р(0) - один символ множества {0,1};

5. каждому предикатному символу р(n) - всюду определенный предикат P (n) = I(p(n)).

Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).

Определим понятие выполнения программы.

Состоянием памяти программы (S,I) называют функцию W: XS D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма тета при интерпретации I и состоянии памяти W (обозначим тетаI(W)) определяется следующим образом:

1) если тета = х, x – переменная, то тетаI(W) = W(x);

2) если тета = a, a – константа, то тетаI(W) = I(a);

3) если тета = f(n)(тета1, тета2..., тетаn), то тетаI(W) = I(f (n))(тета1I(W), тета2I(W),..., тетаnI(W)).

Аналогично определяется значение теста p при интерпретации I и состоянии памяти W или pI(W):

если p = р(n)( тета 1, тета 2,..., тета n), то pI(W) = I(p(n))( тета 1I(W), тета2I(W),... тетаnI(W)), n >= 0.

Конфигурацией программы называют пару U = (L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которую называют протоколом выполнения программы (ПВП).

Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S,I) определяем следующим образом (ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui = (ki,Wi)): U0 = (0, W0), W0 – начальное состояние памяти схемы S при интерпретации I.

Пусть Ui = (ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stop(тета1, тета2... тетаn), то Ui - последняя конфигурация, так что протокол конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность значений тета1I(W), тета2I(W),..., тетаnI(W) объявляют результатом val(S,I) выполнения программы (S,I). В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация Ui+1 = (ki+1, Wi+1), причем

а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

б) если О - оператор присваивания х:= тета, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(х) = тета1(Wi);

в) если О - условный оператор p и pI(Wi) = ДЕЛЬТА, где ДЕЛЬТА {0,1}, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

г) если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.

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

Рассмотрим интерпретацию СПП S1 Интерпретация (S1, I1) задана так:

1. область интерпретации D1 Nat - подмножество множества Nat целых неотрицательных чисел;

2. I1(x)=4; I1(y)=0; I1(a)=1;

3. I1(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2;

4. I1(h)=H, где H - функция вычитания единицы, т. е. H(d)= d - 1;

5. I1(p)=P1, где P1 - предикат «равно 0», т.е. P1(d)=1, если d=0.

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

Разделяемые ресурсы

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

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

Общая память:

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

Ячейка общей памяти – это разделяемая переменная

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

Возникающие проблемы использования на рисунке 63.

Более приемлемое решение было предложено Э. Дейкстрой, которому принадлежит идея использования двоичных семафоров. Семафор - это процесс, поочередно выполняющий действия с именами Ри V:

СЕМ = (Р -> V -> СЕМ).

Он описывается как совместно используемый ресурс (взаискл: СЕМ // ...). При условии, что все процессы подчиняются этой дисциплине, каждый из двух процессов не сможет влиять на изменение счетчика — произвести действие взаискл.V. Таким образом, критический участок, на котором происходит увеличение счетчика, должен иметь вид:

взаискл. Р -> счет.прав?х -> счет.лев!(х + 1) -> взаискл.V -> ….

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

Взаимодействие процессов

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

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

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

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

Механихмы синхронизации процессов

ОС UNIX имеет развитые средства межпроцессной синхронизации по данным и управлению. Для этих целей в ОС существуют следующие механизмы.

-сигналы,

-семафоры,

-программные каналы,

-именованные программные каналы,

-очереди сообщений,

-сегменты разделяемой памяти,

-специальные команды (write? cu? mail),

-Средства межмашинного взаимодействия (uucp,tcp/ip,nfs,rfs).

События и сигналы

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

!!!проблема тупиков

Условия возникновения тупиков

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

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

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

!!! борьба с ними

Основные направления борьбы с тупиками

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

Итак, основные направления борьбы с тупиками:

* Игнорирование проблемы в целом

* Предотвращение тупиков

* Обнаружение тупиков

* Восстановление после тупиков

Одно из главных свойств сетей Петри - ограниченность.

Задача о производителе/потребителе.

Безопасность — это частный случай более общего свойства ограниченности. Некоторые соображения относительно реального ограничения на аппаратную реализацию позиций позволяют прийти к заключению, что безопасность — необязательное требование. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно-реализованный счетчик ограничен по максимальному числу, которое он может представить. Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.

Определение 4.2. Позиция рi P сети Петри С= (Р, Т, I, О) с начальной маркировкой мю является k-безопасной, если мю'(рi) к для всех мю' R(C, мю).

1-безопасная позиция называется просто безопасной. Заметим, что граница k' по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция р1 мо¬жет быть 3-безопасной, тогда как позиция р2 — 8-безопасной). Однако, если позиция pi k-безопасна, то она также и k'-безопасна Для всех k' k. Поскольку число позиций конечно, можно выбрать ft, равное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k-безопасна.

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

В задаче о производителе/потребителе также присутствует сов¬местно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель создает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и исполь¬зует. Такая ситуация может быть промоделирована сетью Петри так, как показано на рис. 3.29. Позиция В представляет собой бу¬фер, каждая фишка соответствует элементу данных, который про¬изведен, но еще не использован.

Одни из вариантов этой задачи — это задача о нескольких про¬изводителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис. 3.30 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис.3.29, за исключением того, что для представления s производителей и t потребителей мы начали выполнение сети с s фишка¬ми в начальной позиции процесса-производителя и t фишками в начальной позиции процесса-потребителя.

!! РИСУНОК

Таким образом мы представляем s производителей и t потребителей, реализуемых реентерабельными совместно используемыми программами. Альтернативой было бы дублирование программного кода для процессов производителя и потребителя, однако результатом этого при том же самом поведении была бы гораздо большая сеть.

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