Question

Do the following project: Following is the file to be programmed in Linux kernel. Run this program. Include the screenshot of the results.

Multi threaded Sorting Application

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 (which we will term 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—which merges the two sub lists into a single sorted list. Because global data are shared across all threads, perhaps the easiest way to set up the data is to create a global array. Each sorting thread will work on one half of this array. A second global array of the same size as the unsorted integer array will also be established. The merging thread will then merge the two sub lists into this second array. Graphically, this program is structured as in Figure 4.27. This programming project will require passing parameters to each of the sorting threads. In particular, it will be necessary to identify the starting index from which each thread is to begin sorting. Refer to the instructions in Project1 for details on passing parameters to a thread. The parent thread will output the sorted array once all sorting threads have exited.

/**
* Project II
*
*/

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10
#define NUMBER_OF_THREADS 3

void *sorter(void *params);   /* thread that performs basic sorting algorithm */
void *merger(void *params);   /* thread that performs merging of results */

int list[SIZE] = {7,12,19,3,18,4,2,6,15,8};

int result[SIZE];

typedef struct
{
   int from_index;
   int to_index;
} parameters;

int main (int argc, const char * argv[])
{
   int i;
  
   pthread_t workers[NUMBER_OF_THREADS];
  
   /* establish the first sorting thread */
   parameters *data = (parameters *) malloc (sizeof(parameters));
   data->from_index = 0;
   data->to_index = (SIZE/2) - 1;
   pthread_create(&workers[0], 0, sorter, data);
  
   /* establish the second sorting thread */
   data = (parameters *) malloc (sizeof(parameters));
   data->from_index = (SIZE/2);
   data->to_index = SIZE - 1;
   pthread_create(&workers[1], 0, sorter, data);
  
   /* now wait for the 2 sorting threads to finish */
   for (i = 0; i < NUMBER_OF_THREADS - 1; i++)
       pthread_join(workers[i], NULL);
  
   /* establish the merge thread */
   data = (parameters *) malloc(sizeof(parameters));
   data->from_index = 0;
   data->to_index = (SIZE/2);
   pthread_create(&workers[2], 0, merger, data);
  
   /* wait for the merge thread to finish */
   pthread_join(workers[2], NULL);

   /* output the sorted array */
   for (i = 0; i < SIZE; i++)
       printf("%d ",result[i]);
   printf("\n");
  
return 0;
}

/**
* Sorting thread.
*
* This thread can essentially use any algorithm for sorting
*/

void *sorter(void *params)
{
   int i;
   parameters* p = (parameters *)params;
  
   int begin = p->from_index;
   int end = p->to_index;
  
   int swapped = 1;
   int j = 0;
   int temp;
  
   while (swapped == 1) {
       swapped = 0;
       j++;
      
       for (i = begin; i <= end - j; i++) {
           if (list[i] > list[i+1]) {
               temp = list[i];
               list[i] = list[i+1];
               list[i+1] = temp;
               swapped = 1;
           }
       }
   }

   pthread_exit(0);
}

/**
* Merge thread
*
* Uses simple merge sort for merging two sublists
*/

void *merger(void *params)
{
   parameters* p = (parameters *)params;
  
   int i,j;
  
   i = p->from_index;
   j = p->to_index;
  
   int position = 0;   /* position being inserted into result list */
  
   while (i < p->to_index && j < SIZE) {
       if (list[i] <= list[j]) {
           result[position++] = list[i];
           i++;
       }
       else {
           result[position++] = list[j];
           j++;
       }
   }
      
   /* copy the remainder */
   if (i < p->to_index) {
       while (i < p->to_index) {
           result[position] = list[i];
           position++;
           i++;
       }
   }
   else {
       while (j < SIZE) {
           result[position] = list[j];
           position++;
           j++;
       }
   }

      
  
   pthread_exit(0);
}

P-26 Chapter 4 Threads & Concurrency • Nine threads to check that each of the 3 x 3 subgrids contains the digits 1 through 9 This would result in a total of eleven separate threads for validating a Sudoku puzzle. However, you are welcome to create even more threads for this project. For example, rather than creating one thread that checks all nine columns, you could create nine separate threads and have each of them check one column. I. Passing Parameters to Each Thread The parent thread will create the worker threads, passing each worker the location that it must check in the Sudoku grid. This step will require passing several parameters to each thread. The easiest approach is to create a data structure using a struct. For example, a structure to pass the row and column where a thread must begin validating would appear as follows: /* structure for passing data to threads */ typedef struct int row; int column; } parameters; Both Pthreads and Windows programs will create worker threads using a strategy similar to that shown below: parameters *data = (parameters *) malloc(sizeof(parameters)); data->row = 1; data->column = 1; /* Now create the thread passing it data as a parameter / The data pointer will be passed to either the pthread_create (Pthreads) function or the CreateThread (Windows) function, which in turn will pass it as a parameter to the function that is to run as a separate thread. II. Returning Results to the Parent Thread Each worker thread is assigned the task of determining the validity of a partie- ular region of the Sudoku puzzle. Once a worker has performed this check, it must pass its results back to the parent. One good way to handle this is to create an array of integer values that is visible to each thread. The index in this array corresponds to the ill worker thread. If a worker sets its corresponding value to 1, it is indicating that its region of the Sudoku puzzle is valid. A value of O indicates otherwise. When all worker threads have completed, the parent thread checks each entry in the result array to determine if the Sudoku puzzle is valid. Project 2–Multithreaded Sorting Application 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 (which we

Answer 1

Code:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10
#define NUMBER_OF_THREADS 3

// Function prototypes
void* sorter(void* params);     /* thread that performs basic sorting algorithm */
void* merger(void* params);     /* thread that performs merging of results */
void displayArray(void);        /* displays the global array */
void printNewLines(int numOfLines);     /* prints a desired number of lines on the screen */

// Declare global variables
int list[SIZE] = {7,12,19,3,18,4,2,6,15,8};
int result[SIZE];

// Define struct parameters
typedef struct parameters
{
        int from_index;
        int to_index;
        int threadCount;
} parameters;

// Main program. Executes the sorting of the list and creation of threads.
int main (int argc, const char* argv[]) 
{
        printf("Unsorted List: ");
        for (int i = 0; i < SIZE; i++) {
                printf("%d ", list[i]);
        }
        printNewLines(2);
    
        pthread_t workers[NUMBER_OF_THREADS];
        
        /* establish the first sorting thread */
        //1. call malloc to allocate a �parameters�
        //2. use �parameters� to specify the first half of the array
    //3. create the first thread
        parameters* p1 = malloc(sizeof(parameters*)); // Allocate memory for parameter set 1
        p1 -> from_index = 0;
        p1 -> to_index = (SIZE - 1) / 2;
        p1 -> threadCount = 1;
        pthread_create(&workers[0], 0, sorter, p1);
        

        /* establish the second sorting thread */
        //1. call malloc to allocate a �parameters�
        //2. use �parameters� to specify the first half of the array
    //3. create the second thread
        parameters* p2 = malloc(sizeof(parameters*)); // Allocate memory for parameter set 2
        p2 -> from_index = p1 -> to_index + 1;
        p2 -> to_index = (SIZE -1);
        p2 -> threadCount = 2;
        pthread_create(&workers[1], 0, sorter, p2);
  
        
        /* now wait for the 2 sorting threads to finish */
        // use ptheread_join; wait for 2 sorting threads to finish 
        pthread_join(workers[0], 0);
        pthread_join(workers[1], 0);


        /* establish the merge thread */
        //reuse �parameters� to hold the beginning index in each half
        //create the third thread: merge 
        p1 -> to_index = p2 -> from_index; // overwrite p1 to index 
        p1 -> threadCount = 3;
        pthread_create(&workers[2], 0, merger, p1);
        pthread_join(workers[2], 0);
        /* wait for the merge thread to finish */
        
        /* output the sorted array */
        displayArray();
        
    return 0;
}

// @description: Sorts the list given a starting and ending index in parameters
// @pre: parameters contains the values of from_index and to_index used for sorting
// @post: list[from_index - to_index] is sorted
// @usage: pthread_create(&workers[i], 0, sorter, p);
void* sorter(void* params)
{
        parameters* p = (parameters*)params;
        int startIndex = p -> from_index;
        int endIndex = p -> to_index;
        int threadCount = p -> threadCount;
        int min_index;
        int temp;

        printf("Sorting Sub-List: %d...\n", threadCount);

        for (int i = startIndex; i < endIndex; i++) {
                min_index = i;
                for (int j = i + 1; j <= endIndex; j++) {
                        if (list[j] < list[min_index]) {
                                min_index = j;
                        }
                }

                temp = list[min_index];
                list[min_index] = list[i];
                list[i] = temp;
        }

        printf("Sorted Sub-List %d: ", threadCount);
        for (int i = startIndex; i <= endIndex; i++) {
                printf("%d ", list[i]);
        }
        printNewLines(1);

        pthread_exit(0);
}

// @description: Merges the sorted sub-lists using parameters
// @pre: parameters contains the start index of list1 in from_index and the start index of list2 in to_index
// @post: result contains the sorted list
// @usage: pthread_create(&workers[i], 0, merger, p);
void* merger(void* params)
{
        printf("Merging the Sub-Lists...\n");
        parameters* p = (parameters*)params;
        int index_list1 = p -> from_index;
        int index_list2 = p -> to_index;
        printf("List 1 begins at index: %d\n", index_list1);
        printf("List 2 begins at index: %d\n", index_list2);
        for (int i = 0; i < SIZE; i++) {
                if (list[index_list1] < list[index_list2]) {
                        result[i] = list[index_list1];
                        printf("%d added to result from List 1!", result[i]);
                        index_list1++;
                        printf("\t new index: %d\n", index_list1);
                }
                else {
                        if (index_list2 <= 9) {
                                result[i] = list[index_list2];
                                printf("%d added to result from List 2!", result[i]);
                                index_list2++;
                                printf("\t new index: %d\n", index_list2);
                        }
                        else {
                                result[i] = list[index_list1];
                                printf("%d added to result from List 1!", result[i]);
                                index_list1++;
                                printf("\t new index: %d\n", index_list1);
                        }
                }
        }
        printNewLines(2);
        
        pthread_exit(0);
}

// @description: Displays the global array result
// @pre: None
// @post: contents of result is printed on the screen
// @usage: displayArray();
void displayArray(void) {
        printf("The sorted array: ");
        for (int i = 0; i < SIZE; i++) {
                printf("%d ", result[i]);
        }
        printNewLines(2);
}

// @description: prints a desired number of new lines
// @pre: numOfLines contains the desired number of new lines to be printed
// @post: prints the desired number of new lines on the screen
// @usage: printNewLines(2);
void printNewLines(int numOfLines) {
        for (int i = 0; i < numOfLines; i++) {
                printf("\n");
        }
}

Output Screesnhots:

Unsorted List: 7 12 19 3 18 4 2 6 15 8 Sorting Sub-List: 2... Sorted sub-List 2: 2 4 6 8 15 Sorting Sub-List: 1... Sorted sub-List 1: 3 7 12 18 19 Merging the sub-Lists... List 1 begins at index: 0 List 2 begins at index: 5 2 added to result from List 2! 3 added to result from List 1! 4 added to result from List 2! 6 added to result from List 2! 7 added to result from List 1! 8 added to result from List 2! 12 added to result from List 1! 15 added to result from List 2! 18 added to result from List 1! 19 added to result from List 1! new index: 6 new index: 1 new index: 7 new index: 8 new index: 2 new index: 9 new index: 3 new index: 10 new index: 4 new index: 5 The sorted array: 2 3 4 6 7 8 12 15 18 19

-------------------------END---------------------

Hope this helps you. Do comment if you have any doubts.

Please give a thumbs up(upvote) if you liked the answer.

Thank You