Что происходит, когда два или более философа проверяют мьютекс на 1 и одновременно выходят из него и входят в тестовую функцию

Question

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

В этом коде, как вы можете видеть, у нас изначально есть мьютекс, который означает, что ни один философ не проверяет, являются ли вилки свободными или нет. Что происходит, когда два или более философа одновременно проверяют мьютекс и видят, что мьютекс находится в одном и том же положении одновременно с мьютексом и входят в функцию, чтобы проверить, свободны ли вилы или нет? Это может случиться или нет - это мой вопрос?

Answer 1

Если бы вы использовали настоящие мьютексы и настоящие семафоры (как в POSIX Pthreads или C11 §7.26 Threads <threads.h>), то вы обнаружите, что мьютекс обеспечивает что у вас не может быть ситуации, когда «два или более философа проверяют мьютекс одновременно». Вот что означает «взаимное исключение».

Однако вы не используете «настоящие мьютексы» или «настоящие семафоры»; вы используете простой int как «семафор» для реализации того, что вы называете «мьютексом». Для простого int взаимное исключение не гарантируется - и вы не можете легко добиться этого с помощью простого C. Поэтому существует реальный риск того, что несколько философов будут проверять мьютекс одновременно. Код не является безопасным, если программа многопоточная.

Мы должны сказать «если программа многопоточная», поскольку программа не является MCVE ( Минимальный, Полный, Проверяемый пример ) ( или MRE или любое другое имя, которое теперь использует SO) или SSCCE ( Short, Self-Contained, Correct Example ). В ней отсутствует основная программа, поэтому невозможно определить, как на самом деле выполняется показанный код.

Answer 2

Вы правы, что беспокоитесь о возможности двух философов проверять мьютекс одновременно. Для правильной работы мьютекса это должно быть как-то сделано невозможным.

Если вы используете мьютексы и семафоры библиотеки 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. На самом деле это невозможно сделать с помощью обычного машинного языка. Вы должны использовать специальные atomi c машинные инструкции, чтобы выполнить эту работу. Пересмотренный в 2011 году стандарт C включает специальные функции для доступа к этим инструкциям; начните с прочтения документации по stdatomi c .h .

Имейте в виду, что примитивы синхронизации сложно сделать правильно, даже для экспертов. Если вы можете написать эту программу, используя семафоры и / или мьютексы, которые кто-то уже реализовал для вас, то вы должны сделать это следующим образом.

---

¹ Если вы работаете с компьютером, который только один процессор - то есть он не может выполнять более одного потока одновременно - и у вас есть возможность отключать прерывания, тогда машинные инструкции atomi c не являются строго необходимыми, но лучше использовать atomi c машинные инструкции в любом случае, так что скомпилированная программа все равно будет работать, если она когда-либо будет перемещена на компьютер с более чем одним ЦП.