(C)用餐哲学家-如何让并发线程等待条件得到满足

我是一个初学者，我正在实现Dining Philosopher的问题。然而，我遇到了一个问题。在我的philospher()函数中，我希望其他线程等待左右筷子可用。我应该如何实现这一点？目前，该程序只是在两位哲学家吃完饭后终止，而不等待其他人吃

我已经试过了：

使用互斥锁锁定philospher()函数中的共享变量，尽管它可以确保没有哲学家挨饿，但使用这种方法意味着放弃并发性(一次只能有一个哲学家吃饭，即使其他哲学家可以使用筷子)
在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);
}

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

唯一可行的解决方案是哲学家不会拿起任何叉子；可以使用右手叉子(即两个邻居都没有同时用餐。)

哲学家的日常生活是：每个哲学家都会有与她相关的状态。邻居们向该州介绍这位哲学家在做什么。

花时间思考。哲学家的境界是思考
哲学家变得饥饿，哲学家的状态是饥饿
检查你是否可以拿起左叉子和右叉子。(即，确保左邻居和右邻居的状态不是EATING。)如果其中一个叉子不可用，请阻止，直到它们可用
当两个叉子都可用时，将状态更改为EATING，拿起叉子开始吃东西
等你吃完了。放下左叉子，检查你的左邻居是否被你放下的叉子挡住了，她是否叫醒她开始吃东西。然后放下右边的叉子，检查你的右边邻居是否被你放下的叉子挡住了，她是否叫醒她开始吃东西
转到步骤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/

我是一个初学者，我正在实现Dining Philosopher的问题。然而，我遇到了一个问题。在我的philospher()函数中，我想要我的其他线要等左右筷子都到了可供他们使用。我应该如何实现这一点？

我已经尝试过：

使用互斥锁锁定philospher()函数中的共享变量，尽管它可以确保没有哲学家挨饿，使用这种方法意味着放弃并发性(只有一位哲学家即使有筷子可供其他人使用，也可以一次吃哲学家使用)

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

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

在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或其他整数类型的普通数组，用全零初始化。

代码

相关内容

最新更新

热门标签：