В теории операционных систем (ОС) под процессом понимается некоторая деятельность, связанная с исполнением программы на процессоре [8]. Многие ОС поддерживают одновременное (параллельное) выполнение нескольких процессов. Процессы могут  выполняться  до  тех пор, пока не возникнет потребность в общении между ними. В каждом конкретном случае общение задается с помощью синхронизирующих правил, определяющих порядок выполнения взаимосвязанных параллельных процессов. Существо синхронизирующих правил определяют отношения предшествования, приоритетности, взаимного исключения. Реализация синхронизирующих правил осуществляется с помощью механизмов (средств)  синхронизации. Такие механизмы весьма многочисленны по способам реализации. Чаще всего они име­ют программно-аппаратную форму реализации и основаны на использовании специальных  переменных, разделяемых и глобально доступных параллельным  взаимодействующим процессам.  В большинстве своем механизмы синхронизации выполняют двоякую роль – обеспечивают не только способ упорядочения развития процессов (отрабатывают тип отношения следования про­цессов), но и взаимодействие между процессами, выражающе­еся в передаче информации между ними.

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

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

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

Существует несколько типов семафоров: двоичные, считающие, счетные, множественные и др. Двоичный семафор может принимать два значения: 0 и 1. Допустимыми значениями считающего семафора являются целые числа. При этом возможны два варианта. Первый вариант – допустимы только целые положительные числа, включая нуль. Второй вариант – допустимы любые целые числа.

При выполнении Р- и V-примитивов для счетного семафора S допускается изменение семафора S не на 1, а на любое определенное число R, что обозначается: P(S,R) и V(S,R). Если в результате выполнения примитива Р полученное  значе­ние семафора  остается  положительным,  то  процесс  продолжается. В противном случае процесс «засыпает» на семафоре.

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

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

       ...

       ...

    ...

         ...

         ...

   END.

Задача взаимного исключения является одной из ключевых проблем параллельного программирования. Было предложено много способов решения этой проблемы. Эффективное решение  задачи было достигнуто путем использования семафорной техники (рис. 5.1).

Семафор исклдоступ используется для обеспечения взаимного исключения.  Операторы,  заключенные между операторными скобками PARBEGIN–PAREND, выполняются параллельно.

Сетевая  модель  решения  задачи  взаимного  исключения представлена на рис. 5.2, а ее текстовое представление – на рис. 5.3. Интерпретация элементов сетевой модели следующая. Позиция S – двоичный семафор, начальное состояние – открыт. Переход TP[i] – операция закрытия семафора i-м процессом, переход TV[i] – операция открытия семафора i-м процессом, переход CS[i] – критическая область i-го процесса. На рис. 5.4 представлен  граф достижимых состояний  (ГДС)  сетевой модели в виде списков следования, полученный с использованием системы СИМС. Соотношение между внутренними номерами элементов

ментов сетевой модели и мнемоническими именами отображено в табл. 5.1. На рис. 5.5 полученный ГДС представлен в графическом виде. На основе анализа данного ГДС можно сказать, что соответствующая сетевая модель  жива   и  безопасна  и, следовательно, исходная система параллельных процессов свободна от тупиковых ситуаций. Анализ достигнутых маркировок показывает, что в системе отсутствует ситуация, когда два процесса одновременно находятся в своих критических областях.

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

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

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

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

Следует отметить, что имеется большое число вариантов постановки   и   решения   задачи   «производитель-потребитель» в рамках конкретной ОС.

         ...

         ...

         ...

        ...

         ...

         ...

   END.  

Программное  решение  задачи  «производитель-потребитель» с использованием семафоров представлено на рис. 5.7. В представленной программе используются три семафора: исклдоступ – двоичный семафор для взаимного исключения, буфер пуст – считающий семафор, определяющий  число  пустых  ячеек  в буфере; буфер полон – считающий семафор, определяющий число заполненных ячеек в буфере. Таким образом, в представленной программе семафоры используются как счетчики ресурсов и синхронизаторы.

Для реализации операций записи и чтения из буфера удобно использовать кольцевой буфер (см. рис. 5.6). При этом вводятся два указателя: iw – для записи, ir – для чтения. Указатель iw определяет пустую ячейку в буфере, куда процесс-производитель должен  поместить  сообщение.  Указатель ir определяет  ячейку в буфере, откуда процесс-потребитель должен считать сообщение. Условие iw = ir указывает, что буфер пуст. Для реализации кольцевого буфера можно использовать линейный буфер емкостью N. При  этом  для сдвига указателей следует использовать сложение с единицей по модулю N:

Сетевая модель, представляющая задачу "производитель-потребитель", изображена на рис. 5.8. Интерпретация элементов сетевой модели следующая. Позиция S – двоичный семафор для взаимного исключения; позиция E – считающий семафор, определяющий число пустых ячеек; позиция F – считающий семафор, определяющий число заполненных ячеек. Переходы, относящиеся к процессу-производителю: T1[1] – закрыть семафор E;  T2[1] – закрыть   семафор S   и   поместить   сообщение в буфер; T3[1] – открыть семафор S; T4[1] – открыть семафор F. Переходы, относящиеся к процессу-потребителю: T1[2] – закрыть семафор F; T2[2] – закрыть семафор S; T3[2] – взять сообщение из буфера; T4[2] – открыть семафоры S и E. Как видно из структуры сетевой модели, процессы носят циклический характер. На рис. 5.9 приведен текст сетевой модели на языке ЯОСМ, причем   в   модели    первоначальное    число   пустых   буферов выбрано равным трем. На рис. 5.10 представлен ГДС сетевой модели в виде списков следования, полученный с использованием системы СИМС.  Соотношение  между  внутренними  номерами элементов  сетевой  модели  и  мнемоническими 

именами  отображено в табл. 5.2. На рис. 5.11 полученный ГДС представлен в графическом виде. На основе анализа данного ГДС можно сделать вывод, что соответствующая сетевая модель является живой и, следовательно, исходная система параллельных процессов свободна от тупиковых ситуаций. Ограниченность позиции BUFF (номер позиции – 9) равна трем, что соответствует отсутствию ситуации переполнения буфера сообщений.

Существует несколько вариантов задачи «читатели-писатели», однако их основная структура остается неизменной. Имеется система параллельных процессов, которые взаимодействуют друг с другом следующим образом. Все процессы делятся на два типа: процессы-читатели и процессы-писатели (рис. 5.12). Процессы работают с общей областью памяти.

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

Пример кольцевой очереди / C++ / Sql.ru

27 сен 2008 ... Пример кольцевой очереди / C++ / Здраствуйте, есть у кого-нибудь ... А что реализовать кольцевой буфер с методами front(), back(), ... http://www.sql.ru/forum/599425/primer-kolcevoy-ocheredi

       ...

       ...

       ...

     ...

       ...

       ...

     ...

       ...

       ...

       ...

       ...

       ...

  END.  

Программное решение задачи «читатели-писатели» с использованием семафоров представлено на рис. 5.13. В представленной программе используется один счетный семафор S.

Сетевая модель, представляющая задачу «читатели-писатели», изображена на рис. 5.14. Интерпретация элементов сетевой модели следующая: позиция S – считающий семафор; переходы, относящиеся к процессу-читателю: TP[i] – закрытие семафора S на единицу; TOP[i] – чтение из области памяти; TVS[i] – открытие семафора S на единицу (i = 2,3); переходы, относящиеся к процессу-писателю: TPS[j] – закрытие семафора S на число n; TOP[j] – запись в область памяти; TVS[j] – открытие семафора S на число n (j = 1). На рис. 5.15 приведен текст сетевой модели на языке ЯОСМ, причем в модели представлены два процесса-читателя и один процесс-писатель. На рис. 5.16 представлен ГДС сетевой модели в виде списков следования, полученный с использованием системы СИМС. Соотношение между внутренними номерами элементов сетевой модели и мнемоническими именами отображено в табл. 5.3. На рис. 5.17 полученный ГДС представлен в графическом виде. На основе анализа данного ГДС можно сказать, что соответствующая сетевая модель является живой и, следовательно, исходная система параллельных процессов свободна от тупиковых ситуаций. На множестве достижимых маркировок отсутствует  такая   маркировка,  у  которой   ненулевые   компоненты с номерами 4 или 7 (соответствующие записи в память) одновременно  существовали  бы  с  ненулевыми  компонентами с номерами 5, 6, 8 или 9 (соответствующими чтению из памяти), что доказывает существование взаимного исключения при записи.

Рассмотрим  формулировку  задачи об обедающих философах в терминологии, предложенной Э. Дейкстрой [8]. За круглым столом расставлены пять стульев, на каждом из которых сидит определенный философ (Фi ) (рис. 5.18).

В центре стола – большое блюдо спагетти, а на столе лежат пять вилок (B1..B5) – каждая между двумя соседними тарелками. Каждый философ может находиться только в двух состояниях – либо он размышляет, либо ест спагетти. Начать думать философу ничто не мешает. Но чтобы начать есть, философу нужны две вилки: одна в правой руке, другая в левой. Закончив еду, философ кладет вилки слева и справа от своей тарелки и опять начинает размышлять до тех пор, пока снова не проголодается.

Существует множество различных формулировок данной задачи, в одной из которых философы интерпретируются как процессы, а вилки – как ресурсы. Задача «обедающие философы» удобна для изучения тупиковых ситуаций в системах парал­лельных процессов.

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

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

       ...

   END.

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

Сетевая модель, представляющая задачу «обедающие философы», изображена на рис. 5.20. Интерпретация элементов сетевой модели следующая. Маркированная позиция М[i] – i-й  философ находится в состоянии размышления, маркированная позиция Е[i] – i-й философ находится в состоянии потребления пищи. Позиция R[j] определяет наличие или отсутствие на столе j-й вилки: если позиция маркирована, то вилка лежит на столе, если не маркирована, то вилка взята и находится в руке философа. Переход GET[i] интерпретируется как взятие i-м философом соседних вилок и переход из состояния размышления к еде. Переход PUT[i] интерпретируется как возврат i-м философом левой и правой вилок и переход от еды к размышлению. На рис. 5.21 приведен текст сетевой модели на языке ЯОСМ.

Следует отметить, что представленная сеть может моделировать различные ситуации из различных проблемных областей. Рассмотрим несколько иную интерпретацию представленной сетевой модели. Пусть имеется специализированная параллельная вычислительная система для реализации итерационных вычислительных процессов, состоящая из совокупности процессорных элементов (ПЭ) и модулей памяти данных (МПД) и памяти команд (МПК),  связанных в кольцо (рис. 5.22).

Данная система работает следующим образом. ПЭ захватывает оба смежных МПД, используя левый для извлечения исходных данных новой итерации, правый – для выборки результатов предыдущей итерации. По завершении итерации он помещает результат в правый  МПД и освобождает оба МПД. ПЭ осуществляет только одновременный захват смежных МПД (если он возможен). Интерпретация элементов сетевой модели в данном  случае будет следующая. Маркированная позиция M[i] – i-й ПЭ обрабатывает внутренние данные, маркированная позиция E[i] – i-й ПЭ захватил оба МПД и обрабатывает данные очередной итерации. Позиция R[j] определяет занятость j-го МПД; если данная позиция маркирована, то j-й МПД свободен, иначе – занят. Переход GET[i] интерпретируется как занятие i-м ПЭ соседних МПД и начало обработки данных итерации. Переход PUT[i] интерпретируется как освобождение соседних МПД и окончание обработки данных итерации.

На рис. 5.23 представлен ГДС сетевой модели в виде списков следования, полученный с использованием системы СИМС. Соотношение между внутренними номерами элементов сетевой модели и мнемоническими именами отображено в табл. 5.4. На рис. 5.24 полученный   ГДС представлен в графическом виде. На основе анализа данного ГДС можно сделать вывод, что соот­вет­ствующая сетевая модель является живой и, следовательно, исходная  система  параллельных процессов свободна от тупиков.

Кольцевой буфер — Википедия

Кольцевой буфер, или циклический буфер — это структура данных, использующая единственный буфер фиксированного размера, как будто бы после ... https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D1%8C%D1%86%D0%B5%D0%B2%D0%BE%D0%B9_%D0%B1%D1%83%D1%84%D0%B5%D1%80

Однако возможна ситуация голодания («оттеснения») отдельного философа, на что указывают определенные циклы в ГДС. Например, следующий цикл:

соответствует оттеснению третьего философа от еды двумя его соседями – вторым и четвертым философами. Они создают такую ситуацию, чтобы у третьего философа не было одновременно двух необходимых для еды вилок. В ГДС это соответствует тому, что из маркировок М8, М9, М10, принадлежащих циклу, нет ни одной выходящей дуги, отмеченной переходом t3 (имя перехода – GET[3]).

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

Решение проблемы голодания отдельного философа основано на введении жетонов – карточек, разрешающих потребление пищи. Жетоны могут передаваться по кругу, от философа к философу. Число циркулирующих в системе жетонов меньше числа философов. На рис. 5.26 представлена сетевая модель i-го философа. Интерпретация позиций, связанных с i-м философом (i =  ), следующая. Маркированные позиции pti , pwi , pei представляют состояния размышления, ожидания и потребления пищи соответственно. Метка в позиции pci свидетельствует, что вилка слева от i-го философа свободна. Метка в позиции pai свидетельствует, что i-й философ имеет жетон. В системе существует два жетона, так что, по крайней ме­ре, два философа могут есть одновременно. Если i-й философ имеет жетон и если он находится в состоянии размышления, то мо­жет  сработать  переход tti,  чем имитируется передача жетона (i 1)-му философу,  сидящему  по  правую  сторону (позиция pai   1 ). Операция означает сложение по модулю 5. Когда i-й философ становится голодным, срабатывает переход twi и философ переходит в состояние ожидания. Переход tei срабатывает, когда имеются метки в позициях pwi , pai , pci и  pci   1. В результате срабатывания появляется метка в позиции pei (состояние потребления пищи). Когда философ заканчивает еду, срабатывает переход tci , в результате чего добавляются метки в позиции pci , pci   1 , pai   1 и pti . Таким образом, философ вновь переходит в состояние размышления. Анализируя ГДС для данной сетевой модели, можно показать, что фаза ожидания каждого философа конечна. Следовательно, система свободна от ситуации голодания.

Как было показано выше, каждая из рассмотренных задач синхронизации представляется программно в паскалеобразной форме с использованием семафоров. Однако кроме этих низкоуровневых механизмов синхронизации существуют высокоуровневые механизмы, например, механизм рандеву языка АДА. Большой интерес вызывает представление задач в сетевой форме на этом современном мощном языке программирования. Ниже описывается проблема обедающих философов на языке АДА [25].

       -- когда заканчивается задача, моделирующая философов).

Пять философов и пять вилок моделируются задачами языка АДА в соответствии с этими двумя типами объектов, причем используются два массива задач в процедуре DINING. После активизации задача, моделирующая действия философов получает идентификационный номер, равный индексу элемента массива, который связан с конкретным философом. Используя этот но­мер, можно  определить  идентификационные номера вилок  сле­ва и справа от философа. В данной постановке задачи считается, что каждый философ смертен, поэтому, приняв пищу 100 000 раз, он умирает. Программа на языке АДА, описывающая проблему обедающих философов, представлена на рис. 5.27. В представленной программе и философы, и вилки моделируются с помощью массивов задач. В этом решении возможны тупики. Пусть каждый философ берет вилку и, чтобы начать еду, ожидает получения второй вилки. Если предположить, что все философы очень упрямы и ни один из них не желает расстаться с вилкой, не получив вторую и не закончив еду, то вся система будет находиться в тупиковом состоянии.

В рассмотренной системе тупиков можно избежать,  используя ограничение на пользование вилками, согласно которому философ может взять две вилки, необходимые для еды, только в том случае, если обе они свободны. Реализовать данное условие можно с использованием условия when оператора отбора. Другим способом избежания тупиков является введение еще одной задачи HOST, гарантирующей, что в каждый данный момент времени за столом находится не более четырех философов. Каждый философ прежде, чем  сесть  за  стол,  должен получить разрешение задачи HOST, а покидая стол, уведомить задачу HOST об этом. Задача HOST представлена на рис. 5.28. Очевидно, что теперь, когда введено данное изменение, никаких тупиков быть не может, так как за столом будет, по крайней мере, один философ, который может приступить к еде. После еды, занимающей конечное время, он уйдет, и другой философ сможет начать прием пищи.