- 相關推薦
基于C++的讀者與寫者問題read—write problem的實現(一)
基于C++的讀者與寫者問題的實現 1
１．設計題目與要求 1
２．總的設計思想及系統平臺、語言、工具等 1
2.1 設計思想 1
2.2 系統平臺，語言，工具 4
３．數據結構與模塊說明（功能與流程圖） 4
3.1 功能實現 4
3.2 流程圖 6
４．源程序 7
4.1 .ReaderAndWriter.CPP // 具體的實現 7
4.2.thread.dat //輔助的文件，但是必不可以少 15
５．運行結果與運行情況 15
６．調試記錄 17
７．自我評析和總結 18
基于C++的讀者與寫者問題read—write problem的實現
１．設計題目與要求
讀者寫者問題（read—write problem）是一個經典的并發程序設計問題。有兩組并發進程：讀者和寫者，共享一個問題F，要求：（1）允許多個讀者可同時對之執行讀操作；（2）只允許一個寫者往文件中寫信息；（3）任一寫者在完成寫操作之前不允許其他讀者或者寫者工作；（4）寫者執行寫操作前，應讓已有的寫者和讀者全部退出。
２．總的設計思想及系統平臺、語言、工具等
2.1 設計思想
根據題目要求，首先分析了以下4種可能發生的情況：
第 1 種情況: 讀者的優先權比寫者高，而且，不用調配。
所有讀者的優先權都比寫者的優先權高，而且，不用調配。一個讀者需要等待的唯一情況是，一個寫者已經占用了文件。一個寫者可以取得文件的條件是，沒有一個讀者處在等待狀態或正在讀文件。允許讀者們結盟，以便能長期占用文件，而禁止寫者的寫。
第 2 種情況: 在一個讀者已經占有了文件的時候，全體讀者的優先權才比寫者高。
在沒有任何一個讀者在讀文件時，讀者的優先權和寫者的優先權相同。相反，如果有一個讀者正在讀文件，則其余的各讀者都可以讀文件，而不管有多少寫者處在等待狀態。所有讀者都有權結盟，以便壟斷文件。
第 3 種情況: 寫者的優先權比讀者的優先權高。
在一個寫者提出要訪問文件時，就必須使其盡可能的得到文件，而且不用調配。也就是說，在出現這一請求時，占據著文件的各進程都被執行完以后，寫者可以立即得到文件。因此，在文件已為一寫者請求之后到來的那些讀者都必須等待，盡管某些讀者正在應用文件，也是如此。所有寫者可以結盟，以便能長期禁止讀者的讀。
第 4 種情況: 所有寫者的和所有讀者有相同的優先權高，哪一類都不會有比另一類更高的優先權。
如果一個讀者正在應用文件，則在一個寫者請求文件之前到來的全體讀者，都能讀文件，而之后到來的讀者或寫者，則要等待，不必區分他們屬于哪一類進程。如果一個寫者正在寫文件，則所有新到來的請求都必須等待。在這一寫者寫完之后，它就要喚醒處在等待隊列中的排在第一個位置的進程。如果此時有幾個讀者連續排在等待隊列中的最前面各位置上，則它們可以同時去讀文件。
最后為了簡化問題，將其分為兩種主要情況：
（1）讀者優先：
如果沒有寫者正在操作，則讀者不需要等待，用一個整型變量readcount記錄當前的讀者數目，用于確定是否釋放寫者線程，（當readcout=0 時，說明所有的讀者都已經讀完，釋放一個寫者線程），每個 讀者開始讀之前都要修改readcount,為了互斥的實現對readcount 的修改，需要一個互斥對象Mutex來實現互斥。
另外，為了實現寫-寫互斥，需要一個臨界區對象 write,當寫者發出寫的請求時，必須先得到臨界區對象的所有權。通過這種方法，可以實現讀寫互斥，當readcount=1 時，（即第一個讀者的到來時，），讀者線程也必須申請臨界區對象的所有權.
當讀者擁有臨界區的所有權，寫者都阻塞在臨界區對象write上。當寫者擁有臨界區對象所有權時，第一個判斷完readcount==1 后，其余的讀者由于等待對readcount的判斷，阻塞在Mutex上！
（2）寫者優先：
寫者優先和讀者優先有相同之處，不同的地方在：一旦有一個寫者到來時，應該盡快讓寫者進行寫，如果有一個寫者在等待，則新到的讀者操作不能讀操作，為此添加一個整型變量writecount,記錄寫者的數目，當writecount=0時才可以釋放讀者進行讀操作！
為了實現對全局變量writecount的互斥訪問，設置了一個互斥對象Mutex3。
為了實現寫者優先，設置一個臨界區對象read,當有寫者在寫或等待時，讀者必須阻塞在臨界區對象read上。
讀者除了要一個全局變量readcount實現操作上的互斥外，還需要一個互斥對象對阻塞在read這一個過程實現互斥，這兩個互斥對象分別為mutex1和mutex2。
測試數據文件格式：測試數據文件包括n 行測試數據，分別描述創建的n 個線程是讀者還是寫者，以及讀寫操作的開始時間和持續時間。每行測試數據包括四個字段，各字段間用空格分隔。第一字段為一個正整數，表示線程序號。第一字段表示相應線程角色，R 表示讀者是，W 表示寫者。第二字段為一個正數，表示讀寫操作的開始時間。線程創建后，延時相應時間（單位為秒）后發出對共享資源的讀寫申請。第三字段為一個正數，表示讀寫操作的持續時間。當線程讀寫申請成功后，開始對共享資源的讀寫操作，該操作持續相應時間后結束，并釋放共享資源。
下面是一個測試數據文件的例子：
1 R 3 5
2 W 4 5
3 R 5 2
4 R 6 5
5 W 5.1 3
運行結果顯示要求：要求在每個線程創建、發出讀寫操作申請、開始讀寫操作和結束讀寫操作時分別顯示一行提示信息，以確信所有處理都遵守相應的讀寫操作限制。
2.2 系統平臺，語言，工具
本次設計在WINDOWS XP操作系統平臺下，使用c++語言實現讀者與寫者問題。使用的軟件是Visual C++。
３．數據結構與模塊說明（功能與流程圖）
3.1 功能實現
相關API介紹：
線程控制：
CreateThread 完成線程創建，在調用進程的地址空間上創建一個線程，以執行指定的函數；它的返回值為所創建線程的句柄。
HANDLE CreateThread（
LPSECURITY_ATTRIBUTES lpThreadAttributes, // SD
DWORD dwStackSize, // initial stack size
LPTHREAD_START_ROUTINElpStartAddress, // thread function
LPVOID lpParameter, // thread argument
DWORD dwCreationFlags, // creation option
LPDWORD lpThreadId // thread identifier
）;
ExitThread 用于結束當前線程。
VOID ExitThread（DWORD dwExitCode // exit code for this thread）;
Sleep 可在指定的時間內掛起當前線程。
VOID Sleep（DWORD dwMilliseconds // sleep time）;
信號量控制：
CreateMutex 創建一個互斥對象，返回對象句柄；
HANDLE CreateMutex（
LPSECURITY_ATTRIBUTES lpMutexAttributes, // SD
BOOL bInitialOwner, // initial owner
LPCTSTR lpName // object name）;
OpenMutex 打開并返回一個已存在的互斥對象句柄，用于后續訪問；
HANDLE OpenMutex（
DWORD dwDesiredAccess, // access
BOOL bInheritHandle, // inheritance option
LPCTSTR lpName // object name）;
ReleaseMutex 釋放對互斥對象的占用，使之成為可用。
BOOL ReleaseMutex（
HANDLE hMutex // handle to mutex）;
WaitForSingleObject 可在指定的時間內等待指定對象為可用狀態；
DWORD WaitForSingleObject（
HANDLE hHandle, // handle to object
DWORD dwMilliseconds // time-out interval）;
測試文件數據結構如下：
struct ThreadInfo
{
int serial; //線程序號
char entity; //線程類別(判斷是讀者還是寫者線程)
double delay; //線程延遲時間
double persist; //線程讀寫操作時間
};
void RP_ReaderThread(void *p) // 讀者優先情況下的讀者線程信息
void RP_WriterThread(void *p) //讀者優先情況下的寫者線程信息
void ReaderPriority(char *file) //讀者優先處理函數
void WP_ReaderThread(void *p) //寫者優先情況下的讀者線程信息
void WP_ReaderThread(void *p) //寫者優先情況下的寫者線程信息
void WriterPriority(char *file) //寫者優先處理函數
int main(int argc,char *argv //主函數,負責調用讀者或者寫者優先函數
3.2 流程圖
否
是
是 否
否
否 是 否
是
是
否
否
是
４．源程序
4.1 .ReaderAndWriter.CPP // 具體的實現
#include "windows.h"
#include <conio.h>
#include <stdlib.h>
#include <fstream.h>
#include <io.h>
#include <string.h>
#include <stdio.h>
#define READER 'R' //讀者
#define WRITER 'W' //寫者
#define INTE_PER_SEC 1000 //每秒時鐘中斷的數目
#define MAX_THREAD_NUM 64 //最大線程數
#define MAX_FILE_NUM 32 //最大文件數目數
#define MAX_STR_LEN 32 //字符串的長度
int readcount=0; //讀者數目
int writecount=0; //寫者數目
CRITICAL_SECTION RP_Write; //臨界資源
CRITICAL_SECTION cs_Write;
CRITICAL_SECTION cs_Read;
struct ThreadInfo
{
int serial; //線程序號
char entity; //線程類別(判斷是讀者還是寫者線程)
double delay; //線程延遲時間
double persist; //線程讀寫操作時間
};
///////////////////////////////////////////////////////////////////////////
// 讀者優先---讀者線程
//P:讀者線程信息
void RP_ReaderThread(void *p)
{
//互斥變量
HANDLE h_Mutex;
h_Mutex=OpenMutex(MUTEX_ALL_ACCESS,FALSE,"mutex_for_readcount");
DWORD wait_for_mutex; //等待互斥變量所有權
DWORD m_delay; //延遲時間
DWORD m_persist; //讀文件持續時間
int m_serial; //線程序號
// 從參數中獲得信息
m_serial=((ThreadInfo*)(p))->serial ;
m_delay=(DWORD)(((ThreadInfo*)(p))->delay *INTE_PER_SEC);
m_persist=(DWORD)(((ThreadInfo*)(p))->persist *INTE_PER_SEC);
Sleep(m_delay); //延遲等待
printf("Reader thread %d sents the reading require.\n",m_serial);
//等待互斥信號,保證對ReadCount 的訪問,修改互斥
wait_for_mutex=WaitForSingleObject(h_Mutex,-1);
//讀者數目增加
readcount++;
if(readcount==1)
{
//第一個讀者,等待資源
EnterCriticalSection(&RP_Write);
}
ReleaseMutex(h_Mutex); //釋放互斥信號
//讀文件
printf("Reader thread %d begins to read file.\n",m_serial);
Sleep(m_persist);
//退出線程
printf("Reader thread %d finished reading file.\n",m_serial);
//等待互斥信號,保證對ReadCount的訪問,修改互斥
wait_for_mutex=WaitForSingleObject(h_Mutex,-1);
//讀者數目減少
readcount--;
if(readcount==0)
{
//如果所有的讀者讀完,喚醒寫者
LeaveCriticalSection(&RP_Write);
}
ReleaseMutex(h_Mutex); //釋放互斥信號
}
//////////////////////////////////////////////////////////////
//P:寫者線程信息
void RP_WriterThread(void *p)
{
DWORD m_delay; //延遲時間
DWORD m_persist; //寫文件持續時間
int m_serial; //線程序號
// 從參數中獲得信息
m_serial=((ThreadInfo*)(p))->serial ;
m_delay=(DWORD)(((ThreadInfo*)(p))->delay *INTE_PER_SEC);
m_persist=(DWORD)(((ThreadInfo*)(p))->persist *INTE_PER_SEC);
Sleep(m_delay);
printf("Write thread %d sents the writing require.\n",m_serial);
//等待資源
EnterCriticalSection(&RP_Write);
//寫文件
printf("Writer thread %d begins to write to the file.\n",m_serial);
Sleep(m_persist);
//退出線程
printf("Write thread %d finished writing to the file.\n",m_serial);
//釋放資源
LeaveCriticalSection(&RP_Write);
}
//////////////////////////////////////////////////////////////
//讀者優先處理函數
//file:文件名
void ReaderPriority(char *file)
{
DWORD n_thread=0; //線程數目
DWORD thread_ID; //線程ID
DWORD wait_for_all; //等待所有線程結束
//互斥對象
HANDLE h_Mutex;
h_Mutex=CreateMutex(NULL,FALSE,"mutex_for_readcount");
//線程對象的數組
HANDLE h_Thread[MAX_THREAD_NUM];
ThreadInfo thread_info[MAX_THREAD_NUM];
readcount=0; //初始化readcount
InitializeCriticalSection(&RP_Write); //初始化臨界區
ifstream inFile;
inFile.open (file);
printf("Reader Priority:\n\n");
while(inFile)
{
//讀入每一個讀者,寫者的信息
inFile>>thread_info[n_thread].serial;
inFile>>thread_info[n_thread].entity;
inFile>>thread_info[n_thread].delay;
inFile>>thread_info[n_thread++].persist;
inFile.get();
}
for(int i=0;i<(int)(n_thread);i++)
{
if(thread_info[i].entity==READER||thread_info[i].entity =='r')
{
//創建讀者進程
h_Thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(RP_ReaderThread),&thread_info[i],0,&thread_ID);
}
else
{
//創建寫線程
h_Thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(RP_WriterThread),&thread_info[i],0,&thread_ID);
}
}
//等待所有的線程結束
wait_for_all=WaitForMultipleObjects(n_thread,h_Thread,TRUE,-1);
printf("All reader and writer have finished operating.\n");
}
////////////////////////////////////////////////////////
//寫者優先---讀者線程
//P:讀者線程信息
void WP_ReaderThread(void *p)
{
//互斥變量
HANDLE h_Mutex1;
h_Mutex1=OpenMutex(MUTEX_ALL_ACCESS,FALSE,"mutex1");
HANDLE h_Mutex2;
h_Mutex2=OpenMutex(MUTEX_ALL_ACCESS,FALSE,"mutex2");
DWORD wait_for_mutex1; //等待互斥變量所有權
DWORD wait_for_mutex2;
DWORD m_delay; //延遲時間
DWORD m_persist; //讀文件持續時間
int m_serial; //線程的序號
//從參數中得到信息
m_serial=((ThreadInfo*)(p))->serial ;
m_delay=(DWORD)(((ThreadInfo*)(p))->delay *INTE_PER_SEC);
m_persist=(DWORD)(((ThreadInfo*)(p))->persist *INTE_PER_SEC);
Sleep(m_delay); //延遲等待
printf("Reader thread %d sents the reading require.\n",m_serial);
wait_for_mutex1=WaitForSingleObject(h_Mutex1,-1);
//讀者進去臨界區
EnterCriticalSection(&cs_Read);
//阻塞互斥對象Mutex2,保證對readCount的訪問和修改互斥
wait_for_mutex2=WaitForSingleObject(h_Mutex2,-1);
//修改讀者的數目
readcount++;
if(readcount==1)
{
// 如果是第1個讀者,等待寫者寫完
EnterCriticalSection(&cs_Write);
}
ReleaseMutex(h_Mutex2);// 釋放互斥信號 Mutex2
//讓其他讀者進去臨界區
LeaveCriticalSection(&cs_Read);
ReleaseMutex(h_Mutex1);
//讀文件
printf("Reader thread %d begins to read file.\n",m_serial);
Sleep(m_persist);
//退出線程
printf("Reader thread %d finished reading file.\n",m_serial);
//阻塞互斥對象Mutex2,保證對readcount的訪問,修改互斥
wait_for_mutex2=WaitForSingleObject(h_Mutex2,-1);
readcount--;
if(readcount==0)
{
//最后一個讀者,喚醒寫者
LeaveCriticalSection(&cs_Write);
}
ReleaseMutex(h_Mutex2); //釋放互斥信號
}
///////////////////////////////////////////
//寫者優先---寫者線程
//P:寫者線程信息
void WP_WriterThread(void *p)
{
DWORD wait_for_mutex3; //互斥變量
DWORD m_delay; //延遲時間
DWORD m_persist; //讀文件持續時間
int m_serial; //線程序號
HANDLE h_Mutex3;
h_Mutex3=OpenMutex(MUTEX_ALL_ACCESS,FALSE,"mutex3");
//從參數中獲得信息
m_serial=((ThreadInfo*)(p))->serial ;
m_delay=(DWORD)(((ThreadInfo*)(p))->delay *INTE_PER_SEC);
m_persist=(DWORD)(((ThreadInfo*)(p))->persist *INTE_PER_SEC);
Sleep(m_delay); //延遲等待
printf("Writer thread %d sents the reading require.\n",m_serial);
wait_for_mutex3=WaitForSingleObject(h_Mutex3,-1);
writecount++; //修改寫者數目
if(writecount==1)
{
EnterCriticalSection(&cs_Read);
}
ReleaseMutex(h_Mutex3);
EnterCriticalSection(&cs_Write);
printf("Writer thread %d begins to write to the file.\n",m_serial);
Sleep(m_persist);
printf("Writer thread %d finished writing to the file.\n",m_serial);
LeaveCriticalSection(&cs_Write);
wait_for_mutex3=WaitForSingleObject(h_Mutex3,-1);
writecount--;
if(writecount==0)
{
LeaveCriticalSection(&cs_Read);
}
ReleaseMutex(h_Mutex3);
}
/////////////////////////////////////////////
//寫者優先處理函數
// file:文件名
void WriterPriority(char * file)
{
DWORD n_thread=0;
DWORD thread_ID;
DWORD wait_for_all;
HANDLE h_Mutex1;
h_Mutex1=CreateMutex(NULL,FALSE,"mutex1");
HANDLE h_Mutex2;
h_Mutex2=CreateMutex(NULL,FALSE,"mutex2");
HANDLE h_Mutex3;
h_Mutex3=CreateMutex(NULL,FALSE,"mutex3");
HANDLE h_Thread[MAX_THREAD_NUM];
ThreadInfo thread_info[MAX_THREAD_NUM];
readcount=0;
writecount=0;
InitializeCriticalSection(&cs_Write);
InitializeCriticalSection(&cs_Read);
ifstream inFile;
inFile.open (file);
printf("Writer priority:\n\n");
while(inFile)
{
inFile>>thread_info[n_thread].serial;
inFile>>thread_info[n_thread].entity;
inFile>>thread_info[n_thread].delay;
inFile>>thread_info[n_thread++].persist;
inFile.get();
}
for(int i=0;i<(int)(n_thread);i++)
{
if(thread_info[i].entity==READER||thread_info[i].entity =='r')
{
//創建讀者進程
h_Thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(WP_ReaderThread),&thread_info[i],0,&thread_ID);
}
else
{
//創建寫線程
h_Thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(WP_WriterThread),&thread_info[i],0,&thread_ID);
}
}
//等待所有的線程結束
wait_for_all=WaitForMultipleObjects(n_thread,h_Thread,TRUE,-1);
printf("All reader and writer have finished operating.\n");
}
/////////////////////////////////////////////////////
//主函數
int main(int argc,char *argv[])
{
char ch;
while(true)
{
printf("*************************************\n");
printf(" 1.Reader Priority\n");
printf(" 2.Writer Priority\n");
printf(" 3.Exit to Windows\n");
printf("*************************************\n");
printf("Enter your choice(1,2,3): ");
do{
ch=(char)_getch();
}while(ch!='1'&&ch!='2'&&ch!='3');
system("cls");
if(ch=='3')
return 0;
else if(ch=='1')
ReaderPriority("thread.dat");
else
WriterPriority("thread.dat");
printf("\nPress Any Key to Coutinue:");
_getch();
system("cls");
}
return 0;
}
4.2.thread.dat //輔助的文件，但是必不可以少
1 r 3 5
2 w 4 5
3 r 5 2
4 r 6 5
5 w 5.1 3
５．運行結果與運行情況
對源程序進行編譯,鏈接后,執行程序:
當選擇1 Reader Priority 時，程序運行結果如下：
按任意建后會到主界面，然后選擇2.Writer Priority 后，程序運行結果如下：
６．調試記錄
在編程過程中，沒有設置計數器來存儲讀者數目，結果在程序運行時，產生了讀者與讀者的互斥。之后通過翻閱資料，了解了需要加入計數器來控制讀者與讀者之間的同等優先，同時也用于控制寫者進程的釋放，既當計數器為0的時候，允許寫進程訪問文件。
在加入計數器后，重新編寫程序，就解決了以上問題。當程序通過編譯鏈接之后，運行程序，得到了正確的結果。然后修改文件thread.dat中的參數：
1 R 3 4
2 R 4 3
3 W 4 5
重新對程序進行測試，分別選擇讀者優先和寫者優先，結果正確。
最后修改文件thread.dat中的參數，使用更多的讀寫請求：
1 W 2 5
2 R 3 4
3 W 5 3
4 R 6 5
5 R 7 4
6 W 9 5
7 R 11 4
8 R 14 5
9 W 17 6
10 R 20 5
運行程序的結果都正確。讀者寫者問題程序設計成功。
７．自我評析和總結
課程設計是培養學生綜合運用所學知識,發現,提出,分析和解決實際問題,鍛煉實踐能力的重要環節,是對學生實際工作能力的具體訓練和考察過程.
操作系統的出現，使用和發展是近四十余年來計算機軟件的一個重大進展。操作系統中引入并發程序設計技術后，程序的執行不在是順序的。一個程序未執行完而另一個程序便已開始執行，程序挖補的順序特性消失，程序與計算不再一一對應，所以操作系統引進進程概念來描述這種變化。讀者與寫者問題就是一個經典的并發程序設計問題。
在開始做課程設計時，我首先翻閱了很多關于并發程序的書籍，找到了基本的解決方法，那就是信號量的使用。記錄型信號量和PV操作不僅可以解決進程的互斥，而且更是實現進程同步的有力工具。但是發現光有信號量是解決不了讀者和寫者問題，因為所有讀進程不會相互互斥。所以程序對信號量進行了改進。引入了一個計數器，記錄讀者的數目，控制是否釋放寫者進程。
做到這些，思路已經基本確定。在變成過程中查閱了許多書籍，也對WINDOWS下的一些API做了些了解。
接近2周的課程設計，讓我學到了不少東西，從開始的查閱書籍，確定思路，到最后的編寫程序和調試。設計過程中遇到了不少困難，但在同學和老師的幫助下都一一克服了。
總之，每一次課程設計不僅是我們學習的好機會，而且是我們鍛煉實際動手能力的平臺，雖然有難度的東西總會讓人很抵觸，比如在課設過程中有很多郁悶的時候，一個小小的錯誤一不小心就花去了自己一上午的時間，所以在這個過程中能夠磨練人的意志與耐心，最后感謝老師的指導與監督，使我在課程設計過程中學到了書本是學不到的知識，同時也對操作系統有了更深刻的認識，為以后的學習打下了堅實的基礎。
【基于C++的讀者與寫者問題read—write problem的實現(一】相關文章：
數據加密標準DES的C++實現03-07
基于圖像的OMR技術的實現03-07
基于XMLSchema的元數據方案實現03-21
基于FPGA的HDLC通信模塊的實現05-14
基于Perl的DoS工具設計與實現03-10
基于PQRM的PACS系統設計與實現03-07
一種基于網絡的監控軟件設計與實現11-20