Эмуляция обедающих философов

@yanyk1n · Регистрация: 12.03.2009

Студворк — интернет-сервис помощи студентам

Доброго времени суток, уважаемые форумчане! Необходима помощь в доработке одной программы...

Суть задачи:

K философов сидят за круглым столом, в центре которого стоит блюдо с рисом. Между каждой парой философов лежит палочка для еды, палочек, следовательно, тоже пять. Для того, чтобы начать есть, философ должен взять две палочки - слева и справа от себя. Таким образом, если один из философов ест, его соседи справа и слева лишены такой возможности, так как им недостает палочек. Каждый философ "работает" по зацикленному алгоритму: сначала он некоторое время думает, затем берет палочки и ест, затем опять думает и т.д. Временные интервалы мышления и еды случайны, действия философов, следовательно, не синхронизированы.

Задача:
Проэммулировать указанную ситуацию. Философы - отдельные процессы, палочки - семафоры (или мютексы)
В условии ничего не говорится про то каким образом философы берут палочки.

При этом требуется предоставить такой алгоритм, при котором гарантируется, что никогда не возникнет deadlock'а или бесконечного голодания.

Код я написал, иногда работает как надо (то есть иногда либо какой-то философ ест два раза подряд, некоторый дохнет от голода или вообще не принимает участие):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <semaphore.h>
#include <string.h>
#define LEFT (i + N - 1) % N //макрос, определяющий номер левого философа
#define RIGHT (i + 1) % N //макрос, определяющий номер правого философа
#define THINKING 0 //код состояния, когда философ размышляет
#define HUNGRY 1 //код состояния, когда философ хочет поесть (ожидает палочки)
#define EATING 2 //код состояния, когда философ ест
#define MAX_TIME 5 //максимальное время, которое может быть потрачено на еду и/или на размышления
 
//=====================================
//Решение было нагло и без спросу скопипастено из книги Таненбаума =)
//=====================================
 
int N; //количество философов
sem_t *mutex = NULL; //взаимное исключение входа в критическую область (взять - положить палочки)
sem_t *eaters = NULL; //указатель на sem_t, которые впоследствии станет указателем на массив из N семафоров
int* state = NULL; //указатель на массив int'ов, характеризующий состояния философов
 
//процесс поедания
void eat(int i) {
    int time = rand() % MAX_TIME;
    printf("Philosopher #%d is eating...\n", i + 1);
    sleep(time);
    printf("Philosopher #%d stopped eating...\n", i + 1);
}
 
//процесс размышлений
void think(int i) {
    int time = rand() % MAX_TIME;
    printf("Philosopher #%d is thinking...\n", i + 1);
    sleep(time);
}
 
//проверка, сможет ли приступить к еде голодный i-й философ...
void test(int i) {
    //если сам филосов голоден, а его соседи не едят (то есть вилки свободны)
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING; //меняем статус, что наш i-й философ поел
        sem_post(&eaters[i]); //филосов начал есть, поэтому инкрементируем семафор, чтобы философа не заблокировали соседи
    }
}
 
//i-й философ пытается взять палочку...
void take_sticks(int i) {
    sem_wait(mutex); //входим в критическую область, чтобы с палочками на данный момент работал только один философ
    state[i] = HUNGRY; //i-й философ теперь хочет есть (а он либо поест, либо не поест сразу, всё зависит от того, не едят ли его соседи...)
    test(i); //попытка взять две вилки...
    sem_post(mutex); //выходим из критической области
    sem_wait(&eaters[i]); //если не удалось начать есть (то есть sem_post не выполнился, и семафор равен нулю), то он блокируется.
    //разблокировать его смогут соседи после приёма пищи
}
 
void put_sticks(int i) {
    sem_wait(mutex); //входим в критическую область, чтобы с палочками на данный момент работал только один философ
    state[i] = THINKING; //i-й философ наелся, теперь начал думать
    test(LEFT); //проверяем, если сосед слева голоден (то есть ожидают вилку), то даём ему сигнал, чтобы они начали есть 
    //test(RIGHT); //аналогично с правым соседом...
    sem_post(mutex);
}
 
 
//код, выполняющийся каждым потоком (характеризующий поведение философа)
void* philosopher(void* arg) {
    int i = *((int*)arg);
    while (1 == 1) { //бесконечный цикл
        think(i); //сначала философ думает
        take_sticks(i); //затем берёт палочки (или, если быть точнее, пытается взять)
        eat(i); //ест
        put_sticks(i); //кладёт палочки обратно
    }
}
 
 
 
int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <NUMBER_OF_PHILOSOPHERS>\n", argv[0]);
        return 1;
    }
 
    //подготовительный процесс...
    N = atoi(argv[1]); //переводим из строки в целочисленную переменную
    if (N <= 1) { //если так вышло, что количество филосов меньше двух, то ругаемся и завершаем программу
        fprintf(stderr, "Error by transformation of the argument...\n");
        return 2; 
    }
 
    mutex = (sem_t*)malloc(sizeof(sem_t));
    if (sem_init(mutex, 0, 1) != 0) { //создаём мьютекс для разграничения доступа к критической области
        fprintf(stderr, "Error by creating semaphore...\n");
        return 3;
    }
 
    eaters = (sem_t*)calloc(N, sizeof(sem_t)); //выделяем память под N семафоров, характеризующих философов
    state = (int*)calloc(N, sizeof(int)); //выделяем память под N целочисленных аргументов, характеризующие состояния философов    
    
    memset(state, 0, N);
 
    srand(time(NULL));
    pthread_t *philosophers = (pthread_t*)malloc(N * sizeof(pthread_t)); //выделяем память под N потоков, символизирующие философов
 
    int i;
    for (i = 0; i < N; i++) {
        if (sem_init(&eaters[i], 0, 0) != 0) {  //создаём N семафоров
            fprintf(stderr, "Error by creating semaphore...\n");
            return 3;
        }
    }
    
    int *t = (int *)malloc(sizeof(int));
    for (i = 0; i < N; i++) {
        *t = i;
        if (pthread_create(&philosophers[i], NULL, philosopher, t) != 0) { //создаём потоки
            fprintf(stderr, "Error by creating thread\n");
            return 2;
        }
    }
    
    void* result;
    for (i = 0; i < N; i++) {
        if (philosophers[i] != -1) {
            if (pthread_join(philosophers[i], &result) != 0) {
                fprintf(stderr, "Error by joining thread\n");
                return 3;
            }
        }
    }
    return 0;
}

В чём я допустил ошибку(-и) и как их исправить? Буду очень благодарен за любую помощь

@romex · 03.06.2011, 22:41

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <semaphore.h>
#include <string.h>
#define LEFT (i + N - 1) % N //макрос, определяющий номер левого философа
#define RIGHT (i + 1) % N //макрос, определяющий номер правого философа
#define THINKING 0 //код состояния, когда философ размышляет
#define HUNGRY 1 //код состояния, когда философ хочет поесть (ожидает палочки)
#define EATING 2 //код состояния, когда философ ест
#define MAX_TIME 5 //максимальное время, которое может быть потрачено на еду и/или на размышления
 
//=====================================
//Решение было нагло и без спросу скопипастено из книги Таненбаума =)
//=====================================
 
int N; //количество философов
sem_t *mutex = NULL; //взаимное исключение входа в критическую область (взять - положить палочки)
sem_t *eaters = NULL; //указатель на sem_t, которые впоследствии станет указателем на массив из N семафоров
int* state = NULL; //указатель на массив int'ов, характеризующий состояния философов
 
//процесс поедания
void eat(int i) {
        int time = rand() % MAX_TIME;
        printf("Philosopher #%d is eating...\n", i + 1);
        sleep(time);
        printf("Philosopher #%d stopped eating...\n", i + 1);
}
 
//процесс размышлений
void think(int i) {
        int time = rand() % MAX_TIME;
        printf("Philosopher #%d is thinking...\n", i + 1);
        sleep(time);
}
 
//проверка, сможет ли приступить к еде голодный i-й философ...
void test(int i) {
        //если сам филосов голоден, а его соседи не едят (то есть вилки свободны)
        if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
                state[i] = EATING; //меняем статус, что наш i-й философ поел
                sem_post(&eaters[i]); //филосов начал есть, поэтому инкрементируем семафор, чтобы философа не заблокировали соседи
        }
}
 
//i-й философ пытается взять палочку...
void take_sticks(int i) {
        sem_wait(mutex); //входим в критическую область, чтобы с палочками на данный момент работал только один философ
        state[i] = HUNGRY; //i-й философ теперь хочет есть (а он либо поест, либо не поест сразу, всё зависит от того, не едят ли его соседи...)
        test(i); //попытка взять две вилки...
        sem_post(mutex); //выходим из критической области
        sem_wait(&eaters[i]); //если не удалось начать есть (то есть sem_post не выполнился, и семафор равен нулю), то он блокируется.
        //разблокировать его смогут соседи после приёма пищи
}
 
void put_sticks(int i) {
        sem_wait(mutex); //входим в критическую область, чтобы с палочками на данный момент работал только один философ
        state[i] = THINKING; //i-й философ наелся, теперь начал думать
        test(LEFT); //проверяем, если сосед слева голоден (то есть ожидают вилку), то даём ему сигнал, чтобы они начали есть 
//Я позволил себе убрать комментарий от test(RIGHT), очевидно поставленный для отладки.
        test(RIGHT); //аналогично с правым соседом... 
//
        sem_post(mutex);
}
 
 
//код, выполняющийся каждым потоком (характеризующий поведение философа)
void* philosopher(void* arg) {
        int i = *((int*)arg);
        while (1 == 1) { //бесконечный цикл
                think(i); //сначала философ думает
                take_sticks(i); //затем берёт палочки (или, если быть точнее, пытается взять)
                eat(i); //ест
                put_sticks(i); //кладёт палочки обратно
        }
}
 
 
 
int main(int argc, char* argv[]) {
        if (argc != 2) {
                fprintf(stderr, "Usage: %s <NUMBER_OF_PHILOSOPHERS>\n", argv[0]);
                return 1;
        }
 
        //подготовительный процесс...
        N = atoi(argv[1]); //переводим из строки в целочисленную переменную
        if (N <= 1) { //если так вышло, что количество филосов меньше двух, то ругаемся и завершаем программу
                fprintf(stderr, "Error by transformation of the argument...\n");
                return 2; 
        }
 
        mutex = (sem_t*)malloc(sizeof(sem_t));
        if (sem_init(mutex, 0, 1) != 0) { //создаём мьютекс для разграничения доступа к критической области
                fprintf(stderr, "Error by creating semaphore...\n");
                return 3;
        }
 
        eaters = (sem_t*)calloc(N, sizeof(sem_t)); //выделяем память под N семафоров, характеризующих философов
        state = (int*)calloc(N, sizeof(int)); //выделяем память под N целочисленных аргументов, характеризующие состояния философов     
        
        memset(state, 0, N);
 
        srand(time(NULL));
        pthread_t *philosophers = (pthread_t*)malloc(N * sizeof(pthread_t)); //выделяем память под N потоков, символизирующие философов
 
        int i;
        for (i = 0; i < N; i++) {
                if (sem_init(&eaters[i], 0, 0) != 0) {  //создаём N семафоров
                        fprintf(stderr, "Error by creating semaphore...\n");
                        return 3;
                }
        }
        
        int *t = (int *)malloc(sizeof(int));
        for (i = 0; i < N; i++) {
                *t = i;
                if (pthread_create(&philosophers[i], NULL, philosopher, t) != 0) { //создаём потоки
                        fprintf(stderr, "Error by creating thread\n");
                        return 2;
                }
        usleep(100000); //Вся загвоздка здесь! 
        //Дело в том, что Нить-родитель успевает изменить номер  i для следующей нити до инициализации предыдущей. То есть несколько нитей импользуют один номер.
      
    }
        
        void* result;
        for (i = 0; i < N; i++) {
                if (philosophers[i] != -1) {
                        if (pthread_join(philosophers[i], &result) != 0) {
                                fprintf(stderr, "Error by joining thread\n");
                                return 3;
                        }
                }
        }
        return 0;
}

Поправка на 63 и 125 строках
Вроде все комильфо. У меня в сетевых клиент-серверных крестиках-ноликах была та же ошибка!

Добавлено через 20 минут
Что любопытно, у меня все философы получали номер последнего всегда. Без исключений.

(то есть иногда либо какой-то философ ест два раза подряд, некоторый дохнет от голода или вообще не принимает участие)

У вас как я понял только часть философов получали одинаковые имена.
Тоже работаю под ubuntu(правда 10.10), но процессор - core i3. Выходит, что от архитектуры и мощности процессора сильно зависит квантование времени между нитями, а это не айс. Либо в 10.10 что-то наковыряли.
Надо как-нибудь взять две разные железки и потестить...

Новые блоги и статьи Все статьи Все блоги /
Видеокарта простаивает ночами? Вот 4 проекта, которые загрузят её наукой Programma_Boinc 10.04.2026 Видеокарта простаивает ночами? Вот 4 проекта, которые загрузят её наукой Если на Windows стоит дискретная NVIDIA или AMD — можно отдать её вычислительную мощность реальным исследованиям. . . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .