（C） 如何让并发线程等待条件满足？

Question

我是一个初学者，我正在实施餐饮哲学家的问题。然而，我遇到了一个问题。在我的哲学家（）函数中，我希望我的其他线程等待，直到左右筷子都可以使用。我应该如何实现这一点？目前，该计划只是在两位哲学家吃完后终止，而不等待其他人吃完

我已经试过了：

• 使用互斥锁来锁定哲学家（）函数中的共享变量，虽然可以确保没有哲学家挨饿，但使用这种方法意味着放弃并发（即使有筷子可供其他哲学家使用，一次也只能有一位哲学家吃饭）

任何帮助都很感激，谢谢！

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

Answer 1

我是一个初学者，我正在解决哲学家的问题。然而，我遇到了一个问题。在我的哲学家（）函数中，我希望我的其他线程等待，直到左右筷子都可以使用。我应该如何实现这一点？

我已经试过了：

• 使用互斥锁来锁定哲学家（）函数中的共享变量，虽然可以确保没有哲学家挨饿，但使用这种方法意味着放弃并发（即使有筷子可供其他哲学家使用，一次也只能有一位哲学家吃饭）

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

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

• 在while循环中使用sleep（）函数，但它也不起作用

正如我在评论中所写，sleep（）不是一个同步函数。它可能在html" target="_blank">解决方案中起作用，但在线程间活动中不起作用。

对于哲学家进餐问题，需要认识到的关键是，如果你想让哲学家同时进餐，而不必安排整个进餐的细节，那么每个哲学家必须能够多次尝试拿起筷子，直到他们成功，同时不妨碍任何其他哲学家进餐。

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

当线程需要等待，直到满足某些依赖于数据的条件时，应立即考虑使用条件变量。有时有合理的选择，但条件变量是这些情况下的瑞士军刀。

条件变量与互斥体一起使用--互斥体用于保护非原子变量，每个线程将通过这些变量确定是否可以继续，如果线程确定它必须等待，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);

当哲学家吃完后，他锁上互斥锁，放下筷子，释放互斥锁，然后向所有等待简历的线程发出信号，这样他们就会再次检查他们是否可以继续。

例如：

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

还要注意的是，由于筷子状态是通过互斥来保护的，因此使用信号量对其进行建模没有任何好处。上面的示例代码假设一个普通的\u Bool数组或其他一些整数类型，用全零初始化。

Answer 2

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

只有当两个叉子都能起作用时，这两个叉子才会起作用

哲人的套路是：0。每个哲学家都会有与她相关的状态。国家由邻居介绍，以了解哲学家在做什么。

1. 花时间思考。哲学家的状态是思考
2. 哲学家变得饥饿，哲学家的状态就是饥饿
3. 检查是否可以拾取左叉和右叉。（即确保左邻右舍

伪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/