Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment 2: Multithreaded Sorting
1. Assignment Overview
In this assignment, you need to design and implement a C program that utilizes
multithreading to accomplish the task of integer sorting.
2. Important Note
There is a zero-tolerance policy on academic offenses such as plagiarism or inappropriate
collaboration. By submitting your solution for this assignment, you acknowledge that the
code submitted is your own work. You also agree that your code may be submitted to a
plagiarism detection software (such as MOSS) that may have servers located outside Canada
unless you have notified me otherwise, in writing, before the submission deadline. Any
suspected act of plagiarism will be reported to the Faculty’s Academic Integrity Officer in
accordance with Dalhousie University’s regulations regarding Academic Integrity.
3. Detailed Requirements
1) Overview: In this assignment, you need to design and implement a C program that utilizes
multithreading to accomplish the task of integer sorting. Specifically, a list of integers should
be divided into two sub-lists of integers by your program. The size of the sub-lists should be
the same (note that when the total number of integers is odd, the integer in the middle of the
list should only be included one of the sub-lists). Then two separate threads (which are called
“sorting threads”) are created. Each of them sorts a sub-list using a sorting algorithm of your
choice. Finally, the sorted sub-lists are merged into a single sorted list by a third thread
(which is called “merging thread”).
2
Because global data are shared across all threads, perhaps the easiest way to store the initial
list of integers is to create a global array. Each sorting thread could work on one half of this
array. A second global array (whose size is the same as that of the unsorted integer array)
could also be established. The merging thread could then merge the sorted sub-lists into this
second array. Graphically, the operation flow of your C program could be illustrated using
the following figure:
2) Parameter Passing: As mentioned previously, the parent thread in your C program needs
to create two worker threads (i.e. the sorting threads) to complete the sorting operation.
When the worker threads are created, the parent thread needs to pass two unsorted sub-lists
of integers to the worker threads. If you choose to use a global array to store the initial list of
integers, then the parent only needs to pass the index number of the starting/ending element
of the sub-lists (instead of the sub-lists themselves) to the worker threads. To pass the index
numbers, the easiest approach is to use “struct”. For example, a struct to pass the starting
and ending index number can be found below:
/* structure for passing data to threads */
typedef struct
{
int starting_index;
int ending_index;
} parameters;
Then the parent thread could create worker threads using a strategy similar to the following
approach (assuming that N1 and N2 are the starting and ending index number; tid is the
variable corresponding to thread identification; attr is the variable corresponding to thread
attributes; sorter() is the function for the worker threads):
/* create worker threads */
parameters *data = (parameters *) malloc(sizeof(parameters));
3
data->starting_index= N1;
data->ending_index = N2;
pthread_create(&tid, &attr, sorter, data);
Note that, for the merging thread, the required parameters can be passed in a similar manner.
3) Program Structure: With the background knowledge mentioned above, the overall
structure of your program should look like the following skeleton:
4) Additional Requirements: Your program should also satisfy the following requirements:
a) Sorting Algorithm: You can use any sorting algorithm to sort a sub-list of integers.
However, in order to make marking easy, you need to add a comment at the beginning
of sorter(), which clearly states the name of the sorting algorithm used in your
program. Here is a list of potential sorting algorithms:
https://en.wikipedia.org/wiki/Sorting_algorithm
b) Sorting Result: Your program should sort the initial list of integers in ascending order
(i.e. from the smallest integer to the largest integer).
c) Input and Output Files:
a. Input file: The initial list of integers are provided via a file named
“IntegerList.txt”.
i. In this file, the integers are separated by commas.
ii. There is NO new line character (i.e. \n) at the end of the list.
iii. The integers in the list are positive. The range of the integers is [1, 999].
4
iv. There could be at most 500 integers in the list.
v. Your program should assume that this file is located in the same
directory as your program.
vi. An example “IntegerList.txt” is available via brightspace.
b. Output file: The sorted list of integers should be placed in a newly-created file
named “SortedIntegerList.txt”. This file should located in the same directory as
your program. The integers in this file should be separated by commas.
d) Total Number of Integers: When the total number of integers is even, each of the sublists
includes half of the integers. When the total number of integers is odd, the integer
in the middle of the list should only be included one of the sub-lists.
e) Total Number of Threads: For simplicity, there should be four threads in your
program in total. These threads include the parent thread (i.e. the thread
corresponding to main()), two sorting threads, and one merging thread.
f) Your program must use the GNU C library (i.e. glibc) to implement the required
features. Here are a few links about glibc:
a. https://www.gnu.org/software/libc/documentation.html
b. https://www.kernel.org/doc/man-pages/
c. http://man7.org/linux/man-pages/index.html
g) Compiling and running your program on bluenose.cs.dal.ca should not lead to errors
or warnings.
a. To compile and run your program on bluenose, you need to be able to upload
a file to or download a file from bluenose. Here is a tutorial on bluenose
downloading/uploading: https://web.cs.dal.ca/~society/#/
5) Readme File: You need to complete a readme file named “Readme.txt”, which includes the
instructions that the TA could use to compile and execute your program on bluenose.
6) Submission: Please pay attention to the following submission requirements:
a) You should place “Readme.txt” in the directory where your program files are located.
b) Your program files and “Readme.txt” should be compressed into a zip file named
“YourFirstName-YourLastName-ASN2.zip”. For example, my zip file should be called
“Qiang-Ye-ASN2.zip”.
c) Finally, you need to submit your zip file for this assignment via brightspace.
Note that there is an appendix at the end of this document, which includes the commands
that you can use to compress your files on bluenose.
4. Grading Criteria
The TA will use your submitted zip file to evaluate your assignment. The full grade is 20
points. The details of the grading criteria are presented as follows.
? “Readme.txt” with the correct compilation/execution instructions is provided [1 Point]
? The program retrieves the initial list of integers from “IntegerList.txt”. [1 Point]
? The parent thread creates two sorting threads, each of which sorts half (approximately
half when the total number of integers is odd) of the unsorted integers. There is a
5
comment at the beginning of sorter(), which clearly indicates the name of the sorting
algorithm implemented in your program. [10 Point]
? After the sorting threads terminate, the parent thread creates a merging thread, which
merges the sorted sub-lists into the final sorted list. [6 Points]
? The program creates a new file named “SortedIntegerList.txt”, which includes the sorted
list of integers and is located in the same directory as your program. The integers are
separated using commas. [1 Point]
? Proper programming format/style (e.g. release the memory that is dynamically allocated
when it is not needed any more; proper comments; proper indentation/variable names,
etc.). [1 Point]
Please note that when “Readme.txt” is not provided or “Readme.txt” does not include the
compilation/execution instructions, your submission will be compiled using the standard
command gcc -o A2 A2.c (or your filename), and you will receive a zero grade
if your program cannot be successfully compiled on bluenose.