共享内存中的并发合并排序-yiteyi-C++库

给定一个“n”和一个“n”数字，使用 同时发生的 合并排序。（提示：尝试使用shmget、shmat系统调用）。 第1部分：算法（如何？） 递归地创建两个子进程，一个用于左半部分，一个用于右半部分。如果进程数组中的元素数少于5，则执行插入排序。然后，两个子项的父项合并结果并返回给父项，依此类推。但是你如何让它同时发生呢？ 第二部分：逻辑（为什么？） 解决这个问题的重要部分不是算法，而是解释操作系统和内核的概念。为了实现并行排序，我们需要一种方法，使两个进程同时在同一个数组上工作。为了简化操作，Linux通过简单的API端点提供了大量系统调用。其中两个是， shmget（） （用于共享内存分配）和 shmat（） （用于共享内存操作）。我们在分叉的子进程之间创建共享内存空间。每个片段被分成左和右两个子片段，并进行排序，有趣的是它们同时工作！shmget（）请求内核分配共享页面对于这两个过程。 为什么传统的fork（）不起作用？ 答案在于fork（）的实际功能。在文档中，“fork（）通过复制调用进程来创建一个新进程”。子进程和父进程在不同的内存空间中运行。在使用fork（）时，两个内存空间具有相同的内容。其中一个进程执行的内存写入、文件描述符（fd）更改等不会影响另一个进程。因此，我们需要一个共享内存段。

null

CPP

                         // C program to implement concurrent merge sort                       
                         #include <sys/types.h>                       
                         #include <sys/ipc.h>                       
                         #include <sys/shm.h>                       
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
                         #include <unistd.h>                       
           
                         void                                     insertionSort(                                     int                                     arr[],                                     int                                     n);                       
                         void                                     merge(                                     int                                     a[],                                     int                                     l1,                                     int                                     h1,                                     int                                     h2);                       
           
                         void                                     mergeSort(                                     int                                     a[],                                     int                                     l,                                     int                                     h)                       
                         {                       
                                                 int                                     i, len=(h-l+1);                       
           
                                                 // Using insertion sort for small sized array                       
                                                 if                                     (len<=5)                       
                                                 {                       
                                                 insertionSort(a+l, len);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 pid_t lpid,rpid;                       
                                                 lpid = fork();                       
                                                 if                                     (lpid<0)                       
                                                 {                       
                                                 // Lchild proc not created                       
                                                 perror                                     (                                     "Left Child Proc. not created"                                     );                       
                                                 _exit(-1);                       
                                                 }                       
                                                 else                                     if                                     (lpid==0)                       
                                                 {                       
                                                 mergeSort(a,l,l+len/2-1);                       
                                                 _exit(0);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 rpid = fork();                       
                                                 if                                     (rpid<0)                       
                                                 {                       
                                                 // Rchild proc not created                       
                                                 perror                                     (                                     "Right Child Proc. not created"                                     );                       
                                                 _exit(-1);                       
                                                 }                       
                                                 else                                     if                                     (rpid==0)                       
                                                 {                       
                                                 mergeSort(a,l+len/2,h);                       
                                                 _exit(0);                       
                                                 }                       
                                                 }                       
           
                                                 int                                     status;                       
           
                                                 // Wait for child processes to finish                       
                                                 waitpid(lpid, &status, 0);                       
                                                 waitpid(rpid, &status, 0);                       
           
                                                 // Merge the sorted subarrays                       
                                                 merge(a, l, l+len/2-1, h);                       
                         }                       
           
                         /* Function to sort an array using insertion sort*/                       
                         void                                     insertionSort(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     i, key, j;                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 {                       
                                                 key = arr[i];                       
                                                 j = i-1;                       
           
                                                 /* Move elements of arr[0..i-1], that are                       
                                                 greater than key, to one position ahead                       
                                                 of their current position */                       
                                                 while                                     (j >= 0 && arr[j] > key)                       
                                                 {                       
                                                 arr[j+1] = arr[j];                       
                                                 j = j-1;                       
                                                 }                       
                                                 arr[j+1] = key;                       
                                                 }                       
                         }                       
           
                         // Method to merge sorted subarrays                       
                         void                                     merge(                                     int                                     a[],                                     int                                     l1,                                     int                                     h1,                                     int                                     h2)                       
                         {                       
                                                 // We can directly copy  the sorted elements                       
                                                 // in the final array, no need for a temporary                       
                                                 // sorted array.                       
                                                 int                                     count=h2-l1+1;                       
                                                 int                                     sorted[count];                       
                                                 int                                     i=l1, k=h1+1, m=0;                       
                                                 while                                     (i<=h1 && k<=h2)                       
                                                 {                       
                                                 if                                     (a[i]<a[k])                       
                                                 sorted[m++]=a[i++];                       
                                                 else                                     if                                     (a[k]<a[i])                       
                                                 sorted[m++]=a[k++];                       
                                                 else                                     if                                     (a[i]==a[k])                       
                                                 {                       
                                                 sorted[m++]=a[i++];                       
                                                 sorted[m++]=a[k++];                       
                                                 }                       
                                                 }                       
           
                                                 while                                     (i<=h1)                       
                                                 sorted[m++]=a[i++];                       
           
                                                 while                                     (k<=h2)                       
                                                 sorted[m++]=a[k++];                       
           
                                                 int                                     arr_count = l1;                       
                                                 for                                     (i=0; i<count; i++,l1++)                       
                                                 a[l1] = sorted[i];                       
                         }                       
           
                         // To check if array is actually sorted or not                       
                         void                                     isSorted(                                     int                                     arr[],                                     int                                     len)                       
                         {                       
                                                 if                                     (len==1)                       
                                                 {                       
                                                 printf                                     (                                     "Sorting Done Successfully"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 int                                     i;                       
                                                 for                                     (i=1; i<len; i++)                       
                                                 {                       
                                                 if                                     (arr[i]<arr[i-1])                       
                                                 {                       
                                                 printf                                     (                                     "Sorting Not Done"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
                                                 printf                                     (                                     "Sorting Done Successfully"                                     );                       
                                                 return                                     ;                       
                         }                       
           
                         // To fill random values in array for testing                       
                         // purpose                       
                         void                                     fillData(                                     int                                     a[],                                     int                                     len)                       
                         {                       
                                                 // Create random arrays                       
                                                 int                                     i;                       
                                                 for                                     (i=0; i<len; i++)                       
                                                 a[i] =                                     rand                                     ();                       
                                                 return                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     shmid;                       
                                                 key_t key = IPC_PRIVATE;                       
                                                 int                                     *shm_array;                       
           
           
                                                 // Using fixed size array.  We can uncomment                       
                                                 // below lines to take size from user                       
                                                 int                                     length = 128;                       
           
                                                 /* printf("Enter No of elements of Array:");                       
                                                 scanf("%d",&length); */                       
           
                                                 // Calculate segment length                       
                                                 size_t                                     SHM_SIZE =                                     sizeof                                     (                                     int                                     )*length;                       
           
                                                 // Create the segment.                       
                                                 if                                     ((shmid = shmget(key, SHM_SIZE, IPC_CREAT | 0666)) < 0)                       
                                                 {                       
                                                 perror                                     (                                     "shmget"                                     );                       
                                                 _exit(1);                       
                                                 }                       
           
                                                 // Now we attach the segment to our data space.                       
                                                 if                                     ((shm_array = shmat(shmid, NULL, 0)) == (                                     int                                     *) -1)                       
                                                 {                       
                                                 perror                                     (                                     "shmat"                                     );                       
                                                 _exit(1);                       
                                                 }                       
           
                                                 // Create a random array of given length                       
                                                 srand                                     (                                     time                                     (NULL));                       
                                                 fillData(shm_array, length);                       
           
                                                 // Sort the created array                       
                                                 mergeSort(shm_array, 0, length-1);                       
           
                                                 // Check if array is sorted or not                       
                                                 isSorted(shm_array, length);                       
           
                                                 /* Detach from the shared memory now that we are                       
                                                 done using it. */                       
                                                 if                                     (shmdt(shm_array) == -1)                       
                                                 {                       
                                                 perror                                     (                                     "shmdt"                                     );                       
                                                 _exit(1);                       
                                                 }                       
           
                                                 /* Delete the shared memory segment. */                       
                                                 if                                     (shmctl(shmid, IPC_RMID, NULL) == -1)                       
                                                 {                       
                                                 perror                                     (                                     "shmctl"                                     );                       
                                                 _exit(1);                       
                                                 }                       
           
                                                 return                                     0;                       
                         }                       

输出：

Sorting Done Successfully

性能改进？ 尝试对代码计时，并将其性能与传统的顺序代码进行比较。如果您知道顺序排序的性能更好，您会感到惊讶！比如说，当left child访问左数组时，该数组被加载到处理器的缓存中。现在，当访问右数组时（由于并发访问），会出现缓存未命中，因为缓存中填充了左段，然后右段被复制到缓存内存中。这种往返过程会继续进行，并且会将性能降低到比顺序代码性能差的程度。有几种方法可以通过控制代码的工作流程来减少缓存未命中。但它们不能完全避免！本文由 平克什·巴贾提亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章