实验报告五生产者和消费者问题概要x

实验报告五

——生产者和消费者问题

姓名：丛菲 学号： 20100830205 班级：信息安全二班

一、实习内容

? 1、模拟操作系统中进程同步和互斥

? 2、实现生产者和消费者问题的算法实现

二、实习目的

? 1、熟悉临界资源、信号量及 PV 操作的定义与物理意义

? 2、了解进程通信的方法

? 3、掌握进程互斥与进程同步的相关知识

? 4、掌握用信号量机制解决进程之间的同步与互斥问题

? 5、实现生产者－消费者问题，深刻理解进程同步问题

三、实习题目

? 在 Linux 操作系统下用 C 实现经典同步问题：生产者 — 消费者，具体要求如下：

一个大小为 10 的缓冲区，初始状态为空。

2 个生产者，随机等待一段时间，往缓冲区中添加数据，若缓冲区已满，等待消 费者取走数据之后再添加，重复 10 次。

2 个消费者，随机等待一段时间，从缓冲区中读取数据，若缓冲区为空，等待生 产者添加数据之后再读取，重复 10 次。

? 提示

本实验的主要目的是模拟操作系统中进程同步和互斥。在系统进程并发执行 异步推进的过程中，由于资源共享和进程间合作而造成进程间相互制约。进程间的 相互制约有两种不同的方式。

间接制约。这是由于多个进程共享同一资源(如 CPU 、共享输入 /输出设备)

而引起的，即共享资源的多个进程因系统协调使用资源而相互制约。

直接制约。

　只是由于进程合作中各个进程为完成同一任务而造成的， 即并发进

程各自的执行结果互为对方的执行条件，从而限制各个进程的执行速度。

生产者和消费者是经典的进程同步问题，在这个问题中，生产者不断的向缓冲

区中写入数据，而消费者则从缓冲区中读取数据。生产者进程和消费者对缓冲区的

操作是互斥，即当前只能有一个进程对这个缓冲区进行操作，生产者进入操作缓冲

区之前，先要看缓冲区是否已满，如果缓冲区已满，则它必须等待消费者进程将数

据取出才能写入数据，同样的，消费者进程从缓冲区读取数据之前，也要判断缓冲

区是否为空，如果为空，则必须等待生产者进程写入数据才能读取数据。

在本实验中， 进程之间要进行通信来操作同一缓冲区。

　一般来说， 进程间的通信根据通信内 容可以划分为两种： 即控制信息的传送与大批量数据传送。

　有时， 也把进程间控制在本实验 中，进程之间要进行通信来操作同一缓冲区。

　一般来说， 进程间的通信根据通信内容可以划 分为两种： 即控制信息的传送与大批量数据传送。

　有时， 也把进程间控制信息的交换称为低 级通信，而把进程间大批量数据的交换称为高级通信。

目前，计算机系统中用得比较普遍的高级通信机制可分为 3 大类：共享存储器系统、 消 息传递系统及管道通信系统。

? 共享存储器系统 共享存储器系统为了传送大量数据，在存储器中划出一块共享存储区，诸进程可通过对 共享存储区进行读数据或写数据以实现通信。

　进程在通信之前， 向系统申请共享存储区中的 一个分区，并为它指定一个分区关键字。

　信息的交换称为低级通信，而把进程间大批量数 据的交换称为高级通信。

目前，计算机系统中用得比较普遍的高级通信机制可分为 3 大类：共享存储器系统、消息 传递系统及管道通信系统。

? 消息传递系统

在消息传递系统中， 进程间的数据交换以消息为单位， 在计算机网络中被称为报文。

　消息传 递系统的实现方式又可以分为以下两种：

（1）直接通信方式

发送进程可将消息直接发送给接收进程， 即将消息挂在接收进程的消息缓冲队列上， 而接收 进程可从自己的消息缓冲队列中取得消息。

（2）间接通信方式

发送进程将消息发送到指定的信箱中， 而接收进程从信箱中取得消息。

　这种通信方式又称信 箱通信方式， 被广泛地应用于计算机网络中。

　相应地， 该消息传递系统被称为电子邮件系统。

? 管道通信系统

向管道提供输入的发送进程， 以字符流方式将大量的数据送入管道， 而接收进程从管道中接 收数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信。

为了协调发送和接收双方的通信，管道通信机制必须提供以下 3 方面的协调功能。

（1）互斥

当一个进程正在对 pipe 文件进行读或写操作时，另一个进程必须等待。

（2）同步 当写进程把一定数量的数据写入 pipe 文件后，便阻塞等待，直到读进程取走数据后，再把 写进程唤醒。

（3）确认对方是否存在

只有确定对方已存在时， 才能进行管道通信，否则会造成因对方不存在而无限制地等待。 在

这个问题当中，我们采用信号量机制进行进程之间的通信， 设置两个信号量，空的信号量和

满的信号量。在Linux系统中，一个或多个信号量构成一个信号量集合。使用信号量机制可

以实现进程之间的同步和互斥， 允许并发进程一次对一组信号量进行相同或不同的操作。 每

个P、V操作不限于减1或加1，而是可以加减任何整数。在进程终止时，系统可根据需要 自动消除所有被进程操作过的信号量的影响

?缓冲区采用循环队列表示，利用头、尾指针来存放、读取数据，以及判断队列是否为空。

缓冲区中数组大小为 10;

?利用随机函数rand()得到A?Z的一个随机字符，作为生产者每次生产的数据， 存放到缓

冲区中；

使用shmget()系统调用实现共享主存段的创建， shmget()返回共享内存区的ID。对于已

经申请到的共享段，进程需把它附加到自己的虚拟空间中才能对其进行读写。

4?信号量的建立采用 semget()函数，同时建立信号量的数量。在信号量建立后，调用semctl() 对信号量进行初始化，例如本实习中，可以建立两个信号量 SEM_EMPTY、SEM_FULL ,

初始化时设置 SEM_EMPTY为10, SEM_FULL为0。使用操 作信号的函数semop()做排除 式操作，使用这个函数防止对共享内存的同时操作。对共享内存操作完毕后采用 shmctl()函

数撤销共享内存段。

5?使用循环，创建 2个生产者以及2个消费者，采用函数 fork()创建一个新的进程。

6?—个进程的一次操作完成后，采用函数 fflush()刷新缓冲区。

7.程序最后使用semctl()函数释放内存。

模拟程序的程序流程图如下所示：

1?主程序流程图：

退出」

2?生产者进程流程图

3?消费者进程流程图

|X sem_idT S EM_FU L L)

v<?m id,册N FMPn i

P操作流程图

stiuct sembufpc;

pc.seMi_num=

pc.SHfli_qp=-l；

pc.sem_flg = 0,

s&irinp^s&^id, fepc, !);+■'

退出」

5.V操作流程图

退出屮

四、实现代码为：

// exet5.cpp

〃#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define mSIZE 3

#define pSIZE 20

staticintmemery[mSIZE] = {0};

staticint process[pSIZE] = {0};

//static int process[pSIZE] = {2,3,2,1,5,2,4,5,3,2,5,2};

//static int process[pSIZE]

{7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1};

void build();

void LRU();

int main(intargc, char *argv[])

{

printf("Random sequence is as follows:\n");

build();

printf("\nlnvoking LRU Algorithn: \n");

LRU();

return 0;

}

void build()

{

inti = 0;

for(i=0; i<pSIZE; i++)

{

process[i] = (int)(10.0*rand()/(RAND_MAX));

printf("%d ",process[i]);

}

printf("\n");

}

void LRU()

{

int flag[mSIZE] = {0};

inti = 0, j = 0;

int m = -1, n = -1;

int max = -1,maxflag = 0;

int count = 0;

for(i = 0; ivpSIZE; i++)

{

for(j=0; jvmSIZE; j++){

for(j=0; jvmSIZE; j++)

{

if(memery[j] == 0)

{

m = j;

break;

}

}

//Find if there are same processes for(j = 0; j <mSIZE; j++)

{

if(memery[j] == process[i])

{

n = j;

}

}

//Find free PB

for(j = 0; j <mSIZE;j++)

{

if(flag[j]>maxflag)

{

maxflag = flag[j];

max = j;

}

}

if(n == -1) // Find no same process

{

if(m != -1) // find free PB

{

memery[m] = process[i];

flag[m] = 0;

for(j = 0;j <= m; j++)

{

flag[j]++;

}

m = -1;

}

else //NO find free PB

{

memery[max] = process[i];

flag[max] = 0;

for(j = 0;j <mSIZE; j++)

{ {

{ {

flag[j]++;

}

max = -1;

maxflag = 0;

count++;

}

}

else // Find same process

{

memery[n] = process[i];

flag[n] = 0;

if(m != -1) //find free PB

{

flag[m] = 0;

}

for(j = 0;j vmSIZE; j++)

五、在虚拟机上的具体操作及结果



flag[j]++;

}

max = -1;

maxflag = 0;

n = -1;

}

for(j = 0 ;j <mSIZE; j++)

{

printf("%d ",memery[j]);

}

printf("\n");

}

printf("\nThe times of page conversion is: %d\n",count);

}

I 寧三町 四 3. D3：Z1：55 wwgbo0file ￡dliL Jiiew dearth IeohCotumeriiljb 圧Ip

I 寧三町 四 3. D3：Z1：55 wwgbo0

file ￡dliL Jiiew dearth Ieoh

Cotumeriiljb 圧Ip

I eseSx Q

excS.c〔T - godit

untto

Find

■include

?Include

^include

^include

RE

In ■ ?; // Eu^Qft

art ■ ?; // ￡G-WGEi3uA-|iAi*4A

buff[H] - {6}; // >?,i3eeF? i<8￡-' l ■乍哇土忌蔚工肇" t entity // 匸^询肛糾昶r piAuA^^+xeOiEuzub€-

t full tf 上—罰肛皿丘"|HA*ZUA- LtX^D1!^ - N

?tdlib.h> cunifitd.h> <pthreadlJh> ^seraphore.h>

"tu?辆E皿)1〕刖卯關站为畝

^define N J

^define H 1€ ff 卯

lnt int int

i?[i

ser

pthre^d ex t iii讥ex： // ^5

int product id - l； //^nJuOBid

lnt prochtu Jd ■ o； //iQ-NbBid

执行exe5.c文件

选择 Applications Acecessories Terminal,执行文件:

S CjIculdLcra CTiaracuriM^p二 Disk Analyser显 MrHUL^e Pt fi( jNk.<，FasswordE and Encryption Ke屮Ttm' inalUse tie cc"irraTd lineZ TCKC Ediior?oor 呱四圻 3. OJ 17j3& wangtwE |亜.T^ke Screerishcrt—：File system it Networic一

S CjIculdLcr

a CTiaracuriM^p

二 Disk Analyser

显 MrHUL^e Pt fi( jNk

.<，FasswordE and Encryption Ke屮

Ttm' inal

Use tie cc"irraTd line

Z TCKC Ediior

?oo

r 呱四圻 3. OJ 17j3& wangtwE |

亜.T^ke Screerishcrt

—：File system it Networic

一 Floppy Dfiv& j. Ubuntu 9.04a!B

孑 Tomboir Notes

CD/DVD Creator

1 Ubon Lu

_iV ALLes&oriH

>1

>

j- Graphic

>

“ Internet I

>

鮭 Office

>

sound & video

>

r/ Adcl#RemDye.?

Places

一寸 Tra&h

_l

Wk

M SJt

#in?j

tmrl fLncl

ExeS-t

exei

^3

Qxn outer

SesrcD

i 100%

氓 ItaD View

V

依次预处理

错误显示为很多头文件没有预定义。连续查找之后得知原因是链接不上 pthread

库

在执行命令后面加上-pthread，即新命令格式为：gcc -oexe5exe5.—pthread，重 新执行后的结果显示如下截图：

!亨丘 9 IK 1 月 3?03：28;4S wangbo Q

?x?5.c (*) - gedlt

=

wangbotSwangbo-desktop:"

二 C2L

Applications Places System

■

File Edit Yiew Ienninal Help

I C UbtmUi

wangbo^/anqbo ? desktop:

7 g“

0

exe5 exe5

c ?Ipthread

3

wdnabo<Vanat>o-desktOD:*?$ ?/exeS

productl in o. like：

1 e

e

0

e

6

6

e

e

0

=

product2 in 1. like：

1 1

8

0

e

e

e

9

e

0

consumed? in e. Uke:

d 1

e

0

e

e

e

e

e

0

consumedl in 1? li“：

e e

e

0

e

e

6

e

e

9

productl in 2? Uke：

9 e

1

0

e

e

e

e

e

e

product2 in 3. like：

e e

1

1

e

0

e

3

e

e

consumed2 in 2? like:

9 e

e

1

0

0

6

e

e

e

consunedl in 3. like；

9 0

e

0

e

0

e

e

e

0

productl in 4. like：

0 0

e

0

1

0

6

0

e

0

product2 in 5. like：

o e

e

0

1

1

e

e

e

e

consumed? in 4. like:

e e

8

9

e

1

6

3

e

e

consumedl in 5. like：

e e

B

9

e

?

e

e

e

e

productl in 6. like：

b e

B

0

B

0

1

3

6

e

product2 in 7. like:

o e

e

0

0

e

1

1

e

e

consumed2 in 6. like:

e e

e

0

e

e

6

1

e

0

consumedl in 7. Uke：

o e

e

0

e

0

6

9

0

e

productl in 8. like:

e e

e

0

e

6

e

e

1

e

product2 in 9. like:

8 e

e

0

e

o

e

3

1

1

consumed2 in 8? like；

e e

e

0

e

e

e

3

e

1

consumedl in 9. like：

9 G

8

0

e

e

e

e

e

9

productl in 0. like:

1 6

e

0

8

0

6

9

e

0

pro(iuct2 in 1. like:

1 1

e

0

e

e

6

e

e

9

Ijft Ubuntu

! v 4 牢匹 1 月 3.03:29 40 wangboM

匚I r x

exeS.c (*) - gedit

File Edit view Terminal Help

o

e

e

e

4

0

e

0

9

Q

6

e

o

e

e

o

e

e

0

6

e

o

v/angbo^wangbo-desktop: ~

e

1

e

0

e

o o 0

0 0 0

0

0

e

e

Appl： canons Places system

亘

consu?ed2 in o. like: consuiedl In 1. like: productl in 2. like： product2 in 3. like: consu?ed2 in 2. like: consuiedl in 3. like： productl in 4. like： product2 m 5? like: consuB^d2 In 4. like: con^uoedl in 、? likw: productl in 6. like： product2 in 7. like: consu?ed2 in 6. like: consuiedl in 7. like: productl In 8. like: product2 in 9. like： consu?&d2 in 8 like： consuoedl in 9? like: productl in 0. like： product2 in 1. like： consuBed2 in 0? like: consutedl In 1. like: productl In 2. Uke： product2 in 3. like；

e e e e

e e e e

e e e e

9

9

9

e e e e

e e e e e e e

1 e o o

9

0

0

0

更 VtMintu X

w9■■雲

w9■■雲(-)? gerdit

App|dfHtior5 Places 1 ■no

■ ■W” 丽 3.03r3%24 | M?gt?O

wa 的 Be 归 wnng fa o-tfestctopTW

File Edit view Terrninial Help

consumedz in 2- like： ■conswed 1 in 1,

consumedz in 2- like： ■conswed 1 in 1, likei productl in 4.. Like； product2 in 5 likje： ccnnaumE?d2 in 4. like- conswiBdl in 気 Ute^ productl in 6. lik巴： products in 7, like: consurhedZ In &. Like^ coinsuffiedi in 化 like^ produKtl in 8a like： prcductZ in 9. like： consumed! in 3_ like： consumed 1 in 91. likei prodiictl in 9.. Like- prodluet2 in 1.. like： cofisuied2 in 0_ like; co^suoedl in 1? li诞： produictl in 2, like： product2 in 3, like: consumed2 in 2. Like： CDnsufhedl in 3- like： product! in 4. like： piroducta in 5. like；

e e e e

e B a a a e

9

O 1 0 & 6 Q 0 8 1 0 -6 1 0 6 0 Q Q Q BBS 0 6 B OSS o q e OSSA o e @ e o e b e e e e e o e o e o q e a 0 fl 9 6 o e e e lose 1 1 e e 0 19? q a o e 9 e i ? o e i i

e

8

0

9

8

e

B

a

6

9

9

B

8

8

B

9

9

0 8 0

& & &

0 g (3

0 Q 0

01 fl 9

Q S

日日日

1 e e

leg

Q Q 0

& 1 B

Q 1 1

8日1 OSS

9 8 0

0 Q 0

0日0 see

9 8 9

o g B

Q G G

0 0S

0 0 0

其中1表示缓冲区被生产者 produced 或者二producer2写入了 Item ,0表示没

有写入数据或者被消费者 consumerl或者consumer2消耗掉

六、实验总结及思考

1、 本次实验是关于生产者与消费者之间互斥和同步的问题。

　问题的是指是P、 V操作，实验设一个共享缓冲区，生产者和消费者互斥的使用， 当一个线程使用 缓冲区的时候，另一个让其等待直到前一个线程释放缓冲区为止。

2、 实验中包含的知识点很多，包括临界区资源共享问题、信号量定义、 PV 操作流程、进程间的通信方式（消息传递和共享内存）、进程同步和互斥、信号 量机制解决进程之间的同步与互斥问题等等。加深了对于本部分内容的理解

通过本实验设计，我们对操作系统的 P、V进一步的认识，深入的了解 P、 V操作的实质和其重要性。课本的理论知识进一步阐述了现实中的实际问题。