Министерство образования  и науки Российской Федерации

     Государственное образовательное учреждение высшего  профессионального образования

     «Магнитогорский государственный технический университет  им. Г.И. Носова»

     Кафедра вычислительной техники  и прикладной математики 
 
 
 
 
 
 

     КУРСОВАЯ  РАБОТА

     по  дисциплине: «Теория вычислительных процессов»

     на  тему: «Реализация механизма мониторов

     Хоара в мультипрограммных системах.

     Задача  о спящем парикмахере» 
 
 

     Исполнитель: Тимохов Е.А. студент 3 курса, группа АВ-08-2

     Руководитель: Кочержинская Ю.В. к. т.н., доц. 
 

     Работа  допущена к защите “_____” _________ 2010г. ____________ 

     Работа  защищена “_____” _________ 2010г. с оценкой ___________ 
 
 
 

     Магнитогорск, 2010

     Введение 3

     1 Мультипрограммный режим  4

     1.1 Основные положения 4

     1.2 Проблема критической секции 5

     2 Мониторы хоара 8

     2.1 История создания 8

     2.2 Определения и основные характеристики 9

     2.3 Принцип работы монитора 10

     2.4 Условные переменные 11

     2.5 Преимущества монитора 12

     3 Задача о спящем парикмахере 14

     3.1 Постановка задачи 14

     3.2 Реализация задачи с помощью сетей Петри 15

     3.3 Листинг программы 16

     Заключение 22

     Список использованных источников 23 

 

Введение

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

     В практической части мы выполним решение  задачи «О спящем парикмахере» при помощи сети Петри и реализуем данную модель на языке высокого уровня с использованием семафоров (С++). 

 

1. мультипрограммный режим

1. Основные  положения

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

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

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

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

           

     Рисунок 1 

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

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

2. Проблема  критической секции

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

     Рассмотрим  два процесса p1 и p2, увеличивающих асинхронно значение общей целочисленной переменной x, представляющей количество единиц ресурса:

     p1: ... x:=x+1; ...;...

     p2: ... x:=x+1; ...;...

     Пусть С1 и С2 - центральные процессоры с внутренними регистрами R1 и R2 соответственно и разделяемой основной памятью. Если бы процесс p1 выполнялся бы на процессоре C1 и p2 - на С2, то могла бы возникнуть любая из следующих двух последовательностей:

1. p1: R1:=x; R1:=R1+1; x:=R1;...

            p2 : ... ; R2:=x; R2:=R2+1; x:=R2;...

     t₀----------------------------------------------------------------------->t₁

2. p1: R1:=x; R1:=R1+1; x:=R1;...

            p2: ... ; R2:=x; R2:=R2+1; x:=R2;...

     Пусть x содержит значение V в момент времени t₀. Тогда, если бы выполнение процессов p₁ и p₂ происходило как в последовательности 1, то в момент t₁ переменная x содержала бы значение V+1; если же - как в последовательности 2, то переменная x содержала бы значение V+2.

     Оба значения x были бы также реализованы, если бы процессы p₁ и p₂ разделяли во времени единственный процессор с переключением управления между процессами посредством прерываний.

     Решение проблемы заключается в разрешении входить в произвольный момент времени в критическую секцию (КС) "x:=x+1" только одному процессу. В общем случае КС могла бы состоять из любого числа операторов.

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

     Относительно  системы сделаны следующие предположения:

1. Считывание из общей памяти и запись в нее - неделимые операции; одновременные обращения (на запись или на считывание) к одной и той же ячейке памяти более чем одного процессора приведут к последовательным обращениям в произвольном порядке.
2. Критические секции не могут иметь связанных с ними приоритетов.
3. Относительные скорости процессоров неизвестны.
4. Программа может останавливаться вне ее КС. Проблема также может быть сформулирована в терминах нескольких процессов, асинхронно разделяющих во времени единственный процессор.

     Предполагается, что система циклических процессов  для проблемы КС имеет следующие  программные формы:

     begin

     P1: begin L1: CS₁; program₁; go to L1 end

     and

     P2: begin L2: CS₂; program₂; go to L2 end

     and

     ...

     and

     Pn: begin Ln: CS_n; program_n; go to Ln end

     end

 

2. Мониторы  Хоара

1. История создания

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

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

2. Определения и основные характеристики

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

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

     Основные  характеристики:

1. Локальные переменные монитора доступны только его процедурам.
2. Процесс входит в монитор путем вызова одной из его процедур.
3. В мониторе в определенный момент времени может находиться только один процесс; любой другой обратившийся будет приостановлен в ожидании доступности монитора.

3. Принцип работы монитора

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