|
|
|
|
| Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Задача об обедающих философах Дейкстры |
|
|
C/C++ - Задача об обедающих философах Дейкстры
|
|
Старожил Сообщения: 222 |
Вот немогу решить эту задачю:
За круглым столом расставлены N стульев, на каждом из которых сидит философ. В центре стола размещено блюдо с макаронами. На столе лежат N вилок, каждая из которых находится между двумя соседними тарелками. Каждый философ может находиться в двух состояниях: размышлять или есть макароны. Для того, чтобы начать есть, философу необходимы две вилки: одна в правой руке, а другая в левой. Закончив еду, философ кладет вилки на место и начинает размышлять до тех пор, пока снова не проголодается. В этой задаче имеются две опасные ситуации: <заговор соседей> и <голодная смерть>. <Заговор соседей> имеет место, когда соседи слева и справа от философа строят козни. Заговорщики поочередно забирают вилки то слева, то справа от <жертвы>. Такие согласованные действия злоумышленников приводят жертву к вынужденному голоданию, так как он никогда не может воспользоваться обеими вилками. <Голодная смерть> возникает, когда философы одновременно проголодаются и одновременно попытаются взять, например, свою левую вилку. При этом возникает тупиковая ситуация, так как никто из них не может начать есть, не имея второй вилки. Поведение каждого философа должно моделироваться отдельным процессом или потоком. При использовании процессов, взаимодействие между процессами - философами может осуществляться через дополнительный процесс - обеденный стол, который знает информацию о наличии вилок на столе. В каждом процессе-философе должно быть реализовано несколько алгоритмов взятия вилок, причем номер алгоритма должен указываться при запуске процесса-философа: 1. Философ вначале пытается взять левую вилку, а затем, как только левая вилка оказалась у него, пытается взять правую. При этом он продолжает удерживать левую вилку, если правая недоступна. Если все философы действуют по такому алгоритму, то может возникнуть ситуация <голодная смерть>, т.е. Процессы, моделирующие философов окажутся в тупиковой ситуации (зависнут) 2. Философ выбирает первую вилку случайным образом, в остальном - все тоже самое, что и в первом алгоритме, в т.ч. возможно возникновение тупиковой ситуации, но с меньшей вероятностью, чем в первом случае. 3. Вы должны предложить и реализовать такой алгоритм поведения философов, который гарантированно не приведет к ситуациям <заговор соседей> и <голодная смерть>. Помогите плиз, написал вроде все правильно но не работает в чем загвоздка??? Код:
 #include <windows.h>
#include <iostream>
using namespace std;
#define N 5 //Число философов
#define LEFT (i-1)%N //Левый сосед философа с номером i
#define RIGHT (i+1)%N //Правый сосед философа сномером i
#define THINKING 0 //Философ размышляет
#define HUNGRY 1 //Философ получается получить вилки
#define EATING 2 //Философ ест
int state[N]; //Состояния каждого философа
struct Philosopher //Описание философа: номер, алгоритм
{
int number;
int algorithm;
};
CRITICAL_SECTION cs; //Для критических секций: синхрон. процессов
CRITICAL_SECTION cs_forks; //и синхр. вилок
HANDLE philMutex[N]; //Каждому философу по мьютексу
void think(int i) //Моделирует размышления философа
{
EnterCriticalSection( &cs ); //Вход в критическую секцию
cout<<"Philosopher number "<<i<<" thinking"<<endl;
LeaveCriticalSection( &cs ); //Выход из критической секции
}
void eat(int i) //Моделирует обед философа
{
EnterCriticalSection( &cs ); //Вход в критическую секцию
cout<<"Philosopher number "<<i<<" eating"<<endl;
LeaveCriticalSection( &cs ); //Выход из критической секции
}
void test(int i) //Проверка возможности начать философом обед
{
if(state[i]==HUNGRY&&state[left]!=EATING&&state[right]!=EATING)
{
state[i]=EATING;
ReleaseMutex( philMutex[i] );
}
}
void take_forks(int i) //Взятие вилок
{
EnterCriticalSection( &cs_forks ); //Вход в критическую секцию
state[i]=HUNGRY; //Фиксация наличия голодного философа
test(i); //Попытка получить две вилки
LeaveCriticalSection( &cs_forks ); //Выход из критической секции
WaitForSingleObject( philMutex[i], INFINITE ); //Блокировка если вилок не досталось
}
void put_forks(int i) //Философ кладет вилки обратно
{
EnterCriticalSection( &cs_forks ); //Вход в критическую секцию
state[i]=THINKING; //Философ перестал есть
test(LEFT); //Проверить может ли есть сосед слева
test(RIGHT); //Проверить может ли есть сосед справа
LeaveCriticalSection( &cs_forks ); //Выход из критической секции
}
DWORD WINAPI philosopher(void *lParam) //Собственно модель философа
{
Philosopher phil=*((Philosopher *)lParam); //Получаем модель философа
while(1) //Моделируем обед
{ //Берем вилки
if(phil.algorithm==2) //Берем обе вилки
{
think(phil.number); //Думаем
take_forks(phil.number);//Берем вилки
eat(phil.number); //Едим
}
//кладем вилки
if(phil.algorithm==2) //Кладем вилки по третьему алгоритму
put_forks(phil.number);
Sleep(10); //Даем время на переключение контекста
}
}
int main()
{
Philosopher phil[N];
for(int i=0; i<N; i++) //Создаем мьютексы
{
philMutex[i] = CreateMutex( NULL, FALSE, NULL );
}
InitializeCriticalSection( &cs ); //Инициализируем
InitializeCriticalSection( &cs_forks ); //критические секции
DWORD id[N]; //Идентификаторы потоков
HANDLE hThread[N]; //Потоки
for(int i=0; i<N; i++)//Создаем потоки
{
hThread[i] = CreateThread(NULL, NULL, &philosopher, &phil[i], NULL, &id[i]);
}
Sleep(INFINITE); //Чтобы потоки успели выполнится с корректными значениями
while(1);
}
|
|
|
------- Отправлено: 00:20, 26-04-2010 |
Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать что не работает то?
-- внутри одного процесса мутекс и critical section даёт один эффект. А в данном случае я бы рекомендовал InterlockedCompareExchange |
|
Отправлено: 12:53, 27-04-2010 | #2 |
|
Старожил Сообщения: 222
|
Профиль | Отправить PM | Цитировать Цитата pva:
Не работает то что каждый философ сразу берет вилку , у вех философов по одной вилке в руке и они ожидают када освободится вторая, и все висит. |
|
|
------- Отправлено: 19:14, 28-04-2010 | #3 |
|
Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать можно внести элемент случайности (не обязательно по команде брать левую вилку) можно подумать случайное число секунд, попробовать взять случайной рукой вилку. Если вилка занята, подождать случайное число секунд, взять случайную вилку.
InterlockedExchange выполняет атомарную операцию, т.е. за 1 цикл процессора, не позволяя двум потокам выполнить её одновременно. InterlockedExchange меняет местами 2 dword-а, InterlockedCompareExchange сравнивает 2 значения и меняет их местами с 3-м, если сравнение дало true. На интеловских процессорах выполняется одной инструкцией. |
|
Отправлено: 00:00, 02-05-2010 | #4 |
|
Участник сейчас на форуме |
 |
Участник вне форума |
 |
Автор темы |
 |
Сообщение прикреплено |
| |||||
| Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
| VBA - Задача по информатике | Triz | Программирование и базы данных | 22 | 24-12-2012 23:02 | |
| C/C++ - Математическая задача | pirojok750 | Программирование и базы данных | 19 | 03-10-2009 12:36 | |
| Теория - Задача | ManHack | Программирование и базы данных | 4 | 23-01-2009 18:21 | |
| Delphi - Простая задача | rim_muvies | Программирование и базы данных | 13 | 31-03-2008 13:44 | |
| Задача С++ | papam | Программирование и базы данных | 1 | 28-11-2005 11:34 | |
|
|
Время: 05:49. | © OSzone.net 2001-
|
|
Powered by: vBulletin Copyright ©2000 - 2025, Jelsoft Enterprises Ltd. |
