高级进程间通信问题——快速排序问题1
需积分: 0 185 浏览量
2022-08-03
11:18:26
上传
评论
收藏 581KB PDF 举报
操作系统课程试验
高级进程间通信问题——快速排序问题
BobAnkh
June 2021
编程平台: Ubuntu 18.04.5 LTS (GNU/Linux 4.15.0‐142‐generic x86_64)
编程语言
: C/C++,
采用了部分
C++11
特性
一. 实验题目
1. 问题描述
对于有 1,000,000 个乱序数据的数据文件执行快速排序。
2. 实验步骤
(1) 首先产生包含 1,000,000 个随机数（数据类型可选整型或者浮点型）的数据文件；
(2) 每次数据分割后产生两个新的进程（或线程）处理分割后的数据，每个进程（线程）处理的
数据小于 1000 以后不再分割（控制产生的进程在 20 个左右）；
(3) 线程（或进程）之间的通信可以选择下述机制之一进行：
• 管道（无名管道或命名管道）
• 消息队列
• 共享内存
(4) 通过适当的函数调用创建上述 IPC 对象，通过调用适当的函数调用实现数据的读出与写入；
(5) 需要考虑线程（或进程）间的同步；
(6) 线程（或进程）运行结束，通过适当的系统调用结束线程（或进程）。
二. 设计思路
为了方便传递快速排序的左右界，定义了一个结构体 Qparam 来存放这两个界，它也是指
示每一个子排序任务（即每一个子排序任务只需要知道左右界即可进行）。定义了一个任务队列
queue<Qparam> job_queue 用于存放目前需要线程来进行执行的任务，通过信号量 jobs
来标识队列中有多少个任务待处理；主进程中在完成相关的初始化之后，会创建第一个工作线程
并将总任务加入到任务队列中，从而开始整个排序任务。每次排序或分划之后，会累加已经排好
序的数量，当这个数量与总数相等时，认为排序完成。
1
评论0