Форум программистов, компьютерный форум, киберфорум
С под Linux
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/29: Рейтинг темы: голосов - 29, средняя оценка - 4.83
4337 / 1469 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
1

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

28.05.2011, 00:06. Просмотров 5960. Ответов 1
Метки нет (Все метки)


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

Суть задачи:
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;
}
В чём я допустил ошибку(-и) и как их исправить? Буду очень благодарен за любую помощь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.05.2011, 00:06
Ответы с готовыми решениями:

задача про обедающих философов
Здравствуйте! Делаю программу про обедающих философов. ...

Реальзация задачи обедающих философов с помощью событий
помогите написать реальзацию задачи обедающих философов с помощью событий. не могу понять сколько...

Потоки. Event. Задача про обедающих философов.
Здравствуйте, товарищи. Возник вопрос непонимания, по которому не удалось продолбиться с помощью...

Как можно упростить код для обедающих философов и добавить описание действия для каждого философа?
import java.util.Random; import java.util.concurrent.Semaphore; import...

1
45 / 45 / 9
Регистрация: 11.04.2010
Сообщений: 223
03.06.2011, 22:41 2
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 что-то наковыряли.
Надо как-нибудь взять две разные железки и потестить...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.06.2011, 22:41

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

ТЕСТ: Кто Вы из греческих философов?
http://testoteka.ukr.net/testdrive/test/47/ Мой результат: Горгий Леонтийский Вы тонкий,...

Задача об обедающих философах
Тема заезженная,но все таки. Интересует решение задачи &quot;Обедающих философов&quot;. Мне надо сделать...

Задача об обедающих философах
Доброго времени суток! Поиском пользовался, но ответа для себя не нашёл, поэтому создаю тему. ...

Многопоточность: задача об обедающих философах
Доброго времени суток! Нужно перевести код с С++ с использованием библиотеки &lt;thread&gt; и &lt;mutex&gt; на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.