Merge Sort with Unix Shared Memory

function MergeSort$($a$[],$ lower$\_$bound, upper$\_$bound$)$

$\{$

int middle;

if $($upper$\_$bound $-$ lower$\_$bound $==1)\{$

if $($a$[$lower$\_$bound$]>$ a$[$upper$\_$bound$])\{$

swap a$[$lower$\_$bound$]$ and a$[$upper$\_$bound$]$;

return;

$\}$

$\}$

$/*$ now we have more than $2$ entries $*/$

middle $=($lower$\_$bound $+$ upper$\_$bound$)/2$;

MergeSort$($a$,$ lower$\_$bound, middle$)$; $/*$ recursively sort the left section $*/$

MergeSort$($a$,$ middle$+1,$ upper$\_$bound$)$; $/*$ recursively sort the right section $*/$

Merge$($a$,$ lower$\_$bound, middle, upper$\_$bound$)$;

$/*$ merge the left and right sections $*/$

return;

$\}$

The two calls to Mergesort$()$ recursively split the give array section into two sorted sections.

The job for program merge.cc to do is the following:

$1.$ When merge.cc runs, it receives the left and right indices Left and Right and other information from its command line arguments.

$2.$ Then, it splits the array section a$[$Left$..$Right$]$ into two at the middle element a$[$M$].$ After the split is obtained, two child processes are created, each of which runs merge.cc using execvp$().$ The first child receives Left and M$-1,$ while the second receives M and Right. In this way each child process performs a merge sort on the given array section. The parent then waits until both child processes complete their job.

$3.$ After this, program merge.cc uses the modified binary merge method to merge the two sorted sections as shown below.

a$.$ merge.cc creates a process for each entry in the two array sections, and waits for the completion of all of these child processes.

b$.$ Each child process uses the assigned array entry to search the other array in order to find its final position in the merged array. Note that these child processes should not store the assigned entry back to the given array. Find a place to store this result array.

$4.$ After all child processes complete, the merged $($and sorted$)$ array must be copied back to shared memory, overwriting the original. At this point don't forget to remove those temporary arrays. Then, merge.cc exits.

You may use multiple shared memory segments, and you must use the execvp$()$ system call to solve this problem. You must use the indicated modified binary search to determine the position of x$[$i$]$ in y$[]$ and the position of y$[$j$]$ in x$[].$

The process structure must be as specified.

The input to program main.cc is in a file with the following format:

n $<-----------------------------$ the number of elements of array a$[]$

a$[0]$ a$[1]$ a$[2].....$ a$[$n$-1]<---$ elements of array a$[]$

If you use more than one shared memory segments, you should repeat the output of shared memory segment and indicate the use of each.

Your output should look like the following, where XXXXX is a description of the purpose of the created shared memory.

$***$ MERGE: shared memory key $=1627930027$

$***$ MERGE: shared memory created

$***$ MERGE: shared memory attached and is ready to use for XXXXX purpose.

Other Output

$***$ MERGE: XXXXX shared memory successfully detached

$***$ MERGE: XXXXX shared memory successfully removed

NOTE: The output lines from main.cc always starts with $***$ MAIN: from

column $1($i$.$e$.,$ no leading space$).$

Messages from merge.cc have an indentation of three spaces and started with ###

M$-$PROC$($abcd$)$:$,$ where abcd is the PID of this particular merge sort process. Data

values printed by a merge sort process has the same indentation as that of ### MPROCE$($abcd$)$: and each integer must printed using four positions, right aligned.

Each process created for binary merge has an indentation of six spaces and

must start with $$$ B$-$PROC$($abcd$).$

A temporary array temp$[]$ always start with $0,$ rather than using the same index$/$subscript as that of the input array. All programs must be written in C$++.$ The following approach will be used to compile and test your programs:

make $<--$ make your program.$/$prog$2<$ input$-$file $<--$ test your program

Your Makefile should generate two binary files: prog$2$ and merge, corresponding to source file main.cc and merge.cc$.$ A README.txt file is always required.

A file named README.txt is required to answer the following questions:

$1.$ The logic of your program

$2.$ Explain the allocation and use of each shared memory segment.

$3.$ Are there potential race conditions in your program?

$4.$ Why you should not save the assigned array entry back to the given array in the binary merge phase?

$5.$ Explain how you allocate a temporary array to hold the intermediate result in each execution of Mergesort$().$

$6.$ We assigned a process to each array entry every time when Mergesort$()$ is executed to perform binary merge. Mergesort$()$ waits for all of these processes before terminates itself. As a result, we repeatedly create and terminate n processes log$2($n$)$ times, which is a waste of time and system resource. Suppose you are allowed to use busy waiting. Can you only create n processes at the beginning of the MERGE phase so that they can be used in each binary merge?

filenames:

main.cc

merge.cc

Makefile

README.txt