55 – Проблемы межпроцессного взаимодействия

55 – Проблемы межпроцессного взаимодействия Проблемы обедающих философов В 1965 году Дейкстра сформулировал и решил проблему синхронизации, назван-ную им проблемой обедающих философов. Проблему можно сформулировать следующим образом: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каждыми двумя тарелками лежит одна вилка. Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает? В листинг 2.10 можно внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может, есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам. Решение, представленное в листинге 2.11, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа с номером i определяются макросами LEFT и RIGHT (то есть если i = 2, то LEFT- 1 и RIGHT - 3). Листинг 2.11. Решение задачи обедающих философов #define N 5 /* Количество философов */ #define LEFT (i+N.l)%N /* Номер левого соседа философа с номером i */ #define RIGHT (i+1)%N /* Номер правого соседа философа с номером i */ #define THINKING 0 /* Философ размышляет */ #define HUNGRY I /* Философ пытается получить вилки */ #define EATING 2 /* Философ ест */ typedef int semaphore; /* Семафоры - особый вид целочисленных переменных */ int state[N]; /* Массив для отслеживания состояния каждого философа */ semaphore mutex - 1; /* Взаимное исключение для критических областей */ semaphore s[N]; /* Каждому философу по семафору */ void philosopher(int i)/* i - номер философа, от 0 до N-1 */ { while (TRUE) { /* Повторять до бесконечности */ think(): /* Философ размышляет */ take_forks(i): /* Получает две вилки или блокируется */ eat(); /* Спагетти, ням-ням */ put_forks(i); /* Кладет на стол обе вилки */ } } void take_forks(int i) /* i - номер философа, от 0 до N-1*/ { down(&mutex); /* Вход в критическую область */ state[i] = HUNGRY: /* Фиксация наличия голодного философа */ test(i): /* Попытка получить две вилки */ up(&mutex): /* Выход из критической области */ down(&s[i]); /* Блокировка, если вилок не досталось */ } void put_forks(i) /* i - номер философа, от 0 до N-1*/ { down(&mutex): /* Вход в критическую область */ state[i] = THINKING: /* Философ перестал есть */ test(LEFT); /* Проверить, может ли есть сосед слева */ test(RIGHT): /* Проверить, может ли есть сосед справа */ up(&mutex); /* Выход из критической области */ } void test(i) /* i - номер философа, от 0 до N-1*/ { if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING: up(&s[i]); } } В программе используется массив семафоров, по одному на философа, чтобы блокировать голодных философов, если их вилки заняты. Обратите внимание, что каждый процесс запускает процедуру philosopher в качестве своей основной программы, но остальные процедуры take_forks, put_forks и test являются обычными процедурами, а не отдельными процессами. Проблема читателей и писателей Проблема обедающих философов полезна для моделирования процессов, соревнующихся за монопольный доступ к ограниченному количеству ресурсов, например к устройствам ввода-вывода. Другой известной задачей является проблема читателей и писателей, моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей? Одно из решений представлено в листинге 2.12. Первый читающий процесс выполняет операцию down на семафоре db, чтобы получить доступ к базе. Последующие читатели просто увеличивают значение счетчика rс. По мере ухода читателей из базы значение счетчика уменьшается, и последний читающий процесс выполняет на семафоре db операцию up, позволяя блокированному пишущему процессу получить доступ к базе. В этом решении один момент требует комментариев. Представьте, что в то время как один читатель уже пользуется базой, другой читатель запрашивает доступ к базе. Доступ разрешается, поскольку читающие процессы друг другу не мешают. Доступ разрешается и третьему, и последующим читателям. Затем доступ запрашивает пишущий процесс. Запрос отклонен, поскольку пишущим процессам необходим монопольный доступ, и пишущий процесс приостанавливается. Пока в базе есть хотя бы один активный читающий процесс, доступ остальным читателям разрешается, а они все приходят и приходят. Если, предположим, новый читающий процесс запрашивает доступ каждые 2 с, а провести в базе ему надо 5 с, то пишущий процесс никогда в базу не попадет. Чтобы избежать такой ситуации, нужно немного изменить программу: если пишущий процесс ждет доступа к базе, новый читающий процесс доступа не получает, а становится в очередь за пишущим процессом. Теперь пишущему процессу нужно подождать, пока базу покинут уже находящиеся в ней читающие процессы, но не нужно пропускать вперед читающие процессы, пришедшие к базе после него. Недостаток этого решения заключается в снижении производительности, вызванном уменьшением конкуренции. Нужно вводить приоритеты. Проблема спящего парикмахера В парикмахерской есть один брадобрей, его кресло и n стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов. В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается - он уже не ждет); barbers, количество брадобреев 0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей. Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит. Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает и спит, пока не придет первый клиент. Приходя в парикмахерскую, посетитель выполняет процедуру customer, запрашивая доступ к mutex для входа в критическую область. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобождает доступ к mutex и уходит. Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем самым активизируя поток брадобрея. В этот момент оба — посетитель и брадобрей — активны. Когда посетитель освобождает доступ к mutex, брадобрей захватывает его, проделывает некоторые служебные операции и начинает стричь клиента. По окончании стрижки посетитель выходит из процедуры и покидает парикмахерскую. В отличие от предыдущих программ, цикла посетителя нет, поскольку каждого посетителя стригут только один раз. Цикл брадобрея существует, и брадобрей пытается найти следующего посетителя. Если ему это удается, он стрижет следующего посетителя, в противном случае брадобрей засыпает. Стоит отметить, что, несмотря на отсутствие передачи данных в проблеме читателей и писателей и в проблеме спящего брадобрея, обе эти проблемы относятся к проблемам межпроцессного взаимодействия, поскольку требуют синхронизации нескольких процессов.

Похожие:

	Гносеологический анализ проблемы взаимодействия культур запада и востока Усиление взаимодействия между культурами – объективная закономерность новейшего времени. Многообразие культур		Темы рефератов по культурологии Элитарная и массовая культуры: проблемы взаимодействия в условиях современного социума
	Выпускная работа по «Основам информационных технологий» Проблемы взаимодействия ит и филигранологии (основные результаты исследования) 16		Регламент взаимодействия Участников информационного взаимодействия,... Гоу впо «башкирская академия государственной службы и управления при президенте республики башкортостан»
	Родительское собрание по правам детей Цель: Актуализация проблемы взаимодействия семьи и школы в обеспечении прав ребенка		Система взаимодействия власти и общества Институты политического опосредования: понятие и явление • Лоббизм и его место в системе взаимодействия власти и общества • Основные...
	Регламент взаимодействия Участников информационного взаимодействия,... Основная цель изучения курса “Исследование систем управления” приобретение знаний, формирование и развитие умений и навыков исследовательской...		Писарева С. А. Эмоционально-ценностные проблемы взаимодействия субъектов... Оперативное совещание «Планирование работы на месяц. Итоги проверки дневников учащихся 3-4 классов»
	Автономная некоммерческая организация высшего образования Приглашаем Вас принять участие в IX всероссийской с международным участием научно-практической конференции студентов «Человек. Общество....		2. содержание дисциплины раздел общие проблемы философии науки Таким образом, бренд будет обладать такими свойствами, которые создавали бы богатый чувственный и эмоциональный опыт его взаимодействия...
	Проблемы и перспективы экономического взаимодействия государств средней... Работа выполнена на кафедре мировой экономики и международных экономических отношений Дипломатической академии Министерства иностранных...		В конце XX начале XXI вв техническое и социальное развитие человечества... Увеличение числа международных неправительственных организаций и тенденции их дальнейшего роста обусловлены целым рядом причин, а...
	Тема: "Современные проблемы взаимодействия детского сада и семьи" В настоящее время система образования Российской Федерации переживает период реформирования, поиска новых форм работы с обучающимися...		Мировая экономика и национальное хозяйство: проблемы взаимодействия В конечном итоге хх1 век ознаменовался началом формирования единого глобального мирового хозяйства. В настоящее время ученые анализируют...
	Проблемы определения содержания римского права: исторический и цивилистический подход. Введение Представленный документ, содержит полное описание xml api протокола взаимодействия web-ориентированных клиентов, с сервером системы...		Программа по формированию навыков безопасного поведения на дорогах... Межпредметные связи в особенности важны для взаимодействия следующих дисциплин: «Современные проблемы истории и методологии политической...