Итак, я просмотрел все проблемы, которые я мог бы исправить как в стеке, так и во многих других источниках.Хотя я смог исправить некоторые проблемы и добавить дополнительное тестирование, он все еще не решил мою проблему.Программа настроена с помощью mergesort.c, который вызывает функции, mergesortTest.c, который проверяет мои функции.Серийная реализация работает просто отлично.Я преодолел проблему с моими первоначальными созданиями.Однако теперь, когда я пытаюсь присоединиться к ним, я получаю ошибку сегмента.Я использовал и valgrind, и gdb, чтобы проверить его и его в моем соединении.Хотя я не могу распечатать сообщение об ошибке, так как это вызывает ошибку сегмента и закрывает мою программу.Я сделал все возможное, чтобы выделить место.Как бы плохо я ни публиковал мой код и вывод gdb в надежде, что кто-то может помочь мне с этим.
**mergesort.c**
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX 100000000
#define MAX_CORE 4
// function prototypes
void serial_mergesort(int A[], int p, int r);
void merge(int A[], int p, int q, int r);
void insertion_sort(int A[], int p, int r);
void *pthread_mergesort(void *arg);
struct mergeS
{
int numElements;
int *A;
int level;
int Max_Level;
};
const int INSERTION_SORT_THRESHOLD = 100; //based on trial and error
/*
* insertion_sort(int A[], int p, int r):
*
* description: Sort the section of the array A[p..r].
*/
void insertion_sort(int A[], int p, int r)
{
int j;
for (j=p+1; j<=r; j++) {
int key = A[j];
int i = j-1;
while ((i > p-1) && (A[i] > key)) {
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
}
/*
* serial_mergesort(int A[], int p, int r):
*
* description: Sort the section of the array A[p..r].
*/
void serial_mergesort(int A[], int p, int r)
{
if (r-p+1 <= INSERTION_SORT_THRESHOLD) {
insertion_sort(A,p,r);
} else {
int q = (p+r)/2;
serial_mergesort(A, p, q);
serial_mergesort(A, q+1, r);
merge(A, p, q, r);
}
}
/*
* pthread_mergesort(void *arg)
*
* description:Sorts based off levels
*
*/
void *pthread_mergesort(void *arg)
{
struct mergeS *threader = (struct mergeS*) arg;
int i = 0;
int flag = 0;
int level = (threader)->level;
printf("level: %d\n",level);
int numElements = threader->numElements;
int Max_Level = threader->Max_Level;
int *A = threader->A;
if(Max_Level == 1)
{
serial_mergesort(A,1,numElements + 1);
return NULL;
}
int low = level * (numElements/Max_Level) + 1;
int high =((level + 1) * ((numElements/Max_Level)));
pthread_t *tids = (pthread_t*) malloc(sizeof(pthread_t) * 2);
struct mergeS *merger = (struct mergeS*) malloc(sizeof(struct mergeS) * 2);
int error = 0;
if(level < Max_Level - 1)
{
for(i = 0;i < 2; i ++)
{
printf("for loop\n");
merger[i].numElements = numElements/(i + 1);
merger[i].level = threader->level + 1;
merger[i].Max_Level = threader->Max_Level;
merger[i].A = threader->A;
if((error = pthread_create(&tids[i],NULL,pthread_mergesort,(void*)&merger[i])) == 0)
{
printf("thread failed\n");
flag = 1;
}
}
printf("error: %d\n",error);
}
serial_mergesort(A,low,high);
int j = 0;
if(flag == 0)
{
for(j = 0;j < 2; j++)
{
printf("for level: %d\n",threader->level);
printf("join = %d\n", j);
if((error = pthread_join(tids[j],NULL)) != 0)
{
printf("error: %d\n",error);
}
}
}
merge(A,low,(high/2) + 1,high);
free(merger);
free (tids);
return NULL;
}
/*
* merge(int A[], int p, int q, int r):
*
* description: Merge two sorted sequences A[p..q] and A[q+1..r]
* and place merged output back in array A. Uses extra
* space proportional to A[p..r].
*/
void merge(int A[], int p, int q, int r)
{
int *B = (int *) malloc(sizeof(int) * (r-p+1));
int i = p;
int j = q+1;
int k = 0;
int l;
// as long as both lists have unexamined elements
// this loop keeps executing.
while ((i <= q) && (j <= r)) {
if (A[i] < A[j]) {
B[k] = A[i];
i++;
} else {
B[k] = A[j];
j++;
}
k++;
}
// now only at most one list has unprocessed elements.
if (i <= q) {
// copy remaining elements from the first list
for (l=i; l<=q; l++) {
B[k] = A[l];
k++;
}
} else {
// copy remaining elements from the second list
for (l=j; l<=r; l++) {
B[k] = A[l];
k++;
}
}
// copy merged output from array B back to array A
k=0;
for (l=p; l<=r; l++) {
A[l] = B[k];
k++;
}
free(B);
}
конец файла
**mergesortTest.c**
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_THREAD 4
#define TRUE 1
#define FALSE 0
// function prototypes
int check_if_sorted(int A[], int n);
void generate_random_array(int A[], int n, int seed);
void serial_mergesort(int A[], int p, int r);
void *pthread_mergesort(void *arg);
void merge(int A[], int p, int q, int r);
void insertion_sort(int A[], int p, int r);
double getMilliSeconds();
// Struct
struct mergeS
{
int numElements;
int *A;
int level;
int Max_Level;
};
/*
* generate_random_array(int A[], int n, int seed):
*
* description: Generate random integers in the range [0,RANGE]
* and store in A[1..n]
*/
#define RANGE 1000000
void generate_random_array(int A[], int n, int seed)
{
int i;
srandom(seed);
for (i=1; i<=n; i++){
A[i] = random()%RANGE;
}
}
/*
* check_if_sorted(int A[], int n):
*
* description: returns TRUE if A[1..n] are sorted in nondecreasing order
* otherwise returns FALSE
*/
int check_if_sorted(int A[], int n)
{
int i=0;
for (i=1; i<n; i++) {
if (A[i] > A[i+1]) {
printf("%d > %d\n",A[i],A[i+1]);
printf("i: %d\n",i);
return FALSE;
}
}
return TRUE;
}
int main(int argc, char **argv) {
printf("argc = %d\n",argc);
int n;
int Max_Level = 4;
int flag = 1;
int seed;
if (argc == 1) { // there must be at least one command-line argument
printf("Default: Input Size = 100000000 levels: 4\n");
printf("Usage: executable input size number of levels\n");
n = 100000000;
seed = 4;
flag = 0;
}
if (argc == 2 && flag == 1) {
printf("Default: Threads: 4\n");
printf("Usage: executable input size number of levels\n");
n = atoi(argv[1]);
Max_Level = 4;
seed = 4;
}
if(argc == 3)
{
n = atoi(argv[1]);
Max_Level = atoi(argv[2]);
seed = Max_Level;
}
if(Max_Level > 15)
{
printf("To many levels. Setting to 4\n");
Max_Level = 4;
seed = Max_Level;
}
int *A = (int *) malloc(sizeof(int) * (n+1)); // n+1 since we are using A[1]..A[n]
// generate random input
generate_random_array(A,n,seed);
double start_time;
double sorting_time;
// sort the input (and time it)
start_time = getMilliSeconds();
serial_mergesort(A,1,n);
sorting_time = getMilliSeconds() - start_time;
////////////////////////////////////////////////////////////////////////////////////////////////////// Start of parallel //////////////////////////////////////////////////////////////////////////////////////////////////////
int *B = (int *) malloc(sizeof(int) * (n+1)); // n+1 since we are using A[1]..A[n]
//int i;
double p_start_time;
double p_sorting_time;
struct mergeS *threader = (struct mergeS*) malloc(sizeof(struct mergeS));
generate_random_array(B,n,seed);
// sort the input with threads (and time it)
p_start_time = getMilliSeconds();
threader[0].numElements = n;
threader[0].level = 0;
threader[0].Max_Level = Max_Level;
threader[0].A = B;
pthread_mergesort(threader);
printf("sorted\n");
/*for(i = 0;i < n + 1;i = i + 1)
{
printf("B[%d]: %d\n",i,B[i]);
}
printf("B:[%d] = %d\n",999,B[999]);
*/
p_sorting_time = getMilliSeconds() - p_start_time;
// print results if correctly sorted otherwise cry foul and exit
if (check_if_sorted(A,n)) {
printf("Serial: Sorting %d elements took %4.2lf seconds.\n", n, sorting_time/1000.0);
} else {
printf("%s: sorting failed!!!!\n", argv[0]);
exit(EXIT_FAILURE);
}
if (check_if_sorted(B,n)) {
printf("Threaded: Sorting %d elements took %4.2lf seconds.\n", n, p_sorting_time/1000.0);
} else {
printf("%s: parallel sorting failed!!!!\n", argv[0]);
exit(EXIT_FAILURE);
}
free(threader);
free(A);
free(B);
exit(EXIT_SUCCESS);
}
конец файла
**GBD error report and code output**
[rutgerluther@onyxnode72 multi-threaded]$ valgrind --leak-check=yes ./mergesort 1000 2
==5636== Memcheck, a memory error detector
==5636== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5636== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5636== Command: ./mergesort 1000 2
==5636==
argc = 3
level: 0
for loop
thread failed
for loop
thread failed
error: 0
sorted
Serial: Sorting 1000 elements took 0.00 seconds.
993090 > 163007
i: 500
./mergesort: parallel sorting failed!!!!
==5636==
==5636== HEAP SUMMARY:
==5636== in use at exit: 9,152 bytes in 5 blocks
==5636== total heap usage: 30 allocs, 25 frees, 33,216 bytes allocated
==5636==
==5636== 1,120 bytes in 2 blocks are possibly lost in loss record 2 of 4
==5636== at 0x4C2B9B5: calloc (vg_replace_malloc.c:711)
==5636== by 0x40128C4: _dl_allocate_tls (in /usr/lib64/ld-2.17.so)
==5636== by 0x4E3E7FB: pthread_create@@GLIBC_2.2.5 (in /usr/lib64/libpthread-2.17.so)
==5636== by 0x400E88: pthread_mergesort (mergesort.c:114)
==5636== by 0x400B00: main (mergesortTest.c:145)
==5636==
==5636== LEAK SUMMARY:
==5636== definitely lost: 0 bytes in 0 blocks
==5636== indirectly lost: 0 bytes in 0 blocks
==5636== possibly lost: 1,120 bytes in 2 blocks
==5636== still reachable: 8,032 bytes in 3 blocks
==5636== suppressed: 0 bytes in 0 blocks
==5636== Reachable blocks (those to which a pointer was found) are not shown.
==5636== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5636==
==5636== For counts of detected and suppressed errors, rerun with: -v
==5636== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
[rutgerluther@onyxnode72 multi-threaded]$ gdb ./mergesort
GNU gdb (GDB) Red Hat Enterprise Linux 7.6.1-110.el7
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/RutgerLuther/RutgerLuther@u.boisestate.edu/backpack/CS453-1-f18/p2/multi-threaded/mergesort...done.
(gdb) b 130
Breakpoint 1 at 0x400abd: file mergesortTest.c, line 130.
(gdb) r 1000 2
Starting program: /home/RutgerLuther/RutgerLuther@u.boisestate.edu/backpack/CS453-1-f18/p2/multi-threaded/./mergesort 1000 2
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
argc = 3
Breakpoint 1, main (argc=<optimized out>, argv=0x7fffffffcf98) at mergesortTest.c:135
135 struct mergeS *threader = (struct mergeS*) malloc(sizeof(struct mergeS));
Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64
(gdb) n
137 generate_random_array(B,n,seed);
(gdb)
140 p_start_time = getMilliSeconds();
(gdb)
141 threader[0].numElements = n;
(gdb)
142 threader[0].level = 0;
(gdb)
143 threader[0].Max_Level = Max_Level;
(gdb)
144 threader[0].A = B;
(gdb)
145 pthread_mergesort(threader);
(gdb)
level: 0
for loop
[New Thread 0x7ffff77f1700 (LWP 5892)]
thread failed
for loop
level: 1
for level: 1
join = 0
[New Thread 0x7ffff6ff0700 (LWP 5893)]
Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffff77f1700 (LWP 5892)]
0x00007ffff7bc7f01 in pthread_join () from /lib64/libpthread.so.0
(gdb)
конец файла
**Valgrind report**
[rutgerluther@onyxnode72 multi-threaded]$ valgrind --leak-check=yes ./mergesort 1000 2
==5636== Memcheck, a memory error detector
==5636== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5636== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5636== Command: ./mergesort 1000 2
==5636==
argc = 3
level: 0
for loop
thread failed
for loop
thread failed
error: 0
sorted
Serial: Sorting 1000 elements took 0.00 seconds.
993090 > 163007
i: 500
./mergesort: parallel sorting failed!!!!
==5636==
==5636== HEAP SUMMARY:
==5636== in use at exit: 9,152 bytes in 5 blocks
==5636== total heap usage: 30 allocs, 25 frees, 33,216 bytes allocated
==5636==
==5636== 1,120 bytes in 2 blocks are possibly lost in loss record 2 of 4
==5636== at 0x4C2B9B5: calloc (vg_replace_malloc.c:711)
==5636== by 0x40128C4: _dl_allocate_tls (in /usr/lib64/ld-2.17.so)
==5636== by 0x4E3E7FB: pthread_create@@GLIBC_2.2.5 (in /usr/lib64/libpthread-2.17.so)
==5636== by 0x400E88: pthread_mergesort (mergesort.c:114)
==5636== by 0x400B00: main (mergesortTest.c:145)
==5636==
==5636== LEAK SUMMARY:
==5636== definitely lost: 0 bytes in 0 blocks
==5636== indirectly lost: 0 bytes in 0 blocks
==5636== possibly lost: 1,120 bytes in 2 blocks
==5636== still reachable: 8,032 bytes in 3 blocks
==5636== suppressed: 0 bytes in 0 blocks
==5636== Reachable blocks (those to which a pointer was found) are not shown.
==5636== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5636==
==5636== For counts of detected and suppressed errors, rerun with: -v
==5636== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
[rutgerluther@onyxnode72 multi-threaded]$
конец файла
Я запускаю это, давая ему только 1000 элементов и используя только 2 потока.Хотя проблема все еще происходит с любыми потоками больше, чем 1. Я прочитал страницы руководства и посмотрел на другие примеры и предыдущие случаи, когда я использовал это и делали одноклассники.Но я все еще не могу понять это.
Любая помощь приветствуется.
Если что-то изменилось и pthread создается правильно.Это вступает в функцию.Я не знаю, каким должно быть значение tids [0].Но элементы в массиве являются случайными числами.
**mergesort.c function call on tids**
level: 1
116 if((error = pthread_create(&tids[i],NULL,pthread_mergesort,(void*)&merger[i])) != 0)
(gdb) info tids
Undefined info command: "tids". Try "help info".
(gdb) print tids[0]
$2 = 140737345689344
(gdb) print &tids
Address requested for identifier "tids" which is in register $r14
(gdb) print *tids
$3 = 140737345689344
(gdb) n
thread failed
for level: 1
join = 0
117 {
(gdb) print tids
$4 = (pthread_t *) 0x604f90
(gdb) print tids[0]
$5 = 140737345689344
(gdb)