操作系统课程设计——用多线程同步方法解决生产者.doc

操作系统课程设计——用多线程同步方法解决生产者

———————————————————————————————— 作者：
———————————————————————————————— 日期：

17

个人收集整理 勿做商业用途
用多线程同步方法解决生产者－消费者问题
—Producer-Consumer Problem
0 引言
随着多处理机体系结构的演变和分布式与并行系统的发展，并发多任务的程序设计技术已愈来愈显得重要，多线程设计模式在这些技术的发展中起着重要作用。在现代操作系统中，利用进（线）程间的并发性实现程序中并发成分的并行执行，可大大提高系统的处理能力和效率,但也可能带来诸如执行结果的不确定性等不良现象,因此并发系统中处理好进（线)程间的互斥与同步就显得至关重要。Java语言中的多线程机制是解决线程间的互斥与同步问题的重要工具，其应用(如网络多媒体应用、工业自动化控制等）很广泛,很复杂且常易出错。因此在应用程序设计过程中,要考虑多个线程如何同步使用进程的共享资源，如何让一个线程与另一个线程协调合作，以免产生线程间的访问冲突。正确运用Jav。语言提供的多线程机制能有避免同一共享互斥资源被多个线程同时访问，维护数据的一致性、安全性。生产者/消费者问题可作为并发进程的同步和互斥问题的一个抽象模型，广泛应用于通信和控制系统中.本文基于Java语言中的多线程机制，实现操作系统中生产者/消费者问题,以助人们更好地透解同步概念及其实现方法。
1 课程设计目的
通过模拟操作者生产者经典问题的实现，深入理解操作系统中多线程同步法的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法，更好地掌握操作系统的原理及实现方法，提高综合运用各专业课知识的能力。
2 课程设计题目和要求
2。1 课程设计题目
题目: 用多线程同步方法解决生产者－消费者问题 (Producer-Consumer Problem）
2.2课程设计目的与要求
初始条件：
1． 操作系统：Linux
2． 程序设计语言：C语言
3． 有界缓冲区内设有20个存储单元,其初值为0。放入／取出的数据项按增序设定为1－20这20个整型数。
技术要求：
1）为每个生产者／消费者产生一个线程，设计正确的同步算法
2)每个生产者和消费者对有界缓冲区进行操作后，即时显示有界缓冲区的当前全部内容、当前指针位置和生产者／消费者线程的自定义标识符。
3）生产者和消费者各有两个以上。
4）多个生产者或多个消费者之间须共享对缓冲区进行操作的函数代码。
2设计总体思想
2。1 多线程编程思想
Linux系统下的多线程遵循POSIX［2]线程接口，称为pthread.编写Linux下的多线程程序，需要使用头文件pthread。h，连接时需要使用库libpthread.a。在LINUX下进行多线程编程首先要用到pthread_create和pthread_join这两个函数,并声明了一个pthread_t型的变量.pthread_t在头文件/usr/include/bits/pthreadtypes.h中定义:
　 typedef unsigned long int pthread_t;
它是一个线程的标识符.函数pthread_create用来创建一个线程，它的原型为：
　　 extern int pthread_create __P （（pthread_t *__thread， __const pthread_attr_t ＊__attr， void ＊（*__start_routine) （void *), void *__arg)）;
第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。这里,我们的函数thread不需要参数，所以最后一个参数设为空指针。第二个参数我们也设为空指针,这样将生成默认属性的线程.对线程属性的设定和修改我们将在下一节阐述.当创建线程成功时，函数返回0，若不为0则说明创建线程失败，常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程,例如线程数目过多了；后者表示第二个参数代表的线程属性值非法。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码.
函数pthread_join用来等待一个线程的结束。函数原型为：
　　extern int pthread_join __P ((pthread_t __th, void **__thread_return))；
第一个参数为被等待的线程标识符,第二个参数为一个用户定义的指针,它可以用来存储被等待线程的返回值.这个函数是一个线程阻塞的函数,调用它的函数将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回.一个线程的结束有两种途径，一种是象我们上面的例子一样，函数结束了，调用它的线程也就结束了；另一种方式是通过函数pthread_exit来实现。它的函数原型为:
　　extern void pthread_exit __P ((void ＊__retval）) __attribute__ （（__noreturn
唯一的参数是函数的返回代码，只要pthread_join中的第二个参数thread_return不是NULL，这个值将被传递给thread_return。最后要说明的是，一个线程不能被多个线程等待，否则第一个接收到信号的线程成功返回,其余调用pthread_join的线程则返回错误代码ESRCH。
2.1。1线程数据
在单线程的程序里,有两种基本的数据：全局变量和局部变量.但在多线程程序里，还有第三种数据类型：线程数据(TSD： Thread—Specific Data）.它和全局变量很象，在线程内部,各个函数可以象使用全局变量一样调用它,但它对线程外部的其它线程是不可见的.这种数据的必要性是显而易见的。例如我们常见的变量errno,它返回标准的出错信息。它显然不能是一个局部变量，几乎每个函数都应该可以调用它；但它又不能是一个全局变量，否则在A线程里输出的很可能是B线程的出错信息。要实现诸如此类的变量,我们就必须使用线程数据。我们为每个线程数据创建一个键，它和这个键相关联，在各个线程里,都使用这个键来指代线程数据，但在不同的线程里，这个键代表的数据是不同的,在同一个线程里，它代表同样的数据内容。和线程数据相关的函数主要有4个：创建一个键；为一个键指定线程数据;从一个键读取线程数据；删除键。
创建键的函数原型为：
　　extern int pthread_keycreate __P (（pthread_key_t ＊__key,
　　void （＊__destr_function) （void ＊)))；
　　第一个参数为指向一个键值的指针，第二个参数指明了一个destructor函数，如果这个参数不为空，那么当每个线程结束时，系统将调用这个函数来释放绑定在这个键上的内存块。这个函数常和函数pthread_once （(pthread_once_t*once_control, void （＊initroutine) (void)））一起使用，为了让这个键只被创建一次。函数pthread_once声明一个初始化函数，第一次调用pthread_once时它执行这个函数，以后的调用将被它忽略.
2。1。2 互斥锁
互斥锁用来保证一段时间内只有一个线程在执行一段代码，必要性显而易见：假设各个线程向同一个文件顺序写入数据，最后得到的结果一定是灾难性的.函数pthread_mutex_init用来生成一个互斥锁。NULL参数表明使用默认属性。如果需要声明特定属性的互斥锁，须调用函数 pthread_mutexattr_init.
函数pthread_mutexattr_setpshared和函数pthread_mutexattr_settype用来设置互斥锁属性.前一个函数设置属性pshared，它有两个取值，PTHREAD_PROCESS_PRIVATE和PTHREA D_PROCESS_SHARED.前者用来不同进程中的线程同步，后者用于同步本进程的不同线程.pthread_mutex_lock声明开始用互斥锁上锁，直至调用pthread_mutex_unlock为止，均被上锁，
即同一时间只能被一个线程调用执行。当一个线程执行到pthread_mutex_lock处时，如果该锁此时被另一个线程使用，那么此线程被阻塞，即程序将等待到另一个线程释放此互斥锁.使用互斥锁的过程中很有可能会出现死锁，可以使用函数pthread_mutex_trylock,它是函数pthread_mutex_lock的非阻塞版本，当它发现死锁不可避免时，会返回相应的信息，程序员可以根据返回值做具体的处理。
2.1.3 信号量
　　信号量本质上是一个非负的整数计数器，它被用来控制对公共资源的访问。当公共资源增加时，调用函数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。
2.2 设计原理
生产者线程和消费者线程共享同一个缓冲队列,生产者线程向缓冲区中写数据，消费者线程从缓冲区中取数据.但两者必须在使用缓冲队列资源时保持互斥，否则可能会导致在写入时产生数据覆盖，在读出时得到错误数据。因而要在程序中设置一个互斥锁或公用信号量，用于保证线程间的互斥执行。同时生产者线程和消费者线程必须保持同步关系，因为生产者线程的执行为消费者线程提供了需要的数据，是其执行的前提。反之，消费者线程的执行为生产者线程腾出了空闲的缓冲单元,为写数据提供了条件.即消费者线程执行的前提:缓冲队列中至少有一个单元有数据；生产者线程执行的前提：缓冲队列中至少有一个单元是空的。在设计过程中，利用信号量和wait 、signal原语操作来实现.如图1所示：

图1 生产者、消费者共享有界缓冲区
2.3 原语操作实现
The structure of the producer process
do {
// 生产产品
wait (empty）;
wait (mutex）；
// 往Buffer中放入产品
signal （mutex)；
signal (full);
｝ while (true）;
The structure of the consumer process
do ｛
wait (full）；
wait (mutex)；
// 从Buffer中取出产品
signal (mutex）；
signal (empty）;
// 消费产品
} while （true)；
3 开发环境与工具
系统平台：LINUX环境
实现语言:C语言
开发工具：VI编辑器
4 概要设计
4.1 数据结构设计
通过分析课程设计要求，具体设计出如下数据结构：
1. int buffer[20]=｛0｝；//定义缓冲区空间大小
2。包含数据结构pthread_t 它记录一个线程的号，主要包括下面几个函数,完成不同的功能:
int pthread_create __P （(pthread_t ＊__thread, __const thread_attr_t *__attr, void *(*__start_routine) （void *), void *__arg));//创建一个线程。
int pthread_join __P ((pthread_t __th， void **__thread_return)）；
//等待一个线程结束.
4.2 程序模块说明
4。2。1 生产者（Producer）模块
生产者线程向一缓冲区中写入数据，且写入缓冲区的数目不能超过缓冲区容量。当生产者产生出数据，需要将其存入缓冲区之前,首先检查缓冲区中是否有“空"存储单元,若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空"存储单元,生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区,若是有，则阻塞等待，否则，获得缓冲区的使用权,将数据存入缓冲区，释放缓冲区的使用权，其流程图如图2所示：

图2 生产者流程图

4。2。2 消费者（Consumer)模块
消费者线程从缓冲区中读取数据，且消费者读取的数目不能超过生产者写入的数目.消费者取数据之前,首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”,则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据,释放缓冲区的使用权。其执行流程如图3所示:

图3 消费者流程图
5 详细设计
5.1 用户名、源程序名、目标程序名
用户名:rj060131
源程序名：producerconsumer。c
目标程序名：producerconsumer
主机IP地址:192.168。1。87
5。2 源程序代码
＃include 〈stdio.h〉
#include 〈pthread。h〉
#include 〈semaphore.h〉
＃include
＃define BUFFER_SIZE 20 //20个缓冲区
int buffer［20］=｛0｝;
sem_t empty；
sem_t full;
pthread_mutex_t mutex； //for mutual exclusion进程信号量
int in=0; //point to the next free positon
int out=0; //point to the first full positon
//把所有的缓冲区输出到屏幕上
void printAll（)｛
int i;
for(i=0;i<20；i++)
printf（”％d ”，buffer［i])；
printf("\n”）;
printf（”current producer pointer：%d\n"，in)；
printf("current consumer pointer：％d\n"，out）;
｝
//生产者线程
void producer(char ＊arg）{
do｛
sem_wait(＆empty）； //空缓冲区减1
pthread_mutex_lock（＆mutex）; //信号量上锁
//往Buffer中放入产品
buffer[in]=in+1;
in=（in+1)％BUFFER_SIZE；//放入指针调整，为下次送出做准备
printf(”%s\n”，arg)；
printAll（）；
pthread_mutex_unlock(&mutex)； //信号量解锁
sem_post(&full)； //满缓冲区加1,即当公共资源增加时,调用函数sem_post(）增加信号量
sleep（1)；
｝while(1)；
}
//消费者线程
void consumer(char *arg）｛
do｛
sem_wait(＆full）； //满缓冲区减1
pthread_mutex_lock(＆mutex)； //信号量上锁
//从Buffer中取出产品
buffer［out]=0;
out=(out+1）%BUFFER_SIZE；//取指针调整，为下次取做准备
printf（”%s\n",arg）;
printAll（)；
pthread_mutex_unlock（＆mutex); //信号量解锁
sem_post(&empty); //空缓冲区加1
sleep(2)；
｝while(1）；
｝
//主线程
int main（)
{ //创建进程
pthread_t producer1,producer2，producer3,producer4， consumer1，consumer2,consumer3， consumer4 ；
void *retval;
pthread_mutex_init（＆mutex，NULL）；// /＊ 用默认属性初始化一个互斥变量mutex
// 初始化信号量
sem_init（&full，0，0)；
sem_init(＆empty，0，BUFFER_SIZE）；
//pthread_create函数用来创建生产者和消费者进程,其四个参数分别表示为进程、NULL、进程要执行的函数、执行函数时的参数
pthread_create（&producer1，NULL，（void＊)producer，”producer1：”);
pthread_create(＆consumer1,NULL,(void＊）consumer,”consumer1:”);
pthread_create(＆producer2,NULL，(void*)producer，"producer2:"）;
pthread_create(＆consumer2，NULL,(void＊）consumer,”consumer2:”）；
pthread_create(＆producer3,NULL,(void＊）producer,"producer3:");
pthread_create(&consumer3，NULL，(void＊）producer，”consumer3:");
pthread_create(＆producer1，NULL,（void＊)producer,”producer4:”)；
pthread_create(＆consumer1，NULL，（void＊）consumer，”consumer4:”)；
//pthread_join用来表示等待线程的结束，表示producer1，producer2，producer3， producer4, consumer1，consumer2，consumer3 consumer4执行完毕之前主程序必须等待
pthread_join(producer1, ＆retval）；
pthread_join（producer2, &retval）；
pthread_join(producer3， ＆retval);
pthread_join(producer4， &retval）;
pthread_join（consumer1, &retval);
pthread_join（consumer2， ＆retval）；
pthread_join（consumer3， &retval)；
pthread_join（consumer4， &retval）;
｝
6 程序运行结果及分析
6。1 运行结果
进入linux开发环境后，通过vi编辑器在其中编写。进入vi编辑器的命令为：
vi producerconsumer.c
其中,目标文件名后添加的.c表示此程序实现语言为c语言。
关于生产者消费者问题的c程序后，对程序代码进行编译，其中编译命令为：
cc —lpthread —o 　producerconsumer　producerconsumer.c
编译完毕后，对程序进行运行，运行命令为：
。/ producerconsumer
其具体执行过程见下图4所示：

对程序执行编译运行命令后，即可在屏幕上显示出程序运行的结果，其运行结果如下图5所示：

6。2 运行情况分析
7 程序调试记录
8 总结
9 参考文献
［1］［美]Abraham Silberschatz Peter Baer Galvin Greg Gagne 著.OPERATING SYSTEM CONCEPTS［Seventh Edition］.高等教育出版社,2007,01
[2]蔡启先.C语言程序设计教程（第二版).重庆大学出版社,2003,07
［3]张尧学等.计算机操作系统教程（第2版）［M].北京：清华大学出版社,2000.
[4］汤子瀛哲凤屏 汤小丹主编。计算机操作系统〔M〕。西安:西安电子科技大学出版社, 2003.
［5］张尧学等.计算机操作系统教程(第2版）［M］.北京:清华大学出版社，2000.