Как решить проблему голода в задаче Dinning Philosophers с помощью условных переменных? - PullRequest
Новая
       25

Как решить проблему голода в задаче Dinning Philosophers с помощью условных переменных?

0 голосов
/ 12 мая 2019

Я написал простую программу, имитирующую Dinning Philosophers с помощью condition_variables, проблема в том, что некоторые философы никогда не получают возможность поесть.

Я пытался поместить точки останова в лямбда-функцию _condVar.Wait, чтобы убедиться, что метод putdownForksуведомляет другие ожидающие потоки, и я делаю, но я все еще не понимаю, почему другие потоки никогда не едят. 

#include <condition_variable>
#include <iostream>
#include <thread>
#include <unistd.h>

#define thread_num 5
#define HUNGRY 0
#define EATING 1
#define THINKING 2

using namespace std;

thread _threads[thread_num];
mutex _mutex;
condition_variable _condVar;
int _states[thread_num];
bool _isCancelRequested;

void think(int id){
    usleep(rand() % 1000000 + 2000000);
}
void eat(int id){
    usleep(rand() % 1000000 + 2000000);
}

void putdownForks(int id){   
    {
        unique_lock<mutex> lck(_mutex);          
        _states[id] = THINKING;
    }
    _condVar.notify_all();    
}

void pickupForks(int id){
    int leftNeighbourId = (id -1 )%thread_num;
    if(leftNeighbourId<0)leftNeighbourId+=thread_num;
    int rightNeighbourId= (id+1)%thread_num;
    {
        unique_lock<mutex> lck(_mutex);
        _states[id] = HUNGRY;
        bool isLeftNeighbourEating = _states[leftNeighbourId] == EATING;
        bool isRightNeighbourEating = _states[rightNeighbourId] == EATING;
        _condVar.wait(lck, 
            [isLeftNeighbourEating, isRightNeighbourEating]
                {
                    return !(isLeftNeighbourEating || isRightNeighbourEating);
                });    
        _states[id] = EATING;
    }  
}

void philosopher(int id){
    while(!_isCancelRequested){
        think(id);
        pickupForks(id);
        eat(id);
        putdownForks(id);
    }
}

void print_info()
{
    {
        unique_lock<mutex> lck(_mutex);
        for(int i=0;i<thread_num;i++)
        {
            cout << "Id: "<< i<< " State: "<< _states[i]<<endl;
        }
        cout << endl;
    }
}

void info(){
    while (!_isCancelRequested)
    {
        usleep(1000000);
        print_info();
    }    
}

int main(){
    for(int i=0; i<thread_num;i++){
        _threads[i]= thread(philosopher,i);
    }
    thread info_thread(info);

    for(int i=0; i<thread_num;i++){
        _threads[i].join();
    }  
    info_thread.join();
}

Это вывод, как состояния менялись с течением времени 

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 1
Id: 4 State: 0

Id: 0 State: 1
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

Id: 0 State: 2
Id: 1 State: 0
Id: 2 State: 0
Id: 3 State: 2
Id: 4 State: 0

ASВы можете видеть, что философы с id 1, 2 и 4 никогда не едят.

1 Ответ

0 голосов
/ 12 мая 2019

Ничего себе, на этот раз мне сложно пережить эффект стека. После уведомления необходимо переоценить условие ожидания, поэтому мне нужно «обновлять» состояние соседей при каждом уведомлении conditional_variable. Метод pickupForks должен выглядеть следующим образом: 

void pickupForks(int id){
    int leftNeighbourId = (id -1 )%thread_num;
    if(leftNeighbourId<0)leftNeighbourId+=thread_num;
    int rightNeighbourId= (id+1)%thread_num;
    {
        unique_lock<mutex> lck(_mutex);
        _states[id] = HUNGRY;
        _condVar.wait(lck, 
            [leftNeighbourId, rightNeighbourId]
                {
                    bool isLeftNeighbourEating = _states[leftNeighbourId] == EATING;
                    bool isRightNeighbourEating = _states[rightNeighbourId] == EATING;
                    return !(isLeftNeighbourEating || isRightNeighbourEating);
                });    
        _states[id] = EATING;
    }  
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...