Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Ruslanizlugansk
0 / 0 / 0
Регистрация: 31.05.2015
Сообщений: 10
1

Реализация стека строк в разделяемой памяти (MPI)

25.11.2017, 17:34. Просмотров 867. Ответов 3
Метки нет (Все метки)

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

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
141
142
143
144
145
146
147
148
149
150
151
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<mpi.h>
// размер участка распределённого стека у каждого процесса
#define SIZE 2
//сообщения
#define MSG_CAN_PUSH 0
#define MSG_CAN_POP 1
#define MSG_KILL 2
int nproc;
int push(char *str) //занести строку в стек
{
 int r,message=MSG_CAN_PUSH;
 MPI_Status status;
 for(r=1;r<nproc;r++) //цикл по процессам
 {
//запрос на наличие места в памяти
 MPI_Send(&message,1,MPI_INT,r,0,MPI_COMM_WORLD);
//получаем ответ
 MPI_Recv(&message,1,MPI_INT,r,0,MPI_COMM_WORLD,&status);
 if(message) //если есть место, то..
 {
 int size = strlen(str)+1;
 //посылаем cтроку
 MPI_Send(&str,size,MPI_CHAR,r,1,MPI_COMM_WORLD);
 printf("Отослал строку '%s'\n",str);
 return 1; //возвращаем "ура!"
 }
 }
 return 0; // не нашли ни одного процесса со свободным местом
}
char * pop() //извлекаем строку из стека
{
 int r,message;
 MPI_Status status;
 for(r=nproc-1;r>0;r--)
 {
 message=MSG_CAN_POP;
//запрос на наличие строк в памяти процесса
 MPI_Send(&message,1,MPI_INT,r,0,MPI_COMM_WORLD);
//получаем ответ (размер последней строки) 
21
 MPI_Recv(&message,1,MPI_INT,r,0,MPI_COMM_WORLD,&status);
 if(message) //если строка есть, то...
 {
 char * str = (char *)malloc(message+1);
 MPI_Recv(&str,message,MPI_CHAR,r,2,MPI_COMM_WORLD,&status);
 return str;
 }
 }
 return NULL; //все процессы пусты
}
void killall() //говорим дочерним процессам, что пора и честь знать
{
 int r,message=MSG_KILL;
 for(r=1;r<nproc;r++)
//посылаем сообщение о завершении работы
 MPI_Send(&message,1,MPI_INT,r,0,MPI_COMM_WORLD);
}
void master()
{
 printf("Мастер запущен\n");
 char * str[10];
 str[0] = "Строка 1";
 str[1] = "Строка 2";
 str[2] = "Строка 3";
 str[3] = "Строка 4";
 str[4] = "Строка 5";
 str[5] = "Строка 6";
 str[6] = "Строка 7";
 str[7] = "Строка 8";
 str[8] = "Строка 9";
 str[9] = "Строка 10";
 int i=0;
 for(;i<10;i++)
//занести 10 строк в стек
 if(!push (str[i])) fprintf(stderr,"Не могу послать строку
 %d\n",i+1);
 for(i=0;i<10;i++)
 printf("Получил строку: '%s'\n",pop()); //получаем из стека
 killall();
}
void slave(int rank)
{
 printf("Дочерний процесс %d запущен\n",rank);
 int message;
 int used=0; //сколько сообщений содержится в стеке текущего процесса
 char *buf[SIZE]; //место для стека
 MPI_Status status;
 while(1)
 {
//получаем запрос от сервера
 MPI_Recv(&message,1,MPI_INT,0,0,MPI_COMM_WORLD,&status);
 switch(message)
 { 
22
//процесс-мастер спрашивает, есть ли свободное место в стеке
 case MSG_CAN_PUSH :
 message=SIZE-used; //кол-во свободных ячеек в стеке
 MPI_Send(&message,1,MPI_INT,0,0,MPI_COMM_WORLD);
 if(message) //если место есть, то...
 {
//ждём, пока нам пришлют строчку
 MPI_Probe(0,1,MPI_COMM_WORLD,&status);
 int size;
 MPI_Get_count(&status,MPI_CHAR,&size);
//определяем её размер
 buf[used] = (char *)malloc(size);
 //выделяем память
 
MPI_Recv(buf[used++],size,MPI_CHAR,0,1,MPI_COMM_WORLD,&status);
 //получаем строчку у процесса-мастера
 }
 break;
 case MSG_CAN_POP :
 //процесс-мастер спрашивает размер строки в голове стека
 if(used)
 message=strlen(buf[used-1]);
 //размер строки в голове стека
 else message=0;
 MPI_Send(&message,1,MPI_INT,0,0,MPI_COMM_WORLD);
 if(message) //если место есть, то...
 {
 MPI_Send(buf[used-1],message,MPI_CHAR,0,2,
 MPI_COMM_WORLD);
 free(buf[used-1]);
 used--;
 }
 break;
 case MSG_KILL : return;
 default :
 fprintf(stderr,"Неизвестное сообщение.\n");
 return;
 }
 }
}
int main(int argc, char *argv[])
{
 int rank;
 MPI_Init(&argc,&argv);
 MPI_Comm_size(MPI_COMM_WORLD,&nproc);
 MPI_Comm_rank(MPI_COMM_WORLD,&rank);
 if(rank)
 slave(rank);
 else
 master();
 MPI_Finalize();
system("pause");
 return 0;
}
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2017, 17:34
Ответы с готовыми решениями:

Реализация стека на массиве и динамическом распределении памяти
всем привет, дано такое задание: Используя стек, решить следующую задачу....

Синхронизация доступа к разделяемой памяти
Когда потоки являются дочерними по отношению к процессу тут все просто - объект...

Как сохранить данные контейнера в разделяемой памяти
Ищу быстрый способ обмена данными между процессами. Процессы - одинакового типа...

Есть ли оверхед от использования разделяемой памяти, в сравнении с глобальной?
Если оверхед есть, то по каким причинам? Я понимаю что зависит от реализации....

Реализация стека
Реализация стека (добавить 1 элемент, вытащить 1 элемент в стеке, определить,...

3
AlexVRud
480 / 192 / 72
Регистрация: 04.07.2014
Сообщений: 544
27.11.2017, 16:43 2
Ruslanizlugansk, вам точно нужно это сделать для MPI? Судя по заданию вам надо http://www.intuit.ru/studies/courses/2249/52/lecture/1556?page=2#sect5. Это вытекает из
При запуске программа создает блок разделяемой памяти (если его еще нет) или присоединяется к существующему блоку.
В MPI общей для всех узлов разделяемой памяти нет. Есть для подгрупп процессов в MPI-3 https://software.intel.com/sites/def...n_to_MPI-3.pdf.
Но это не подходит для текста задания. Созданная вами программа тоже не соответствует фразе "или присоединяется к существующему блоку"
Может вы уточните задание?
1
Ruslanizlugansk
0 / 0 / 0
Регистрация: 31.05.2015
Сообщений: 10
28.11.2017, 02:52  [ТС] 3
Я уточню

Добавлено через 9 часов 51 минуту
Да, написано в MPI.

Часть 2. Примеры использования функций MPI

Задание №1. Написать реализацию стека строк в разделяемой памяти. При запуске
программа создает блок разделяемой памяти (если его еще нет) или присоединяется к
существующему блоку. Программа должна обеспечивать основные функции работы со
стеком (добавить и удалить элемент) и возможность запуска себя во многих экземплярах.
Алгоритм
Сначала программа определяет свой ранг – если ранг равен нулю, то программа
запускает процесс-мастер, который записывает 10 строк в стек, распределённый между
дочерними процессами, а затем забирает 10 строк из распределённого стека. Если ранг не
равен нулю, программа запускает дочерний процесс, который ждёт от процесса-мастера
сообщение.
0
AlexVRud
480 / 192 / 72
Регистрация: 04.07.2014
Сообщений: 544
28.11.2017, 16:11 4
Лучший ответ Сообщение было отмечено Ruslanizlugansk как решение

Решение

Ты пишешь на Си или С++? В последнем есть замечательный класс std::string для работы со строками.
Напиши вспомогательные функции для посылки/получения данных, например:

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
enum DefaultTags : int {
  DEFAULT_TAG_STRING_LEN = 100,
  DEFAULT_TAG_STRING_DATA
};
 
 
void send_string(const std::string &str, int destination,
                 MPI_Comm communicator = MPI_COMM_WORLD,
                 int tag_len = DEFAULT_TAG_STRING_LEN,
                 int tag_data = DEFAULT_TAG_STRING_DATA)
{
  MPI_Request requests[2];
  const int size = str.size();
  MPI_Isend(&size, 1, MPI_INT, destination, tag_len, communicator, &requests[0]);
  MPI_Isend(str.data(), size + 1, MPI_CHAR, destination, tag_data, communicator, &requests[1]);
  MPI_Waitall(2, requests, MPI_STATUS_IGNORE);
}
 
 
std::string recv_string(int source, MPI_Comm communicator = MPI_COMM_WORLD,
                        int tag_len = DEFAULT_TAG_STRING_LEN,
                        int tag_data = DEFAULT_TAG_STRING_DATA)
{
  int size = 0;
  MPI_Recv(&size, 1, MPI_INT, source, tag_len, communicator, MPI_STATUS_IGNORE);
  std::string str(size, ' ');
  MPI_Recv(&str[0], size + 1, MPI_CHAR, source, tag_data, communicator, MPI_STATUS_IGNORE);
  return str;
}
Далее, в С++ есть классы std::vector/std::stack/... с которыми проще хранить "множества" данных. Тогда в "дочерних" процессах можно писать:

C++
1
2
3
4
5
6
7
8
9
10
11
12
    std::stack<std::string> m_stack;
 
//... PUSH ...
 
    std::string str = recv_string(0);
    m_stack.push(str);
 
//... POP ...
 
    std::string str = m_stack.top();
    m_stack.pop();
    send_string(str, 0);
Не задумываясь над местом для хранения данных. Замечу, что этот код уже смотрится кратко, за счёт вспомогательных функций и стандартных классов С++.

У тебя сейчас в коде все "дочерние" процессы получают данные для стека. А они должны быть распределены по ним.

Можно изменить логику твоей программы. Главный процесс подсчитывает количество элементов в стеке. При добавлении в стек строки он посылает команду PUSH и строку выбранному по кругу процессу. При извлечении данных, он определяет номер процесса в котором хранится вершина стека, посылает ему команду POP и ждёт от него строку. В конце работы он посылает всем команду EXIT. Дочерние же процессы в цикле ждут команду и выполняют необходимые действия. Тогда данные будут распределяться по всем процессам.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2017, 16:11

Реализация стека
Подскажите, как создать класс, который реализует стек? А также методы...

Реализация стека
Помогите создать структуру данных типа &quot;стек&quot;, элементы которого занимают 10...

Реализация стека
Всем доброго времени суток! Нашел в на просторах интернета исходник реализации...


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

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

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