Сортировка деревом. Процессы

@WildAngel · Регистрация: 19.02.2012

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

Здравствуйте, пытаюсь реализовать сортировку с помощью дерева произвольным числом процессов. Данные считываю из файла в пайп. Далее, процессы вызывают метод, в котором забирают по значению из пайпа и отправляют это значение в метод добавление узла дерева, до тех пор, пока не наткнутся на сигнальный символ. Указатель на корень дерева я размещаю в разделяемой памяти.
Ошибки состоят вот в чем:
1) В дерево добавляются элементы только самым первым процессом. остальные процессы только получают значение.
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
//Структура дерева: 
typedef struct tree
    {
        char* a;
        struct tree *left;
        struct tree *right;
    }TREE;
 
TREE ** root = NULL;
//Метод создания процессов и объявление разделяемой памяти
void sort_tree(int count, int pipe_read)
{   
    int processes[count];
    
        int segment_id;
        if((segment_id = shmget(IPC_PRIVATE, sizeof(TREE), IPC_CREAT|0666)) < 0)
        {
            perror("Segment creation failed\n");
            exit(EXIT_FAILURE);
        }
        printf("Segment created : %d\n", segment_id);
 
    if ((root = (TREE**)shmat(segment_id, 0, 0)) < (TREE**)0)
        {
            perror("Segment attaching failed\n");
            exit(EXIT_FAILURE);
        }
    printf("Segment attaching : %d\n", segment_id);
 
 
    for (int i=0; i<count; i++)
    {
        printf("Creating process %d \n", i);
        if ((processes[i]=fork()) <0)
        {   
            shmdt(root);
                shmctl(segment_id, IPC_RMID, NULL);     
            exit(-1);
        }       
        else if (processes[i]==0)
        {   
            call_process(pipe_read, i, *root);
            exit(0);
        }
    }
 
    int status;
    for (int i=0; i<count; i++)
    {
        waitpid(processes[i], &status, 0);
        printf("Finish process %d\n", i);
    }
    shmdt(root);
    shmctl(segment_id, IPC_RMID, NULL);
}
//Метод, в котором процессы забирают значение из pipe и пытаются его добавить в дерево
void call_process(int pipe_read, int id, TREE* root)
{
    char *value;    
    read (pipe_read, &value, sizeof(value));    
    while (value!="@")
    {
        printf("Read from pipe by process %d %s", id, value);       
        root = AddNode(root, value);
        read (pipe_read, &value, sizeof(value));                    
    }   
    return; 
}
//Метод добавления в дерево
void AddNode(TREE* node, char* value)
{      
    if (node == NULL)
    {
        if(*root==NULL){
            TREE* n = (TREE*)malloc(sizeof(TREE));
            n->a = value;
            n->left = NULL;
            n->right = NULL;
            *root = n;
            printf("Add Root %s", (*root)->a);
            return ;
        }
        else 
        {
            AddNode(*root, value);          
            return ;
        }
    }  
    if (strcmp(node->a , value) < 0)
    {       
        if (node->right == NULL)
        {
            TREE* n = (TREE*)malloc(sizeof(TREE));
            n->a = value;
            n->left = NULL;
            n->right = NULL;
            node->right = n;
            printf("Add Right %s", value);              
            return ;
        }           
        else
        {
            printf("Adding Right %s", value);       
            AddNode(node->right, value);            
            return ;
        }       
    }     
       
    if (node->left == NULL)
    {
        TREE* n = (TREE*)malloc(sizeof(TREE));
        n->a = value;
        n->left = NULL;
        n->right = NULL;
        node->left = n;  
        printf("Add Left %s", value);
        return ;     
    }           
    else
    {   
        printf("Adding left %s", value);    
        AddNode(node->left, value); 
        return ;
    }        
}

g_u_e_s_t · 12.10.2012, 09:29

Сообщение от WildAngel

Указатель на корень дерева я размещаю в разделяемой памяти.

Это и есть ошибка. Этого мало, _все_ процессы должны видеть дерево _полностью_.

@WildAngel · 12.10.2012, 12:19 **[ТС]**

попытка увеличить размер

C++ (Qt)
1
segment_id = shmget(IPC_PRIVATE, sizeof(TREE)* count_elements, IPC_CREAT|0666)

не меняет положения. оибки все равно остаются.
или можно как-то по-другому это сделать?

g_u_e_s_t · 12.10.2012, 12:26

А что на месте malloc() в AddNode()?

@WildAngel · 12.10.2012, 12:30 **[ТС]**

выделяем память для узла дерева

g_u_e_s_t · 12.10.2012, 12:32

Сообщение от WildAngel

выделяем память для узла дерева

не понятно. покажите как Вы это делаете.
На всякий случай еще раз: память полученная через malloc() доступна только тому процессу который ее выделил.

@WildAngel · 12.10.2012, 12:50 **[ТС]**

Вместо malloc сделала создание нового узла с помощью конструктора. Ничего не изменилось(

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
typedef struct tree
    {
        char* a;
        struct tree *left;
        struct tree *right;
        tree(char* value)
        {
            a = value;
            left = NULL;
            right = NULL;
                }
    }TREE;
 
TREE ** root = NULL;
TREE * AddNode(TREE* node, char* value)
{      
    if (node == NULL)
    {
        if(*root==NULL){
            *root = new TREE(value);
            printf("Add Root %s", (*root)->a);
            return *root;
        }
        else 
        {
            AddNode(*root, value);
        }
    }    
       
    if (strcmp(node->a , value) < 0)
    {       
        if (node->right == NULL)
        {
            TREE* n = new TREE(value);
            node->right = n;    
            printf("Add Right %s", value);              
            return node;
        }           
        else
        {
            printf("Adding Right %s", value);       
            AddNode(node->right, value);            
            return node;
        }       
    }    
       
    if (node->left == NULL)
    {
        TREE* n = new TREE(value);
        node->left = n;     
        printf("Add Left %s", value);
        return node;     
    }           
    else
    {   
        printf("Adding left %s", value);    
        AddNode(node->left, value); 
        return node;
    }        
}

g_u_e_s_t · 12.10.2012, 12:54

Вы не понимаете, или плохо говорю... _ВСЕ_ узлы дерева _ДОЛЖНЫ_ лежать в SHM.

@WildAngel · 12.10.2012, 13:16 **[ТС]**

Пытаюсь реализовать Ваш совет, но безуспешно. Правильно ли я отправляю узел в память или нет?

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
TREE * AddNode(TREE* node, char* value, int segment_id)
{      
    if (node == NULL)
    {
        if(*root==NULL){
            *root = new TREE(value);
            if ((root = (TREE**)shmat(segment_id, 0, 0)) < (TREE**)0)
                {
                    perror("Segment attaching failed\n");
                    exit(EXIT_FAILURE);
                }
            printf("Add Root %s", (*root)->a);
            return *root;
        }
        else 
        {
            AddNode(*root, value, segment_id);
        }
    }
    
       
    if (strcmp(node->a , value) < 0)
    {       
        if (node->right == NULL)
        {
            TREE* n = new TREE(value);
            node->right = n;
            if ((node = (TREE*)shmat(segment_id, 0, 0)) < (TREE*)0)
                {
                    perror("Segment attaching failed\n");
                    exit(EXIT_FAILURE);
                }   
            printf("Add Right %s", value, segment_id);              
            return node;
        }           
        else
        {
            printf("Adding Right %s", value);       
            AddNode(node->right, value, segment_id);            
            return node;
        }       
    }     
       
    if (node->left == NULL)
    {
        TREE* n = new TREE(value);
        node->left = n;         
        if ((node = (TREE*)shmat(segment_id, 0, 0)) < (TREE*)0)
            {
                perror("Segment attaching failed\n");
                exit(EXIT_FAILURE);
            }       
        printf("Add Left %s", value);
        return node;     
    }           
    else
    {   
        printf("Adding left %s", value);    
        AddNode(node->left, value, segment_id); 
        return node;
    }   
        
}

g_u_e_s_t · 12.10.2012, 13:27

Увы нет. Если у Вас сложности именно с SHM, то представьте что на его месте простой массив из N узлов дерева, именно узлов, а не указателей на узлы. shmat() в sort_tree() выделил память для этого массива, далее Вы должны брать память для узлов дерева только в этом массиве, никаких new и malloc().
Так же Вам потребуется синхронизация доступа к узлам дерева.

@WildAngel · 12.10.2012, 14:38 **[ТС]**

Спасибо за помощь, буду пытаться реализовать этот совет.

@WildAngel · 13.10.2012, 19:55 **[ТС]**

Всё-таки, ничего не выходит.
1. Каждый процесс теперь строит своё дерево.
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
typedef struct tree
    {
        char* a;
        struct tree *left;
        struct tree *right;
    }TREE;
 
static struct sembuf sop_lock = {0, -1, 0};
 
static struct sembuf sop_unlock = {0, 1, 0};
 
TREE * root;
int segment_id;
 
TREE * AddNode(TREE* node, char* value)
{      
    if (node == NULL)
    {
        node=(TREE*)shmat(segment_id, 0, 0);
        node->left=NULL;
        node->right=NULL;
        node->a=value;
        printf("Add %s", value);
        return node;
    }      
       
    if (strcmp(node->a , value) < 0)
    {   
        printf("Adding Right %s", value);       
        AddNode(node->right, value);            
        return node;        
    }               
    else
    {   
        printf("Adding left %s", value);    
        AddNode(node->left, value); 
        return node;
    }
    return node;            
}
 
void call_process(int pipe_read, int id, int semid)
{
    char *value;    
    read (pipe_read, &value, sizeof(value));    
    while (value!="@")
    {   
        printf("Read from pipe by process %d %s", id, value);
        printf("Lock by process %d \n", id);        
        semop(semid, &sop_lock, 1);
        root = AddNode(root, value);            
        semop(semid, &sop_unlock, 1);
        printf("Unlock by process %d \n", id);
        read (pipe_read, &value, sizeof(value));                        
    }   
    return; 
}
 
 
void sort_tree(char* a[], int count, int pipe_read, int count_elements)
{   
    int processes[count];
    
    int semid = semget(IPC_PRIVATE, 1, 0666|IPC_CREAT);
 
        if(semid==-1)
        {
            perror("Semaphore creation failed\n");
            exit(EXIT_FAILURE);
        }
    union semun
        {
            int val;
            struct semid_ds *buf;
            ushort * array;
        } argument;
        argument.val = 0;
 
        if(semctl(semid, 0, SETVAL, argument) == -1)
        {
            printf("Cannot set semaphore value.\n");
        }
        else
        {   
            printf("Semaphore initialized.\n");
        }
    semop(semid, &sop_unlock, 1);
        
        if((segment_id = shmget(IPC_PRIVATE, sizeof(TREE)*count_elements, IPC_CREAT|0666)) < 0)
        {
            perror("Segment creation failed\n");
            exit(EXIT_FAILURE);
        }
        printf("Segment created : %d\n", segment_id);
    
    if ((root = (TREE*)shmat(segment_id, 0, 0)) < (TREE*)0)
        {
            perror("Segment attaching failed\n");
            exit(EXIT_FAILURE);
        }
    printf("Segment attaching : %d\n", segment_id);
    root = NULL;
    for (int i=0; i<count; i++)
    {
        printf("Creating process %d \n", i);
        if ((processes[i]=fork()) <0)
        {   
            shmdt(root);
                shmctl(segment_id, IPC_RMID, NULL);     
            exit(-1);
        }       
        else if (processes[i]==0)
        {   
            call_process(pipe_read, i,semid);
            exit(0);
        }
    }
 
    int status;
    for (int i=0; i<count; i++)
    {
        waitpid(processes[i], &status, 0);
        printf("Finish process %d\n", i);
    }
    
    shmdt(root);
    shmctl(segment_id, IPC_RMID, NULL);
}

g_u_e_s_t · 13.10.2012, 20:18

Сообщение от WildAngel

1. Каждый процесс теперь строит своё дерево.

Пардон, но Вы сказки рассказываете...

Сообщение от WildAngel

C
1
2
3
4
5
6
7
8
9
if (node == NULL)
* * {
* * * * node=(TREE*)shmat(segment_id, 0, 0);
* * * * node->left=NULL;
* * * * node->right=NULL;
* * * * node->a=value;
* * * * printf("Add %s", value);
* * * * return node;
* * }

Вы все время пишите в одно и то же место...

@WildAngel · 13.10.2012, 21:01 **[ТС]**

Мне не понятно. Опять ошибка с разделяемой памятью или что? алгоритм добавления в дерево верный. Когда на экран вывожу сообщения с помощью printf, то видно: процесс 0 добавляет в корень, потом в ветви. При этом одновременно процесс 1 опять добавляет корень и т.д.

g_u_e_s_t · 13.10.2012, 21:22

Сообщение от WildAngel

Опять ошибка с разделяемой памятью или что?

да. попробуйте вместо printf("Add %s", value); написать printf("Add %s at %p\n", value, (void *)node);
адрес будет всегда один и тот же. Так же проблема с *a - строку так же надо скопировать в shm.

@WildAngel · 13.10.2012, 21:52 **[ТС]**

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

C++
1
2
node->a=(char*)shmat(segment_id, 0, 0);
        node->a=value;

g_u_e_s_t · 13.10.2012, 22:22

просто представьте, что у Вас есть такое: char mem[1024*1024]; т.е. 1мб памяти и в этом куске памяти нужно создать дерево без пайпов, процессов и прочего. Сделайте указатель на этот кусок памяти char *memptr = mem[0]; И двигайте его при добавлении каждого узла дерева: node = (TREE *)memptr;memptr+=sizeof(TREE);
Копировать, да, при добавлении:strcpy(memptr, value);node->a=memptr;memptr+=strlen(value)+1+возмож ное выравнивание;
Как сделаете - возвращайтесь к shm и процессам.

@WildAngel · 13.10.2012, 23:27 **[ТС]**

совсем не понятна вот эта операция: node = (TREE *)memptr; ведь memptr типа char*, можно ли так делать?

g_u_e_s_t · 15.10.2012, 09:03

А почему нет?
если не нравиться, кастуйте через (void *) или объявите mem[] как TREE (кстати проще будет считать выравнивание после записи TREE.a)

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	12.10.2012, 12:26
	А что на месте malloc() в AddNode()? 0

@WildAngel 0 / 0 / 0 Регистрация: 19.02.2012 Сообщений: 16
	12.10.2012, 12:30 [ТС]
	выделяем память для узла дерева 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	12.10.2012, 12:54
	Вы не понимаете, или плохо говорю... _ВСЕ_ узлы дерева _ДОЛЖНЫ_ лежать в SHM. 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	12.10.2012, 13:27
	Увы нет. Если у Вас сложности именно с SHM, то представьте что на его месте простой массив из N узлов дерева, именно узлов, а не указателей на узлы. shmat() в sort_tree() выделил память для этого массива, далее Вы должны брать память для узлов дерева только в этом массиве, никаких new и malloc(). Так же Вам потребуется синхронизация доступа к узлам дерева. 1

@WildAngel 0 / 0 / 0 Регистрация: 19.02.2012 Сообщений: 16
	12.10.2012, 14:38 [ТС]
	Спасибо за помощь, буду пытаться реализовать этот совет. 0

@WildAngel 0 / 0 / 0 Регистрация: 19.02.2012 Сообщений: 16
	13.10.2012, 21:01 [ТС]
	Мне не понятно. Опять ошибка с разделяемой памятью или что? алгоритм добавления в дерево верный. Когда на экран вывожу сообщения с помощью printf, то видно: процесс 0 добавляет в корень, потом в ветви. При этом одновременно процесс 1 опять добавляет корень и т.д. 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	13.10.2012, 22:22
	просто представьте, что у Вас есть такое: char mem[10241024]; т.е. 1мб памяти и в этом куске памяти нужно создать дерево без пайпов, процессов и прочего. Сделайте указатель на этот кусок памяти char memptr = mem[0]; И двигайте его при добавлении каждого узла дерева: node = (TREE *)memptr;memptr+=sizeof(TREE); Копировать, да, при добавлении:strcpy(memptr, value);node->a=memptr;memptr+=strlen(value)+1+возмож ное выравнивание; Как сделаете - возвращайтесь к shm и процессам. 0

@WildAngel 0 / 0 / 0 Регистрация: 19.02.2012 Сообщений: 16
	13.10.2012, 23:27 [ТС]
	совсем не понятна вот эта операция: node = (TREE )memptr; ведь memptr типа char, можно ли так делать? 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	15.10.2012, 09:03
	А почему нет? если не нравиться, кастуйте через (void *) или объявите mem[] как TREE (кстати проще будет считать выравнивание после записи TREE.a) 0