Instruction

Modify your solution from the pa$3-$shared memory assignment to use threads instead of shared memory. You will need to redeclare the array $\text{'}$in$\text{'}$ as a local storage instead of shared memory. An example of a thread call is provided in thread.cc

You will need to compile your code as:

g$++-$o thread thread.cc $-$lpthread

Requirements

Modify thread.cc to spawn eight threads.

The program should assign one$-$eighth $(1/8$th$)$ of the array $\text{'}$in$\text{'}$ content to each thread.

Each thread should be responsible for sorting its assigned portion of the shared memory.

Shared.cc:

$/*$ Essa Imhmed

August $18,2024$

simple implementation of mergesort.

Input: from a method that generates random numbers between $1$ and $100$

Output: the data in sorted order

Notes: Since mergesort actually relies upon external storage to

store the merge of two segments, we use an additional array to

store the merge called "out$[]"$ and then place the results

back into $"$in$[]"$ for subsequent merges.

Alena Fisher

pa$3-$ Shared Memory

$10/30/2024$

$*/$

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

$/*$ value to size the arrays $*/$

#define MAXNUM $10000$

#define NUM$\_$PROCESSES $8//$ Number of child processes for sorting

$/*$ declare the arrays $*/$

int $*$in; $//$ pointer to the shared memory segment

std::vector out$($MAXNUM$)$; $//$ internal array for merging

sid::vector in$($MAXNUM$)$;

struct Thread $\{$

int val$1$;

int val$2$;

$\}$

$/*$ Merge function that merges two sorted halves of the array $*/$

void merge$($int loc$1,$ int loc$2,$ int loc$3,$ int loc$4)\{$

int i $=$ loc$1,$ j $=$ loc$3,$ insert $=$ loc$1$;

while $($i $<=$ loc$2$ && j $<=$ loc$4)\{$

if $($in$[$i$]<=$ in$[$j$])$

out$[$insert$++]=$ in$[$i$++]$;

else

out$[$insert$++]=$ in$[$j$++]$;

$\}$

$//$ Handle any remaining elements

while $($i $<=$ loc$2)$

out$[$insert$++]=$ in$[$i$++]$;

while $($j $<=$ loc$4)$

out$[$insert$++]=$ in$[$j$++]$;

$//$ Copy merged data back to the original array

for $($i $=$ loc$1$; i $<=$ loc$4$; $++$i$)$

in$[$i$]=$ out$[$i$]$;

$\}$

$/*$ Recursive sort function $*/$

void sort$($int loc$1,$ int loc$2)\{$

if $($loc$1>=$ loc$2)$ return; $//$ base case

int mid $=($loc$1+$ loc$2)/2$;

sort$($loc$1,$ mid$)$; $//$ sort the first half

sort$($mid $+1,$ loc$2)$; $//$ sort the second half

merge$($loc$1,$ mid, mid $+1,$ loc$2)$; $//$ merge the sorted halves

$\}$

$/*$ Helper function to print the array $*/$

void printar$($int NUM$)\{$

for $($int i $=0$; i $<=$ NUM; $++$i$)$

std::cout $<<$ in$[$i$]<<""$;

std::cout $<<$ std::endl;

$\}$

$/*$ Function to generate random numbers to fill the array$*/$

void generateRandomNumbers$($int count$)\{$

$//$ Seed for random number

srand$($static$\_$cast$($std::time$($nullptr$)))$;

$//$ Filling the array with random numbers between $0$ and $100$

for$($int i $=0$; i $<$ count; i$++)\{$

in$[$i$]=$ std::rand$()\%100$;

$\}$

$\}$

int main$()\{$

int share$\_$key$\_$in; $//$ ID

pid$\_$t children$[$NUM$\_$PROCESSES$]$; $//$ Array of $8$ elements

struct shmid$\_$ds item;

$/*$ Get shared memory $*/$

if $(($share$\_$key$\_$in $=$ shmget$($IPC$\_$PRIVATE, MAXNUM $*$ sizeof$($int$),$ IPC$\_$CREAT $|0666))<0)\{$

std::cerr $<<$ "Cannot get shared memory" $<<$ std::endl;

return $1$;

$\}$

$/*$ Attach shared memory segment $*/$

if $(($in $=($int $*)$shmat$($share$\_$key$\_$in$,$ nullptr, SHM$\_$RND$))==($void $*)-1)\{$

std::cerr $<<$ "Cannot attach to shared memory" $<<$ std::endl;

return $1$;

$\}$

$//$ Calling the method to generate random numbers

generateRandomNumbers$($MAXNUM$)$;

$//$ Printing the unsorted array

std::cout $<<$ "Unsorted array: $"<<$ std::endl;

printar$($MAXNUM $-1)$;

$//$ Determining the segment size for each process

int segment$\_$size $=$ MAXNUM $/$ NUM$\_$PROCESSES;

$//$ Fork child process

for$($int i $=0$; i $<$ NUM$\_$PROCESSES; i$++)\{$

if$(($children$[$i$]=$ fork$())==0)\{$

$//$ Starting index for the segment

int start $=$ i $*$ segment$\_$size;

$//$ End index for the segment

int end $=$ std::min$($start $+$ segment$\_$size $-1,$ MAXNUM $-1)$;

if$($start $<$ MAXNUM$)\{$

$//$ Sorting the segment

sort$($start$,$ end$)$;

$\}$

exit$(0)$;

$\}$

$\}$

$//$ Parent process waiting for child processes to finish

for$($int i $=0$; i $<$ NUM$\_$PROCESSES; $++$i$)\{$

waitpid$($children$[$i$],$ nullptr, $0)$;

$\}$

$//$ Merging the sorted segments into a single array

for$($int segment$\_$size $=1$; segment$\_$size $<$ MAXNUM; segment$\_$size $*=2)\{$

for$($int i $=0$; i $<$ MAXNUM; i $+=2*$ segment$\_$size$)\{$

int start$1=$ i; $//$ Starting index of the first se