读者/写者问题与进程同步一无优先

一、设计目的

理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。

二、设计要求

在windows环境下编写一个控制台应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。请用信号量和PV操作实现读者/写者问题。

读者/写者问题的描述如下：

有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。有一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。这些条件具体来说就是：

（1）任意多的读进程可以同时读这个文件；

（2）一次只允许一个写进程往文件中写；

（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；

（4）写进程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。

对于读者-写者无优先问题：除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。

三、数据结构设计

3.1 设计测试数据

图1 测试数据
线程名称	申请时刻	持续使用时间
"r1"	0	8
"w1"	1	11
"r2"	2	4
"r3"	3	1
"w2"	4	6
"w3"	6	9
"r4"	7	7
"w4"	9	3
"r5"	10	16
"w5"	12	4

为了验证算法的正确性，需要设计测试数据，并对测试数据进行分析，总结出在该组测试数据下，程序应该得到什么结果，然后运行程序，将程序运行结果与分析结果相比较，如果二者一致，则可认为程序是正确的。

作者设计的测试数据如图2-1所示，包括10个线程，其中有5个读者线程r1~r5，另外5个是写者线程w1~w5。读者线程r1在时刻0提出读请求，如果请求得到允许，r1将用8秒的时间读文件；写者线程w3在时刻6提出写请求，如果请求得到允许，w3将用9秒的时间写文件。从表中可以看出，10个线程提出请求的次序是：r1,w1,r2,r3,w2,w3,r4,w4,r5,w5。

无优先算法

线程实际读写文件顺序为：r1,w1,r2,r3,w2,w3,r4,w4,r5,w5。执行情况见图2-2。

图2 线程的运行状况
线程名称	申请时刻	持续时间	开始操作时刻	结束操作时刻
"r1"	0	8	0	8
"w1"	1	11	8	19
"r2"	2	4	19	23
"r3"	3	1	19	20
"w2"	4	6	23	29
"w3"	6	9	29	38
"r4"	7	7	38	45
"w4"	9	3	45	48
"r5"	10	16	48	64
"w5"	12	4	64	68

3.2 程序功能及界面设计

该程序采用简单的控制台应用程序界面，在主界面上显示程序的功能。该程序的功能如下：演示无优先算法->退出。

3.3 函数设计

实现读者/写者问题的源程序名称是reader_and_writer.cpp。该程序共包括10个函数。这些函数可以分成4组。各组包含的函数及其功能如图8-5。

组别	包括函数	函数功能
一	main()	显示主菜单，接收用户的选择并执行相应的功能。
二	RF_reader_thread() RF_writer_thread() reader_first()	读者优先算法的读者线程函数读者优先算法的写者线程函数读者优先算法的初始化函数：创建10个线程并等待它们结束
三	WF_reader_thread() WF_writer_thread() writer_first()	写者优先算法的读者线程函数写者优先算法的写者线程函数写者优先算法的初始化函数：创建10个线程并等待它们结束
四	FIFO_reader_thread() FIFO_writer_thread() first_come_first_serverd()	无优先算法的读者线程函数无者优先算法的写者线程函数无者优先算法的初始化函数：创建10个线程并等待它们结束
图3 函数功能简述

程序开始部分定义了宏MAX_THREAD，表示程序中创建的线程数。还定义了测试数据的结构体TEST_INFO，该结构体包含三个数据项：线程名称；提出请求的时刻；操作持续时间。接着定义了全局变量，这些全局变量的作用如下：

数组test_data保存了10个线程的测试数据；

整数read_count记录一段时间内同时对文件进行读操作的线程数；

CS_DATA是临界区变量，用来保护文件，实现对文件的读—写互斥和写—写互斥（相当于算法描述中的r_w_w）；

互斥体h_mutex_read_count用来保护整数read_count，以保证多个读者对read_count的互斥访问；

互斥体h_mutex_write_count用来保护整数write_count，以保证多个写者对write_count的互斥访问，该互斥体只在写者优先算法中使用；

互斥体h_mutex_wait只在无优先算法中使用，当文件被使用时，后继的读请求和写请求依次阻塞在h_mutex_wait上。

四、算法设计

流程图：

图4 算法设计流程图

五、程序代码

#include <windows.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <io.h>
#include <string.h>
#define MAX_THREAD 10           //待测试的线程数
typedef struct{                      //表示测试数据格式
	char thread_name[3];            //线程名
	unsigned int require_moment;    //请求操作时刻
	unsigned int persist_time;        //操作持续时间
}TEST_INFO;
TEST_INFO test_data[MAX_THREAD]={    //测试数据表
	{"r1",0,15},                          // r表示读者线程
	{"r2",1, 15},                         //w表示写者线程
	{"w1",3,3},
	{"r3",4, 2},
	{"w2",5,6},
	{"w3",6,10},
	{"r4",7,8},
	{"r5",9,2},
	{"w4",10,18},
	{"w5",12,2}
};

int read_count=0;                     //记录正在读文件的读者数
int write_count=0;                     //在写者优先算法中记录声明要写文件的写者数
CRITICAL_SECTION CS_DATA;       //用于保护文件的临界区变量
HANDLE h_mutex_read_count=CreateMutex(NULL,FALSE,"mutex_read_count");
//读者计数器互斥体
HANDLE h_mutex_write_count=CreateMutex(NULL,FALSE,"mutex_write_count");
//写者计数器互斥体
HANDLE h_mutex_reader_wait=CreateMutex(NULL,FALSE,"mutex_reader_wait");
//在写者优先算法中用于阻塞读者的互斥体
HANDLE h_mutex_first_reader_wait=
CreateMutex(NULL,FALSE,"mutex_first_reader_wait");
//在写者优先算法中用于阻塞第一个读者的互斥体
HANDLE h_mutex_wait=CreateMutex(NULL,FALSE,"mutex_wait");
//无优先时用于阻塞读者和写者的互斥体


//读者优先时的读者线程
void RF_reader_thread(void *data){
	char thread_name[3];                                  //存放线程名称
	strcpy(thread_name,((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	WaitForSingleObject(h_mutex_read_count,-1);
//申请进入关于读者计数器的临界区相当于P操作
	read_count++;
	if(read_count==1)
		EnterCriticalSection(&CS_DATA);      //申请进入关于文件的临界区相当于P操作
	ReleaseMutex(h_mutex_read_count);
//离开关于读者计数器的临界区相当于V操作
	printf("%s ",thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);    //用延迟相应秒来模拟读文件操作
	WaitForSingleObject(h_mutex_read_count,-1);
	read_count--;
	if(read_count==0)
		LeaveCriticalSection(&CS_DATA);  //离开关于文件的临界区相当于V操作
	ReleaseMutex(h_mutex_read_count);
}

//读者优先时的写者线程
void RF_writer_thread(void *data){
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	EnterCriticalSection(&CS_DATA);
	printf("%s ",((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);    //用延迟相应秒来模拟写文件操作
	LeaveCriticalSection(&CS_DATA);
}

//读者优先时的初始化程序
void reader_first(){
	int i=0;
	HANDLE h_thread[MAX_THREAD];
	printf("读优先申请次序：");
	for(i=0;i<MAX_THREAD;i++){
		printf("%s ",test_data[i].thread_name);
	};
	printf("
");
	printf("读优先操作次序：");
	InitializeCriticalSection(&CS_DATA);            //初始化临界区变量
	for(i=0;i<MAX_THREAD;i++){           //根据线程名称创建不同的线程
		if(test_data[i].thread_name[0]=='r')  //名称的首字母是’r’则创建读者线程
h_thread[i]=CreateThread(
NULL,
0,
(LPTHREAD_START_ROUTINE)(RF_reader_thread),
&test_data[i],0,NULL);
		else                           //名称的首字母是’w’则创建写者线程
	h_thread[i]=CreateThread(
NULL,
0,
(LPTHREAD_START_ROUTINE)(RF_writer_thread),
&test_data[i],0,NULL);
	}
	WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);    //等待所有线程结束
    printf("
");
}
//无优先时的读者线程
void FIFO_reader_thread(void *data){
	char thread_name[3];
	strcpy(thread_name,((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	WaitForSingleObject(h_mutex_wait,-1);
	WaitForSingleObject(h_mutex_read_count,-1);
	read_count++;
	if(read_count==1)
		EnterCriticalSection(&CS_DATA);
	ReleaseMutex(h_mutex_read_count);
	ReleaseMutex(h_mutex_wait);
	printf("%s ",thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);
	WaitForSingleObject(h_mutex_read_count,-1);
	read_count--;
	if(read_count==0)
		LeaveCriticalSection(&CS_DATA);
	ReleaseMutex(h_mutex_read_count);
}

//无优先时的写者线程
void FIFO_writer_thread(void *data){
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	WaitForSingleObject(h_mutex_wait,-1);
	EnterCriticalSection(&CS_DATA);
	printf("%s ",((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);
	LeaveCriticalSection(&CS_DATA);
	ReleaseMutex(h_mutex_wait);
}

//无优先时的初始化程序
void first_come_first_served(){
	int i=0;
	HANDLE h_thread[MAX_THREAD];
	printf("无优先申请次序：");
	for(i=0;i<MAX_THREAD;i++){
		printf("%s ",test_data[i].thread_name);
	};
	printf("
");
	printf("无优先操作次序：");
	InitializeCriticalSection(&CS_DATA);
	for(i=0;i<MAX_THREAD;i++){
		if(test_data[i].thread_name[0]=='r')
			h_thread[i]=CreateThread
(NULL,
0,
(LPTHREAD_START_ROUTINE)(FIFO_reader_thread),
&test_data[i],0,NULL);
		else
			h_thread[i]=CreateThread
(NULL,
0,
(LPTHREAD_START_ROUTINE)(FIFO_writer_thread),
&test_data[i],0,NULL);
	}

	WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);
    printf("
");
}

//写者优先时的读者线程
void WF_reader_thread(void *data){
	char thread_name[3];
	strcpy(thread_name,((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	WaitForSingleObject(h_mutex_reader_wait,-1);
	WaitForSingleObject(h_mutex_first_reader_wait,-1);
	WaitForSingleObject(h_mutex_read_count,-1);
	read_count++;
	if(read_count==1)
		EnterCriticalSection(&CS_DATA);
	ReleaseMutex(h_mutex_read_count);
	ReleaseMutex(h_mutex_first_reader_wait);
	ReleaseMutex(h_mutex_reader_wait);
	printf("%s ",thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);
	WaitForSingleObject(h_mutex_read_count,-1);
	read_count--;
	if(read_count==0)
		LeaveCriticalSection(&CS_DATA);
	ReleaseMutex(h_mutex_read_count);
}

//写者优先时的写者线程
void WF_writer_thread(void *data){
	Sleep(((TEST_INFO *)data)->require_moment*1000);
	WaitForSingleObject(h_mutex_write_count,-1);
	if(write_count==0)
		WaitForSingleObject(h_mutex_first_reader_wait,-1);
	write_count++;
	ReleaseMutex(h_mutex_write_count);
	EnterCriticalSection(&CS_DATA);
	printf("%s ",((TEST_INFO *)data)->thread_name);
	Sleep(((TEST_INFO *)data)->persist_time*1000);
	LeaveCriticalSection(&CS_DATA);
	WaitForSingleObject(h_mutex_write_count,-1);
	write_count--;
	if(write_count==0)
		ReleaseMutex(h_mutex_first_reader_wait);
	ReleaseMutex(h_mutex_write_count);
}

//写者优先时的初始化程序
void writer_first(){
	int i=0;
	HANDLE h_thread[MAX_THREAD];
	printf("写优先申请次序：");
	for(i=0;i<MAX_THREAD;i++){
		printf("%s ",test_data[i].thread_name);
	}
	printf("
");
	printf("写优先操作次序：");
	InitializeCriticalSection(&CS_DATA);

	for(i=0;i<MAX_THREAD;i++){
		if(test_data[i].thread_name[0]=='r')
			h_thread[i]=CreateThread
(NULL,
0,
(LPTHREAD_START_ROUTINE)(WF_reader_thread),
&test_data[i],0,NULL);
		else
			h_thread[i]=CreateThread
 (NULL,
0,
(LPTHREAD_START_ROUTINE)(WF_writer_thread),
&test_data[i],0,NULL);
	}
	WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);
    printf("
");
}

//主程序
int main(int argc,char *argv[]){
	char select;
	while(1){
		printf("|-----------------------------------|
");
		printf("|  1:reader first          |
");
		printf("|  2:first come first served |
");
		printf("|  3:writer first           |
");
		printf("|  4:exit                 |
");
		printf("|-----------------------------------|
");
		printf("select a function(1~4):");
		do{
			select=(char)getch();
		}while(select!='1'&&select!='2'&&select!='3'&&select!='4');
		system("cls");
		switch(select){
		case '1':
			reader_first();
			break;
		case '2':
			first_come_first_served();
			break;
		case '3':
			writer_first();
			break;
		case '4':
			return 0;
		}
		printf("
Press any key to continue.");
		getch();
		system("cls");
	}
	return 0;
}

六、运行结果

6.1 运行结果截图

图5 运行结果

6.2 运行结果分析

包括10个线程，其中有5个读者线程r1~r5，另外5个是写者线程w1~w5。读者线程r1在时刻0提出读请求，请求得到允许，r1将用8秒的时间读文件；写者线程w1在时刻2提出写请求，由于读-写为互斥关系即在r1结束后获得运行即第8秒开始运行，而r2,r3分别在时刻2，3到达，由于读-读为同步关系，即r2,r3同时开始运行，而此时w2也已经到达，因为读-写互斥得等23时刻r2,r3均运行结束才能开始，同时写-写也互斥，根据此规则，不难推理出10个线程提出请求的次序是：r1,w1,r2,r3,w2,w3,r4,w4,r5,w5验证了运行结果的正确性。

七、设计总结

通过在Windows环境下编写控制台应用程序，我深入研究了临界区和进程互斥的概念，并成功地实现了读者-写者问题的无优先算法，采用了信号量和PV操作确保了对共享数据区的正确访问。在设计中，我创建了N个线程，包括读者线程和写者线程，它们按照预先设计好的测试数据进行读写操作。通过信号量，我能够满足读者-写者问题的四个条件，即读-读允许，读-写互斥，写-写互斥，以及写者执行前等待已有读者或写者退出。设计的测试数据经过仔细分析，验证了算法的正确性。通过预测程序应该得到的结果，并在实际运行中与分析结果进行对比，我确认了无优先算法在给定的测试数据下的正确性。这次实验深化了我对进程互斥和临界区的理解,让我更加熟练地掌握了这些关键概念，为我未来在操作系统和并发编程领域的学习和研究奠定了坚实的基础。

一、 设计目的