Operating system Using C 3 Write a multithreaded sorting pro

Operating system

Using C++

3. Write a multithreaded sorting program that works as follows: A list of integers is divided into two smaller lists of equal size. Two separate threads (sorting threads) sort each sub list using a sorting algorithm of your choice. The two sub lists are then merged by a third thread (a merging thread).

Solution

#include #include #include #include struct Params { int *start; size_t len; int depth; }; // only used for synchronizing stdout from overlap. pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER; // forward declare our thread proc void *merge_sort_thread(void *pv); // a simple merge algorithm. there are *several* more efficient ways // of doing this, but the purpose of this exercise is to establish // merge-threading, so we stick with simple for now. void merge(int *start, int *mid, int *end) { int *res = malloc((end - start)*sizeof(*res)); int *lhs = start, *rhs = mid, *dst = res; while (lhs != mid && rhs != end) *dst++ = (*lhs <= *rhs) ? *lhs++ : *rhs++; while (lhs != mid) *dst++ = *lhs++; while (rhs != end) *dst++ = *rhs++; // copy results memcpy(start, res, (end - start)*sizeof(*res)); free(res); } // our multi-threaded entry point. void merge_sort_mt(int *start, size_t len, int depth) { if (len < 2) return; if (depth <= 0 || len < 4) { merge_sort_mt(start, len/2, 0); merge_sort_mt(start+len/2, len-len/2, 0); } else { struct Params params = { start, len/2, depth/2 }; pthread_t thrd; pthread_mutex_lock(&mtx); printf(\"Starting subthread...\ \"); pthread_mutex_unlock(&mtx); // create our thread pthread_create(&thrd, NULL, merge_sort_thread, ¶ms); // recurse into our top-end parition merge_sort_mt(start+len/2, len-len/2, depth/2); // join on the launched thread pthread_join(thrd, NULL); pthread_mutex_lock(&mtx); printf(\"Finished subthread.\ \"); pthread_mutex_unlock(&mtx); } // merge the paritions. merge(start, start+len/2, start+len); } // our thread-proc that invokes merge_sort. this just passes the // given parameters off to our merge_sort algorithm void *merge_sort_thread(void *pv) { struct Params *params = pv; merge_sort_mt(params->start, params->len, params->depth); return pv; } // public-facing api void merge_sort(int *start, size_t len) { merge_sort_mt(start, len, 4); // 4 is a nice number, will use 7 threads. } int main() { static const unsigned int N = 2048; int *data = malloc(N * sizeof(*data)); unsigned int i; srand((unsigned)time(0)); for (i=0; i