0

我是一个初学者，我正在实施餐饮哲学家的问题。但是，我遇到了一个问题。在我的哲学家（）函数中，我希望我的其他线程等到左右筷子可供它们使用。我应该如何实现这个？目前，程序只是在 2 位哲学家吃完后终止，而无需等待其他人吃完

我已经尝试过：

  • 使用互斥锁来锁定 philosopher() 函数中的共享变量，虽然它可以确保没有哲学家挨饿，但使用这种方法意味着放弃并发性（即使有筷子可供其他哲学家使用，也只有一个哲学家可以同时进食）利用）
  • 在我的 while 循环中使用 sleep() 函数，但它也不起作用

任何帮助表示赞赏，谢谢！

代码

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h> 
#include <stdlib.h>

#define NUM 5  // Number of Philosophers
sem_t chopSticks[NUM]; // binary semaphore for each chopstick
sem_t mutex;
int philNo[NUM] = {0, 1, 2, 3, 4};

void* philosopher(void*);

int main()
{
    int semValue;
    pthread_t threadId[NUM]; // 5 concurrent threads for 5 philsophers
    sem_init(&mutex, 0, 1);
    for(int i=0; i< NUM; i++)
        sem_init(&chopSticks[i], 0, 1); 
    
    for(int i=0; i< NUM; i++)
    {
        pthread_create(&threadId[i], NULL, philosopher, (void*) &philNo[i]);
        printf("\nPhilosopher %d is thinking", i+1);
    }
    
    for(int i=0; i< NUM; i++)
        pthread_join(threadId[i], NULL);

return 0;
}

void* philosopher(void* philNo)
{
    int n = *(int*) philNo;
    int rightValue, leftValue;
    
    int left = (n+4) % NUM; 
    int right = (n+1) % NUM; 
    sem_getvalue(&chopSticks[left], &leftValue);
    sem_getvalue(&chopSticks[right], &rightValue);
    
    //sem_wait(&mutex);
    /* while(leftValue != 1 && rightValue != 1)
    {
        wait for the left and right chopsticks to be free
        How should I implement this?
    } */
        
    if(leftValue == 1 && rightValue == 1) // if both left and right chopSticks are free then start eating
    {
        sem_wait(&chopSticks[left]);
        sem_wait(&chopSticks[right]);
        printf("\nPhilosopher %d has taken Chopstick-%d and Chopstick-%d", n+1, left+1, right+1);
        printf("\nPhilosopher %d is Eating", n+1);
        sleep(1);
        sem_post(&chopSticks[left]);
        sem_post(&chopSticks[right]);
        printf("\nPhilosopher %d finished eating", n+1);
        printf("\nPhilosopher %d has put down chopstick-%d and chopstick-%d", n+1, left+1, right+1);
        
    }
    //sem_post(&mutex);
}
4

2 回答 2

0

餐桌上的每个叉子都不能有 sempahore。这是一个典型的错误，会导致你陷入僵局。想象一下，所有哲学家同时拿起左叉，你的信号量实现将允许这样做，但在那之后，没有人能够拿起右叉，因为没有可用的并且所有线程都将无限期地阻塞。

唯一可行的解​​决方案是哲学家在左右叉子都可用之前不会拿起任何叉子（即两个邻居都没有同时吃饭。）

哲学家的惯例是： 0. 每个哲学家都会有与她相关的状态。该州由邻居转介以了解哲学家在做什么。

  1. 花时间思考。哲学家的状态是思考。
  2. 哲学家饿了，哲学家的状态是饥饿。
  3. 检查您是否可以拿起左叉和右叉。（即确保左邻居和右邻居的状态不是 EATING。）如果任何一个 fork 不可用，则在它们可用之前阻塞。
  4. 当两个叉子都可用时，将状态更改为 EATING，拿起叉子并开始进食。
  5. 当你吃完。放下左叉子，检查你的左邻居是否被你放下的叉子挡住了，如果她叫醒她开始吃饭。然后放下右边的叉子，检查你的右边邻居是否被你放下的叉子挡住了，她是否叫醒她开始吃饭。
  6. 转到步骤 1。

伪oop代码如下：

#define N 5
#define LEFT(i) (i-1)%N
#define RIGHT(i) (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
 
class DinningPhilosopher {
public:
    DinningPhilosopher();
    ~DinningPhilosopher();
    void
    philosopherRoutine(
        IN byte i
        );
 
private:
    byte m_state[N];
    Semaphore *m_sem[N];
    Mutex *m_mutex;
 
    void
    takeForks(
        IN byte i
        );
 
    void
    putForks(
        IN byte i
        );
 
    void
    testForkAvailability(
        IN byte i
        );
};
 
DinningPhilosopher::DinningPhilosopher()
{
    // All philosopher's are thinking initially.
    for (int i=0; i<N; i++) {
        m_state[i] = THINKING;
    }
    for (int i=0; i<N; i++) {
        m_sem[i] = new Semaphore(0);
    }
    m_mutex = new Mutex();
}
 
// N threads will be spawned, one for each philosopher.
// Argument i is philosopher id between (0,N)
void
DinningPhilosopher::philosopherRoutine(
    IN byte i
    )
{
    while(true) {
        continueThinking();
        takeForks(i);
        continueEating();
        putForks(i);
    }
}
 
void
DinningPhilosopher::takeForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're HUNGRY.
        m_state[i] = HUNGRY;
        // Test if left fork & right forks are available.
        // If available announce neighbours you're EATING.
        // so they don't pick up forks you already claimed.
        testForkAvailability(i);
    m_mutex->unlock();
    // If you are not yet EATING,
    // block till required forks are available.
    // Section A.
    m_sem[i]->wait();
}
 
void
DinningPhilosopher::testForkAvailability(
    IN byte i
    )
{
    // Note that m_mutex was locked before calling this function
    // Thread has exclusive access to execute this function.
    if (m_state[LEFT(i)] != EATING && // your left fork is available
        m_state[RIGHT(i)] != EATING && // your right fork is available
        m_state[i] == HUNGRY // and you want to start eating.
        ) {
        // Announce neighbours you started eating.
        m_state[i] = EATING;
        // Fork availability is passed.
        // Make sure you're not blocked at "Section A"
        // in function takeForks()
        m_sem[i]->post();
    }
}
 
void
DinningPhilosopher::putForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're done EATING.
        m_state[i] = THINKING;
        // Put down the left fork,
        // If your left neighbour is blocked at "Section A"
        // of function takeForks().
        // Allow him to unblock to start eating.
        testAvailability(LEFT(i));
        // Put down the right fork.
        testAvailability(RIGHT(i));
    m_mutex->unlock();
}

查看以下链接： https ://codeistry.wordpress.com/2018/04/06/dinning-philosophers-problem/

于 2021-10-18T05:19:22.620 回答
0

我是一个初学者，我正在实施餐饮哲学家的问题。但是，我遇到了一个问题。在我的哲学家（）函数中，我希望我的其他线程等到左右筷子可供它们使用。我应该如何实现这个？

我已经尝试过：

  • 使用互斥锁来锁定 philosopher() 函数中的共享变量，虽然它可以确保没有哲学家挨饿，但使用这种方法意味着放弃并发性（即使有筷子可供其他哲学家使用，也只有一个哲学家可以同时进食）利用）

您绝对需要至少一个互斥锁或类似的同步对象，因为您的线程需要访问共享数据（筷子的状态，或等价物）。共享数据只能在受适当同步对象保护的临界区中访问。

但是，您不一定需要在此类访问之间保持互斥锁锁定，并且通常您希望避免这样做，以便其他线程有机会运行。

  • 在我的 while 循环中使用 sleep() 函数，但它也不起作用

正如我在评论中所写，sleep()不是同步功能。它可能会在解决方案中发挥作用，但不会在线程间活动中发挥作用。

哲学家进餐问题要认识到的关键是，如果您希望哲学家同时进餐而不必精心安排整顿饭，那么每个哲学家必须能够多次尝试拿起筷子直到他们成功，而不会阻止任何其他人哲学家从吃在此期间。

此外，当线程没有理由认为自上次尝试以来发生了任何变化时，它会适得其反。

当线程需要等待直到满足某些数据相关条件才能继续时，您应该立即考虑使用条件变量。有时有合理的替代方案，但条件变量是这些情况下的瑞士军刀。

条件变量与互斥锁一起使用——互斥锁用于保护非原子变量，每个线程将通过这些变量确定它是否可以继续，如果线程确定它必须等待，CV 会帮助它同时允许其他线程在等待时锁定互斥锁，并在接收到它应该再次检查的通知时。这应该始终在循环中执行，因为线程可能会在唤醒后确定条件仍然不适合它继续前进。

在餐饮哲学家问题中，有几种方法可以实现这一点。您可以为每根筷子使用单独的条件变量，它们都具有相同的互斥锁，但只使用一个互斥锁和一个 CV 会更简单：

  • 当其中一位哲学家决定他准备好吃饭时，他锁定互斥锁，并检查他需要的两根筷子是否都可用。

    • 如果是这样，他拿起它们，释放互斥体，然后继续吃。

    • 如果不是，那么他等待条件变量被另一个线程发出信号。在此等待期间互斥锁会自动释放，并在线程从中恢复之前重新获得。当线程恢复时，它会循环回来再次检查筷子。

    例如（为清楚起见省略了错误检查）：

    pthread_mutex_lock(&mutex);
while(chopsticks[left] || chopsticks[right]) {
    pthread_cond_wait(&cv, &mutex);
}
chopsticks[left] = 1;
chopsticks[right] = 1;
pthread_mutex_unlock(&mutex);

  • 当哲学家吃完饭后，他锁定互斥体，放下筷子，释放互斥体，然后向所有等待 CV 的线程发出信号，以便它们再次检查是否可以继续。

    例如：

    pthread_mutex_lock(&mutex);
chopsticks[left] = 0;
chopsticks[right] = 0;
pthread_mutex_unlock(&mutex);
pthread_cond_broadcast(&cv);

另请注意，由于筷子状态是通过互斥锁保护的，因此使用信号量对其进行建模没有任何优势。上面的示例代码假定一个普通数组_Bool或其他整数类型，初始化为全零。

于 2021-10-20T03:13:29.777 回答