我是一名学生，我需要使用线程和fork（）在C中实现Mergesort程序。没有助手的实施是由学校助理预先准备的。到目前为止，我已经实现了线程并行化，但是该程序比没有线程运行它要慢得多。

我正在使用以下方法从预制文件中读取数字并测量时间：

$ time cat rand_stevila.bin | ./mergeSort 10000

当我使用运行的线程进行订购时：

$ time cat rand_stevila.bin | ./mergeSort 10000 -t

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <pthread.h>
#include <unistd.h>
#include <wait.h>

void printHelp(int argc,char **argv);
void submergeSortSimple(int *array,int min1,int max1,int min2,int max2);
void submergeSortProc(int *array,int max2);
void submergeSortThread(int *array,int max2);
void mergeSort(int *array,int min,int max,void(*submergeSort)(int *,int,int));
void merge(int *arr,int mid,int max);

int max_paralelizacij;
pthread_mutex_t mtx = pthREAD_MUTEX_INITIALIZER;

struct {
    int *array;
    int min;
    int max;
    void (*function)(int *,int);
} typedef thread_args;

void *thread_fun(void *args) {
    thread_args *thr_arg = (thread_args*)args;
    mergeSort((*thr_arg).array,(*thr_arg).min,(*thr_arg).max,(*thr_arg).function);
    return 0;
}

// preprosta implementacija mergeSort rekurzije,// samo klicemo margeSort za levo in desno polovico
// v istem procesu/isti niti
void submergeSortSimple(int *array,int max2) {
    mergeSort(array,min1,max1,submergeSortSimple);
    mergeSort(array,min2,max2,submergeSortSimple);
}

// TODO: funkcija ki paralelizira sortiranje z uporabo procesov
// za preprosto paralelizacijo samo izvedemo vsak klic mergeSort 
// funkcije v svojem procesu,in počakamo,da se klica zaključita
void submergeSortProc(int *array,int max2) {
    printf("implementacija submergeSortProc manjka\n");
    return;
}

// TODO: funkcija,ki paralelizira sortiranje z uporabo niti
// za preprosto paralelizacijo samo izvedemo vsak klic mergeSort 
// funkcije v svoji niti,da se klica zaključita
void submergeSortThread(int *array,int max2) {
    pthread_t tid1,tid2;
    thread_args arg1,arg2;

    arg1.array = array;
    arg1.min = min1;
    arg1.max = max1;
    arg1.function = submergeSortThread;

    arg2.array = array;
    arg2.min = min2;
    arg2.max = max2;
    arg2.function = submergeSortThread;

    pthread_create(&tid1,&thread_fun,&arg1);
    pthread_join(tid1,NULL); 

    pthread_create(&tid2,&arg2);
    pthread_join(tid2,NULL); 
    return;
}

// mergeSort in merge funkciji
// ti dve izvajata dejansko sortiranje

// void mergeSort(int *array,int))
//
// int *array
//   kazalec na tabelo števil,ki jih urejamo
//
// int min,int max
//   indeks prvega in zadnjega števila v tabeli,//   označujeta interval,ki ga sortiramo
//
// void (*submergeSort)(int *array,int max2)
//   kazalec na funkcijo,ki naj kliče mergeSort za dva podintervala 
//   in vrne,ko sta oba intervala sortirana
void mergeSort(int *array,void (*submergeSort)(int *,int)) {
    int mid;

    if (min < max) {
        mid = (min + max) / 2;
        submergeSort(array,min,mid,mid+1,max);
        merge(array,max);
    }
}

// void merge(int *arr,int max)
// 
// int *arr
//   kazalec na tabelo
//
// int min,int max
//   indeksi na del tabele,ki jih je potrebno združiti
//   min je začetni indeks prve podtabele,mid je zadnji indeks
//   prve podtabele in max je zadnji indeks druge podtabele
// 
// metoda zdruzi dve sosednji sortirani podtabeli,// tako da je nova podtabela tudi sortirana
void merge(int *arr,int max) {
    // drugi korak algoritma mergeSort
    int *tmp = malloc((max - min + 1) * sizeof(int));
    int i,j,k,m;
    j = min;
    m = mid + 1;

    for (i = min; j <= mid && m <= max; i++) {
        pthread_mutex_lock(&mtx); 
        if (arr[j] <= arr[m]) {
            tmp[i - min] = arr[j];
            j++;
        } else {
            tmp[i - min] = arr[m];
            m++;
        }
        pthread_mutex_unlock(&mtx); 
    }
    if (j > mid) {
        for (k = m; k <= max; k++) {
            pthread_mutex_lock(&mtx); 
            tmp[i - min] = arr[k];
            pthread_mutex_unlock(&mtx); 
            i++;
        }
    } else {
        for (k = j; k <= mid; k++) {
            pthread_mutex_lock(&mtx); 
            tmp[i - min] = arr[k];
            pthread_mutex_unlock(&mtx);
            i++;
        }
    }
    for (k = min; k <= max; k++) {
        pthread_mutex_lock(&mtx); 
        arr[k] = tmp[k - min];
        pthread_mutex_unlock(&mtx);
    }

    free(tmp);
}

int main(int argc,char *argv[]) {
#define NO_PAR 0 
#define PROC_PAR 1
#define THREAD_PAR 2
    int technique = NO_PAR;
    void (*submergeSortFun)(int *,int);
    submergeSortFun = submergeSortSimple;
    while (1) {
        int c;
        c = getopt(argc,argv,"ptn:");
        //printf("while\n");
        if (c == -1) {
            break;
        }
        switch (c) {
          case 'p':
            technique = PROC_PAR;
            submergeSortFun = submergeSortProc;
            break;
          case 't':
            technique = THREAD_PAR;
            submergeSortFun = submergeSortThread;
            //printf("HALOOOOOO\n");
            break;
          case 'n':
            //printf("Vrednost: %s\n",optarg);
            max_paralelizacij = atoi(optarg);
            //printf("Max par: %d\n",max_paralelizacij); 
            break;
          default:
            //printf("more printat\n");
            printHelp(argc,argv);
            return 0;
        }
    }
    //printf("\nHIER\n");

    int i;
    int size;
    int *arr;
    if (optind >= argc) {
        printHelp(argc,argv);
        return -1;
    }

    size = atoi(argv[optind]);

    // TODO: inicializacija za razlicne tehnike 
    switch (technique) {
      case NO_PAR:
        arr = malloc(sizeof(int) * size);
        break;
      case PROC_PAR:
        // inicializacija za uporabo procesov
        // ustvariti je potrebno deljen pomnilnik,semafor,...
        dprintf(2,"not implemented\n");
        exit(-1);
        break;
      case THREAD_PAR:
        //printf("\ntechnique\n");
        arr = malloc(sizeof(int)*size);

        // inicializacija za uporabo procesov
        // tukaj potrebujete morebitne sinhronizacijske strukture

        //dprintf(2,"not implemented\n");
        //exit(-1);
        break;
    }
    char buffer[101];
    for (i = 0; i < size; i += 1) {
        //printf("ines erbus\n");
        // preberi binarne vrednosti
        read(0,&arr[i],4);
    }

    for (i = 0; i < size; i++) {
        //printf("Serbus ines\n");
        printf("%d ",arr[i]);
    }
    printf("\n\n\n\nKonec Filanja\n\n\n\n");
    //printf("test\n");
    mergeSort(arr,size - 1,submergeSortFun);

    for (i = 0; i < size; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");

    // TODO: ciscenje za razlicnimi tehnikami
    switch (technique) {
      case NO_PAR:
        free(arr);
        break;
      case PROC_PAR:
        dprintf(2,"not implemented\n");
        exit(-1);
        break;
      case THREAD_PAR:
        dprintf(2,"not implemented\n");
        exit(-1);
        break;
    }
    return 0;
}

void printHelp(int argc,char **argv) {
    printf("uporaba\n");
    printf("%s <opcija> <n>\n",argv[0]);
    printf("\tn je število celih števil prebranih z standardnega vhoda\n");
    printf("\tfunkcije prebere n*4 bajtov v tabelo in jih sortira\n");
    printf("opcije:\n");
    printf("-p\n");
    printf("\tparalelizacija s pomočjo procesov\n");
    printf("-t\n");
    printf("\tparalelizacija s pomočjo niti\n");
}