Синхронизация потоков

@Horrorous · Регистрация: 13.04.2009

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

Доброго времени суток!
Задача состоит в том, чтобы отсортировать слова пользуясь алгоритмом слияния.
Алгоритм реализован правильно, но проблема оказалось в том, что потоки создаются рекурсивно, что усложняет их синхронизацию. Первоначально пробовал синхронизировать мьютексом, но по словам преподавателя тут надо использовать условные переменные. Разобрался и с этой синхронизацией перечитав кучу материала в интернете, однако во всех рассмотрен вариант когда есть поток потребитель и поток производитель. В моем же случае потребитель и производитель это один и тот же поток, поэтому по моему смысл такой синхронизации в моем случае теряется. Но вот что все же вышло из моих попыток...

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <sys/utsname.h>
 
 
typedef struct
{
    char str[20];
} slovo;
 
    slovo list[100];
 
typedef struct
{
    long lb, ub;
    pthread_cond_t cond;
} par;
 
pthread_t thread[3];
pthread_mutex_t mutex;
pthread_cond_t cond[3];
 
 
void merge(long lb, long split, long ub, pthread_cond_t cnd)
{
 
    long pos1=lb;
    long pos2=split+1;
    long pos3=0;    slovo *temp = new slovo[ub-lb+1];
    pthread_mutex_lock(&mutex); //захват мьютекса
    pthread_cond_signal(&cnd); //сигнал
    while (pos1 <= split && pos2 <= ub) {
        if (strcmp(list[pos1].str, list[pos2].str)<0)
            strcpy(temp[pos3++].str, list[pos1++].str);
        else
            strcpy(temp[pos3++].str, list[pos2++].str);
    }
 
    while (pos2 <= ub)
        strcpy(temp[pos3++].str, list[pos2++].str);
    while (pos1 <= split)
        strcpy(temp[pos3++].str, list[pos1++].str);
 
 
    for (pos3 = 0; pos3 < ub-lb+1; pos3++)
        strcpy(list[lb+pos3].str, temp[pos3].str);
    pthread_mutex_unlock(&mutex); // освобождение мьютекса
 
 
}
 
static void *mergeSort(void *_pParam)
{
    par *n = (par*) _pParam;
    int rc2, rc3, cn1, cn2;
    long split;
    par *n1 = (par*)malloc(sizeof(par)), *n2 = (par*)malloc(sizeof(par));
    pthread_mutex_lock(&mutex); //захват мьютекса
    if (n->lb < n->ub)
    {
        split = (n->lb + n->ub)/2;
 
        n1->lb = n->lb;
        n1->ub = split;
        n2->lb = split + 1;
        n2->ub = n->ub;
        cn1 = pthread_cond_init(&cond[0], NULL); //
        cn2 = pthread_cond_init(&cond[1], NULL); //инициализации условных переменных для передачи след потокам
        n1->cond = cond[0];
        n2->cond = cond[1];
        rc2 = pthread_create(&thread[0], NULL, mergeSort, (void*)n1);
        rc3 = pthread_create(&thread[1], NULL, mergeSort, (void*)n2);
        if(pthread_cond_wait(&n->cond, &mutex) == 0)
        merge(n->lb, split, n->ub, n->cond);
    }
    pthread_mutex_unlock(&mutex); //освобождение мьютекса
 
    return 0;
}
 
 
 
 
 
int main (int argc, char **argv)
{
    int cnt = 0;
    int rc1, rm;
    char str[101];
    printf("Vvedite slova: ");
    gets(str);
    char *ptr = strtok(str,"\t ");
    for(cnt=0; ptr!=NULL; cnt++)
    {
        strcpy(list[cnt].str, ptr);
        ptr = strtok(NULL,"\t ");
    }
    par *n1 = (par*)malloc(sizeof(par));
    n1->lb = 0;
    n1->ub = cnt - 1;
    int rc = pthread_cond_init(&cond[2], NULL);
    n1->cond = cond[2];
    rm = pthread_mutex_init(&mutex, NULL);
    rc1 = pthread_create(&thread[2], NULL, mergeSort, (void*)n1);
    pthread_join(thread[2], NULL);
    strcpy(str,"");
    for(int i=0;i<cnt;i++)
    {
        strcat(str,list[i].str);
        strcat(str," ");
    }
    puts("Result: \n"); puts(str);
    int c;
    scanf("%d", &c);
    return 0;
}

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

Буду благодарен любой помощи.

@niXman · 11.05.2010, 00:39

поясните задание.
разобраться в вашем коде, и понять что именно вам требуется - не просто

@Horrorous · 11.05.2010, 01:26 **[ТС]**

Сейчас попробую разъяснить все как можно подробней. После запуска программы с клавиатуры вводится строка слов. Строка разбивается на слова и сохраняется как массив слов. mergeSort - это функция которая запускается как поток, она разбивает массив пополам до мельчайших элементов которые можно сравнить. После разбивки данные посылаются в merge, которая представляет собой функцию сортровки мельчайших элементов. Вот вроде и все. дело в том что mergeSort рекурсивно создает свои потоки. Нужно синхронизировать эти потоки

Добавлено через 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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <sys/utsname.h>
 
 
typedef struct
{
        char str[20];
} slovo;
 
        slovo list[100];
 
typedef struct
{
        long lb, ub;
        pthread_cond_t cond;
} par;
 
pthread_t thread[3];
pthread_mutex_t mutex;
pthread_cond_t cond[3];
 
 
void merge(long lb, long split, long ub, pthread_cond_t cnd) ..собственно фушкция изменения положения элемента в массиве, т. е. сортировка 2-х рассматриваемых элементов
{
 
        long pos1=lb;
        long pos2=split+1;
        long pos3=0;    slovo *temp = new slovo[ub-lb+1];
        pthread_mutex_lock(&mutex); //захват мьютекса
        pthread_cond_signal(&cnd); //сигнал
        while (pos1 <= split && pos2 <= ub) {
                if (strcmp(list[pos1].str, list[pos2].str)<0)
                        strcpy(temp[pos3++].str, list[pos1++].str);
                else
                        strcpy(temp[pos3++].str, list[pos2++].str);
        }
 
        while (pos2 <= ub)
                strcpy(temp[pos3++].str, list[pos2++].str);
        while (pos1 <= split)
                strcpy(temp[pos3++].str, list[pos1++].str);
 
 
        for (pos3 = 0; pos3 < ub-lb+1; pos3++)
                strcpy(list[lb+pos3].str, temp[pos3].str);
        pthread_mutex_unlock(&mutex); // освобождение мьютекса
 
 
}
 
static void *mergeSort(void *_pParam)
{
        par *n = (par*) _pParam;
        int rc2, rc3, cn1, cn2;
        long split;
        par *n1 = (par*)malloc(sizeof(par)), *n2 = (par*)malloc(sizeof(par));
        pthread_mutex_lock(&mutex); //захват мьютекса
        if (n->lb < n->ub)
        {
                split = (n->lb + n->ub)/2;
 
                n1->lb = n->lb;
                n1->ub = split;
                n2->lb = split + 1;
                n2->ub = n->ub;
                cn1 = pthread_cond_init(&cond[0], NULL); //
                cn2 = pthread_cond_init(&cond[1], NULL); //инициализации условных переменных для передачи след потокам
                n1->cond = cond[0];
                n2->cond = cond[1];
                rc2 = pthread_create(&thread[0], NULL, mergeSort, (void*)n1); //В потоке создается еще 2 потока (рекурсивно)
                rc3 = pthread_create(&thread[1], NULL, mergeSort, (void*)n2);//
                if(pthread_cond_wait(&n->cond, &mutex) == 0)
                merge(n->lb, split, n->ub, n->cond);
        }
        pthread_mutex_unlock(&mutex); //освобождение мьютекса
 
        return 0;
}
 
 
 
 
 
int main (int argc, char **argv)
{
        int cnt = 0;
        int rc1, rm;
        char str[101];
        printf("Vvedite slova: ");
        gets(str);
        char *ptr = strtok(str,"\t ");
        for(cnt=0; ptr!=NULL; cnt++)
        {
                strcpy(list[cnt].str, ptr);
                ptr = strtok(NULL,"\t ");
        } //Досюда строка разбивается на слова
        par *n1 = (par*)malloc(sizeof(par));
        n1->lb = 0;
        n1->ub = cnt - 1;
        int rc = pthread_cond_init(&cond[2], NULL);
        n1->cond = cond[2];
        rm = pthread_mutex_init(&mutex, NULL);
        rc1 = pthread_create(&thread[2], NULL, mergeSort, (void*)n1); // запуск первого потока
        pthread_join(thread[2], NULL);
        strcpy(str,"");
        for(int i=0;i<cnt;i++)
        {
                strcat(str,list[i].str);
                strcat(str," ");
        }
        puts("Result: \n"); puts(str);
        int c;
        scanf("%d", &c);
        return 0;
}

Новые блоги и статьи Все статьи Все блоги /
1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	11.05.2010, 00:39
	поясните задание. разобраться в вашем коде, и понять что именно вам требуется - не просто 0

Опции темы