This is some code in C for quicksort. The quicksort works correctly, but I am trying to implement multithreading. I am trying to run the recursive calls in parallel with a limit on how much threads can be running at one time (set by the global variable 'maximumThreads'). My logic is incorrect with managing how many threads can be ran at the same time. The part that I need you to look at is after the for loop in quick sort, where I have my logic for the mutex and the conditional variable. Right now when I run my code, the program runs without stopping. I would like help with correctly implementing this. #include #include #include #include #define SORT_THRESHOLD 40 typedef struct _sortParams { char** array; int left; int right; int* currentThreads; pthread_mutex_t* mutex; pthread_cond_t* cond_var } SortParams; static int maximumThreads; /* maximum # of threads to be used */ /* This is an implementation of insert sort, which although it is */ /* n-squared, is faster at sorting short lists than quick sort, */ /* due to its lack of recursive procedure call overhead. */ static void insertSort(char** array, int left, int right) { int i, j; for (i = left + 1; i <= right; i++) { char* pivot = array[i]; j = i - 1; while (j >= left && (strcmp(array[j],pivot) > 0)) { array[j + 1] = array[j]; j--; } array[j + 1] = pivot; } } /* Recursive quick sort, but with a provision to use */ /* insert sort when the range gets small. */ static void quickSort(void* p) { SortParams* params = (SortParams*) p; char** array = params->array; int left = params->left; int right = params->right; int i = left, j = right; if (j - i > SORT_THRESHOLD) { /* if the sort range is substantial, use quick sort */ int m = (i + j) >> 1; /* pick pivot as median of */ char* temp, *pivot; /* first, last and middle elements */ if (strcmp(array[i],array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } if (strcmp(array[m],array[j]) > 0) { temp = array[m]; array[m] = array[j]; array[j] = temp; if (strcmp(array[i],array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } } pivot = array[m]; for (;;) { while (strcmp(array[i],pivot) < 0) i++; /* move i down to first element greater than or equal to pivot */ while (strcmp(array[j],pivot) > 0) j--; /* move j up to first element less than or equal to pivot */ if (i < j) { char* temp = array[i]; /* if i and j have not passed each other */ array[i++] = array[j]; /* swap their respective elements and */ array[j--] = temp; /* advance both i and j */ } else if (i == j) { i++; j--; } else break; /* if i > j, this partitioning is done */ } pthread_mutex_lock(params->mutex); // Wait if the maximum number of threads is reached while(*params->currentThreads >= maximumThreads) { pthread_cond_wait(params->cond_var, params->mutex); } // Increment the current thread count (*params->currentThreads)++; pthread_mutex_unlock(params->mutex); SortParams first = {params->array, left, j, params->currentThreads, params->mutex, params->cond_var}; SortParams second = {params->array, i, right, params->currentThreads, params->mutex, params->cond_var}; pthread_t thread1, thread2; pthread_create(&thread1, NULL, (void*)quickSort, &first); pthread_create(&thread2, NULL, (void*)quickSort, &second); pthread_join(thread1, NULL); pthread_join(thread2, NULL); // After the threads finish, decrement the current thread count // and signal any waiting threads pthread_mutex_lock(params->mutex); (*params->currentThreads)--; pthread_cond_signal(params->cond_var); pthread_mutex_unlock(params->mutex); } else insertSort(array,i,j); /* for a small range use insert sort */ } /* user interface routine to set the number of threads sortT is permitted to use */ void setSortThreads(int count) { maximumThreads = count; } /* user callable sort procedure, sorts array of count strings, beginning at address array */ void sortThreaded(char** array, unsigned int count) { SortParams parameters; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER; int currentThreads = 0; parameters.array = array; parameters.left = 0; parameters.right = count - 1; parameters.currentThreads = ¤tThreads; parameters.mutex = &mutex; parameters.cond_var = &cond_var; quickSort(¶meters); pthread_cond_destroy(&cond_var); pthread_mutex_destroy(&mutex); }
This is some code in C for quicksort. The quicksort works correctly, but I am trying to implement multithreading. I am trying to run the recursive calls in parallel with a limit on how much threads can be running at one time (set by the global variable 'maximumThreads'). My logic is incorrect with managing how many threads can be ran at the same time. The part that I need you to look at is after the for loop in quick sort, where I have my logic for the mutex and the conditional variable. Right now when I run my code, the program runs without stopping. I would like help with correctly implementing this. #include #include #include #include #define SORT_THRESHOLD 40 typedef struct _sortParams { char** array; int left; int right; int* currentThreads; pthread_mutex_t* mutex; pthread_cond_t* cond_var } SortParams; static int maximumThreads; /* maximum # of threads to be used */ /* This is an implementation of insert sort, which although it is */ /* n-squared, is faster at sorting short lists than quick sort, */ /* due to its lack of recursive procedure call overhead. */ static void insertSort(char** array, int left, int right) { int i, j; for (i = left + 1; i <= right; i++) { char* pivot = array[i]; j = i - 1; while (j >= left && (strcmp(array[j],pivot) > 0)) { array[j + 1] = array[j]; j--; } array[j + 1] = pivot; } } /* Recursive quick sort, but with a provision to use */ /* insert sort when the range gets small. */ static void quickSort(void* p) { SortParams* params = (SortParams*) p; char** array = params->array; int left = params->left; int right = params->right; int i = left, j = right; if (j - i > SORT_THRESHOLD) { /* if the sort range is substantial, use quick sort */ int m = (i + j) >> 1; /* pick pivot as median of */ char* temp, *pivot; /* first, last and middle elements */ if (strcmp(array[i],array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } if (strcmp(array[m],array[j]) > 0) { temp = array[m]; array[m] = array[j]; array[j] = temp; if (strcmp(array[i],array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } } pivot = array[m]; for (;;) { while (strcmp(array[i],pivot) < 0) i++; /* move i down to first element greater than or equal to pivot */ while (strcmp(array[j],pivot) > 0) j--; /* move j up to first element less than or equal to pivot */ if (i < j) { char* temp = array[i]; /* if i and j have not passed each other */ array[i++] = array[j]; /* swap their respective elements and */ array[j--] = temp; /* advance both i and j */ } else if (i == j) { i++; j--; } else break; /* if i > j, this partitioning is done */ } pthread_mutex_lock(params->mutex); // Wait if the maximum number of threads is reached while(*params->currentThreads >= maximumThreads) { pthread_cond_wait(params->cond_var, params->mutex); } // Increment the current thread count (*params->currentThreads)++; pthread_mutex_unlock(params->mutex); SortParams first = {params->array, left, j, params->currentThreads, params->mutex, params->cond_var}; SortParams second = {params->array, i, right, params->currentThreads, params->mutex, params->cond_var}; pthread_t thread1, thread2; pthread_create(&thread1, NULL, (void*)quickSort, &first); pthread_create(&thread2, NULL, (void*)quickSort, &second); pthread_join(thread1, NULL); pthread_join(thread2, NULL); // After the threads finish, decrement the current thread count // and signal any waiting threads pthread_mutex_lock(params->mutex); (*params->currentThreads)--; pthread_cond_signal(params->cond_var); pthread_mutex_unlock(params->mutex); } else insertSort(array,i,j); /* for a small range use insert sort */ } /* user interface routine to set the number of threads sortT is permitted to use */ void setSortThreads(int count) { maximumThreads = count; } /* user callable sort procedure, sorts array of count strings, beginning at address array */ void sortThreaded(char** array, unsigned int count) { SortParams parameters; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER; int currentThreads = 0; parameters.array = array; parameters.left = 0; parameters.right = count - 1; parameters.currentThreads = ¤tThreads; parameters.mutex = &mutex; parameters.cond_var = &cond_var; quickSort(¶meters); pthread_cond_destroy(&cond_var); pthread_mutex_destroy(&mutex); }
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
This is some code in C for quicksort. The quicksort works correctly, but I am trying to implement multithreading. I am trying to run the recursive calls in parallel with a limit on how much threads can be running at one time (set by the global variable 'maximumThreads'). My logic is incorrect with managing how many threads can be ran at the same time. The part that I need you to look at is after the for loop in quick sort, where I have my logic for the mutex and the conditional variable. Right now when I run my code, the program runs without stopping. I would like help with correctly implementing this.
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <stdio.h>
#define SORT_THRESHOLD 40
typedef struct _sortParams {
char** array;
int left;
int right;
int* currentThreads;
pthread_mutex_t* mutex;
pthread_cond_t* cond_var
} SortParams;
static int maximumThreads; /* maximum # of threads to be used */
/* This is an implementation of insert sort, which although it is */
/* n-squared, is faster at sorting short lists than quick sort, */
/* due to its lack of recursive procedure call overhead. */
static void insertSort(char** array, int left, int right) {
int i, j;
for (i = left + 1; i <= right; i++) {
char* pivot = array[i];
j = i - 1;
while (j >= left && (strcmp(array[j],pivot) > 0)) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = pivot;
}
}
/* Recursive quick sort, but with a provision to use */
/* insert sort when the range gets small. */
static void quickSort(void* p) {
SortParams* params = (SortParams*) p;
char** array = params->array;
int left = params->left;
int right = params->right;
int i = left, j = right;
if (j - i > SORT_THRESHOLD) { /* if the sort range is substantial, use quick sort */
int m = (i + j) >> 1; /* pick pivot as median of */
char* temp, *pivot; /* first, last and middle elements */
if (strcmp(array[i],array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
if (strcmp(array[m],array[j]) > 0) {
temp = array[m]; array[m] = array[j]; array[j] = temp;
if (strcmp(array[i],array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
}
pivot = array[m];
for (;;) {
while (strcmp(array[i],pivot) < 0) i++; /* move i down to first element greater than or equal to pivot */
while (strcmp(array[j],pivot) > 0) j--; /* move j up to first element less than or equal to pivot */
if (i < j) {
char* temp = array[i]; /* if i and j have not passed each other */
array[i++] = array[j]; /* swap their respective elements and */
array[j--] = temp; /* advance both i and j */
} else if (i == j) {
i++; j--;
} else break; /* if i > j, this partitioning is done */
}
pthread_mutex_lock(params->mutex);
// Wait if the maximum number of threads is reached
while(*params->currentThreads >= maximumThreads) {
pthread_cond_wait(params->cond_var, params->mutex);
}
// Increment the current thread count
(*params->currentThreads)++;
pthread_mutex_unlock(params->mutex);
SortParams first = {params->array, left, j, params->currentThreads, params->mutex, params->cond_var};
SortParams second = {params->array, i, right, params->currentThreads, params->mutex, params->cond_var};
pthread_t thread1, thread2;
pthread_create(&thread1, NULL, (void*)quickSort, &first);
pthread_create(&thread2, NULL, (void*)quickSort, &second);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
// After the threads finish, decrement the current thread count
// and signal any waiting threads
pthread_mutex_lock(params->mutex);
(*params->currentThreads)--;
pthread_cond_signal(params->cond_var);
pthread_mutex_unlock(params->mutex);
} else insertSort(array,i,j); /* for a small range use insert sort */
}
/* user interface routine to set the number of threads sortT is permitted to use */
void setSortThreads(int count) {
maximumThreads = count;
}
/* user callable sort procedure, sorts array of count strings, beginning at address array */
void sortThreaded(char** array, unsigned int count) {
SortParams parameters;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER;
int currentThreads = 0;
parameters.array = array; parameters.left = 0; parameters.right = count - 1;
parameters.currentThreads = ¤tThreads; parameters.mutex = &mutex;
parameters.cond_var = &cond_var;
quickSort(¶meters);
pthread_cond_destroy(&cond_var);
pthread_mutex_destroy(&mutex);
}
#include <string.h>
#include <pthread.h>
#include <stdio.h>
#define SORT_THRESHOLD 40
typedef struct _sortParams {
char** array;
int left;
int right;
int* currentThreads;
pthread_mutex_t* mutex;
pthread_cond_t* cond_var
} SortParams;
static int maximumThreads; /* maximum # of threads to be used */
/* This is an implementation of insert sort, which although it is */
/* n-squared, is faster at sorting short lists than quick sort, */
/* due to its lack of recursive procedure call overhead. */
static void insertSort(char** array, int left, int right) {
int i, j;
for (i = left + 1; i <= right; i++) {
char* pivot = array[i];
j = i - 1;
while (j >= left && (strcmp(array[j],pivot) > 0)) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = pivot;
}
}
/* Recursive quick sort, but with a provision to use */
/* insert sort when the range gets small. */
static void quickSort(void* p) {
SortParams* params = (SortParams*) p;
char** array = params->array;
int left = params->left;
int right = params->right;
int i = left, j = right;
if (j - i > SORT_THRESHOLD) { /* if the sort range is substantial, use quick sort */
int m = (i + j) >> 1; /* pick pivot as median of */
char* temp, *pivot; /* first, last and middle elements */
if (strcmp(array[i],array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
if (strcmp(array[m],array[j]) > 0) {
temp = array[m]; array[m] = array[j]; array[j] = temp;
if (strcmp(array[i],array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
}
pivot = array[m];
for (;;) {
while (strcmp(array[i],pivot) < 0) i++; /* move i down to first element greater than or equal to pivot */
while (strcmp(array[j],pivot) > 0) j--; /* move j up to first element less than or equal to pivot */
if (i < j) {
char* temp = array[i]; /* if i and j have not passed each other */
array[i++] = array[j]; /* swap their respective elements and */
array[j--] = temp; /* advance both i and j */
} else if (i == j) {
i++; j--;
} else break; /* if i > j, this partitioning is done */
}
pthread_mutex_lock(params->mutex);
// Wait if the maximum number of threads is reached
while(*params->currentThreads >= maximumThreads) {
pthread_cond_wait(params->cond_var, params->mutex);
}
// Increment the current thread count
(*params->currentThreads)++;
pthread_mutex_unlock(params->mutex);
SortParams first = {params->array, left, j, params->currentThreads, params->mutex, params->cond_var};
SortParams second = {params->array, i, right, params->currentThreads, params->mutex, params->cond_var};
pthread_t thread1, thread2;
pthread_create(&thread1, NULL, (void*)quickSort, &first);
pthread_create(&thread2, NULL, (void*)quickSort, &second);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
// After the threads finish, decrement the current thread count
// and signal any waiting threads
pthread_mutex_lock(params->mutex);
(*params->currentThreads)--;
pthread_cond_signal(params->cond_var);
pthread_mutex_unlock(params->mutex);
} else insertSort(array,i,j); /* for a small range use insert sort */
}
/* user interface routine to set the number of threads sortT is permitted to use */
void setSortThreads(int count) {
maximumThreads = count;
}
/* user callable sort procedure, sorts array of count strings, beginning at address array */
void sortThreaded(char** array, unsigned int count) {
SortParams parameters;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER;
int currentThreads = 0;
parameters.array = array; parameters.left = 0; parameters.right = count - 1;
parameters.currentThreads = ¤tThreads; parameters.mutex = &mutex;
parameters.cond_var = &cond_var;
quickSort(¶meters);
pthread_cond_destroy(&cond_var);
pthread_mutex_destroy(&mutex);
}
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question
I don't see the logic in here that limits the number of threads. How can we do that?
Solution
by Bartleby ExpertKnowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education