分类： LINUX
2011-06-19 16:53:37
/*
* 多进程编程——进程间通信——内存映射——快速排序
* 待排序数的个数大于某一值，则创建子进程进行排序，子进程排序完，通过管道把结果返回给父进程。
* 待排序数的个数小于某一值，自己排序
* Lzy 2011-6-17
*/
#include
#include
#include
#include
#include
#define DATA_NUM 100000 //要进行排序的数据为1000个
#define NUM 100 //要处理的数据大于NUM创建子进程进行处理
#define LIMIT 100000 //排序数的范围0~LIMIT
/*
* 一趟快速排序
* 入口参数num->数组首地址 left-right>排序的下标范围
* 出口参数 基准值在数组中位置值
*/
int partion(int num[], int left, int right)
{
int temp;
int fd[2]; //管道描述符
int pid = -1; //进程描述符
int pos = num[left]; //定义基准值
/*
* 待排序的个数是否大于给定的值
* 大于则创建管道，创建子进程
*/
if(right - left > NUM) //处理数据大于设定的数量
{
pipe(fd); //创建匿名管道进行父子进程通信
pid = fork(); //创建子进程
}
/*
* 通过pid区分父子进程，pid大于0
* 读取子进程写入管道的值，利用管道自动同步机制等子进程结束。
* 读取管道数据，父进程返回
*/
if(pid > 0) //父进程从管道读入数据，返回
{
close(fd[1]); //父进程关闭管道写端
read(fd[0], &left, sizeof(left)); //从管道读入数据
return left;
}
/*
* 共用代码
* 创建子进程则只有子进程执行这段代码，父进程等待
* 无需创建子进程则自己执行
*/
while(left < right)
{
/*
* 一趟快速排序
* 取第一个为基准值
* 先从右向左扫描，找取第一个小于基准值的元素，交换位置
* 再从左向右扫描，找取第一个大于基准值的元素，交换位置
*/
while(left < right && num[right] >= pos) //从右向左进行扫描，查找第一个小于基准值的数据元素
{
right--;
}
temp = num[left]; //数据交换
num[left] = num[right];
num[right] = temp;
while(left < right && num[left] <= pos) //从左向右进行扫描，查找第一个大于基准值的数据元素
{
left++;
}
temp = num[left]; //数据交换
num[left] = num[right];
num[right] = temp;
}
/*
* 子进程排序结束，子进程退出
* 利用管道向父进程返回结果
*/
if(pid == 0) //子进程排序完成，返回基准位置，退出进程
{
close(fd[0]); //子进程关闭管道读端
write(fd[1], &left, sizeof(left)); //数据写入管道
exit(0);
}
return left;
}
/*
* 递归调用实现快速排序
* 入口参数num->数组首地址 left-right>排序的下标范围
*/
void qu_sort(int num[], int left, int right)
{
int pos;
if(left < right)
{
pos = partion(num, left, right); //划分左右子树
qu_sort(num, left, pos-1); //递归调用，对左子树进行排序
qu_sort(num, pos+1, right); //递归调用，对右子树进行排序
}
}
/*
* 主程序
*/
int main(void)
{
unsigned int i;
int data; //中间变量
int fd; //定义文件描述符
int *ptr; //用来保存指向映射内存首地址
fd = open("data", O_RDWR | O_CREAT, 0776); //打开文件
if(fd < 0)
{
perror("open");
exit(0);
}
srand((unsigned)time(NULL));
for(i = 0; i < DATA_NUM; i++) //往文件中写入DATA_NUM个数据
{
data = rand() % LIMIT; //产生随机数
write(fd, &data, sizeof(data)); //数据写入文件
}
ptr = mmap(NULL, DATA_NUM*sizeof(int), PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); //内存映射
if((int)ptr == -1)
{
perror("mmap");
exit(0);
}
qu_sort(ptr, 0, DATA_NUM-1); //数据排序
munmap(ptr, DATA_NUM*sizeof(int)); //取消映射
lseek(fd, 0, SEEK_SET); //读写位置指向文件头
for(i = 0; i < 200; i++) //从文件中读出200个数据便于观察
{
read(fd, &data, sizeof(data));
printf("%d ",data);
}
printf("\n");
close(fd);
return 0;
}
