0 
#define N 5 /* number of philosophers */
#define LEFT (i + N−1) % N /* number of i’s left neighbor */
#define RIGHT (i + 1) % N /* number of i’s right neighbor */
#define THINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is trying to get for ks */
#define EATING 2 /* philosopher is eating */

typedef int semaphore; /* semaphores are a special kind of int */

int state[N]; /* array to keep track of everyone’s state */
semaphore mutex = 1; /* mutual exclusion for critical regions */
semaphore s[N]; /* one semaphore per philosopher */

void philosopher(int i) /* i: philosopher number, from 0 to N−1 */
{
    while (TRUE) /* repeat forever */
    {
        think(); /* philosopher is thinking */
        take forks(i); /* acquire two for ks or block */

        eat(); /* yum-yum, spaghetti */
        put forks(i); /* put both for ks back on table */
    }
}

void take forks(int i) /* i: philosopher number, from 0 to N−1 */
{
    down(&mutex); /* enter critical region */
    state[i] = HUNGRY; /* record fact that philosopher i is hungry */
    test(i); /* tr y to acquire 2 for ks */
    up(&mutex); /* exit critical region */
    down(&s[i]); /* block if for ks were not acquired */
}

void put forks(i) /* i: philosopher number, from 0 to N−1 */
{
    down(&mutex); /* enter critical region */
    state[i] = THINKING; /* philosopher has finished eating */
    test(LEFT); /* see if left neighbor can now eat */
    test(RIGHT); /* see if right neighbor can now eat */
    up(&mutex); /* exit critical region */
}

void test(i) /* i: philosopher number, from 0 to N−1 */
{
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
    {
        state[i] = EATING;
        up(&s[i]);
    }
}

如您所见，在这段代码中，我们有一个互斥锁，它最初是一个互斥锁，这意味着没有哲学家在测试分叉是否是免费的。当两个或多个哲学家同时检查互斥锁并碰巧看到互斥锁是一个并且两者同时在互斥锁下并进入该函数以测试分叉是否空闲时会发生什么？这是否会发生是我的问题？

4

2 回答 2

3

如果您使用的是真正的互斥锁和真正的信号量（如POSIX Pthreads或 C11 §7.26 Threads<threads.h>中所见），那么您会发现互斥锁确保您不会遇到“两个或多个哲学家同时检查互斥锁”的情况时间”。这就是“互斥”的意思。

但是，您没有使用“真正的互斥锁”或“真正的信号量”；您正在使用普通int作为“信号量”来实现您所谓的“互斥量”。使用普通 C 不能保证互斥int——而且你不能使用普通 C 轻松实现它。因此，你可能有多个哲学家同时检查互斥锁的真正风险。如果程序是多线程的，那么代码是不安全的。

我们不得不说“如果程序是多线程的”，因为该程序不是 MCVE（最小、完整、可验证示例）（或 MRE 或 SO 现在使用的任何名称）或 SSCCE（简短、自包含、正确示例）。它缺少主程序，因此无法判断显示的代码是如何实际执行的。

于 2020-03-11T15:04:10.520 回答
1

您担心两位哲学家同时检查互斥锁的可能性是正确的。为了使互斥体正常工作，必须以某种方式使其成为不可能。

如果您使用 C 库的互斥锁和信号量，C 库保证这是不可能的。具体来说，在这段代码中：

void take_forks(int i) /* i: philosopher number, from 0 to N−1 */
{
    down(&mutex); /* enter critical region */

如果两个或多个线程down同时在一个未锁定的互斥体上调用，down则将锁定授予其中一个线程，并将立即返回该线程。所有其他线程将被“阻塞”，直到持有锁的线程通过调用up. 然后其中一个等待线程将收到锁，down将在该线程中返回，依此类推。

现在，你写了

typedef int semaphore; /* semaphores are a special kind of int */

这让我觉得你没有使用 C 库的信号量，你被分配自己实现它们。你要知道，这是用普通的C语言做不到的。事实上，用普通的机器语言是做不到的。您必须使用特殊的原子机器指令才能完成这项工作。¹ C 标准的 2011 年修订版包括用于访问这些指令的特殊功能；首先阅读stdatomic.h的文档。

请注意，同步原语很难正确处理，即使对于专家来说也是如此。如果有任何方法可以使用其他人已经为您实现的信号量和/或互斥锁来编写此程序，那么您应该这样做。

¹ 如果您正在使用只有一个 CPU 的计算机——也就是说，它不能同时执行多个线程——并且您有能力禁用中断，那么原子机器指令并不是绝对必要的，但是无论如何，最好使用原子机器指令，这样编译后的程序在移动到具有多个 CPU 的计算机时仍然可以工作。

于 2020-03-11T15:11:57.520 回答