消费者生产者问题---计算机操作系统课程设计

齐齐哈尔大学 操作系统课程综合实践 题目 多进程同步方法解决生产 者 消费者问题 班级 0 姓名 0 学号 0 指导教师 0 2011 年 12 月 7 日 1 综合实践评分表 班级0姓名0指导教师0 题目 多进程同步方法解决生产者 消费者问题 评分标准 评分的依据 评分标准 分数权 重 AC 得分 选题10 选题符合大纲要求 题目较新颖 工作量 大 选题基本符合大纲 要求 工作量适中 工作态度10 态度端正 能主动认 真完成各个环节的工 作 不迟到早退 出 勤好 能够完成各环节基 本工作 出勤较好 存储结构 算法描述 20 能正确选择存储结构 定义准确 算法流程 图或类 C 语言描述 的算法准确无误 能正确选择存储结 构 算法流程图或 类 C 语言描述的算 法基本准确 独立解决问 题的能力 10 具有独立分析 解决 问题能力 有一定的 创造性 能够独立完 成软件的设计与调试 工作 程序结构清晰 逻辑严谨 功能完善 有一定的分析 解 决问题能力 能够 在老师指导下完成 软件的设计与调试 工作 程序功能较 完善 答辨问题回 答 20 能准确回答老师提出 的问题 能基本准确回答老 师提出的问题 程序运行情 况 10 程序运行正确 界面 清晰 测试数据设计 合理 程序运行正确 界 面较清晰 能给出 合适的测试数据 综合实践报 告 20 格式规范 层次清晰 设计思想明确 解决 问题方法合理 体会 深刻 格式较规范 设计 思想基本明确 解 决问题方法较合理 总分 指导教师 签字 注 介于注 介于 A 和和 C 之间为之间为 B 级 低于级 低于 C 为为 D 级和级和 E 级 按各项指标打分后 级 按各项指标打分后 总分在总分在 90 0 100100 为优 为优 8080 8989 为良 为良 7070 7979 为中 为中 6060 6969 为及格 为及格 6060 分以下分以下 为不及格 为不及格 2 多进程同步方法解决生产者 消费者问题多进程同步方法解决生产者 消费者问题 摘要摘要 本文论述了多进程同步方法解决生产者 消费者问题的过程 该程序使学生对操作 系统的工作机制有了初步的了解 其主要目的是使学生了解和撑握在 Linux 系统平台下的 C 语言编程 用来解决实现生活中遇到的问题 并以 Linux 系统开发平台 以及虚拟机来 实现 关键字关键字 生产者 消费者问题 Linux 系统平台 虚拟机 信号量 线程 thread 3 多进程同步方法解决生产者 消费者问题多进程同步方法解决生产者 消费者问题 一 课程设计所需设备 计算机一台 Red Hat linux9 03 系统一套 二 课程设计预期目的 通过研究 Linux 的进程机制和信号量实现生产者消费者问题的并发控 制 三 课程设计任务 用多进程同步方法解决生产者 消费者问题 设计目的 通过研究 Linux 的进程机制和信号量实现生产者消费者问题 的并发控制 说明 有界缓冲区内设有 20 个存储单元 放入 取出的数据项设定为 1 20 这 20 个整型数 设计要求 1 每个生产者和消费者对有界缓冲区进行操作后 即时显示有界缓冲区 的全部内容 当前指针位置和生产者 消费者线程的标识符 2 生产者和消费者各有两个以上 3 多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码 四 课程设计基本思想 多进程是一种非常简洁的多任务操作方式 在 Linux 系统下 启动一个 新的进程必须分配给它独立的地址空间 建立众多的数据表来维护它的代码 段 堆栈段和数据段 这是一种烦琐的多任务工作方式 生产者 消费者方案是多进程应用程序开发中最常用的构造之一 因此 困难也在于此 因为在一个应用程序中可以多次重复生产者 消费者行为 其代码也可以如此 设计中创建了 Consumer 类 该类通过在一些多进程应 用程序中促进代码重用以及简化代码调试和维护来解决这个问题 多进程应 用程序通常利用生产者 消费者编程方案 其中由生产者进程创建重复性作 4 业 将其传递给作业队列 然后由消费者进程处理作业 多进程是一种使应用程序能同时处理多个操作的编程技术 通常有两种 不同类型的多进程操作使用多个进程 适时事件 当作业必须在特定的时间 或在特定的间隔内调度执行时 后台处理 当后台事件必须与当前执行流并 行处理或执行时 适时事件的示例包括程序提醒 超时事件以及诸如轮询和 刷新之类的重复性操作 后台处理的示例包括等待发送的包或等待处理的已 接收的消息 生产者 消费者方案很适合于后台处理类别的情况 这些情况通常围绕 一个作业 生产者 方和一个作业 消费者 方 当然 关于作业并行执行 还有其它考虑事项 在大多数情况下 对于使用同一资源的作业 应以 FCFS 的方式按顺序处理 这可以通过使用单进程的消费者轻松实现 通过 使用这种方法 使用单个进程来访问单个资源 而不是用多个进程来访问单 个资源 要启用标准消费者 当作业到来时创建一个作业队列来存储所有作 业 生产者进程通过将新对象添加到消费者队列来交付这个要处理的新对象 然后消费者进程从队列取出每个对象 并依次处理 当队列为空时 消费者 进入休眠 当新的对象添加到空队列时 消费者会醒来并处理该对象 五 详细设计 5 1 调试问题分析 为解决生产者 消费者问题 应该设置两个资源信号量 其中一个表示 空缓冲区的数目 用 Full 表示 其初始值为有界缓冲区的大小 BUFFER NUM 另一个表示缓冲区中产品的数目 用 Empty 表示 其初始值为 0 另外 由于有界缓冲区是一个临界资源 必须互斥使用 所以还需要再 设置一个互斥信号量 Mutex 起初值为 1 在生产者 消费者问题中 信号量实现两种功能 首先 它是生产产品 和消费产品的计数器 计数器的初始值是可利用的资源数目 有界缓冲区的 长度 其次 它是确保产品的生产者和消费者之间动作同步的同步器 生产者要生产一个产品时 首先对资源信号量 Full 和互斥信号量 Mutex 进行 P 操作 申请资源 如果可以通过的话 就生产一个产品 并把 产品送入缓冲区 然后对互斥信号量 Mutex 和资源信号量 Empty 进行 V 操作 释放资源 消费者要消费一个产品时 首先对资源信号量 Empty 和互斥信号量 Mutex 进行 P 操作 申请资源 如果可以通过的话 就从缓冲区取出一个产 品并消费掉 然后对互斥信号量 Mutex 和资源信号量 Full 进行 V 操作 释 5 放资源 如果缓冲区中已经没有可用资源 就把申请资源的进程添加到等待队列 的队尾 如果有一个资源被释放 在等待队列中的第一个进程被唤醒并取得 这个资源的使用权 5 2 程序流程图 生产者线程开始 资源信号量 P 操作 互斥信号量 P 操作 生产一个产品 把产品送入缓冲区 互斥信号量 V 操 作 资源信号量 V 操 作 等待队列中有消 费者线程 等待队列中有消 费者线程 线程自我阻塞 添加到等待队列 线程自我阻塞 添加到等待队列 未通过 未通过 通过 通过 唤醒对头的消费者线程 唤醒对头的消费者线程 生产者线程结束 Y Y N N 图一 生产者流程结构 6 消费者线程开始 资源信号量 P 操作 互斥信号量 P 操作 从缓冲区取出一个产品 消费一个产品 互斥信号量 V 操 作 资源信号量 V 操 作 等待队列中有生 产者线程 等待队列中有生 产者线程 线程自我阻塞 添加到等待队列 线程自我阻塞 添加到等待队列 未通过 未通过 通过 通过 唤醒对头的生产者线程 唤醒对头的生产者线程 消费者线程结束 Y Y N N 图二 消费者流程结构 5 3 程序自定义函数 1 void produce struct sem info 这个函数是生产者进行的生产过程 为所有的生产者所共享 结构体指 针用来接收生产者线程创建时传来的生产者的个人信息 2 void consumer struct sem info 这个函数是消费者进行的生产过程 为所有的消费者所共享 结构体指 7 针用来接收消费者线程创建时传来的消费者的个人信息 3 void setproduce void 这个函数是用来设置生产者的个数和他们的名字 4 void setconsumer void 这个函数是用来设置消费者的个数和他们的名字 5 void activepthread int 这个函数是用来创建生产者线程 int 型参数为生产者的个数 6 void activecthread int 这个函数是用来创建生产者线程 int 型参数为生产者的个数 7 int gettime void 这个函数返回来一个整数 作为线程的 sleep 函数的参数 8 void myscanf void 这个函数用来获取设置生产者和消费者的个数时的整数 确保这个数字 在 0 到 MAX BUFFER 之间 5 4 系统函数调用 线程线程 Linux 系统下的多线程遵循 POSIX 线程接口 称为 pthread 编写 Linux 下的多线程程序 需要使用头文件 pthread h 连接时需要使用库 libpthread a Linux 下 pthread 的实现是通过系统调用 clone 来实现 的 clone 是 Linux 所特有的系统调用 它的使用方式类似 fork 函数 pthread create 用来创建一个线程 它的原型为 extern int pthread create P pthread t thread const pthread attr t attr void start routine void void arg 第一个参数为指向线程标识符的指针 第二个参数用来设置线程属性 第三 个参数是线程运行函数的起始地址 最后一个参数是运行函数的参数 第二 个参数我们也设为空指针 这样将生成默认属性的线程 当创建线程成功时 函数返回 0 若不为 0 则说明创建线程失败 常见的错误返回代码为 EAGAIN 和 EINVAL 前者表示系统限制创建新的线程 例如线程数目过多了 后者 表示第二个参数代表的线程属性值非法 创建线程成功后 新创建的线程则 运行参数三和参数四确定的函数 原来的线程则继续运行下一行代码 函数 pthread join 用来等待一个线程的结束 函数原型为 extern int pthread join P pthread t th void thread return 第一个参数为被等待的线程标识符 第二个参数为一个用户定义的指针 它 8 可以用来存储被等待线程的返回值 这个函数是一个线程阻塞的函数 调用 它的函数将一直等待到被等待的线程结束为止 当函数返回时 被等待线程 的资源被收回 一个线程的结束有两种途径 一种是函数结束了 调用它的 线程也就结束了 另一种方式是通过函数 pthread exit 来实现 它的函数 原型为 extern void pthread exit P void retval attribute noreturn 唯一的参数是函数的返回代码 只要 pthread join 中的第二个参数 thread return 不是 NULL 这个值将被传递给 thread return 最后要说明 的是 一个线程不能被多个线程等待 否则第一个接收到信号的线程成功返 回 其余调用 pthread join 的线程则返回错误代码 ESRCH 信号量信号量 信号量本质上是一个非负的整数计数器 它被用来控制对公共资源的访问 当公共资源增加时 调用函数 sem post 增加信号量 只有当信号量值 大于 时 才能使用公共资源 使用后 函数 sem wait 减少信号量 函数 sem trywait 和函数 pthread mutex trylock 起同样的作用 它是函数 sem wait 的非阻塞版本 它们都在头文件 usr include semaphore h 中定义 信号量的数据类型为结构 sem t 它本质上是一个长整型的数 函数 sem init 用来初始化一个信号量 它的原型为 extern int sem init P sem t sem int pshared unsigned int value sem 为指向信号量结构的一个指针 pshared 不为 时此信号量在进程间共 享 否则只能为当前进程的所有线程共享 value 给出了信号量的初始值 函数 sem post sem t sem 用来增加信号量的值 当有线程阻塞在这个 信号量上时 调用这个函数会使其中的一个线程不在阻塞 选择机制同样是 由线程的调度策略决定的 函数 sem wait sem t sem 被用来阻塞当前线程直到信号量 sem 的值大 于 0 解除阻塞后将 sem 的值减一 表明公共资源经使用后减少 函数 sem trywait sem t sem 是函数 sem wait 的非阻塞版本 它直接 将信号量 sem 的值减一 函数 sem destroy sem t sem 用来释放信号量 sem 六 源程序清单 9 6 16 1 源程序 源程序 include include include include typedef HANDLE Semaphore 信号量的Windows原型 define P S WaitForSingleObject S INFINITE 定义 Windows下的P操作 define V S ReleaseSemaphore S 1 NULL 定义 Windows下的V操作 define rate 1000 define CONSUMER NUM 2 消费者个数 define PRODUCER NUM 3 生产者个数 define BUFFER NUM 20 缓冲区个数 charchar thing 8 鸡腿堡 薯条 可乐 三明治 面包 小笼包 火腿 馒头 生产和消费的产品名称 struct Buffer intint product BUFFER NUM 缓冲区 intint start end 两个指针相当于教材中的 in out 指针 g buf Semaphore Empty Full Mutex 分别相当于Empty Full Mutex三个信号量 消费者线程 DWORD WINAPI Consumer LPVOID para i表示第i个消费者 intint i intint para 利用para传入当前消费者的编号 intint ptr 待消费的内容的指针 printf 消费者 1d 需要资源 n i intint j 0 whilewhile j 4 等待产品 P Full 有产品 先锁住缓冲区 P Mutex 记录消费的物品 ptr g buf start 再移动缓冲区指针 g buf start g buf start 1 BUFFER NUM 10 让其他消费者或生产者使用 printf 消费者 01d 我需要buf d s n i ptr thing g buf product ptr 消费完毕 并释放一个缓冲 printf 消费者 01d 我消费完毕 s n i thing g buf product ptr V Mutex V Empty Sleep rate rand 10 110 returnreturn 0 生产者线程 DWORD WINAPI Producer LPVOID para intint i intint para CONSUMER NUM intint ptr intint data 产品 intint j 0 whilewhile j 4 data rand 8 printf 生产者 01d 生产出 s n i thing data 等待存放空间 P Empty 有地方 先锁住缓冲区 P Mutex 记录消费的物品 ptr g buf end 再移动缓冲区指针 g buf end g buf end 1 BUFFER NUM printf 生产者 01d 放到缓冲区 buf d s n i ptr thing data g buf product ptr data 放好了完毕 释放一个产品 让其他消费者或生产者使用 V Mutex V Full Sleep rate 2 rand 10 110 returnreturn 0 11 intint main intint argc charchar argv 线程技术 前面为消费者线程 后面为生产者线程 HANDLE hThread CONSUMER NUM PRODUCER NUM 线 程计数 srand time NULL rand DWORD tid intint i 0 初始化信号量 Mutex CreateSemaphore NULL 1 1 MutexOfConsumerAndProducer Empty CreateSemaphore NULL BUFFER NUM BUFFER NUM BufferSemaphone Full CreateSemaphore NULL 0 BUFFER NUM ProductSemaphone ifif Empty Full Mutex printf Create Semaphone Error n returnreturn 1 intint totalThreads CONSUMER NUM PRODUCER NUM 开启消费者线程 printf 先请消费者上席 n forfor i 0 i CONSUMER NUM i hThread i CreateThread NULL 0 Consumer ifif hThread i WaitForSingleObject hThread i 10 printf 生产者就位 n forfor i totalThreads i hThread i CreateThread NULL 0 Producer ifif hThread i WaitForSingleObject hThread i 10 生产者和消费者的执行 WaitForMultipleObjects totalThreads hThread TRUE INFINITE returnreturn 0 12 6 26 2 编译及运行结果 编译及运行结果 在程序中设置了两个消费者 三个生产者 为便于描述出生产 消费的 过程 我用食物代表被缓冲区消费的资源 在实验结果中我们可以看到几个 生产者生产的食物放在缓冲区中 消费者