实验3读者写者问题与进程同步文档格式.docx
《实验3读者写者问题与进程同步文档格式.docx》由会员分享,可在线阅读,更多相关《实验3读者写者问题与进程同步文档格式.docx(18页珍藏版)》请在冰点文库上搜索。
![实验3读者写者问题与进程同步文档格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/9/344917d3-7a10-4955-96bb-815a70946f59/344917d3-7a10-4955-96bb-815a70946f591.gif)
除了上述四个规则外,不再规定读写的优先权,谁先等待谁就先使用文件。
实验步骤
算法分析
1、错误的解法
图3-1错误的解法
semaphorer_w_w=1;
reader(){
P(r_w_w);
读文件;
V(r_w_w);
}
writer(){
写文件;
有同学认为,可以将文件视为临界资源,使用临界资源的代码就构成临界区,为了对临界区进行管理,只需设置一个互斥信号量r_w_w,读或者写之前执行P(r_w_w),之后执行V(r_w_w)即可,从而得到图3-1所示的算法描述。
该方法虽然能满足读—写互斥和写—写互斥,但是不满足读—读允许,只要有一个读者在读文件,其他的读者都被阻塞了。
可见,单纯使用互斥信号量不能解决读者/写者问题,还需要引入计数器对读者进行记数。
2、读者优先
如何纠正上述解法中存在的错误呢?
其实,对于相继到达的一批读者,并不是每个读者都需要执行P(r_w_w)和V(r_w_w)。
在这批读者中,只有最先到达的读者才需要执行P(r_w_w),与写者竞争对文件的访问权,假设执行P(r_w_w)成功则获得了文件的访问权,其他的读者可直接访问文件;
同理,只有最后退出临界区的读者需要执行V(r_w_w)来归还文件访问权。
为了记录正在读文件的一批读者的数量,需要设置一个整型变量readercount,每一个读者到达时都要将readercount加1,退出时都要将readercount减1。
由于只要有一个读者在读文件,便不允许写者写文件,所以,仅当readercount=0时,即尚无读者在读文件时,读者才需要执行P(r_w_w)操作。
假设P(r_w_w)操作成功,读者便可去读文件,相应地,readercount+1。
同理,仅当在执行了readercount减1操作后其值为0时,才需要执行V(r_w_w)操作,以便让写者写文件。
又因为readercount是一个可被多个读者访问的临界资源,所以应该为它设置一个互斥信号量readercount_mutex.。
每个读者在访问readercount之前执行P(readercount_mutex),之后执行V(readercount_mutex)。
通过上述分析得到图3-2所示的算法描述,其中的数字表示语句对应的行号。
图3-2读者优先算法
01semaphorer_w_w=1;
02semaphorereadercount_mutex=1;
03intreadercount=0;
04reader(){
05P(readercount_mutex);
06if(readercount==0)P(r_w_w);
07readercount++;
08V(readercount_mutex);
09读文件;
10P(readercount_mutex);
11readercount--;
12if(readercount==0)V(r_w_w);
13V(readercount_mutex);
14}
15
16writer(){
17P(r_w_w);
18写文件;
19V(r_w_w);
20}
3、写者优先
通过增加信号量并修改上述程序可以得到写者优先算法。
为了实现写者优先算法,需要将写者和读者分开排队,并且第一个读者和其它读者也要分开排队。
这样就需要三个队列,一个是写者排队的地方,另一个是第一个读者排队的地方,第三个是其它读者排队的地方。
相应地需要设置三个信号量,r_w_w、first_reader_wait和reader_wait。
当一个写者声明想写文件时,可以让新的读者中的第一个到first_reader_wait上排队等待;
当有读者阻塞在first_reader_wait上时,让其它读者阻塞在reader_wait上;
当有一个写者在写文件时,其它写者到r_w_w上排队。
只要有活跃的写者或者写者队列不为空,则阻塞新到达的读者。
为了记录已经发出声明的写者数量,需要设置一个整数writercount,以表示声明要写文件的写者数目。
由于只要有一个写者到达,就不允许读者去读,因此仅当writercount=0,表示无写者声明写时,写者才需要执行P(first_reader_wait)操作,假设操作成功,写者便可以执行P(r_w_w)去竞争写文件权利。
其它写者不需要再向读者声明,可以直接执行P(r_w_w)去竞争写文件权利。
同理仅当写者在执行writercount减1操作后其值为0时,才需要执行V(first_reader_wait)操作,以便唤醒第一个被阻塞的读者去读文件。
又因为writercount是一个可被多个写者访问的临界资源,所以,应该为它设置一个互斥信号量writer_mutex。
4、无优先
除了在读者优先时需要的信号量r_w_w和readercount_mutex之外,还需要设置一个信号量wait供读者和写者排队。
读者和写者都排在wait队列上。
假设有读者在读文件,则第一个写者阻塞在r_w_w上,其它的写者和读者阻塞在wait上;
假设有一个写者在写文件,则其它写者和读者都阻塞在wait上。
无优先的算法描述如图3-3所示。
图3-3无优先算法
02semaphorewait=1;
03semaphorereadercount_mutex=1;
04intreadercount=0;
05reader(){
06P(wait);
07P(readercount_mutex);
08if(readercount==0)P(r_w_w);
09readercount++;
10V(readercount_mutex);
11V(wait);
12读文件;
13P(readercount_mutex);
14readercount--;
15if(readercount==0)V(r_w_w);
16V(readercount_mutex);
17}
18writer(){
19P(wait);
20P(r_w_w);
21写文件;
22V(r_w_w);
23V(wait);
24}
3.3.2程序功能及界面设计
该程序采用简单的控制台应用程序界面,在主界面上显示程序的功能。
该程序的功能如下:
1.演示读者优先算法;
2.演示写者优先算法;
3.演示无优先算法;
4.退出。
3.3.3函数设计
实现读者/写者问题的源程序名称是reader_and_writer.cpp。
该程序共包括10个函数。
这些函数可以分成4组。
各组包含的函数及其功能如图3-4。
组别
包括函数
函数功能
一
main()
显示主菜单,接收用户的选择并执行相应的功能。
二
RF_reader_thread()
RF_writer_thread()
reader_first()
读者优先算法的读者线程函数
读者优先算法的写者线程函数
读者优先算法的初始化函数:
创建10个线程并等待它们结束
三
WF_reader_thread()
WF_writer_thread()
writer_first()
写者优先算法的读者线程函数
写者优先算法的写者线程函数
写者优先算法的初始化函数:
四
FIFO_reader_thread()
FIFO_writer_thread()
first_come_first_serverd()
无优先算法的读者线程函数
无者优先算法的写者线程函数
无者优先算法的初始化函数:
图3-4函数功能简述
程序开始部分定义了宏MAX_THREAD,表示程序中创建的线程数。
还定义了测试数据的结构体TEST_INFO,该结构体包含三个数据项:
线程名称;
提出请求的时刻;
操作持续时间。
接着定义了全局变量,这些全局变量的作用如下:
数组test_data保存了10个线程的测试数据;
整数read_count记录一段时间内同时对文件进行读操作的线程数;
整数write_count记录一段时间内提出写操作请求的线程数,该整数只在写者优先算法中使用;
CS_DATA是临界区变量,用来保护文件,实现对文件的读—写互斥和写—写互斥〔相当于算法描述中的r_w_w〕;
互斥体h_mutex_read_count用来保护整数read_count,以保证多个读者对read_count的互斥访问;
互斥体h_mutex_write_count用来保护整数write_count,以保证多个写者对write_count的互斥访问,该互斥体只在写者优先算法中使用;
互斥体h_mutex_first_reader_wait和h_mutex_reader_wait只在写者优先算法中使用,当有写者在写文件时,提出读请求的第一个读者阻塞在h_mutex_first_reader_wait上,其余的读者阻塞在h_mutex_reader_wait上;
互斥体h_mutex_wait只在无优先算法中使用,当文件被使用时,后继的读请求和写请求依次阻塞在h_mutex_wait上。
3.3.4参考源程序
3.3.4.1Linux下的参考源程序
编译命令
gccreader_and_writer.cpp–oreader_and_writer.o–lcurses–lpthread
程序清单
#include<
unistd.h>
pthread.h>
curses.h>
stdlib.h>
string.h>
#defineMAX_THREAD10
typedefstruct{
charthread_name[3];
unsignedintrequire_moment;
unsignedintpersist_time;
}TEST_INFO;
TEST_INFOtest_data[MAX_THREAD]={
{"
r1"
0,15},
r2"
1,15},
w1"
3,3},
r3"
4,2},
w2"
5,6},
w3"
6,10},
r4"
7,8},
r5"
9,2},
w4"
10,18},
w5"
12,2}
};
intread_count=0;
intwrite_count=0;
pthread_mutex_tCS_DATA;
pthread_mutex_th_mutex_read_count;
pthread_mutex_th_mutex_write_count;
pthread_mutex_th_mutex_reader_wait;
pthread_mutex_th_mutex_first_reader_wait;
pthread_mutex_th_mutex_wait;
void*RF_reader_thread(void*data){
strcpy(thread_name,((TEST_INFO*)data)->
thread_name);
sleep(((TEST_INFO*)data)->
require_moment);
pthread_mutex_lock(&
h_mutex_read_count);
read_count++;
if(read_count==1)
pthread_mutex_lock(&
CS_DATA);
pthread_mutex_unlock(&
printw("
%s"
thread_name);
refresh();
persist_time);
read_count--;
if(read_count==0)
pthread_mutex_unlock(&
return0;
void*RF_writer_thread(void*data){
((TEST_INFO*)data)->
voidreader_first(){
inti=0;
pthread_th_thread[MAX_THREAD];
readerfirstrequiresequence:
"
);
for(i=0;
i<
MAX_THREAD;
i++){
printw("
test_data[i].thread_name);
};
\n"
readerfirstoperationsequence:
pthread_mutex_init(&
CS_DATA,NULL);
if(test_data[i].thread_name[0]=='
r'
)
pthread_create(&
h_thread[i],NULL,RF_reader_thread,&
test_data[i]);
else
h_thread[i],NULL,RF_writer_thread,&
}
pthread_join(h_thread[i],NULL);
void*FIFO_reader_thread(void*data){
h_mutex_wait);
void*FIFO_writer_thread(void*data){
voidfirst_come_first_served(){
FCFSrequiresequence:
FCFS:
operationsequence:
h_thread[i],NULL,FIFO_reader_thread,&
h_thread[i],NULL,FIFO_writer_thread,&
void*WF_reader_thread(void*data){
h_mutex_reader_wait);
h_mutex_first_reader_wait);
void*WF_writer_thread(void*data){
h_mutex_write_count);
if(write_count==0)
write_count++;
write_count--;
pthread