Задача Реализация механизма мониторов. Хоара в мультипрограммных системах. Задача о спящем парик
Работа добавлена на сайт bukvasha.net: 2015-10-29Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
«Магнитогорский государственный технический университет им. Г.И. Носова»
Кафедра вычислительной техники и прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине: «Теория вычислительных процессов»
на тему: «Реализация механизма мониторов
Хоара в мультипрограммных системах.
Задача о спящем парикмахере»
Исполнитель: Тимохов Е.А. студент 3 курса, группа АВ-08-2
Руководитель: Кочержинская Ю.В. к. т.н., доц.
Работа допущена к защите “_____” _________ 2010г. ____________
Работа защищена “_____” _________ 2010г. с оценкой ___________
Магнитогорск, 2010
Введение. 3
1. Мультипрограммный режим Ошибка! Закладка не определена.
1.1 Основные положения. 3
1.2 Проблема критической секции. 5
2. Мониторы хоара. 8
2.1 История создания. 8
2.2 Определения и основные характеристики. 9
2.3 Принцип работы монитора. 10
2.4 Условные переменные. 11
2.5 Преимущества монитора. 12
3. Задача о спящем парикмахере. 3
3.1 Постановка задачи. 3
3.2 Реализация задачи с помощью сетей Петри. 3
3.3 Листинг программы.. Ошибка! Закладка не определена.
Заключение. 3
Список использованных источников. 3
Введение
Данная работа состоит из двух основных частей. В теоретической части мы рассмотрим историю возникновения понятия алгоритма, узнаем определение алгоритма, виды и свойства алгоритмов.
В практической части мы выполним решение задачи «О спящем парикмахере» при помощи сети Петри и реализуем данную модель на языке высокого уровня с использованием семафоров (С++).
1 мультипрограммный режим
1.1 Основные положения
Процессы, выполняемые в мультипрограммном режиме, можно рассматривать как набор последовательных слабосвязанных процессов, которые действуют почти независимо друг от друга, лишь изредка используя общие ресурсы. Взаимосвязь между такими процессами устанавливается с помощью различных сообщений и так называемого механизма синхронизации, который позволяет согласовывать и координировать работу процессов.
Хотя каждый процесс, выполняемый в мультипрограммном режиме, имеет доступ к общим ресурсам, существует некоторая область, которую в фиксированный момент времени может использовать лишь один процесс. Нарушение этого условия приведет к неизвестному порядку обработки процессов. Назовем такую область критической. При использовании критической области возникают различные проблемы, среди которых можно выделить проблемы состязания (гонок) и тупиков (клинчей).
Условие состязания возникает, когда процессы настолько связаны между собой, что порядок их выполнения влияет на результат операции.
Условие тупиков появляется, если два взаимосвязанных процесса блокируют друг друга при обращении к критической области.
Рисунок 1
В системах, допускающих перераспределение любых ресурсов в произвольной последовательности, но имеющей и неосвобожденные ресурсы, время от времени должны возникать тупиковые ситуации.
Пример. Пусть программе А нужен ресурс R1. Она запрашивает его и получает. Программе В нужен ресурс R2. Она запрашивает его и получает. Далее, пусть программа А, не отпуская R1, запрашивает R2, а программа В, не отпуская R2, запрашивает R1. Налицо типичный клинч, если только один из ресурсов R1 или R2 не может быть освобожден до момента завершения обработки соответствующего процесса.
1.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;...
t0----------------------------------------------------------------------->t1
(2) p1: R1:=x; R1:=R1+1; x:=R1;...
p2: ... ; R2:=x; R2:=R2+1; x:=R2;...
Пусть x содержит значение V в момент времени t0. Тогда, если бы выполнение процессов p1 и p2 происходило как в последовательности 1, то в момент t1 переменная x содержала бы значение V+1; если же - как в последовательности 2, то переменная x содержала бы значение V+2.
Оба значения x были бы также реализованы, если бы процессы p1 и p2 разделяли во времени единственный процессор с переключением управления между процессами посредством прерываний.
Решение проблемы заключается в разрешении входить в произвольный момент времени в критическую секцию (КС) "x:=x+1" только одному процессу. В общем случае КС могла бы состоять из любого числа операторов.
Более точно проблема формулируется так. Пусть имеется мультипроцессорная система с общей памятью. Каждая из программ, выполняемых процессорами, содержит критическую секцию, в которой организован доступ к общим данным; программы выполняются циклически. Необходимо так запрограммировать доступ к общей памяти, чтобы в любой момент времени только один из процессоров находился в своей КС.
Относительно системы сделаны следующие предположения:
1. Считывание из общей памяти и запись в нее - неделимые операции; одновременные обращения (на запись или на считывание) к одной и той же ячейке памяти более чем одного процессора приведут к последовательным обращениям в произвольном порядке.
2. Критические секции не могут иметь связанных с ними приоритетов.
3. Относительные скорости процессоров неизвестны.
4. Программа может останавливаться вне ее КС. Проблема также может быть сформулирована в терминах нескольких процессов, асинхронно разделяющих во времени единственный процессор.
Предполагается, что система циклических процессов для проблемы КС имеет следующие программные формы:
begin
P1: begin L1: CS1; program1; go to L1 end
and
P2: begin L2: CS2; program2; go to L2 end
and
...
and
Pn: begin Ln: CSn; programn; go to Ln end
end
2 Мониторы Хоара
2.1 История создания
Идея монитора была впервые сформулирована в 1974 г. одним из классиков компьютерных наук профессором Чарльзом Хоаром. Это был ответ на недостатки семафоров. Семафорные механизмы являются слишком примитивными, так как сам семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы решения задач получаются запутанными и ненаглядными.
Нужны были понятные и очевидные решения, которые позволяли бы создавать параллельные взаимодействующие программы. Таким решением являются т.н. мониторы, предложенные Хоаром.
2.2 Определения и основные характеристики
Монитор (в параллельном программировании) – это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причем в каждый момент им может пользоваться только один процесс.
Монитор представляет собой программный модуль, состоящий из инициализирующей последовательности, одной или нескольких процедур и локальных данных.
Основные характеристики:
1. Локальные переменные монитора доступны только его процедурам.
2. Процесс входит в монитор путем вызова одной из его процедур.
3. В мониторе в определенный момент времени может находиться только один процесс; любой другой обратившийся будет приостановлен в ожидании доступности монитора.
2.3 Принцип работы монитора
Пусть некоторый ресурс распределяется между процессами планировщиком. Этот планировщик имеет переменные, с помощью которых он отслеживает, занят ресурс или свободен. Для получения ресурса процесс должен обратиться к планировщику, причем процедуру планировщика разделяют все процессы, и такое обращение может произойти в любой момент. Но планировщик не в состоянии обслужить более одного процесса одновременно – он и является монитором (рис. 2).
Рисунок 2
Таким образом, монитор – такой механизм организации параллелизма, который содержит данные и процедуры, необходимые для реализации динамического распределения общих ресурсов.
Процесс, желающий получить доступ к разделяемым переменным, обращается к монитору, который в свою очередь предоставляет доступ или отказывает в нем. Вход в монитор находится под жестким контролем. Здесь осуществляется взаимоисключение, т.е. в любой момент времени только один процесс может войти в монитор. Остальные обратившиеся процессы вынуждены ждать, причем режимом ожидания автоматически управляет сам монитор. При отказе в доступе монитор блокирует обратившийся процесс и определяет условие, по которому процесс ждет. При деблокировании сам монитор и проверяет это условие.
2.4 Условные переменные
Условная переменная(conditional variable) – символизирует ожидание потоком, выполняющим метод монитора, наступления некоторого события.
Существует три операции:
1. Wait – выполняется поток, который хочет подождать наступления события. Снимает блокировку монитора, после чего другой поток может войти в него; ожидает, пока какой-либо другой поток не подаст условный сигнал.
2. Signal – выполняется поток, сигнализирующём о наступлении события. Пробуждает максимум один ожидающий поток; если отсутствуют потоки, ожидающие события, информация о приходе сигнала теряется.
3. Broadcast – также выполняется потоком, сигнализирующем о наступлении события. Пробуждает все ожидающие события потоки.
Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, эта процедура монитора выдает команду WAIT с указанием условия ожидания. Процесс мог бы оставаться внутри монитора, но это противоречит принципам взаимоисключения, если в монитор бы затем вошел другой процесс. Поэтому процесс в режиме ожидания вне монитора ждет, пока требуемый ресурс освободится.
Доступ ко всем внутренним данным монитора возможен только изнутри монитора. При первом обращении монитор присваивает своим переменным начальные значения; при последующих обращениях используются сохраненные от предыдущего обращения значения. Для защиты каких-либо данных нужно просто поместить их в монитор.
Процесс, занимавший ресурс, со временем обратится к монитору, чтобы возвратить ресурс системе. Соответствующая процедура монитора может просто принять уведомление об освобождении ресурса и ждать очередного запроса на этот ресурс. Но может оказаться, что уже есть процессы, ожидающие освобождения этого ресурса. Тогда монитор выполняет команду извещения SIGNAL, чтобы один из ожидавших процессов мог получить ресурс и покинуть монитор. Если ресурс никому не требовался, то подобное оповещение не вызывает никаких последствий, а ресурс вносится в список свободных.
Чтобы гарантировать получение ресурса находившимся в ожидании процессом, ему назначается более высокий приоритет, чем новым процессам, пытающимся войти в монитор. В противном случае новый процесс мог бы перехватить ресурс в момент его освобождения, что при многократном повторении приведет к бесконечному ожиданию.
Для операционной системы реального времени можно организовать дисциплину обслуживания на основе абсолютных или динамически изменяемых приоритетов.
2.5 Пример монитора Хоара
Пример монитора Хоара:
Monitor Resource;
condition free; {условие – свободный}
Var busy : Boolean;
Procedure Request; {запрос}
Begin
If busy then WAIT(free);
busy:=true;
TakeOff; {выдать ресурс}
End;
Procedure Release;
Begin
TakeOn; {взять ресурс}
busy:=false;
SIGNAL(free)
End;
Begin
busy:=false;
End
Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам REQUEST и RELEASE. Если процесс обращается к REQUEST в тот момент, когда ресурс используется, то значение busy=true, и REQUEST выполнит операцию монитора WAIT(free). Обратившийся процесс помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free.
Когда процесс, использующий ресурс, обращается к RELEASE, операция монитора SIGNAL(free) деблокирует процесс из начала очереди. Он готов сразу после операции WAIT(free), которая его и блокировала, возобновить выполнение процедуры REQUEST.
Если же SIGNAL(free) выполняется в то время, когда нет ожидающего условия free процесса, то никакие действия не выполняются.
Доступ к разделяемым переменным ограничен телом монитора, а мониторы входят в состав ядра ОС, поэтому разделяемые переменные становятся системными переменными, что автоматически исключает критические интервалы (два процесса никогда не смогут получить одновременного доступа к разделяемым переменным).
Процедуры монитора выполняются только по требованиям процесса.
2.6 Преимущества монитора
Преимущества монитора перед другими средствами синхронизации:
· в форме монитора легко реализовать любой механизм;
· повышается наглядность;
· мониторы дают процессам возможность совместно использовать программные модули, представляющие собой критические секции.
Если несколько процессов совместно используют ресурс и работают с ним совершенно одинаково, то в мониторе нужна только одна процедура, в то время как решение с семафорами требует наличия КС в каждом процессе.
Таким образом, мониторы обеспечивают по сравнению с семафорами упрощение организации взаимодействующих вычислительных процессов и большую наглядность при незначительной потере эффективности.
3 Задача о спящем парикмахере
Задача о парикмахере, который спит на работе, является аллегорической демонстрацией подсистемы управления процессами и была сформулирована Дейкстрой в 1968 г.
3.1 Постановка задачи
Парикмахерская состоит из комнаты ожидания О и комнаты, в которой стоит кресло парикмахера З. Через двери Д можно попасть из комнаты О в комнату З, а из комнаты З на улицу. Если парикмахер заходит в комнату ожидания и никого там не находит, то он идет спать. Если клиент заходит в парикмахерскую и находит спящего парикмахера, то он его будит. В комнате ожидания число мест ограничено и равно N.
Согласно данной задаче необходимо определить элементы который будут запрограммированы отдельными процессами, разработать алгоритм и программно его реализовать.
Рисунок 3 – Задача о спящем парикмахере
3.2 Реализация задачи с помощью сетей Петри
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.
Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами, вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, разновременно при выполнении некоторых условий.
1. Переходы
2.
Состояние сети определяется её разметкой. Места, из которых ведут дуги на данный переход, называются входными местами для данного перехода. Места, из которых выходят дуги, называются выходными. Выполнение условия обозначается на схеме сети изменением её разметки, т.е. помещением в данное место сети n фишек, где n- это емкость условия.
На каждом из последующих шагов работы мы переходим в следующее состояние. Выполнение условия обозначает срабатывание перехода, событие обозначается изменением разметки сети. Работа сети представляет собой совокупность срабатывания переходов. На рисунке 4 представлена сеть Петри.
|
|
|
Рисунок 4 - Реализация алгоритма с помощью сетей Петри
3.3 Листинг программы
Для реализации на языке высокого уровня необходимо создать N потоков, которые будут моделировать действия клиентов. В решении предлагается использовать три семафора:
1.
customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается – он уже не ждет);
2.
barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента;
3.
mutex для реализации взаимного исключения.
Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей. Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
Семафор – это системное средство для синхронизации выполнения процессов, позволяющее войти в заданный участок кода не более чем заданному количеству потоков.
Далее представим основные фрагменты кода программы написанной на языке высокого уровня (С++).
#include<windows.h>
//---------------------------------------------------------------------------
int yshed = 0; //кол-во ушедших без стрижки
int dovol = 0; //счетчик подстриженных
int count = 0; //ожидающие
int client; //счетчик клиентов
//для реализации взаимного исключения (для распределения доступа к ожидающим)
HANDLE mutex;
HANDLE customerSemaphore; //для подсчета ожидающих посетителей
//количество брадобреев (0 или 1),простаивающих в ожидании клиента
HANDLE barberSemaphore;
DWORD WINAPI customer(LPVOID); //посетитель
DWORD WINAPI barber(LPVOID); //парикмахер
void getPricheson(); //функция стрижки
randomize();
DWORD SLEEP_STR = rand()%200+250; // время стрижки
DWORDSLEEP_PRX = rand()%2000+2000; //время прихода клиента
void Zprint(AnsiString text) // печать
{
MainFormBarber->Memo1->Lines->Add("[" + Time() + " " + Date() + "]==> " + text);
}
//---------------------------------------------------------------------------------------------------------------
DWORD WINAPI barber(LPVOID) //парикмахер
{
While(TRUE)
{
If(count == 0) //нет никого, тогда посплю
{
Zprint("Парикмахер решил вздремнуть");
MainFormBarber->Label8->Caption = "Сплю";
//заблокируемся до появления посетителя
WaitForSingleObject(customerSemaphore,INFINITE);
}
else //буду работать тогда
{
//получаем доступ к ожидающим
WaitForSingleObject(mutex,INFINITE);
count--; //уменьшаем кол-во ожидающих клиентов
ReleaseSemaphore(mutex,1,NULL); //выход из критической области
//парикмахерготовкработе
ReleaseSemaphore(barberSemaphore,1,NULL);
getPricheson() ; //получить модную стрижку
}
}
}
//--------------------------------------------------------------------------
DWORD WINAPI customer(LPVOID) //клиент
{
WaitForSingleObject(mutex,INFINITE); //вход в критическую область
if(count < NUMBER_OF_SEATS ) //если есть свободное место
{
Sleep(SLEEP_PRX); //приостановка потока
char buffer2[100];
sprintf(buffer2, "Пришел %d клиент. Cел на %d кресло для ожидания",client+1,count+1);
Zprint((AnsiString)buffer2);
client++; //увеличиваем счетчик клиентов
count++; // увеличиваем кол-во ожидающих клиентов
switch ( count ) {
case 1: {MainFormBarber->Label5->Caption = IntToStr(client); break;}
case 2: {MainFormBarber->Label9->Caption = IntToStr(client); break;}
case 3: {MainFormBarber->Label10->Caption = IntToStr(client); break;}
case 4: {MainFormBarber->Label11->Caption = IntToStr(client); break;}
case 5: {MainFormBarber->Label12->Caption = IntToStr(client); break;}
}
MainFormBarber->Label13->Caption = "Свободно!";
MainFormBarber->Label14->Caption = IntToStr(client);
//если парикмахер спит, это его разбудит
ReleaseSemaphore(customerSemaphore,1,NULL);
ReleaseSemaphore(mutex,1,NULL); // выходи из критической области
//если парикмахер занят, переходим в состояние ожидания
WaitForSingleObject(barberSemaphore,INFINITE);
}
else
{
Sleep(SLEEP_PRX); //приостановка потока
//нет свободного кресла для ожидания – идем домой. Выход из критической области
ReleaseSemaphore(mutex,1,NULL);
char buffer3[100];
sprintf(buffer3, "Клиент %d видит, что все места заняты и уходит",client+1);
MainFormBarber->Label13->Caption = "Занято!!!";
Zprint((AnsiString)buffer3);
yshed++; //увеличиваем счетчик ушедших
client++; //увеличиваем счетчик клиентов
MainFormBarber->Label14->Caption = IntToStr(client);
}
Sleep(SLEEP_PRX); //приостановка потока
}
//---------------------------------------------------------------------------------------------------------------
void getPricheson() //функция стрижки
{
char buffer1[100];
sprintf(buffer1, "Парикмахер стрижет клиента, который сидел на месте %d",count+1);
Zprint((AnsiString)buffer1);
switch ( count+1 ) {
case 1: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label5->Caption =""; break;}
case 2: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label9->Caption =""; break;}
case 3: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label10->Caption =""; break;}
case 4: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label11->Caption =""; break;}
case 5: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label12->Caption =""; break;}
}
dovol++; //увеличиваем счетчик бритоголовых
Sleep(SLEEP_STR); //приостановка потока на время стрижки
//---------------------------------------------------------------------------------------------------------------
void __fastcall TMainFormBarber::FormDestroy(TObject *Sender)
{
//удаляемвсесемафоры
CloseHandle(customerSemaphore);
CloseHandle(barberSemaphore);
CloseHandle(mutex);
}
//---------------------------------------------------------------------------------------------------------------
void __fastcall TMainFormBarber::clickClick(TObject *Sender) //обработчик кнопки
{
MainFormBarber->click->Enabled = false;
//семафоры
mutex=CreateSemaphore(NULL,1,1,NULL);
customerSemaphore = CreateSemaphore(NULL, 0, 1, NULL);
barberSemaphore = CreateSemaphore(NULL, 0, 1, NULL);
// потоки клиентов и парикмахера
HANDLE threadCus[NUMBER_OF_CUSTOMERS];
HANDLE threadBar;
DWORD cusThreadId;
DWORD barThreadId;
for(int i=0;i< NUMBER_OF_CUSTOMERS;++i)
{
threadCus[i] = CreateThread(NULL, 0, customer, (LPVOID)i, 0, &cusThreadId);
}
threadBar = CreateThread(NULL, 0, barber, (LPVOID)1, 0, &barThreadId);
}
Заключение
В данной работе мы раскрыли вопрос о видах и свойствах алгоритмов.
В практической части курсовой работы мы рассмотрели одну из классических задач на синхронизацию потоков – задачу о спящем парикмахере и произвели решение этой задачи с использованием семафоров.
Список использованных источников
1 Э. Таненбаум – Современные ОС. – Москва: Изд. 3-е. М.:Питер.–2010.–1116c.
2 Е. В. Рабинович – Теория вычислительных процессов.– Новосибирск: Изд. 1-е. Новосибирск :Издательство НГТУ–2008.–162 c.
3 Иванв В. Е., Сабельфельд В.Н. Алгоритмы. – М.: Наука, 2003.–98c.
