Linux程序设计课程设计 Linux程序设计课程组长春工业大学2017-12-24课程设计任务书目录第1章设计要求 (1)2.1设计目的 (1)2.2设计要求 (1)第2章测试数据设计 (2)第3章算法实现 (3)第4章算法结果 (19)第5章结果可视化 (21)第6章性能分析 (21)参考文献 (22)心得 (22)第1章设计要求2.1设计目的理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。

2.2设计要求在linux环境下编写应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。

读者/写者问题描述如下：有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。

有一些只读取这个数据区的线程（reader）和一些只往数据区中写数据的线程（writer）。

以下假设共享数据区是文件。

这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。

这些条件具体来说就是：（1）任意多的读线程可以同时读这个文件；（2）一次只允许一个写线程往文件中写；（3）如果一个写线程正在往文件中写，禁止任何读线程或写线程访问文件；（4）写线程执行写操作前，应让已有的写者或读者全部退出。

这说明当有读者在读文件时不允许写者写文件。

对于读者-写者问题，有三种解决方法：1、读者优先除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。

这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。

2、写者优先除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。

当一个写者声明想写文件时，不允许新的读者再访问文件。

3、无优先除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。

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

作者设计的测试数据如表1所示，包括10个线程，其中有5个读者线程r1~r5，另外5个是写者线程w1~w5。

读者线程r1在时刻0提出读请求，如果请求得到允许，r1将用15秒的时间读文件；写者线程w3在时刻6提出写请求，如果请求得到允许，w3将用10秒的时间写文件。

从表中可以看出，10个线程提出请求的次序是：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。

（1）读者优先算法线程实际读写文件顺序为：r1,r2,r3,r4,r5,w1,w2,w3,w4,w5。

执行情况见表2。

（2）写者优先算法线程实际读写文件顺序为：r1,r2,w1,w2,w3,w4,w5,r3,r4,r5。

执行情况见表3。

名称时刻时间作时刻作时刻"r1" 0 15 0 15"r2" 1 15 1 16"w1" 3 3 16 19"w2" 5 6 19 25"w3" 6 10 25 35"w4" 10 18 35 53"w5" 12 2 53 55"r3" 4 2 55 57"r4" 7 8 55 63"r5" 9 2 55 57（3）无优先算法线程实际读写文件顺序为：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。

执行情况见表4。

第3章算法实现读者优先算法：#include <time.h>#include <stdio.h>#include <unistd.h>#include <stdlib.h>#include <pthread.h>#include <string.h>#include <fcntl.h>#define MAX_THREAD 10#define SNL 8typedef struct{char tn[3]; //name of threadunsigned int rm; //the moment when this thread request to access data.unsigned int pt; //duration of operationunsigned int i; //same to rmunsigned int b; //instance at which this thread begin to operate data unsigned int e; //ending instance}TEST_INFO;//TEST_INFO test_data[MAX_THREAD];typedef struct {char sn[SNL+1]; //student numberTEST_INFO ti[MAX_THREAD]; //test item}TI; //test_item_for_student//TI test_items[STUDENTS];TI test_item={{"20152566"},{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8}, {"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}};char r_seq[MAX_THREAD][3];char o_seq[MAX_THREAD][3];int sr=0;int so=0;int rc=0; //count how many readers are readingpthread_mutex_t cs_d; //guarentee mutually access datapthread_mutex_t cs_rc; //guarentee mutually access "rc"pthread_mutex_t cs_sr; //guarentee mutually access "sr"pthread_mutex_t cs_so; //guarentee mutually access "sr"time_t base; //the moment when function main begin/*void print_answer(){int i;printf("%s\n",test_item.sn);printf("name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test _item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}printf("r_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",r_seq[i]);}printf("\n");printf("o_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",o_seq[i]);}printf("\n");}*/void save_answer(FILE *f){int i;fprintf(f,"\t%s_answer.txt\n\tr/w problem:read first\n\n",test_item.sn);fprintf(f,"name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(t est_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}fprintf(f,"\n");fprintf(f,"r_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",r_seq[i]);}fprintf(f,"\n");fprintf(f,"o_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",o_seq[i]);}fprintf(f,"\n");}void *r(void *td){struct timeval t;time_t rl=base;sleep(((TEST_INFO *)td)->rm); gettimeofday(&t,NULL);((TEST_INFO *)td)->i=difftime(_sec,rl); pthread_mutex_lock(&cs_sr);strcpy(r_seq[sr++],((TEST_INFO *)td)->tn); pthread_mutex_unlock(&cs_sr);pthread_mutex_lock(&cs_rc);rc++;if(rc==1)pthread_mutex_lock(&cs_d); pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);((TEST_INFO *)td)->b=difftime(_sec,rl); pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn); pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt); gettimeofday(&t,NULL);((TEST_INFO *)td)->e=difftime(_sec,rl);pthread_mutex_lock(&cs_rc);rc--;if(rc==0)pthread_mutex_unlock(&cs_d); pthread_mutex_unlock(&cs_rc);return 0;}void *w(void *td){struct timeval t;time_t wl=base;sleep(((TEST_INFO *)td)->rm); gettimeofday(&t,NULL);((TEST_INFO *)td)->i=difftime(_sec,wl); pthread_mutex_lock(&cs_sr);strcpy(r_seq[sr++],((TEST_INFO *)td)->tn); pthread_mutex_unlock(&cs_sr);pthread_mutex_lock(&cs_d); gettimeofday(&t,NULL);((TEST_INFO *)td)->b=difftime(_sec,wl); pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn); pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt); gettimeofday(&t,NULL);((TEST_INFO *)td)->e=difftime(_sec,wl);pthread_mutex_unlock(&cs_d);return 0;}void create_exam(){int i=0;pthread_t ht[MAX_THREAD];pthread_mutex_init(&cs_d,NULL);pthread_mutex_init(&cs_rc,NULL);pthread_mutex_init(&cs_sr,NULL);pthread_mutex_init(&cs_so,NULL);struct timeval t;gettimeofday(&t,NULL);base=_sec;for(i=0;i<MAX_THREAD;i++){if((test_item.ti)[i].tn[0]=='r'){pthread_create(&ht[i],NULL,r,&((test_item.ti)[i]));}else if((test_item.ti)[i].tn[0]=='w'){pthread_create(&ht[i],NULL,w,&((test_item.ti)[i]));}}for(i=0;i<MAX_THREAD;i++){pthread_join(ht[i],NULL);}pthread_mutex_destroy(&cs_d);pthread_mutex_destroy(&cs_rc);pthread_mutex_destroy(&cs_sr);pthread_mutex_destroy(&cs_so);}int main(int argc,char *argv[]){int i=0;int si,pos;int fd;FILE *fa;char file_name[100];create_exam();sprintf(file_name,"%s_answer.txt",test_item.sn);if((fa=fopen(file_name,"w"))==NULL){printf("Error openning answer file:%s\n",file_name);exit(3);}save_answer(fa);exit(0);}1.写优先算法#include <time.h>#include <stdio.h>#include <unistd.h>#include <stdlib.h>#include <pthread.h>#include <string.h>#include <fcntl.h>#define MAX_THREAD 10#define SNL 8typedef struct{char tn[3]; //name of threadunsigned int rm; //the moment when this thread request to access data.unsigned int pt; //duration of operationunsigned int i; //same to rmunsigned int b; //instance at which this thread begin to operate dataunsigned int e; //ending instance}TEST_INFO;//TEST_INFO test_data[MAX_THREAD];typedef struct {char sn[100]; //student numberTEST_INFO ti[MAX_THREAD]; //test item}TI; //test_item_for_student//TI test_items[STUDENTS];TI test_item={{"20152566"},{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8}, {"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}};char r_seq[MAX_THREAD][3];char o_seq[MAX_THREAD][3];int sr=0;int so=0;int rc=0; //count how many readers are readingpthread_mutex_t cs_d; //guarentee mutually access datapthread_mutex_t cs_rc; //guarentee mutually access "rc"pthread_mutex_t cs_sr; //guarentee mutually access "sr"pthread_mutex_t cs_so; //guarentee mutually access "sr"time_t base; //the moment when function main begin/*void print_answer(){int i;printf("%s\n",test_item.sn);printf("name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test _item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}printf("r_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",r_seq[i]);}printf("\n");printf("o_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",o_seq[i]);}printf("\n");}*/void save_answer(FILE *f){ //save the resultint i;fprintf(f,"\t%s_answer.txt\n\tr/w problem:read first\n\n",test_item.sn);fprintf(f,"name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(t est_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}fprintf(f,"\n");fprintf(f,"r_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",r_seq[i]);}fprintf(f,"\n");fprintf(f,"o_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",o_seq[i]);}fprintf(f,"\n");}void *w(void *td){struct timeval t;//结构体精确到秒time_t rl=base; //返回时间main函数开始的时间sleep(((TEST_INFO *)td)->rm);//休眠读线程进入的时间长gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->i=difftime(_sec,rl);//将系统时间与main主函数执行的时间差赋值给i变量（读线程进入的时间）pthread_mutex_lock(&cs_sr);//建立互斥锁strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);pthread_mutex_unlock(&cs_sr);//解除互斥锁pthread_mutex_lock(&cs_rc);rc++;if(rc==1)pthread_mutex_lock(&cs_d);pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->b=difftime(_sec,rl);//将系统时间与main主函数执行的时间差赋值给b变量（读线程开始的时间）pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn);//将读线程名复制给0_seq队列pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt);//休眠写进程持续的时间长gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->e=difftime(_sec,rl);//pthread_mutex_lock(&cs_rc);rc--;if(rc==0)pthread_mutex_unlock(&cs_d);pthread_mutex_unlock(&cs_rc);return 0;}void *r(void *td){struct timeval t;time_t wl=base;sleep(((TEST_INFO *)td)->rm);//休眠写进程进入的时间长gettimeofday(&t,NULL);((TEST_INFO *)td)->i=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给i变量（写线程进入的时间）pthread_mutex_lock(&cs_sr);//建立互斥锁strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);// 将写线程名复制给r_seq队列pthread_mutex_unlock(&cs_sr);//解除互斥锁pthread_mutex_lock(&cs_d);gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->b=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给b变量（写线程开始的时间）pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn);// 将写线程名复制给o_seq队列pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt);//休眠写进程持续的时间长gettimeofday(&t,NULL);//获取当前的时间((TEST_INFO *)td)->e=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给e变量（写线程结束的时间）pthread_mutex_unlock(&cs_d);return 0;}void create_exam(){int i=0;pthread_t ht[MAX_THREAD];pthread_mutex_init(&cs_d,NULL);//初始化互斥锁pthread_mutex_init(&cs_rc,NULL);pthread_mutex_init(&cs_sr,NULL);pthread_mutex_init(&cs_so,NULL);struct timeval t;gettimeofday(&t,NULL);base=_sec;for(i=0;i<MAX_THREAD;i++){//分别创建读写线程的初始化if((test_item.ti)[i].tn[0]=='r'){pthread_create(&ht[i],NULL,r,&((test_item.ti)[i]));}else if((test_item.ti)[i].tn[0]=='w'){pthread_create(&ht[i],NULL,w,&((test_item.ti)[i]));}}for(i=0;i<MAX_THREAD;i++){pthread_join(ht[i],NULL);}pthread_mutex_destroy(&cs_d);//销毁互斥锁pthread_mutex_destroy(&cs_rc);pthread_mutex_destroy(&cs_sr);pthread_mutex_destroy(&cs_so);}int main(int argc,char *argv[]){int i=0;int si,pos;int fd;FILE *fa;char file_name[100];create_exam();sprintf(file_name,"%s_answer.txt",test_item.sn);//从文件中读取if((fa=fopen(file_name,"w"))==NULL){printf("Error openning answer file:%s\n",file_name);exit(3);}save_answer(fa);exit(0);}2.无优先算法#include <time.h>#include <stdio.h>#include <unistd.h>#include <stdlib.h>#include <pthread.h>#include <string.h>#include <fcntl.h>#define MAX_THREAD 10#define SNL 8typedef struct{char tn[3]; //name of threadunsigned int rm; //the moment when this thread request to access data.unsigned int pt; //duration of operationunsigned int i; //same to rmunsigned int b; //instance at which this thread begin to operate dataunsigned int e; //ending instance}TEST_INFO;//TEST_INFO test_data[MAX_THREAD];typedef struct {char sn[100]; //student numberTEST_INFO ti[MAX_THREAD]; //test item}TI; //test_item_for_student//TI test_items[STUDENTS];TI test_item={{"20152566"},{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8},{"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}};char r_seq[MAX_THREAD][3];char o_seq[MAX_THREAD][3];int sr=0;int so=0;int rc=0; //count how many readers are readingpthread_mutex_t cs_d; //guarentee mutually access datapthread_mutex_t cs_rc; //guarentee mutually access "rc"pthread_mutex_t cs_sr; //guarentee mutually access "sr"pthread_mutex_t cs_so; //guarentee mutually access "sr"time_t base; //the moment when function main begin/*void print_answer(){int i;printf("%s\n",test_item.sn);printf("name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test _item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}printf("r_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",r_seq[i]);}printf("\n");printf("o_seq:");for(i=0;i<MAX_THREAD;i++){printf("%4s",o_seq[i]);}printf("\n");}*/void save_answer(FILE *f){ //save the resultint i;fprintf(f,"\t%s_answer.txt\n\tr/w problem:read first\n\n",test_item.sn);fprintf(f,"name r_m p_t i_t b_t e_t\n");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(t est_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);}fprintf(f,"\n");fprintf(f,"r_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",r_seq[i]);}fprintf(f,"\n");fprintf(f,"o_seq:");for(i=0;i<MAX_THREAD;i++){fprintf(f,"%4s",o_seq[i]);}fprintf(f,"\n");}void *r(void *td){struct timeval t;//结构体精确到秒time_t rl=base; //返回时间main函数开始的时间sleep(((TEST_INFO *)td)->rm);//休眠读线程进入的时间长gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->i=difftime(_sec,rl);//将系统时间与main主函数执行的时间差赋值给i变量（读线程进入的时间）pthread_mutex_lock(&cs_sr);//建立互斥锁strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);pthread_mutex_unlock(&cs_sr);//解除互斥锁pthread_mutex_lock(&cs_rc);rc++;if(rc==1)pthread_mutex_lock(&cs_d);pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->b=difftime(_sec,rl);//将系统时间与main主函数执行的时间差赋值给b变量（读线程开始的时间）pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn);//将读线程名复制给0_seq队列pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt);//休眠写进程持续的时间长gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->e=difftime(_sec,rl);//pthread_mutex_lock(&cs_rc);rc--;if(rc==0)pthread_mutex_unlock(&cs_d);pthread_mutex_unlock(&cs_rc);return 0;}void *w(void *td){struct timeval t;time_t wl=base;sleep(((TEST_INFO *)td)->rm);//休眠写进程进入的时间长gettimeofday(&t,NULL);((TEST_INFO *)td)->i=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给i变量（写线程进入的时间）pthread_mutex_lock(&cs_sr);//建立互斥锁strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);// 将写线程名复制给r_seq队列pthread_mutex_unlock(&cs_sr);//解除互斥锁pthread_mutex_lock(&cs_d);gettimeofday(&t,NULL);//获得当前的时间((TEST_INFO *)td)->b=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给b变量（写线程开始的时间）pthread_mutex_lock(&cs_so);strcpy(o_seq[so++],((TEST_INFO *)td)->tn);// 将写线程名复制给o_seq队列pthread_mutex_unlock(&cs_so);sleep(((TEST_INFO *)td)->pt);//休眠写进程持续的时间长gettimeofday(&t,NULL);//获取当前的时间((TEST_INFO *)td)->e=difftime(_sec,wl);//将系统时间与main主函数执行的时间差赋值给e变量（写线程结束的时间）pthread_mutex_unlock(&cs_d);return 0;}void create_exam(){int i=0;pthread_t ht[MAX_THREAD];pthread_mutex_init(&cs_d,NULL);//初始化互斥锁pthread_mutex_init(&cs_rc,NULL);pthread_mutex_init(&cs_sr,NULL);pthread_mutex_init(&cs_so,NULL);struct timeval t;gettimeofday(&t,NULL);base=_sec;for(i=0;i<MAX_THREAD;i++){//分别创建读写线程的初始化pthread_create(&ht[i],NULL,r,&((test_item.ti)[i]));}for(i=0;i<MAX_THREAD;i++){pthread_join(ht[i],NULL);}pthread_mutex_destroy(&cs_d);//销毁互斥锁pthread_mutex_destroy(&cs_rc);pthread_mutex_destroy(&cs_sr);pthread_mutex_destroy(&cs_so);}int main(int argc,char *argv[]){int i=0;int si,pos;int fd;FILE *fa;char file_name[100];create_exam();sprintf(file_name,"%s_answer.txt",test_item.sn);//从文件中读取if((fa=fopen(file_name,"w"))==NULL){printf("Error openning answer file:%s\n",file_name);exit(3);}save_answer(fa);exit(0);}第4章算法结果读者优先写者无优先第5章结果可视化第6章性能分析1.读优先等待时间=b_t-i_t=99平均等待时间=9.9周转时间=e_t-i_t=170平均周转时间=17带权周转时间=周转时间/p_t=15.15带权平均周转时间=1.5152.写优先等待时间=b_t-i_t=127平均等待时间=12.7周转时间=e_t-i_t=208平均周转时间=20.8带权周转时间=周转时间/p_t=带权平均周转时间=2.423.无优先\等待时间=b_t-i_t=41+4+18+0+20+9+30+2+13=周转时间=e_t-i_t=56+10+31+3+20+16+43+6+20=带权周转时间=周转时间/p_t=56/15+13/6+40/13+3/3+27/0+20/7+53/13+7/4+27/10=参考文献GNU/Linux编程心得这次的实验课程设计可以说的上是正规的解决问题的案例了。