我撰寫了這個程式來使用 Dijkstra 演算法解決哲學家進餐問題，請注意我使用的是布爾陣列 ( data->locked) 而不是二進制信號量陣列。
我不確定這個解決方案是否有效（因此是 SO 問題）。
訪問和函式中的data->locked陣列會導致資料競爭嗎？如果是這樣，甚至可以使用僅使用互斥鎖的 Dijkstra 演算法來解決這個問題嗎？testtake_forks
我只被允許使用互斥鎖，沒有信號量，沒有條件變數（這是一個賦值）。
使用示例：
./a.out 4 1000 1000
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stdbool.h>
#define NOT_HUNGRY 1
#define HUNGRY 2
#define EATING 3
#define RIGHT ((i 1) % data->n)
#define LEFT ((i data->n - 1) % data->n)
typedef struct s_data
{
int n;
int t_sleep;
int t_eat;
int *state;
bool *locked;
pthread_mutex_t *state_mutex;
} t_data;
typedef struct s_arg
{
t_data *data;
int i;
} t_arg;
int ft_min(int a, int b)
{
if (a < b)
return (a);
return (b);
}
int ft_max(int a, int b)
{
if (a > b)
return (a);
return (b);
}
// if the LEFT and RIGHT threads are not eating
// and thread number i is hungry, change its state to EATING
// and signal to the while loop in `take_forks` to stop blocking.
// if a thread has a state of HUNGRY then it's guaranteed
// to be out of the critical section of `take_forks`.
void test(int i, t_data *data)
{
if (
data->state[i] == HUNGRY
&& data->state[LEFT] != EATING
&& data->state[RIGHT] != EATING
)
{
data->state[i] = EATING;
data->locked[i] = false;
}
}
// set the state of the thread number i to HUNGRY
// and block until the LEFT and RIGHT threads are not EATING
// in which case they will call `test` from `put_forks`
// which will result in breaking the while loop
void take_forks(int i, t_data *data)
{
pthread_mutex_lock(data->state_mutex);
data->locked[i] = true;
data->state[i] = HUNGRY;
test(i, data);
pthread_mutex_unlock(data->state_mutex);
while (data->locked[i]);
}
// set the state of the thread number i to NOT_HUNGRY
// then signal to the LEFT and RIGHT threads
// so they can start eating when their neighbors are not eating
void put_forks(int i, t_data *data)
{
pthread_mutex_lock(data->state_mutex);
data->state[i] = NOT_HUNGRY;
test(LEFT, data);
test(RIGHT, data);
pthread_mutex_unlock(data->state_mutex);
}
void *philosopher(void *_arg)
{
t_arg *arg = _arg;
while (true)
{
printf("%d is thinking\n", arg->i);
take_forks(arg->i, arg->data);
printf("%d is eating\n", arg->i);
usleep(arg->data->t_eat * 1000);
put_forks(arg->i, arg->data);
printf("%d is sleeping\n", arg->i);
usleep(arg->data->t_sleep * 1000);
}
return (NULL);
}
void data_init(t_data *data, pthread_mutex_t *state_mutex, char **argv)
{
int i = 0;
data->n = atoi(argv[1]);
data->t_eat = atoi(argv[2]);
data->t_sleep = atoi(argv[3]);
pthread_mutex_init(state_mutex, NULL);
data->state_mutex = state_mutex;
data->state = malloc(data->n * sizeof(int));
data->locked = malloc(data->n * sizeof(bool));
while (i < data->n)
{
data->state[i] = NOT_HUNGRY;
data->locked[i] = true;
i ;
}
}
int main(int argc, char **argv)
{
pthread_mutex_t state_mutex;
t_data data;
t_arg *args;
pthread_t *threads;
int i;
if (argc != 4)
{
fputs("Error\nInvalid argument count\n", stderr);
return (1);
}
data_init(&data, &state_mutex, argv);
args = malloc(data.n * sizeof(t_arg));
i = 0;
while (i < data.n)
{
args[i].data = &data;
args[i].i = i;
i ;
}
threads = malloc(data.n * sizeof(pthread_t));
i = 0;
while (i < data.n)
{
pthread_create(threads i, NULL, philosopher, args i);
i ;
}
i = 0;
while (i < data.n)
pthread_join(threads[i ], NULL);
}
uj5u.com熱心網友回復：
你的自旋回圈while (data->locked[i]);是一場資料競賽；您在讀取它時沒有持有鎖data->locked[i]，因此另一個執行緒可以在您讀取它時獲取鎖并寫入同一個變數。事實上，你依賴于這種情況。但這是未定義的行為。
直接的實際后果是編譯器可以洗掉測驗（因為在沒有資料競爭的情況下，data->locked[i]無法在迭代之間更改），或者完全洗掉回圈（因為它現在是一個無限回圈，并且非平凡的無限回圈是 UB）。當然，其他不希望的結果也是可能的。
所以你必須在測驗標志時持有互斥鎖。如果它是假的，那么你應該持有互斥鎖，直到你將它設定為真并做你的其他作業；否則會有一場比賽，另一個執行緒可以先得到它。如果為真，則洗掉互斥體，稍等片刻，再取一次，然后重試。
（“一小段時間”有多長，以及您在這期間選擇做什么作業，可能是您應該測驗的事情。根據您的 pthread 實作使用哪種公平演算法，您可能會遇到take_forks成功重新獲得鎖的情況即使put_forks也在等待鎖定它。）
當然，在一個“真正的”程式中，你一開始就不會這樣做。你會使用條件變數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/447424.html