VPF::[Visual C++] Обедающие философы - Форум программистов

DubrovinAV

Дата 17.5.2008, 18:55 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 20.9.2007

Репутация: нет
Всего: нет

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

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

Поведение каждого философа должно моделироваться отдельным процессом или потоком. При использовании процессов, взаимодействие между процессами - философами может осуществляться через дополнительный процесс - обеденный стол, который знает информацию о наличии вилок на столе. В каждом процессе-философе должно быть реализовано несколько алгоритмов взятия вилок, причем номер алгоритма должен указываться при запуске процесса-философа:
1. Философ вначале пытается взять левую вилку, а затем, как только левая вилка оказалась у него, пытается взять правую. При этом он продолжает удерживать левую вилку, если правая недоступна. Если все философы действуют по такому алгоритму, то может возникнуть ситуация <голодная смерть>, т.е. Процессы, моделирующие философов окажутся в тупиковой ситуации (зависнут) 2. Философ выбирает первую вилку случайным образом, в остальном - все тоже самое, что и в первом алгоритме, в т.ч. возможно возникновение тупиковой ситуации, но с меньшей вероятностью, чем в первом случае.
3. Вы должны предложить и реализовать такой алгоритм поведения философов, который гарантированно не приведет к ситуациям <заговор соседей> и <голодная смерть>.

Проблемма с предотвращением ситуации заговор соседей. С этим и прошу помощи.
Привожу листинг для третьего задания(не реализовано предотвращения заговора соседей):

Код


#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);
}

Также прилагаю код всей программы:

Присоединённый файл ( Кол-во скачиваний: 268 )

phil.cpp 6,18 Kb

feexink

Дата 13.11.2022, 19:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 13.11.2022

Репутация: нет
Всего: нет

Модератор: Сообщение скрыто.

Noubpoeno

Дата 10.12.2022, 00:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 9.12.2022

Репутация: нет
Всего: нет

Модератор: Сообщение скрыто.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »